Ver el código de «Cotas de Chernoff»

En la [[teoría de probabilidad]], las '''Cotas de Chernoff''' fueron nombradas luego de su presentación por [[Herman Chernoff]] y, gracias a Herman Rubin,<ref>{{cita libro | url=http://www.crcpress.com/product/isbn/9781482204964 | título=Past, Present, and Future of Statistics | capítulo=A career in statistics | página=35 | editorial=CRC Press | last1=Chernoff | first1=Herman | editor-first1=Xihong | editor-last1=Lin | editor-first2=Christian | editor-last2=Genest | editor-first3=David L. | editor-last3=Banks | editor-first4=Geert | editor-last4=Molenberghs | editor-first5=David W. | editor-last5=Scott | editor-first6=Jane-Ling | editor-last6=Wang | año=2014 | isbn=9781482204964 | urlcapítulo=http://nisla05.niss.org/copss/past-present-future-copss.pdf}}</ref> se dieron cotas exponencialmente decrecientes para las distribuciones de sumas de [[Variable aleatoria|variables aleatorias]] independientes. Son una cota más fina que las conocidas cotas basadas en el primer y segundo momento tales como la [[inecuación]] de Markov o la inecuación de Chebyshev, las cuales solo obtienen cotas de nivel exponencial cuando la distribución decrece. Sin embargo, las cotas de Chernoff requieren que las variables sean independientes - una condición que ni las inecuaciones de Markov ni de Chebyshev requieren.

Están relacionadas con las (antecesoras históricas) inecuaciones de Bernstein, y a la inecuación de Hoeffding.

==Ejemplo==
Sean {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} variables aleatorias independientes que distribuyen Bernoulli, cada una con probabilidad ''p'' > 1/2 de ser igual a 1. Entonces la probabilidad de la ocurrencia simultánea de más de ''n''/2 de los eventos {{math|{''X<sub>k</sub>'' {{=}} 1} }} tiene un valor exacto {{mvar|S}}, donde

:<math> S=\sum_{i = \lfloor \tfrac{n}{2} \rfloor + 1}^n \binom{n}{i}p^i (1 - p)^{n - i} .</math>

La cota de Chernoff muestra que {{mvar|S}} tiene la siguiente cota inferior:

:<math> S \ge 1 - e^{-\frac{1}{2p}n \left(p - \frac{1}{2} \right)^2} .</math>

En efecto, notando que {{math|''μ'' {{=}} ''np''}}, lo cual obtenemos por la forma multiplicativa de las cotas de Chernoff (ver más abajo o el [[Corolario]] 13.3 en las notas de clases de Sinclair),<ref>{{cita web|url = http://www.cs.berkeley.edu/~sinclair/cs271/n13.pdf|título = Class notes for the course "Randomness and Computation"|fecha = Fall 2011|fechaacceso = 30 de octubre de 2014|website = |editorial = |apellido = Sinclair|nombre = Alistair|urlarchivo = https://web.archive.org/web/20141031035717/http://www.cs.berkeley.edu/~sinclair/cs271/n13.pdf|fechaarchivo = 31 de octubre de 2014}}</ref>

:<math>\begin{align}
\Pr\left (\sum_{k=1}^n X_k \le\left\lfloor \tfrac{n}{2}\right\rfloor \right ) &=\Pr\left (\sum_{k=1}^n X_k\le\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{align}</math>

Estas cotas admiten varias generalizaciones como se señala más abajo. Podemos encontrar varias representaciones de las cotas de Chernoff: la original ''forma aditiva'' (la cual da una cota para el error absoluto) o la más práctica ''forma multiplicativa'' (la cual da una cota del error relativo para la esperanza).

== Primer paso para probar las cotas de Chernoff ==
Las cotas de Chernoff para una variable aleatoria {{mvar|X}}, la cual es la suma de {{mvar|n}} variables aleatorias independientes {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}}, se obtienen al aplicar {{mvar|e<sup>tX</sup>}} para algún ''t'' bien elegido. Este método fue aplicado por primera vez por Sergei Bernstein para probar las relacionadas inecuaciones de Bernstein.

De la inecuación de Markov y usando la independencia podemos llegar a la siguiente inecuación:

Para cualquier ''t'' > 0,

: <math>\Pr(X \ge a) = \Pr\left (e^{tX} \ge e^{ta}\right ) \le \frac{ E \left [e^{tX} \right ]}{e^{ta}} = e^{-ta}\mathrm{E} \left [\prod_i e^{tX_i} \right].</math>

En particular optimizando sobre ''t'' y usando la independencia de {{mvar|X<sub>i</sub>}} obtenemos,

:| <math> \Pr(X \ge a)  \leq \min_{t>0} e^{-ta} \prod_i E \left [e^{tX_i} \right ].</math>         ''(1)''

Similarmente,

: <math>\Pr (X \le a) = \Pr\left (e^{-tX} \ge e^{-ta}\right) </math>

y también,

: <math> \Pr (X \le a) \leq \min_{t>0} e^{ta} \prod_i \mathrm{E} \left[e^{-tX_i} \right ]</math>

== Definiciones precisas y demostraciones ==

=== Teorema para la forma aditiva (error absoluto) ===
El siguiente teorema fue anunciado por Wassily Hoeffding y por esto es llamado el teorema Chernoff-Hoeffding.

:'''Teorema Chernoff-Hoeffding.''' Supón que {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} son variables aleatorias igualmente distribuidas, tomando valores en {{math|{0, 1}.}} Sea {{math|''p'' {{=}} E[''X<sub>i</sub>'']}} y {{math|''ε'' > 0}}. Entonces
::<math>\begin{align}
\Pr \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\|p) n} \\
\Pr \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\|p) n}
\end{align}</math>
:donde
::<math> D(x\|y) = x \ln \frac{x}{y} + (1-x) \ln \left (\frac{1-x}{1-y} \right )</math>
:es la divergencia Kullback–Leibler entre dos variables aleatorias que distribuyen Bernoulli con parámetros ''x'' y ''y'' respectivamente. Si {{math|''p'' ≥ {{sfrac|1|2}},}} entonces
::<math> \Pr\left ( X>np+x \right ) \leq \exp \left (-\frac{x^2}{2np(1-p)} \right ).</math>

