O'Reilly logo

Concentration of Measure for the Analysis of Randomized Algorithms by Alessandro Panconesi, Devdatt P. Dubhashi

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

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

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

Start Free Trial

No credit card required