Chernovin pisteet

Tšernovin estimaatti antaa eksponentiaalisesti pieneneviä arvioita riippumattomien satunnaismuuttujien summien suurten poikkeamien todennäköisyydestä . Nämä arviot ovat tarkempia kuin estimaatit, jotka on saatu käyttämällä ensimmäistä tai toista momenttia, kuten Markovin epäyhtälö tai Tšebyševin epäyhtälö , jotka antavat vain pienenemisen potenssilain . Samaan aikaan Tšernovin estimaatti edellyttää, että satunnaismuuttujat ovat riippumattomia aggregaatissa, jota ei edellytä Markovin epäyhtälö eikä Tšebyševin epäyhtälö, vaikka Tšebyshevin epäyhtälö edellyttää satunnaismuuttujien parittaista riippumattomuutta .

Tšernovin arvio liittyy Bernsteinin epätasa-arvoon ja Höfdingin epätasa-arvoon , jotka edeltävät sitä historiallisesti.

Perustapaus

Tšernov-estimaatin päätapaus satunnaismuuttujalle saavutetaan soveltamalla Markovin epäyhtälöä e tX :ään [1] . Kaikille $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}}}.

Kun X on n satunnaismuuttujan summa X 1 , ... , X n , mille tahansa $t>0$

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

Erityisesti optimoimalla t :n suhteen ja olettaen, että X i ovat riippumattomia, saamme

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

(yksi)

samoin

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

ja näin,

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

Tšernovin arvioiden erityisarvot saadaan laskemalla tietyille määrille . $\mathrm {E} \left[e^{-t\cdot X_{i}}\right]$ $X_{i}$

Esimerkki

Olkoon X 1 , ..., X n riippumattomia Bernoullin satunnaismuuttujia, joiden summa on X ja jokainen on yhtä suuri todennäköisyydellä 1 . Bernoulli-muuttujan osalta seuraava on totta: $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)},

Näin ollen

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

Kaikille ja , saamme $\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))},

ja Chernoffin arvion yleinen tapaus antaa [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 }}}\oikea]^{np}.

Yli n /2 tapahtuman samanaikaisen esiintymisen todennäköisyys { X k = 1 } on täsmälleen yhtä suuri kuin:

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

Tämän todennäköisyyden alempi arvio voidaan laskea käyttämällä Chernoffin epäyhtälöä:

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

Todellakin, merkitsemällä μ = np , saamme Chernoff-estimaatin kertovan muodon (katso alla tai johtopäätös 13.3 Sinclairin luokkamuistiinpanoissa) [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}}\oikea)^{2}.}\end{aligned}}

Tämä tulos sallii useita yleistyksiä, kuten alla on todettu. Chernoff-estimaateista voidaan havaita useita muotoja: alkuperäinen additiivinen muoto (antaa arvion absoluuttiselle virheelle ) tai käytännöllisempi kertova muoto (rajaa virhettä suhteessa keskiarvoon).

Additiivinen muoto (absoluuttisen virheen arviointi)

Wassily Hoefding [4] osoitti seuraavan lauseen .

Chernov-Hoefdingin lause . Olkoon X 1 , ..., X n riippumattomia identtisesti jakautuneita satunnaismuuttujia, joiden arvot ovat {0, 1}. Olkoon p = E[ X ] ja ε > 0 . Sitten

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

missä

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

Tämä on Kullback-Leiblerin ero satunnaismuuttujien välillä, joilla on Bernoulli-jakauma parametreilla x ja y . Jos p ≥yksi2, sitten

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

Yksinkertaisempi estimaatti saadaan heikentämällä tätä lausetta käyttämällä epäyhtälöä D ( p + ε || p ) ≥ 2 ε 2 , joka seuraa D ( p + ε || p ) konveksiteetista ja siitä, että

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

Tämä tulos on Hoefdingin epätasa-arvon erikoistapaus . Joissakin tapauksissa käytetään arvioita

{\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( 2v+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}}

vahvempi p <yksikahdeksan.

Kertova muoto (arvio suhteellisesta virheestä)

