Limite de Chernoff

Propriedades

A função exponencial é convexa, então, pela desigualdade de Jensen, ${\displaystyle \operatorname {E} (e^{tX})\geq e^{t\operatorname {E} (X)}}$. Segue-se que o limite para a cauda direita é maior ou igual a um quando ${\displaystyle a\leq \operatorname {E} (X)}$, sendo, portanto, trivial; da mesma forma, o limite para a cauda esquerda é trivial para ${\displaystyle a\geq \operatorname {E} (X)}$. Assim, podemos combinar os dois ínfimos e definir o limite de Chernoff bilateral:

$${\displaystyle C(a)=\inf _{t}M(t)e^{-ta}}$$

que fornece um limite superior para a função de distribuição acumulada dobrada de ${\displaystyle X}$ (dobrada na média, não na mediana).

O logaritmo do limite de Chernoff bilateral é conhecido como a função de taxa [en] (ou "transformada de Cramér") ${\displaystyle I=-\log C}$. É equivalente à transformada de Legendre–Fenchel [en], ou conjugado convexo, da função geradora de cumulantes ${\displaystyle K=\log M}$, definida como:

$${\displaystyle I(a)=\sup _{t}at-K(t)}$$

A função geradora de momentos é logaritmicamente convexa [en], então, por uma propriedade do conjugado convexo, o limite de Chernoff deve ser logaritmicamente côncavo [en]. O limite de Chernoff atinge seu máximo na média, ${\displaystyle C(\operatorname {E} (X))=1}$, e é invariante sob translação: ${\textstyle C_{X+k}(a)=C_{X}(a-k)}$.

O limite de Chernoff é exato se, e somente se, ${\displaystyle X}$ for uma massa concentrada única (distribuição degenerada [en]). O limite é apertado apenas nos extremos ou além de uma variável aleatória limitada, onde os ínfimos são atingidos para ${\displaystyle t}$ infinito. Para variáveis aleatórias ilimitadas, o limite não é apertado em nenhum ponto, embora seja assintoticamente apertado até fatores subexponenciais ("exponencialmente apertado"). Momentos individuais podem fornecer limites mais apertados, ao custo de maior complexidade analítica.

Na prática, o limite exato de Chernoff pode ser difícil de avaliar analiticamente, caso em que um limite superior adequado para a função geradora de momentos (ou cumulantes) pode ser usado (por exemplo, uma CGF subparabólica gerando um limite de Chernoff subgaussiano).

Funções de taxa exatas e limites de Chernoff para distribuições comuns

Distribuição	${\displaystyle \operatorname {E} (X)}$	${\displaystyle K(t)}$	${\displaystyle I(a)}$	${\displaystyle C(a)}$
Distribuição normal	${\displaystyle 0}$	${\displaystyle {\frac {1}{2}}\sigma ^{2}t^{2}}$	${\displaystyle {\frac {1}{2}}\left({\frac {a}{\sigma }}\right)^{2}}$	${\displaystyle \exp \left({-{\frac {a^{2}}{2\sigma ^{2}}}}\right)}$
Distribuição de Bernoulli(detalhada abaixo)	${\displaystyle p}$	${\displaystyle \ln \left(1-p+pe^{t}\right)}$	${\displaystyle D_{KL}(a\parallel p)}$	${\displaystyle \left({\frac {p}{a}}\right)^{a}{\left({\frac {1-p}{1-a}}\right)}^{1-a}}$
Bernoulli padrão (H é a função de entropia binária [en])	${\displaystyle {\frac {1}{2}}}$	${\displaystyle \ln \left(1+e^{t}\right)-\ln(2)}$	${\displaystyle \ln(2)-H(a)}$	${\displaystyle {\frac {1}{2}}a^{-a}(1-a)^{-(1-a)}}$
Distribuição de Rademacher [en]	${\displaystyle 0}$	${\displaystyle \ln \cosh(t)}$	${\displaystyle \ln(2)-H\left({\frac {1+a}{2}}\right)}$	${\displaystyle {\sqrt {(1+a)^{-1-a}(1-a)^{-1+a}}}}$
Distribuição gama	${\displaystyle \theta k}$	${\displaystyle -k\ln(1-\theta t)}$	${\displaystyle -k\ln {\frac {a}{\theta k}}-k+{\frac {a}{\theta }}}$	${\displaystyle \left({\frac {a}{\theta k}}\right)^{k}e^{k-a/\theta }}$
Distribuição qui-quadrada	${\displaystyle k}$	${\displaystyle -{\frac {k}{2}}\ln(1-2t)}$	${\displaystyle {\frac {k}{2}}\left({\frac {a}{k}}-1-\ln {\frac {a}{k}}\right)}$	${\displaystyle \left({\frac {a}{k}}\right)^{k/2}e^{k/2-a/2}}$
Distribuição de Poisson	${\displaystyle \lambda }$	${\displaystyle \lambda (e^{t}-1)}$	${\displaystyle a\ln(a/\lambda )-a+\lambda }$	${\displaystyle (a/\lambda )^{-a}e^{a-\lambda }}$

