3.7 Princípio de Grandes Desvios

A primeira tarefa nossa será otimizar a estimativa grosseira feita na seção anterior. Essas estimativas são chamadas de estimativas de grandes desvios, pois se referem a probabilidades que a média empírica de $X_{i}$ se desvie de sua esperança por um valor constante $a$ . Futuramente no curso estudaremos as probabilidades de que esse desvio seja de ordem $a_{n}\to 0$ que são chamados de desvios moderados ou flutuações, dependendo se a probabilidade de desvio converge a zero ou não.

{theorem}

[Princípio de Grandes Desvios - cota superior] Consideramos variáveis aleatórias \iid $X_{1},X_{2},\dots$ tais que $\phi_{X_{1}}(s)<\infty$ , para todo $s\in(-\delta,\delta)$ . Então, para $a>0$ ,

P\big{[}X_{1}+\dots+X_{n}\geq\big{(}m+a\big{)}n\big{]}\leq\ex{-\psi_{X_{1}}(m+% a)n},

(3.75)

onde $m=E(X_{1})$ e

\psi_{X_{1}}(x)=\sup_{s\geq 0}\big{\{}xs-\log\big{(}\phi_{X_{1}}(s)\big{)}\big% {\}}

(3.76)

é chamada função taxa.

É importante observar que para estimar $P\big{[}X_{1}+\dots+X_{n}\leq(m-a)n\big{]}$ , basta considerarmos $X^{\prime}_{i}=-X_{i}$ ao utilizar o teorema acima.

Demonstração.

Já sabemos que, para todo $s\geq 0$ ,

\begin{split}P\big{[}X_{1}&+\dots+X_{n}\geq\big{(}m+a\big{)}n\big{]}\leq\phi_{% X_{1}}^{n}(s)\ex{-s(m+a)n}\\[2.84526pt] &=\ex{\log\big{(}\phi_{X_{1}}(s)\big{)}n-s(m+a)n}\\ &=\ex{-\big{(}(m+a)s-\log\big{(}\phi_{X_{1}}(s)\big{)}\big{)}n}\\ \end{split}

(3.77)

O que termina a prova do teorema se tomamos o ínfimo em $s\geq 0$ . ∎

{exercise}

Calcule $\psi_{X}(a)$ quando $X$ é distribuída como $\Ber(p)$ , $U_{[0,1]}$ e $\Exp(\lambda)$ .

{exercise}

Na Nova Caledônia, temos $k$ habitantes. Seja $f:\{1,\dots,k\}\to\{0,1\}$ uma função que indica a intenção de voto de cada cidadão. Mais precisamente, para cada habitante $i\in\{1,\dots,k\}$ , se $f(i)=0$ , então $i$ vota no candidato $0$ , enquanto se $f(i)=1$ , o cidadão $i$ vota no candidato $1$ . Para estimar o número $k_{1}=\#f^{-1}(\{1\})$ de pessoas que votam em $1$ , nós escolhemos variáveis aleatórias $Y_{i}$ i.i.d. com distribuição uniforme em $\{1,\dots,k\}$ e queremos estimar

\text{Err}_{n}(\epsilon)=P\Big{[}\Big{|}\frac{1}{n}\sum_{i=1}^{n}f(Y_{i})-% \frac{k_{1}}{k}\Big{|}>\epsilon\Big{]}.

(3.78)

Sabendo que $k$ é par e $k_{1}=k/2$ , então

a)

use o método do segundo momento para obter um $n$ tal que $\text{Err}_{n}(0.01)<0.02$ e um $n$ tal que $\text{Err}_{n}(0.01)<10^{-12}$ ,
b)

use o método do momento exponencial para obter resolver o ítem acima.

Compare os quatro resultados obtidos acima.

Vamos agora tomar um exemplo concreto para análise. Sejam $X_{1},X_{2},\dots$ variáveis aleatórias \iidcom distribuição $\Ber(1/2)$ , donde

\phi_{X_{1}}(s)=\frac{1}{2}(1+e^{s})\quad\text{e}\quad\psi_{X_{1}}(x)=\sup_{s% \geq 0}\{xs-\log(1+e^{s})+\log(2)\}.

(3.79)

Um cálculo simples nos mostra que, se $x<1$ , o mínimo acima é atingido no único ponto $s_{\text{max}}=\log(\tfrac{x}{1-x})$ . Portanto, podemos concluir do Teorema 3.7 que

\begin{split}P[X_{1}+\dots&+X_{n}>1/2+a]\leq\ex{-\psi_{X_{1}}(s_{\text{max}})n% }\\ &=\exp\Big{\{}-n\Big{(}b\log(b)+(1-b)\log(1-b)+\log(2)\Big{)}\Big{\}}\end{split}

