Cotas de Chernoff

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 con las (antecesoras históricas) inecuaciones de Bernstein, y a la inecuación de Hoeffding.

Ejemplo

Sean X₁, ..., X_n 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 {X_k = 1} tiene un valor exacto S, donde

${\displaystyle S=\sum _{i=\lfloor {\tfrac {n}{2}}\rfloor +1}^{n}{\binom {n}{i}}p^{i}(1-p)^{n-i}.}$ 

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

${\displaystyle S\geq 1-e^{-{\frac {1}{2p}}n\left(p-{\frac {1}{2}}\right)^{2}}.}$ 

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]​

${\displaystyle {\begin{aligned}\Pr \left(\sum _{k=1}^{n}X_{k}\leq \left\lfloor {\tfrac {n}{2}}\right\rfloor \right)&=\Pr \left(\sum _{k=1}^{n}X_{k}\leq \left(1-\left(1-{\tfrac {1}{2p}}\right)\right)\mu \right)\\&\leq e^{-{\frac {\mu }{2}}\left(1-{\frac {1}{2p}}\right)^{2}}\\&=e^{-{\frac {n}{2p}}\left(p-{\frac {1}{2}}\right)^{2}}\end{aligned}}}$ 

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 Chernoff

Las cotas de Chernoff para una variable aleatoria X, la cual es la suma de n variables aleatorias independientes X₁, ..., X_n, se obtienen al aplicar e^tX 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,

${\displaystyle \Pr(X\geq a)=\Pr \left(e^{tX}\geq e^{ta}\right)\leq {\frac {E\left[e^{tX}\right]}{e^{ta}}}=e^{-ta}\mathrm {E} \left[\prod _{i}e^{tX_{i}}\right].}$ 

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

| ${\displaystyle \Pr(X\geq a)\leq \min _{t>0}e^{-ta}\prod _{i}E\left[e^{tX_{i}}\right].}$  (1)

Similarmente,

${\displaystyle \Pr(X\leq a)=\Pr \left(e^{-tX}\geq e^{-ta}\right)}$ 

y también,

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

Definiciones precisas y demostraciones

Teorema para la forma aditiva (error absoluto)

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

Teorema Chernoff-Hoeffding. Supón que X₁, ..., X_n son variables aleatorias igualmente distribuidas, tomando valores en {0, 1}. Sea p = E[X_i] y ε > 0. Entonces

${\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 \|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 \|p)n}\end{aligned}}}$ 

donde

${\displaystyle D(x\|y)=x\ln {\frac {x}{y}}+(1-x)\ln \left({\frac {1-x}{1-y}}\right)}$ 

es la divergencia Kullback–Leibler entre dos variables aleatorias que distribuyen Bernoulli con parámetros x y y respectivamente. Si p ≥ 1/2, entonces

${\displaystyle \Pr \left(X>np+x\right)\leq \exp \left(-{\frac {x^{2}}{2np(1-p)}}\right).}$ 

Demostración

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

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

${\displaystyle \left({\frac {\mathrm {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 computar fácilmente el ínfimo, 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}}$ 

Igualando la ecuación a 0 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}}}$ 

entonces

${\displaystyle e^{t}={\frac {(1-p)q}{(1-q)p}}.}$ 

Por lo que,

${\displaystyle t=\log \left({\frac {(1-p)q}{(1-q)p}}\right).}$ 

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

${\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\|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 \|p)n}.}$ 

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

Cotas más simples

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

${\displaystyle {\frac {d^{2}}{dx^{2}}}D(p+x\|p)={\frac {1}{(p+x)(1-p-x)}}\geq 4={\frac {d^{2}}{dx^{2}}}(2x^{2}).}$ 

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

${\displaystyle D((1+x)p\|p)\geq {\tfrac {1}{4}}x^{2}p,\qquad -{\tfrac {1}{2}}\leq x\leq {\tfrac {1}{2}},}$ 

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)

Cota de Chernoff Multiplicativa. Supón que X₁, ..., X_n 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,

