Hoefdings ulighed
Hoefdings ulighed giver en øvre grænse for sandsynligheden for, at summen af stokastiske variable afviger fra dens forventede værdi . Hoefdings ulighed blev bevist af Wassily Hoefding i 1963. [1] Hoefding-uligheden er et specialtilfælde af Azuma-Hoefding-uligheden og et mere generelt tilfælde af Bernstein-uligheden , bevist af Sergei Bernstein i 1923. De er også særlige tilfælde af MacDiarmids ulighed .
Særligt tilfælde for Bernoulli tilfældige variabler
Hoefdings ulighed kan anvendes på et vigtigt specialtilfælde af identisk fordelte Bernoulli stokastiske variable , og som en ulighed bruges ofte i kombinatorik og datalogi . Overvej en partisk mønt, der kommer op med hoveder med sandsynlighed og haler med sandsynlighed . Vi slår en mønt . Den matematiske forventning om, hvor mange gange en mønt vil lande hoveder, er . Desuden kan sandsynligheden for, at en mønt lander på hoveder ikke mere end én gang, estimeres nøjagtigt ved udtrykket:
I tilfældet for nogle begrænser Höfdings ulighed denne sandsynlighed til et udtryk, der falder eksponentielt fra :
På samme måde begrænser Hoefdings ulighed for nogle tilfælde sandsynligheden for at lande mindst lige så mange hoveder som forventet af:
Således betyder Hoefdings ulighed, at antallet af hoveder, der kommer op, er koncentreret omkring middelværdien med en eksponentielt lille hale.
Generel sag
Lade være uafhængige stokastiske variable .
Antag, at er næsten pålideligt afgrænset, det vil sige, antag for , at:
![{\displaystyle \Pr(X_{i}\in [a_{i},b_{i}])=1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9af9259a76be1722ad3b8418b0ee0c08820a98d9)
Vi bestemmer det empiriske gennemsnit af disse variable:
Sætning 2 fra Hoeffding (1963), beviser ulighederne:
![{\displaystyle \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),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5d509b0b28ca0848edf854fdcc0d067c5f9f1f1)
![{\displaystyle \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),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/856605af1201092ff6becd66d7f953843d4af4cc)
som er sande for alle positive værdier af t. Her er den forventede værdi .
![{\displaystyle \mathrm {E} [{\overline {X}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4c9357e5f7e859a52fbe40a16d5c90aa7501945)
Bemærk, at uligheden også er sand, hvis den opnås ved hjælp af stikprøve uden erstatning, i hvilket tilfælde de stokastiske variable ikke længere er uafhængige. Beviset for denne påstand kan findes i Hoefdings papir. For lidt bedre bundne estimater i tilfælde af ikke-erstattende prøvetagning, se for eksempel artiklen, [2] .
Se også
Noter
Links
- Robert J. Serfling. Sandsynlighedsuligheder for summen i prøveudtagning uden erstatning // Statistikkens annaler. - 1974. - V. 2 , nr. 1 . — s. 39–48 . - doi : 10.1214/aos/1176342611 .
- Wassily Hoeffding. Sandsynlighedsuligheder for summer af afgrænsede stokastiske variable // Journal of the American Statistical Association. - 1963. - T. 58 , nr. 301 . — S. 13–30 .