Koncentration ojämlikhet

I sannolikhetsteorin ger koncentrationsskillnader gränser för hur en slumpvariabel avviker från något värde (vanligtvis dess förväntade värde ). Lagen om stora antal av klassisk sannolikhetsteori säger att summor av oberoende slumpvariabler är, under mycket milda förhållanden, nära deras förväntningar med stor sannolikhet. Sådana summor är de mest grundläggande exemplen på slumpvariabler koncentrerade kring deras medelvärde . Nyligen genomförda resultat visar att sådant beteende delas av andra funktioner hos oberoende slumpvariabler.

Koncentrationsskillnader kan sorteras efter hur mycket information om den slumpmässiga variabeln som behövs för att kunna använda dem.

Markovs ojämlikhet

Huvudartikel: Markovs ojämlikhet

Låt $X$ vara en slumpvariabel som är icke-negativ ( nästan säkert ). Sedan, för varje konstant $a>0$ ,

$\Pr(X\geq a)\leq {\frac {\operatörsnamn {E} (X)}{a}}.$

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

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

Chebyshevs ojämlikhet

Huvudartikel: Chebyshevs ojämlikhet

Chebyshevs olikhet kräver följande information om en slumpvariabel $X$ :

• Det förväntade värdet $\operatörsnamn {E} [X]$ är ändligt.
• Variansen $])^{2}]}$${\displaystyle \operatörsnamn {Var} [X]=\operatörsnamn {E} [(X-\operatörsnamn {E} [$ X är ändlig.

Sedan, för varje konstant $a>0$ ,

$\Pr(|X-\operatörsnamn {E} [X]|\geq a)\leq {\frac {\operatörsnamn {Var} [X]}{a^{2}}},$

eller motsvarande,

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

där $\operatorname {Std} [X]$ är standardavvikelsen för $X$ .

Chebyshevs ojämlikhet kan ses som ett specialfall av den generaliserade Markovs olikhet tillämpad på stokastisk variabel $|X-\operatörsnamn {E} [X]|$ med $\Phi (x)=x^{2}$ .

Vysochanskij–Petunin ojämlikhet

Huvudartikel: Vysochanskij–Petunin ojämlikhet

Låt X vara en slumpvariabel med unimodal fördelning, medelvärde μ och finit, icke-noll varians σ ² . Sedan, för alla ${\textstyle \lambda >{\sqrt {\frac {8}{3}}}=1,63299\ldots ,}$

$P(\left|X-\mu \right|\geq \lambda \sigma )\leq {\frac {4}{9\lambda ^{2}}}.$

(För ett relativt elementärt bevis se t.ex. ).

Ensidig ojämlikhet Vysochanskij–Petunin

Huvudartikel: Vysochanskij–Petunin ojämlikhet

För en unimodal slumpvariabel $X$ och $r\geq 0$ gäller den ensidiga Vysochanskij-Petunin-olikheten enligt följande:

$\mathbb {P} (XE[X]\geq r)\leq {\begin{cases}{\dfrac {4}{9}}{\dfrac {\operatörsnamn {Var} (X)}{r ^{2}+\operatörsnamn {Var} (X)}}&{\text{för }}r^{2}\geq {\dfrac {5}{3}}\operatörsnamn {Var} (X),\ \[5pt]{\dfrac {4}{3}}{\dfrac {\operatörsnamn {Var} (X)}{r^{2}+\operatörsnamn {Var} (X)}}-{\dfrac {1 }{3}}&{\text{annars.}}\end{case}}$

Paley-Zygmund ojämlikhet

Huvudartikel: Paley-Zygmund ojämlikhet

Cantellis ojämlikhet

Huvudartikel: Cantellis ojämlikhet

Gauss ojämlikhet

Huvudartikel: Gauss ojämlikhet

Chernoffs gränser

Huvudartikel: Chernoff bunden

Den generiska Chernoff-gränsen kräver endast den momentgenererande funktionen av $X$ , definierad som: $M_{X}(t):=\operatörsnamn {E } \!\left[e^{tX}\right]$ , förutsatt att den finns. Baserat på Markovs ojämlikhet, för varje $t>0$ :

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

och för varje $t<0$ :

$\Pr(X\leq a)\leq {\frac {\operatörsnamn {E} [e^{t\cdot X}]}{e^{t\cdot a}}}.$

Det finns olika Chernoff-gränser för olika distributioner och olika värden på parametern $t$ . Se för en sammanställning av fler koncentrationsskillnader.

Gränser för summor av oberoende avgränsade variabler

Huvudartiklar: Hoeffdings ojämlikhet , Azumas ojämlikhet , McDiarmids ojämlikhet , Bennetts ojämlikhet och Bernsteins ojämlikheter (sannolikhetsteori)

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

$a_{i}\leq X_{i}\leq b_{i}$ nästan säkert .

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

$\forall i:c_{i}\leq C$

Låt $S_{n}$ vara deras summa, $E_{n}$ dess förväntade värde och $V_{n}$ dess varians:

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

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

$V_{n}:=\operatörsnamn {Var} [S_{n}]=\summa _ {i=1}^{n}\operatörsnamn {Var} [X_{i}]$

Det är ofta intressant att binda skillnaden mellan summan och dess förväntade värde. Flera ojämlikheter kan användas.

1. Hoeffdings ojämlikhet säger att:

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

2. Slumpvariabeln $S_{n}-E_{n}$ är ett specialfall av en martingal , och $S_{0}-E_{0}=0$ . Därför kan den allmänna formen av Azumas ojämlikhet också användas och den ger en liknande gräns:

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

Detta är en generalisering av Hoeffdings eftersom den kan hantera andra typer av martingaler, såväl som supermartingales och submartingales . Observera att om den enklare formen av Azumas olikhet används, är exponenten i gränsen sämre med en faktor 4.

3. Summafunktionen, ${\displaystyle S_{n}=f(X_{1},\dots ,X_{n})} ,$ är ett specialfall av en funktion av n variabler. Denna funktion ändras på ett begränsat sätt: om variabeln i ändras, ändras värdet på f med högst $b_{i}-a_{i}<C$ . Därför McDiarmids ojämlikhet också användas och det ger en liknande gräns:

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

Detta är en annan generalisering av Hoeffdings eftersom den kan hantera andra funktioner förutom summafunktionen, så länge de ändras på ett begränsat sätt.

4. Bennetts ojämlikhet erbjuder en viss förbättring jämfört med Hoeffdings när varianserna för summanterna är små jämfört med deras nästan säkra gränser C . Det står att:

$\Pr \left[|S_{n}-E_{n}|>t\right]\leq 2\ exp \left[-{\frac {V_{n}}{C^{2}}}h\left({\frac {Ct}{V_{n}}}\right)\right],$ där $h(u)=(1+u)\log(1+u)-u$

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

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

Detta är en generalisering av Hoeffdings eftersom den kan hantera slumpvariabler med inte bara nästan säker gräns utan både nästan säker bunden och variansbunden.

6. Chernoff-gränser har en särskilt enkel form när det gäller summan av oberoende variabler, eftersom $\operatorname {E } [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatörsnamn {E} [e^{t\cdot X_{i}}]}$ .

Anta till exempel att variablerna $X_{i}$ uppfyller $X_{i}\geq E(X_{i})-a_{i }-M$ , för $1\leq i\leq n$ . Då har vi lägre svansojämlikhet:

$\Pr[S_{n}-E_ {n}<-\lambda ]\leq \exp \left(-{\frac {\lambda ^{2}}{2(V_{n}+\summa _{i=1}^{n}a_{i }^{2}+M\lambda /3)}}\höger)$

Om $X_{i}$ uppfyller $X_{i}\leq E(X_{i})+a_{i}+M$ , vi har ojämlikhet i övre svansen:

$\Pr[S_{n}-E_{ n}>\lambda ]\leq \exp \left(-{\frac {\lambda ^{2}}{2(V_{n}+\summa _{i=1}^{n}a_{i}^ {2}+M\lambda /3)}}\höger)$

Om $X_{i}$ är iid, $|X_{i}|\leq 1$ och $\sigma ^{2}$ är variansen av $X_{i}$ , en typisk version av Chernoff-olikhet är :

$\Pr[|S_{n}|\geq k\sigma ]\leq 2e^{-k^{2}/4n}{\text{ för }}0\leq k\leq 2\sigma .$

7. Liknande gränser finns i: Rademacher distribution#Bounds on sums

Efron–Stein ojämlikhet

Efron–Stein-olikheten (eller inflytandeolikhet, eller MG bunden till varians) begränsar variansen för en allmän funktion.

Antag att $X_{1}\dots X_{n}$ , $X_{1}'\dots X_{n}'$ är oberoende med $X_{i}'$ och $X_{i}$ har samma fördelning för alla $i$ .

Låt $X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots,X_{i-1},X_{i}', X_{i+1},\dots ,X_{n}).$ Sedan

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

Bretagnolle–Huber–Carol ojämlikhet

Bretagnolle–Huber–Carol Ojämlikhet begränsar skillnaden mellan en vektor av multinomiellt fördelade slumpvariabler och en vektor med förväntade värden. Ett enkelt bevis visas i (bilaga avsnitt).

Om en slumpmässig vektor $är {\displaystyle (Z_{1},Z_{2},Z_{3},\ldots ,Z_{n})}$ multinomialt fördelad med parametrar $(p_{1},p_{2},\ldots ,p_{n})$ och uppfyller $Z_{1}+Z_{2}+\dots +Z_{n}=M,$ sedan

$\Pr \left(\sum _{i=1}^{n}|Z_{i}-Mp_{i}|\geq 2M\varepsilon \right)\leq 2^{n}e^{- 2M\varepsilon ^{2}}.$

Denna olikhet används för att begränsa det totala variationsavståndet .

Mason och van Zwet ojämlikhet

Mason och van Zwet olikheten för multinomial slumpmässiga vektorer gäller en liten modifiering av den klassiska chi-kvadratstatistiken.

Låt den slumpmässiga vektorn $(N_{1},\ldots ,N_{k})$ vara multinomiellt fördelad med parametrarna $n$ och $(p_{1},\ldots,p_{k})$ så att $p_{i}>0$ för $i<k.$ Sedan för varje $C>0$ och $\delta >0$ finns det konstanter $a,b,c> 0,$ så att för alla $n\geq 1$ och $\lambda ,p_{1},\ldots ,p_{k-1}$ som uppfyller $\lambda >Cn\min\{p_{i}|1\leq i\leq k-1\}$ och $\sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,$ vi har

$\Pr \left(\sum _{i=1}^{k-1}{\frac {(N_{i}-np_{i})^{2}}{np_{i}}}> \lambda \right)\leq ae^{bk-c\lambda }.$

Dvoretzky–Kiefer–Wolfowitz ojämlikhet

Huvudartikel: Dvoretzky–Kiefer–Wolfowitz ojämlikhet

Ojämlikheten mellan Dvoretzky–Kiefer–Wolfowitz begränsar skillnaden mellan den verkliga och den empiriska kumulativa fördelningsfunktionen .

Givet ett naturligt tal $n$ , låt $X_{1},X_{2},\dots ,X_{n}$ vara verkligt värderade oberoende och identiskt fördelade stokastiska variabler med kumulativ fördelningsfunktion F (·). Låt $F_{n}$ beteckna den associerade empiriska distributionsfunktionen definierad av

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

Så $F(x)$ är sannolikheten att en enda slumpvariabel $X$ är mindre än $x$ och $F_{n} (x)$ är det genomsnittliga antalet slumpvariabler som är mindre än $x$ .

Sedan

$\Pr \left(\sup _{x\in \mathbb {R} }{\bigl (}F_{n}(x)-F(x){\bigr )}>\varepsilon \right)\ leq e^{-2n\varepsilon ^{2}}{\text{ för varje }}\varepsilon \geq {\sqrt {{\tfrac {1}{2n}}\ln 2}}.$

Ojämlikhet mot koncentration

Anti-koncentrationsojämlikheter , å andra sidan, ger en övre gräns för hur mycket en slumpvariabel kan koncentrera sig kring en kvantitet.

Till exempel visar Rao och Yehudayoff att det finns något $C>0$ så att för de flesta riktningar av hyperkuben $x\in \{\pm 1\}^ {n}$ , följande är sant:

$\Pr \left(\langle x,Y\rangle =k\right)\leq {\frac {C}{\sqrt {n}}} ,$

där $Y$ ritas likformigt från en delmängd $B\subseteq \{\pm 1\}^{n}$ av tillräckligt stor storlek.

Sådana ojämlikheter är av betydelse inom flera områden, inklusive kommunikationskomplexitet ( t.ex. i bevis på gapet Hamming-problemet ) och grafteori .

En intressant anti-koncentrationsojämlikhet för viktade summor av oberoende Rademacher -slumpvariabler kan erhållas med Paley-Zygmund- och Khintchine -olikheterna.

externa länkar

• Karthik Sridharan, " A Gentle Introduction to Concentration Oequalities " - Cornell University