- Hoeffding's inequality
Hoeffding's
inequality , named afterWassily Hoeffding , is a result inprobability theory that gives anupper bound on theprobability for the sum ofrandom variables to deviate from itsexpected value .Let
:X_1, dots, X_n !
be
independent random variables . Assume that the X_i arealmost sure ly bounded; that is, assume for 1leq ileq n that:Pr(X_i in [a_i, b_i] ) = 1. !
Then, for the sum of these variables
:S = X_1 + cdots + X_n !
we have the inequality (Hoeffding 1963, Theorem 2):
:Pr(S - mathrm{E} [S] geq nt) leq exp left( - frac{2,n^2,t^2}{sum_{i=1}^n (b_i - a_i)^2} ight),!
which is valid for positive values of "t" (where mathrm{E} [S] is the
expected value of S).This
inequality is a special case of the more general Bernstein inequality in probability theory, proved bySergei Bernstein in 1923. It is also a special case ofMcDiarmid's inequality .ee also
*
Chebyshev's inequality ,Markov's inequality andChernoff bounds .*
Azuma's inequality *
McDiarmid's inequality Primary sources
* Wassily Hoeffding, Probability inequalities for sums of bounded random variables, "Journal of the American Statistical Association" 58 (301): 13–30, March 1963. ( [http://links.jstor.org/sici?sici=0162-1459%28196303%2958%3A301%3C13%3APIFSOB%3E2.0.CO%3B2-D JSTOR] )
Wikimedia Foundation. 2010.