Limite de Chernoff

Na teoria das probabilidades, um limite de Chernoff é um limite superior exponencialmente decrescente para a cauda de uma variável aleatória, baseado em sua função geradora de momentos [en]. O mínimo de todos esses limites exponenciais forma o limite de Chernoff-Cramér, que pode decair mais rapidamente que exponencialmente (por exemplo, subgaussiano [en]).^[1][2] É particularmente útil para somas de variáveis aleatórias independentes, como somas de variáveis de Bernoulli.^[3][4]

O limite é comumente nomeado em homenagem a Herman Chernoff, que descreveu o método em um artigo de 1952,^[5] embora Chernoff tenha atribuído o conceito a Herman Rubin.^[6] Em 1938, Harald Cramér publicou um conceito quase idêntico, agora conhecido como teorema de Cramér [en].

O limite de Chernoff é mais preciso que os limites de cauda baseados no primeiro ou segundo momento, como a desigualdade de Markov [en] ou a desigualdade de Chebyshev, que fornecem apenas limites de decaimento polinomial. No entanto, quando aplicado a somas, o limite de Chernoff exige que as variáveis aleatórias sejam independentes, uma condição não necessária para as desigualdades de Markov ou Chebyshev.

O limite de Chernoff está relacionado às desigualdades de Bernstein [en]. Também é usado para provar a desigualdade de Hoeffding [en], a desigualdade de Bennett [en] e a desigualdade de McDiarmid [en].

O limite genérico de Chernoff para uma variável aleatória ${\displaystyle X}$ é obtido aplicando a desigualdade de Markov a ${\displaystyle e^{tX}}$ (por isso, às vezes é chamado de "limite de Markov exponencial" ou "limite de momentos exponenciais").

Para ${\displaystyle t>0}$, isso fornece um limite para a cauda direita [en] de ${\displaystyle X}$ em termos de sua função geradora de momentos [en] ${\displaystyle M(t)=\operatorname {E} (e^{tX})}$:

${\displaystyle \operatorname {P} \left(X\geq a\right)=\operatorname {P} \left(e^{tX}\geq e^{ta}\right)\leq M(t)e^{-ta}\qquad (t>0)}$

Como esse limite é válido para todo ${\displaystyle t>0}$, podemos tomar o ínfimo:

${\displaystyle \operatorname {P} \left(X\geq a\right)\leq \inf _{t>0}M(t)e^{-ta}}$

Realizando a mesma análise com ${\displaystyle t<0}$, obtemos um limite semelhante para a cauda esquerda:

${\displaystyle \operatorname {P} \left(X\leq a\right)=\operatorname {P} \left(e^{tX}\geq e^{ta}\right)\leq M(t)e^{-ta}\qquad (t<0)}$

e

${\displaystyle \operatorname {P} \left(X\leq a\right)\leq \inf _{t<0}M(t)e^{-ta}}$

A quantidade ${\displaystyle M(t)e^{-ta}}$ pode ser expressa como o valor esperado ${\displaystyle \operatorname {E} (e^{tX})e^{-ta}}$, ou equivalentemente ${\displaystyle \operatorname {E} (e^{t(X-a)})}$.

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.^[7]

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)}$[8]	${\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 }}$

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^[9] 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.

Quando X é a soma de n variáveis aleatórias independentes X₁, ..., X_n, a função geradora de momentos de X é o produto das funções geradoras de momentos individuais, resultando em:

${\displaystyle \Pr(X\geq a)\leq \inf _{t>0}{\frac {\operatorname {E} \left[\prod _{i}e^{t\cdot X_{i}}\right]}{e^{t\cdot a}}}=\inf _{t>0}e^{-t\cdot a}\prod _{i}\operatorname {E} \left[e^{t\cdot X_{i}}\right].}$

(1)

e:

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

