Editing Chernoff bound (section)

==Proofs==

===Multiplicative form===
Following the conditions of the multiplicative Chernoff bound, let {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} be independent [[Bernoulli random variable]]s, whose sum is {{math|''X''}}, each having probability ''p<sub>i</sub>'' of being equal to 1. For a Bernoulli variable:

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

So, using ({{EquationNote|1}}) with <math>a = (1+\delta)\mu</math> for any <math>\delta>0</math> and where <math>\mu = \operatorname E[X] = \textstyle\sum_{i=1}^n p_i</math>,

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

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

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

This proves the result desired.

===Chernoff–Hoeffding theorem (additive form)===
Let {{math|''q'' {{=}} ''p'' + ''ε''}}. Taking {{math|''a'' {{=}} ''nq''}} in ({{EquationNote|1}}), we obtain:

:<math>\Pr\left ( \frac{1}{n} \sum X_i \ge q\right )\le \inf_{t>0} \frac{E \left[\prod e^{t X_i}\right]}{e^{tnq}} = \inf_{t>0} \left ( \frac{ E\left[e^{tX_i} \right] }{e^{tq}}\right )^n.</math>

Now, knowing that {{math|Pr(''X<sub>i</sub>'' {{=}} 1) {{=}} ''p'', Pr(''X<sub>i</sub>'' {{=}} 0) {{=}} 1 − ''p''}}, we have

:<math>\left (\frac{\operatorname E\left[e^{tX_i} \right] }{e^{tq}}\right )^n = \left (\frac{p e^t + (1-p)}{e^{tq} }\right )^n = \left ( pe^{(1-q)t} + (1-p)e^{-qt} \right )^n.</math>

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

:<math>\frac{d}{dt} \left (pe^{(1-q)t} + (1-p)e^{-qt} \right) = (1-q)pe^{(1-q)t}-q(1-p)e^{-qt}</math>

Setting the equation to zero and solving, we have

:<math>\begin{align}
(1-q)pe^{(1-q)t} &= q(1-p)e^{-qt} \\
(1-q)pe^{t} &= q(1-p)
\end{align}</math>

so that

:<math>e^t = \frac{(1-p)q}{(1-q)p}.</math>

Thus,

:<math>t = \log\left(\frac{(1-p)q}{(1-q)p}\right).</math>

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

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

We now have our desired result, that

:<math>\Pr \left (\tfrac{1}{n}\sum X_i \ge p + \varepsilon\right ) \le e^{-D(p+\varepsilon\parallel p) n}.</math>

To complete the proof for the symmetric case, we simply define the random variable {{math|''Y<sub>i</sub>'' {{=}} 1 − ''X<sub>i</sub>''}}, apply the same proof, and plug it into our bound.