Chernoff bound

The exponential function is convex, so by Jensen's inequality ${\displaystyle \operatorname {E} (e^{tX})\geq e^{t\operatorname {E} (X)}}$. It follows that the bound on the right tail is greater or equal to one when ${\displaystyle a\leq \operatorname {E} (X)}$, and therefore trivial; similarly, the left bound is trivial for ${\displaystyle a\geq \operatorname {E} (X)}$. We may therefore combine the two infima and define the two-sided Chernoff bound:

$${\displaystyle C(a)=\inf _{t}M(t)e^{-ta}}$$

which provides an upper bound on the folded cumulative distribution function of ${\displaystyle X}$ (folded at the mean, not the median). The logarithm of the two-sided Chernoff bound is known as the rate function (or Cramér transform) ${\displaystyle I=-\log C}$. It is equivalent to the Legendre–Fenchel transform or convex conjugate of the cumulant generating function ${\displaystyle K=\log M}$, defined as:

$${\displaystyle I(a)=\sup _{t}at-K(t)}$$

The moment generating function is log-convex, so by a property of the convex conjugate, the Chernoff bound must be log-concave. The Chernoff bound attains its maximum at the mean, ${\displaystyle C(\operatorname {E} (X))=1}$, and is invariant under translation: ${\textstyle C_{X+k}(a)=C_{X}(a-k)}$.

The Chernoff bound is exact if and only if ${\displaystyle X}$ is a single concentrated mass (degenerate distribution). The bound is tight only at or beyond the extremes of a bounded random variable, where the infima are attained for infinite ${\displaystyle t}$. For unbounded random variables the bound is nowhere tight, though it is asymptotically tight up to sub-exponential factors ("exponentially tight"). Individual moments can provide tighter bounds, at the cost of greater analytical complexity.[7]

In practice, the exact Chernoff bound may be unwieldy or difficult to evaluate analytically, in which case a suitable upper bound on the moment (or cumulant) generating function may be used instead (e.g. a sub-parabolic CGF giving a sub-Gaussian Chernoff bound).

Exact rate functions and Chernoff bounds for common distributions

Distribution	${\displaystyle \operatorname {E} (X)}$	${\displaystyle K(t)}$	${\displaystyle I(a)}$	${\displaystyle C(a)}$
Normal distribution	${\displaystyle 0}$	${\displaystyle {\frac {1}{2}}\sigma ^{2}t^{2}}$	${\displaystyle {\frac {1}{2}}\left({\frac {a}{\sigma }}\right)^{2}}$	${\displaystyle \exp \left({-{\frac {a^{2}}{2\sigma ^{2}}}}\right)}$
Bernoulli distribution(detailed below)	${\displaystyle p}$	${\displaystyle \ln \left(1-p+pe^{t}\right)}$	${\displaystyle D_{KL}(a\parallel p)}$	${\displaystyle \left({\frac {p}{a}}\right)^{a}{\left({\frac {1-p}{1-a}}\right)}^{1-a}}$
Standard Bernoulli (H is the binary entropy function)	${\displaystyle {\frac {1}{2}}}$	${\displaystyle \ln \left(1+e^{t}\right)-\ln(2)}$	${\displaystyle \ln(2)-H(a)}$	${\displaystyle {\frac {1}{2}}a^{-a}(1-a)^{-(1-a)}}$
Rademacher distribution	${\displaystyle 0}$	${\displaystyle \ln \cosh(t)}$	${\displaystyle \ln(2)-H\left({\frac {1+a}{2}}\right)}$	${\displaystyle {\sqrt {(1+a)^{-1-a}(1-a)^{-1+a}}}}$
Gamma distribution	${\displaystyle \theta k}$	${\displaystyle -k\ln(1-\theta t)}$	${\displaystyle -k\ln {\frac {a}{\theta k}}-k+{\frac {a}{\theta }}}$	${\displaystyle \left({\frac {a}{\theta k}}\right)^{k}e^{k-a/\theta }}$
Chi-squared distribution	${\displaystyle k}$	${\displaystyle -{\frac {k}{2}}\ln(1-2t)}$	${\displaystyle {\frac {k}{2}}\left({\frac {a}{k}}-1-\ln {\frac {a}{k}}\right)}$[8]	${\displaystyle \left({\frac {a}{k}}\right)^{k/2}e^{k/2-a/2}}$
Poisson distribution	${\displaystyle \lambda }$	${\displaystyle \lambda (e^{t}-1)}$	${\displaystyle a\ln(a/\lambda )-a+\lambda }$	${\displaystyle (a/\lambda )^{-a}e^{a-\lambda }}$

