Concentration of Measure

Devdatt Dubhashi and Alessandro Panconesi have a first draft of a monograph on concentration of measure, essentially the study of tail bounds for random variables: given a random variable X, how does it deviate from E[X] ?

Their goal is to write a "user-friendly" guide to measure concentration. From the preface:

Our main goal here is to give an exposition of the basic methods for measure concentration in a manner which makes it accessible to the researcher in randomized algorithms and enables him/her to quickly start putting them to work in his/her application.

The book starts with the basic Chernoff-Hoeffding bounds and variants. It then delves deeper into "more recent" technology like Azuma's inequality, martingales, the method of bounded differences, and more. Talagrand's inequality comes next, followed by the log-Sobolev inequality.

What the draft does really well is connect the dots between the techniques and how they are applied. With exercises, problems, and worked-out examples, it is an excellent text for a course, or even as a companion text in a course. I should add that it is very well written; balancing exposition and rigor at the level that I like (your mileage may vary).

It's a book that's really needed. There are a lot of sophisticated methods for analyzing tail bounds, and a text written like this can potentially make martingales and Talagrand's inequality the kind of as-natural-as-breathing analysis tools that Chernoff bounds currently are.

Now I can only hope the authors manage to finish the draft. Maybe if you like the manuscript you should email them with encouragement !

Categories

• books
• probability