Chernov poäng

Chernovs uppskattning ger exponentiellt minskande uppskattningar av sannolikheten för stora avvikelser av summor av oberoende slumpvariabler . Dessa uppskattningar är mer exakta än uppskattningar som erhålls med hjälp av första eller andra ögonblick, såsom Markovs ojämlikhet eller Chebyshevs ojämlikhet , som bara ger en kraftlag av minskande. Samtidigt kräver Chernovs uppskattning att de stokastiska variablerna är oberoende i aggregatet, ett villkor som varken Markovs olikhet eller Chebyshevs olikhet kräver, även om Chebyshevs olikhet kräver parvis oberoende av stokastiska variabler.

Chernovs uppskattning är relaterad till Bernsteins ojämlikheter och Höfdings ojämlikhet , som föregår den historiskt.

Grundläggande fall

Huvudfallet med Chernov-uppskattningen för en slumpvariabel uppnås genom att tillämpa Markovs olikhet på e tX [1] . För alla $X$ $t>0$

P(X\geq a)=P(e^{t\cdot X}\geq e^{t\cdot a})\leq {\frac {\mathrm {E} \left[e^{t \cdot X}\right]}{e^{t\cdot a}}}.

När X är summan av n slumpvariabler X 1 , ... , X n , för någon $t>0$

P(X\geq a)\leq e^{-ta}\mathrm {E} \left[\prod _{i}e^{t\cdot X_{i}}\right].

Vi får i synnerhet optimera med avseende på t och anta att X i är oberoende

P(X\geq a)\leq \min _{t>0}e^{-ta}\prod _{i}\mathrm {E} \left[e^{tX_{i}}\right ].

(ett)

Liknande

P(X\leq a)=P\left(e^{-tX}\geq e^{-ta}\right)

och sålunda,

P(X\leq a)\leq \min _{t>0}e^{ta}\prod _{i}\mathrm {E} \left[e^{-tX_{i}}\right ].

Specifika värden av Chernovs uppskattningar erhålls genom beräkning för specifika kvantiteter . $\mathrm {E} \left[e^{-t\cdot X_{i}}\right]$ $X_{i}$

Exempel

Låt X 1 , ..., X n vara oberoende Bernoulli-slumpvariabler vars summa är X , och var och en är lika med 1 med sannolikhet . För en Bernoulli-variabel gäller följande: $p>0,5$

\mathrm {E} \left[e^{t\cdot X_{i}}\right]=(1-p)e^{0}+pe^{t}=1+p(e^{ t}-1)\leq e^{p(e^{t}-1)},

Följaktligen,

\mathrm {E} \left[e^{t\cdot X}\right]\leq e^{n\cdot p(e^{t}-1)}.

För alla och , vi erhåller $\delta>0$ $t=\ln(1+\delta )>0$ $a=(1+\delta )np$

{\displaystyle \mathrm {E} \left[e^{t\cdot X}\right]\leq e^{\delta np))

e^{-ta}={\frac {1}{(1+\delta )^{(1+\delta )np))},

och det allmänna fallet med Chernoff-uppskattningen ger [2] :64

P[X\geq (1+\delta )np]\leq {\frac {e^{\delta np)){(1+\delta )^{(1+\delta )np))}= \left[{\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\right]^{np}.

Sannolikheten för samtidig förekomst av fler än n /2 händelser { X k = 1 } är exakt lika med:

P\left[X>{n \over 2}\right]=\sum _{i=\lfloor {\tfrac {n}{2))\rfloor +1}^{n}{\binom { n}{i}}p^{i}(1-p)^{ni}.

Den lägre uppskattningen av denna sannolikhet kan beräknas med Chernoff-ojämlikheten:

P\left[X>{n \over 2}\right]\geq 1-e^{-{\frac {1}{2p}}n\left(p-{\frac {1}{2 }}\right)^{2}}.

Med beteckningen μ = np får vi faktiskt den multiplikativa formen av Chernoff-uppskattningen (se nedan eller följd 13.3 i Sinclairs klassanteckningar) [3] :

{\begin{aligned}P\left(X\leq \left\lfloor {\tfrac {n}{2}}\right\rfloor \right)&=P\left(X\leq \left(1) -\left(1-{\tfrac {1}{2p}}\right)\right)\mu \right)\\&\leq e^{-{\frac {\mu }{2}}\left( 1-{\frac {1}{2p}}\right)^{2}}\\&=e^{-{\frac {n}{2p}}\left(p-{\frac {1}{ 2}}\right)^{2}.}\end{aligned}}