(3.80)

Note que $P[X_{1}+\dots+X_{n}=n]=2^{-n}=\ex{-\log(2)n}=\ex{-\psi_{X_{1}}(1-)n}$ . Isso nos dá um forte indício de que talvez nossas cotas superiores não estejam tão longe de ser precisas. Para confirmar essa hipótese, precisamos obter cotas inferiores parecidas.

Figura 3.1: Funções taxa

\psi_{X}(b)

de uma variável

X

com distribuição

\Ber(1/2)

, e

\psi_{X^{\prime}}(b)

de uma variável com distribuição

\Ber(3/4)

, para

b\in(0,1)

Antes de buscar cotas inferiores para as probabilidades de desvio, vamos estabelecer algumas propriedades da função $\psi_{X}(b)$ . Primeiramente, quando podemos dizer que o supremo na definição de $\psi_{X}$ é atingido em algum $s_{\text{max}}$ ? Certamente, esse nem sempre é o caso, por exemplo se $X=m$ quase certamente, então $\phi_{X}(s)=e^{sm}$ e o supremo definindo $\psi_{X}(b)$ não é atingido se $b\neq m$ .

{lemma}

Seja $X$ uma variável aleatória tal que $\phi_{X}(s)<\infty$ para todo $s\in(-\delta,\delta)$ . Supondo $a\geq 0$ é tal que $P[X>m+a]>0$ , então existe $s_{\text{max}}\geq 0$ tal que

\psi_{X}(m+a)=(m+a)s_{\text{max}}-\log\big{(}\phi_{X}(s_{\text{max}})\big{)}.

(3.81)

Demonstração.

Por hipótese, existe $x>m+a$ tal que $p=P[X\geq x]>0$ , donde $\phi_{X}(s)\geq pe^{s(m+a)}$ . Dessa forma, $(m+a)s-\log\big{(}\phi_{X}(s)\big{)}\leq(m+a-x)s-\log(p)$ , que converge a menos infinito quando $s$ diverge. Isso, junto com a continuidade de $\phi_{X}$ implica a existência do $s_{\text{max}}$ desejado. ∎

{lemma}

Seja $X$ uma variável aleatória tal que $\phi_{X}(s)<\infty$ para todo $s\in(-\delta,\delta)$ . Então o conjunto onde a função $\psi_{X}(s)$ é finita é um intervalo, na qual $\psi_{X}$ é convexa e portanto contínua.

Demonstração.

Primeiramente, supomos que $a<b$ são tais que $\psi_{X}(a)$ e $\psi_{X}(b)$ são finitas. Logo, para todo $c\in(a,b)$ , temos que a função linear $cs$ é menor ou igual a $as\vee bs$ , daí

\begin{split}\psi_{X}(c)&=\sup_{s\geq 0}\{cs-\log(\phi_{X}(s))\}\leq\sup_{s% \geq 0}\{(as\vee bs)-\log(\phi_{X}(s))\}\\ &\leq\sup_{s\geq 0}\{as-\log(\phi_{X}(s))\}\vee\sup_{s\geq 0}\{bs-\log(\phi_{X% }(s))\}<\infty.\end{split}

(3.82)

Para mostrar que $\psi_{X}$ é convexa, observe que $\psi_{X}(x)$ é dada pelo supremo (para $s\geq 0$ ) das funções afins $x\mapsto xs-\psi_{X}(s)$ . Como o supremo de funções convexas é também convexo, obtemos o enunciado do lemma. ∎

{exercise}

Suponha que se $\phi_{X}(s)$ é finita para todo $s\in(-\delta,\delta)$ e mostre que

a)

na definição de $\psi_{X}(a)$ , poderíamos tomar o ínfimo em todos $s\in\mathbb{R}$ (ao invéz de $s\geq 0$ ) sem mudar o valor de $\psi_{X}(a)$ ,
b)

a função $\psi_{X}(s)$ é não negativa, semi-contínua inferior e convexa em seu domínio
c)

$\psi_{X}(a)$ se anula somente em $a=0$ e $\psi_{X}$ é crescente no seu domínio.

Buscaremos agora cotas inferiores para a probabilidade de obter um grande desvio. Gostaríamos que essas estimativas fossem o mais próximas possíveis das estimativas superiores obtidas acima. Certamente não podemos obter algo como

``P\big{[}X_{1}+\dots+X_{n}\geq\big{(}m+a\big{)}n\big{]}\geq\exp\{-\psi_{X_{1}% }(a)n\}",

(3.83)