Kertomainen Chernov-arvio . Olkoon X 1 , ..., X n itsenäisiä satunnaismuuttujia, joiden arvot ovat { 0, 1}. Merkitään niiden summaa X , merkitään tämän summan odotus arvolla μ . Sitten jokaiselle

\delta \geq 0

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

Samalla tavalla sen voi osoittaa kenelle tahansa $0<\delta <1,$

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

Käytännössä yllä oleva kaava osoittautuu usein hankalaksi [2] , joten käytetään heikompia mutta käteviä arvioita

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 ,

jotka saadaan käyttämällä epäyhtälöä logaritmien epäyhtälöiden luettelosta [5] . Tai vielä heikompi eriarvoisuus ${\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 yksi.

Sovellukset

Tšernovin arvioissa on sovelluksia joukon tasapainottamiseen ja pakettien reitittämiseen harvassa verkossa .

Joukkotasapainotuksen ongelma nousee esiin tilastollisen kokeen suunnittelussa . Tyypillisesti, kun suunnitellaan tilastollista koetta kyseisessä kokeessa annetuilla osallistujaominaisuuksilla, meidän on jaettava osallistujat kahteen ei-päällekkäiseen ryhmään, jotta jokainen ominaisuus on mahdollisimman tasapainossa näiden kahden ryhmän välillä. Katso myös Probability and Computing: Randomized Algorithms and Probabilistic Analysis Arkistoitu 16. huhtikuuta 2021 Wayback Machinessa .

Chernoff-estimaatteja käytetään myös kovien rajojen saavuttamiseen reititysongelmissa käyttämällä permutaatioita. Tämä vähentää reititysruuhkaa harvoissa verkoissa . Katso lisää artikkelista Probability and Computing: Randomized Algorithms and Probabilistic Analysis Arkistoitu 16. huhtikuuta 2021 Wayback Machinessa .

Myös Chernoff-estimaatteja käytetään laskennallisen oppimisen teoriassa todistamaan, että oppimisalgoritmi on todennäköisyydellä likimäärin oikea . Eli suurella todennäköisyydellä tässä algoritmissa on pieni virhe riittävän suuressa harjoitusdatajoukossa [6] .

Chernoff-pisteitä voidaan käyttää tehokkaasti arvioimaan sovelluksen/algoritmin " vahvuustasoa " tutkimalla sen häiriöavaruutta satunnaistuksen avulla. [7]

Matriisipisteet

Rudolf Ahlswede ja Andreas Winter käyttivät Chernoff-estimaatteja satunnaismuuttujille matriisiarvoilla. [8] Seuraava versio epätasa-arvosta löytyy Troppin työstä. [9]

Olkoon M 1 , ..., M t satunnaismuuttujia, joiden matriisiarvot ovat sellaisia, että ja . Merkitse matriisinormioperaattoria . Jos epäyhtälö pätee lähes varmasti kaikille , niin jokaiselle ε > 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}}}\oikea).

Päätelläksemme, että poikkeamaa 0:sta rajoittaa ε suurella todennäköisyydellä, meidän on valittava (näytteiden lukumäärä) verrannollinen logaritmiin . Yleisessä tapauksessa riippuvuus ei ole ilmeinen: ota esimerkiksi diagonaalinen satunnaismatriisi dimensioiden merkeistä . Riippumattoman otosnormin operaattorin summa on täsmälleen suurin poikkeama riippumattomien satunnaisten pituuksien välillä . Saavuttaakseen enimmäispoikkeaman kiinteän rajan vakiolla todennäköisyydellä, on nostettava logaritmisesti kanssa . [kymmenen] $t$ ${\displaystyle d_{1}+d_{2))$ $\ln(\min(d_{1},d_{2}))$ $d\times d$ $t$ $d$ $t$ $t$ $d$

Seuraava lause on johdettu sillä oletuksella, että sen arvo on alhainen ulottuvuusriippuvuuden välttämiseksi. $M$

Lause ilman mittariippuvuutta

Olkoon 0 < ε < 1 ja se on satunnainen symmetrinen reaalimatriisi, jossa ja lähes varma. Oletetaan, että jokaisella kantoaaltoelementillä on korkeintaan arvo . Laitetaan $M$ $\|\mathrm {E} [M]\|\leq 1$ $\|M\|\leq \gamma$ $M$ $r$

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

