\documentclass[12pt]{article} \usepackage{wide,me} \parindent0pt
$$\newcommand{\indx}{{\it index}}$$

## Chernoff Bound

Intro

• Markov: $\Pr[f(X) > z] < E[f(X)]/z$.
• Chebyshev used $X^2$ in $f$
• other functions yield other bounds
• Chernoff most popular

Theorem:

• Let $X_i$ poisson (ie independent 0/1) trials, $E[\sum X_i]=\mu$ $\Pr[X > (1+\epsilon) \mu ] < \left[ \frac{e^\epsilon}{(1+\epsilon)^{(1+\epsilon)}}\right]^\mu.$
• note independent of $n$
• and exponential in $\mu$, base $< 1$.

Proof.

• For any $t>0$, $$\begin{eqnarray*} \Pr[X > (1+\epsilon)\mu] &= &\Pr[\exp(tX) > \exp(t(1+\epsilon)\mu)]\\ &< &\frac{E[\exp(tX)]}{\exp(t(1+\epsilon)\mu)} \end{eqnarray*}$$
• Use independence. $$\begin{eqnarray*} E[\exp(tX)] &= &\prod E[\exp(tX_i)]\\ E[\exp(tX_i)] &= &p_ie^t+(1-p_i) \\ &= &1+p_i(e^t-1)\\ &\le &\exp(p_i(e^t-1)) \end{eqnarray*}$$ $\prod \exp(p_i(e^t-1)) = \exp(\mu(e^t-1))$
• So overall bound is $\frac{\exp((e^t-1)\mu)}{\exp(t(1+\epsilon)\mu)}$ True for any $t$. To minimize, plug in $t=\ln(1+\epsilon)$.
• Simpler bounds:
• less than $e^{-\mu\epsilon^2/(2+\epsilon)}$ for all $\epsilon$ (because $\ln(1+\epsilon) < 2\epsilon/(1+\epsilon)$)
• less than $e^{-\mu\epsilon^2/3}$ for $\epsilon < 1$
• less than $e^{-\mu \epsilon^2/4}$ for $\epsilon < 2e-1$.
• Less than $2^{-(1+\epsilon)\mu}$ for larger $\epsilon$.
• By same argument on $\exp(-tX)$, $\Pr[X < (1-\epsilon)\mu] < \left[ \frac{e^{-\epsilon}}{(1-\epsilon)^{(1-\epsilon)}}\right]^\mu$ bound by $e^{-\epsilon^2/2}$.
General observations:
• Bound trails off when $\epsilon \approx 1/\sqrt{\mu}$, ie absolute error $\sqrt{\mu}$
• no surprise, since standard deviation is around $\mu$ (recall chebyshev)
• If $\mu = \Omega(\log n)$, probability of constant $\epsilon$ deviation is $O(1/n)$, Useful if polynomial number of events.
• Note similarity to to Gaussian distribution.
• Generalizes: bound applies to any vars distributed in range $[0,1]$.
Zillions of Chernoff applications.

### Alternative Proof by Van Vu

Theorem:
• Let $X_i$ be discrete independent r.v.'s
• with $E[X_i]=0$
• and $|X_i|\le 1$.
• Let $X=\sum X_i$
• and $\sigma^2$ be variance of $X$. Then $\Pr[|X| \ge \lambda \sigma] \le 2e^{-\lambda^2/4}$

Proof:

• Prove upper tail and double by applying to $-X$
• Moment trick: $\Pr[X \ge \lambda \sigma] \le E[e^{tX}/e^{t\lambda\sigma}]$
• Bound $e^{tZ}$ when $t\le 1$ and $|Z|\le 1$ and $E[Z]=0$ (i.e. $Z=X_i$) \begin{align*} E[e^{tZ}] &= \sum p_j e^{tz_j}\\ &= \sum p_j(1+tz_j+(tz_j)^2/2!+(tz_j)^3/3!\cdots)\\ &= \sum p_j + \sum p_jtz_j + \sum p_j((tz_j)^2/2!+(tz_j)^3/3!\cdots)\\ &\le 1+t\dot 0+\sum p_j(tz_j)^2(1/2!+1/3!+\dots )\\ &\le 1+t^2\sum p_j(z_j)^2(e-2)\\ &\le 1+t^2 E[Z^2]\\ &=1+t^2\sigma_Z^2\\ &\le e^{t^2\sigma_Z^2} \end{align*}
• Then \begin{align*} E[e^{tX}] &= \prod E[e^{tX_i}]\\ &\le \prod e^{t^2\sigma_{X_i}^2}\\ &=e^{t_2\sigma_X^2} \end{align*}
• So, overall bounds at most $e^{t^2\sigma^2}/e^{t\lambda\sigma} = e^{t\sigma(t\sigma-\lambda)}$
• optimize at $t=\lambda/2\sigma$ (which must be $< 1$ to work)