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

8

The Method of Bounded Variances

In this chapter we describe a tail bound similar in flavour to the method of bounded differences. This new bound too rests on a martingale inequality similar to Azuma’s. In the previous chapters we saw how, given a function f(X1, . . . , Xn), the strength of the method of bounded differences depends on our ability to bound the absolute increments of the Doob martingale sequence Zi := E[f |X1, . . . , Xi]. In doing this, we would expose the variables X1, . . . , Xn one at a time and consider the expected change of f when Xi is revealed, conditioned on the values of the X1, . . . , Xi−1 exposed so far, and take the maximum value among all assignments to the first i − 1 variable. That is, we would look for a bound ...

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