Skóre Černova

Černovův odhad poskytuje exponenciálně klesající odhady pravděpodobnosti velkých odchylek součtů nezávislých náhodných veličin . Tyto odhady jsou přesnější než odhady získané pomocí prvního nebo druhého momentu, jako je Markovova nerovnost nebo Čebyševova nerovnost , které dávají pouze mocninný klesající zákon . Černovův odhad zároveň vyžaduje, aby náhodné veličiny byly v souhrnu nezávislé , což je podmínka, kterou Markovova ani Čebyševova nerovnost nevyžaduje, ačkoli Čebyševova nerovnost vyžaduje párovou nezávislost na náhodných veličinách.

Černovův odhad souvisí s Bernsteinovými nerovnostmi a Höfdingovou nerovností , které mu historicky předcházejí.

Základní případ

Hlavní případ Černovova odhadu pro náhodnou veličinu je dosažen aplikací Markovovy nerovnosti na e tX [1] . Pro každého $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}}}.

Když X je součet n náhodných proměnných X 1 , ... , X n , pro libovolné $t>0$

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

Dostaneme zejména optimalizaci s ohledem na t a za předpokladu, že X i jsou nezávislé

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

(jeden)

Podobně

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

a tudíž,

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

Konkrétní hodnoty Černovových odhadů se získávají výpočtem pro konkrétní veličiny . $\mathrm {E} \left[e^{-t\cdot X_{i}}\right]$ $X_{i}$

Příklad

Nechť X 1 , ..., X n jsou nezávislé Bernoulliho náhodné proměnné , jejichž součet je X a každá je s pravděpodobností rovna 1 . Pro Bernoulliho proměnnou platí následující: $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)},

Tudíž,

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

Pro jakékoli a získáme $\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))},

a obecný případ Chernoffova odhadu dává [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}.

Pravděpodobnost současného výskytu více než n /2 událostí { X k = 1 } je přesně rovna:

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

Spodní odhad této pravděpodobnosti lze vypočítat pomocí Chernoffovy nerovnosti:

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

Ve skutečnosti, označíme -li μ = np , dostaneme multiplikativní formu Chernoffova odhadu (viz níže nebo důsledek 13.3 v poznámkách ke třídě Sinclaira) [3] :

{\begin{aligned}P\left(X\leq \left\lpatro {\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}}

Tento výsledek připouští různá zobecnění, jak je uvedeno níže. Lze zaznamenat několik forem Chernoffových odhadů: původní aditivní formu (udává odhad absolutní chyby ) nebo praktičtější multiplikativní formu (omezuje chybu s ohledem na průměr).

Aditivní forma (vyhodnocení absolutní chyby)

Následující větu dokázal Wassily Hoefding [4] .

Černovova-Hoefdingova věta . Nechť X 1 , ..., X n jsou nezávislé identicky rozdělené náhodné proměnné nabývající hodnot {0, 1}. Nechť p = E[ X ] a ε > 0 . Pak

{\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 \paralelní p)n},\\P\left({\frac {1}{n))\součet 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} }

kde

D(x\paralelní y)=x\ln {\frac {x}{y}}+(1-x)\ln \left({\frac {1-x}{1-y}}\ že jo).

Toto je Kullback-Leibler divergence mezi náhodnými proměnnými, které mají Bernoulliho rozdělení s parametry x a y . Pokud p ≥jeden2, pak

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

Jednodušší odhad získáme oslabením této věty pomocí nerovnosti D ( p + ε || p ) ≥ 2 ε 2 , která vyplývá z konvexity D ( p + ε || p ) a skutečnosti , že

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

Tento výsledek je speciální případ Hoefdingovy nerovnosti . V některých případech se používají odhady

