Puntuación de Chernov

La estimación de Chernov da estimaciones exponencialmente decrecientes de la probabilidad de grandes desviaciones de sumas de variables aleatorias independientes . Estas estimaciones son más precisas que las estimaciones obtenidas utilizando el primer o segundo momento, como la desigualdad de Markov o la desigualdad de Chebyshev , que dan solo una ley de potencia decreciente. Al mismo tiempo, la estimación de Chernov requiere que las variables aleatorias sean independientes en el agregado, una condición que no requieren ni la desigualdad de Markov ni la desigualdad de Chebyshev, aunque la desigualdad de Chebyshev requiere la independencia por pares de las variables aleatorias.

La estimación de Chernov está relacionada con las desigualdades de Bernstein y la desigualdad de Höfding , que la preceden históricamente.

Caso básico

El caso principal de la estimación de Chernov para una variable aleatoria se logra aplicando la desigualdad de Markov a e tX [1] . Para todos $X$ ${\ estilo de visualización 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}}}.

Cuando X es la suma de n variables aleatorias X 1 , ... , X n , para cualquier ${\ estilo de visualización t> 0}$

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

En particular, optimizando con respecto a t y asumiendo que los X i son independientes, obtenemos

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

(una)

Similarmente

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

y por lo tanto,

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

Los valores específicos de las estimaciones de Chernov se obtienen mediante el cálculo de cantidades específicas . $\mathrm {E} \left[e^{-t\cdot X_{i}}\right]$ $X_{yo}$

Ejemplo

Sean X 1 , ..., X n variables aleatorias de Bernoulli independientes cuya suma es X , y cada una es igual a 1 con probabilidad . Para una variable de Bernoulli, se cumple lo siguiente: ${\ estilo de visualización 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)},

Como consecuencia,

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

Para cualquier y , obtenemos $\delta>0$ ${\ estilo de visualización t = \ ln (1 + \ delta)> 0}$ ${\ estilo de visualización 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))},

y el caso general de la estimación de Chernoff da [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}.

La probabilidad de ocurrencia simultánea de más de n /2 eventos { X k = 1 } es exactamente igual a:

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

La estimación más baja de esta probabilidad se puede calcular utilizando la desigualdad de Chernoff:

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

De hecho, denotando μ = np , obtenemos la forma multiplicativa de la estimación de Chernoff (ver más abajo o el Corolario 13.3 en las notas de clase de Sinclair) [3] :

{\begin{alineado}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}}\derecha)^{2}.}\end{alineado}}

Este resultado admite varias generalizaciones, como se indica a continuación. Se pueden observar varias formas de estimaciones de Chernoff: la forma aditiva original (da una estimación del error absoluto ) o la forma multiplicativa más práctica (limita el error con respecto a la media).

Forma aditiva (evaluación de error absoluto)

El siguiente teorema fue demostrado por Wassily Hoefding [4] .

Teorema de Chernov-Hoefding . Sean X 1 , ..., X n variables aleatorias independientes idénticamente distribuidas que toman los valores {0, 1}. Sea p = E[ X ] y ε > 0 . Después

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

dónde

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

Esta es la divergencia de Kullback-Leibler entre variables aleatorias que tienen una distribución de Bernoulli con parámetros x e y, respectivamente. Si p ≥una2, entonces

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

Se obtiene una estimación más simple debilitando este teorema usando la desigualdad D ( p + ε || p ) ≥ 2 ε 2 , que se sigue de la convexidad de D ( p + ε || p ) y del hecho de que

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

Este resultado es un caso especial de la desigualdad de Hoefding . En algunos casos, se utilizan estimaciones

{\begin{alineado}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\paralelo y)\geq {\frac {(xy)^{2}}{2x}},&&&x\geq y\end{alineado}}

más fuerte para p <unaocho.

Forma multiplicativa (estimación del error relativo)

Estimación multiplicativa de Chernov . Sean X 1 , ..., X n variables aleatorias independientes que toman los valores {0, 1}. Denotemos su suma por X , denotemos la expectativa de esta suma por μ . Entonces por cada

