Mittaa keskittymiseroja

Todennäköisyysteoriassa pitoisuusepäyhtälömitat antavat arvioita satunnaismuuttujan poikkeamasta jostakin arvosta (yleensä sen matemaattisesta odotuksesta ). Klassisen todennäköisyysteorian suurten lukujen laki sanoo, että riippumattomien satunnaismuuttujien summat, jotka ovat melko heikkojen ehtojen alaisia, suurella todennäköisyydellä osoittautuvat lähellä heidän matemaattisia odotuksiaan. Tällaiset summat ovat parhaita esimerkkejä satunnaismuuttujista, jotka keskittyvät niiden keskiarvojen ympärille .

Markovin epätasa-arvo

Olkoon satunnaismuuttuja, lähes varmasti ei-negatiivinen. Sitten mihin tahansa vakioon $X$ $a>0$

P(X\geq a)\leq {\frac {\operaattorinimi {E} (X)}{a))

Huomaa seuraava lauseke Markovin epäyhtälölle: if on ei-negatiivinen tiukasti kasvava funktio, niin $\Phi$

P(X\geq a)=P(\Phi (X)\geq \Phi (a))\leq {\frac {\operaattorin nimi {E} (\Phi (X))}{\Phi (a )}}

Chebyshevin epätasa-arvo

Chebyshev-epäyhtälö edellyttää, että satunnaismuuttuja täyttää seuraavat ehdot: $X$

matemaattinen odotus tietysti; ${\näyttötyyli \operaattorin nimi {E} [X]}$
dispersio on rajallinen. ${\displaystyle \operaattorin nimi {D} [X]=\operaattorin nimi {E} [(X-\operaattorin nimi {E} [X])^{2}]=\sigma ^{2))$

Sitten mihin tahansa vakioon $a>0$

{\displaystyle P(|X-\operaattorinimi {E} [X]|\geq a)\leq {\frac {\operaattorinimi {D} [X]}{a^{2))))

tai vastaavasti

{\displaystyle P(|X-\operaattorinimi {E} [X]|\geq a\cdot \operaattorinimi {Std} [X])\leq {\frac {1}{a^{2))))

missä on satunnaismuuttujan keskihajonta . $\operaattorin nimi {Std} [X]=\sigma$ $X$

Tšebyševin epäyhtälöä voidaan pitää satunnaismuuttujaan c sovelletun yleistetyn Markovin epäyhtälön erikoistapauksena . $|X-\operaattorinimi {E} [X]|$ ${\displaystyle \Phi (x)=x^{2))$

Vysochansky-Petunin epätasa-arvo

Gaussin epäyhtälö

Tšernovin rajat

Tšernovin rajan päätapaus [1] :63–65 edellyttää generoivan funktion olemassaoloa, joka määritellään muodossa . Markovin epätasa-arvon perusteella kullekin $X$ $M_{X}(t):=\operaattorin nimi {E} \!\left[e^{tX}\right]$ $t>0$

{\displaystyle P(X\geq a)\leq {\frac {\operaattorin nimi {E} [e^{t\cdot X}]}{e^{t\cdot a))))

ja jokaiselle $t<0$

{\displaystyle P(X\leq a)\leq {\frac {\operaattorin nimi {E} [e^{t\cdot X}]}{e^{t\cdot a))))

Chernoffin rajat ovat erilaisia parametrin eri jakaumille ja eri arvoille . $t$

Riippumattomien satunnaismuuttujien summien rajat

Olkoon riippumattomia satunnaismuuttujia siten, että kaikille i: ${\displaystyle X_{1},X_{2},\dots ,X_{n))$

{\displaystyle a_{i}\leq X_{i}\leq b_{i))

melkein todennäköisesti .

c_{i}:=b_{i}-a_{i}

\forall i:c_{i}\leq C

Olkoon - niiden summa, - matemaattinen odotus ja - varianssi $S_{n}$ $E_{n}$ $D_{n}$

{\displaystyle S_{n}:=\sum _{i=1}^{n}X_{i))

E_{n}:=\operaattorinimi {E} [S_{n}]=\sum _{i=1}^{n}\operaattorinimi {E} [X_{i}]

D_{n}:=\operaattorinimi {D} [S_{n}]=\sum _{i=1}^{n}\operaattorinimi {D} [X_{i}]

