Chernoff bound#The first step in the proof of Chernoff bounds

File:Chernoff-bound.svg random variable]]

The generic Chernoff bound for a random variable $X$ is attained by applying Markov's inequality to $e^\{tX\}$ (which is why it is sometimes called the exponential Markov or exponential moments bound). For positive $t$ this gives a bound on the right tail of $X$ in terms of its moment-generating function $M(t)\; =\; \backslash operatorname\; E\; (e^\{t\; X\})$:

:$\backslash operatorname\; P\; \backslash left(X\; \backslash geq\; a\; \backslash right)\; =\; \backslash operatorname\; P\; \backslash left(e^\{t\; X\}\; \backslash geq\; e^\{t\; a\}\backslash right)\; \backslash leq\; M(t)\; e^\{-t\; a\}\; \backslash qquad\; (t\; >\; 0)$

Since this bound holds for every positive $t$, we may take the infimum:

:$\backslash operatorname\; P\; \backslash left(X\; \backslash geq\; a\backslash right)\; \backslash leq\; \backslash inf\_\{t\; >\; 0\}\; M(t)\; e^\{-t\; a\}$

Performing the same analysis with negative $t$ we get a similar bound on the left tail:

:

and

:

The quantity $M(t)\; e^\{-t\; a\}$ can be expressed as the expected value $\backslash operatorname\; E\; (e^\{t\; X\})\; e^\{-t\; a\}$, or equivalently $\backslash operatorname\; E\; (e^\{t\; (X-a)\})$.

The exponential function is convex, so by Jensen's inequality $\backslash operatorname\; E\; (e^\{t\; X\})\; \backslash ge\; e^\{t\; \backslash operatorname\; E\; (X)\}$. It follows that the bound on the right tail is greater or equal to one when $a\; \backslash le\; \backslash operatorname\; E\; (X)$, and therefore trivial; similarly, the left bound is trivial for $a\; \backslash ge\; \backslash operatorname\; E\; (X)$. We may therefore combine the two infima and define the two-sided Chernoff bound:$$C(a)\; =\; \backslash inf\_\{t\}\; M(t)\; e^\{-t\; a\}$$which provides an upper bound on the folded cumulative distribution function of $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) $I\; =\; -\backslash log\; C$. It is equivalent to the Legendre–Fenchel transform or convex conjugate of the cumulant generating function $K\; =\; \backslash log\; M$, defined as: $$I(a)\; =\; \backslash 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, $C(\backslash operatorname\; E(X))=1$, and is invariant under translation: $C\_\{X+k\}(a)\; =\; C\_X(a\; -\; k)$.

