**1**

**Chernoff–Hoeffding Bounds**

**1.1 What Is “Concentration of Measure”?**

The basic idea of concentration of measure is well illustrated by the simplest of random experiments, and one lying at the fountainhead of probability theory: coin tossing. If we toss a fair coin once, the result is completely unpredictable – it can be “heads” or “tails” with equal probability. Now suppose that we toss the same coin a large number of times, say, a thousand times. The outcome is now *sharply predictable*! Namely, the number of heads is “very likely to be around 500”. This apparent paradox, which is nevertheless familiar to everybody, is an instance of the phenomenon of the concentration of measure – although there are potentially a large number of possibilities, ...

Start Free Trial

No credit card required