Chernov pontszáma

Csernov becslése exponenciálisan csökkenő becsléseket ad a független valószínűségi változók összegei nagy eltéréseinek valószínűségére . Ezek a becslések pontosabbak, mint az első vagy második mozzanatokkal kapott becslések, mint például a Markov-egyenlőtlenség vagy a Csebisev -egyenlőtlenség , amelyek csak a csökkenő hatványtörvényt adják. Ugyanakkor Csernov becslése megköveteli, hogy a valószínűségi változók az aggregátumban függetlenek legyenek, ezt a feltételt sem Markov-egyenlőtlenség, sem Csebisev-egyenlőtlenség nem követeli meg, bár a Csebisev-egyenlőtlenség megköveteli a valószínűségi változók páronkénti függetlenségét .

Csernov becslése Bernstein egyenlőtlenségéhez és Höfding egyenlőtlenségéhez kapcsolódik , amelyek történelmileg megelőzik.

Alapeset

A Csernov-becslés fő esetét egy valószínűségi változóra úgy érjük el, hogy a Markov-egyenlőtlenséget alkalmazzuk e tX -re [1] . Mindenkinek $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}}}.

Ha X n valószínűségi változó összege X 1 , ... , X n , bármely $t>0$

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

Pontosabban, ha t -re optimalizáljuk, és feltételezzük, hogy az X i függetlenek, azt kapjuk

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

(egy)

Hasonlóképpen

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

és így,

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

A Csernov-féle becslések konkrét értékeit meghatározott mennyiségek kiszámításával kapják meg . $\mathrm {E} \left[e^{-t\cdot X_{i}}\right]$ $X_{i}$

Példa

Legyenek X 1 , ..., X n független Bernoulli valószínűségi változók , amelyek összege X , és mindegyik egyenlő 1 valószínűséggel . Egy Bernoulli-változóra a következő igaz: $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)},

Következésképpen,

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

Bármely és , kapunk $\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 Chernoff-becslés általános esete pedig azt adja [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}.

Több mint n /2 esemény egyidejű előfordulásának valószínűsége { X k = 1 } pontosan egyenlő a következővel:

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

Ennek a valószínűségnek az alsó becslése a Chernoff-egyenlőtlenség segítségével számítható ki:

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

Valóban, ha μ = np -t jelölünk , megkapjuk a Chernoff-becslés multiplikatív alakját (lásd alább vagy a 13.3 következményt Sinclair osztályjegyzeteiben) [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}}\jobbra)^{2}.}\end{igazított}}

Ez az eredmény különféle általánosításokat enged meg, amint azt alább megjegyezzük. A Chernoff-becslések többféle formája is megfigyelhető: az eredeti additív forma (becslést ad az abszolút hibára ) vagy a gyakorlatiasabb multiplikatív forma (korlátozza a hibát az átlaghoz képest).

Additív forma (abszolút hiba értékelése)

A következő tételt Wassily Hoefding [4] bizonyította .

Csernov-Hoefding tétel . Legyenek X 1 , ..., X n független , azonos eloszlású valószínűségi változók , amelyek értékei {0, 1}. Legyen p = E[ X ] és ε > 0 . Akkor

{\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{igazított} }

ahol

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

Ez a Kullback-Leibler eltérés azon valószínűségi változók között, amelyek Bernoulli-eloszlásúak x és y paraméterekkel . Ha p ≥egy2, akkor

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

Egyszerűbb becslést kapunk, ha ezt a tételt gyengítjük a D ( p + ε || p ) ≥ 2 ε 2 egyenlőtlenséggel , amely D ( p + ε || p ) konvexitásából és abból a tényből következik, hogy

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

Ez az eredmény a Hoefding-egyenlőtlenség speciális esete . Egyes esetekben becsléseket használnak

{\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{igazított}}

erősebb p < eseténegynyolc.

Multiplikatív forma (relatív hiba becslése)

Multiplikatív Csernov becslés . Legyenek X 1 , ..., X n független valószínűségi változók, amelyek a(z) {0, 1} értékeket veszik fel . Az összegüket jelöljük X - el, ennek az összegnek a várható értékét μ -vel . Aztán mindenre