${\displaystyle \Pr(X>(1+\delta )\mu )<\left({\frac {e^{\delta }}{(1+\delta )^{(1+\delta )}}}\right)^{\mu }.}$ 

Demostración

Evaluando Pr(X_i = 1) = p_i. De acuerdo a (1),

${\displaystyle {\begin{aligned}\Pr(X>(1+\delta )\mu )&\leq \inf _{t>0}{\frac {\mathrm {E} \left[\prod _{i=1}^{n}\exp(tX_{i})\right]}{\exp(t(1+\delta )\mu )}}\\&=\inf _{t>0}{\frac {\prod _{i=1}^{n}\mathrm {E} \left[e^{tX_{i}}\right]}{\exp(t(1+\delta )\mu )}}\\&=\inf _{t>0}{\frac {\prod _{i=1}^{n}\left[p_{i}e^{t}+(1-p_{i})\right]}{\exp(t(1+\delta )\mu )}}\end{aligned}}}$ 

La tercera línea abajo está dada porque ${\displaystyle e^{tX_{i}}}$  toma el valor e^t con probabilidad p_i y el valor 1 con probabilidad 1 − p_i. Este es idéntico al cálculo anterior en la demostración del teorema de la forma aditiva.

Reescribiendo ${\displaystyle p_{i}e^{t}+(1-p_{i})}$  as ${\displaystyle p_{i}(e^{t}-1)+1}$  y notando que ${\displaystyle 1+x\leq e^{x}}$  (con inecuación estricta si x > 0), hacemos ${\displaystyle x=p_{i}(e^{t}-1)}$ . El mismo resultado puede obtenerse al reemplazar a en la ecuación para la cota de Chernoff con (1 + δ)μ.

Por lo tanto,

${\displaystyle \Pr(X>(1+\delta )\mu )<{\frac {\prod _{i=1}^{n}\exp(p_{i}(e^{t}-1))}{\exp(t(1+\delta )\mu )}}={\frac {\exp \left((e^{t}-1)\sum _{i=1}^{n}p_{i}\right)}{\exp(t(1+\delta )\mu )}}={\frac {\exp((e^{t}-1)\mu )}{\exp(t(1+\delta )\mu )}}.}$ 

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

${\displaystyle {\frac {\exp((e^{t}-1)\mu )}{\exp(t(1+\delta )\mu )}}={\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. Una estrategia similar de demostración puede ser usada para mostrar que

${\displaystyle \Pr(X<(1-\delta )\mu )<\left[{\frac {\exp(-\delta )}{(1-\delta )^{(1-\delta )}}}\right]^{\mu }.}$ 

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

${\displaystyle \Pr(X\geq (1+\delta )\mu )\leq e^{-{\frac {\delta ^{2}\mu }{3}}},\qquad 0<\delta <1,}$ 

${\displaystyle \Pr(X\geq (1+\delta )\mu )\leq e^{-{\frac {\delta \mu }{3}}},\qquad 1<\delta ,}$ 

${\displaystyle \Pr(X\leq (1-\delta )\mu )\leq e^{-{\frac {\delta ^{2}\mu }{2}}},\qquad 0<\delta <1.}$ 

Mejores cotas de Chernoff para algunos casos especiales

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 X₁, ..., X_n son variables aleatorias independientes, y que X denota la suma de ellas.

• Si ${\displaystyle \Pr(X_{i}=1)=\Pr(X_{i}=-1)={\tfrac {1}{2}}}$ . Entonces,

${\displaystyle \Pr(X\geq a)\leq e^{\frac {-a^{2}}{2n}},\qquad a>0,}$ 

y por lo tanto también

${\displaystyle \Pr(|X|\geq a)\leq 2e^{\frac {-a^{2}}{2n}},\qquad a>0.}$ 

• Si ${\displaystyle \Pr(X_{i}=1)=\Pr(X_{i}=0)={\tfrac {1}{2}},\mathrm {E} [X]=\mu ={\frac {n}{2}}}$  Entonces,

${\displaystyle \Pr(X\geq \mu +a)\leq e^{\frac {-2a^{2}}{n}},\qquad a>0,}$ 

${\displaystyle \Pr(X\leq \mu -a)\leq e^{\frac {-2a^{2}}{n}},\qquad 0<a<\mu ,}$ 

Aplicaciones de las cotas de Chernoff

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 algoritmo, una implementación de hardware o la pertinencia de una solución cuyos parámetros estructurales son afectados con incertidumbre.

Cotas de Chernoff para matrices

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 M₁, ..., M_t son copias independientes de M entonces para todo ε > 0,

${\displaystyle \Pr \left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}\right\|_{2}>\varepsilon \right)\leq d\exp \left(-C{\frac {\varepsilon ^{2}t}{\gamma ^{2}}}\right).}$ 

