Desigualdad de Hoefding

La desigualdad de Hoefding da un límite superior a la probabilidad de que la suma de las variables aleatorias se desvíe de su valor esperado . La desigualdad de Hoefding fue demostrada por Wassily Hoefding en 1963. [1] La desigualdad de Hoefding es un caso especial de la desigualdad de Azuma-Hoefding y un caso más general de la desigualdad de Bernstein , demostrada por Sergei Bernstein en 1923. También son casos especiales de la desigualdad de MacDiarmid .

Caso especial para variables aleatorias de Bernoulli

La desigualdad de Hoefding se puede aplicar a un caso especial importante de variables aleatorias de Bernoulli distribuidas idénticamente , y como desigualdad se usa a menudo en combinatoria e informática . Considere una moneda sesgada que sale cara con probabilidad y cruz con probabilidad . Lanzamos una moneda . La expectativa matemática de cuántas veces una moneda caerá cara es . Además, la probabilidad de que una moneda caiga en cara no más de una vez se puede estimar exactamente mediante la expresión: $pags$ $1 p$ $norte$ $p\cdot n$ $k$

\Pr {\Big (}H(n)\leqslant k{\Big )}=\sum _{i=0}^{k}{\binom {n}{i}}p^{i} (1-p)^{ni}\,.

En el caso de algunos , la desigualdad de Höfding limita esta probabilidad a una expresión que decrece exponencialmente de : ${\ Displaystyle k = (p-\ varepsilon) n}$ $\varepsilon >0$ $\varepsilon^{2}\cdotn$

\Pr {\Big (}H(n)\leqslant (p-\varepsilon)n{\Big)}\leqslant \exp {\big (}-2\varepsilon ^{2}n{\big ) }\,.

De manera similar, en el caso de algunos , la desigualdad de Hoefding limita la probabilidad de caer al menos tantas caras como se esperaba por: $k=(p+\varepsilon)n$ $\varepsilon >0$ ${\ estilo de visualización \ varepsilon n}$

\Pr {\Big (}H(n)\geqslant (p+\varepsilon)n{\Big)}\leqslant \exp {\big (}-2\varepsilon ^{2}n{\big )} \,.

Así, la desigualdad de Hoefding significa que el número de caras que salen se concentra alrededor de la media, con una cola exponencialmente pequeña.

\Pr {\Big (}(p-\varepsilon)n\leqslant H(n)\leqslant (p+\varepsilon)n{\Big)}\geqslant 1-2\exp {\big (}-2 \varepsilon ^{2}n{\grande)}\,.

Caso general

Sean variables aleatorias independientes . ${\ estilo de visualización X_ {1}, \ puntos, X_ {n}}$

Suponga que están acotadas de forma casi fiable , es decir, suponga para , que: $X_{yo}$ $1 \leqslant i \leqslant n$

\Pr(X_{i}\in [a_{i},b_{i}])=1.

Determinamos la media empírica de estas variables:

{\overline {X}}=(X_{1}+\cdots +X_{n})/n\,.

El Teorema 2 de Hoeffding (1963), demuestra las desigualdades:

\Pr({\overline {X}}-\mathrm {E} [{\overline {X}}]\geqslant t)\leqslant \exp \left(-{\frac {2t^{2}n ^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}}\derecha),

\Pr(|{\overline {X}}-\mathrm {E} [{\overline {X}}]|\geqslant t)\leqslant 2\exp \left(-{\frac {2t^{ 2}n^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),

que son verdaderas para todos los valores positivos de t. Aquí está el valor esperado . $\mathrm {E} [{\overline {X}}]$ $\overline {X}$

Tenga en cuenta que la desigualdad también es cierta si se obtiene utilizando un muestreo sin reemplazo, en cuyo caso las variables aleatorias ya no son independientes. La prueba de esta afirmación se puede encontrar en el artículo de Hoefding. Para obtener estimaciones con un límite ligeramente mejor en el caso del muestreo sin sustitución, véase, por ejemplo, el artículo, [2] . $X_{yo}$

Véase también

Enlaces

Robert J. Serfling. Desigualdades de probabilidad para la suma en muestreo sin reemplazo // The Annals of Statistics. - 1974. - V. 2 , N º 1 . — págs. 39–48 . -doi : 10.1214 / aos/1176342611 .
Wassily Hoeffding. Desigualdades de probabilidad para sumas de variables aleatorias acotadas // Revista de la Asociación Estadounidense de Estadística. - 1963. - T. 58 , N º 301 . — P. 13–30 .