Abstract:
The Chernoff Bounds. Flipping $n$ fair coins and counting Heads minus Tails one naturally gets a limiting Gaussian distribution. But here we are concerned with extremely small probabilities, e.g., that there are $n^{2/3}$ more heads than tails. This general method gives good upper bounds on the probability of a random variable $X$ being more than $\alpha$ standard deviations off the mean, when $\alpha$ is “large” and $X$ is the sum of mutually independent random variables.
A variety of applications are given. One example: there exist tournaments $T$ on n players so that no matter how the players are orders nearly half the games will be upsets.