donde ${\displaystyle \lVert M\rVert _{2}\leq \gamma }$  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 de 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 dimensiones

Sea 0 < ε < 1 y M una matriz simétrica real aleatoria con ${\displaystyle \|\mathrm {E} [M]\|_{2}\leq 1}$  y ${\displaystyle \|M\|_{2}\leq \gamma }$  casi siempre. Asume que cada elemento en la base de 'M' tiene a lo sumo rango r. Evalúa

${\displaystyle t=\Omega \left({\frac {\gamma \log(\gamma /\varepsilon ^{2})}{\varepsilon ^{2}}}\right).}$ 

Si ${\displaystyle r\leq t}$  se cumple casi siempre, entonces

${\displaystyle \Pr \left(\left\|{\frac {1}{t}}\sum _{i=1}^{t}M_{i}-\mathrm {E} [M]\right\|_{2}>\varepsilon \right)\leq {\frac {1}{\mathbf {poly} (t)}}}$ 

donde M₁, ..., M_t son copias de 'M' igualmente distribuidas.

Variante de muestreo

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 B⊆A. 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 S⊂A de tamaño k. Denota el tamaño relativo de la sub-población (|B∩S|/|S|) con r_S.

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

${\displaystyle \mathrm {Pr} \left(r_{S}<(1-d)\cdot r\right)<\exp \left(-r\cdot d^{2}\cdot k/2\right)}$ 

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 (r_S>0.5) tomando: d = 1 - 1 / (2 r):^[7]​

${\displaystyle \mathrm {Pr} \left(r_{S}>0.5\right)>1-\exp \left(-r\cdot \left(1-{\frac {1}{2r}}\right)^{2}\cdot k/2\right)}$ 

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

Referencias

1. Chernoff, Herman (2014). «A career in statistics». En 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). . Archivado desde el original el 31 de octubre de 2014. 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.

• Chernoff, H. (1952). «A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations». [Annals of Mathematical Statistics] 23 (4): 493-507. JSTOR 2236576. MR 57518. Zbl 0048.11804. doi:10.1214/aoms/1177729330. 
• Hoeffding, W. (1963). «Probability Inequalities for Sums of Bounded Random Variables». [Journal of the American Statistical Association] 58 (301): 13-30. JSTOR 2282952. doi:10.2307/2282952. 
• Chernoff, H. (1981). «A Note on an Inequality Involving the Normal Distribution». [Annals of Probability] 9 (3): 533. JSTOR 2243541. MR 614640. Zbl 0457.60014. doi:10.1214/aop/1176994428. 
• Hagerup, T. (1990). «A guided tour of Chernoff bounds». [Information Processing Letters] 33 (6): 305. doi:10.1016/0020-0190(90)90214-I. 
• Ahlswede, R.; Winter, A. (2003). «Strong Converse for Identification via Quantum Channels». [IEEE Transactions on Information Theory] 48 (3): 569-579. arXiv:quant-ph/0012127. doi:10.1109/18.985947. 
• Mitzenmacher, M.; Upfal, E. (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. ISBN 978-0-521-83540-4. 
• Nielsen, F. (2011). «Chernoff information of exponential families». arXiv:1102.2684

 [cs.IT]. 

•   Datos: Q1070305