Chernoff atado

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

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 .

Límites genéricos de Chernoff

Límite de Chernoff bilateral para una variable aleatoria de chi-cuadrado

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 : ${\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 se cumple para cada positivo , podemos tomar el ínfimo : ${\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 puede expresarse 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 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 \operatorname {E} (X)}$ ${\displaystyle a\geq \operatorname {E} (X)}$ $${\displaystyle C(a)=\inf _{t}M(t)e^{-ta}}$$ ${\displaystyle 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(\operatorname {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).

Límites inferiores del MGF

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.

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 como resultado 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 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 ).

Sumas de variables aleatorias independientes y acotadas

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

Sumas de variables aleatorias independientes de Bernoulli

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

Forma multiplicativa (error relativo)

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

Forma aditiva (error absoluto)

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 .

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

Matriz Chernoff limitada

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.

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

Variante de muestreo

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.

Pruebas

Forma multiplicativa

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.

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

Véase también

• 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

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: Oxford University Press. p. 21. ISBN 978-0-19-953525-5.OCLC 837517674  .
2. Wainwright, M. (22 de enero de 2015). "Límites básicos de concentración y cola" (PDF) . Archivado (PDF) desde el original el 8 de mayo de 2016.
3. Vershynin, Roman (2018). Probabilidad de alta dimensión: una introducción con aplicaciones en la ciencia de datos. Cambridge, Reino Unido. p. 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). "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". Anales de 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, Christian; Banks, David L.; Molenberghs, Geert; Scott, David W.; Wang, Jane-Ling (eds.). Pasado, presente y futuro de la estadística. CRC Press. pág. 35. ISBN 9781482204964. Archivado desde el original (PDF) el 11 de febrero de 2015.
7. Philips, Thomas K.; Nelson, Randolph (1995). "El límite de momento es más estricto que el límite de Chernoff para probabilidades de cola positiva". The American Statistician . 49 (2): 175–178. doi :10.2307/2684633. ISSN  0003-1305. JSTOR  2684633.
8. Ghosh, Malay (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. Theodosopoulos, Ted (1 de marzo de 2007). "Una reversión del límite de Chernoff". Statistics & Probability Letters . 77 (5): 558–565. arXiv : math/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. Cambridge University Press. ISBN 978-0-521-83540-4.
11. Dillencourt, Michael; Goodrich, Michael; Mitzenmacher, Michael (2024). "Aprovechamiento de límites de Chernoff parametrizados para análisis de algoritmos simplificados". Cartas de procesamiento de información . 187 (106516). doi : 10.1016/j.ipl.2024.106516 .
12. 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.
13. Consulte esta sección del libro para obtener más información sobre el problema.
14. Kearns, M.; Vazirani, U. (1994). Introducción a la teoría del aprendizaje computacional . MIT Press. Capítulo 9 (Apéndice), páginas 190-192. ISBN 0-262-11193-4.
15. Alippi, C. (2014). "Algoritmos aleatorios". Inteligencia para sistemas integrados . Springer. ISBN 978-3-319-05278-6.
16. Sinclair, Alistair (otoño de 2011). «Apuntes de clase para el curso «Aleatoriedad y computación»» (PDF) . Archivado desde el original (PDF) el 31 de octubre de 2014. Consultado el 30 de octubre de 2014 .
17. Ahlswede, R.; Winter, A. (2003). "Conversación fuerte para identificación a través de canales cuánticos". IEEE Transactions on Information Theory . 48 (3): 569–579. arXiv : quant-ph/0012127 . doi :10.1109/18.985947. S2CID  523176.
18. Tropp, J. (2010). "Límites de cola fáciles de usar para sumas de matrices aleatorias". Fundamentos de las matemáticas computacionales . 12 (4): 389–434. arXiv : 1004.4389 . doi :10.1007/s10208-011-9099-z. S2CID  17735965.
19. Magen, A. ; Zouzias, A. (2011). "Límites de Chernoff con valores matriciales de rango bajo y multiplicación de matrices aproximada". arXiv : 1005.2724 [cs.DM].
20. Goldberg, AV; Hartline, JD (2001). "Subastas competitivas para múltiples bienes digitales". Algoritmos — ESA 2001. Apuntes de clase en 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
21. Ver gráficos de: el límite en función de r cuando k cambia y el límite en función de k cuando r cambia.

Lectura adicional

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