Chernoff atado

En teoría de probabilidad , un límite de Chernoff es un límite superior exponencialmente decreciente en la cola de una variable aleatoria basada en su función generadora de momentos . El mínimo de todos estos límites exponenciales forma el límite de Chernoff o de Chernoff-Cramér , que puede decaer más rápido que el exponencial (por ejemplo, subgaussiano ). ^{[1] [2]} Es especialmente útil para sumas de variables aleatorias independientes, como las sumas de variables aleatorias de Bernoulli . ^{[3] [4]}

El límite recibe comúnmente el nombre de Herman Chernoff , quien describió el método en un artículo de 1952, ^[5] aunque el propio Chernoff lo atribuyó a Herman Rubin. ^[6] En 1938, Harald Cramér había publicado un concepto casi idéntico ahora conocido como teorema de Cramér .

Es un límite más preciso que los límites de cola basados ​​en el primer o segundo momento, como la desigualdad de Markov o la desigualdad de Chebyshev , que solo producen límites de ley de potencia en el decaimiento de la cola. Sin embargo, cuando se aplica a sumas, el límite de Chernoff requiere que las variables aleatorias sean independientes, una condición que no se requiere ni en la desigualdad de Markov ni en la desigualdad de Chebyshev.

El límite de Chernoff está relacionado con las desigualdades de Bernstein . También se utiliza para demostrar la desigualdad de Hoeffding , la desigualdad de Bennett y la desigualdad de McDiarmid .

El límite genérico de Chernoff para una variable aleatoria se obtiene aplicando la desigualdad de Markov a (por eso a veces se lo llama límite exponencial de Markov o límite exponencial de momentos ). Para valores positivos, esto da un límite en la cola derecha de en términos de su función generadora de momentos :${\estilo de visualización X}$$estilo de visualización e^{tX}}$${\estilo de visualización t}$${\estilo de visualización X}$ ${\displaystyle M(t)=\nombre del operador {E} (e^{tX})}$

${\displaystyle \operatorname {P} \left(X\geq a\right)=\operatorname {P} \left(e^{tX}\geq e^{ta}\right)\leq M(t)e^{-ta}\qquad (t>0)}$

Dado que este límite se cumple para cada positivo , podemos tomar el ínfimo :${\estilo de visualización t}$

${\displaystyle \operatorname {P} \left(X\geq a\right)\leq \inf _{t>0}M(t)e^{-ta}}$

Realizando el mismo análisis con negativo obtenemos un límite similar en la cola izquierda :${\estilo de visualización t}$

${\displaystyle \operatorname {P} \left(X\leq a\right)=\operatorname {P} \left(e^{tX}\geq e^{ta}\right)\leq M(t)e^{-ta}\qquad (t<0)}$

y

${\displaystyle \operatorname {P} \left(X\leq a\right)\leq \inf _{t<0}M(t)e^{-ta}}$

La cantidad puede expresarse como valor esperado o equivalente .$Estilo de visualización M(t)e^{-ta}}$${\displaystyle \operatorname {E} (e^{tX})e^{-ta}}$${\displaystyle \operatorname {E} (e^{t(Xa)})}$

La función exponencial es convexa, por lo que por la desigualdad de Jensen . Se deduce que el límite en la cola derecha es mayor o igual a uno cuando , y por lo tanto trivial; de manera similar, el límite izquierdo es trivial para . Por lo tanto, podemos combinar los dos ínfimos y definir el límite de Chernoff bilateral: que proporciona un límite superior en la función de distribución acumulativa plegada de (plegada en la media, no en la mediana).${\displaystyle \operatorname {E} (e^{tX})\geq e^{t\operatorname {E} (X)}}$${\displaystyle a\leq \nombre del operador {E} (X)}$${\displaystyle a\geq \operatorname {E} (X)}$$${\displaystyle C(a)=\inf _{t}M(t)e^{-ta}}$$${\estilo de visualización X}$

