15.2 Princípio dos Grandes Desvios

A Desigualdade de Concentração de Chernoff diz que a probabilidade de um grande desvio decai, pelo menos, exponencialmente rápido. Porém, em muitos casos, vale algo muito mais forte: a velocidade de decaimento é exatamente exponencial, com uma taxa que pode ser descrita quase explicitamente.

Definição 15.4 (Função taxa).

Seja $X$ uma variável aleatória. Definimos a função taxa $I$ associada à distribuição de $X$ , como a função $I:\mathbb{R}\to[0,+\infty]$ dada por

I(a)=\sup_{t\in\mathbb{R}}\left[\mathclap{\phantom{\big{|}}}at-\log M(t)\right],

(15.5)

onde $M(t)$ é a função geradora de momentos da variável $X$ .

Podemos pensar na função taxa como uma tentativa de obter a melhor estimativa possível a partir de (15.2). A razão pela qual a função $I$ merece esse nome é que, uma vez que maximizamos $[at-\log M(t)]$ sobre todo $t$ , a desigualdade (15.2) deixa de ser apenas mais uma cota superior, sendo de fato a melhor cota superior possível. A maximização em (15.5) é conhecida como a transformada de Legendre, isto é, a função taxa é a transformada de Legendre do logaritmo da função geradora de momentos.

Dado $A\subseteq\mathbb{R}$ , para descrever a maneira mais fácil (ou menos difícil) de $\frac{S_{n}}{n}$ estar em $A$ , vamos denotar

I(A)=\inf_{a\in A}I(a).

Se $A$ for um intervalo da reta, denotaremos por $A^{\circ}$ o seu interior (o intervalo excluindo as extremidades de $A$ ) e por $\bar{A}$ o seu fecho (o intervalo incluindo as extremidades de $A$ caso sejam números reais), respectivamente.

Teorema 15.6 (Princípio dos Grandes Desvios de Cramér).

Sejam $(X_{n})_{n}$ variáveis aleatórias i.i.d., com distribuição comum $X$ , e $J$ um intervalo de $\mathbb{R}$ . Se $I(J)<\infty$ , então

\displaystyle e^{-I(J^{\circ})\cdot n+o(n)}\leqslant\mathbb{P}\left(\tfrac{S_{% n}}{n}\in J\right)\leqslant e^{-I(\bar{J})\cdot n+o(n)},

onde $I$ é a função taxa da variável $X$ . Em particular, quando $I(J^{\circ})=I(\bar{J})$ , temos a taxa exata de decaimento exponencial para estas probabilidades:

\mathbb{P}\left(\tfrac{S_{n}}{n}\in J\right)=e^{-I(J)\cdot n+o(n)}.

Caso $I(\bar{J})=+\infty$ , vale

\mathbb{P}\left(\tfrac{S_{n}}{n}\in J\right)\leqslant e^{-cn+o(n)}

para todo $c\in\mathbb{R}$ .

A demonstração do teorema acima será dada na próxima seção. Antes disso, vamos discutir a relação entre a função geradora de momentos, $M$ , e sua transformada de Legendre, a função taxa $I$ .

Vejamos como encontrar $I(a)$ graficamente e algebricamente. No caso de o supremo em (15.5) ser atingido em $t=y$ para algum $y$ no interior do intervalo onde $M$ é finita, a derivada de $at-\log M(t)$ se anula em $t=y$ , donde

a=\frac{M^{\prime}(y)}{M(y)}.

(15.7)

Às vezes é possível expressar $y$ em termos de $a$ , e assim calcular $I$ por

I(a)=a\cdot y-\log M(y),\quad y=y(a).

Esse processo de encontrar $y$ tal que $(\log M)^{\prime}(y)=a$ e expressar $I(a)=ay-\log M(y)$ está ilustrado na Figura 15.1 e nos exemplos abaixo.

Reciprocamente, se existe $y$ tal que $(\log M)^{\prime}(y)=a$ , então o supremo em (15.5) é atingido em $t=y$ , pois, como mostraremos mais abaixo, $\log M$ é uma função convexa.

Figura 15.1: Obtenção da função taxa a partir da função $\log M_{X}$ .

Exemplo 15.8.

Se $X\sim\mathcal{N}(\mu,\sigma^{2})$ , temos

\log M(t)=\frac{\sigma^{2}t^{2}}{2}+t\mu,

assim

a=(\log M)^{\prime}(y)=\sigma^{2}y+\mu,\qquad y=\frac{a-\mu}{\sigma^{2}},

portanto,

I(a)=\frac{a(a-\mu)}{\sigma^{2}}-\left[\frac{(a-\mu)^{2}}{2\sigma^{2}}+\frac{% \mu(a-\mu)}{\sigma^{2}}\right]=\frac{(a-\mu)^{2}}{2\sigma^{2}},\quad a\in% \mathbb{R}.\qed

Exemplo 15.9.

Se $X\sim\mathop{\mathrm{Poisson}}\nolimits(\lambda)$ , temos

