Chernov score

Chernovs skøn giver eksponentielt faldende estimater af sandsynligheden for store afvigelser af summer af uafhængige stokastiske variable . Disse estimater er mere nøjagtige end estimater opnået ved brug af første eller andet øjeblik, såsom Markovs ulighed eller Chebyshevs ulighed , som kun giver en magtlov om aftagende. Samtidig kræver Chernovs estimat, at de stokastiske variable er uafhængige i aggregatet, en betingelse, som hverken Markovs ulighed eller Chebyshevs ulighed kræver, selvom Chebyshevs ulighed kræver parvis uafhængighed af stokastiske variable.

Chernovs skøn er relateret til Bernsteins uligheder og Höfdings ulighed , som går forud for det historisk.

Grundlæggende sag

Hovedtilfældet af Chernov-estimatet for en stokastisk variabel opnås ved at anvende Markovs ulighed på e tX [1] . For alle $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 er summen af n stokastiske variable X 1 , ... , X n , for enhver $t>0$

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

Især at optimere med hensyn til t og antage, at X i er uafhængig, får vi

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

(en)

Tilsvarende

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

og dermed,

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

Specifikke værdier af Chernovs estimater opnås ved beregning for specifikke mængder . $\mathrm {E} \left[e^{-t\cdot X_{i}}\right]$ $X_{i}$

Eksempel

Lad X 1 , ..., X n være uafhængige Bernoulli stokastiske variable, hvis sum er X , og hver er lig med 1 med sandsynlighed . For en Bernoulli-variabel er følgende sandt: $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ølgelig,

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

For enhver og , vi opnår $\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))},

og det generelle tilfælde af Chernoff-estimatet giver [2] :64

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

Sandsynligheden for samtidig forekomst af mere end n /2 hændelser { X k = 1 } er nøjagtigt lig med:

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

Det lavere estimat af denne sandsynlighed kan beregnes ved hjælp af Chernoff-uligheden:

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

Faktisk, der angiver μ = np , får vi den multiplikative form af Chernoff-estimatet (se nedenfor eller konsekvens 13.3 i Sinclairs klassenoter) [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}}

Dette resultat indrømmer forskellige generaliseringer, som nævnt nedenfor. Flere former for Chernoff-estimater kan bemærkes: den oprindelige additivform (giver et estimat for den absolutte fejl ) eller den mere praktiske multiplikationsform (begrænser fejlen i forhold til middelværdien).

Additiv form (evaluering for absolut fejl)

Følgende sætning blev bevist af Wassily Hoefding [4] .

Chernov-Hoefding teorem . Lad X 1 , ..., X n være uafhængige identisk fordelte stokastiske variabler med værdierne {0, 1}. Lad p = E[ X ] og ε > 0 . Derefter

{\begin{aligned}P\left({\frac {1}{n}}\sum 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))\sum 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} }

hvor

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

Dette er Kullback-Leibler-divergensen mellem stokastiske variable, der har en Bernoulli-fordeling med henholdsvis parametrene x og y . Hvis p ≥en2, så

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

Et enklere estimat opnås ved at svække denne sætning ved at bruge uligheden D ( p + ε || p ) ≥ 2 ε 2 , som følger af konveksiteten af D ( p + ε || p ) og det faktum, at

{\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}).

Dette resultat er et særligt tilfælde af Hoefdings ulighed . I nogle tilfælde anvendes skøn

{\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\parallel y)\geq {\frac {3(xy)^{2}}{2( 2y+x)}},\\[6pt]D(x\parallel y)\geq {\frac {(xy)^{2}}{2y}},&&&x\leq y,\\[6pt]D( x\parallel y)\geq {\frac {(xy)^{2}}{2x}},&&&x\geq y\end{aligned}}

stærkere for p <enotte.

Multiplikativ form (estimat for relativ fejl)

Multiplikativ Chernov-estimat . Lad X 1 , ..., X n være uafhængige stokastiske variabler, der tager værdierne {0, 1}. Lad os betegne deres sum med X , lad os betegne forventningen til denne sum med μ . Så for hver