Limites inferiores a partir da FGM

Usando apenas a função geradora de momentos, um limite inferior para as probabilidades de cauda pode ser obtido aplicando a desigualdade de Paley–Zygmund [en] a ${\displaystyle e^{tX}}$, resultando em:

$${\displaystyle \operatorname {P} \left(X>a\right)\geq \sup _{t>0\land M(t)\geq e^{ta}}\left(1-{\frac {e^{ta}}{M(t)}}\right)^{2}{\frac {M(t)^{2}}{M(2t)}}}$$

(um limite para a cauda esquerda é obtido para ${\displaystyle t<0}$). Diferentemente do limite de Chernoff, esse resultado não é exponencialmente apertado.

Theodosopoulos construiu um limite inferior mais apertado baseado na FGM usando um procedimento de inclinação exponencial [en].

Para distribuições específicas (como a binomial), limites inferiores da mesma ordem exponencial do limite de Chernoff estão frequentemente disponíveis.

Forma multiplicativa (erro relativo)

Limite de Chernoff multiplicativo. Suponha que X₁, ..., X_n sejam variáveis aleatórias independentes tomando valores em {0, 1}. Seja X sua soma e μ = E[X] o valor esperado da soma. Então, para qualquer δ > 0,

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

Uma estratégia de prova semelhante pode ser usada para mostrar que, para 0 < δ < 1,

${\displaystyle \Pr(X\leq (1-\delta )\mu )\leq \left({\frac {e^{-\delta }}{(1-\delta )^{1-\delta }}}\right)^{\mu }.}$

A fórmula acima é frequentemente difícil de usar na prática, então os seguintes limites mais soltos, mas mais convenientes, são frequentemente usados, que seguem da desigualdade ${\displaystyle \textstyle {\frac {2\delta }{2+\delta }}\leq \log(1+\delta )}$ da lista de desigualdades logarítmicas:

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

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

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

Note que os limites são triviais para ${\displaystyle \delta =0}$.

Além disso, com base na expansão de Taylor para a função W de Lambert,

${\displaystyle \Pr(X\geq R)\leq 2^{-xR},\qquad x>0,\ R\geq (2^{x}e-1)\mu .}$

Forma aditiva (erro absoluto)

O seguinte teorema é devido a Wassily Hoeffding e, portanto, é chamado de teorema de Chernoff–Hoeffding.

Teorema de Chernoff–Hoeffding. Suponha que X₁, ..., X_n sejam variáveis aleatórias i.i.d. tomando valores em {0, 1}. Seja p = E[X₁] e ε > 0.

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

onde

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

é a divergência de Kullback–Leibler entre variáveis aleatórias de Bernoulli com parâmetros x e y, respectivamente. Se p ≥ ⁠1/2⁠, então ${\displaystyle D(p+\varepsilon \parallel p)\geq {\tfrac {\varepsilon ^{2}}{2p(1-p)}}}$, o que implica

${\displaystyle \Pr \left({\frac {1}{n}}\sum X_{i}>p+x\right)\leq \exp \left(-{\frac {x^{2}n}{2p(1-p)}}\right).}$

Um limite mais simples segue relaxando o teorema usando D(p + ε || p) ≥ 2ε², que decorre da convexidade de D(p + ε || p) e do fato de que

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

Esse resultado é um caso especial da desigualdade de Hoeffding. Às vezes, os limites

