Chernoff Bound

Exponential Transform

• Why exponential transform $t\mapsto e^{\lambda t}$?
  • Nice behavior under independent summations
    • $\psi (\lambda )$ is smooth and convex in $\lambda$; the dual ${\psi }^{\ast }(t)$ is convex

Chernoff Bounds

Assuming zero mean, if the MGF $\mathbb{E}{e}^{sX}<\infty$ for some $s\in [0,c]$, then for any $a>0$,

$$\mathbb{P}(S_n\ge an)\le e^{-\psi (a)n},$$

where $S_n={\sum }_i{X}_i$ and $\psi (a)={\sup }_{s\ge 0}(as-\log M_X(s))$.

$\psi$ is called the large deviation rate function.

Proof

By monotonicity and Markov Inequality,

$$\mathbb{P}(S_n>an)=\mathbb{P}(e^{s{S}_n}>e^{san})\le e^{-san}\mathbb{E}[e^{s{S}_n}]=\exp (-san+n\log M_{X_1}(s))\le \exp (-n\psi (a)).$$

Exponential Decay

The positivity of $\psi (a)$ gives the exponential decay of the tail of the distribution. To see the positivity, let $h(s)=as-\log M_X(s)$. Then,

$$h(0)=0,h^{\prime }(0)=a-\mathbb{E}[X]=a>0.$$

Therefore, $\psi (a)>h(0)=0$.

Example - Gaussian

The MGF of a standard normal r.v. is $M_X(t)=e^{t^2/2}$, which gives $h(s)=as-s^2/2$, and thus $\psi (a)=a^2/2$, and thus $\mathbb{P}(s_n\ge an)\le \exp (-n{a}^2/2)$.

Large Deviation Principle

For a sum of i.i.d. random variables $X_i$, the large deviation principle states that for any $a>0$, we have

$$\underset{n\to \infty }{\lim }\frac{1}{n}\log \mathbb{P}(S_n\ge an)=-\psi (a).$$

That is, the Chernoff bound is also a lower bound and hence tight.

Simplified Proof

Assume the following regularity conditions

1. $M_X$ is finite on $\mathbb{R}$
2. $X$ is continuous with PDF $f$
3. $F_X(t)\in (0,1)$ on $\mathbb{R}$, i.e., $X$ is not bounded above or below

The first condition implies that $M_X$ is differentiable on $\mathbb{R}$ (see Exercise 5 (Interchanging expectation and differentiation)) and the third condition implies ${\lim }_{s\to \infty }\frac{\log M_X(s)}{s}=\infty$ (see Exercise 3).

Note that by ^hgrad and ${\lim }_{s\to \infty }h(s)=-\infty$, we know that $h$ has a maximizer $s^{\ast }\ge 0$ such that $\psi (a)=h(s^{\ast })$ and $h^{\prime }(s^{\ast })=0$, which implies $M^{\prime }(s^{\ast })/M(s^{\ast })=a$.

We define a tilted distribution $Y$ with PDF $g(x)=\frac{e^{s^{\ast }x}}{M(s^{\ast })}f(x)$. We have

$$\mathbb{E}[Y]=\frac{M^{\prime }(s^{\ast })}{M(s^{\ast })}=a.$$

We will show then the probability mass of $S_n$ around $an$ is the “tilted” mass of $\sum Y_i$ around $an$, which approaches 1 by LLN. Specifically, for any $\delta \in (0,a)$, let $B=\left\{(x_1,\dots ,x_n):a-\delta \le \frac{1}{n}{\sum }_i{x}_i\le a+\delta \right\}\in {\mathbb{R}}^n$. We have

$$\begin{array}{rl}P(S_n\ge (a-\delta )n)\ge & P((a+\delta )n\ge S_n\ge (a-\delta )n)\\ =& {\int }_{B}f(x_1)\cdots f(x_n)\mathrm{d}{x}_1\cdots \mathrm{d}{x}_n\\ =& {\int }_{B}M(s^{\ast }{)}^n{e}^{-s^{\ast }{\sum }_i{x}_i}g(x_1)\cdots g(x_n)\mathrm{d}{x}_1\cdots \mathrm{d}{x}_n\\ \ge & {\int }_{B}M(s^{\ast }{)}^n{e}^{-s^{\ast }n(a+\delta )}g(x_1)\cdots g(x_n)\mathrm{d}{x}_1\cdots \mathrm{d}{x}_n\\ =& M(s^{\ast }{)}^n{e}^{-s^{\ast }n(a+\delta )}\mathbb{P}((Y_1,\dots ,Y_n)\in B)\\ \to & M(s^{\ast }{)}^n{e}^{-s^{\ast }n(a+\delta )}\text{as }n\to \infty .\end{array}$$

Therefore,

$$\underset{n\to \infty }{\lim }\frac{1}{n}\log \mathbb{P}(S_n\ge (a-\delta )n)\ge \log M(s^{\ast })-s^{\ast }(a+\delta ).$$

Substituting $a-\delta$ with $a$ gives

$$\underset{n\to \infty }{\lim }\frac{1}{n}\log \mathbb{P}(S_n\ge an)\ge -\psi (a)-2s^{\ast }\delta .$$

Letting $\delta \to 0$ and combining with the upper bound gives the desired result.