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

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.

No credit card required