==== Demostración ====
Sea {{math|''q'' {{=}} ''p'' + ''ε''}}. Tomando {{math|''a'' {{=}} ''nq''}} en ''(1)'', obtenemos:

:<math>\Pr\left ( \frac{1}{n} \sum X_i \ge q\right )\le \inf_{t>0} \frac{E \left[\prod e^{t X_i}\right]}{e^{tnq}} = \inf_{t>0} \left ( \frac{ E\left[e^{tX_i} \right] }{e^{tq}}\right )^n.</math>

Luego, conociendo que {{math|Pr(''X<sub>i</sub>'' {{=}} 1) {{=}} ''p'', Pr(''X<sub>i</sub>'' {{=}} 0) {{=}} 1 − ''p''}}, tenemos que

:<math>\left (\frac{\mathrm{E}\left[e^{tX_i} \right] }{e^{tq}}\right )^n = \left (\frac{p e^t + (1-p)}{e^{tq} }\right )^n = \left ( pe^{(1-q)t} + (1-p)e^{-qt} \right )^n.</math>

Por lo tanto podemos computar fácilmente el ínfimo, usando cálculo:

:<math>\frac{d}{dt} \left (pe^{(1-q)t} + (1-p)e^{-qt} \right) = (1-q)pe^{(1-q)t}-q(1-p)e^{-qt}</math>

Igualando la ecuación a 0 y resolviéndola, tenemos

:<math>\begin{align}
(1-q)pe^{(1-q)t} &= q(1-p)e^{-qt} \\
(1-q)pe^{t} &= q(1-p)
\end{align}</math>

entonces

:<math>e^t = \frac{(1-p)q}{(1-q)p}.</math>

Por lo que,

:<math>t = \log\left(\frac{(1-p)q}{(1-q)p}\right).</math>

Como {{math|''q'' {{=}} ''p'' + ''ε'' > ''p''}}, vemos que {{math|''t'' > 0}}, por lo cual nuestra cota se satisface para {{mvar|t}}. Luego de resolverlo para {{mvar|t}}, podemos sustituir en las ecuaciones anteriores para llegar a que