Detta resultat tillåter olika generaliseringar, som noteras nedan. Flera former av Chernoff-uppskattningar kan noteras: den ursprungliga additiva formen (ger en uppskattning för det absoluta felet ) eller den mer praktiska multiplikationsformen (begränsar felet med avseende på medelvärdet).

Additiv form (utvärdering för absolut fel)

Följande teorem bevisades av Wassily Hoefding [4] .

Chernov-Hoefding-satsen . Låt X 1 , ..., Xn vara oberoende identiskt fördelade slumpvariabler med värdena {0, 1}. Låt p = E[ X ] och ε > 0 . Sedan

{\begin{aligned}P\left({\frac {1}{n}}\summa X_{i}\geq p+\varepsilon \right)\leq \left(\left({\frac {p }{p+\varepsilon }}\right)^{p+\varepsilon }{\left({\frac {1-p}{1-p-\varepsilon }}\right)}^{1-p-\varepsilon } \right)^{n}&=e^{-D(p+\varepsilon \parallel p)n},\\P\left({\frac {1}{n))\summa X_{i}\leq p -\varepsilon \right)\leq \left(\left({\frac {p}{p-\varepsilon }}\right)^{p-\varepsilon }{\left({\frac {1-p}{ 1-p+\varepsilon }}\right)}^{1-p+\varepsilon }\right)^{n}&=e^{-D(p-\varepsilon \parallel p)n},\end{aligned} }

var

D(x\parallel y)=x\ln {\frac {x}{y}}+(1-x)\ln \left({\frac {1-x}{1-y}}\ höger).

Detta är Kullback-Leibler-divergensen mellan slumpvariabler som har en Bernoulli-fördelning med parametrarna x respektive y . Om p ≥ett2, då

P\left(\sum X_{i}>np+x\right)\leq \exp \left(-{\frac {x^{2}}{2np(1-p)))\right) .

En enklare skattning erhålls genom att försvaga denna sats med olikheten D ( p + ε || p ) ≥ 2 ε 2 , som följer av konvexiteten för D ( p + ε || p ) och det faktum att

{\frac {d^{2}}{d\varepsilon ^{2}}}D(p+\varepsilon \parallel p)={\frac {1}{(p+\varepsilon )(1-p- \varepsilon )}}\geq 4={\frac {d^{2}}{d\varepsilon ^{2}}}(2\varepsilon ^{2}).

Detta resultat är ett specialfall av Hoefdings ojämlikhet . I vissa fall används uppskattningar

{\begin{aligned}D((1+x)p\parallel p)\geq {\frac {1}{4}}x^{2}p,&&&{-{\tfrac {1}{ 2))}\leq x\leq {\tfrac {1}{2)),\\[6pt]D(x\parallell y)\geq {\frac {3(xy)^{2}}{2( 2y+x)}},\\[6pt]D(x\parallell y)\geq {\frac {(xy)^{2}}{2y}},&&&x\leq y,\\[6pt]D( x\parallell y)\geq {\frac {(xy)^{2}}{2x}},&&&x\geq y\end{aligned}}

starkare för p <ettåtta.

Multiplikativ form (uppskattning för relativt fel)

Multiplikativ Chernov uppskattning . Låt X 1 , ..., Xn vara oberoende slumpvariabler med värdena { 0, 1}. Låt oss beteckna deras summa med X , låt oss beteckna förväntan på denna summa med μ . Sedan för varje

\delta \geq 0

