15.1 Desigualdade de concentração

Seja $X$ uma variável aleatória integrável com média $\mu$ . Sejam $(X_{n})_{n}$ independentes e com a mesma distribuição de $X$ , e tome $S_{n}=X_{1}+\dots+X_{n}$ .

A Lei dos Grandes Números de Tchebyshev para este caso foi provada da seguinte forma: dado qualquer $a\in(\mu,+\infty)$ ,

\mathbb{P}\left(\tfrac{S_{n}}{n}\geqslant a\right)\leqslant\mathbb{P}\left((% \tfrac{S_{n}}{n}-\mu)^{2}\geqslant(a-\mu)^{2}\right)\leqslant\tfrac{1}{(a-\mu)% ^{2}}\mathbb{E}\left(\tfrac{S_{n}}{n}-\mu\right)^{2}=\tfrac{\mathbb{V}X}{(a-% \mu)^{2}}\cdot\frac{1}{n}

A desigualdade acima diz que, quando $\mathbb{E}X^{2}<\infty$ , a probabilidade de $\tfrac{S_{n}}{n}$ diferir de $\mu$ por mais que uma quantidade fixa $a-\mu$ decai pelo menos tão rápido quanto $\frac{1}{n}$ . Na prova da Lei dos Grandes Números de Cantelli, vimos que, quando $\mathbb{E}X^{4}<\infty$ , esta probabilidade decai pelo menos tão rápido quanto $\frac{1}{n^{2}}$ . Em geral, se $\mathbb{E}X^{2k}<\infty$ ela decai pelo menos tão rápido quanto $\frac{1}{n^{k}}$ .

Tentaremos agora obter estimativas melhores usando momentos de $e^{tX}$ ao invés de $X^{2k}$ . Para todos $t\geqslant 0$ e $a\in(\mu,+\infty)$ ,

\mathbb{P}\left(\tfrac{S_{n}}{n}\geqslant a\right)\leqslant\mathbb{P}\left[e^{% tS_{n}}\geqslant e^{atn}\right]\leqslant\tfrac{1}{e^{atn}}\mathbb{E}[e^{tS_{n}% }]={e^{-atn}}M(t)^{n}={e^{-[at-\log M(t)]n}},

(15.1)

onde $M(t)=\mathbb{E}[e^{tX}]$ é a função geradora de momentos de $X$ ; observe que na penúltima igualdade utilizamos que as variáveis $(X_{n})$ são i.i.d com distribuição comum $X$ . De modo análogo, para $a\in(-\infty,\mu)$ e $t\leqslant 0$ , obtemos

\mathbb{P}\left(\tfrac{S_{n}}{n}\leqslant a\right)\leqslant{e^{-[at-\log M(t)]% n}}.

(15.2)

Portanto, se mostrarmos que a expressão entre colchetes é positiva para algum $t$ , teremos estabelecido que essa probabilidade de fato decai pelo menos exponencialmente rápido. Sabemos que a função geradora de momentos é finita em um intervalo que contém o ponto $t=0$ . Denotaremos os extremos desse intervalo por $\mathcal{D}_{M}^{-}\leqslant 0$ e $\mathcal{D}_{M}^{+}\geqslant 0$ .

Teorema 15.3 (Desigualdade de Concentração de Chernoff).

Sejam $(X_{n})_{n}$ variáveis aleatórias i.i.d. com distribuição comum $X$ , média $\mu$ , função geradora de momentos $M(t)$ e $S_{n}=X_{1}+\dots+X_{n}$ . Se $\mathcal{D}_{M}^{+}>0$ , então, para qualquer $a>\mu$ , existe $t>0$ tal que $[at-\log M(t)]>0$ . Como

\mathbb{P}\left(\tfrac{S_{n}}{n}\geqslant a\right)\leqslant{e^{-[at-\log M(t)]% n}},

segue que essa probabilidade decai pelo menos exponencialmente rápido em $n$ . Analogamente, se $\mathcal{D}_{M}^{-}<0$ e $a<\mu$ , então $[at-\log M(t)]>0$ para algum $t<0$ e a estimativa em (15.2) decai, pelo menos, exponencialmente rápido.

Demonstração.

Suponha que $\mathcal{D}_{M}^{+}>0$ e seja $a>\mu$ . Consideramos inicialmente o caso em que $\mathcal{D}_{M}^{-}<0$ . Pela Proposição 10.7, $(\log M)^{\prime}(0)=M^{\prime}(0)=\mu<a$ e, por conseguinte, $[at-\log M(t)]>0$ para todo $t>0$ suficientemente pequeno, provando o teorema neste caso.

Consideramos agora o caso geral. Para reduzir ao caso em que $\mathcal{D}_{M}^{-}<0$ , vamos truncar as variáveis $X_{n}$ . Para cada $n$ e $k$ , defina $X_{n;k}=X_{n}\mathds{1}_{\{X_{n}\geqslant-k\}}$ . Pelo Teorema da Convergência Dominada, $\lim_{k}\mathbb{E}X_{n;k}=\mu$ e $\lim_{k}(as-\log\mathbb{E}[e^{sX_{n;k}}])=as-\log M(s)$ para todo $s\in[0,\mathcal{D}_{M}^{+})$ . Tome $k$ tal que $\mathbb{E}X_{n;k}<a$ . Pelo caso anterior, podemos tomar $t>0$ tal que $(at-\log\mathbb{E}[e^{tX_{n;k}}])>0$ . Como $X_{n}\leqslant X_{n;k}$ , vale $[at-\log M(t)]>0$ , concluindo a prova do teorema.

A segunda parte do teorema, com $\mathcal{D}_{M}^{-}<0$ e $a<\mu$ , segue da primeira parte trocando-se os sinais de $a$ , $\mu$ , $t$ e $X$ . ∎