:<math>\begin{align}
\log \left (pe^{(1-q)t} + (1-p)e^{-qt} \right ) &= \log \left ( e^{-qt}(1-p+pe^t) \right ) \\
&= \log\left (e^{-q \log\left(\frac{(1-p)q}{(1-q)p}\right)}\right) + \log\left(1-p+pe^{\log\left(\frac{1-p}{1-q}\right)}e^{\log\frac{q}{p}}\right ) \\
&= -q\log\frac{1-p}{1-q} -q \log\frac{q}{p} + \log\left(1-p+ p\left(\frac{1-p}{1-q}\right)\frac{q}{p}\right) \\
&= -q\log\frac{1-p}{1-q} -q \log\frac{q}{p} + \log\left(\frac{(1-p)(1-q)}{1-q}+\frac{(1-p)q}{1-q}\right) \\
&= -q \log\frac{q}{p} + \left ( -q\log\frac{1-p}{1-q} + \log\frac{1-p}{1-q} \right ) \\
&= -q\log\frac{q}{p} + (1-q)\log\frac{1-p}{1-q} \\
&= -D(q \| p).
\end{align}</math>

Ahora tenemos el resultado deseado, que

:<math>\Pr \left (\tfrac{1}{n}\sum X_i \ge p + \varepsilon\right ) \le e^{-D(p+\varepsilon\|p) n}.</math>

Para completar la demostración para el caso simétrico, simplemente definimos la variable aleatoria {{math|''Y<sub>i</sub>'' {{=}} 1 − ''X<sub>i</sub>''}}, aplicamos la misma demostración, y sustituímos en nuestra cota.

==== Cotas más simples ====
Una cota más simple se obtiene al relajar el teorema usando {{math|''D''(''p'' + ''x'' {{!!}} ''p'') ≥ 2''x''<sup>2</sup>}}, debido a que {{math|''D''(''p'' + ''x'' {{!!}} ''p'')}} es convexo y al hecho de que

:<math>\frac{d^2}{dx^2} D(p+x\|p) = \frac{1}{(p+x)(1-p-x)}\geq 4=\frac{d^2}{dx^2}(2x^2).</math>

Este resultado es un caso especial de la inecuación de Hoeffding. En algunas ocasiones, la cota

:<math>D( (1+x) p \| p) \geq \tfrac{1}{4} x^2 p, \qquad -\tfrac{1}{2} \leq x \leq \tfrac{1}{2},</math>

la cual es más fuerte para {{math|''p'' < {{sfrac|1|8}},}} es también usada.