\log M(t)=\lambda(e^{t}-1).

Analisando o gráfico de $\log M(t)$ , observamos que o supremo de $at-\log M(t)$ é atingido em algum $y\in\mathbb{R}$ somente se $a>0$ . Neste caso,

a=(\log M)^{\prime}(y)=\lambda e^{y},\qquad y=\log\tfrac{a}{\lambda},

I(a)=ay-\log M(y)=a\log\tfrac{a}{\lambda}-a+\lambda.

Se $a=0$ , o supremo vale $\lambda$ , pois $\log M(t)$ tende a $-\lambda$ quando $t\to-\infty$ . Se $a<0$ , o supremo vale $+\infty$ pois $at-\log M(t)\geqslant at-\lambda$ para todo $t<0$ .

Em resumo,

I(a)=\begin{cases}+\infty,&a<0,\\ \lambda,&a=0,\\ a\log\tfrac{a}{\lambda}-a+\lambda,&a>0.\\ \end{cases}

Os casos $a=0$ e $a<0$ refletem o fato de que variáveis de Poisson nunca tomam valores negativos, e tomam o valor zero com probabilidade $e^{-\lambda}$ . ∎

Exercício 15.10.

Calcule a função taxa da variável $X$ nos seguintes casos:

(a)

$X\sim\mathop{\mathrm{Bernoulli}}\nolimits(p)$ .
(b)

$X\sim\mathop{\mathrm{Exp}}\nolimits(\lambda)$ .
(c)

$X=\mu$ q.c. ∎

Como dito anteriormente, $\log M$ é uma função convexa, a função I também goza da mesma propriedade.

Proposição 15.11.

As funções $I$ e $\log M$ são convexas.

Demonstração.

Consideremos inicialmente a função $I$ . Sejam $0<\alpha<1$ e $\beta=1-\alpha$ . Para $a_{1}$ e $a_{2}\in\mathbb{R}$ ,

	$\displaystyle I(\alpha a_{1}+\beta a_{2})$	$\displaystyle=\sup_{t\in\mathbb{R}}\left[\mathclap{\phantom{\big{\|}}}(\alpha a% _{1}+\beta a_{2})t-(\alpha+\beta)\log M(t)\right]$
		$\displaystyle=\sup_{t\in\mathbb{R}}\left[\mathclap{\phantom{\big{\|}}}\alpha(a_% {1}t-\log M(t))+\beta(a_{2}t-\log M(t))\right]$
		$\displaystyle\leqslant\sup_{t\in\mathbb{R}}\left[\mathclap{\phantom{\big{\|}}}% \alpha(a_{1}t-\log M(t))\right]+\sup_{t\in\mathbb{R}}\left[\mathclap{\phantom{% \big{\|}}}\beta(a_{2}t-\log M(t))\right]$
		$\displaystyle=\alpha I(a_{1})+\beta I(a_{2}),$

o que mostra que a função taxa $I$ é convexa. Passamos agora à convexidade de $\log M$ . Sejam $t_{1}$ e $t_{2}\in\mathbb{R}$ . Usando a Desigualdade de Hölder (Apêndice D.7),

	$\displaystyle\log M(\alpha t_{1}+\beta t_{2})$	$\displaystyle=\log\mathbb{E}\left[e^{\alpha t_{1}X}\cdot e^{\beta t_{2}X}\right]$
		$\displaystyle\leqslant\log\left\{\left(\mathbb{E}\left[\left(e^{\alpha t_{1}X}% \right)^{\frac{1}{\alpha}}\right]\right)^{\alpha}\left(\mathbb{E}\left[\left(e% ^{\beta t_{2}X}\right)^{\frac{1}{\beta}}\right]\right)^{\beta}\right\}$
		$\displaystyle=\alpha\log\mathbb{E}[e^{t_{1}X}]+\beta\log\mathbb{E}[e^{t_{2}X}]$
		$\displaystyle=\alpha\log M(t_{1})+\beta\log M(t_{2}),$

o que conclui a prova. ∎

	$\displaystyle I(\alpha a_{1}+\beta a_{2})$	$\displaystyle=\sup_{t\in\mathbb{R}}\left[\mathclap{\phantom{\big{\|}}}(\alpha a% _{1}+\beta a_{2})t-(\alpha+\beta)\log M(t)\right]$
		$\displaystyle=\sup_{t\in\mathbb{R}}\left[\mathclap{\phantom{\big{\|}}}\alpha(a_% {1}t-\log M(t))+\beta(a_{2}t-\log M(t))\right]$
		$\displaystyle\leqslant\sup_{t\in\mathbb{R}}\left[\mathclap{\phantom{\big{\|}}}% \alpha(a_{1}t-\log M(t))\right]+\sup_{t\in\mathbb{R}}\left[\mathclap{\phantom{% \big{\|}}}\beta(a_{2}t-\log M(t))\right]$
		$\displaystyle=\alpha I(a_{1})+\beta I(a_{2}),$