Editing Chernoff bound (section)

=== Additive form (absolute error) ===
The following theorem is due to [[Wassily Hoeffding]]<ref>{{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
 }}</ref> and hence is called the Chernoff–Hoeffding theorem.

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

::<math>\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}</math>
:where
::<math> D(x\parallel y) = x \ln \frac{x}{y} + (1-x) \ln \left (\frac{1-x}{1-y} \right )</math>
:is the [[Kullback–Leibler divergence]] between [[Bernoulli distribution|Bernoulli distributed]] random variables with parameters ''x'' and ''y'' respectively. If {{math|''p'' ≥ {{sfrac|1|2}},}} then <math>D(p+\varepsilon\parallel p)\ge \tfrac{\varepsilon^2}{2p(1-p)}</math> which means

::<math> \Pr\left ( \frac{1}{n}\sum X_i>p+x \right ) \leq \exp \left (-\frac{x^2n}{2p(1-p)} \right ).</math>

A simpler bound follows by relaxing the theorem using {{math|''D''(''p'' + ''ε'' {{!!}} ''p'') ≥ 2''ε''<sup>2</sup>}}, which follows from the [[Convex function|convexity]] of {{math|''D''(''p'' + ''ε'' {{!!}} ''p'')}} and the fact that

:<math>\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).</math>

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

:<math>
\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}
</math>

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