Limites específicos de Chernoff são obtidos calculando a função geradora de momentos ${\displaystyle \operatorname {E} \left[e^{-t\cdot X_{i}}\right]}$ para instâncias específicas das variáveis aleatórias ${\displaystyle X_{i}}$.

Quando as variáveis aleatórias também são identicamente distribuídas (iid), o limite de Chernoff para a soma reduz-se a uma simples reescala do limite de Chernoff de uma única variável. Ou seja, o limite de Chernoff para a média de n variáveis iid é equivalente à n-ésima potência do limite de Chernoff de uma única variável (veja teorema de Cramér [en]).

Os limites de Chernoff também podem ser aplicados a somas gerais de variáveis aleatórias independentes e limitadas, independentemente de sua distribuição; isso é conhecido como desigualdade de Hoeffding [en]. A prova segue uma abordagem semelhante aos outros limites de Chernoff, mas aplicando o lema de Hoeffding [en] para limitar as funções geradoras de momentos.

Suponha que X₁, ..., X_n sejam variáveis aleatórias independentes tomando valores em [a,b]. Seja X sua soma e μ = E[X] o valor esperado da soma. Então, para qualquer ${\displaystyle t>0}$,

${\displaystyle \Pr(X\leq \mu -t)<e^{-2t^{2}/(n(b-a)^{2})},}$

${\displaystyle \Pr(X\geq \mu +t)<e^{-2t^{2}/(n(b-a)^{2})}.}$

Os limites nas seções seguintes para variáveis de Bernoulli são derivados usando que, para uma variável de Bernoulli ${\displaystyle X_{i}}$ com probabilidade p de ser igual a 1,

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

Pode-se encontrar várias formas de limites de Chernoff: a forma aditiva original (que fornece um limite para o erro absoluto) ou a forma multiplicativa mais prática (que limita o erro relativo à média).

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,^[10] 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,^[11]

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

O seguinte teorema é devido a Wassily Hoeffding^[12] 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.

Os limites de Chernoff têm aplicações úteis em balanceamento de conjuntos [en] e roteamento de pacotes em redes esparsas [en].

O problema de balanceamento de conjuntos surge ao projetar experimentos estatísticos. Tipicamente, ao projetar um experimento estatístico, dadas as características de cada participante, precisamos saber como dividir os participantes em dois grupos disjuntos de modo que cada característica seja aproximadamente equilibrada entre os dois grupos.^[13]

Os limites de Chernoff também são usados para obter limites apertados para problemas de roteamento de permutação, que reduzem o congestionamento de rede [en] ao rotear pacotes em redes esparsas.^[13]

Os limites de Chernoff são utilizados na teoria do aprendizado computacional para provar que um algoritmo de aprendizado é provavelmente aproximadamente correto [en], ou seja, com alta probabilidade, o algoritmo tem pequeno erro em um conjunto de dados de treinamento suficientemente grande.^[14]

Os limites de Chernoff podem ser usados efetivamente para avaliar o "nível de robustez" de uma aplicação/algoritmo ao explorar seu espaço de perturbação com randomização.^[15] O uso do limite de Chernoff permite abandonar a forte—e majoritariamente irrealista—hipótese de pequena perturbação (a magnitude da perturbação é pequena). O nível de robustez pode ser usado para validar ou rejeitar uma escolha algorítmica específica, uma implementação de hardware ou a adequação de uma solução cujos parâmetros estruturais são afetados por incertezas.

Um uso simples e comum dos limites de Chernoff é para "reforçar" algoritmos randomizados. Se um algoritmo produz uma estimativa que é a resposta desejada com probabilidade p > 1/2, pode-se obter uma taxa de sucesso maior executando o algoritmo ${\displaystyle n=\log(1/\delta )2p/(p-1/2)^{2}}$ vezes e retornando a estimativa produzida por mais de n/2 execuções do algoritmo. (Não pode haver mais de uma estimativa.) Assumindo que essas execuções do algoritmo são independentes, a probabilidade de que mais de n/2 das estimativas estejam corretas é igual à probabilidade de que a soma de variáveis aleatórias de Bernoulli independentes X_k que são 1 com probabilidade p seja maior que n/2. Isso pode ser mostrado como sendo pelo menos ${\displaystyle 1-\delta }$ via o limite de Chernoff multiplicativo (Corolário 13.3 nas notas de aula de Sinclair, μ = np).:^[16]

