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 ...
No credit card required