P(X\geq (1+\delta )\mu )\leq \left({\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\ höger)^{\mu }.

På liknande sätt kan man visa det för vilken som helst $0<\delta <1,$

P(X\leq (1-\delta )\mu )\leq \left({\frac {e^{-\delta }}{(1-\delta )^{1-\delta }}} \right)^{\mu }.

I praktiken visar sig ovanstående formel ofta vara besvärlig [2] , så svagare men bekväma uppskattningar används

P(X\leq (1-\delta )\mu )\leq e^{-{\frac {\delta ^{2}\mu }{2))},\qquad 0<\delta <1 ,

P(X\geq (1+\delta )\mu )\leq e^{-{\frac {\delta ^{2}\mu}{2+\delta ))},\qquad 0\leq \delta ,

som erhålls med hjälp av en olikhet från listan över logaritmiska olikheter [5] . Eller en ännu svagare ojämlikhet ${\frac {2\delta }{2+\delta }}\leq \ln(1+\delta )$

P(X\geq (1+\delta )\mu )\leq e^{-{\frac {\delta ^{2}\mu}{3))},\qquad 0<\delta \leq ett.

Applikationer

Chernovs uppskattningar har tillämpningar inom setbalansering och paketrouting i glesa nätverk .

Problemet med balansering av mängder uppstår vid utformningen av ett statistiskt experiment . Vanligtvis, när vi utformar ett statistiskt experiment med deltagaregenskaper som ges i det experimentet, måste vi dela upp deltagarna i två icke-överlappande grupper så att varje egenskap är så balanserad som möjligt mellan de två grupperna. Se även Probability and Computing: Randomized Algorithms and Probabilistic Analysis Arkiverad 16 april 2021 på Wayback Machine .

Chernoff-uppskattningar används också för att uppnå hårda gränser i routingproblem med hjälp av permutationer. Detta minskar routingstockning i glesa nätverk. Se mer i Probability and Computing: Randomized Algorithms and Probabilistic Analysis Arkiverad 16 april 2021 på Wayback Machine .

Dessutom används Chernoff-uppskattningar i teorin om beräkningsinlärning för att bevisa att inlärningsalgoritmen är ungefär korrekt i sannolikhet . Det vill säga, med hög sannolikhet har denna algoritm ett litet fel på en tillräckligt stor uppsättning träningsdata [6] .

Chernoff-poäng kan effektivt användas för att utvärdera " robusthetsnivån " för en applikation/algoritm genom att undersöka dess störningsutrymme med hjälp av randomisering. [7]

Matrix poäng

Rudolf Ahlswede och Andreas Winter använde Chernoff-skattningar för slumpvariabler med matrisvärden. [8] Nästa version av ojämlikheten finns i Tropps verk. [9]

Låt M 1 , ..., M t vara slumpvariabler med matrisvärden som och . Beteckna matrisnormoperatorn . Om olikheten nästan säkert gäller för alla , då för varje ε > 0 $M_{i}\in \mathbb {C} ^{d_{1}\times d_{2))$ $\mathbb {E} [M_{i}]=0$ $\lVert M\rVert$ $M$ $\lVert M_{i}\rVert \leq \gamma$ $i\in \{1,\ldots ,t\}$

P\left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}\right\|>\varepsilon \right)\leq ( d_{1}+d_{2})\exp \left(-{\frac {3\varepsilon ^{2}t}{8\gamma ^{2}}}\right).

För att dra slutsatsen att avvikelsen från 0 begränsas av ε med hög sannolikhet måste vi välja (antal sampel) proportionellt mot logaritmen för . I det allmänna fallet är beroendet av inte uppenbart: ta till exempel en diagonal slumpmässig matris av dimensionstecken . Summan av oberoende provnormoperator är exakt den maximala avvikelsen bland oberoende slumpmässiga längdvandringar . För att nå en fast gräns för maximal avvikelse med konstant sannolikhet, måste öka logaritmiskt med . [tio] $t$ ${\displaystyle d_{1}+d_{2))$ $\ln(\min(d_{1},d_{2}))$ $d\times d$ $t$ $d$ $t$ $t$ $d$

Följande sats härleds under antagandet att den har en låg rang för att undvika dimensionsberoende. $M$

Sats utan dimensionsberoende

Låt 0 < ε < 1 och vara en slumpmässig symmetrisk reell matris med och nästan säker. Antag att varje bärarelement har rang som mest . Låt oss sätta $M$ $\|\mathrm {E} [M]\|\leq 1$ $\|M\|\leq \gamma$ $M$ $r$

t=\Omega \left({\frac {\gamma \ln(\gamma /\varepsilon ^{2})}{\varepsilon ^{2))}\right).