Jos melkein varmasti, niin $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))),

missä M 1 , ..., M t ovat itsenäisiä identtisesti jakautuneita kopioita . $M$

Lause ei täysin satunnaisille matriiseille

Ankit Garg, Yin Tat Lee, Zhao Song ja Nikhil Srivastava [11] saivat Chernoff-tyyppiset estimaatit matriisiarvoisten satunnaismuuttujien summille, jotka on otettu näytteiden avulla laajentajalla satunnaiskävelyllä .

Rasmus King ja Zhao Song [12] saivat Chernov-tyyppiset estimaatit satunnaisten puiden Laplacian matriisien summille.

Näytteenottomuunnelma

Seuraavaa Chernoffin estimaatin versiota voidaan käyttää arvioimaan todennäköisyyttä, että suurin osa väestöstä jää vähemmistöön otoksessa ja päinvastoin. [13]

Oletetaan, että on olemassa yleinen populaatio ja osapopulaatio . Merkitään osajoukon ( ) suhteellinen koko merkillä . $A$ $B\subseteq A$ $|B|/|A|$ $r$

Oletetaan, että valitsemme kokonaisluvun hapan ja satunnaisen otoksen , jonka koko on . Merkitään osajoukon ( ) suhteellinen koko merkillä . $k$ $S\subset A$ $k$ $|B\cap S|/|S|$ ${\displaystyle r_{S))$

Sitten jokaisesta osakkeesta : $d\in [0,1]$

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

Erityisesti, jos ─ on enemmistö (eli ), niin voimme arvioida ylhäältä todennäköisyyden, että se pysyy enemmistönä otettaessa [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).$

Tämä arvio ei tietenkään pidä paikkaansa. Esimerkiksi jos , niin saamme triviaalin arvion . $r=0,5$ $P>0$

Todisteet

Chernov-Hoefdingin lause (additiivinen muoto)

Olkoon q = p + ε . Ottamalla a = nq kaavassa (1) saamme:

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}}\oikea] }{e^{tq}}}\right)^{n}.

Nyt kun tiedämme, että Pr( Xi = 1 ) = p , Pr( Xi = 0 ) = 1 − p , meillä on

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

Joten voimme helposti laskea minimin käyttämällä differentiointitekniikkaa:

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

Tasaamalla tuloksena olevan lausekkeen nollaan ja ratkaisemalla yhtälön suhteessa , saamme $t$

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

niin

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

Näin ollen

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

Koska q = p + ε > p , näemme, että t > 0 , joten arviomme täyttyy t :llä . Kun meillä on t , voimme palata edellisiin yhtälöihin ja etsiä

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

Meillä on nyt haluttu tulos, koska

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

Todistuksen täydentämiseksi symmetrisessä tapauksessa määritämme yksinkertaisesti satunnaismuuttujan Y i = 1 − X i , käytämme siihen täsmälleen samaa todistusta ja lisäämme tuloksen estimaatiimme.

Kertova muoto

Olkoon Pr( Xi = 1 ) = p i . Kaavan (1) mukaan

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

Kolmas rivi seuraa siitä, että se saa arvon e t todennäköisyydellä p i ja arvon 1 todennäköisyydellä 1 − p i . Tämä on identtinen lisäainemuodon todistuksessa olevien laskelmien kanssa. $e^{tX_{i))$

Kirjoittamalla uudelleen muotoon ja muistaen, että (jos x > 0 , niin epäyhtälö on tiukka), asetamme . Sama tulos voidaan saada korvaamalla a Chernoff-estimaattorissa suoraan arvolla (1 + δ ) μ . [viisitoista] $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)$

Tällä tavalla,

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

Jos laitamme vain t = ln(1 + δ ) niin, että t > 0 arvolle δ > 0 , voimme liittää sen viimeiseen lausekkeeseen ja löytää

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

Q.E.D.

Katso myös

mittaa keskittymiseroja

Linkit