Usein on mielenkiintoista arvioida eron summan ja sen matemaattisen odotuksen välillä. Useita epätasa-arvoja voidaan käyttää.

1. Hoefdingin epätasa-arvo sanoo sen

P\left[|S_{n}-E_{n}|>t\oikea]<2\exp \left(-{\frac {2t^{2}}{\sum _{i=1} ^{n}c_{i}^{2}}}\oikea)<2\exp \left(-{\frac {2t^{2}}{nC^{2}}}\oikea)

2. Satunnaismuuttuja on martingaalin ja . Siksi voidaan käyttää Azuman epäyhtälöä , joka antaa hieman heikomman arvion $(S_{n}-E_{n})$ $S_{0}-E_{0}=0$

P\left[|S_{n}-E_{n}|>t\oikea]<2\exp \left(-{\frac {t^{2}}{2\sum _{i=1 }^{n}c_{i}^{2}}}\oikea)<2\exp \left(-{\frac {t^{2}}{2nC^{2}}}\oikea)

Tässä on mahdollista ottaa huomioon kaikki martingaalit , mukaan lukien supermartingaalit ja submartingaalit .

3. Summafunktio on muuttujien funktion erikoistapaus. Tämä funktio muuttuu rajoitetusti: jos muuttuja muuttuu, myös arvo muuttuu enintään . Siksi voidaan käyttää McDiarmidin epäyhtälöä , ja se antaa samanlaisen arvion $S_{n}=f(X_{1},\pisteet ,X_{n})$ $n$ $i$ $f$ $b_{i}-a_{i}<C$

P\left[|S_{n}-E_{n}|>t\oikea]<2\exp \left(-{\frac {2t^{2}}{\sum _{i=1} ^{n}c_{i}^{2}}}\oikea)<2\exp \left(-{\frac {2t^{2}}{nC^{2}}}\oikea)

Tämä on toinen yleistys Hoefdingin epäyhtälöstä, koska tässä on mahdollista työskennellä paitsi summausfunktion, myös muiden funktioiden kanssa, jos ne muuttuvat rajoitetusti.

4. Bennettin epäyhtälö antaa jonkin verran parannusta Höfdingin epätasa-arvoon, kun termien varianssit ovat pieniä verrattuna niiden "melkein todennäköisesti-rajoihin" C .

P\left[|S_{n}-E_{n}|>t\right]\leq 2\exp \left[-{\frac {D_{n}}{C^{2}}}h \left({\frac {Ct}{D_{n}}}\right)\right],

missä

h(u)=(1+u)\log(1+u)-u

5. Ensimmäinen Bernsteinin epätasa-arvo toteaa, että

P\left[|S_{n}-E_{n}|>t\oikea]<2\exp \left(-{\frac {t^{2}/2}{D_{n}+C \cdot t/3}}\right)

Kuten Höfdingin epäyhtälö, jolle tämä arvio on yleistys, Bernsteinin ensimmäinen epäyhtälö ottaa lähes varmasti huomioon rajalliset satunnaismuuttujat. Lisäksi se mahdollistaa tarkemman arvion saamisen edellyttäen, että satunnaismuuttujien varianssit ovat rajalliset.

6. Chernoffin rajoilla on erityisen yksinkertainen muoto riippumattomien suureiden summalle, koska

\operaattorinimi {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operaattorinimi {E} [e^{t\cdot X_{i }}]}

Esimerkiksi [2] olkoon satunnaismuuttujien tyydyttävä epäyhtälö , niin alemman hännän kohdalla meillä on epäyhtälö $X_{i}$ $X_{i}\geq E(X_{i})-a_{i}-M$ $1\leq i\leq n$

P[S_{n}-E_{n}<-\lambda ]\leq \exp \left(-{\frac {\lambda ^{2)){2(D_{n}+\sum _{ i=1}^{n}a_{i}^{2}+M\lambda /3)}}\oikea)

Jos tyydyttää epätasa-arvon , niin ylemmän hännän osalta meillä on epäyhtälö $X_{i}$ $X_{i}\leq E(X_{i})+a_{i}+M$

