## 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

6

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 ...

## 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