\delta \geq 0

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

På lignende måde kan man vise, at for evt $0<\delta <1,$

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

I praksis viser ovenstående formel sig ofte at være besværlig [2] , så der anvendes svagere, men bekvemme skøn

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 opnås ved hjælp af en ulighed fra listen over logaritmiske uligheder [5] . Eller en endnu svagere ulighed ${\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 en.

Ansøgninger

Chernovs estimater har applikationer inden for sætbalancering og pakkerouting i sparsomme netværk.

Problemet med afbalancering af mængder opstår ved design af et statistisk eksperiment . Typisk, når vi designer et statistisk eksperiment med deltageregenskaber givet i det pågældende forsøg, skal vi opdele deltagerne i to ikke-overlappende grupper, så hver egenskab er så afbalanceret som muligt mellem de to grupper. Se også Probability and Computing: Randomized Algorithms and Probabilistic Analysis Arkiveret 16. april 2021 på Wayback Machine .

Chernoff-estimater bruges også til at opnå hårde grænser i routingproblemer ved hjælp af permutationer. Dette reducerer routing- overbelastning i sparsomme netværk. Se mere i Probability and Computing: Randomized Algorithms and Probabilistic Analysis Arkiveret 16. april 2021 på Wayback Machine .

Også Chernoff-estimater bruges i teorien om beregningsmæssig læring for at bevise, at indlæringsalgoritmen er omtrent korrekt i sandsynlighed . Det vil sige, med stor sandsynlighed har denne algoritme en lille fejl på et tilstrækkeligt stort sæt træningsdata [6] .

Chernoff-score kan effektivt bruges til at evaluere " robusthedsniveauet " af en applikation/algoritme ved at undersøge dens forstyrrelsesrum ved hjælp af randomisering. [7]

Matrix score

Rudolf Ahlswede og Andreas Winter brugte Chernoff-estimater for stokastiske variable med matrixværdier. [8] Den næste version af uligheden kan findes i Tropps værk. [9]

Lad M 1 , ..., M t være stokastiske variable med matrixværdier som og . Betegn matrixnormoperatoren . Hvis uligheden næsten helt sikkert gælder for alle , så for hver ε > 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).

For at konkludere, at afvigelsen fra 0 er begrænset af ε med høj sandsynlighed, skal vi vælge (antal stikprøver) proportionalt med logaritmen af . I det generelle tilfælde er afhængigheden af ikke indlysende: Tag for eksempel en diagonal tilfældig matrix af tegn på dimension . Summen af uafhængig prøvenormoperator er nøjagtigt den maksimale afvigelse blandt uafhængige tilfældige vandreture . For at nå en fast grænse for maksimal afvigelse med en konstant sandsynlighed, skal stige logaritmisk med . [ti] $t$ ${\displaystyle d_{1}+d_{2))$ $\ln(\min(d_{1},d_{2}))$ $d\times d$ $t$ $d$ $t$ $t$ $d$

Følgende sætning er udledt under den antagelse, at den har en lav rang for at undgå dimensionsafhængighed. $M$

Sætning uden dimensionsafhængighed

Lad 0 < ε < 1 og vær en tilfældig symmetrisk reel matrix med og næsten sikker. Antag, at hvert bæreelement højst har rang . Lad os sætte $M$ $\|\mathrm {E} [M]\|\leq 1$ $\|M\|\leq \gamma$ $M$ $r$

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

Hvis næsten helt sikkert, så $r\leq t$

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

hvor M 1 , ..., M t er uafhængige identisk distribuerede kopier af . $M$

Sætning for ikke helt tilfældige matricer

Ankit Garg, Yin Tat Lee, Zhao Song og Nikhil Srivastava [11] opnåede estimater af Chernoff-typen for summer af matrix-vurderede tilfældige variabler samplet ved hjælp af en expander random walk .

Rasmus King og Zhao Song [12] opnåede estimater af Chernov-typen for summer af Laplacian -matricer af tilfældige træer.

