Abrir menú principal

En la teoría de probabilidad, las Cotas de Chernoff fueron nombradas luego de su presentación por Herman Chernoff y, gracias a Herman Rubin,[1]​ se dieron cotas exponencialmente decrecientes para las distribuciones de sumas de variables aleatorias independientes. Son una cota más fina que las conocidas cotas basadas en el primer y segundo momento tales como la inecuación de Markov o la inecuación de Chebyshev, las cuales solo obtienen cotas de nivel exponencial cuando la distribución decrece. Sin embargo, las cotas de Chernoff requieren que las variables sean independientes - una condición que ni las inecuaciones de Markov ni de Chebyshev requieren.

Están relacionadas a las (antecesoras históricas) inecuaciones de Bernstein, y a la inecuación de Hoeffding.

EjemploEditar

Sean X1, ..., Xn variables aleatorias independientes que distribuyen Bernoulli, cada una con probabilidad p > 1/2 de ser igual a 1. Entonces la probabilidad de la ocurrencia simultánea de más de n/2 de los eventos {Xk = 1} tiene un valor exacto S, donde

 

La cota de Chernoff muestra que S tiene la siguiente cota inferior:

 

En efecto, notando que μ = np, lo cual obtenemos por la forma multiplicativa de las cotas de Chernoff (ver más abajo o el Corolario 13.3 en las notas de clases de Sinclair),[2]

 

Estas cotas admiten varias generalizaciones como se señala más abajo. Podemos encontrar varias representaciones de las cotas de Chernoff: la original forma aditiva (la cual da una cota para el error absoluto) o la más práctica forma multiplicativa (la cual da una cota del error relativo para la esperanza).

Primer paso para probar las cotas de ChernoffEditar

Las cotas de Chernoff para una variable aleatoria X, la cual es la suma de n variables aleatorias independientes X1, ..., Xn, se obtienen al aplicar etX para algún t bien elegido. Este método fue aplicado por primera vez por Sergei Bernstein para probar las relacionadas inecuaciones de Bernstein.

De la inecuación de Markov y usando la independencia podemos llegar a la siguiente inecuación:

Para cualquier t > 0,

 

En particular optimizando sobre t y usando la independencia de Xi obtenemos,

|   (1)

Similarmente,

 

y también,

 

Definiciones precisas y demostracionesEditar

Teorema para la forma aditiva (error absoluto)Editar

El siguiente teorema fue anunciado por Wassily Hoeffding y por esto es llamado el teorema Chernoff-Hoeffding.

Teorema Chernoff-Hoeffding. Supón que X1, ..., Xn son variables aleatorias igualmente distribuidas, tomando valores en {0, 1}. Sea p = E[Xi] y ε > 0. Entonces
 
donde
 
es la divergencia Kullback–Leibler entre dos variables aleatorias que distribuyen Bernoulli con parámetros x y y respectivamente. Si p1/2, entonces
 

DemostraciónEditar

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

 

Luego, conociendo que Pr(Xi = 1) = p, Pr(Xi = 0) = 1 − p, tenemos que

 

Por lo tanto podemos computar fácilmente el ínfimo, usando cálculo:

 

Igualando la ecuación a 0 y resolviéndola, tenemos

 

entonces

 

Por lo que,

 

Como q = p + ε > p, vemos que t > 0, por lo cual nuestra cota se satisface para t. Luego de resolverlo para t, podemos sustituir en las ecuaciones anteriores para llegar a que

 

Ahora tenemos el resultado deseado, que

 

Para completar la demostración para el caso simétrico, simplemente definimos la variable aleatoria Yi = 1 − Xi, aplicamos la misma demostración, y sustituímos en nuestra cota.

Cotas más simplesEditar

Una cota más simple se obtiene al relajar el teorema usando D(p + x || p) ≥ 2x2, debido a que D(p + x || p) es convexo y al hecho de que

 

Este resultado es un caso especial de la inecuación de Hoeffding. En algunas ocasiones, la cota

 

la cual es más fuerte para p < 1/8, es también usada.

Teorema para la forma multiplicativa de las cotas de Chernoff (error relativo)Editar

Cota de Chernoff Multiplicativa. Supón que X1, ..., Xn son variables aleatorias independientes tomando valores en {0, 1}. Sea X la variable que denota su suma y μ = E[X] la suma de los valores esperados. Entonces para todo δ > 0,
 

DemostraciónEditar

Evaluando Pr(Xi = 1) = pi. De acuerdo a (1),

 

La tercera línea abajo está dada porque   toma el valor et con probabilidad pi y el valor 1 con probabilidad 1 − pi. Este es idéntico al cálculo anterior en la demostración del teorema de la forma aditiva.

Reescribiendo   as   y notando que   (con inecuación estricta si x > 0), hacemos  . El mismo resultado puede obtenerse al reemplazar a en la ecuación para la cota de Chernoff con (1 + δ)μ.

Por lo tanto,

 

Si simplemente hacemos t = log(1 + δ) tal que t > 0 para δ > 0, podemos sustituir y encontrar

 

Esto prueba el resultado deseado. Una estrategia similar de demostración puede ser usada para mostrar que

 

La fórmula anterior en la práctica es usualmete torpe para computar,[3]​ por lo que las siguientes cotas más flojas pero más convenientes son usadas a menudo:

 
 
 

Mejores cotas de Chernoff para algunos casos especialesEditar