{\ estilo de visualización \ delta \ geq 0}

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

De manera similar, se puede demostrar que para cualquier ${\ estilo de visualización 0<\ delta <1,}$

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

En la práctica, la fórmula anterior a menudo resulta ser engorrosa [2] , por lo que se utilizan estimaciones más débiles pero convenientes.

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,

que se obtienen utilizando una desigualdad de la lista de desigualdades logarítmicas [5] . O una desigualdad aún más débil ${\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 una.

Aplicaciones

Las estimaciones de Chernov tienen aplicaciones en el equilibrio de conjuntos y el enrutamiento de paquetes en redes dispersas .

El problema del equilibrio de conjuntos surge en el diseño de un experimento estadístico . Por lo general, al diseñar un experimento estadístico con las propiedades de los participantes dadas en ese experimento, necesitamos dividir a los participantes en dos grupos que no se superpongan para que cada propiedad esté lo más equilibrada posible entre los dos grupos. Consulte también Probabilidad y computación: algoritmos aleatorios y análisis probabilístico . Archivado el 16 de abril de 2021 en Wayback Machine .

Las estimaciones de Chernoff también se utilizan para lograr límites estrictos en problemas de enrutamiento mediante permutaciones. Esto reduce la congestión de enrutamiento en redes dispersas . Ver más en Probabilidad y computación: algoritmos aleatorios y análisis probabilístico Archivado el 16 de abril de 2021 en Wayback Machine .

Además, las estimaciones de Chernoff se utilizan en la teoría del aprendizaje computacional para probar que el algoritmo de aprendizaje es aproximadamente correcto en probabilidad . Es decir, con una alta probabilidad, este algoritmo tiene un pequeño error en un conjunto suficientemente grande de datos de entrenamiento [6] .

Los puntajes de Chernoff se pueden usar de manera efectiva para evaluar el " nivel de robustez " de una aplicación/algoritmo al examinar su espacio de perturbación mediante la aleatorización. [7]

Puntuación matriz

Rudolf Ahlswede y Andreas Winter utilizaron estimaciones de Chernoff para variables aleatorias con valores matriciales. [8] La siguiente versión de la desigualdad se puede encontrar en el trabajo de Tropp. [9]

Sean M 1 , ..., M t variables aleatorias con valores matriciales tales que y . Denote el operador de norma matricial . Si es casi seguro que la desigualdad se cumple para todos , entonces para cada ε > 0 $M_{i}\in \mathbb {C} ^{d_{1}\times d_{2))$ $\mathbb {E} [M_{i}]=0$ ${\ estilo de visualización \ lVert M \ rVert}$ $METRO$ $\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).

Para concluir que la desviación de 0 está acotada por ε con alta probabilidad, debemos elegir (número de muestras) proporcional al logaritmo de . En el caso general, la dependencia de no es obvia: por ejemplo, tome una matriz aleatoria diagonal de signos de dimensión . La suma del operador de norma de muestra independiente es exactamente la desviación máxima entre recorridos aleatorios independientes de longitud . Para alcanzar un límite fijo de desviación máxima con probabilidad constante, debe aumentar logarítmicamente con . [diez] $t$ ${\displaystyle d_{1}+d_{2))$ ${\ estilo de visualización \ ln (\ min (d_ {1}, d_ {2}))}$ ${\ estilo de visualización d \ veces d}$ $t$ $d$ $t$ $t$ $d$

El siguiente teorema se deriva bajo el supuesto de que tiene un rango bajo para evitar la dependencia de la dimensión. $METRO$

Teorema sin dependencia de la dimensión

Sea 0 < ε < 1 y sea una matriz real simétrica aleatoria con y casi segura. Suponga que cada elemento portador tiene rango como máximo . Pongamos $METRO$ $\|\mathrm {E} [M]\|\leq 1$ $\|M\|\leq\gamma$ $METRO$ $r$

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

Si es casi seguro, entonces ${\ estilo de visualización 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 {poli} (t))),

donde M 1 , ..., M t son copias independientes distribuidas idénticamente de . $METRO$

Teorema para matrices no completamente aleatorias

