Inegalitatea Hoeffding

Inegalitatea Hoeffding ne permite să indicăm probabilitatea maximă ca suma variabilelor aleatorii limitate și independente să depășească suma valorilor lor așteptate cu o anumită cantitate. Această inegalitate a fost publicată de Wassily Hoeffding în 1963 și joacă un rol important în teoria statisticilor neparametrice datorită puținelor ipoteze făcute cu privire la vc

Teorema

Lasa-i sa fie $X_{1},...,X_{n}$ ${\ displaystyle X_ {1}, ..., X_ {n}}$ $X_ {1}, ..., X_ {n}$ n variabile aleatoare independente dar limitate în valorile lor minime și maxime pentru care

P(a_{i}\leq X_{i}\leq b_{i})=1

{\ displaystyle P (a_ {i} \ leq X_ {i} \ leq b_ {i}) = 1}

{\ displaystyle P (a_ {i} \ leq X_ {i} \ leq b_ {i}) = 1}

Și

-\infty <a_{i},b_{i}<+\infty

{\ displaystyle - \ infty <a_ {i}, b_ {i} <+ \ infty}

{\ displaystyle - \ infty <a_ {i}, b_ {i} <+ \ infty}

pentru

i=1,...,n

{\ displaystyle i = 1, ..., n}

{\ displaystyle i = 1, ..., n}

și să fie S suma lor

S=X_{1}+...+X_{n}

{\ displaystyle S = X_ {1} + ... + X_ {n}}

{\ displaystyle S = X_ {1} + ... + X_ {n}}

și E [S] valoarea așteptată a sumei S

asa de

P(S-E[S]\geq t)\leq e^{-{\frac {2t^{2}}{\sum (b_{i}-a_{i})^{2}}}}

{\ displaystyle P (SE [S] \ geq t) \ leq e ^ {- {\ frac {2t ^ {2}} {\ sum (b_ {i} -a_ {i}) ^ {2}}}} }

{\ displaystyle P (SE [S] \ geq t) \ leq e ^ {- {\ frac {2t ^ {2}} {\ sum (b_ {i} -a_ {i}) ^ {2}}}} }

pentru t> 0

Dacă ne interesează nu suma, ci media, atunci inegalitatea devine

P(M-\mu \geq \delta )\leq e^{-{\frac {2n^{2}\delta ^{2}}{\sum (b_{i}-a_{i})^{2}}}}

{\ displaystyle P (M- \ mu \ geq \ delta) \ leq e ^ {- {\ frac {2n ^ {2} \ delta ^ {2}} {\ sum (b_ {i} -a_ {i}) ^ {2}}}}}

{\ displaystyle P (M- \ mu \ geq \ delta) \ leq e ^ {- {\ frac {2n ^ {2} \ delta ^ {2}} {\ sum (b_ {i} -a_ {i}) ^ {2}}}}}

pentru

\delta

{\ displaystyle \ delta}

\ delta

> 0

unde este $M={\frac {1}{n}}S$ ${\ displaystyle M = {\ frac {1} {n}} S}$ ${\ displaystyle M = {\ frac {1} {n}} S}$ Și $\mu ={\frac {1}{n}}E[S]$ ${\ displaystyle \ mu = {\ frac {1} {n}} E [S]}$ ${\ displaystyle \ mu = {\ frac {1} {n}} E [S]}$ .

Exemplu

Gândiți-vă la aruncarea de n = 10 zaruri cu șase fețe și la numerele de la a = 1 la b = 6, despre care nu știm dacă sunt trucate sau nu și, prin urmare, nu putem presupune variabila uniformă aleatorie și nici măcar un generic vc dintre care știm că înseamnă varianță (în cazul zarurilor „dreapta” media este egală cu 3,5 și varianța este egală cu 2,91667).

Cu toate acestea, datorită inegalității Hoeffding, se poate afirma că probabilitatea ca suma S a acestor 10 zaruri să depășească suma adevărată (și necunoscută) a valorilor așteptate (E [S]) cu t = 10 nu este cu siguranță mai mare de 45%, în cât

P(S-E[S]\geq 10)\leq e^{-{\frac {210^{2}}{\sum (6-1)^{2}}}}=e^{-{\frac {200}{105^{2}}}}=e^{-{\frac {200}{250}}}=0,4493...

{\ displaystyle P (SE [S] \ geq 10) \ leq e ^ {- {\ frac {210 ^ {2}} {\ sum (6-1) ^ {2}}}} = e ^ {- { \ frac {200} {105 ^ {2}}}} = e ^ {- {\ frac {200} {250}}} = 0.4493 ...}

{\ displaystyle P (SE [S] \ geq 10) \ leq e ^ {- {\ frac {210 ^ {2}} {\ sum (6-1) ^ {2}}}} = e ^ {- { \ frac {200} {105 ^ {2}}}} = e ^ {- {\ frac {200} {250}}} = 0.4493 ...}

Aceasta înseamnă că dacă, să spunem cazul, suma celor 10 zaruri se dovedește a fi S = 47, atunci cu o încredere mai mare de 55% putem spune că media teoretică a celor zece zaruri este mai mică sau egală cu 37 (E [S] ≤ 47-10).

Rețineți că nici nu s-a făcut ipoteza că cele zece zaruri au fost încărcate în mod egal, darămite că zarurile nu sunt încărcate. Nici o presupunere nu a fost făcută cu privire la varianța celor zece variabile aleatorii corespunzătoare celor zece zaruri.

Presupunând în schimb că cele zece zaruri sunt toate „corecte”, atunci am fi putut afirma că probabilitatea ca suma celor zece zaruri să dea 45 sau mai mult este egală cu 4%, mult mai mică decât valoarea maximă indicată de inegalitatea Hoeffding. Această diferență se explică, de exemplu, prin faptul că puținele ipoteze făcute pentru inegalitate fac posibilă formularea unor afirmații valabile atât pentru zarurile „corecte”, cât și pentru zarurile încărcate puternic, inclusiv printre altele zarurile încărcate indicând pe cinci fețe valoarea 1 și pe a șasea valoarea 6, ignorând valorile intermediare.

Bibliografie

Wassily Hoeffding , Inegalități de probabilitate pentru sume de variabile aleatorii mărginite , în Journal of the American Statistical Association , 1963.

Elemente conexe

Inegalitatea lui Cebicev , care necesită cunoașterea varianței , dar variabilele nu sunt neapărat limitate
Inegalitatea lui Bernstein , care necesită cunoașterea varianței și variabilele sunt mărginite

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică