Chernoff obligado

Límites exponencialmente decrecientes en distribuciones de cola de variables aleatorias

En teoría de la probabilidad , un límite de Chernoff es un límite superior exponencialmente decreciente en la cola de una variable aleatoria en función de su función generadora de momentos . El mínimo de todos estos límites exponenciales forma el límite de Chernoff o 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 sumas de variables aleatorias de Bernoulli . ^{[3] [4]}

La encuadernación lleva 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 que ahora se conoce como teorema de Cramér .

Es un límite más definido 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 la desintegración 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 es requerida ni por la desigualdad de Markov ni por 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 .

Límites genéricos de Chernoff

Chernoff bilateral ligado a una variable aleatoria chi-cuadrado

La cota genérica de Chernoff para una variable aleatoria se logra aplicando la desigualdad de Markov (razón por la cual a veces se la llama cota exponencial de Markov o cota de momentos exponenciales ). De manera positiva, esto da un límite en la cola derecha de en términos de su función generadora de momento : ${\displaystyle X}$ ${\displaystyle e^{tX}}$ ${\displaystyle t}$ ${\displaystyle X}$ ${\displaystyle M(t)=\operatorname {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 es válido para todo positivo , podemos tomar el mínimo : ${\displaystyle 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 : ${\displaystyle 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 se puede expresar como valor esperado o equivalente . ${\displaystyle M(t)e^{-ta}}$ ${\displaystyle \operatorname {E} (e^{tX})e^{-ta}}$ ${\displaystyle \operatorname {E} (e^{t(X-a)})}$

Propiedades

La función exponencial es convexa, por lo que según la desigualdad de Jensen . De ello se deduce que el límite en la cola derecha es mayor o igual a uno cuando , y por tanto trivial; de manera similar, el límite izquierdo es trivial para . Por lo tanto, podemos combinar los dos ínfima y definir el límite de Chernoff de dos caras: ${\displaystyle \operatorname {E} (e^{tX})\geq e^{t\operatorname {E} (X)}}$ ${\displaystyle a\leq \operatorname {E} (X)}$ ${\displaystyle a\geq \operatorname {E} (X)}$

$${\displaystyle C(a)=\inf _{t}M(t)e^{-ta}}$$

función de distribución acumulativa ${\displaystyle X}$

El logaritmo de la cota de Chernoff bilateral se conoce como función de velocidad (o transformada de Cramér ) . Es equivalente a la transformada de Legendre-Fenchel o conjugada convexa de la función generadora acumulativa , definida como: ${\displaystyle I=-\log C}$ ${\displaystyle K=\log M}$

$${\displaystyle I(a)=\sup _{t}at-K(t)}$$

función generadora de momentoslog-convexalog-cóncavo ${\displaystyle C(\operatorname {E} (X))=1}$ ${\textstyle C_{X+k}(a)=C_{X}(a-k)}$

La cota de Chernoff es exacta si y sólo si se trata de una única masa concentrada ( distribución degenerada ). El límite es estricto sólo en o más allá de los extremos de una variable aleatoria acotada, donde los ínfimas se alcanzan para infinito . Para las variables aleatorias ilimitadas, el límite no es ajustado en ninguna parte, aunque sí es asintóticamente ajustado hasta factores subexponenciales ("exponencialmente ajustados"). ^{[ cita necesaria ]} 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 de Chernoff exacto puede ser difícil de manejar o difícil de evaluar analíticamente, en cuyo caso se puede utilizar en su lugar un límite superior adecuado de la función generadora de momento (o acumulante) (por ejemplo, un CGF subparabólico que proporcione un límite de Chernoff subgaussiano). ).

Límites inferiores del MGF

Utilizando únicamente la función generadora de momentos, se puede obtener un límite inferior de las probabilidades de cola aplicando la desigualdad de Paley-Zygmund a , obteniendo: ${\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 ajustado) utilizando un procedimiento de inclinación exponencial .

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

Sumas de variables aleatorias independientes

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 que:

y:

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

Los límites específicos de Chernoff se logran 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 están distribuidas de manera idéntica ( iid ), el límite de Chernoff para la suma se reduce a un simple cambio de escala del límite de Chernoff de una sola variable. Es decir, el límite de Chernoff para el promedio de n iid variables es equivalente a la enésima potencia del límite de Chernoff en una sola variable (ver teorema de Cramér ).

Sumas de variables aleatorias acotadas independientes

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

La desigualdad de Hoeffding . Supongamos que X ₁ , ..., X _n son variables aleatorias independientes que toman valores en [a,b]. Sea X su suma y sea μ = E[ X ] el valor esperado de la suma. Entonces para cualquiera, ${\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})}.}$

Sumas de variables aleatorias independientes de Bernoulli

Los límites en las siguientes secciones para las variables aleatorias de Bernoulli se derivan usando eso, 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).

Forma multiplicativa (error relativo)

Encuadernación multiplicativa de Chernoff. Supongamos que X ₁ , ..., X _n son variables aleatorias independientes que toman valores en {0, 1}. Sea X su suma y sea μ = 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.}$

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

Forma aditiva (error absoluto)

El siguiente teorema se debe a Wassily Hoeffding ^[11] y por eso se denomina teorema de Chernoff-Hoeffding.

Teorema de Chernoff-Hoeffding. Supongamos 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 de Bernoulli con parámetros x e y respectivamente. Si p ≥1/2, entonces que 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 una cota más simple relajando el teorema usando D ( p + ε || p ) ≥ 2 ε ² , que se sigue de la convexidad de D ( p + ε || p ) y el 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}}}$

que son más fuertes para p <1/8, también se utilizan.

Aplicaciones

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 2 grupos separados de modo que cada característica esté lo más equilibrada posible entre los dos grupos. ^[12]

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

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

Los límites de Chernoff se pueden utilizar eficazmente para evaluar el "nivel de robustez" de una aplicación/algoritmo explorando su espacio de perturbación con aleatorización. ^[14] El uso de la cota de Chernoff permite abandonar la hipótesis de la pequeña perturbación fuerte (y en su mayoría poco realista) (la magnitud de la perturbación es pequeña). El nivel de robustez puede utilizarse, 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 "impulsar" algoritmos aleatorios . Si uno tiene un algoritmo que genera una suposición que es la respuesta deseada con probabilidad p > 1/2, entonces se puede obtener una mayor tasa de éxito ejecutando el algoritmo varias veces y generando una suposición que se genera en más de n /2 ejecuciones de el algoritmo. (No puede haber más de una suposición). Suponiendo que estas ejecuciones de algoritmos 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 es mayor que n /2. Se puede demostrar que esto es al menos a través del límite multiplicativo de Chernoff (Corolario 13.3 en las notas de clase de Sinclair, μ = np ).: ^[15] ${\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 }$

Matrix Chernoff obligado

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

Sean M ₁ , ..., M _t variables aleatorias independientes valoradas en matrices tales que y . Denotemos por la norma del operador de la matriz . Si es casi seguro que se cumple 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).}$

Observe que para concluir que la desviación de 0 está limitada por ε con alta probabilidad, debemos elegir un número de muestras proporcional al logaritmo de . En general, desafortunadamente, la dependencia es inevitable: tomemos, por ejemplo, una matriz de dimensión de signo aleatorio diagonal . La norma del operador de la suma de t muestras independientes es precisamente la desviación máxima entre d paseos aleatorios 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. ^[18] ${\displaystyle t}$ ${\displaystyle d_{1}+d_{2}}$ ${\displaystyle \log(\min(d_{1},d_{2}))}$ ${\displaystyle d\times d}$

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

Teorema sin dependencia de las dimensiones.

Sea 0 < ε < 1 y M una matriz real simétrica aleatoria con y casi con seguridad. Supongamos que cada elemento sobre el soporte de M tiene como máximo rango r . Colocar ${\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, 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 .

Variante de muestreo

La siguiente variante de la cota de Chernoff se puede utilizar para acotar la probabilidad de que una mayoría en una población se convierta en minoría en una muestra, o viceversa. ^[19]

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 |) por  r .

Supongamos que elegimos un número entero k y una muestra aleatoria S  ⊂  A de tamaño k . Marque el tamaño relativo de la subpoblación en la muestra (| B ∩ S |/| S |) por 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 ): ^{[20 ]}