Ankit Garg, Yin Tat Lee, Zhao Song y Nikhil Srivastava [11] obtuvieron estimaciones de tipo Chernoff para sumas de variables aleatorias con valores matriciales muestreadas mediante un paseo aleatorio de expansión .

Rasmus King y Zhao Song [12] obtuvieron estimaciones de tipo Chernov para sumas de matrices laplacianas de árboles aleatorios.

Variante de muestreo

La siguiente versión de la estimación de Chernoff se puede utilizar para estimar la probabilidad de que la mayoría de la población se convierta en minoría en la muestra y viceversa. [13]

Supongamos que hay una población general y una subpoblación . Denotemos el tamaño relativo de la subpoblación ( ) por . $A$ $B\subconjunto A$ ${\ estilo de visualización | B |/| A |}$ $r$

Digamos que elegimos un número entero agrio y una muestra aleatoria de tamaño . Denotemos el tamaño relativo de la subpoblación ( ) por . $k$ $S\subconjunto A$ $k$ $|B\cap S|/|S|$ ${\ Displaystyle r_ {S}}$

Entonces para cada acción : ${\ estilo de visualización d \ en [0,1]}$

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

En particular, si ─ es la mayoría en (es decir, ), entonces podemos estimar desde arriba la probabilidad de que siga siendo la mayoría en [ 14] : $B$ $A$ ${\ estilo de visualización 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\derecha).$

Esta estimación, por supuesto, no es exacta. Por ejemplo, si , entonces obtenemos una estimación trivial . ${\ estilo de visualización r = 0,5}$ ${\ estilo de visualización P> 0}$

Evidencia

Teorema de Chernov-Hoefding (forma aditiva)

Sea q = p + ε . Tomando a = nq en la fórmula (1) , obtenemos:

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

Ahora, sabiendo que Pr( X i = 1) = p , Pr( X i = 0) = 1 − p , tenemos

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

Entonces podemos calcular fácilmente el mínimo usando la técnica de diferenciación:

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

Igualando la expresión resultante a cero y resolviendo la ecuación con respecto a , obtenemos $t$

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

asi que

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

Como consecuencia,

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

Como q = p + ε > p , vemos que t > 0 , por lo que t satisface nuestra estimación . Una vez que tenemos t , podemos volver a las ecuaciones anteriores y encontrar

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

Ahora tenemos el resultado deseado porque

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

Para completar la prueba en el caso simétrico, simplemente definimos una variable aleatoria Y i = 1 − X i , le aplicamos exactamente la misma prueba y sumamos el resultado a nuestra estimación.

Forma multiplicativa

Sea Pr( X yo = 1) = pag yo . Según la fórmula (1) ,

{\begin{alineado}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}\nombre del operador {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{alineado}}

La tercera línea se deriva del hecho de que toma el valor e t con probabilidad p i y el valor 1 con probabilidad 1 − p i . Esto es idéntico a los cálculos anteriores en la prueba de la forma aditiva. $e^{tX_{i))$

Reescribiendo como y recordando que (si x > 0 , entonces la desigualdad es estricta), hacemos . Se puede obtener el mismo resultado reemplazando directamente a en el estimador de Chernoff con (1 + δ ) μ . [quince] $p_{i}e^{t}+(1-p_{i})$ $p_{i}(e^{t}-1)+1$ ${\ estilo de visualización 1 + x \ leq e ^ {x}}$ $x=p_{i}(e^{t}-1)$

De este modo,

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

Si solo ponemos t = ln(1 + δ ) , de modo que t > 0 para δ > 0 , entonces podemos reemplazar eso en la última expresión y encontrar

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

QED

Véase también

medir la desigualdad de concentración

Enlaces