Sampling variant

Den følgende version af Chernoff-estimatet kan bruges til at estimere sandsynligheden for, at størstedelen af befolkningen bliver en minoritet i stikprøven og omvendt. [13]

Antag, at der er en generel befolkning og en subpopulation . Lad os betegne den relative størrelse af delpopulationen ( ) med . $EN$ $B\subseteq A$ $|B|/|A|$ $r$

Lad os sige, at vi vælger et heltal surt og en tilfældig stikprøve af størrelse . Lad os betegne den relative størrelse af delpopulationen ( ) med . $k$ $S\subset A$ $k$ $|B\cap S|/|S|$ ${\displaystyle r_{S))$

Derefter for hver andel : $d\in [0,1]$

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

Især hvis ─ er flertallet i (dvs. ), så kan vi estimere ovenfra sandsynligheden for, at det forbliver flertallet ved at tage [14] : $B$ $EN$ $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).$

Dette skøn er naturligvis ikke korrekt. For eksempel, hvis , så får vi et trivielt skøn . $r=0,5$ $P>0$

Beviser

Chernov-Hoefding teorem (tilsætningsform)

Lad q = p + ε . Tager vi 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 ved, at 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 nemt beregne minimum ved hjælp af differentieringsteknikken:

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

Ligner det resulterende udtryk til nul og løser ligningen med hensyn til , 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ølgelig,

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

Da q = p + ε > p , ser vi, at t > 0 , så vores estimat er opfyldt med t . Når vi har t , kan vi gå tilbage til de foregående ligninger og finde

{\begin{aligned}\ln \left(pe^{(1-q)t}+(1-p)e^{-qt}\right)&=\ln \left(e^{- qt}(1-p+pe^{t})\right)\\&=\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\parallel p).\end{aligned}}

Vi har nu det ønskede resultat pga

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

For at fuldende beviset i det symmetriske tilfælde definerer vi blot en stokastisk variabel Y i = 1 − X i , anvender nøjagtig det samme bevis på den og tilføjer resultatet til vores estimat.

Multiplikativ form

Lad Pr( X i = 1) = pi . Ifølge formel (1) ,

{\begin{aligned}P(X\geq (1+\delta )\mu )&\leq \inf _{t>0}{\frac {\operatørnavn {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ørnavn {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 linje følger af, at den tager værdien e t med sandsynlighed p i og værdien 1 med sandsynlighed 1 − p i . Dette er identisk med beregningerne ovenfor i beviset for additivformen. $e^{tX_{i))$

Ved at omskrive som og huske at (hvis x > 0 , så er uligheden streng), sætter vi . Det samme resultat kan opnås ved direkte at erstatte a i Chernoff-estimatoren med (1 + δ ) μ . [femten] $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å denne måde

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)\sum _{i=1}^{n }p_{i}\right)}}{e^{t(1+\delta )\mu }}}={\frac {e^{(e^{t}-1)\mu }}{e^ {t(1+\delta )\mu}}}.

Hvis vi bare sætter t = ln(1 + δ ) , så t > 0 for δ > 0 , så kan vi sætte det ind i det sidste udtryk og finde

{\frac {e^{(e^{t}-1)\mu }}{e^{t(1+\delta )\mu }}}={\frac {e^{(1+ \delta -1)\mu }}{(1+\delta )^{(1+\delta )\mu }}}=\venstre[{\frac {e^{\delta }}{(1+\delta )^{(1+\delta )}}}\right]^{\mu }

Q.E.D.

Se også

måle koncentrationsulighed

Yderligere læsning

Chernoff, H. (1952). "Et mål for asymptotisk effektivitet for test af en hypotese baseret på summen af 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 note om en ulighed, der involverer normalfordelingen." 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 guidet tur til Chernoff-grænsen". Informationsbehandlingsbreve . 33 (6): 305. DOI : 10.1016/0020-0190(90)90214-I .
Nielsen, F. (2011), Chernoff information om eksponentielle familier, arΧiv : 1102.2684 [cs.IT].