Using only the moment generating function, a lower bound on the tail probabilities can be obtained by applying the Paley-Zygmund inequality to ${\displaystyle e^{tX}}$, yielding:

$${\displaystyle \operatorname {P} \left(X>a\right)\geq \sup _{t>0\land M(t)\geq e^{ta}}\left(1-{\frac {e^{ta}}{M(t)}}\right)^{2}{\frac {M(t)^{2}}{M(2t)}}}$$

(a bound on the left tail is obtained for negative ${\displaystyle t}$). Unlike the Chernoff bound however, this result is not exponentially tight.

Theodosopoulos[9] constructed a tight(er) MGF-based lower bound using an exponential tilting procedure.

For particular distributions (such as the binomial) lower bounds of the same exponential order as the Chernoff bound are often available.

Multiplicative Chernoff bound. Suppose X₁, ..., X_n are independent random variables taking values in {0, 1}. Let X denote their sum and let μ = E[X] denote the sum's expected value. Then for any δ > 0,

${\displaystyle \Pr(X\geq (1+\delta )\mu )\leq \left({\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\right)^{\mu }.}$

A similar proof strategy can be used to show that for 0 < δ < 1

${\displaystyle \Pr(X\leq (1-\delta )\mu )\leq \left({\frac {e^{-\delta }}{(1-\delta )^{1-\delta }}}\right)^{\mu }.}$

The above formula is often unwieldy in practice, so the following looser but more convenient bounds[10] are often used, which follow from the inequality ${\displaystyle \textstyle {\frac {2\delta }{2+\delta }}\leq \log(1+\delta )}$ from the list of logarithmic inequalities:

${\displaystyle \Pr(X\geq (1+\delta )\mu )\leq e^{-\delta ^{2}\mu /(2+\delta )},\qquad 0\leq \delta ,}$

${\displaystyle \Pr(X\leq (1-\delta )\mu )\leq e^{-\delta ^{2}\mu /2},\qquad 0<\delta <1,}$

${\displaystyle \Pr(|X-\mu |\geq \delta \mu )\leq 2e^{-\delta ^{2}\mu /3},\qquad 0<\delta <1.}$

Notice that the bounds are trivial for ${\displaystyle \delta =0}$.

The following theorem is due to Wassily Hoeffding[11] and hence is called the Chernoff–Hoeffding theorem.

Chernoff–Hoeffding theorem. Suppose X₁, ..., X_n are i.i.d. random variables, taking values in {0, 1}. Let p = E[X₁] and ε > 0.

${\displaystyle {\begin{aligned}\Pr \left({\frac {1}{n}}\sum X_{i}\geq p+\varepsilon \right)\leq \left(\left({\frac {p}{p+\varepsilon }}\right)^{p+\varepsilon }{\left({\frac {1-p}{1-p-\varepsilon }}\right)}^{1-p-\varepsilon }\right)^{n}&=e^{-D(p+\varepsilon \parallel p)n}\\\Pr \left({\frac {1}{n}}\sum X_{i}\leq p-\varepsilon \right)\leq \left(\left({\frac {p}{p-\varepsilon }}\right)^{p-\varepsilon }{\left({\frac {1-p}{1-p+\varepsilon }}\right)}^{1-p+\varepsilon }\right)^{n}&=e^{-D(p-\varepsilon \parallel p)n}\end{aligned}}}$

where

${\displaystyle D(x\parallel y)=x\ln {\frac {x}{y}}+(1-x)\ln \left({\frac {1-x}{1-y}}\right)}$

is the Kullback–Leibler divergence between Bernoulli distributed random variables with parameters x and y respectively. If p ≥ 1/2, then ${\displaystyle D(p+\varepsilon \parallel p)\geq {\tfrac {\varepsilon ^{2}}{2p(1-p)}}}$ which means

${\displaystyle \Pr \left({\frac {1}{n}}\sum X_{i}>p+x\right)\leq \exp \left(-{\frac {x^{2}n}{2p(1-p)}}\right).}$

A simpler bound follows by relaxing the theorem using D(p + ε || p) ≥ 2ε², which follows from the convexity of D(p + ε || p) and the fact that

${\displaystyle {\frac {d^{2}}{d\varepsilon ^{2}}}D(p+\varepsilon \parallel p)={\frac {1}{(p+\varepsilon )(1-p-\varepsilon )}}\geq 4={\frac {d^{2}}{d\varepsilon ^{2}}}(2\varepsilon ^{2}).}$

This result is a special case of Hoeffding's inequality. Sometimes, the bounds

${\displaystyle {\begin{aligned}D((1+x)p\parallel p)\geq {\frac {1}{4}}x^{2}p,&&&{-{\tfrac {1}{2}}}\leq x\leq {\tfrac {1}{2}},\\[6pt]D(x\parallel y)\geq {\frac {3(x-y)^{2}}{2(2y+x)}},\\[6pt]D(x\parallel y)\geq {\frac {(x-y)^{2}}{2y}},&&&x\leq y,\\[6pt]D(x\parallel y)\geq {\frac {(x-y)^{2}}{2x}},&&&x\geq y\end{aligned}}}$

which are stronger for p < 1/8, are also used.

Let 0 < ε < 1 and M be a random symmetric real matrix with ${\displaystyle \|\operatorname {E} [M]\|\leq 1}$ and ${\displaystyle \|M\|\leq \gamma }$ almost surely. Assume that each element on the support of M has at most rank r. Set

${\displaystyle t=\Omega \left({\frac {\gamma \log(\gamma /\varepsilon ^{2})}{\varepsilon ^{2}}}\right).}$

If ${\displaystyle r\leq t}$ holds almost surely, then

${\displaystyle \Pr \left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}-\operatorname {E} [M]\right\|>\varepsilon \right)\leq {\frac {1}{\mathbf {poly} (t)}}}$