\delta \geq 0

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

Hasonló módon ezt bárkinek meg lehet mutatni $0<\delta <1,$

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

A gyakorlatban a fenti képlet gyakran nehézkesnek bizonyul [2] , ezért gyengébb, de kényelmes becsléseket használnak.

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 ,

amelyeket a logaritmikus egyenlőtlenségek listájából származó egyenlőtlenség felhasználásával kapunk [5] . Vagy még gyengébb egyenlőtlenség ${\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 egy.

Alkalmazások

Csernov becslései szerint ritka hálózatok esetén a halmazkiegyenlítés és a csomagok útválasztása is alkalmazható.

A halmazkiegyenlítés problémája egy statisztikai kísérlet tervezésénél merül fel . Jellemzően, amikor egy statisztikai kísérletet tervezünk az adott kísérletben megadott résztvevői tulajdonságokkal, akkor a résztvevőket két nem átfedő csoportra kell osztanunk, hogy minden tulajdonság a lehető legjobban kiegyensúlyozott legyen a két csoport között. Lásd még : Probability and Computing: Randomized Algorithms and Probabilistic Analysis Archiválva 2021. április 16-án a Wayback Machine -nél .

A Chernoff-becsléseket arra is használják, hogy permutációkkal kemény határokat érjenek el az útválasztási problémákban. Ez csökkenti az útválasztási torlódást a ritka hálózatokban. További információ: Valószínűség és számítás: Véletlenszerű algoritmusok és valószínűségi elemzés , archiválva 2021. április 16-án, a Wayback Machine -nél .

A számítási tanulás elméletében a Chernoff-becsléseket is használják annak bizonyítására, hogy a tanulási algoritmus valószínűsége megközelítőleg helyes . Vagyis nagy valószínűséggel ennek az algoritmusnak van egy kis hibája kellően nagy betanítási adathalmazon [6] .

A Chernoff-pontszámok hatékonyan használhatók egy alkalmazás/algoritmus " robusztussági szintjének " értékelésére, ha véletlenszerűsítéssel vizsgálják a perturbációs terét. [7]

Mátrix pontszám

Rudolf Ahlswede és Andreas Winter Chernoff becsléseket használt mátrixértékekkel rendelkező valószínűségi változókra. [8] Az egyenlőtlenség következő változata Tropp munkájában található. [9]

Legyenek M 1 , ..., M t valószínűségi változók olyan mátrixértékekkel, hogy és . Jelölje a mátrix norma operátorát . Ha az egyenlőtlenség szinte biztosan mindenre érvényes , akkor minden ε > 0 -ra $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}}}\jobbra).

Annak megállapításához, hogy a 0-tól való eltérést nagy valószínűséggel ε határolja , a logaritmusával arányos (mintaszámot) kell választanunk . Általános esetben a függőség nem nyilvánvaló: például vegyünk egy diagonális véletlenszerű mátrixot dimenziójelekből . A független mintanorma operátor összege pontosan a legnagyobb eltérés a független véletlenszerű hosszúságú séták között . Ahhoz, hogy állandó valószínűséggel elérjük a maximális eltérés rögzített határát, logaritmikusan kell növekednie -val . [tíz] $t$ ${\displaystyle d_{1}+d_{2))$ $\ln(\min(d_{1},d_{2}))$ $d\times d$ $t$ $d$ $t$ $t$ $d$

A következő tétel abból a feltételezésből származik, hogy a dimenziófüggés elkerülése érdekében alacsony rangú. $M$

Tétel dimenziófüggés nélkül

Legyen 0 < ε < 1 , és legyen egy véletlenszerű szimmetrikus valós mátrix a és majdnem biztos. Tegyük fel, hogy minden hordozóelemnek legfeljebb rangja van . Tegyük fel $M$ $\|\mathrm {E} [M]\|\leq 1$ $\|M\|\leq \gamma$ $M$ $r$

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

Ha szinte biztosan, akkor $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))),

ahol M 1 , ..., M t független, azonos eloszlású másolatai . $M$

Tétel nem teljesen véletlenszerű mátrixokhoz