↑ Este método fue utilizado por primera vez por Sergei Bernstein en pruebas relacionadas con las desigualdades de Bernstein .
↑ 1 2 Mitzenmacher, Michael y Upfal, Eli. Probabilidad y Computación: Algoritmos Aleatorios y Análisis Probabilístico . - Prensa de la Universidad de Cambridge, 2005. - ISBN 978-0-521-83540-4 . -doi : 10.1017 / CBO9780511813603.005 . Archivado el 16 de abril de 2021 en Wayback Machine .
↑ Sinclair, Alistair Notas de clase para el curso "Aleatoriedad y computación" (enlace no disponible) (otoño de 2011). Consultado el 30 de octubre de 2014. Archivado desde el original el 31 de octubre de 2014. (indefinido)
↑ Hoeffding, W. (1963). “Desigualdades de probabilidad para sumas de variables aleatorias acotadas” (PDF) . Revista de la Asociación Estadounidense de Estadística . 58 (301): 13-30. DOI : 10.2307/2282952 . JSTOR2282952 . _
↑ Desigualdades útiles . logaritmo _ Consultado el 13 de mayo de 2020. Archivado desde el original el 19 de agosto de 2020. (indefinido)
↑ M. Kearns, U. Vazirani. Una introducción a la teoría del aprendizaje computacional. Capítulo 9 (Apéndice), páginas 190-192. Prensa del MIT, 1994.
↑ C.Alippi: capítulo "Algoritmos aleatorios" en Intelligence for Embedded Systems. Springer, 2014, 283 páginas ISBN 978-3-319-05278-6 .
↑ Ahlswede, R.; Invierno, A. (2003). “Fuerte conversación para la identificación a través de canales cuánticos”. Transacciones IEEE sobre teoría de la información . 48 (3): 569-579. arXiv : quant-ph/0012127 . DOI : 10.1109/18.985947 .
↑ Tropp, J. (2010). "Límites de cola fáciles de usar para sumas de matrices aleatorias". Fundamentos de Matemática Computacional . 12 (4): 389-434. arXiv : 1004.4389 . DOI : 10.1007/s10208-011-9099-z .
↑ Magen, A. & Zouzias, A. (2011), Límites de Chernoff con valores de matriz de rango bajo y multiplicación de matriz aproximada, arΧiv : 1005.2724 [cs.DM].
↑ Ankit Garg, Yin Tat Lee, Zhao Song, Nikhil Srivastava. A Matrix Expander Chernoff Bound // Association for Computing MachineryNueva YorkNYEstados Unidos. — 2018. Archivado el 14 de abril de 2021.
↑ Rasmus Kyng, Zhao Song. Un límite de Chernoff de matriz para distribuciones fuertemente Rayleigh y dispersores espectrales de unos pocos árboles de expansión aleatorios // FOCS. - 2018. - 1 de octubre. Archivado desde el original el 22 de abril de 2021.
↑ Goldberg, AV Subastas competitivas para múltiples bienes digitales // Algoritmos - ESA 2001 / AV Goldberg, JD Hartline. - 2001. - vol. 2161. - Pág. 416. - ISBN 978-3-540-42493-2 . -doi : 10.1007 / 3-540-44676-1_35 . ; Lema 6.1
↑ Ver gráficos: Frontier en función de r con k variable Archivado el 4 de enero de 2015 en Wayback Machine y Frontier en función de k con r variable Archivado el 4 de enero de 2015 en Wayback Machine .
↑ Consulte la prueba anterior.

Lecturas adicionales

Chernoff, H. (1952). "Una medida de eficiencia asintótica para pruebas de una hipótesis basada en la suma de observaciones". Anales de Estadística Matemática . 23 (4): 493-507. doi : 10.1214/aoms/ 1177729330 . JSTOR2236576 . _ MR 0057518 . Zbl 0048.11804 .
Chernoff, H. (1981). "Una nota sobre una desigualdad que involucra la distribución normal". Anales de probabilidad . 9 (3): 533-535. doi : 10.1214/ aop /1176994428 . JSTOR2243541 . _ MR 0614640 . Zbl 0457.60014 .
Hagerup, T.; Rub, C. (1990). "Una visita guiada por los límites de Chernoff". Cartas de procesamiento de información . 33 (6): 305. DOI : 10.1016/0020-0190(90)90214-I .
Nielsen, F. (2011), información de Chernoff de familias exponenciales, arΧiv : 1102.2684 [cs.IT].