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},\ldots ,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})\leq (n+1)^{|X|}2^{-nD_{\mathrm {KL} }(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,

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