Om nästan säkert, alltså $r\leq t$

P\left(\left\|{\frac {1}{t}}\summa _{i=1}^{t}M_{i}-\mathrm {E} [M]\right\| >\varepsilon \right)\leq {\frac {1}{\mathbf {poly} (t))),

där M 1 , ..., M t är oberoende identiskt distribuerade kopior av . $M$

Sats för inte helt slumpmässiga matriser

Ankit Garg, Yin Tat Lee, Zhao Song och Nikhil Srivastava [11] erhöll Chernoff-typ uppskattningar för summor av matrisvärderade slumpvariabler samplade med hjälp av en expander random walk .

Rasmus King och Zhao Song [12] erhöll Chernov-typ uppskattningar för summor av Laplacian matriser av slumpmässiga träd.

Samplingsvariant

Följande version av Chernoff-uppskattningen kan användas för att uppskatta sannolikheten för att majoriteten av befolkningen kommer att bli en minoritet i urvalet och vice versa. [13]

Anta att det finns en allmän befolkning och en subpopulation . Låt oss beteckna den relativa storleken på delpopulationen ( ) med . $A$ $B\subseteq A$ $|B|/|A|$ $r$

Låt oss säga att vi väljer ett heltal surt och ett slumpmässigt urval av storlek . Låt oss beteckna den relativa storleken på delpopulationen ( ) med . $k$ $S\subset A$ $k$ $|B\cap S|/|S|$ ${\displaystyle r_{S))$

Sedan för varje andel : $d\in [0,1]$

P\left(r_{S}<(1-d)\cdot r\right)<\exp \left(-r\cdot d^{2}\cdot k/2\right).

I synnerhet, om ─ är majoriteten i (dvs. ), så kan vi från ovan uppskatta sannolikheten att den kommer att förbli majoriteten när vi tar [14] : $B$ $A$ $r>0,5$ $B$ $S(r_{S}>0.5),$ $d=1-{\frac {1}{2r))$

$P\left(r_{S}>0.5\right)>1-\exp \left(-r\cdot \left(1-{\frac {1}{2r))\right)^{2} \cdot k/2\right).$

Denna uppskattning är naturligtvis inte korrekt. Till exempel, om , då får vi en trivial uppskattning . $r=0.5$ $P>0$

Bevis

Chernov-Hoefding-satsen (additiv form)

Låt q = p + ε . Om vi tar a = nq i formel (1) får vi:

P\left({\frac {1}{n}}\sum X_{i}\geq q\right)\leq \inf _{t>0}{\frac {E\left[\prod e ^{tX_{i}}\right]}{e^{tnq}}}=\inf _{t>0}\left({\frac {E\left[e^{tX_{i}}\right] }{e^{tq}}}\right)^{n}.

När vi nu vet att Pr( X i = 1) = p , Pr( X i = 0) = 1 − p , har vi

\left({\frac {\mathrm {E} \left[e^{tX_{i}}\right]}{e^{tq}}}\right)^{n}=\left({ \frac {pe^{t}+(1-p)}{e^{tq}}}\right)^{n}=\left(pe^{(1-q)t}+(1-p) e^{-qt}\right)^{n}.

Så vi kan enkelt beräkna minimum med hjälp av differentieringstekniken:

{\frac {d}{dt}}\left(pe^{(1-q)t}+(1-p)e^{-qt}\right)=(1-q)pe^{ (1-q)t}-q(1-p)e^{-qt}.

Att likställa det resulterande uttrycket till noll och lösa ekvationen med avseende på , får vi $t$

{\begin{aligned}(1-q)pe^{(1-q)t}&=q(1-p)e^{-qt}\\(1-q)pe^{t} &=q(1-p)\end{aligned}}

så

e^{t}={\frac {(1-p)q}{(1-q)p)).

Följaktligen,

t=\ln \left({\frac {(1-p)q}{(1-q)p}}\right).

Eftersom q = p + ε > p ser vi att t > 0 , så vår uppskattning är uppfylld av t . När vi har t , kan vi gå tillbaka till föregående ekvationer och hitta