↑ Sergei Bernstein käytti tätä menetelmää ensimmäisenä Bernsteinin epäyhtälöihin liittyvissä todisteissa .
↑ 1 2 Mitzenmacher, Michael ja Upfal, Eli. Todennäköisyys ja laskeminen: satunnaistetut algoritmit ja todennäköisyysanalyysi . - Cambridge University Press, 2005. - ISBN 978-0-521-83540-4 . - doi : 10.1017/CBO9780511813603.005 . Arkistoitu 16. huhtikuuta 2021 Wayback Machinessa
↑ Sinclair, Alistair Luokan muistiinpanot kurssille "Satunnaisuus ja laskeminen" (linkki ei saatavilla) (syksy 2011). Haettu 30. lokakuuta 2014. Arkistoitu alkuperäisestä 31. lokakuuta 2014. (määrätön)
↑ Hoeffding, W. (1963). "Rajattujen satunnaismuuttujien summien todennäköisyysepäyhtälöt" (PDF) . American Statistical Associationin lehti . 58 (301): 13-30. DOI : 10.2307/2282952 . JSTOR 2282952 .
↑ Hyödyllisiä epätasa-arvoja . logaritmi . Haettu 13. toukokuuta 2020. Arkistoitu alkuperäisestä 19. elokuuta 2020. (määrätön)
↑ M. Kearns, U. Vazirani. Johdatus laskennalliseen oppimisen teoriaan. Luku 9 (Liite), sivut 190-192. MIT Press, 1994.
↑ C.Alippi: Luku "Satunnaistetut algoritmit" julkaisussa Intelligence for Embedded Systems. Springer, 2014, 283 s . ISBN 978-3-319-05278-6 .
↑ Ahlswede, R.; Winter, A. (2003). "Vahva keskustelu kvanttikanavien tunnistamiseen". IEEE Transactions on Information Theory . 48 (3): 569-579. arXiv : quant-ph/0012127 . DOI : 10.1109/18.985947 .
↑ Tropp, J. (2010). "Käyttäjäystävälliset loppurajat satunnaismatriisien summille". Laskennallisen matematiikan perusteet . 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. Matrix Expander Chernoff Bound // Association for Computing MachineryNew YorkNYYhdysvallat. — 2018. Arkistoitu 14. huhtikuuta 2021.
↑ Rasmus Kyng, Zhao Song. Matrix Chernoff Bound for Strongly Rayleigh -jakaumia ja spektrihajottajat muutamasta satunnaisesta ulottuvasta puusta // FOCS. - 2018 - 1. lokakuuta. Arkistoitu alkuperäisestä 22. huhtikuuta 2021.
↑ Goldberg, AV :n kilpailevat huutokaupat useille digitaalisille tuotteille // Algoritmit - ESA 2001 / AV Goldberg, JD Hartline. - 2001. - Voi. 2161. - s. 416. - ISBN 978-3-540-42493-2 . - doi : 10.1007/3-540-44676-1_35 . ; Lemma 6.1
↑ Näytä kaaviot: Raja muuttuvan k :n funktiona Arkistoitu 4. tammikuuta 2015 Wayback Machinessa ja Frontier funktiona k muuttuvalla r:llä Arkistoitu 4. tammikuuta 2015 Wayback Machinessa .
↑ Katso yllä olevaa todistusta.

Lue lisää

Chernoff, H. (1952). "Asymptoottisen tehokkuuden mitta hypoteesin testeissä havaintojen summan perusteella." Annals of Mathematical Statistics . 23 (4): 493-507. doi : 10.1214/aoms/ 1177729330 . JSTOR 2236576 . MR 0057518 . Zbl 0048.11804 .
Chernoff, H. (1981). "Huomautus normaalijakaumaan liittyvästä epätasa-arvosta." Annals of Probability . 9 (3): 533-535. doi : 10.1214/ aop /1176994428 . JSTOR 2243541 . MR 0614640 . Zbl 0457.60014 .
Hagerup, T.; Rub, C. (1990). "Opastettu kierros Chernoffin rajoilla". Tietojenkäsittelykirjeet . 33 (6): 305. DOI : 10.1016/0020-0190(90)90214-I .
Nielsen, F. (2011), Chernoff-tiedot eksponentiaalisista perheistä, arΧiv : 1102.2684 [cs.IT].