{\begin{aligned}D((1+x)p\paralelní p)\geq {\frac {1}{4}}x^{2}p,&&&{-{\tfrac {1}{ 2))}\leq x\leq {\tfrac {1}{2)),\\[6pt]D(x\paralelní y)\geq {\frac {3(xy)^{2}}{2( 2y+x)}},\\[6pt]D(x\rovnoběžné y)\geq {\frac {(xy)^{2}}{2y}},&&&x\leq y,\\[6pt]D( x\paralelní y)\geq {\frac {(xy)^{2}}{2x}},&&&x\geq y\end{aligned}}

silnější pro p <jedenosm.

Multiplikativní forma (odhad relativní chyby)

Multiplikativní Černovův odhad . Nechť X 1 , ..., X n jsou nezávislé náhodné proměnné nabývající hodnot {0, 1}. Označme jejich součet X , očekávání tohoto součtu označme μ . Pak pro každého

\delta \geq 0

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

Podobným způsobem lze ukázat, že pro všechny $0<\delta <1,$

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

V praxi se výše uvedený vzorec často ukazuje jako těžkopádný [2] , proto se používají slabší, ale pohodlné odhady

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 ,

které jsou získány pomocí nerovnosti ze seznamu logaritmických nerovností [5] . Nebo ještě slabší nerovnost ${\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 jeden.

Aplikace

Černovovy odhady mají uplatnění při vyvažování množin a směrování paketů v řídkých sítích.

Problém vyvažování množin vzniká při návrhu statistického experimentu . Při navrhování statistického experimentu s vlastnostmi účastníků uvedenými v tomto experimentu obvykle potřebujeme rozdělit účastníky do dvou nepřekrývajících se skupin tak, aby každá vlastnost byla mezi těmito dvěma skupinami co nejvyváženější. Viz také Probability and Computing: Randomized Algorithms and Probabilistic Analysis Archived 16. dubna 2021 na Wayback Machine .

Chernoffovy odhady se také používají k dosažení pevných hranic v problémech směrování pomocí permutací. To snižuje zahlcení směrováním v řídkých sítích. Více viz Pravděpodobnost a výpočetní technika: Randomizované algoritmy a pravděpodobnostní analýza archivované 16. dubna 2021 na Wayback Machine .

Chernoffovy odhady se také používají v teorii výpočetního učení k prokázání, že algoritmus učení je přibližně správný z hlediska pravděpodobnosti . To znamená, že s vysokou pravděpodobností má tento algoritmus malou chybu na dostatečně velkém souboru trénovacích dat [6] .

Chernoffova skóre lze efektivně použít k vyhodnocení „ úrovně robustnosti “ aplikace/algoritmu zkoumáním jejího poruchového prostoru pomocí randomizace. [7]

Matrix skóre

Rudolf Ahlswede a Andreas Winter použili Chernoffovy odhady pro náhodné proměnné s maticovými hodnotami. [8] Další verzi nerovnosti lze nalézt v Troppově díle. [9]

Nechť M 1 , ..., M t jsou náhodné veličiny s maticovými hodnotami takovými, že a . Označte maticový normový operátor . Pokud nerovnost téměř jistě platí pro všechny , pak pro každé ε > 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).

Abychom dospěli k závěru, že odchylka od 0 je s vysokou pravděpodobností ohraničena ε , musíme zvolit (počet vzorků) úměrný logaritmu . V obecném případě není závislost na zřejmá: vezměte například diagonální náhodnou matici znaků dimenze . Součet operátoru nezávislého vzorku normy je přesně maximální odchylka mezi nezávislými náhodnými procházkami délky . Aby bylo dosaženo pevné hranice maximální odchylky s konstantní pravděpodobností, musí se logaritmicky zvyšovat s . [deset] $t$ ${\displaystyle d_{1}+d_{2))$ $\ln(\min(d_{1},d_{2}))$ $d\times d$ $t$ $d$ $t$ $t$ $d$

Následující věta je odvozena za předpokladu, že má nízkou úroveň, aby se zabránilo závislosti na rozměrech. $M$

Věta bez závislosti na rozměrech