El logaritmo del límite de Chernoff bilateral se conoce como función de velocidad (o transformada de Cramér ) . Es equivalente a la transformada de Legendre-Fenchel o conjugado convexo de la función generadora de cumulantes , definida como: La función generadora de momentos es log-convexa , por lo que por una propiedad del conjugado convexo, el límite de Chernoff debe ser log-cóncavo . El límite de Chernoff alcanza su máximo en la media, y es invariante bajo traslación: .${\displaystyle I=-\log C}$ ${\displaystyle K=\log M}$$${\displaystyle I(a)=\sup _{t}at-K(t)}$$${\displaystyle C(\nombre del operador {E} (X))=1}$${\textstyle C_{X+k}(a)=C_{X}(a-k)}$

El límite de Chernoff es exacto si y solo si es una masa concentrada única ( distribución degenerada ). El límite es estricto solo en los extremos de una variable aleatoria limitada o más allá de ellos, donde los ínfimos se alcanzan para infinito . Para variables aleatorias no acotadas, el límite no es estricto en ningún punto, aunque es asintóticamente estricto hasta factores subexponenciales ("exponencialmente estricto"). ^{[ cita requerida ]} Los momentos individuales pueden proporcionar límites más estrictos, a costa de una mayor complejidad analítica. ^[7]${\displaystyle X}$${\displaystyle t}$

En la práctica, el límite exacto de Chernoff puede ser difícil de manejar o de evaluar analíticamente, en cuyo caso se puede utilizar en su lugar un límite superior adecuado en la función generadora de momentos (o cumulante) (por ejemplo, un CGF subparabólico que proporcione un límite de Chernoff subgaussiano).

Funciones de velocidad exactas y límites de Chernoff para distribuciones comunes

Distribución	${\displaystyle \operatorname {E} (X)}$	${\displaystyle K(t)}$	${\displaystyle I(a)}$	${\displaystyle C(a)}$
Distribución normal	${\displaystyle 0}$	${\displaystyle {\frac {1}{2}}\sigma ^{2}t^{2}}$	${\displaystyle {\frac {1}{2}}\left({\frac {a}{\sigma }}\right)^{2}}$	${\displaystyle \exp \left({-{\frac {a^{2}}{2\sigma ^{2}}}}\right)}$
Distribución de Bernoulli (detallada a continuación)	${\displaystyle p}$	${\displaystyle \ln \left(1-p+pe^{t}\right)}$	${\displaystyle D_{KL}(a\parallel p)}$	${\displaystyle \left({\frac {p}{a}}\right)^{a}{\left({\frac {1-p}{1-a}}\right)}^{1-a}}$
Bernoulli estándar ( H es la función de entropía binaria )	${\displaystyle {\frac {1}{2}}}$	${\displaystyle \ln \left(1+e^{t}\right)-\ln(2)}$	${\displaystyle \ln(2)-H(a)}$	${\displaystyle {\frac {1}{2}}a^{-a}(1-a)^{-(1-a)}}$
Distribución de Rademacher	${\displaystyle 0}$	${\displaystyle \ln \cosh(t)}$	${\displaystyle \ln(2)-H\left({\frac {1+a}{2}}\right)}$	${\displaystyle {\sqrt {(1+a)^{-1-a}(1-a)^{-1+a}}}}$
Distribución gamma	${\displaystyle \theta k}$	${\displaystyle -k\ln(1-\theta t)}$	${\displaystyle -k\ln {\frac {a}{\theta k}}-k+{\frac {a}{\theta }}}$	${\displaystyle \left({\frac {a}{\theta k}}\right)^{k}e^{k-a/\theta }}$
Distribución de chi-cuadrado	${\displaystyle k}$	${\displaystyle -{\frac {k}{2}}\ln(1-2t)}$	${\displaystyle {\frac {k}{2}}\left({\frac {a}{k}}-1-\ln {\frac {a}{k}}\right)}$[8]	${\displaystyle \left({\frac {a}{k}}\right)^{k/2}e^{k/2-a/2}}$
Distribución de Poisson	${\displaystyle \lambda }$	${\displaystyle \lambda (e^{t}-1)}$	${\displaystyle a\ln(a/\lambda )-a+\lambda }$	${\displaystyle (a/\lambda )^{-a}e^{a-\lambda }}$