${\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 nada estricto. Por ejemplo, cuando r  = 0,5 obtenemos una cota trivial Prob > 0.

Pruebas

forma multiplicativa

Siguiendo las condiciones de la cota multiplicativa de Chernoff, sean X ₁ , ..., X _n variables aleatorias independientes de Bernoulli , 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 for any 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 prueba el resultado deseado.

Teorema de Chernoff-Hoeffding (forma aditiva)

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 mínimo usando 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 resolviendo, 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 nuestra cota se satisface en t . Habiendo resuelto t , podemos volver a 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 para el caso simétrico, simplemente definimos la variable aleatoria Y _i = 1 − X _i , aplicamos la misma prueba y la insertamos en nuestro límite.

Ver también

• Desigualdades de Bernstein
• Desigualdad de concentración : un resumen de los límites finales de variables aleatorias.
• teorema de cramer
• Valor entrópico en riesgo
• La desigualdad de Hoeffding
• Matrix Chernoff obligado
• Función generadora de momento

Referencias

1. Boucheron, Stéphane (2013). Desigualdades de concentración: una teoría no asintótica de la independencia. Gábor Lugosi, Pascal Massart. Oxford: Prensa de la Universidad de Oxford. pag. 21.ISBN​ 978-0-19-953525-5. OCLC  837517674.
2. Wainwright, M. (22 de enero de 2015). "Límites básicos de cola y concentración" (PDF) . Archivado (PDF) desde el original el 8 de mayo de 2016.
3. Vershynin, romano (2018). Probabilidad de alta dimensión: una introducción con aplicaciones en ciencia de datos. Cambridge, Reino Unido. pag. 19.ISBN​ 978-1-108-41519-4. OCLC  1029247498.{{cite book}}: CS1 maint: location missing publisher (link)
4. Tropp, Joel A. (26 de mayo de 2015). "Una introducción a las desigualdades de concentración de matrices". Fundamentos y tendencias en aprendizaje automático . 8 (1–2): 60. arXiv : 1501.01571 . doi :10.1561/2200000048. ISSN  1935-8237. S2CID  5679583.
5. Chernoff, Herman (1952). "Una medida de eficiencia asintótica para pruebas de una hipótesis basada en la suma de observaciones". Los anales de la estadística matemática . 23 (4): 493–507. doi : 10.1214/aoms/1177729330 . ISSN  0003-4851. JSTOR  2236576.
6. Chernoff, Herman (2014). "Una carrera en estadística" (PDF) . En Lin, Xihong; Genest, cristiano; Bancos, David L.; Molenberghs, Geert; Scott, David W.; Wang, Jane-Ling (eds.). Pasado, presente y futuro de la estadística. Prensa CRC. pag. 35.ISBN​ 9781482204964. Archivado desde el original (PDF) el 11 de febrero de 2015.
7. Philips, Thomas K.; Nelson, Randolph (1995). "El límite del momento es más estricto que el límite de Chernoff para las probabilidades de cola positivas". El estadístico estadounidense . 49 (2): 175-178. doi :10.2307/2684633. ISSN  0003-1305. JSTOR  2684633.
8. Ghosh, malayo (4 de marzo de 2021). "Límites de cola exponenciales para variables aleatorias de chi cuadrado". Revista de teoría y práctica estadística . 15 (2): 35. doi : 10.1007/s42519-020-00156-x . ISSN  1559-8616. S2CID  233546315.
9. Teodosopoulos, Ted (1 de marzo de 2007). "Una reversión del límite de Chernoff". Cartas de estadística y probabilidad . 77 (5): 558–565. arXiv : matemáticas/0501360 . doi :10.1016/j.spl.2006.09.003. ISSN  0167-7152. S2CID  16139953.
10. Mitzenmacher, Michael; Upfal, Eli (2005). Probabilidad y Computación: Algoritmos Aleatorios y Análisis Probabilístico. Prensa de la Universidad de Cambridge. ISBN 978-0-521-83540-4.
11. 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. JSTOR  2282952.
12. Consulte la sección de este libro para obtener más información sobre el problema.
13. Kearns, M.; Vazirani, U. (1994). Una introducción a la teoría del aprendizaje computacional . Prensa del MIT. Capítulo 9 (Apéndice), páginas 190–192. ISBN 0-262-11193-4.
14. Alippi, C. (2014). "Algoritmos aleatorios". Inteligencia para Sistemas Embebidos . Saltador. ISBN 978-3-319-05278-6.
15. Sinclair, Alistair (otoño de 2011). «Apuntes de clase del curso “Aleatoriedad y Computación”» (PDF) . Archivado desde el original (PDF) el 31 de octubre de 2014 . Consultado el 30 de octubre de 2014 .
16. Ahlswede, R.; Invierno, A. (2003). "Conversación fuerte para 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. S2CID  523176.
17. Tropp, J. (2010). "Límites finales fáciles de usar para sumas de matrices aleatorias". Fundamentos de la Matemática Computacional . 12 (4): 389–434. arXiv : 1004.4389 . doi :10.1007/s10208-011-9099-z. S2CID  17735965.
18. Magen, A .; Zouzias, A. (2011). "Límites de Chernoff con valor matricial de rango bajo y multiplicación aproximada de matrices". arXiv : 1005.2724 [cs.DM].
19. Goldberg, AV; Hartline, JD (2001). "Subastas competitivas para múltiples productos digitales". Algoritmos: ESA 2001 . Apuntes de conferencias sobre informática. vol. 2161. pág. 416. CiteSeerX 10.1.1.8.5115 . doi :10.1007/3-540-44676-1_35. ISBN  978-3-540-42493-2.; lema 6.1
20. Ver gráficas de: el límite en función de r cuando k cambia y el límite en función de k cuando r cambia.

Otras lecturas

• 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. SEÑOR  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. SEÑOR  0614640. Zbl  0457.60014.
• Hagerup, T.; Rub, C. (1990). "Una visita guiada a 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). "Una caracterización información-geométrica de la información de Chernoff". Cartas de procesamiento de señales IEEE . 20 (3): 269–272. arXiv : 1102.2684 . doi :10.1109/LSP.2013.2243726. S2CID  15034953.