Nechť 0 < ε < 1 a je náhodná symetrická reálná matice s téměř jistotou. Předpokládejme, že každý nosný prvek má hodnotu nejvýše . Položme $M$ $\|\mathrm {E} [M]\|\leq 1$ $\|M\|\leq \gamma$ $M$ $r$

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

Pokud téměř jistě, tak ano $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))),

kde M 1 , ..., M t jsou nezávislé identicky distribuované kopie . $M$

Věta pro ne zcela náhodné matice

Ankit Garg, Yin Tat Lee, Zhao Song a Nikhil Srivastava [11] získali odhady Chernoffova typu pro součty náhodných proměnných s hodnotou matice odebraných pomocí expandéru náhodné procházky .

Rasmus King a Zhao Song [12] získali odhady typu Chernov pro součty laplaciánských matic náhodných stromů.

Varianta vzorkování

Následující verzi Chernoffova odhadu lze použít k odhadu pravděpodobnosti, že se většina populace stane ve vzorku menšinou a naopak. [13]

Předpokládejme, že existuje obecná populace a subpopulace . Označme relativní velikost subpopulace ( ) pomocí . $A$ $B\subseteq A$ $|B|/|A|$ $r$

Řekněme, že zvolíme celočíselný sour a náhodný vzorek velikosti . Označme relativní velikost subpopulace ( ) pomocí . $k$ $S\subset A$ $k$ $|B\cap S|/|S|$ ${\displaystyle r_{S))$

Pak pro každé sdílení : $d\in [0,1]$

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

Konkrétně, pokud je ─ většina v (tj. ), pak můžeme shora odhadnout pravděpodobnost, že zůstane většinou v braní [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).$

Tento odhad samozřejmě není přesný. Například, jestliže , pak dostaneme triviální odhad . $r=0,5$ $P>0$

Důkazy

Černov-Hoefdingova věta (aditivní forma)

Nechť q = p + ε . Vezmeme-li a = nq ve vzorci (1) , dostaneme:

P\left({\frac {1}{n}}\součet 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}.

Nyní, když víme, že Pr( X i = 1) = p , Pr( X i = 0) = 1 − p , máme

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

Takže můžeme snadno vypočítat minimum pomocí techniky diferenciace:

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

Když výsledný výraz vyrovnáme nule a vyřešíme rovnici vzhledem k , dostaneme $t$

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

tak

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

Tudíž,

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

Protože q = p + ε > p , vidíme, že t > 0 , takže našemu odhadu vyhovuje t . Jakmile máme t , můžeme se vrátit k předchozím rovnicím a najít

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

Nyní máme požadovaný výsledek, protože

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

Abychom dokončili důkaz v symetrickém případě, jednoduše definujeme náhodnou veličinu Y i = 1 − X i , aplikujeme na ni přesně stejný důkaz a výsledek přidáme k našemu odhadu.

Násobná forma

Nechť Pr( X i = 1) = p i . Podle vzorce (1 )

{\begin{aligned}P(X\geq (1+\delta )\mu )&\leq \inf _{t>0}{\frac {\operatorname {E} \left[\prod _{ i=1}^{n}e^{tX_{i}}\right]}{e^{t(1+\delta )\mu }}}\\[4pt]&=\inf _{t>0 }{\frac {\prod _{i=1}^{n}\jméno operátora {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}}

Třetí řádek vyplývá z toho, že nabývá hodnoty e t s pravděpodobností p i a hodnoty 1 s pravděpodobností 1 − p i . To je totožné s výpočty výše v důkazu aditivní formy. $e^{tX_{i))$

Přepíšeme jako a zapamatujeme si to (pokud x > 0 , pak je nerovnost striktní), nastavíme . Stejného výsledku lze získat přímým nahrazením a v Chernoffově odhadu za (1 + δ ) μ . [patnáct] $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)$

Takto,

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}}}.

Pokud dáme t = ln(1 + δ ) , takže t > 0 pro δ > 0 , pak to můžeme zapojit do posledního výrazu a najít

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

Q.E.D.

