The Simple Method of Bounded Differences in Action
In this chapter we shall see the “method of bounded differences”, namely, Corollary 5.2 in action by applying it to various examples of increasing sophistication.
6.1 Chernoff–Hoeffding Revisited
Let X1, . . . , Xn be independent variables taking values in [0, 1], and consider f(x1, . . . , xn) := ∑i xi. Then, of course, f has the Lipschitz property with each di = 1 in (5.9), and by Corollary 5.2, we get for X := X1 + · · · + Xn the classical Chernoff–Hoeffding bound
6.2 Stochastic Optimisation: Bin Packing
The bin-packing problem is a well-studied combinatorial optimisation problem: we are ...