Utilizando únicamente la función generadora de momentos, se puede obtener un límite inferior para las probabilidades de cola aplicando la desigualdad de Paley-Zygmund a , lo que da como resultado: (se obtiene un límite en la cola izquierda para ). Sin embargo, a diferencia del límite de Chernoff, este resultado no es exponencialmente estricto.${\displaystyle e^{tX}}$$${\displaystyle \operatorname {P} \left(X>a\right)\geq \sup _{t>0\land M(t)\geq e^{ta}}\left(1-{\frac {e^{ta}}{M(t)}}\right)^{2}{\frac {M(t)^{2}}{M(2t)}}}$$${\displaystyle t}$

Theodosopoulos ^[9] construyó un límite inferior basado en MGF más estricto utilizando un procedimiento de inclinación exponencial .

Para distribuciones particulares (como la binomial ) a menudo se encuentran disponibles límites inferiores del mismo orden exponencial que el límite de Chernoff.

Cuando X es la suma de n variables aleatorias independientes X ₁ , ..., X _n , la función generadora de momentos de X es el producto de las funciones generadoras de momentos individuales, dando como resultado que:

${\displaystyle \Pr(X\geq a)\leq \inf _{t>0}{\frac {\operatorname {E} \left[\prod _{i}e^{t\cdot X_{i}}\right]}{e^{t\cdot a}}}=\inf _{t>0}e^{-t\cdot a}\prod _{i}\operatorname {E} \left[e^{t\cdot X_{i}}\right].}$

( 1 )

y:

${\displaystyle \Pr(X\leq a)\leq \inf _{t<0}e^{-ta}\prod _{i}\operatorname {E} \left[e^{tX_{i}}\right]}$

Los límites de Chernoff específicos se obtienen calculando la función generadora de momentos para instancias específicas de las variables aleatorias .${\displaystyle \operatorname {E} \left[e^{-t\cdot X_{i}}\right]}$${\displaystyle X_{i}}$

Cuando las variables aleatorias también se distribuyen de manera idéntica ( iid ), el límite de Chernoff para la suma se reduce a un simple reescalamiento del límite de Chernoff de una sola variable. Es decir, el límite de Chernoff para el promedio de n variables iid es equivalente a la n ésima potencia del límite de Chernoff de una sola variable (véase el teorema de Cramér ).

Los límites de Chernoff también pueden aplicarse a sumas generales de variables aleatorias independientes y acotadas, independientemente de su distribución; esto se conoce como desigualdad de Hoeffding . La prueba sigue un enfoque similar al de los otros límites de Chernoff, pero aplicando el lema de Hoeffding para acotar las funciones generadoras de momentos (véase desigualdad de Hoeffding ).

Desigualdad de Hoeffding . Supóngase que X ₁ , ..., X _n son variables aleatorias independientes que toman valores en [a,b]. Sea X su suma y μ = E[ X ] el valor esperado de la suma. Entonces, para cualquier,${\displaystyle t>0}$

${\displaystyle \Pr(X\leq \mu -t)<e^{-2t^{2}/(n(b-a)^{2})},}$

${\displaystyle \Pr(X\geq \mu +t)<e^{-2t^{2}/(n(b-a)^{2})}.}$

Los límites en las siguientes secciones para las variables aleatorias de Bernoulli se derivan utilizando que, para una variable aleatoria de Bernoulli con probabilidad p de ser igual a 1,${\displaystyle X_{i}}$

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

Se pueden encontrar muchos tipos de límites de Chernoff: la forma aditiva original (que da un límite al error absoluto ) o la forma multiplicativa más práctica (que limita el error relativo a la media).

Límite de Chernoff multiplicativo. Supongamos que X ₁ , ..., X _n son variables aleatorias independientes que toman valores en {0, 1}. Sea X su suma y μ = E[ X ] el valor esperado de la suma. Entonces, para cualquier δ > 0 ,

${\displaystyle \Pr(X\geq (1+\delta )\mu )\leq \left({\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\right)^{\mu }.}$

Se puede utilizar una estrategia de prueba similar para demostrar que para 0 < δ < 1

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

La fórmula anterior suele ser difícil de manejar en la práctica, por lo que a menudo se utilizan los siguientes límites más flexibles pero más convenientes ^[10] , que se derivan de la desigualdad de la lista de desigualdades logarítmicas :${\displaystyle \textstyle {\frac {2\delta }{2+\delta }}\leq \log(1+\delta )}$

${\displaystyle \Pr(X\geq (1+\delta )\mu )\leq e^{-\delta ^{2}\mu /(2+\delta )},\qquad 0\leq \delta ,}$

${\displaystyle \Pr(X\leq (1-\delta )\mu )\leq e^{-\delta ^{2}\mu /2},\qquad 0<\delta <1,}$

${\displaystyle \Pr(|X-\mu |\geq \delta \mu )\leq 2e^{-\delta ^{2}\mu /3},\qquad 0<\delta <1.}$

Tenga en cuenta que los límites son triviales para . ${\displaystyle \delta =0}$

Además, basándose en la expansión de Taylor para la función W de Lambert , ^[11]

${\displaystyle \Pr(X\geq R)\leq 2^{-xR},\qquad x>0,\ R\geq (2^{x}e-1)\mu .}$

El siguiente teorema se debe a Wassily Hoeffding ^[12] y por lo tanto se llama teorema de Chernoff-Hoeffding.

Teorema de Chernoff-Hoeffding. Supóngase que X ₁ , ..., X _n son variables aleatorias iid , que toman valores en {0, 1}. Sea p = E[ X ₁ ] y ε > 0 .

${\displaystyle {\begin{aligned}\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 \parallel 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 \parallel p)n}\end{aligned}}}$

dónde

${\displaystyle D(x\parallel y)=x\ln {\frac {x}{y}}+(1-x)\ln \left({\frac {1-x}{1-y}}\right)}$

es la divergencia de Kullback–Leibler entre variables aleatorias distribuidas según Bernoulli con parámetros x e y respectivamente. Si p ≥ ⁠1/2⁠ , entonces¿qué significa?${\displaystyle D(p+\varepsilon \parallel p)\geq {\tfrac {\varepsilon ^{2}}{2p(1-p)}}}$

${\displaystyle \Pr \left({\frac {1}{n}}\sum X_{i}>p+x\right)\leq \exp \left(-{\frac {x^{2}n}{2p(1-p)}}\right).}$

Se obtiene un límite más simple al relajar el teorema usando D ( p + ε || p ) ≥ 2 ε ² , lo que se deduce de la convexidad de D ( p + ε || p ) y del hecho de que

${\displaystyle {\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 Hoeffding . A veces, los límites

${\displaystyle {\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(x-y)^{2}}{2(2y+x)}},\\[6pt]D(x\parallel y)\geq {\frac {(x-y)^{2}}{2y}},&&&x\leq y,\\[6pt]D(x\parallel y)\geq {\frac {(x-y)^{2}}{2x}},&&&x\geq y\end{aligned}}}$

¿Cuáles son más fuertes para p < ⁠1/8, también se utilizan .

Los límites de Chernoff tienen aplicaciones muy útiles en el equilibrio de conjuntos y el enrutamiento de paquetes en redes dispersas .

El problema del equilibrio de conjuntos surge al diseñar experimentos estadísticos. Normalmente, al diseñar un experimento estadístico, dadas las características de cada participante en el experimento, necesitamos saber cómo dividir a los participantes en dos grupos disjuntos de modo que cada característica esté aproximadamente lo más equilibrada posible entre los dos grupos. ^[13]

Los límites de Chernoff también se utilizan para obtener límites estrictos para problemas de enrutamiento de permutación que reducen la congestión de la red al enrutar paquetes en redes dispersas. ^[13]

Los límites de Chernoff se utilizan en la teoría del aprendizaje computacional para demostrar que un algoritmo de aprendizaje es probablemente aproximadamente correcto , es decir, con alta probabilidad el algoritmo tiene un pequeño error en un conjunto de datos de entrenamiento suficientemente grande. ^[14]

Los límites de Chernoff se pueden utilizar de manera eficaz para evaluar el "nivel de robustez" de una aplicación o un algoritmo explorando su espacio de perturbaciones con aleatorización. ^[15] El uso del límite de Chernoff permite abandonar la hipótesis de perturbaciones pequeñas (la magnitud de la perturbación es pequeña), que es fuerte y en la mayoría de los casos poco realista. El nivel de robustez se puede utilizar, a su vez, para validar o rechazar una elección algorítmica específica, una implementación de hardware o la idoneidad de una solución cuyos parámetros estructurales se ven afectados por incertidumbres.

