Hoeffding inequality

In probability theory , the Hoeffding inequality (after Wassilij Hoeffding ) describes the maximum probability that a sum of independent and limited random variables will deviate more than a constant from their expected value .

The Hoeffding inequality is also called the additive Chernoff inequality and is a special case of the Bernstein inequality .

sentence

Be independent random variables so that it almost certainly holds true. Also be a positive, real-valued constant. Then: ${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$ ${\displaystyle a_{i}\leq X_{i}-{\textrm {E}}[X_{i}]\leq b_{i}}$ ${\displaystyle c}$

${\displaystyle \Pr \left[\sum (X_{i}-{\textrm {E}}[X_{i}])\geq c\right]\leq {\textrm {exp}}\left({\frac {-2c^{2}}{\sum (b_{i}-a_{i})^{2}}}\right).}$

proof

This proof follows the presentation by D. Pollard, see also Lutz Dümbgen's script (see literature).

To simplify the notation, consider the random variables with and furthermore, for an initially arbitrary map, the mapping that grows monotonically on the real numbers . According to the Chebyshev inequality : ${\displaystyle Y_{i}=X_{i}-{\textrm {E}}[X_{i}]}$ ${\displaystyle {\textrm {E}}[Y_{i}]=0}$ ${\displaystyle z>0}$ ${\displaystyle x\mapsto \exp(zx)}$

${\displaystyle \Pr \left[\sum Y_{i}\geq c\right]\leq {\frac {{\textrm {E}}[\exp \left(z\sum Y_{i}\right)]}{\exp(zc)}}=\exp(-zc)\cdot \prod {\textrm {E}}\left[\exp(zY_{i})\right].}$

Because of the convexity of the exponential function

${\displaystyle \exp(zY_{i})=\exp \left({\frac {b_{i}-Y_{i}}{b_{i}-a_{i}}}za_{i}+{\frac {Y_{i}-a_{i}}{b_{i}-a_{i}}}zb_{i}\right)\leq {\frac {b_{i}-Y_{i}}{b_{i}-a_{i}}}\exp(za_{i})+{\frac {Y_{i}-a_{i}}{b_{i}-a_{i}}}\exp(zb_{i}),}$

and with it follows that ${\displaystyle {\textrm {E}}[Y_{i}]=0}$

${\displaystyle {\textrm {E}}\left[\exp(zY_{i})\right]\leq {\frac {b_{i}}{b_{i}-a_{i}}}\exp(za_{i})+{\frac {-a_{i}}{b_{i}-a_{i}}}\exp(zb_{i})=e^{-u_{i}\lambda _{i}}\left(\left(1-\lambda _{i}\right)+\lambda _{i}e^{u_{i}}\right)}$

for the constants and . Looking at the logarithm of the right hand side of this term ${\displaystyle \lambda _{i}={\frac {-a_{i}}{b_{i}-a_{i}}}}$ ${\displaystyle u_{i}=z(b_{i}-a_{i})}$

${\displaystyle L(u,\lambda )=-u\lambda +\log \left(\left(1-\lambda \right)+\lambda e^{u}\right),}$

so one can show by means of curve discussion and Taylor series expansion that it always applies. If one reinserts this value into the first inequality due to the monotony of the exponential function as the upper bound, one obtains ${\displaystyle L(u,\lambda )\leq {\frac {u^{2}}{8}}}$

${\displaystyle \Pr \left[\sum Y_{i}\geq c\right]\leq \exp(-zc)\cdot \prod \exp({\frac {u_{i}^{2}}{8}})=\exp \left(-zc+{\frac {z^{2}}{8}}\sum (b_{i}-a_{i})^{2}\right),}$

which leads to the assertion to be proven if you choose . ${\displaystyle z={\tfrac {4c}{\sum (b_{i}-a_{i})^{2}}}}$

Examples

• Consider the following question: how likely is it to total at least 500 if you roll the dice 100 times? Describes the outcome of the dice roll with , so , it follows the Hoeffding's inequality: ${\displaystyle X}$ ${\displaystyle {\textrm {E}}[X]=3{,}5}$ ${\displaystyle -2{,}5\leq X-{\textrm {E}}[X]\leq 2{,}5}$

${\displaystyle \Pr \left[\sum X\geq 500\right]=\Pr \left[\sum (X-{\textrm {E}}[X])\geq 150\right]}$

${\displaystyle \leq \exp \left({\frac {-2\cdot 150^{2}}{\sum (2{,}5+2{,}5)^{2}}}\right)=\exp \left({\frac {-45000}{100\cdot 25}}\right)=\exp \left(-18\right)\approx 1{,}523\cdot 10^{-8}}$

literature

• Wassily Hoeffding, "Probability Inequalities for Sums of Bounded Random Variables," Journal of the American Statistical Association, Vol. 58, 1963, pp. 13-30.
• David Pollard, "Convergence of Stochastic Processes", Springer Verlag, 1984.
• Lutz Dümbgen, Empirical Processes , University of Bern, 2010.
• Otto Kerner, Joseph Maurer, Jutta Steffens, Thomas Thode and Rudolf Voller, Vieweg Mathematik Lexikon , second revised edition, Vieweg Verlag, 1993.