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, 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 Plantilla:Math 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 Plantilla:Math tiene un valor exacto Plantilla:Mvar, donde

$S=\sum _{i=\lfloor \frac{n}{2}\rfloor +1}^n(\genfrac{}{}{0ex}{}{n}{i})p^i(1-p{)}^{n-i}.$

La cota de Chernoff muestra que Plantilla:Mvar tiene la siguiente cota inferior:

$S\ge 1-e^{-\frac{1}{2p}n{(p-\frac{1}{2})}^2}.$

En efecto, notando que Plantilla:Math, 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),

$\begin{array}{cc}\mathrm{Pr}(\sum _{k=1}^n{X}_k\le \lfloor \frac{n}{2}\rfloor )& =\mathrm{Pr}(\sum _{k=1}^n{X}_k\le (1-(1-\frac{1}{2p}))\mu )\\ & \le e^{-\frac{\mu }{2}{(1-\frac{1}{2p})}^2}\\ & =e^{-\frac{n}{2p}{(p-\frac{1}{2})}^2}\end{array}$

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 Plantilla:Mvar, la cual es la suma de Plantilla:Mvar variables aleatorias independientes Plantilla:Math, se obtienen al aplicar Plantilla:Mvar 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,

$\mathrm{Pr}(X\ge a)=\mathrm{Pr}(e^{tX}\ge e^{ta})\le \frac{E\left[e^{tX}\right]}{e^{ta}}=e^{-ta}\mathrm{E}\left[\prod _i{e}^{t{X}_i}\right].$

En particular optimizando sobre t y usando la independencia de Plantilla:Mvar obtenemos,

| $\mathrm{Pr}(X\ge a)\le \underset{t>0}{\min }{e}^{-ta}\prod _{i}E\left[e^{t{X}_i}\right].$ (1)

Similarmente,

$\mathrm{Pr}(X\le a)=\mathrm{Pr}(e^{-tX}\ge e^{-ta})$

y también,

