O'Reilly logo

Concentration of Measure for the Analysis of Randomized Algorithms by Alessandro Panconesi, Devdatt P. Dubhashi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

5

Martingales and the Method of Bounded Differences

The Chernoff–Hoeffding bounds provide very sharp concentration estimates when the random variable X under consideration can be expressed as the sum X = X1 + · · · + Xn of independent and bounded random variables. However in many applications, to do this might be very difficult or impossible. It would therefore be useful to obtain sharp concentration results for the case when X is some complicated function of not necessarily independent variables. Such a generalisation would be useful in many diverse contexts but especially in the analysis of randomized algorithms where the parameters that characterise the behaviour of the algorithm are the result of a complicated interaction among a base set ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required