Hoefdingin epätasa-arvo

Hoefdingin epäyhtälö antaa ylärajan todennäköisyydelle , että satunnaismuuttujien summa poikkeaa odotusarvostaan . Hoefdingin eriarvoisuuden todisti Wassily Hoefding vuonna 1963. [1] Hoefdingin epäyhtälö on erikoistapaus Azuma-Hoefdingin epäyhtälöstä ja yleisempi tapaus Bernsteinin epäyhtälöstä , jonka Sergei Bernstein todisti vuonna 1923. Ne ovat myös MacDiarmidin eriarvoisuuden erikoistapauksia .

Erikoistapaus Bernoullin satunnaismuuttujille

Hoefdingin epäyhtälöä voidaan soveltaa identtisesti jakautuneiden Bernoullin satunnaismuuttujien tärkeässä erikoistapauksessa , ja epäyhtälönä käytetään usein kombinatoriikassa ja tietojenkäsittelytieteessä . Harkitse puolueellista kolikkoa, joka nousee esiin todennäköisyydellä ja hännän todennäköisyydellä . Heitämme kolikon . Matemaattinen odotus siitä, kuinka monta kertaa kolikon päät laskeutuvat, on . Lisäksi todennäköisyys, että kolikko osuu päähän vain kerran, voidaan arvioida tarkasti lausekkeella: $s$ $1-s$ $n$ $p\cdot n$ $k$

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

Joidenkin tapauksessa Höfdingin epäyhtälö rajoittaa tämän todennäköisyyden lausekkeeseen, joka pienenee eksponentiaalisesti arvosta : $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 ) }\,.

Samoin joidenkin tapauksessa Hoefdingin epätasa-arvo rajoittaa todennäköisyyttä saada vähintään niin monta päätä kuin on odotettu: $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 )} \,.

Siten Hoefdingin epätasa-arvo tarkoittaa, että esiin tulevien päiden lukumäärä keskittyy keskiarvon ympärille eksponentiaalisesti pienellä häntällä.

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

Yleinen tapaus

Olkoon riippumattomia satunnaismuuttujia . $X_{1},\dots ,X_{n}$

Oletetaan, että ne ovat lähes luotettavasti rajattuja, eli oletetaan , että: $X_{i}$ $1 \leqslant i \leqslant n$

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

Määritämme näiden muuttujien empiirisen keskiarvon:

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

Hoeffdingin (1963) lause 2 todistaa epäyhtälöt:

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

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

jotka pätevät kaikille t:n positiivisille arvoille. Tässä odotettu arvo . $\mathrm {E} [{\overline {X}}]$ $\overline {X}$

Huomaa, että epäyhtälö on myös totta, jos se saadaan otoksella ilman korvausta, jolloin satunnaismuuttujat eivät ole enää riippumattomia. Todiste tälle väitteelle löytyy Hoefdingin paperista. Hieman paremmin sidotut estimaatit ei-korvaavan otannan tapauksessa, katso esimerkiksi artikkeli [2] . $X_{i}$

Katso myös

Linkit

Robert J. Serfling. Todennäköisyysepäyhtälöt summalle otannoissa ilman korvausta // The Annals of Statistics. - 1974. - V. 2 , nro 1 . — s. 39–48 . - doi : 10.1214/aos/1176342611 .
Wassily Hoeffding. Todennäköisyysepäyhtälöt rajattujen satunnaismuuttujien summille // Journal of the American Statistical Association. - 1963. - T. 58 , nro 301 . - S. 13-30 .