Ankit Garg, Yin Tat Lee, Zhao Song és Nikhil Srivastava [11] Chernoff-típusú becsléseket kaptak a mátrix értékű valószínűségi változók összegére, mintavételezett expander véletlenszerű sétával .

Rasmus King és Zhao Song [12] Csernov-típusú becsléseket kapott véletlenszerű fák laplaci mátrixainak összegére.

Mintavételi változat

A Chernoff becslés alábbi változata használható annak a valószínűségére, hogy a lakosság többsége kisebbségbe kerül a mintában és fordítva. [13]

Tegyük fel, hogy létezik egy általános populáció és egy alpopuláció . Jelöljük az alpopuláció relatív méretét ( ) . $A$ $B\subseteq A$ $|B|/|A|$ $r$

Tegyük fel, hogy egy egész számot választunk, és egy véletlenszerű méretű mintát . Jelöljük az alpopuláció relatív méretét ( ) . $k$ $S\subset A$ $k$ $|B\cap S|/|S|$ ${\displaystyle r_{S))$

Ezután minden megosztásnál : $d\in [0,1]$

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

Konkrétan, ha ─ a többség (azaz ), akkor felülről megbecsülhetjük annak valószínűségét, hogy a többség marad a [ 14] vételnél : $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).$

Ez a becslés természetesen nem pontos. Például ha , akkor triviális becslést kapunk . $r=0,5$ $P>0$

Bizonyíték

Chernov-Hoefding tétel (additív forma)

Legyen q = p + ε . Ha az (1) képletben a = nq -t vesszük, a következőt kapjuk:

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

Most, ha tudjuk, hogy Pr( X i = 1) = p , Pr( X i = 0) = 1 − p , azt kapjuk

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

Így könnyen kiszámíthatjuk a minimumot a differenciálási technikával:

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

Ha a kapott kifejezést nullával egyenlővé tesszük, és az egyenletet -re vonatkozóan megoldjuk , azt kapjuk $t$

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

így

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

Következésképpen,

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

Mivel q = p + ε > p , azt látjuk, hogy t > 0 , így becslésünket t teljesíti . Ha megvan a t , akkor visszatérhetünk az előző egyenletekhez, és megkereshetjük

{\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}}\jobbra)}\jobbra)+\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{igazított}}

Most megvan a kívánt eredmény, mert

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

A szimmetrikus esetben a bizonyítás befejezéséhez egyszerűen definiálunk egy Y i = 1 − X i valószínűségi változót , alkalmazzuk rá pontosan ugyanazt a bizonyítást, és hozzáadjuk az eredményt a becslésünkhöz.

Multiplikatív forma

Legyen Pr( X i = 1) = p i . Az (1) képlet szerint

{\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}\operátornév {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}}

A harmadik sor abból következik, hogy az e t értéket p i valószínűséggel , az 1 értéket pedig 1 − p i valószínűséggel veszi fel . Ez megegyezik a fenti számításokkal az adalékanyag forma bizonyítása során. $e^{tX_{i))$

Átírva így, és emlékezve arra, hogy (ha x > 0 , akkor az egyenlőtlenség szigorú), beállítjuk . Ugyanezt az eredményt kaphatjuk, ha a Chernoff-becslésben a- t közvetlenül (1 + δ ) μ -re cseréljük . [tizenöt] $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)$

Ily módon

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

Ha csak t = ln(1 + δ ) -t tesszük , hogy t > 0 δ > 0 esetén , akkor ezt bedughatjuk az utolsó kifejezésbe, és megkereshetjük

{\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 )}}}\jobbra]^{\mu }

Q.E.D.

Lásd még

mérje a koncentrációs egyenlőtlenséget

Linkek