$\mathrm{Pr}(X\le a)\le \underset{t>0}{\min }{e}^{ta}\prod _i\mathrm{E}\left[e^{-t{X}_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 Plantilla:Math son variables aleatorias igualmente distribuidas, tomando valores en Plantilla:Math Sea Plantilla:Math y Plantilla:Math. Entonces

$\begin{array}{cc}\mathrm{Pr}(\frac{1}{n}\sum X_i\ge p+\epsilon )\le {\left({\left(\frac{p}{p+\epsilon }\right)}^{p+\epsilon }{\left(\frac{1-p}{1-p-\epsilon }\right)}^{1-p-\epsilon }\right)}^n& =e^{-D(p+\epsilon \Vert p)n}\\ \mathrm{Pr}(\frac{1}{n}\sum X_i\le p-\epsilon )\le {\left({\left(\frac{p}{p-\epsilon }\right)}^{p-\epsilon }{\left(\frac{1-p}{1-p+\epsilon }\right)}^{1-p+\epsilon }\right)}^n& =e^{-D(p-\epsilon \Vert p)n}\end{array}$

donde

$D(x\Vert 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 Plantilla:Math entonces

$\mathrm{Pr}(X>np+x)\le \exp (-\frac{x^2}{2np(1-p)}).$

Demostración

Sea Plantilla:Math. Tomando Plantilla:Math en (1), obtenemos:

$\mathrm{Pr}(\frac{1}{n}\sum X_i\ge q)\le \underset{t>0}{\inf }\frac{E[\prod e^{t{X}_i}]}{e^{tnq}}=\underset{t>0}{\inf }{\left(\frac{E\left[e^{t{X}_i}\right]}{e^{tq}}\right)}^n.$

Luego, conociendo que Plantilla:Math, tenemos que

${\left(\frac{\mathrm{E}\left[e^{t{X}_i}\right]}{e^{tq}}\right)}^n={\left(\frac{p{e}^t+(1-p)}{e^{tq}}\right)}^n={(p{e}^{(1-q)t}+(1-p)e^{-qt})}^n.$

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

$\frac{d}{dt}(p{e}^{(1-q)t}+(1-p)e^{-qt})=(1-q)p{e}^{(1-q)t}-q(1-p)e^{-qt}$

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

$\begin{array}{cc}(1-q)p{e}^{(1-q)t}& =q(1-p)e^{-qt}\\ (1-q)p{e}^t& =q(1-p)\end{array}$

entonces

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

Por lo que,

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

Como Plantilla:Math, vemos que Plantilla:Math, por lo cual nuestra cota se satisface para Plantilla:Mvar. Luego de resolverlo para Plantilla:Mvar, podemos sustituir en las ecuaciones anteriores para llegar a que

$\begin{array}{cc}\log (p{e}^{(1-q)t}+(1-p)e^{-qt})& =\log (e^{-qt}(1-p+p{e}^t))\\ & =\log \left(e^{-q\log \left(\frac{(1-p)q}{(1-q)p}\right)}\right)+\log (1-p+p{e}^{\log \left(\frac{1-p}{1-q}\right)}{e}^{\log \frac{q}{p}})\\ & =-q\log \frac{1-p}{1-q}-q\log \frac{q}{p}+\log (1-p+p\left(\frac{1-p}{1-q}\right)\frac{q}{p})\\ & =-q\log \frac{1-p}{1-q}-q\log \frac{q}{p}+\log (\frac{(1-p)(1-q)}{1-q}+\frac{(1-p)q}{1-q})\\ & =-q\log \frac{q}{p}+(-q\log \frac{1-p}{1-q}+\log \frac{1-p}{1-q})\\ & =-q\log \frac{q}{p}+(1-q)\log \frac{1-p}{1-q}\\ & =-D(q\Vert p).\end{array}$

Ahora tenemos el resultado deseado, que

$\mathrm{Pr}(\frac{1}{n}\sum X_i\ge p+\epsilon )\le e^{-D(p+\epsilon \Vert p)n}.$

Para completar la demostración para el caso simétrico, simplemente definimos la variable aleatoria Plantilla:Math, 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 Plantilla:Math, debido a que Plantilla:Math es convexo y al hecho de que

$\frac{d^2}{d{x}^2}D(p+x\Vert p)=\frac{1}{(p+x)(1-p-x)}\ge 4=\frac{d^2}{d{x}^2}(2x^2).$

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

$D((1+x)p\Vert p)\ge \frac{1}{4}{x}^{2}p,-\frac{1}{2}\le x\le \frac{1}{2},$

la cual es más fuerte para Plantilla:Math es también usada.

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

Cota de Chernoff Multiplicativa. Supón que Plantilla:Math son variables aleatorias independientes tomando valores en Plantilla:Math Sea Plantilla:Mvar la variable que denota su suma y Plantilla:Math la suma de los valores esperados. Entonces para todo Plantilla:Math,

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

Demostración

Evaluando Plantilla:Math. De acuerdo a (1),

$\begin{array}{cc}\mathrm{Pr}(X>(1+\delta )\mu )& \le \underset{t>0}{\inf }\frac{\mathrm{E}[\prod _{i=1}^n\exp (t{X}_i)]}{\exp (t(1+\delta )\mu )}\\ & =\underset{t>0}{\inf }\frac{\prod _{i=1}^n\mathrm{E}\left[e^{t{X}_i}\right]}{\exp (t(1+\delta )\mu )}\\ & =\underset{t>0}{\inf }\frac{\prod _{i=1}^n[p_i{e}^t+(1-p_i)]}{\exp (t(1+\delta )\mu )}\end{array}$

La tercera línea abajo está dada porque $e^{t{X}_i}$ toma el valor Plantilla:Mvar con probabilidad Plantilla:Mvar y el valor 1 con probabilidad Plantilla:Math. Este es idéntico al cálculo anterior en la demostración del teorema de la forma aditiva.

Reescribiendo $p_i{e}^t+(1-p_i)$ as $p_i(e^t-1)+1$ y notando que $1+x\le e^x$ (con inecuación estricta si Plantilla:Math), hacemos $x=p_i(e^t-1)$. El mismo resultado puede obtenerse al reemplazar Plantilla:Mvar en la ecuación para la cota de Chernoff con Plantilla:Math.

Por lo tanto,

$\mathrm{Pr}(X>(1+\delta )\mu )<\frac{\prod _{i=1}^n\exp (p_i(e^t-1))}{\exp (t(1+\delta )\mu )}=\frac{\exp ((e^t-1)\sum _{i=1}^n{p}_i)}{\exp (t(1+\delta )\mu )}=\frac{\exp ((e^t-1)\mu )}{\exp (t(1+\delta )\mu )}.$

Si simplemente hacemos Plantilla:Math tal que Plantilla:Math para Plantilla:Math, podemos sustituir y encontrar

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

$\mathrm{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, por lo que las siguientes cotas más flojas pero más convenientes son usadas a menudo:

$\mathrm{Pr}(X\ge (1+\delta )\mu )\le e^{-\frac{{\delta }^2\mu }{3}},0<\delta <1,$

$\mathrm{Pr}(X\ge (1+\delta )\mu )\le e^{-\frac{\delta \mu }{3}},1<\delta ,$

$\mathrm{Pr}(X\le (1-\delta )\mu )\le e^{-\frac{{\delta }^2\mu }{2}},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 Plantilla:Math son variables aleatorias independientes, y que Plantilla:Mvar denota la suma de ellas.

• Si $\mathrm{Pr}(X_i=1)=\mathrm{Pr}(X_i=-1)=\frac{1}{2}$. Entonces,

$\mathrm{Pr}(X\ge a)\le e^{\frac{-a^2}{2n}},a>0,$

y por lo tanto también

$\mathrm{Pr}(|X|\ge a)\le 2e^{\frac{-a^2}{2n}},a>0.$

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

$\mathrm{Pr}(X\ge \mu +a)\le e^{\frac{-2a^2}{n}},a>0,$

$\mathrm{Pr}(X\le \mu -a)\le e^{\frac{-2a^2}{n}},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. 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 Plantilla:Harv una cota de Chernoff para variables aleatorias con representación matricial.

Si M está distribuida acorde a cierta distribución sobre Plantilla:Math matrices con esperanza 0, y si Plantilla:Math son copias independientes de M entonces para todo Plantilla:Math,

$\mathrm{Pr}({\Vert \frac{1}{t}\sum _{i=1}^t{M}_i\Vert }_2>\epsilon )\le d\exp (-C\frac{{\epsilon }^{2}t}{{\gamma }^2}).$

donde $\Vert M{\Vert }_2\le \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.

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 Plantilla:Math y M una matriz simétrica real aleatoria con $\Vert \mathrm{E}[M]{\Vert }_2\le 1$ y $\Vert M{\Vert }_2\le \gamma$ casi siempre. Asume que cada elemento en la base de 'M' tiene a lo sumo rango r. Evalúa

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

Si $r\le t$ se cumple casi siempre, entonces

$\mathrm{Pr}({\Vert \frac{1}{t}\sum _{i=1}^t{M}_i-\mathrm{E}[M]\Vert }_2>\epsilon )\le \frac{1}{𝐩𝐨𝐥𝐲(t)}$

donde Plantilla:Math 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

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

$\mathrm{P}\mathrm{r}(r_S<(1-d)\cdot r)<\exp (-r\cdot d^2\cdot k/2)$

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

$\mathrm{P}\mathrm{r}(r_S>0.5)>1-\exp (-r\cdot {(1-\frac{1}{2r})}^2\cdot k/2)$

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

Referencias

• Plantilla:Cita publicación
• Plantilla:Cita publicación
• Plantilla:Cita publicación
• Plantilla:Cita publicación
• Plantilla:Cita publicación
• Plantilla:Cita libro
• Plantilla:Cite arXiv

Plantilla:Control de autoridades