pois senão isso nos daria uma igualdade o que é impossível, pois perdemos um pouco de precisão ao utilizar a desigualdade de Markov na cota superior.

Contudo, gostaríamos de entender se ao menos o expoente $\psi_{X_{1}}(a)$ na cota superior também possui algum papel na cota inferior. Isso é confirmado no seguinte resultado.

{theorem}

[Princípio de Grandes Desvios - cota inferior] Sejam $X_{1},X_{2},\dots$ variáveis aleatórias \iidcom $\phi_{X_{1}}(s)<\infty$ , para todo $s\in\mathbb{R}$ . Então, para todo $a>0$ ,

\liminf_{n\to\infty}\frac{1}{n}\log P\big{[}X_{1}+\dots+X_{n}\geq\big{(}m+a% \big{)}n\big{]}\geq-\psi_{X_{1}}(m+a),

(3.84)

onde novamente $m=E(X_{1})$ e $\psi_{X_{1}}(x)$ é definida como no Teorema 3.7.

Note que o resultado do teorema acima é mais fraco que o que vemos na equação (3.83), mas mostra que $\psi_{X_{1}}(a)$ é realmente o expoente correto no decaimento da probabilidade de grandes desvios.

Um corolário dos Teoremas 3.7 e 3.1 é o seguinte

{corollary}

Se $X_{1},X_{2},\dots$ variáveis aleatórias \iidcom $\phi_{X_{1}}(s)<\infty$ , para todo $s\in\mathbb{R}$ , então

\lim_{n\to\infty}\frac{1}{n}\log P\big{[}X_{1}+\dots+X_{n}\geq\big{(}m+a\big{)% }n\big{]}=-\psi_{X_{1}}(m+a).

(3.85)

A idéia da prova é transformar a distribuição de $X_{i}$ , usando uma exponencial como derivada de Radon-Nikodim. Essa nova distribuição possuirá esperança maior que $m+a$ , de forma que se tomamos a média de variáveis \iid $X^{\prime}_{1},\dots,X^{\prime}_{n}$ distribuídas dessa forma, obteremos algo que se concentra acima de $m+a$ . Finalmente, o preço pago para que as variáveis $X_{i}$ se comportem como as $X^{\prime}_{i}$ será aproximadamente $\exp\{-\psi_{X_{1}}(m+a)\}$ , como desejado para nossa cota inferior.

Demonstração.

Primeiramente, consideraremos o caso $P[X_{1}\leq m+a]=1$ , que se assemelha ao caso que analizamos acima $(\Ber(1/2)\leq 1)$ . Nesse caso, temos

\begin{split}P\big{[}X_{1}+\dots+X_{n}\geq\big{(}m+a\big{)}n\big{]}&=P[X_{i}=m% +a,\text{ para todo $i\leq n$}]\\ &=P[X_{1}=m+a]^{n}.\end{split}

Donde o limite acima é igual a $\log(P[X_{1}=m+a])$ . Mas por outro lado,

\begin{split}-\psi_{X_{1}}(m+a)&=\inf_{s\geq 0}\big{\{}\log\big{(}E(\ex{s(X_{1% })})\big{)}-(m+a)s\big{\}}=\inf_{s\geq 0}\big{\{}\log\big{(}E(\ex{s(X_{1}-m-a)% })\big{)}\big{\}}\\ &\leq\liminf_{s\to\infty}\;\log\big{(}E(\ex{s(X_{1}-m-a)})\big{)}=\log\big{(}P% [X_{1}=m+a]\big{)},\end{split}

pelo Teorema da Convergência Dominada, demonstrando o teorema nesse caso especial.

Suponhamos agora que $P[X_{1}>m+a]>0$ , o que implica que para $b>m+a$ suficientemente próximo de $m+a$ , temos $P[X_{1}>b]>0$ . Observe que basta mostrar que para todo $b>a$ satisfazendo $P[X_{1}>b]>0$ e para todo $\delta>0$ , temos

\liminf_{n}\frac{1}{n}\log\Big{(}P\Big{[}\frac{X_{1}+\dots+X_{n}}{n}\in(b-% \delta,b+\delta)\Big{]}\Big{)}\geq-\psi_{X_{1}}(b),

(3.86)

pois a função $\psi_{X_{1}}(x)$ é convexa, portanto contínua.

Vamos definir uma nova distribuição $\nu$ com derivada de Radon-Nikodim

\frac{\d{\nu}}{\d{P}_{X_{1}}}=\frac{1}{Z_{\sigma}}\ex{\sigma x}.

(3.87)

Observamos primeiramente que o valor de $\sigma$ ainda não foi escolhido. Além disso após escolhido $\sigma$ , teremos que calcular a constante de normalização $Z_{\sigma}$ de forma que $\nu$ seja uma probabilidade.

