Desigualtat de Hoeffding

En teoria de la provabilitat, la desigualtat de Hoeffding proporciona una cota superior a la provabilitat de que la suma de variables aleatòries es desvie una certa cantitat de la seua valor esperat. La desigualtat de Hoeffding va ser demostrada per Wassily Hoeffding en 1963.

La desigualtat de Hoeffding és un cas particular de la desigualtat de Azuma-Hoeffding, encara que generalisa la desigualtat de Bernstein, demostrada per Sergei Bernstein en 1923. Abdós són casos especials de la desigualtat de McDiarmid.

Cas particular de variables de Bernouilli

La desigualtat de Hoeffding pot aplicar-se a l'important especial de variables de Bernouilli idénticamente distribuïdes, i est és la manera en que la desigualtat s'aplica freqüentment en combinatòria i en informàtica.

Si es considera una moneda desequilibrada que mostra cara en provabilitat $p$ i creu en provabilitat $1-p$, i es consideren $n$ llançaments d'esta moneda. El valor esperat del número de voltes que s'obté cara és $p\cdot n$. Més encara, la provabilitat de que s'obtinguen com a molt $k$ cares pot quantificar-se exactament per mig de la següent expressió:

En el cas de que $k=(p-ϵ)n$ per a algun $ϵ>0$, la desigualtat de Hoeffding acota esta provabilitat per mig d'un terme que disminuïx exponencialment en ${ϵ}^2\cdot n$:

De manera similar, en el cas de que $k=(p+ϵ)n$ per a algun $ϵ>0$, la desigualtat de Hoeffding acota la provabilitat de que s'obtinguen a lo manco $ϵn$ un número de cares major que el valor esperat:

En eixes condicions la desigualtat de Hoeffding implica que el número de cares que s'obtenen es concentra al voltant de la mija, en coes que decreixen exponencialment.

Cas general

Sean $X_1,\dots ,X_n$ n variables aleatòries independents. Si s'assumix que les $X_i$ estan acotades casi en seguritat; és dir, si s'assumix per a $1\le i\le n$ que:

Es definix la mija mostral d'estes variables com:

La segona teorema en l'artícul de Hoeffding prova les següents desigualtats:

que són vàlides per a valors positius de t. Ací $\mathrm{E}[\bar{X}]$ representa el valor esperat de $\bar{X}$.

Note's que les desigualtats també són vàlides quan les $X_i$ han segut obtingudes usant mostreig sense tongada; en este cas les variables aleatòries no són de cap manera independents. Una demostració d'esta afirmació pot trobar-se en l'artícul de Hoeffding. Per a cotes llaugerament millors en el cas de mostreig sense tongada, pot consultar-se l'artícul de Serfling (1974).

Vore també

• Desigualtat de Chebyshov
• Desigualtat de Markov