En la teoría de la probabilidad , las desigualdades de concentración proporcionan límites sobre cómo una variable aleatoria se desvía de algún valor (normalmente, su valor esperado ). La ley de un gran número de la teoría clásica de la probabilidad establece que las sumas de variables aleatorias independientes están, en condiciones muy suaves, cercanas a su expectativa con una gran probabilidad. Estas sumas son los ejemplos más básicos de variables aleatorias concentradas alrededor de su media . Los resultados recientes muestran que tal comportamiento es compartido por otras funciones de variables aleatorias independientes.
Las desigualdades de concentración se pueden clasificar de acuerdo con la cantidad de información sobre la variable aleatoria que se necesita para usarlas.
La desigualdad de Markov
Dejar ser una variable aleatoria que no sea negativa ( casi con seguridad ). Entonces, por cada constante,
Tenga en cuenta la siguiente extensión de la desigualdad de Markov: si es una función estrictamente creciente y no negativa, entonces
La desigualdad de Chebyshev
La desigualdad de Chebyshev requiere la siguiente información sobre una variable aleatoria :
- El valor esperado es finito.
- La varianza es finito.
Entonces, por cada constante ,
o equivalente,
dónde es la desviación estándar de.
La desigualdad de Chebyshev puede verse como un caso especial de la desigualdad de Markov generalizada aplicada a la variable aleatoria con .
Desigualdad de Vysochanskij-Petunin
Desigualdad de Paley-Zygmund
La desigualdad de Cantelli
La desigualdad de Gauss
Límites de Chernoff
El límite de Chernoff genérico [1] : 63–65 requiere solo la función generadora de momento de, definido como: , siempre que exista. Basado en la desigualdad de Markov, para cada:
y por cada :
Hay varios límites de Chernoff para diferentes distribuciones y diferentes valores del parámetro . Consulte [2] : 5–7 para obtener una recopilación de más desigualdades de concentración.
Límites en sumas de variables independientes
Dejar ser variables aleatorias independientes tales que, para todo i :
Dejar ser su suma, su valor esperado y su varianza:
A menudo es interesante acotar la diferencia entre la suma y su valor esperado. Se pueden utilizar varias desigualdades.
1. La desigualdad de Hoeffding dice que:
2. La variable aleatoria es un caso especial de martingala , y. Por lo tanto, la forma general de la desigualdad de Azuma también se puede usar y produce un límite similar:
Esta es una generalización de Hoeffding ya que puede manejar otros tipos de martingalas, así como supermartingales y submartingales . Tenga en cuenta que si se usa la forma más simple de la desigualdad de Azuma, el exponente en el límite es peor por un factor de 4.
3. La función de suma, , es un caso especial de una función de n variables. Esta función cambia de forma acotada: si se cambia la variable i , el valor de f cambia como máximo. Por lo tanto, la desigualdad de McDiarmid también se puede usar y produce un límite similar:
Esta es una generalización diferente de la de Hoeffding, ya que puede manejar otras funciones además de la función de suma, siempre que cambien de forma acotada.
4. desigualdad de Bennett ofrece algunas mejoras con respecto Hoeffding es cuando las varianzas de los sumandos son pequeñas en comparación con su casi segura de los límites C . Dice que:
- dónde
5. La primera de las desigualdades de Bernstein dice que:
Esta es una generalización de Hoeffding, ya que puede manejar variables aleatorias no solo con un límite casi seguro, sino con un límite casi seguro y con un límite de varianza.
6. Los límites de Chernoff tienen una forma particularmente simple en el caso de la suma de variables independientes, ya que .
Por ejemplo, [3] suponga que las variables satisfacer , por . Entonces tenemos una desigualdad de cola más baja:
Si satisface , tenemos desigualdad de cola superior:
Si son iid, y es la varianza de , una versión típica de la desigualdad de Chernoff es:
7. Se pueden encontrar límites similares en: Distribución de Rademacher # Límites en sumas
Desigualdad Efron-Stein
La desigualdad de Efron-Stein (o desigualdad de influencia, o límite de MG en la varianza) limita la varianza de una función general.
Suponer que , son independientes con y teniendo la misma distribución para todos .
Dejar Luego
Desigualdad de Dvoretzky – Kiefer – Wolfowitz
La desigualdad de Dvoretzky-Kiefer-Wolfowitz delimita la diferencia entre la función de distribución acumulativa real y empírica .
Dado un número natural , dejar Ser variables aleatorias independientes de valor real e idénticamente distribuidas con función de distribución acumulativa F (·). Dejar denotar la función de distribución empírica asociada definida por
Entonces es la probabilidad de que una sola variable aleatoria es más pequeña que , y es el número promedio de variables aleatorias que son menores que.
Luego
Desigualdades anti-concentración
Las desigualdades anti-concentración , por otro lado, proporcionan un límite superior sobre cuánto puede concentrarse una variable aleatoria alrededor de una cantidad.
Por ejemplo, Rao y Yehudayoff [4] muestran que existen algunos tal que, para la mayoría de direcciones del hipercubo , lo siguiente es cierto:
dónde se extrae uniformemente de un subconjunto de tamaño suficientemente grande.
Estas desigualdades son importantes en varios campos, incluida la complejidad de la comunicación ( por ejemplo , en las pruebas del problema de Hamming de la brecha [5] ) y la teoría de grafos . [6]
Se puede obtener una desigualdad anti-concentración interesante para sumas ponderadas de variables aleatorias independientes de Rademacher utilizando las desigualdades de Paley-Zygmund y Khintchine . [7]
Referencias
- ^ Mitzenmacher, Michael; Upfal, Eli (2005). Probabilidad y computación: algoritmos aleatorios y análisis probabilístico . Prensa de la Universidad de Cambridge. ISBN 0-521-83540-2.
- ^ Slagle, NP (2012). "Cien estadísticas y desigualdades de probabilidad" (PDF) .
- ^ Chung, Fan ; Lu, Linyuan (2010). "Antiguas y nuevas desigualdades de concentración" (PDF) . Gráficos y redes complejas . Sociedad Matemática Estadounidense . Consultado el 14 de agosto de 2018 .
- ^ Rao, Anup; Yehudayoff, Amir (2018). "Anti-concentración en la mayoría de las direcciones" . Coloquio electrónico sobre complejidad computacional.
- ^ Sherstov, Alexander A. (2012). "La complejidad de la comunicación de la distancia de Gap Hamming" . Teoría de la Computación .
- ^ Matthew Kwan; Benny Sudakov; Tuan Tran (2018). "Anticoncentración para estadísticas de subgrafos". Revista de la Sociedad Matemática de Londres . 99 (3): 757–777. arXiv : 1807.05202 . Código bibliográfico : 2018arXiv180705202K . doi : 10.1112 / jlms.12192 . S2CID 54065186 .
- ^ Veraar, Mark (2009). "Sobre las desigualdades de Khintchine con un peso". arXiv : 0909.2586v1 [ math.PR ].
enlaces externos
Karthik Sridharan, " Una suave introducción a las desigualdades de concentración " - Universidad de Cornell