P[S_{n}-E_{n}>\lambda ]\leq \exp \left(-{\frac {\lambda ^{2)){2(D_{n}+\sum _{i =1}^{n}a_{i}^{2}+M\lambda /3)}}\oikea)

Jos ovat riippumattomia ja tasaisesti jakautuneita, ja on varianssi , niin Chernoffin epätasa-arvon tyypillinen muoto on seuraava: $X_{i}$ $|X_{i}|\leq 1$ $\sigma ^{2}$ $X_{i}$

P[|S_{n}|\geq k\sigma ]\leq 2e^{-k^{2}/4n},\qquad 0\leq k\leq 2\sigma

7. Samanlaiset rajat löytyvät osiosta: Rademacher-jakauma (Bounds on sum)

Efron-Steinin epätasa-arvo

Efron-Steinin epäyhtälö (vaikutusepäyhtälö eli MG-varianssiestimaattori) arvioi satunnaismuuttujien yleisen funktion varianssin.

Olkoon , riippumaton, a ja niillä on sama jakauma kaikille . $X_{1}\dots X_{n}$ $X_{1}'\dots X_{n}'$ $X_{i}'$ $X_{i}$ $i$

Laita sitten $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}', X_{i+1},\pisteet ,X_{n}).$

\mathrm {D} (f(X))\leq {\frac {1}{2}}\sum _{i=1}^{n}E[(f(X)-f(X^) {(i)}))^{2}]

Dvoretsky-Kiefer-Wolfowitzin epätasa-arvo

Dvoretsky-Kiefer-Wolfowitz epäyhtälö arvioi todellisen ja empiirisen jakaumafunktion välisen eron.

Olkoon annetulle luonnolliselle luvulle riippumattomia ja identtisesti jakautuneita reaaliarvoisia satunnaismuuttujia jakaumafunktiolla . Merkitään vastaava empiirinen jakaumafunktio , joka on määritelty kaavalla $n$ ${\displaystyle X_{1},X_{2},\dots ,X_{n))$ $F$ $F_{n}$

F_{n}(x)={\frac {1}{n}}\sum _{i=1}^{n}\mathbf {1} _{\{X_{i}\leq x\ }},\qquad x\in \mathbb {R} .

On siis tapahtuman todennäköisyys, että yksi satunnaismuuttuja on pienempi kuin , ja se on niiden arvojen keskimääräinen lukumäärä otoksesta , jonka realisaatiot ovat pienempiä kuin . $F(x)$ $X$ $x$ $F_{n}(x)$ ${\displaystyle X_{1},X_{2},\dots ,X_{n))$ $x$

Sitten seuraavat yksipuoliset ja kaksipuoliset arviot pitävät paikkansa:

P\left(\sup _{x\in \mathbb {R} }{\bigl (}F_{n}(x)-F(x){\bigr )}>\varepsilon \right)\leq e^{-2n\varepsilon ^{2)),\qquad \forall \varepsilon \geq {\sqrt ({\tfrac {1}{2n))\ln 2)),

P{\Bigl (}\sup _{x\in \mathbb {R} }|F_{n}(x)-F(x)|>\varepsilon {\Bigr )}\leq 2e^{- 2n\varepsilon ^{2}},\qquad \forall \varepsilon >0.

Muistiinpanot

↑ Mitzenmacher, Michael. Todennäköisyys ja laskeminen: satunnaistetut algoritmit ja todennäköisyysanalyysi / Mitzenmacher, Michael, Upfal, Eli. - Cambridge University Press, 2005. - ISBN 0-521-83540-2 . Arkistoitu 16. huhtikuuta 2021 Wayback Machinessa
↑ Chung, tuuletin; Lu, Linyuan Vanhat ja uudet keskittymiserot . Monimutkaiset graafit ja verkot . American Mathematical Society (2010). Haettu 14. elokuuta 2018. Arkistoitu alkuperäisestä 15. huhtikuuta 2021. (määrätön)

Linkit

Karthik Sridharan, " Helpeä johdatus keskittymiseroista , arkistoitu 9. toukokuuta 2020 Wayback Machinessa " - Cornell University
Sata todennäköisyyttä/tilastollista epätasa -arvoa arkistoitu 13. huhtikuuta 2021 Wayback Machinessa . Katso "4 pitoisuuden epätasa-arvoa"