{\begin{aligned}\ln \left(pe^{(1-q)t}+(1-p)e^{-qt}\right)&=\ln \left(e^{- qt}(1-p+pe^{t})\höger)\\&=\ln \left(e^{-q\ln \left({\frac {(1-p)q}{(1- q)p}}\right)}\right)+\ln \left(1-p+pe^{\ln \left({\frac {1-p}{1-q}}\right)}e^ {\ln {\frac {q}{p}}}\right)\\&=-q\ln {\frac {1-p}{1-q}}-q\ln {\frac {q}{ p}}+\ln \left(1-p+p\left({\frac {1-p}{1-q}}\right){\frac {q}{p}}\right)\\& =-q\ln {\frac {1-p}{1-q}}-q\ln {\frac {q}{p}}+\ln \left({\frac {(1-p)(1 -q)}{1-q))+{\frac {(1-p)q}{1-q))\right)\\&=-q\ln {\frac {q}{p))+ \left(-q\ln {\frac {1-p}{1-q}}+\ln {\frac {1-p}{1-q}}\right)\\&=-q\ln { \frac {q}{p}}+(1-q)\ln {\frac {1-p}{1-q}}\\&=-D(q\parallell p).\end{aligned}}

Vi har nu önskat resultat eftersom

P\left({\tfrac {1}{n}}\sum X_{i}\geq p+\varepsilon \right)\leq e^{-D(p+\varepsilon \parallel p)n}.

För att slutföra beviset i det symmetriska fallet definierar vi helt enkelt en slumpvariabel Y i = 1 − X i , tillämpar exakt samma bevis på den och lägger till resultatet till vår uppskattning.

Multiplikativ form

Låt Pr( Xi = 1 ) = pi . Enligt formel (1) ,

{\begin{aligned}P(X\geq (1+\delta )\mu )&\leq \inf _{t>0}{\frac {\operatörsnamn {E} \left[\prod _{ i=1}^{n}e^{tX_{i}}\right]}{e^{t(1+\delta )\mu }}}\\[4pt]&=\inf _{t>0 }{\frac {\prod _{i=1}^{n}\operatörsnamn {E} \left[e^{tX_{i}}\right]}{e^{t(1+\delta )\mu ))}\\[4pt]&=\inf _{t>0}{\frac {\prod _{i=1}^{n}\left[p_{i}e^{t}+(1- p_{i})\right]}{e^{t(1+\delta )\mu }}}.\end{aligned}}

Den tredje raden följer av att den tar värdet e t med sannolikheten pi och värdet 1 med sannolikheten 1 − pi . Detta är identiskt med beräkningarna ovan i beviset för tillsatsformen. $e^{tX_{i))$

Om vi skriver om som och kommer ihåg att (om x > 0 är ojämlikheten strikt), sätter vi . Samma resultat kan erhållas genom att direkt ersätta a i Chernoff-estimatorn med (1 + δ ) μ . [femton] $p_{i}e^{t}+(1-p_{i})$ $p_{i}(e^{t}-1)+1$ ${\displaystyle 1+x\leq e^{x))$ $x=p_{i}(e^{t}-1)$

På det här sättet,

P(X\geq (1+\delta )\mu )\leq {\frac {\prod _{i=1}^{n}e^{p_{i}(e^{t}-1 )}}{e^{t(1+\delta )\mu }}}={\frac {e^{\left((e^{t}-1)\summa _{i=1}^{n }p_{i}\right)}}{e^{t(1+\delta )\mu }}}={\frac {e^{(e^{t}-1)\mu }}{e^ {t(1+\delta )\mu}}}.

Om vi bara sätter t = ln(1 + δ ) , så att t > 0 för δ > 0 , så kan vi plugga in det i det sista uttrycket och hitta

{\frac {e^{(e^{t}-1)\mu }}{e^{t(1+\delta )\mu }}}={\frac {e^{(1+ \delta -1)\mu }}{(1+\delta )^{(1+\delta )\mu }}}=\vänster[{\frac {e^{\delta }}{(1+\delta )^{(1+\delta )}}}\höger]^{\mu }

Q.E.D.

Se även

mäta ojämlikhet i koncentrationen

Länkar

