En la teoría de la probabilidad , el límite de Chernoff , llamado así por Herman Chernoff pero debido a Herman Rubin, [1] da límites exponencialmente decrecientes en las distribuciones de cola de sumas de variables aleatorias independientes. Es un límite más agudo que los límites de cola conocidos 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, el límite de Chernoff requiere que las variables sean independientes, una condición que ni la desigualdad de Markov ni la desigualdad de Chebyshev requieren, aunque la desigualdad de Chebyshev requiere que las variables sean independientes por pares.
El límite de Chernoff genérico para una variable aleatoria X se obtiene aplicando la desigualdad de Markov a e tX . [2] Por cada:
Cuando X es la suma de n variables aleatorias X 1 , ..., X n , obtenemos para cualquier t > 0,
En particular, optimizando sobre t y asumiendo que X i son independientes, obtenemos,
( 1 )
Similar,
y entonces,
Los límites de Chernoff específicos se obtienen calculando para instancias específicas de las variables básicas .
Ejemplo
Sean X 1 , ..., X n variables aleatorias de Bernoulli independientes , cuya suma es X , cada una con probabilidad p > 1/2 de ser igual a 1. Para una variable de Bernoulli:
Entonces:
Para cualquier , tomando y da:
y
y el límite de Chernoff genérico da:
La probabilidad de ocurrencia simultánea de más de n / 2 de los eventos { X k = 1} tiene un valor exacto:
Se puede calcular un límite inferior de esta probabilidad en función de la desigualdad de Chernoff:
De hecho, al notar que μ = np , obtenemos por la forma multiplicativa del límite de Chernoff (ver más abajo o el Corolario 13.3 en las notas de clase de Sinclair), [3]
Este resultado admite varias generalizaciones como se describe a continuación. Uno puede 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 en relación con la media).
Forma aditiva (error absoluto)
El siguiente teorema se debe a Wassily Hoeffding [4] y, por lo tanto, se denomina teorema de Chernoff-Hoeffding.
Teorema de Chernoff-Hoeffding. Suponga que X 1 , ..., X n son variables aleatorias iid , que toman valores en {0, 1}. Sea p = E [ X 1 ] y ε > 0 .
que son más fuertes para p < 1/8, también se utilizan.
Forma multiplicativa (error relativo)
Límite de Chernoff multiplicativo. Suponga que X 1 , ..., 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 ,
Se puede utilizar una estrategia de prueba similar para demostrar que
La fórmula anterior a menudo es difícil de manejar en la práctica, [5] por lo que a menudo se usan los siguientes límites más flexibles pero más convenientes:
El problema de equilibrio de conjuntos surge al diseñar experimentos estadísticos. Por lo general, 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 sea lo más equilibrada posible entre los dos grupos. [6]
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 mientras se enrutan paquetes en redes dispersas. [6]
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. [8] El uso del límite 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, a su vez, usarse 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.
Vinculado a la matriz
Rudolf Ahlswede y Andreas Winter introdujeron una cota de Chernoff para variables aleatorias con valores matriciales. [9] La siguiente versión de la desigualdad se puede encontrar en el trabajo de Tropp. [10]
Sean M 1 , ..., M t variables aleatorias con valores de matriz independientes tales que y . Denotemos por la norma del operador de la matriz . Si es casi seguro para todos , entonces para cada ε > 0
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, una dependencia de es inevitable: tome, por ejemplo, una matriz diagonal de signo aleatorio de dimensión . 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. [11]
El siguiente teorema se puede obtener asumiendo 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 seguro. Suponga que cada elemento en el soporte de M tiene como máximo rango r . Colocar
Si se sostiene casi con seguridad, entonces
donde M 1 , ..., M t son copias de iid M .
Teorema con matrices que no son completamente aleatorias
Garg, Lee, Song y Srivastava [12] demostraron una cota de tipo Chernoff para sumas de variables aleatorias con valores matriciales muestreadas mediante una caminata aleatoria en un expansor, lo que confirma una conjetura de Wigderson y Xiao.
Kyng y Song [13] demostraron una cota de tipo Chernoff para sumas de matriz laplaciana de árboles de expansión aleatorios.
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. [14]
Supongamos que hay una población general A y una sub-población B ⊆ A . Marque el tamaño relativo de la subpoblación (| B | / | A |) con 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 sub-población en la muestra (| B ∩ S | / | S |) por r S .
Entonces, para cada fracción d ∈ [0,1]:
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 ): [15 ]
Este límite, por supuesto, no es para nada estrecho. Por ejemplo, cuando r = 0.5 obtenemos un límite trivial Prob > 0.
Pruebas
Teorema de Chernoff-Hoeffding (forma aditiva)
Sea q = p + ε . Tomando a = nq en ( 1 ), obtenemos:
Ahora, sabiendo que Pr ( X i = 1) = p , Pr ( X i = 0) = 1 - p , tenemos
Por lo tanto, podemos calcular fácilmente el mínimo, usando cálculo:
Poniendo la ecuación a cero y resolviendo, tenemos
así que eso
Por lo tanto,
Como q = p + ε > p , vemos que t > 0 , por lo que nuestro límite se satisface en t . Habiendo resuelto para t , podemos volver a conectar las ecuaciones anteriores para encontrar que
Ahora tenemos nuestro resultado deseado, que
Para completar la prueba del caso simétrico, simplemente definimos la variable aleatoria Y i = 1 - X i , aplicamos la misma prueba y la conectamos a nuestro límite.
La tercera línea de arriba sigue porque toma el valor e t con probabilidad p i y el valor 1 con probabilidad 1 - p i . Esto es idéntico al cálculo anterior en la demostración del teorema para la forma aditiva (error absoluto) .
Reescritura como y recordando que (con desigualdad estricta si x > 0 ), establecemos. El mismo resultado se puede obtener reemplazando directamente a en la ecuación para el límite de Chernoff con (1 + δ ) μ . [dieciséis]
Por lo tanto,
Si simplemente establecemos t = log (1 + δ ) de modo que t > 0 para δ > 0 , podemos sustituir y encontrar
Esto prueba el resultado deseado.
Ver también
Desigualdad de concentración : un resumen de los límites de cola de las variables aleatorias.
Valor entrópico en riesgo
Referencias
^ 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 . Prensa CRC. pag. 35. ISBN 9781482204964.
^ Este método fue aplicado por primera vez por Sergei Bernstein para probar las desigualdades de Bernstein relacionadas.
^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 .
^Hoeffding, W. (1963). "Desigualdades de probabilidad para las 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 .
^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.
^ a b Consulte la sección de este libro para obtener más información sobre el problema.
^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.
^Alippi, C. (2014). "Algoritmos aleatorios". Inteligencia para sistemas integrados . Saltador. ISBN 978-3-319-05278-6.
^Ahlswede, R .; Invierno, A. (2003). "Converse fuerte para la identificación a través de canales cuánticos". Transacciones IEEE sobre teoría de la información . 48 (3): 569–579. arXiv : quant-ph / 0012127 . doi : 10.1109 / 18.985947 .
^Tropp, J. (2010). "Límites de cola fáciles de usar para sumas de matrices aleatorias". Fundamentos de la matemática computacional . 12 (4): 389–434. arXiv : 1004.4389 . doi : 10.1007 / s10208-011-9099-z .
^Magen, A .; Zouzias, A. (2011). "Límites de Chernoff con valores de matriz de bajo rango y multiplicación aproximada de la matriz". arXiv : 1005,2724 [ cs.DM ].
^Garg, Ankit; Lee, Yin Tat; Song, Zhao; Srivastava, Nikhil (2018). Un expansor de matriz Chernoff Bound . STOC '18 Actas del 50 simposio anual ACM sobre Teoría de la Computación. arXiv : 1704.03864 .
^Kyng, Rasmus; Canción, Zhao (2018). Una matriz Chernoff enlazada para distribuciones fuertemente Rayleigh y esparsificadores espectrales de unos pocos árboles de expansión aleatorios . Simposio FOCS '18 IEEE sobre fundamentos de la informática. arXiv : 1810.08345 .
^Goldberg, AV; Hartline, JD (2001). "Subastas competitivas para múltiples bienes digitales". Algoritmos - ESA 2001 . Apuntes de conferencias en Ciencias de la Computación. 2161 . pag. 416. CiteSeerX 10.1.1.8.5115 . doi : 10.1007 / 3-540-44676-1_35 . ISBN 978-3-540-42493-2.; lema 6.1
^ 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 .
^ Consulte la prueba anterior
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 .; Rüb, 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). "Información de Chernoff de familias exponenciales". arXiv : 1102.2684 [ cs.IT ].