Escolheremos $\sigma\geq 0$ como no Lema 3.7, isto é, tal que $\psi_{X_{1}}(b)=b\sigma-\log\big{(}\phi_{X_{1}}(\sigma)\big{)}$ . Isso nos dá imediatamente que $Z_{\sigma}=E[\ex{\sigma X_{1}}]=\phi_{X_{1}}(\sigma)$ por definição.

Por diferenciabilidade de $\phi_{X_{1}}$ , o máximo deve ser assumido em um ponto de derivada zero para a função $\psi_{X_{1}}$ , ou seja

b=\frac{\phi_{X_{1}}^{\prime}(\sigma)}{\phi_{X_{1}}(\sigma)}\overset{\text{% Prop.\leavevmode\nobreak\ \ref{p:propried_phi}}}{=}\frac{E(X\ex{\sigma X})}{E(% \ex{\sigma X})}=\frac{E(X\ex{\sigma X})}{Z_{\sigma}}=\int x\nu(\d{x}).

3.6⁢E⁢(X⁢\ex⁢σ⁢X)E⁢(\ex⁢σ⁢X)=E⁢(X⁢\ex⁢σ⁢X)Zσ=∫x⁢ν⁢(x⋅).b=\frac{\phi_{X_{1}}^{\prime}(\sigma)}{\phi_{X_{1}}(\sigma)}\overset{\text{% Prop.\leavevmode\nobreak\ \ref{p:propried_phi}}}{=}\frac{E(X\ex{\sigma X})}{E(% \ex{\sigma X})}=\frac{E(X\ex{\sigma X})}{Z_{\sigma}}=\int x\nu(\d{x}). (3.88)

Isso implica que se uma variável aleatória tem distribuição $\nu$ , sua esperança é $b$ . É possível verificar que uma tal variável aleatória $X^{\prime}$ satisfaz obrigatoriamente $\phi_{X^{\prime}}(s)<\infty$ para todo $s\geq 0$ , donde $X^{\prime}\in\mathcal{L}^{p}$ para todo $p>1$ .

Como prometido, consideramos variáveis $X_{1}^{\prime},X_{2}^{\prime},\dots$ \iidcom distribuição $\nu$ . Pela lei fraca dos grandes números, para qualquer $\delta>0$ ,

\lim_{n}P\Big{[}\frac{X_{1}^{\prime}+\dots+X_{n}^{\prime}}{n}\in(b-\delta,b+% \delta)\Big{]}=1.

(3.89)

Finalmente vamos relacionar essa probabilidade à probabilidade definida em termos de $X_{i}$ , na qual estamos interessados.

\begin{split}P\Big{[}&\frac{X_{1}+\dots+X_{n}}{n}\in(b-\delta,b+\delta)\Big{]}% =\int_{x_{i};\big{|}\tfrac{1}{n}\sum_{i\leq n}x_{i}-b\big{|}<\delta}\;\;% \bigotimes_{i=1}^{n}(X_{1}\circ P)(\d{x}_{i})\\ &=Z_{\sigma}^{n}\int_{x_{i};\big{|}\tfrac{1}{n}\sum_{i\leq n}x_{i}-b\big{|}<% \delta}\;\;\ex{-\sigma\textstyle{\sum_{i=1}^{n}x_{i}}}\bigotimes_{i=1}^{n}(X_{% 1}^{\prime}\circ P)(\d{x}_{i})\\[5.69054pt] &\geq Z_{\sigma}^{n}\exp\{-(b+\delta)\sigma n\}P\Big{[}\frac{X_{1}^{\prime}+% \dots+X_{n}^{\prime}}{n}\in(b-\delta,b+\delta)\Big{]}.\end{split}

Tomando o logarítmo, dividindo por $n$ e tomando o liminf quando $n$ vai a infinito, recuperamos

\begin{split}\lim_{n}\frac{1}{n}\log\Big{(}P\Big{[}&\frac{X_{1}+\dots+X_{n}}{n% }\in(b-\delta,b+\delta)\Big{]}\Big{)}\geq\log(Z_{\sigma})-(b+\delta)\sigma\\ &=\log(\phi_{X_{1}}(\sigma))-(b+\delta)\sigma=-\psi_{X_{1}}(\sigma)-\delta% \sigma.\end{split}

(3.90)

Como isso vale para todo $\delta>0$ , provamos (3.86) o que conclui a prova do teorema. ∎

{exercise}

Mostre o Teorema 3.1 no caso em que $\phi_{X_{1}}(s)<\infty$ , para todo $s\in(-\delta,\delta)$ .