where M₁, ..., M_t are i.i.d. copies of M.

Following the conditions of the multiplicative Chernoff bound, let X₁, ..., X_n be independent Bernoulli random variables, whose sum is X, each having probability p_i of being equal to 1. For a Bernoulli variable:

${\displaystyle \operatorname {E} \left[e^{t\cdot X_{i}}\right]=(1-p_{i})e^{0}+p_{i}e^{t}=1+p_{i}(e^{t}-1)\leq e^{p_{i}(e^{t}-1)}}$

So, using (1) with ${\displaystyle a=(1+\delta )\mu }$ for any ${\displaystyle \delta >0}$ and where ${\displaystyle \mu =\operatorname {E} [X]=\textstyle \sum _{i=1}^{n}p_{i}}$,

${\displaystyle {\begin{aligned}\Pr(X>(1+\delta )\mu )&\leq \inf _{t\geq 0}\exp(-t(1+\delta )\mu )\prod _{i=1}^{n}\operatorname {E} [\exp(tX_{i})]\\[4pt]&\leq \inf _{t\geq 0}\exp {\Big (}-t(1+\delta )\mu +\sum _{i=1}^{n}p_{i}(e^{t}-1){\Big )}\\[4pt]&=\inf _{t\geq 0}\exp {\Big (}-t(1+\delta )\mu +(e^{t}-1)\mu {\Big )}.\end{aligned}}}$