Un uso simple y común de los límites de Chernoff es para "potenciar" algoritmos aleatorios . Si uno tiene un algoritmo que genera una suposición que es la respuesta deseada con probabilidad p > 1/2, entonces uno puede obtener una tasa de éxito más alta ejecutando el algoritmo veces y generando una suposición que es generada por más de n /2 ejecuciones del algoritmo. (No puede haber más de una suposición de este tipo). Suponiendo que estas ejecuciones del algoritmo son independientes, la probabilidad de que más de n /2 de las suposiciones sean correctas es igual a la probabilidad de que la suma de las variables aleatorias independientes de Bernoulli X _k que son 1 con probabilidad p sea mayor que n /2. Esto se puede demostrar al menos a través del límite de Chernoff multiplicativo (Corolario 13.3 en las notas de clase de Sinclair, μ = np ).: ^[16]${\displaystyle n=\log(1/\delta )2p/(p-1/2)^{2}}$${\displaystyle 1-\delta }$

${\displaystyle \Pr \left[X>{n \over 2}\right]\geq 1-e^{-n\left(p-1/2\right)^{2}/(2p)}\geq 1-\delta }$

Rudolf Ahlswede y Andreas Winter introdujeron un límite de Chernoff para variables aleatorias con valores matriciales. ^[17] La ​​siguiente versión de la desigualdad se puede encontrar en el trabajo de Tropp. ^[18]

Sean M ₁ , ..., M _t variables aleatorias independientes con valores matriciales tales que y . Denotemos por la norma del operador de la matriz . Si se cumple casi con seguridad para todos , entonces para cada ε > 0${\displaystyle M_{i}\in \mathbb {C} ^{d_{1}\times d_{2}}}$${\displaystyle \mathbb {E} [M_{i}]=0}$${\displaystyle \lVert M\rVert }$${\displaystyle M}$${\displaystyle \lVert M_{i}\rVert \leq \gamma }$${\displaystyle i\in \{1,\ldots ,t\}}$

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

Nótese que para concluir que la desviación de 0 está limitada por ε con alta probabilidad, necesitamos elegir un número de muestras proporcional al logaritmo de . En general, desafortunadamente, una dependencia de es inevitable: tomemos por ejemplo una matriz de signo aleatorio diagonal de dimensión . La norma del operador de la suma de t muestras independientes es precisamente la desviación máxima entre d caminatas aleatorias independientes de longitud t . Para lograr un límite fijo en la desviación máxima con probabilidad constante, es fácil ver que t debería crecer logarítmicamente con d en este escenario. ^[19]${\displaystyle t}$${\displaystyle d_{1}+d_{2}}$${\displaystyle \log(\min(d_{1},d_{2}))}$${\displaystyle d\times d}$

El siguiente teorema se puede obtener asumiendo que M tiene rango bajo, para evitar la dependencia de las dimensiones.

Sea 0 < ε < 1 y M una matriz real simétrica aleatoria con y casi con seguridad. Supongamos que cada elemento en el soporte de M tiene como máximo rango r . ${\displaystyle \|\operatorname {E} [M]\|\leq 1}$${\displaystyle \|M\|\leq \gamma }$

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

Si es casi seguro que se cumple, entonces${\displaystyle r\leq t}$

${\displaystyle \Pr \left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}-\operatorname {E} [M]\right\|>\varepsilon \right)\leq {\frac {1}{\mathbf {poly} (t)}}}$

donde M ₁ , ..., M _t son copias iid de M .

La siguiente variante del límite de Chernoff se puede utilizar para limitar la probabilidad de que una mayoría en una población se convierta en una minoría en una muestra, o viceversa. ^[20]

Supongamos que hay una población general A y una subpoblación B  ⊆  A . Marque el tamaño relativo de la subpoblación (| B |/| A |) mediante  r .

Supongamos que elegimos un entero k y una muestra aleatoria S  ⊂  A de tamaño k . Marcamos el tamaño relativo de la subpoblación en la muestra (| B ∩ S |/| S |) mediante r _S .

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

${\displaystyle \Pr \left(r_{S}<(1-d)\cdot r\right)<\exp \left(-r\cdot d^{2}\cdot {\frac {k}{2}}\right)}$