${\displaystyle \Pr \left[X>{n \over 2}\right]\geq 1-e^{-n\left(p-1/2\right)^{2}/(2p)}\geq 1-\delta }$

Rudolf Ahlswede e Andreas Winter introduziram um limite de Chernoff para variáveis aleatórias com valores matriciais.^[17] A seguinte versão da desigualdade pode ser encontrada no trabalho de Tropp.^[18]

Seja M₁, ..., M_t variáveis aleatórias independentes com valores matriciais tais que ${\displaystyle M_{i}\in \mathbb {C} ^{d_{1}\times d_{2}}}$ e ${\displaystyle \mathbb {E} [M_{i}]=0}$. Denote por ${\displaystyle \lVert M\rVert }$ a norma de operador da matriz ${\displaystyle M}$. Se ${\displaystyle \lVert M_{i}\rVert \leq \gamma }$ for válido quase certamente para todo ${\displaystyle i\in \{1,\ldots ,t\}}$, então, para todo ε > 0,

Leonard E. Parker Jr.

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

Note que, para concluir que o desvio de 0 é limitado por ε com alta probabilidade, precisamos escolher um número de amostras ${\displaystyle t}$ proporcional ao logaritmo de ${\displaystyle d_{1}+d_{2}}$. Em geral, infelizmente, uma dependência em ${\displaystyle \log(\min(d_{1},d_{2}))}$ é inevitável: considere, por exemplo, uma matriz de sinal aleatório diagonal de dimensão ${\displaystyle d\times d}$. A norma de operador da soma de t amostras independentes é precisamente o desvio máximo entre d caminhadas aleatórias independentes de comprimento t. Para alcançar um limite fixo no desvio máximo com probabilidade constante, é fácil ver que t deve crescer logaritmicamente com d neste cenário.^[19]

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.

A seguinte variante do limite de Chernoff pode ser usada para limitar a probabilidade de que uma maioria em uma população se torne uma minoria em uma amostra, ou vice-versa.^[20]

Suponha que haja uma população geral A e uma subpopulação B ⊆ A. Marque o tamanho relativo da subpopulação (|B|/|A|) por r.

Suponha que escolhamos um inteiro k e uma amostra aleatória S ⊂ A de tamanho k. Marque o tamanho relativo da subpopulação na amostra (|B∩S|/|S|) por r_S.

Então, para toda fração d ∈ [0,1]:

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

Em particular, se B for uma maioria em A (ou seja, r > 0.5), podemos limitar a probabilidade de que B permaneça maioria em S (r_S > 0.5) tomando: d = 1 − 1/(2r):^[21]

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

Esse limite não é, de forma alguma, apertado. Por exemplo, quando r = 0.5, obtemos um limite trivial Prob > 0.

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.

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.

• 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 
• Chernoff, H. (1981). «A Note on an Inequality Involving the Normal Distribution». Annals of Probability. 9 (3): 533–535. JSTOR 2243541. MR 614640. Zbl 0457.60014. doi:10.1214/aop/1176994428 
• Hagerup, T.; Rüb, C. (1990). «A guided tour of Chernoff bounds». Information Processing Letters. 33 (6). 305 páginas. doi:10.1016/0020-0190(90)90214-I 
• Nielsen, F. (2011). «An Information-Geometric Characterization of Chernoff Information». IEEE Signal Processing Letters. 20 (3): 269–272. arXiv:1102.2684. doi:10.1109/LSP.2013.2243726