Lecture 9: Large-Deviation Bounds

We saw the statement and proof of some very useful large-deviation bounds (showing that the random variable $S_n = \sum_{i = 1}^n X_i$ does not deviate much from its mean) a.k.a. concentration bounds (the r.v. is “concentrated” around the mean) a.k.a. tail bounds (which bound the probability in the tail of the distribution). The most general bounds we saw said that for independent random variables $X_i \in [0,1]$ with mean $p_i$, the random variable $S_n = \sum_i X_i$ (with mean $\mu = \sum_i p_i$) satisfies the upper-tail bound of

$$\Pr[ S_n \geq \mu + \lambda ] \leq \exp\left\{- \frac{\lambda^2}{2\mu + \lambda}\right\},$$

and for the lower-tail, a bound of:

$$\Pr[ S_n \leq \mu - \lambda ] \leq \exp\left\{- \frac{\lambda^2}{3\mu}\right\}.$$

One small thing to mention: mid-way through the derivation of the bound, we’d said:

$$\Pr[ S_n \geq \mu + \lambda ] \leq \exp\{ - (\mu + \lambda) \log (1 + \lambda/\mu) + \lambda \}.$$

We drew a box around this and mentioned it was useful (after which we simplified it to get the upper tail bound expression above). But we didn’t get back to it. Let’s do that now.

If we set $\lambda = \beta\mu$, then the bound can be simplified and written as:

$$\Pr[ S_n \geq (1+\beta)\mu ] \leq \left( \frac{e^\beta}{(1+\beta)^{1+\beta}} \right)^\mu.$$

This bound is sometimes more powerful than the generic upper-tail bound mentioned at the top above, and hence worth noting.

Let’s see an example. Consider the case of $n$ balls and $n$ bins: the expected load of any fixed bin is $1$, and we saw that the probability that this load is more than $O(\log n)$ is at most $1/n^2$. But if we use this expression we just noted, with $\beta = O(\frac{\log n}{\log \log n})$, then $(1+\beta)^{1+\beta}$ becomes $n^{O(1)}$. However, the numerator is only $e^\beta$, which is asymptotically smaller. And since $\mu = 1$, putting it all together tells us that the load of any fixed bin is more than $\beta$ with probability at most $1/n^2$. Union bounding over all $n$ bins means that $L_{\max}$, the load of the most loaded bin is also at most $\beta = O(\frac{\log n}{\log \log n})$ with high probability.

Indeed, this is the right answer: with $n$ balls and $n$ bins, the max load is indeed $\Theta(\frac{\log n}{\log \log n})$. We just saw the upper bound using a Chernoff bound followed by a trivial union bound over all $n$ bins. The lower bound can be proved using a “second-moment” calcuation. See the first two pages here for more details (and an alternate proof of the upper bound).