En particular, si B es mayoría en A (es decir, r  > 0,5), podemos limitar la probabilidad de que B siga siendo mayoría en S ( r _S  > 0,5) tomando: d  = 1 − 1/(2 r ): ^[21]

${\displaystyle \Pr \left(r_{S}>0.5\right)>1-\exp \left(-r\cdot \left(1-{\frac {1}{2r}}\right)^{2}\cdot {\frac {k}{2}}\right)}$

Por supuesto, este límite no es estricto en absoluto. Por ejemplo, cuando r  = 0,5 obtenemos un límite trivial Prob > 0.

Siguiendo las condiciones del límite de Chernoff multiplicativo, sean X ₁ , ..., X _n variables aleatorias de Bernoulli independientes , cuya suma es X , cada una con probabilidad p _i de ser igual a 1. Para una variable de Bernoulli:

${\displaystyle \operatorname {E} \left[e^{t\cdot X_{i}}\right]=(1-p_{i})e^{0}+p_{i}e^{t}=1+p_{i}(e^{t}-1)\leq e^{p_{i}(e^{t}-1)}}$

Entonces, usando ( 1 ) con para cualquier y donde ,${\displaystyle a=(1+\delta )\mu }$${\displaystyle \delta >0}$${\displaystyle \mu =\operatorname {E} [X]=\textstyle \sum _{i=1}^{n}p_{i}}$

${\displaystyle {\begin{aligned}\Pr(X>(1+\delta )\mu )&\leq \inf _{t\geq 0}\exp(-t(1+\delta )\mu )\prod _{i=1}^{n}\operatorname {E} [\exp(tX_{i})]\\[4pt]&\leq \inf _{t\geq 0}\exp {\Big (}-t(1+\delta )\mu +\sum _{i=1}^{n}p_{i}(e^{t}-1){\Big )}\\[4pt]&=\inf _{t\geq 0}\exp {\Big (}-t(1+\delta )\mu +(e^{t}-1)\mu {\Big )}.\end{aligned}}}$

Si simplemente establecemos t = log(1 + δ ) de modo que t > 0 para δ > 0 , podemos sustituir y encontrar

${\displaystyle \exp {\Big (}-t(1+\delta )\mu +(e^{t}-1)\mu {\Big )}={\frac {\exp((1+\delta -1)\mu )}{(1+\delta )^{(1+\delta )\mu }}}=\left[{\frac {e^{\delta }}{(1+\delta )^{(1+\delta )}}}\right]^{\mu }.}$

Esto demuestra el resultado deseado.

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

${\displaystyle \Pr \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

${\displaystyle \left({\frac {\operatorname {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}.}$

Por lo tanto, podemos calcular fácilmente el ínfimo, utilizando el cálculo:

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

Poniendo la ecuación a cero y resolviéndola, tenemos

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

de modo que

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

De este modo,

${\displaystyle t=\log \left({\frac {(1-p)q}{(1-q)p}}\right).}$

Como q = p + ε > p , vemos que t > 0 , por lo que nuestro límite se satisface en t . Después de haber resuelto t , podemos volver a introducirlo en las ecuaciones anteriores para encontrar que

${\displaystyle {\begin{aligned}\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\parallel p).\end{aligned}}}$

Ahora tenemos el resultado deseado, que

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

Para completar la prueba del caso simétrico, simplemente definimos la variable aleatoria Y _i = 1 − X _i , aplicamos la misma prueba y la introducimos en nuestro límite.

• Desigualdades de Bernstein
• Desigualdad de concentración : un resumen de los límites de cola de las variables aleatorias.
• Teorema de Cramer
• El valor entrópico en riesgo
• Desigualdad de Hoeffding
• Matriz Chernoff limitada
• Función generadora de momentos

• 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 . JSTOR  2236576. 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 . JSTOR  2243541. MR  0614640. Zbl  0457.60014.
• Hagerup, T.; Rüb, C. (1990). "Un recorrido guiado por los límites de Chernoff". Information Processing Letters . 33 (6): 305. doi :10.1016/0020-0190(90)90214-I.
• Nielsen, F. (2011). "Una caracterización geométrica de la información de Chernoff". IEEE Signal Processing Letters . 20 (3): 269–272. arXiv : 1102.2684 . doi :10.1109/LSP.2013.2243726. S2CID  15034953.