↑ Ezt a módszert először Szergej Bernstein alkalmazta a Bernstein-egyenlőtlenségekkel kapcsolatos bizonyításokban .
↑ 1 2 Mitzenmacher, Michael és Upfal, Eli. Valószínűségszámítás és számítás: Véletlenszerű algoritmusok és valószínűségi elemzés . - Cambridge University Press, 2005. - ISBN 978-0-521-83540-4 . - doi : 10.1017/CBO9780511813603.005 . Archiválva : 2021. április 16. a Wayback Machine -nél
↑ Sinclair, Alistair Osztályjegyzetek a "Véletlenség és számítás" kurzushoz (hivatkozás nem érhető el) (2011 ősz). Letöltve: 2014. október 30. Az eredetiből archiválva : 2014. október 31.. (határozatlan)
↑ Hoeffding, W. (1963). „Valószínűségi egyenlőtlenségek határos véletlenszerű változók összegére” (PDF) . Az Amerikai Statisztikai Szövetség folyóirata . 58 (301): 13-30. DOI : 10.2307/2282952 . JSTOR 2282952 .
↑ Hasznos egyenlőtlenségek . logaritmus . Letöltve: 2020. május 13. Az eredetiből archiválva : 2020. augusztus 19. (határozatlan)
↑ M. Kearns, U. Vazirani. Bevezetés a számítógépes tanuláselméletbe. 9. fejezet (Függelék), 190-192. oldal. MIT Press, 1994.
↑ C.Alippi: „Véletlenszerű algoritmusok” fejezet az Intelligence for Embedded Systems-ben. Springer, 2014, 283 pp ISBN 978-3-319-05278-6 .
↑ Ahlswede, R.; Winter, A. (2003). „Erős beszélgetés a kvantumcsatornákon keresztüli azonosításhoz”. IEEE Transactions on Information Theory . 48 (3): 569-579. arXiv : quant-ph/0012127 . DOI : 10.1109/18.985947 .
↑ Tropp, J. (2010). „Felhasználóbarát véghatárok véletlen mátrixok összegeihez”. A számítógépes matematika alapjai . 12 (4): 389-434. arXiv : 1004.4389 . DOI : 10.1007/s10208-011-9099-z .
↑ Magen, A. & Zouzias, A. (2011), Alacsony rangú mátrixértékű Chernoff-határok és közelítő mátrixszorzás, arΧiv : 1005.2724 [cs.DM].
↑ Ankit Garg, Yin Tat Lee, Zhao Song, Nikhil Srivastava. A Matrix Expander Chernoff Bound // Association for Computing MachineryNew YorkNYEgyesült Államok. — 2018. Archiválva : 2021. április 14.
↑ Rasmus Kyng, Zhao Song. Mátrix Chernoff-kötés erős Rayleigh-eloszlások és spektrális porlasztók számára néhány véletlenszerűen terjedő fáról // FOCS. - 2018. - október 1. Archiválva az eredetiből 2021. április 22-én.
↑ Goldberg, AV Competitive Auctions for Multiple Digital Goods // Algoritmusok - ESA 2001 / AV Goldberg, JD Hartline. - 2001. - 20. évf. 2161. - P. 416. - ISBN 978-3-540-42493-2 . - doi : 10.1007/3-540-44676-1_35 . ; Lemma 6.1
↑ Grafikonok megtekintése: Határ az r függvényében változó k -val Archivált : 2015. január 4. a Wayback Machine -nél és a Frontier a k függvényében változó r -vel Archiválva : 2015. január 4. a Wayback Machine -nél .
↑ Lásd a fenti bizonyítékot.

További olvasnivaló

Chernoff, H. (1952). „A hipotézisek aszimptotikus hatékonyságának mérőszáma a megfigyelések összegén alapulva.” Annals of Mathematical Statistics . 23 (4): 493-507. doi : 10.1214/aoms/ 1177729330 . JSTOR 2236576 . MR 0057518 . Zbl 0048.11804 .
Chernoff, H. (1981). „Megjegyzés a normál eloszlással kapcsolatos egyenlőtlenségről.” Annals of Probability . 9 (3): 533-535. doi : 10.1214/ aop /1176994428 . JSTOR 2243541 . MR 0614640 . Zbl 0457.60014 .
Hagerup, T.; Rub, C. (1990). "Túra a Chernoff határaiban". Információfeldolgozási levelek . 33 (6): 305. DOI : 10.1016/0020-0190(90)90214-I .
Nielsen, F. (2011), Chernoff információ az exponenciális családokról, arΧiv : 1102.2684 [cs.IT].