=== Teorema para la forma multiplicativa de las cotas de Chernoff (error relativo) ===
:'''Cota de Chernoff Multiplicativa.''' Supón que {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} son variables aleatorias independientes tomando valores en {{math|{0, 1}.}} Sea {{mvar|X}} la variable que denota su suma y {{math|''μ'' {{=}} E[''X'']}} la suma de los valores esperados. Entonces para todo {{math|''δ'' > 0}},
::<math>\Pr ( X > (1+\delta)\mu) < \left(\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu.</math>

==== Demostración ====
Evaluando {{math|Pr(''X<sub>i</sub>'' {{=}} 1) {{=}} ''p<sub>i</sub>''}}.
De acuerdo a ''(1)'',

:<math>\begin{align}
\Pr (X > (1 + \delta)\mu) &\le \inf_{t > 0} \frac{\mathrm{E}\left[\prod_{i=1}^n\exp(tX_i)\right]}{\exp(t(1+\delta)\mu)}\\
& = \inf_{t > 0} \frac{\prod_{i=1}^n\mathrm{E}\left [e^{tX_i} \right]}{\exp(t(1+\delta)\mu)} \\
& = \inf_{t > 0} \frac{\prod_{i=1}^n\left[p_ie^t + (1-p_i)\right]}{\exp(t(1+\delta)\mu)}
\end{align}</math>

La tercera línea abajo está dada porque <math>e^{tX_i}</math> toma el valor {{mvar|e<sup>t</sup>}} con probabilidad {{mvar|p<sub>i</sub>}} y el valor 1 con probabilidad {{math|1 − ''p<sub>i</sub>''}}. Este es idéntico al cálculo anterior en la demostración del teorema de la forma aditiva.

Reescribiendo <math>p_ie^t + (1-p_i)</math> as <math>p_i(e^t-1) + 1</math> y notando que <math>1+x \le e^x</math> (con inecuación estricta si {{math|''x'' > 0}}), hacemos <math>x = p_i(e^t-1)</math>. 
El mismo resultado puede obtenerse al reemplazar {{mvar|a}} en la ecuación para la cota de Chernoff con {{math|(1 + ''δ'')''μ''}}.

Por lo tanto,

:<math>\Pr(X > (1+\delta)\mu) < \frac{\prod_{i=1}^n\exp(p_i(e^t-1))}{\exp(t(1+\delta)\mu)} = \frac{\exp\left((e^t-1)\sum_{i=1}^n p_i\right)}{\exp(t(1+\delta)\mu)}  = \frac{\exp((e^t-1)\mu)}{\exp(t(1+\delta)\mu)}.</math>

Si simplemente hacemos {{math|''t'' {{=}} log(1 + ''δ'')}} tal que {{math|''t'' > 0}} para {{math|''δ'' > 0}}, podemos sustituir y encontrar

:<math>\frac{\exp((e^t-1)\mu)}{\exp(t(1+\delta)\mu)} = \frac{\exp((1+\delta - 1)\mu)}{(1+\delta)^{(1+\delta)\mu}} = \left[\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right]^\mu</math>

Esto prueba el resultado deseado. Una estrategia similar de demostración puede ser usada para mostrar que

:<math>\Pr(X < (1-\delta)\mu) < \left[\frac{\exp(-\delta)}{(1-\delta)^{(1-\delta)}}\right]^\mu.</math>

La fórmula anterior en la práctica es usualmente torpe para computar,<ref name="MitzenmacherUpfal">{{cita libro | url=http://books.google.com/books/about/Probability_and_Computing.html?id=0bAYl6d7hvkC | título=Probability and Computing: Randomized Algorithms and Probabilistic Analysis | editorial=[[Cambridge University Press]] | autor=Mitzenmacher, Michael and Upfal, Eli | año=2005 | isbn=0-521-83540-2}}</ref> por lo que las siguientes cotas más flojas pero más convenientes son usadas a menudo:

:<math>\Pr( X \ge (1+\delta)\mu) \le e^{-\frac{\delta^2\mu}{3}}, \qquad 0 < \delta < 1,</math>
:<math>\Pr( X \ge (1+\delta)\mu) \le e^{-\frac{\delta\mu}{3}}, \qquad 1 < \delta,</math>
:<math>\Pr( X \le (1-\delta)\mu) \le e^{-\frac{\delta^2\mu}{2}}, \qquad 0 < \delta < 1.</math>

=== Mejores cotas de Chernoff para algunos casos especiales ===

Podemos obtener cotas más fuertes usando técnicas de demostración más simples para algunos casos especiales de variables aleatorias simétricas.
 
Supón que {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} son variables aleatorias independientes, y que {{mvar|X}} denota la suma de ellas.

* Si <math>\Pr(X_i = 1)  = \Pr(X_i = -1) = \tfrac{1}{2}</math>. Entonces,
::<math>\Pr( X \ge a) \le e^{\frac{-a^2}{2n}}, \qquad a > 0,</math>
:y por lo tanto también
::<math>\Pr( |X| \ge a) \le 2e^{\frac{-a^2}{2n}}, \qquad a > 0.</math>

* Si <math>\Pr(X_i = 1) = \Pr(X_i = 0) = \tfrac{1}{2}, \mathrm{E}[X] = \mu = \frac{n}{2} </math> Entonces,
::<math>\Pr( X \ge \mu+a) \le e^{\frac{-2a^2}{n}}, \qquad a > 0,</math>
::<math>\Pr( X \le \mu-a) \le e^{\frac{-2a^2}{n}}, \qquad 0 < a < \mu,</math>

== Aplicaciones de las cotas de Chernoff ==

Las cotas de Chernoff tienen aplicaciones muy útiles en el balance de conjuntos y el enrutamiento de paquetes en redes esparcidas.

El problema del balance de conjuntos surge durante el diseño de experimentos estadísticos. Típicamente mientras diseñamos un experimento estadístico, dadas las características de cada participante en el experimento, necesitamos conocer como dividir los participantes en dos conjuntos disjuntos tal que las características están tan balanceada como sea posible entre los dos grupos. Referirse a [http://books.google.com/books?id=0bAYl6d7hvkC&printsec=frontcover&source=gbs_summary_r&cad=0#PPA71,M1 sección del libro] para más información del problema.

Las cotas de Chernoff son también usadas para obtener cotas ajustadas para los problemas de la permutación de enrutamiento con una congestión de redes reducida durante el enrutamiento de paquetes en redes esparcidas. Referirse a [http://books.google.com/books?id=0bAYl6d7hvkC&printsec=frontcover&source=gbs_summary_r&cad=0#PPA72,M1 sección del libro] para un completo tratamiento del problema.

Las cotas de Chernoff puedes ser usadas de manera efectiva para evaluar el "nivel de robustez" de una aplicación/algoritmo al explorar su espacio de perturbación con aleatoriedad.<ref name="Alippi2014">C.Alippi: "Randomized Algorithms" chapter in ''Intelligence for Embedded Systems.'' Springer, 2014, 283pp, ISBN 978-3-319-05278-6.</ref>
El uso de cotas de Chernoff permite abandonar la hipótesis de las fuertes -y mayormente no realistas- pequeñas perturbaciones. El nivel de robustez puede ser, en cambio, usado para validar o rechazar una elección específica de algoritmo, una implementación de [[hardware]] o la pertinencia de una solución cuyos parámetros estructurales son afectados con incertidumbre.

== Cotas de Chernoff para matrices ==

Rudolf Ahlswede y Andreas Winter introdujeron {{Harv| Ahlswede|Winter|2003}} una cota de Chernoff para variables aleatorias con representación matricial.

Si ''M'' está distribuida acorde a cierta distribución sobre {{math|''d'' × ''d''}} matrices con esperanza 0, y si {{math|''M''<sub>1</sub>, ..., ''M<sub>t</sub>''}} son copias independientes de ''M'' entonces para todo {{math|''ε'' > 0}},

:<math>\Pr\left( \left\| \frac{1}{t} \sum_{i=1}^t M_i \right\|_2 > \varepsilon \right) \leq d \exp \left( -C \frac{\varepsilon^2 t}{\gamma^2} \right).</math>

donde <math> \lVert M \rVert_2 \leq \gamma </math> se cumple casi siempre y ''C'' > 0 es una constante.

Notar que el número de muestras en la inecuación depende logarítmicamente de ''d''. En general, desafortunadamente, tal dependencia es inevitable: toma por ejemplo una matriz diagona aleatoria de dimensión ''d''. El operador norma de la suma de ''t'' muestras independientes es precisamente la máxima desviación entre ''d'' caminos independientes de longitud ''t''. En orden de alcanzar una cota fija en la desviación máxima con probabilidad constante, es fácil darse cuenta de que ''t'' debería crecer logarítmicamente con ''d'' en este caso.<ref>*{{cite arXiv |last1=Magen |first1=A. |last2=Zouzias |first2=A. |year=2011 |title=Low Rank Matrix-Valued Chernoff Bounds and Approximate Matrix Multiplication |class=cs.DM |eprint=1005.2724 }}</ref>

El siguiente teorema se puede satisfacer si asumimos que ''M'' tiene bajo rango, con el objetivo de evitar la dependencia de las dimensiones.


=== Teorema sin la dependencia de las dimensiones ===

Sea {{math|0 < ''ε'' < 1}} y ''M'' una [[matriz simétrica]] real aleatoria con <math>\| \mathrm{E}[M] \|_2 \leq 1 </math> y <math>\| M\|_2 \leq \gamma </math> casi siempre. Asume que cada elemento en la base de 'M' tiene a lo sumo rango ''r''. Evalúa 

:<math> t = \Omega \left( \frac{\gamma\log (\gamma/\varepsilon^2)}{\varepsilon^2} \right).</math>

Si <math> r \leq t </math> se cumple casi siempre, entonces

:<math>\Pr\left(\left\| \frac{1}{t} \sum_{i=1}^t M_i - \mathrm{E}[M] \right\|_2 > \varepsilon \right) \leq \frac{1}{\mathbf{poly}(t)}</math>

donde {{math|''M''<sub>1</sub>, ..., ''M<sub>t</sub>''}} son copias de 'M' igualmente distribuidas.

== Variante de muestreo ==

La siguiente variante de las cotas de Chernoff puede ser usada para acotar la probabilidad de que una mayoría en una población se convierta en minoría en una muestra, o viceversa<ref>{{cita libro | doi = 10.1007/3-540-44676-1_35| capítulo = Competitive Auctions for Multiple Digital Goods| título = Algorithms — ESA 2001| volumen = 2161| páginas = 416| series = Lecture Notes in Computer Science| año = 2001| last1 = Goldberg | first1 = A. V. | last2 = Hartline | first2 = J. D. | isbn = 978-3-540-42493-2}}; lemma 6.1</ref>

Supón que hay una población general ''A'' y una sub-población ''B''⊆''A''. Denota el tamaño relativo de la sub-población (|''B''|/|''A''|) con ''r''.

Supón que elegimos un entero ''k'' y una muestra aleatoria ''S''⊂''A'' de tamaño ''k''. Denota el tamaño relativo de la sub-población (|''B''∩''S''|/|''S''|) con ''r<sub>S</sub>''.

Entonces, para toda fracción ''d''∈[0,1]:

:<math>\mathrm{Pr}\left(r_S < (1-d)\cdot r\right) < \exp\left(-r\cdot d^2 \cdot k/2\right)</math>

En particular, si ''B'' es una mayoría en ''A'' (''r'' > 0.5) podemos acotar la probabilidad de que ''B'' se mantenga como una minoría en ''S'' (''r<sub>S</sub>''>0.5) tomando: ''d'' = 1 - 1 / (2 ''r''):<ref>Ver grafos de: [https://www.desmos.com/calculator/eqvyjug0re la cota como una función de ''r'' donde ''k'' cambia] y [https://www.desmos.com/calculator/nxurzg7bqj la cota como una función de ''k'' donde ''r'' cambia].</ref>

:<math>\mathrm{Pr}\left(r_S > 0.5\right) > 1 - \exp\left(-r\cdot \left(1 - \frac{1}{2 r}\right)^2 \cdot k/2\right)</math>

Esta cota no es fina para nada. Por ejemplo, cuando  ''r'' = 0.5 tenemos una cota trivial ''Prob'' > 0.

==Referencias==

{{listaref}}<!--added under references heading by script-assisted edit-->
* {{cita publicación
 |last1=Chernoff |first1=H.
 |año=1952
 |título=A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
 |url=https://archive.org/details/sim_annals-of-mathematical-statistics_1952-12_23_4/page/493 |publicación=[Annals of Mathematical Statistics]
 |volumen=23 |número=4 |páginas=493–507
 |doi=10.1214/aoms/1177729330
 |jstor=2236576
 |mr=57518
 |zbl=0048.11804
}}
* {{cita publicación
 |last1=Hoeffding |first1=W.
 |año=1963
 |título=Probability Inequalities for Sums of Bounded Random Variables
 |url=https://archive.org/details/sim_journal-of-the-american-statistical-association_1963-03_58_301/page/13 |publicación=[Journal of the American Statistical Association]
 |volumen=58 |número=301 |páginas=13–30
 |doi=10.2307/2282952
 |jstor=2282952
}}
* {{cita publicación
 |last1=Chernoff |first1=H.
 |año=1981
 |título=A Note on an Inequality Involving the Normal Distribution
 |url=https://archive.org/details/sim_annals-of-probability_1981-06_9_3/page/533 |publicación=[Annals of Probability]
 |volumen=9 |número=3 |páginas=533
 |doi=10.1214/aop/1176994428
 |jstor=2243541
 |mr=614640
 |zbl=0457.60014
}}
* {{cita publicación
 |last1=Hagerup |first1=T.
 |año=1990
 |título=A guided tour of Chernoff bounds
 |url=https://archive.org/details/sim_information-processing-letters_1990-02-10_33_6/page/n32 |publicación=[Information Processing Letters]
 |volumen=33 |número=6 |páginas=305
 |doi=10.1016/0020-0190(90)90214-I
}}
* {{cita publicación
 |last1=Ahlswede |first1=R.
 |last2=Winter |first2=A.
 |año=2003
 |título=Strong Converse for Identification via Quantum Channels
 |volumen=48 |número=3 |páginas=569–579
 |publicación=[IEEE Transactions on Information Theory]
 |arxiv=quant-ph/0012127
 |doi=10.1109/18.985947
 |ref=harv
}}
* {{cita libro
 |last1=Mitzenmacher |first1=M.
 |last2=Upfal |first2=E.
 |año=2005
 |título=Probability and Computing: Randomized Algorithms and Probabilistic Analysis
 |url=http://books.google.com/books?id=0bAYl6d7hvkC
 |isbn=978-0-521-83540-4
}}
* {{cite arXiv
 |last=Nielsen |first=F.
 |year=2011
 |title=Chernoff information of exponential families
 |class=cs.IT
 |eprint=1102.2684
}}

{{DEFAULTSORT:Chernoff Bound}}
{{Control de autoridades}}
[[Categoría:Inecuaciones probabilísticas]]