If we simply set t = log(1 + δ) so that t > 0 for δ > 0, we can substitute and find

${\displaystyle \exp {\Big (}-t(1+\delta )\mu +(e^{t}-1)\mu {\Big )}={\frac {\exp((1+\delta -1)\mu )}{(1+\delta )^{(1+\delta )\mu }}}=\left[{\frac {e^{\delta }}{(1+\delta )^{(1+\delta )}}}\right]^{\mu }.}$

This proves the result desired.

Let q = p + ε. Taking a = nq in (1), we obtain:

${\displaystyle \Pr \left({\frac {1}{n}}\sum X_{i}\geq q\right)\leq \inf _{t>0}{\frac {E\left[\prod e^{tX_{i}}\right]}{e^{tnq}}}=\inf _{t>0}\left({\frac {E\left[e^{tX_{i}}\right]}{e^{tq}}}\right)^{n}.}$

Now, knowing that Pr(X_i = 1) = p, Pr(X_i = 0) = 1 − p, we have

${\displaystyle \left({\frac {\operatorname {E} \left[e^{tX_{i}}\right]}{e^{tq}}}\right)^{n}=\left({\frac {pe^{t}+(1-p)}{e^{tq}}}\right)^{n}=\left(pe^{(1-q)t}+(1-p)e^{-qt}\right)^{n}.}$

Therefore, we can easily compute the infimum, using calculus:

${\displaystyle {\frac {d}{dt}}\left(pe^{(1-q)t}+(1-p)e^{-qt}\right)=(1-q)pe^{(1-q)t}-q(1-p)e^{-qt}}$

Setting the equation to zero and solving, we have

${\displaystyle {\begin{aligned}(1-q)pe^{(1-q)t}&=q(1-p)e^{-qt}\\(1-q)pe^{t}&=q(1-p)\end{aligned}}}$

so that

${\displaystyle e^{t}={\frac {(1-p)q}{(1-q)p}}.}$

Thus,

${\displaystyle t=\log \left({\frac {(1-p)q}{(1-q)p}}\right).}$

As q = p + ε > p, we see that t > 0, so our bound is satisfied on t. Having solved for t, we can plug back into the equations above to find that

${\displaystyle {\begin{aligned}\log \left(pe^{(1-q)t}+(1-p)e^{-qt}\right)&=\log \left(e^{-qt}(1-p+pe^{t})\right)\\&=\log \left(e^{-q\log \left({\frac {(1-p)q}{(1-q)p}}\right)}\right)+\log \left(1-p+pe^{\log \left({\frac {1-p}{1-q}}\right)}e^{\log {\frac {q}{p}}}\right)\\&=-q\log {\frac {1-p}{1-q}}-q\log {\frac {q}{p}}+\log \left(1-p+p\left({\frac {1-p}{1-q}}\right){\frac {q}{p}}\right)\\&=-q\log {\frac {1-p}{1-q}}-q\log {\frac {q}{p}}+\log \left({\frac {(1-p)(1-q)}{1-q}}+{\frac {(1-p)q}{1-q}}\right)\\&=-q\log {\frac {q}{p}}+\left(-q\log {\frac {1-p}{1-q}}+\log {\frac {1-p}{1-q}}\right)\\&=-q\log {\frac {q}{p}}+(1-q)\log {\frac {1-p}{1-q}}\\&=-D(q\parallel p).\end{aligned}}}$

We now have our desired result, that

${\displaystyle \Pr \left({\tfrac {1}{n}}\sum X_{i}\geq p+\varepsilon \right)\leq e^{-D(p+\varepsilon \parallel p)n}.}$

To complete the proof for the symmetric case, we simply define the random variable Y_i = 1 − X_i, apply the same proof, and plug it into our bound.