Mäta ojämlikhet i koncentrationen

I sannolikhetsteorin ger mätningar av koncentrationsojämlikheter uppskattningar av avvikelsen för en slumpvariabel från något värde (vanligtvis från dess matematiska förväntningar ). Lagen om stora antal av klassisk sannolikhetsteori säger att summan av oberoende slumpvariabler, under förutsättning av ganska svaga förhållanden, med hög sannolikhet visar sig ligga nära deras matematiska förväntningar. Sådana summor är utmärkta exempel på slumpvariabler som är koncentrerade kring deras medelvärden .

Markovs ojämlikhet

Låt en slumpmässig variabel, nästan säkert icke-negativ. Sedan, för vilken konstant som helst $X$ $a>0$

P(X\geq a)\leq {\frac {\operatörsnamn {E} (X)}{a))

Notera följande uttryck för Markovs ojämlikhet: om är en icke-negativ strikt ökande funktion, då $\Phi$

P(X\geq a)=P(\Phi (X)\geq \Phi (a))\leq {\frac {\operatörsnamn {E} (\Phi (X))}{\Phi (a )}}

Chebyshevs ojämlikhet

Chebyshev-ojämlikheten kräver att den slumpmässiga variabeln uppfyller följande villkor: $X$

matematiska förväntningar såklart; $\operatörsnamn {E} [X]$
spridningen är ändlig. ${\displaystyle \operatörsnamn {D} [X]=\operatörsnamn {E} [(X-\operatörsnamn {E} [X])^{2}]=\sigma ^{2))$

Sedan för någon konstant $a>0$

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

eller på motsvarande sätt

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

var är standardavvikelsen för den slumpmässiga variabeln . $\operatörsnamn {Std} [X]=\sigma$ $X$

Chebyshev-ojämlikheten kan betraktas som ett specialfall av den generaliserade Markov-olikheten som tillämpas på den slumpmässiga variabeln c . $|X-\operatörsnamn {E} [X]|$ ${\displaystyle \Phi (x)=x^{2))$

Vysochansky-Petunin ojämlikhet

Gaussisk ojämlikhet

Chernovs gränser

Huvudfallet med Chernov-gränsen [1] :63–65 kräver att det finns en genererande funktion definierad som . Baserat på Markov ojämlikhet, för varje $X$ $M_{X}(t):=\operatörsnamn {E} \!\left[e^{tX}\right]$ $t>0$

{\displaystyle P(X\geq a)\leq {\frac {\operatörsnamn {E} [e^{t\cdot X}]}{e^{t\cdot a))))

och för varje $t<0$

{\displaystyle P(X\leq a)\leq {\frac {\operatörsnamn {E} [e^{t\cdot X}]}{e^{t\cdot a))))

Chernoff-gränserna är olika för olika distributioner och olika värden på parametern . $t$

Gränser för summor av oberoende slumpvariabler

Låta vara oberoende slumpvariabler så att för alla i: ${\displaystyle X_{1},X_{2},\dots ,X_{n))$

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

nästan troligen .

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

\forall i:c_{i}\leq C

Låt - deras summa, - matematisk förväntan och - varians $S_{n}$ $E_{n}$ $D_{n}$

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

E_{n}:=\operatörsnamn {E} [S_{n}]=\summa _{i=1}^{n}\operatörsnamn {E} [X_{i}]

D_{n}:=\operatörsnamn {D} [S_{n}]=\summa _{i=1}^{n}\operatörsnamn {D} [X_{i}]

Det är ofta av intresse att uppskatta skillnaden mellan summan och dess matematiska förväntan. Flera ojämlikheter kan användas.

1. Hoefdings ojämlikhet säger att

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

2. En slumpvariabel är ett specialfall av martingal , och . Därför kan man använda Azumas ojämlikhet , vilket ger en något svagare uppskattning $(S_{n}-E_{n})$ $S_{0}-E_{0}=0$

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

Här blir det möjligt att överväga vilken martingal som helst , inklusive supermartingaler och submartingales .