${\displaystyle {\begin{aligned}D((1+x)p\parallel p)\geq {\frac {1}{4}}x^{2}p,&&&{-{\tfrac {1}{2}}}\leq x\leq {\tfrac {1}{2}},\\[6pt]D(x\parallel y)\geq {\frac {3(x-y)^{2}}{2(2y+x)}},\\[6pt]D(x\parallel y)\geq {\frac {(x-y)^{2}}{2y}},&&&x\leq y,\\[6pt]D(x\parallel y)\geq {\frac {(x-y)^{2}}{2x}},&&&x\geq y\end{aligned}}}$

que são mais fortes para p < ⁠1/8⁠, também são usados.

Teorema sem dependência nas dimensões

Seja 0 < ε < 1 e M uma matriz simétrica real aleatória com ${\displaystyle \|\operatorname {E} [M]\|\leq 1}$ e ${\displaystyle \|M\|\leq \gamma }$ quase certamente. Suponha que cada elemento no suporte de M tenha no máximo posto r. Defina

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

Se ${\displaystyle r\leq t}$ for válido quase certamente, então

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

onde M₁, ..., M_t são cópias i.i.d. de M.

Forma multiplicativa

Seguindo as condições do limite de Chernoff multiplicativo, sejam X₁, ..., X_n variáveis aleatórias de Bernoulli independentes, cuja soma é X, cada uma com probabilidade p_i de ser igual a 1. Para uma variável de Bernoulli:

${\displaystyle \operatorname {E} \left[e^{t\cdot X_{i}}\right]=(1-p_{i})e^{0}+p_{i}e^{t}=1+p_{i}(e^{t}-1)\leq e^{p_{i}(e^{t}-1)}}$

Assim, usando (1) com ${\displaystyle a=(1+\delta )\mu }$ para qualquer ${\displaystyle \delta >0}$ e onde ${\displaystyle \mu =\operatorname {E} [X]=\textstyle \sum _{i=1}^{n}p_{i}}$,

${\displaystyle {\begin{aligned}\Pr(X>(1+\delta )\mu )&\leq \inf _{t\geq 0}\exp(-t(1+\delta )\mu )\prod _{i=1}^{n}\operatorname {E} [\exp(tX_{i})]\\[4pt]&\leq \inf _{t\geq 0}\exp {\Big (}-t(1+\delta )\mu +\sum _{i=1}^{n}p_{i}(e^{t}-1){\Big )}\\[4pt]&=\inf _{t\geq 0}\exp {\Big (}-t(1+\delta )\mu +(e^{t}-1)\mu {\Big )}.\end{aligned}}}$

Se simplesmente definirmos t = log(1 + δ) de modo que t > 0 para δ > 0, podemos substituir e encontrar

${\displaystyle \exp {\Big (}-t(1+\delta )\mu +(e^{t}-1)\mu {\Big )}={\frac {\exp((1+\delta -1)\mu )}{(1+\delta )^{(1+\delta )\mu }}}=\left[{\frac {e^{\delta }}{(1+\delta )^{(1+\delta )}}}\right]^{\mu }.}$

Isso prova o resultado desejado.

Teorema de Chernoff–Hoeffding (forma aditiva)

Seja q = p + ε. Tomando a = nq em (1), obtemos:

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

Agora, sabendo que Pr(X_i = 1) = p, Pr(X_i = 0) = 1 − p, temos

${\displaystyle \left({\frac {\operatorname {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}.}$

Portanto, podemos calcular facilmente o í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 a equação a zero e resolvendo, temos

${\displaystyle {\begin{aligned}(1-q)pe^{(1-q)t}&=q(1-p)e^{-qt}\\(1-q)pe^{t}&=q(1-p)\end{aligned}}}$

de modo que

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

Assim,

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

Como q = p + ε > p, vemos que t > 0, então nosso limite é satisfeito em t. Tendo resolvido para t, podemos substituir nas equações acima para encontrar 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\parallel p).\end{aligned}}}$

Agora temos o resultado desejado, que

${\displaystyle \Pr \left({\tfrac {1}{n}}\sum X_{i}\geq p+\varepsilon \right)\leq e^{-D(p+\varepsilon \parallel p)n}.}$

Para completar a prova para o caso simétrico, simplesmente definimos a variável aleatória Y_i = 1 − X_i, aplicamos a mesma prova e a substituímos em nosso limite.