Podemos obtener cotas más fuertes usando técnicas de demostración más simples para algunos casos especiales de variables aleatorias simétricas.

Supón que X1, ..., Xn son variables aleatorias independientes, y que X denota la suma de ellas.

  • Si  . Entonces,
 
y por lo tanto también
 
  • Si   Entonces,
 
 

Aplicaciones de las cotas de ChernoffEditar

Las cotas de Chernoff tienen aplicaciones muy útiles en el balance de conjuntos y el enrutamiento de paquetes en redes esparcidas.

El problema del balance de conjuntos surge durante el diseño de experimentos estadísticos. Típicamente mientras diseñamos un experimento estadístico, dadas las características de cada participante en el experimento, necesitamos conocer como dividir los participantes en dos conjuntos disjuntos tal que las características están tan balanceada como sea posible entre los dos grupos. Referirse a sección del libro para más información del problema.

Las cotas de Chernoff son también usadas para obtener cotas ajustadas para los problemas de la permutación de enrutamiento con una congestión de redes reducida durante el enrutamiento de paquetes en redes esparcidas. Referirse a sección del libro para un completo tratamiento del problema.

Las cotas de Chernoff puedes ser usadas de manera efectiva para evaluar el "nivel de robustez" de una aplicación/algoritmo al explorar su espacio de perturbación con aleatoriedad.[4]​ El uso de cotas de Chernoff permite abandonar la hipótesis de las fuertes -y mayormente no realistas- pequeñas perturbaciones. El nivel de robustez puede ser, en cambio, usado para validar o rechazar una elección específica de algorítmo, una implementación de hardware o la pertinencia de una solución cuyos parámetros estructurales son afectados con incertidumbre.

Cotas de Chernoff para matricesEditar

Rudolf Ahlswede y Andreas Winter introdujeron (Ahlswede y Winter, 2003) una cota de Chernoff para variables aleatorias con representación matricial.

Si M está distribuida acorde a cierta distribución sobre d × d matrices con esperanza 0, y si M1, ..., Mt son copias independientes de M entonces para todo ε > 0,

 

donde   se cumple casi siempre y C > 0 es una constante.

Notar que el número de muestras en la inecuación depende logarítmicamente de d. En general, desafortunadamente, tal dependencia es inevitable: toma por ejemplo una matriz diagona aleatoria de dimensión d. El operador norma de la suma de t muestras independientes es precisamente la máxima desviación entre d caminos independientes de longitud t. En orden de alcanzar una cota fija en la desviación máxima con probabilidad constante, es fácil darse cuenta que t debería crecer logarítmicamente con d en este caso.[5]

El siguiente teorema se puede satisfacer si asumimos que M tiene bajo rango, con el objetivo de evitar la dependencia de las dimensiones.


Teorema sin la dependencia de las dimensionesEditar

Sea 0 < ε < 1 y M una matriz simétrica real aleatoria con   y   casi siempre. Asume que cada elemento en la base de 'M' tiene a lo sumo rango r. Evalúa

 

Si   se cumple casi siempre, entonces

 

donde M1, ..., Mt son copias de 'M' igualmente distribuidas.

Variante de muestreoEditar

La siguiente variante de las cotas de Chernoff puede ser usada para acotar la probabilidad de que una mayoría en una población se convierta en minoría en una muestra, o viceversa[6]

Supón que hay una población general A y una sub-población BA. Denota el tamaño relativo de la sub-población (|B|/|A|) con r.

Supón que elegimos un entero k y una muestra aleatoria SA de tamaño k. Denota el tamaño relativo de la sub-población (|BS|/|S|) con rS.

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

 

En particular, si B es una mayoría en A (r > 0.5) podemos acotar la probabilidad de que B se mantenga como una minoría en S (rS>0.5) tomando: d = 1 - 1 / (2 r):[7]

 

Esta cota no es fina para nada. Por ejemplo, cuando r = 0.5 tenemos una cota trivial Prob > 0.

ReferenciasEditar

  1. Chernoff, Herman (2014). «A career in statistics». Lin, Xihong; Genest, Christian; Banks, David L.; Molenberghs, Geert; Scott, David W.; Wang, Jane-Ling, eds. Past, Present, and Future of Statistics. CRC Press. p. 35. ISBN 9781482204964. 
  2. Sinclair, Alistair (Fall 2011). «Class notes for the course "Randomness and Computation"». Consultado el 30 de octubre de 2014. 
  3. Mitzenmacher, Michael and Upfal, Eli (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. ISBN 0-521-83540-2. 
  4. C.Alippi: "Randomized Algorithms" chapter in Intelligence for Embedded Systems. Springer, 2014, 283pp, ISBN 978-3-319-05278-6.
  5. *Magen, A.; Zouzias, A. (2011). «Low Rank Matrix-Valued Chernoff Bounds and Approximate Matrix Multiplication». arXiv:1005.2724  [cs.DM]. 
  6. Goldberg, A. V.; Hartline, J. D. (2001). «Competitive Auctions for Multiple Digital Goods». Algorithms — ESA 2001. Lecture Notes in Computer Science 2161. p. 416. ISBN 978-3-540-42493-2. doi:10.1007/3-540-44676-1_35. ; lemma 6.1
  7. Ver grafos de: la cota como una función de r donde k cambia y la cota como una función de k donde r cambia.

 [cs.IT].