Viz také

měřit koncentrační nerovnost

Odkazy

↑ Tuto metodu poprvé použil Sergei Bernstein v důkazech souvisejících s Bernsteinovými nerovnostmi .
↑ 1 2 Mitzenmacher, Michael a Upfal, Eli. Pravděpodobnost a výpočty: Randomizované algoritmy a pravděpodobnostní analýza . - Cambridge University Press, 2005. - ISBN 978-0-521-83540-4 . - doi : 10.1017/CBO9780511813603.005 . Archivováno 16. dubna 2021 na Wayback Machine
↑ Sinclair, Alistair Poznámky ke kurzu "Náhodnost a počítání" (odkaz není k dispozici) (podzim 2011). Získáno 30. října 2014. Archivováno z originálu 31. října 2014. (neurčitý)
↑ Hoeffding, W. (1963). “Pravděpodobnostní nerovnosti pro součty omezených náhodných proměnných” (PDF) . Journal of the American Statistical Association . 58 (301): 13-30. DOI : 10.2307/2282952 . JSTOR 2282952 .
↑ Užitečné nerovnosti . logaritmus . Staženo 13. května 2020. Archivováno z originálu dne 19. srpna 2020. (neurčitý)
↑ M. Kearns, U. Vazirani. Úvod do teorie výpočetního učení. Kapitola 9 (Příloha), strany 190-192. MIT Press, 1994.
↑ C.Alippi: Kapitola "Randomizované algoritmy" v Intelligence for Embedded Systems. Springer, 2014, 283 s. ISBN 978-3-319-05278-6 .
↑ Ahlswede, R.; Winter, A. (2003). „Silná konverzace pro identifikaci prostřednictvím kvantových kanálů“. IEEE Transactions on Information Theory . 48 (3): 569-579. arXiv : quant-ph/0012127 . DOI : 10.1109/18.985947 .
↑ Tropp, J. (2010). „Uživatelsky přívětivé hranice pro součty náhodných matic“. Základy výpočetní matematiky . 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 YorkNYSpojené státy americké. — 2018. Archivováno 14. dubna 2021.
↑ Rasmus Kyng, Zhao Song. Matrix Chernoff vázaný na silně Rayleighovo rozdělení a spektrální rozdělovače z několika náhodných kostrových stromů // FOCS. - 2018. - 1. října. Archivováno z originálu 22. dubna 2021.
↑ Goldberg, AV Konkurenční aukce pro vícenásobné digitální zboží // Algoritmy - ESA 2001 / AV Goldberg, JD Hartline. - 2001. - Sv. 2161. - S. 416. - ISBN 978-3-540-42493-2 . - doi : 10.1007/3-540-44676-1_35 . ; Lemma 6.1
↑ Zobrazit grafy: Hranice jako funkce r s proměnným k Archivováno 4. ledna 2015 na Wayback Machine a Hranice jako funkce k s proměnlivým r Archivováno 4. ledna 2015 na Wayback Machine .
↑ Viz výše uvedený důkaz.

Další čtení

Chernoff, H. (1952). "Míra asymptotické účinnosti pro testy hypotézy založené na součtu pozorování." Annals of Mathematical Statistics . 23 (4): 493-507. doi : 10.1214/aoms/ 1177729330 . JSTOR 2236576 . MR 0057518 . Zbl 0048.11804 .
Chernoff, H. (1981). "Poznámka k nerovnosti zahrnující normální distribuci." Annals of Probability . 9 (3): 533-535. doi : 10.1214/ aop /1176994428 . JSTOR 2243541 . MR 0614640 . Zbl 0457.60014 .
Hagerup, T.; Rub, C. (1990). „Komentovaná prohlídka hranic Chernoff“ . Information Processing Letters . 33 (6): 305. DOI : 10.1016/0020-0190(90)90214-I .
Nielsen, F. (2011), Chernoffovy informace o exponenciálních rodinách, arΧiv : 1102.2684 [cs.IT].