Inegalitatea lui Hoefding

Inegalitatea lui Hoefding oferă o limită superioară a probabilității ca suma variabilelor aleatoare să se abate de la valoarea sa așteptată . Inegalitatea lui Hoefding a fost dovedită de Wassily Hoefding în 1963. [1] Inegalitatea Hoefding este un caz special al inegalității Azuma-Hoefding și un caz mai general al inegalității Bernstein , dovedit de Serghei Bernstein în 1923. Sunt, de asemenea, cazuri speciale de inegalitate a lui MacDiarmid .

Caz special pentru variabile aleatoare Bernoulli

Inegalitatea lui Hoefding poate fi aplicată unui caz special important de variabile aleatoare Bernoulli distribuite identic , iar ca inegalitate este adesea folosită în combinatorică și informatică . Luați în considerare o monedă părtinitoare care iese din cap cu probabilitate și cozi cu probabilitate . Aruncăm o monedă . Așteptarea matematică de câte ori va ateriza o monedă capete este de . În plus, probabilitatea ca o monedă să cadă pe capete nu mai mult de o dată poate fi estimată exact prin expresia: $p$ $1-p$ $n$ $p\cdot n$ $k$

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

În cazul unora , inegalitatea lui Höfding limitează această probabilitate la o expresie care scade exponențial de la : $k=(p-\varepsilon )n$ $\varepsilon >0$ $\varepsilon ^{2}\cdot n$

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

În mod similar, în cazul unora , inegalitatea lui Hoefding limitează probabilitatea de a ateriza cel puțin atâtea capete cât se așteaptă de: $k=(p+\varepsilon )n$ $\varepsilon >0$ $\varepsilon n$

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

Astfel, inegalitatea lui Hoefding înseamnă că numărul de capete care apar este concentrat în jurul mediei, cu o coadă exponențial mică.

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

Caz general

Fie variabile aleatoare independente . $X_{1},\dots ,X_{n}$

Să presupunem că sunt mărginite aproape sigur , adică să presupunem că pentru , că: $X_{i}$ $1 \leqslant i \leqslant n$

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

Determinăm media empirică a acestor variabile:

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

Teorema 2 din Hoeffding (1963), demonstrează inegalitățile:

\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}}}\right),

\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),

care sunt adevărate pentru toate valorile pozitive ale lui t. Iată valoarea așteptată . $\mathrm {E} [{\overline {X}}]$ $\overline {X}$

Rețineți că inegalitatea este adevărată și dacă este obținută folosind eșantionarea fără înlocuire, caz în care variabilele aleatoare nu mai sunt independente. Dovada acestei afirmații poate fi găsită în lucrarea lui Hoefding. Pentru estimări legate puțin mai bune în cazul eșantionării fără înlocuire, a se vedea, de exemplu, articolul, [2] . $X_{i}$

Vezi și

Link -uri

Robert J. Serfling. Inegalități de probabilitate pentru suma din eșantionarea fără înlocuire // The Annals of Statistics. - 1974. - V. 2 , nr 1 . — p. 39–48 . - doi : 10.1214/aos/1176342611 .
Wassily Hoeffding. Inegalități de probabilitate pentru sumele variabilelor aleatoare mărginite // Journal of the American Statistical Association. - 1963. - T. 58 , Nr. 301 . — S. 13–30 .