Teorema de Sanov

Em teoria da informação, o teorema de Sanov dá um limite à probabilidade de observar uma sequência atípica de amostras a partir de uma dada distribuição de probabilidade.

Definição

Considere

$A$

um conjunto de distribuições de probabilidade sobre um alfabeto

$X$

e considere

$q$

uma distribuição arbitrária sobre

$X$

, sendo que

$q$

pode ou não estar em

$A$

. Suponha que são retiradas

$n$

amostras independentes e identicamente distribuídas a partir de

$q$

, representadas pelo vetor

$x^n=x_1,x_2,\dots ,x_n$

. Além disto, deseja-se saber se a distribuição empírica,

${\hat{p}}_{x^n}$

, das amostras cai no interior do conjunto

$A$

— formalmente, escreve-se

$\{x^n:{\hat{p}}_{x^n}\in A\}$

. Então,

$q^n(x^n)\le (n+1{)}^{|X|}{2}^{-n{D}_{\mathrm{K}\mathrm{L}}(p^{*}||q)},$

em que

• $q^n(x^n)$ é uma abreviação para $q(x_1)q(x_2)\cdots q(x_n)$ e
• $p^{*}$ é a projeção de informação de $q$ sobre $A$.

Em palavras, a probabilidade de retirar uma distribuição atípica é proporcional à divergência de Kullback–Leibler da distribuição verdadeira à distribuição atípica. No caso em que consideramos um conjunto de possíveis distribuições atípicas, há uma distribuição atípica dominante, dada pela projeção de informação.

Além disto, se

$A$

for o fecho de seu interior,

$\underset{n\to \mathrm{\infty }}{\lim }\frac{1}{n}\log q^n(x^n)=-D_{\mathrm{K}\mathrm{L}}(p^{*}||q).$