3. Summeringsfunktionen är ett specialfall av en funktion av variabler. Denna funktion ändras på ett begränsat sätt: om variabeln ändras ändras värdet också med högst . Därför kan man använda McDiarmids inequality , och det kommer att ge en liknande uppskattning $S_{n}=f(X_{1},\dots ,X_{n})$ $n$ $i$ $f$ $b_{i}-a_{i}<C$

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

Detta är ytterligare en generalisering av Hoefdings ojämlikhet, eftersom det här är möjligt att arbeta inte bara med summeringsfunktionen, utan även med andra funktioner om de förändras på ett begränsat sätt.

4. Bennetts ojämlikhet ger en viss förbättring jämfört med Höfdings ojämlikhet när termernas varianser är små jämfört med deras "nästan troligen-gränser" 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],

var

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

5. Den första av Bernsteins ojämlikheter säger att

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

Liksom Höfdings ojämlikhet, för vilken denna uppskattning är en generalisering, tar Bernsteins första olikhet nästan säkert hänsyn till avgränsade slumpvariabler. Dessutom tillåter det en att få en mer exakt uppskattning, förutsatt att de slumpmässiga variablerna har begränsade varianser.

6. Chernoff-gränserna har en särskilt enkel form för summan av oberoende storheter, eftersom

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

Till exempel, [2] låt de slumpmässiga variablerna tillfredsställa olikheten för , då för den nedre svansen har vi olikheten $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}+\summa _{ i=1}^{n}a_{i}^{2}+M\lambda /3)}}\right)

Om tillfredsställer ojämlikheten , så har vi ojämlikheten för den övre svansen $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}+\summa _{i =1}^{n}a_{i}^{2}+M\lambda /3)}}\right)

Om är oberoende och jämnt fördelade, och är variansen av , då är den typiska formen av Chernoff-ojämlikheten följande: $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. Liknande gränser finns i avsnittet: Rademacher-fördelning (gränser för summor)

Efron-Stein ojämlikhet

Efron-Stein-olikheten (inflytandeolikhet eller MG-variansskattare) uppskattar variansen för en allmän funktion av slumpvariabler.

Låt , vara oberoende, a och ha samma fördelning för alla . $X_{1}\dots X_{n}$ $X_{1}'\dots X_{n}'$ $X_{i}'$ $X_{i}$ $i$

Lägg sedan $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots,X_{i-1},X_{i}', X_{i+1},\dots ,X_{n}).$

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

Dvoretsky-Kiefer-Wolfowitz ojämlikhet

Dvoretsky-Kiefer-Wolfowitz ojämlikhet uppskattar skillnaden mellan de faktiska och empiriska fördelningsfunktionerna .

Låt för ett givet naturligt tal vara oberoende och identiskt fördelade reella slumpvariabler med fördelningsfunktionen . Låt beteckna motsvarande empiriska fördelningsfunktion , definierad av formeln $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} .

Således är sannolikheten för en händelse att en enda slumpmässig variabel är mindre än , och är det genomsnittliga antalet värden från urvalet , vars realiseringar är mindre än . $F(x)$ $X$ $x$ $F_{n}(x)$ ${\displaystyle X_{1},X_{2},\dots ,X_{n))$ $x$

Då är följande ensidiga och tvåsidiga uppskattningar sanna:

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.

Anteckningar

↑ Mitzenmacher, Michael. Sannolikhet och beräkning: Randomiserade algoritmer och probabilistisk analys / Mitzenmacher, Michael, Upfal, Eli. - Cambridge University Press, 2005. - ISBN 0-521-83540-2 . Arkiverad 16 april 2021 på Wayback Machine
↑ Chung, Fan; Lu, Linyuan Gamla och nya koncentrationsskillnader . Komplexa grafer och nätverk . American Mathematical Society (2010). Hämtad 14 augusti 2018. Arkiverad från originalet 15 april 2021. (obestämd)

Länkar

Karthik Sridharan, " A Gentle Introduction to Concentration Inequalities Archived 9 maj 2020 at the Wayback Machine " - Cornell University
Hundra sannolikhet/statistik ojämlikheter Arkiverad 13 april 2021 på Wayback Machine . Se "4 koncentrationsskillnader"