Automatically generated from handwritten notes — tailbounds.pdf

Efficient AI · Lecture notes

Tail bounds

A ladder of deviation bounds: start with the mean, add variance, then use moment generating functions to get exponentially small bounds for sums of independent Bernoulli variables.

Roadmap
  1. Why tail probabilities?
  2. Markov’s inequality
  3. Chebyshev’s inequality
  4. Moment generating functions
  5. Chernoff bounds
  6. Poisson trials and the binomial example
Main story We repeatedly ask the same question: how large can $\Pr(X \ge a)$ be, given limited information about $X$?

1. Why tail probabilities?

Randomized algorithms — and randomized proposals for compression — need probabilistic analysis. Typical random variables of interest:

We need a way to understand how large these quantities can become. Instead of asking for the exact distribution of $X$, we often only ask for an upper bound on a tail probability such as $\Pr(X \ge a)$.

upper bound true prob. $a$
Goal: bound the shaded tail by something computable.
$\Pr(X \ge a) \le$ (some upper bound).
Two regimes If the distribution of $X$ is known and easy to analyze, use $1 - F(a)$. Otherwise, use tail bounds that depend only on moments / MGFs.

Running example throughout: independent coin tosses (Bernoulli / Poisson trials)

\[ X = X_1 + X_2 + \dots + X_n, \qquad X_i \sim \mathrm{Bern}(p_i). \]
Question. What is $\Pr(\#\text{heads} \ge 3n/4)$? If all $p_i$ are equal, this is binomial. If the $p_i$ differ, exact manipulation is less convenient — but the same bounds still apply.

2. Markov’s inequality

The weakest useful information about a nonnegative random variable is its expectation. Markov’s inequality says that even this alone limits how much probability mass can sit far out in the tail.

Question. What can you say about the tail if you know only the expectation $E(X)$?
\[ \Pr(X \ge a) \;\le\; \frac{E(X)}{a} \qquad\text{if $X$ is nonnegative.} \]

Intuition

Fix $\mu = E(X)$ and $X \ge 0$. To maximize $\Pr(X \ge a)$ under this mean constraint, push mass to the extremes: put mass $1-p$ at $0$ and mass $p$ at $a$. Then $ap=\mu$, so $p=\mu/a$. That worst-case probability is exactly Markov’s bound.

Proof

\[ E(X) = \sum_x x\,\Pr(x) = \underbrace{\sum_{x \lt a} x\,\Pr(x)}_{\ge 0} + \sum_{x \ge a} x\,\Pr(x) \;\ge\; a\,\Pr(X \ge a). \]

Divide by $a > 0$ to finish.

Tightness Yes — equality is achieved by the two-point distribution above (mass at $0$ and $a$).

Binomial example (Markov)

Take unbiased coins: $E(X)=np=n/2$. Then

\[ \Pr\!\left(X \ge \tfrac{3n}{4}\right) \;\le\; \frac{n/2}{3n/4} = \tfrac{2}{3}. \]

This is a constant bound. It is valid with very little information, but it does not improve as $n$ grows. To get decay with $n$, we need more information than just the mean.

3. Chebyshev’s inequality

The next piece of information is the variance. It measures how much $X$ typically deviates from its mean. Variance is the centered second moment: $\mathrm{Var}(X)=E((X-\mu)^2)=E(X^2)-E(X)^2$.

\[ \Pr(|X-\mu| \ge a) = \Pr\bigl((X-\mu)^2 \ge a^2\bigr) \;\le\; \frac{E((X-\mu)^2)}{a^2} = \frac{\mathrm{Var}(X)}{a^2}. \]

Proof: apply Markov to $Y=(X-\mu)^2 \ge 0$.

Tightness

Equality is achievable. Take a three-point law for $X-\mu$:

Then $E((X-\mu)^2)=a^2 p$, and Chebyshev’s bound is tight for this $Y$. (Equivalently: $X=\mu$, $\mu-a$, $\mu+a$ with probabilities $1-v$, $v/2$, $v/2$.)

Binomial example (Chebyshev)

For $X_i\sim\mathrm{Bern}(1/2)$: $E(X)=n/2$, $\mathrm{Var}(X)=n/4$.

\[ \Pr\!\left(\left|X-\tfrac{n}{2}\right| \ge \tfrac{n}{4}\right) \;\le\; \frac{n/4}{(n/4)^2} = \frac{4}{n}. \]

This is the bound Chebyshev actually gives (two-sided). For the one-sided event $X \ge 3n/4$, the notes write $\tfrac{4}{n}\cdot\tfrac12=\tfrac{2}{n}$ by symmetry — that is a heuristic, not a consequence of Chebyshev alone. Either way we already improve from Markov’s constant $2/3$ to an $O(1/n)$ guarantee.

Higher moments Chebyshev is Markov applied to a squared deviation. The same trick can use higher even powers: \[ \Pr(|X-\mu|\ge a) \;\le\; \frac{E\bigl((X-\mu)^{2k}\bigr)}{a^{2k}}. \] Larger $k$ often improves the bound when those moments exist, but this is not automatic for every distribution and threshold.

4. Moment generating functions

Instead of choosing one moment at a time, Chernoff bounds package exponential moments into one object: the moment generating function.

\[ M_X(t) = E(e^{tX}). \]

We mainly care that $M_X(t)$ exists in a neighborhood of $t=0$. Differentiating under the expectation (under mild conditions),

\[ M_X^{(r)}(t) = E(X^r e^{tX}), \qquad M_X^{(r)}(0) = E(X^r). \]

Thus the derivatives of the MGF at zero recover the moments of $X$. We use $r$ for derivative order here to avoid confusing it with the number of Bernoulli trials $n$.

Uniqueness If $M_X(t)=M_Y(t)$ for all $t\in(-\delta,\delta)$ for some $\delta > 0$, then $X$ and $Y$ have the same distribution. Matching all moments alone is not enough in general (there are distinct laws with identical moment sequences); the neighborhood-of-zero MGF hypothesis is the right sufficient condition.
\[ \text{If $X,Y$ independent:} \quad M_{X+Y}(t) = M_X(t)\, M_Y(t). \]

5. Chernoff bounds

The Chernoff trick is simple: exponentiate $X$, apply Markov to the nonnegative random variable $e^{tX}$, and then choose the best $t$. The sign of $t$ selects which tail we control.

Upper tail ($t > 0$)

\[ \Pr(X \ge a) = \Pr(e^{tX} \ge e^{ta}) \;\le\; \frac{E[e^{tX}]}{e^{ta}} = \frac{M_X(t)}{e^{ta}}. \]

This holds for every $t > 0$, so we may optimize:

\[ \Pr(X \ge a) \;\le\; \min_{t > 0} \frac{M_X(t)}{e^{ta}}. \]

Lower tail ($t < 0$)

The same calculation with $t < 0$ bounds $\Pr(X \le a)$, again minimizing $M_X(t)/e^{ta}$ over $t < 0$.

Takeaway More information about $X$ (mean $\to$ variance $\to$ MGF) yields better analytic tail bounds. Chernoff is the MGF-optimized Markov bound.

6. Poisson trials and the binomial example

Now specialize to independent Bernoulli variables. This is the setting where Chernoff becomes especially useful: independence makes the MGF of the sum factor into a product.

\[ X=\sum_{i=1}^n X_i, \qquad X_i\in\{0,1\}, \qquad \Pr(X_i=1)=p_i, \qquad \mu=\sum_i p_i. \]

MGF bound

\[ \begin{aligned} M_X(t) &= \prod_i E(e^{tX_i}) = \prod_i\bigl(1 + p_i(e^t-1)\bigr) \\ &\le \prod_i e^{(e^t-1)p_i} = e^{(e^t-1)\mu}, \end{aligned} \]

using $1+x \le e^x$.

Theorem (multiplicative Chernoff)

Plugging the MGF bound into the optimized Markov bound gives the following standard upper-tail forms.

  1. For any $\delta > 0$, \[ \Pr\bigl(X \ge (1+\delta)\mu\bigr) \lt \left( \frac{e^\delta}{(1+\delta)^{1+\delta}} \right)^{\!\mu}. \]
  2. For $0 < \delta < 1$, \[ \Pr\bigl(X \ge (1+\delta)\mu\bigr) \;\le\; e^{-\mu \delta^2 / 3}. \]
  3. For $R \ge 6\mu$, \[ \Pr(X \ge R) \;\le\; 2^{-R}. \]

Proof sketch of (1)

\[ \Pr\bigl(X \ge (1+\delta)\mu\bigr) \;\le\; \frac{E[e^{tX}]}{e^{t(1+\delta)\mu}} \;\le\; \frac{e^{(e^t-1)\mu}}{e^{t(1+\delta)\mu}}. \]

Choose $t=\ln(1+\delta)$ (with $\delta > 0$) to obtain

\[ \left( \frac{e^\delta}{(1+\delta)^{1+\delta}} \right)^{\!\mu}. \]

Special cases

Back to the binomial question

Unbiased coins: $\mu=n/2$. The event $X\ge 3n/4$ is $X\ge(1+\delta)\mu$ with $\delta=1/2$. Bound (2) gives

\[ \Pr\!\left(X \ge \tfrac{3n}{4}\right) \;\le\; e^{-\mu \delta^2 / 3} = e^{-(n/2)\,(1/4)\,/\,3} = e^{-n/24}. \]
Exponential bound: $\displaystyle e^{-n/24}$

Compare: Markov $\le 2/3$, Chebyshev $\le O(1/n)$, Chernoff $\le e^{-\Theta(n)}$. More structure $\Rightarrow$ sharper tails.

Standard reference: Mitzenmacher and Upfal, Probability and Computing, Chapters 3–4.