↑ Denna metod användes först av Sergei Bernstein i bevis relaterade till Bernsteins ojämlikheter .
↑ 1 2 Mitzenmacher, Michael, & Upfal, Eli. Sannolikhet och beräkning: Randomiserade algoritmer och sannolikhetsanalys . - Cambridge University Press, 2005. - ISBN 978-0-521-83540-4 . - doi : 10.1017/CBO9780511813603.005 . Arkiverad 16 april 2021 på Wayback Machine
↑ Sinclair, Alistair Klassanteckningar för kursen "Slumpmässighet och beräkning" (länk ej tillgänglig) (hösten 2011). Hämtad 30 oktober 2014. Arkiverad från originalet 31 oktober 2014. (obestämd)
↑ Hoeffding, W. (1963). "Sannolikhet ojämlikheter för summor av begränsade slumpmässiga variabler" (PDF) . Journal of the American Statistical Association . 58 (301): 13-30. DOI : 10.2307/2282952 . JSTOR 2282952 .
↑ Användbara ojämlikheter . logaritm . Hämtad 13 maj 2020. Arkiverad från originalet 19 augusti 2020. (obestämd)
↑ M. Kearns, U. Vazirani. En introduktion till beräkningslärandeteori. Kapitel 9 (Bilaga), sidorna 190-192. MIT Press, 1994.
↑ C.Alippi: "Randomiserade algoritmer" kapitel i Intelligence for Embedded Systems. Springer, 2014, 283 sidor ISBN 978-3-319-05278-6 .
↑ Ahlswede, R.; Winter, A. (2003). "Stark konversation för identifiering via kvantkanaler". IEEE Transactions on Information Theory . 48 (3): 569-579. arXiv : quant-ph/0012127 . DOI : 10.1109/18.985947 .
↑ Tropp, J. (2010). "Användarvänliga svansgränser för summor av slumpmässiga matriser". Grunder för beräkningsmatematik . 12 (4): 389-434. arXiv : 1004.4389 . DOI : 10.1007/s10208-011-9099-z .
↑ Magen, A. & Zouzias, A. (2011), Low Rank Matrix-Valued Chernoff Bounds and Approximate Matrix Multiplication, arΧiv : 1005.2724 [cs.DM].
↑ Ankit Garg, Yin Tat Lee, Zhao Song, Nikhil Srivastava. A Matrix Expander Chernoff Bound // Association for Computing MachineryNew YorkNYUSA. — 2018. Arkiverad 14 april 2021.
↑ Rasmus Kyng, Zhao Song. En matris Chernoff bunden för starkt Rayleigh-distributioner och spektrala sparsifierare från några slumpmässiga träd // FOCS. - 2018. - 1 oktober. Arkiverad från originalet den 22 april 2021.
↑ Goldberg, AV- konkurrensauktioner för flera digitala varor // Algoritmer - ESA 2001 / AV Goldberg, JD Hartline. - 2001. - Vol. 2161. - S. 416. - ISBN 978-3-540-42493-2 . - doi : 10.1007/3-540-44676-1_35 . ; Lemma 6.1
↑ Se grafer: Frontier som funktion av r med varierande k Arkiverad 4 januari 2015 på Wayback Machine och Frontier som funktion av k med varierande r Arkiverad 4 januari 2015 på Wayback Machine .
↑ Se beviset ovan.

Ytterligare läsning

Chernoff, H. (1952). "Ett mått på asymptotisk effektivitet för tester av en hypotes baserat på summan av observationer." Annals of Mathematical Statistics . 23 (4): 493-507. doi : 10.1214/aoms/ 1177729330 . JSTOR 2236576 . MR 0057518 . Zbl 0048.11804 .
Chernoff, H. (1981). "En anteckning om en ojämlikhet som involverar normalfördelningen." Annals of Probability . 9 (3): 533-535. doi : 10.1214/ aop /1176994428 . JSTOR 2243541 . MR 0614640 . Zbl 0457.60014 .
Hagerup, T.; Rub, C. (1990). "En guidad rundtur i Chernoffs gränser". Informationsbehandlingsbrev . 33 (6): 305. DOI : 10.1016/0020-0190(90)90214-I .
Nielsen, F. (2011), Chernoff information of exponential familys, arΧiv : 1102.2684 [cs.IT].