The Chernoff bound is exact if and only if $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 $t$. For unbounded random variables the bound is nowhere tight, though it is asymptotically tight up to sub-exponential factors ("exponentially tight").{{Citation needed|date=February 2023}} Individual moments can provide tighter bounds, at the cost of greater analytical complexity.{{Cite journal |last1=Philips |first1=Thomas K. |last2=Nelson |first2=Randolph |date=1995 |title=The Moment Bound Is Tighter Than Chernoff's Bound for Positive Tail Probabilities |url=https://www.jstor.org/stable/2684633 |journal=The American Statistician |volume=49 |issue=2 |pages=175–178 |doi=10.2307/2684633 |jstor=2684633 |issn=0003-1305}}

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).

Using only the moment generating function, a bound from below on the tail probabilities can be obtained by applying the Paley-Zygmund inequality to $e^\{tX\}$, yielding: $$\backslash operatorname\; P\; \backslash left(X\; >\; a\backslash right)\; \backslash geq\; \backslash sup\_\{t\; >\; 0\; \backslash and\; M(t)\; \backslash geq\; e^\{ta\}\}\; \backslash left(\; 1\; -\; \backslash frac\{e^\{ta\}\}\{M(t)\}\; \backslash right)^2\; \backslash frac\{M(t)^2\}\{M(2t)\}$$(a bound on the left tail is obtained for negative $t$). Unlike the Chernoff bound however, this result is not exponentially tight.

Theodosopoulos{{Cite journal |last=Theodosopoulos |first=Ted |date=2007-03-01 |title=A reversion of the Chernoff bound |url=https://www.sciencedirect.com/science/article/pii/S0167715206002884 |journal=Statistics & Probability Letters |language=en |volume=77 |issue=5 |pages=558–565 |doi=10.1016/j.spl.2006.09.003 |s2cid=16139953 |issn=0167-7152|arxiv=math/0501360 }} constructed a tight(er) MGF-based bound from below using an exponential tilting procedure.

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

When {{mvar|X}} is the sum of {{mvar|n}} independent random variables {{math|X₁, ..., X_n}}, the moment generating function of {{mvar|X}} is the product of the individual moment generating functions, giving that:

{{NumBlk|:|$\backslash Pr(X\; \backslash geq\; a)\; \backslash leq\; \backslash inf\_\{t\; >\; 0\}\; \backslash frac\{\backslash operatorname\; E\; \backslash left\; [\backslash prod\_i\; e^\{t\backslash cdot\; X\_i\}\backslash right]\}\{e^\{t\backslash cdot\; a\}\}\; =\; \backslash inf\_\{t\; >\; 0\}\; e^\{-t\backslash cdot\; a\}\backslash prod\_i\backslash operatorname\; E\backslash left[\; e^\{t\backslash cdot\; X\_i\}\backslash right].$|{{EquationRef|1}}}}

and:

:

Specific Chernoff bounds are attained by calculating the moment-generating function $\backslash operatorname\; E\; \backslash left[e^\{-t\backslash cdot\; X\_i\}\; \backslash right\; ]$ for specific instances of the random variables $X\_i$.

When the random variables are also identically distributed (iid), the Chernoff bound for the sum reduces to a simple rescaling of the single-variable Chernoff bound. That is, the Chernoff bound for the average of n iid variables is equivalent to the nth power of the Chernoff bound on a single variable (see Cramér's theorem).

{{main|Hoeffding's inequality}}

Chernoff bounds may also be applied to general sums of independent, bounded random variables, regardless of their distribution; this is known as Hoeffding's inequality. The proof follows a similar approach to the other Chernoff bounds, but applying Hoeffding's lemma to bound the moment generating functions (see Hoeffding's inequality).

:Hoeffding's inequality. Suppose {{math|X₁, ..., X_n}} are independent random variables taking values in {{math|[a,b].}} Let {{mvar|X}} denote their sum and let {{math|μ {{=}} E[X]}} denote the sum's expected value. Then for any $t>0$,

::

::

The bounds in the following sections for Bernoulli random variables are derived by using that, for a Bernoulli random variable $X\_i$ with probability p of being equal to 1,

:$\backslash operatorname\; E\; \backslash left[e^\{t\backslash cdot\; X\_i\}\; \backslash right]\; =\; (1\; -\; p)\; e^0\; +\; p\; e^t\; =\; 1\; +\; p\; (e^t\; -1)\; \backslash leq\; e^\{p\; (e^t\; -\; 1)\}.$

One can encounter many flavors of Chernoff bounds: the original additive form (which gives a bound on the absolute error) or the more practical multiplicative form (which bounds the error relative to the mean).

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

:$\backslash Pr\; (\; X\; \backslash ge\; (1+\backslash delta)\backslash mu)\; \backslash leq\; \backslash left(\backslash frac\{e^\{\backslash delta\}\}\{(1+\backslash delta)^\{1+\backslash delta\}\}\backslash right)^\backslash mu.$

A similar proof strategy can be used to show that for {{math|0 < δ < 1}}

:$\backslash Pr(X\; \backslash le\; (1-\backslash delta)\backslash mu)\; \backslash leq\; \backslash left(\backslash frac\{e^\{-\backslash delta\}\}\{(1-\backslash delta)^\{1-\backslash delta\}\}\backslash right)^\backslash mu.$

The above formula is often unwieldy in practice, so the following looser but more convenient bounds{{cite book | url=https://books.google.com/books?id=0bAYl6d7hvkC | title=Probability and Computing: Randomized Algorithms and Probabilistic Analysis | publisher=Cambridge University Press |author1=Mitzenmacher, Michael |author2=Upfal, Eli | year=2005 | isbn=978-0-521-83540-4}} are often used, which follow from the inequality $\backslash textstyle\backslash frac\{2\backslash delta\}\{2+\backslash delta\}\; \backslash le\; \backslash log(1+\backslash delta)$ from the list of logarithmic inequalities:

:$\backslash Pr(\; X\; \backslash ge\; (1+\backslash delta)\backslash mu)\backslash le\; e^\{-\backslash delta^2\backslash mu/(2+\backslash delta)\},\; \backslash qquad\; 0\; \backslash le\; \backslash delta,$

:

:

Notice that the bounds are trivial for $\backslash delta\; =\; 0$.

In addition, based on the Taylor expansion for the Lambert W function, {{cite journal

| last1 = Dillencourt

| first1 = Michael

| last2 = Goodrich

| first2 = Michael

| last3 = Mitzenmacher

| first3 = Michael

| title = Leveraging Parameterized Chernoff Bounds for Simplified Algorithm Analyses

| journal = Information Processing Letters

| number = 106516

| year = 2024

| volume = 187

| doi = 10.1016/j.ipl.2024.106516

| doi-access = free

}}

:$\backslash Pr(\; X\; \backslash ge\; R)\backslash le\; 2^\{-xR\},\; \backslash qquad\; x\; >\; 0,\; \backslash \; R\; \backslash ge\; (2^x\; e\; -1)\backslash mu.$

The following theorem is due to Wassily Hoeffding{{cite journal

|last1=Hoeffding |first1=W.

|year=1963

|title=Probability Inequalities for Sums of Bounded Random Variables

|journal=Journal of the American Statistical Association

|volume=58 |issue=301 |pages=13–30

|doi=10.2307/2282952

|jstor=2282952

|url=http://repository.lib.ncsu.edu/bitstream/1840.4/2170/1/ISMS_1962_326.pdf

}} and hence is called the Chernoff–Hoeffding theorem.

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

::$\backslash begin\{align\}$

\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{align}

:where

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

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

::$\backslash Pr\backslash left\; (\; \backslash frac\{1\}\{n\}\backslash sum\; X\_i>p+x\; \backslash right\; )\; \backslash leq\; \backslash exp\; \backslash left\; (-\backslash frac\{x^2n\}\{2p(1-p)\}\; \backslash right\; ).$

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

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

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

:$$

\begin{align}

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{align}

which are stronger for {{math|p < {{sfrac|1|8}},}} are also used.

Chernoff bounds have very useful applications in set balancing and packet routing in sparse networks.

The set balancing problem arises while designing statistical experiments. Typically while designing a statistical experiment, given the features of each participant in the experiment, we need to know how to divide the participants into 2 disjoint groups such that each feature is roughly as balanced as possible between the two groups.Refer to this [https://books.google.com/books?id=0bAYl6d7hvkC&pg=PA71 book section] for more info on the problem.

Chernoff bounds are also used to obtain tight bounds for permutation routing problems which reduce network congestion while routing packets in sparse networks.

Chernoff bounds are used in computational learning theory to prove that a learning algorithm is probably approximately correct, i.e. with high probability the algorithm has small error on a sufficiently large training data set.{{cite book |first1=M. |last1=Kearns |first2=U. |last2=Vazirani |title=An Introduction to Computational Learning Theory |at=Chapter 9 (Appendix), pages 190–192 |publisher=MIT Press |year=1994 |isbn=0-262-11193-4 }}

Chernoff bounds can be effectively used to evaluate the "robustness level" of an application/algorithm by exploring its perturbation space with randomization.{{cite book |first=C. |last=Alippi |chapter=Randomized Algorithms |title=Intelligence for Embedded Systems |publisher=Springer |year=2014 |isbn=978-3-319-05278-6 }}

The use of the Chernoff bound permits one to abandon the strong—and mostly unrealistic—small perturbation hypothesis (the perturbation magnitude is small). The robustness level can be, in turn, used either to validate or reject a specific algorithmic choice, a hardware implementation or the appropriateness of a solution whose structural parameters are affected by uncertainties.

A simple and common use of Chernoff bounds is for "boosting" of randomized algorithms. If one has an algorithm that outputs a guess that is the desired answer with probability p > 1/2, then one can get a higher success rate by running the algorithm $n\; =\; \backslash log(1/\backslash delta)\; 2p/(p\; -\; 1/2)^2$ times and outputting a guess that is output by more than n/2 runs of the algorithm. (There cannot be more than one such guess.) Assuming that these algorithm runs are independent, the probability that more than n/2 of the guesses is correct is equal to the probability that the sum of independent Bernoulli random variables {{math|X_k}} that are 1 with probability p is more than n/2. This can be shown to be at least $1-\backslash delta$ via the multiplicative Chernoff bound (Corollary 13.3 in Sinclair's class notes, {{math|μ {{=}} np}}).:{{Cite web|url = http://www.cs.berkeley.edu/~sinclair/cs271/n13.pdf|title = Class notes for the course "Randomness and Computation"|date = Fall 2011|access-date = 30 October 2014|last = Sinclair|first = Alistair|archive-url = https://web.archive.org/web/20141031035717/http://www.cs.berkeley.edu/~sinclair/cs271/n13.pdf|archive-date = 31 October 2014|url-status = dead}}

:$\backslash Pr\backslash left[X\; >\; \{n\; \backslash over\; 2\}\backslash right]\; \backslash ge\; 1\; -\; e^\{-n\; \backslash left(p\; -\; 1/2\; \backslash right)^2/(2p)\}\; \backslash geq\; 1-\backslash delta$

{{main|Matrix Chernoff bound}}

Rudolf Ahlswede and Andreas Winter introduced a Chernoff bound for matrix-valued random variables.{{cite journal

|last1=Ahlswede |first1=R.

|last2=Winter |first2=A.

|year=2003

|title=Strong Converse for Identification via Quantum Channels

|volume=48 |issue=3 |pages=569–579

|journal=IEEE Transactions on Information Theory

|arxiv=quant-ph/0012127

|doi=10.1109/18.985947

|s2cid=523176

}} The following version of the inequality can be found in the work of Tropp.{{cite journal

|last1=Tropp |first1=J.

|year=2010

|title=User-friendly tail bounds for sums of random matrices

|arxiv=1004.4389

|doi=10.1007/s10208-011-9099-z

|volume=12

|issue=4

|journal=Foundations of Computational Mathematics

|pages=389–434

|s2cid=17735965

}}

Let {{math|M₁, ..., M_t}} be independent matrix valued random variables such that $M\_i\backslash in\; \backslash mathbb\{C\}^\{d\_1\; \backslash times\; d\_2\}$ and $\backslash mathbb\{E\}[M\_i]=0$.

Let us denote by $\backslash lVert\; M\; \backslash rVert$ the operator norm of the matrix $M$. If $\backslash lVert\; M\_i\; \backslash rVert\; \backslash leq\; \backslash gamma$ holds almost surely for all $i\backslash in\backslash \{1,\backslash ldots,\; t\backslash \}$, then for every {{math|ε > 0}}

:$\backslash Pr\backslash left(\; \backslash left\backslash |\; \backslash frac\{1\}\{t\}\; \backslash sum\_\{i=1\}^t\; M\_i\; \backslash right\backslash |\; >\; \backslash varepsilon\; \backslash right)\; \backslash leq\; (d\_1+d\_2)\; \backslash exp\; \backslash left(\; -\backslash frac\{3\backslash varepsilon^2\; t\}\{8\backslash gamma^2\}\; \backslash right).$

Notice that in order to conclude that the deviation from 0 is bounded by {{math|ε}} with high probability, we need to choose a number of samples $t$ proportional to the logarithm of $d\_1+d\_2$. In general, unfortunately, a dependence on $\backslash log(\backslash min(d\_1,d\_2))$ is inevitable: take for example a diagonal random sign matrix of dimension $d\backslash times\; d$. The operator norm of the sum of t independent samples is precisely the maximum deviation among d independent random walks of length t. In order to achieve a fixed bound on the maximum deviation with constant probability, it is easy to see that t should grow logarithmically with d in this scenario.{{cite arXiv |last1=Magen |first1=A.|author1-link=Avner Magen |last2=Zouzias |first2=A. |year=2011 |title=Low Rank Matrix-Valued Chernoff Bounds and Approximate Matrix Multiplication |class=cs.DM |eprint=1005.2724 }}

The following theorem can be obtained by assuming M has low rank, in order to avoid the dependency on the dimensions.

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

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

If $r\; \backslash leq\; t$ holds almost surely, then

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

where {{math|M₁, ..., M_t}} are i.i.d. copies of M.

The following variant of Chernoff's bound can be used to bound the probability that a majority in a population will become a minority in a sample, or vice versa.{{Cite book | doi = 10.1007/3-540-44676-1_35| chapter = Competitive Auctions for Multiple Digital Goods| title = Algorithms — ESA 2001| volume = 2161| pages = 416| series = Lecture Notes in Computer Science| year = 2001| last1 = Goldberg | first1 = A. V. | last2 = Hartline | first2 = J. D. | isbn = 978-3-540-42493-2| citeseerx = 10.1.1.8.5115}}; lemma 6.1

Suppose there is a general population A and a sub-population B ⊆ A. Mark the relative size of the sub-population (|B|/|A|) by r.

Suppose we pick an integer k and a random sample S ⊂ A of size k. Mark the relative size of the sub-population in the sample (|B∩S|/|S|) by r_S.

Then, for every fraction d ∈ [0,1]:

:

In particular, if B is a majority in A (i.e. r > 0.5) we can bound the probability that B will remain majority in S(r_S > 0.5) by taking: d = 1 − 1/(2r):See graphs of: [https://www.desmos.com/calculator/eqvyjug0re the bound as a function of r when k changes] and [https://www.desmos.com/calculator/nxurzg7bqj the bound as a function of k when r changes].

:$\backslash Pr\backslash left(r\_S\; >\; 0.5\backslash right)\; >\; 1\; -\; \backslash exp\backslash left(-r\backslash cdot\; \backslash left(1\; -\; \backslash frac\{1\}\{2\; r\}\backslash right)^2\; \backslash cdot\; \backslash frac\; k\; 2\; \backslash right)$

This bound is of course not tight at all. For example, when r = 0.5 we get a trivial bound Prob > 0.

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

:$\backslash operatorname\; E\; \backslash left[e^\{t\backslash cdot\; X\_i\}\; \backslash right]\; =\; (1\; -\; p\_i)\; e^0\; +\; p\_i\; e^t\; =\; 1\; +\; p\_i\; (e^t\; -1)\; \backslash leq\; e^\{p\_i\; (e^t\; -\; 1)\}$

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

:$\backslash begin\{align\}$

\Pr (X > (1 + \delta)\mu) &\le \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{align}

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

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

This proves the result desired.

Let {{math|q {{=}} p + ε}}. Taking {{math|a {{=}} nq}} in ({{EquationNote|1}}), we obtain:

:$\backslash Pr\backslash left\; (\; \backslash frac\{1\}\{n\}\; \backslash sum\; X\_i\; \backslash ge\; q\backslash right\; )\backslash le\; \backslash inf\_\{t>0\}\; \backslash frac\{E\; \backslash left[\backslash prod\; e^\{t\; X\_i\}\backslash right]\}\{e^\{tnq\}\}\; =\; \backslash inf\_\{t>0\}\; \backslash left\; (\; \backslash frac\{\; E\backslash left[e^\{tX\_i\}\; \backslash right]\; \}\{e^\{tq\}\}\backslash right\; )^n.$

Now, knowing that {{math|Pr(X_i {{=}} 1) {{=}} p, Pr(X_i {{=}} 0) {{=}} 1 − p}}, we have

:$\backslash left\; (\backslash frac\{\backslash operatorname\; E\backslash left[e^\{tX\_i\}\; \backslash right]\; \}\{e^\{tq\}\}\backslash right\; )^n\; =\; \backslash left\; (\backslash frac\{p\; e^t\; +\; (1-p)\}\{e^\{tq\}\; \}\backslash right\; )^n\; =\; \backslash left\; (\; pe^\{(1-q)t\}\; +\; (1-p)e^\{-qt\}\; \backslash right\; )^n.$

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

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

Setting the equation to zero and solving, we have

:$\backslash begin\{align\}$

(1-q)pe^{(1-q)t} &= q(1-p)e^{-qt} \\

(1-q)pe^{t} &= q(1-p)

\end{align}

so that

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

Thus,

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

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

:$\backslash begin\{align\}$

\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{align}

We now have our desired result, that

:$\backslash Pr\; \backslash left\; (\backslash tfrac\{1\}\{n\}\backslash sum\; X\_i\; \backslash ge\; p\; +\; \backslash varepsilon\backslash right\; )\; \backslash le\; e^\{-D(p+\backslash varepsilon\backslash parallel\; p)\; n\}.$

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

• Bernstein inequalities
• Concentration inequality − a summary of tail-bounds on random variables.
• Cramér's theorem
• Entropic value at risk
• Hoeffding's inequality
• Matrix Chernoff bound
• Moment generating function

{{Reflist}}

• {{cite journal

|last1=Chernoff |first1=H.

|year=1952

|title=A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

|journal=Annals of Mathematical Statistics

|volume=23 |issue=4 |pages=493–507

|doi=10.1214/aoms/1177729330

|jstor=2236576

|mr=57518

|zbl=0048.11804

|doi-access=free

}}

• {{cite journal

|last1=Chernoff |first1=H.

|year=1981

|title=A Note on an Inequality Involving the Normal Distribution

|journal=Annals of Probability

|volume=9 |issue=3 |pages=533–535

|doi=10.1214/aop/1176994428

|jstor=2243541

|mr=614640

|zbl=0457.60014

|doi-access=free

}}

• {{cite journal

|last1=Hagerup |first1=T.

|last2=Rüb |first2=C.

|year=1990

|title=A guided tour of Chernoff bounds

|journal=Information Processing Letters

|volume=33 |issue=6 |pages=305

|doi=10.1016/0020-0190(90)90214-I

}}

• {{cite journal

|last=Nielsen |first=F.

|year=2011

|title=An Information-Geometric Characterization of Chernoff Information

|journal=IEEE Signal Processing Letters

|volume=20

|issue=3

|pages=269–272

|doi=10.1109/LSP.2013.2243726

|arxiv=1102.2684

|s2cid=15034953

}}

{{DEFAULTSORT:Chernoff Bound}}

Category:Probabilistic inequalities