Teorema de Sanov

En matemáticas y teoría de la información , el teorema de Sanov establece una cota para la probabilidad de observar una secuencia atípica de muestras de una distribución de probabilidad dada . En el lenguaje de la teoría de grandes desviaciones , el teorema de Sanov identifica la función de tasa para grandes desviaciones de la medida empírica de una secuencia de variables aleatorias independientes e idénticamente distribuidas (i.i.d.).

Sea A un conjunto de distribuciones de probabilidad sobre un alfabeto X , y sea q una distribución arbitraria sobre X (donde q puede o no estar en A ). Supongamos que extraemos n muestras i.i.d. de q , representadas por el vector${\displaystyle x^{n}=(x_{1},x_{2},\ldots ,x_{n})}$. Entonces, tenemos la siguiente cota sobre la probabilidad de que la medida empírica${\displaystyle {\hat {p}}_{x^{n}}}$de las muestras se encuentra dentro del conjunto A :

${\displaystyle q^{n}({\hat {p}}_{x^{n}}\in A)\leq (n+1)^{|X|}2^{-nD_{\mathrm {KL} }(p^{*}||q)}}$,

dónde

• ${\displaystyle q^{n}}$es la distribución de probabilidad conjunta sobre${\displaystyle X^{n}}$, y
• ${\displaystyle p^{*}}$es la proyección de información de q sobre A.
• ${\displaystyle D_{\mathrm {KL} }(P\|Q)}$La divergencia KL viene dada por:${\displaystyle D_{\mathrm {KL} }(P\|Q)=\sum _{x\in {\mathcal {X}}}P(x)\log {\frac {P(x)}{Q(x)}}.}$

En otras palabras, la probabilidad de obtener una distribución atípica está limitada por una función de la divergencia KL entre la distribución verdadera y la atípica; en el caso de que consideremos un conjunto de posibles distribuciones atípicas, existe una distribución atípica dominante, dada por la proyección de información.

Además, si A es un conjunto cerrado, entonces

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

Definir:

• ${\textstyle \Sigma }$es un conjunto finito con tamaño${\textstyle \geq 2}$. Entendido como “alfabeto”.
• ${\textstyle \Delta (\Sigma )}$es el símplex generado por el alfabeto. Es un subconjunto de${\textstyle \mathbb {R} ^{\Sigma }}$.
• ${\textstyle L_{n}}$es una variable aleatoria que toma valores en${\textstyle \Delta (\Sigma )}$. Llevar${\textstyle n}$muestras de la distribución${\textstyle \mu }$, entonces${\textstyle L_{n}}$es el vector de probabilidad de frecuencia para la muestra.
• ${\textstyle {\mathcal {L}}_{n}}$es el espacio de valores que${\textstyle L_{n}}$puede tomar. En otras palabras, es

$${\displaystyle \{(a_{1}/n,\dots ,a_{|\Sigma |}/n):\sum _{i}a_{i}=n,a_{i}\in \mathbb {N} \}}$$Entonces, el teorema de Sanov establece: ^{[ 1 ]}

• Para cada subconjunto medible${\textstyle S\in \Delta (\Sigma)}$,$${\displaystyle -\inf _{\nu \in int(S)}D(\nu \|\mu )\leq \liminf _{n}{\frac {1}{n}}\ln P_{\mu }(L_{n}\in S)\leq \limsup _{n}{\frac {1}{n}}\ln P_{\mu }(L_{n}\in S)\leq -\inf _{\nu \in cl(S)}D(\nu \|\mu )}$$
• Para cada subconjunto abierto${\estilo de texto U\en \Delta (\Sigma )}$,$${\displaystyle -\lim _{n}\lim _{\nu \in U\cap {\mathcal {L}}_{n}}D(\nu \|\mu )=\lim _{n}{\frac {1}{n}}\ln P_{\mu }(L_{n}\in S)=-\inf _{\nu \in U}D(\nu \|\mu )}$$

Aquí,${\displaystyle int(S)}$significa el interior , y${\displaystyle cl(S)}$significa el cierre .

• Cover, Thomas M.; Thomas, Joy A. (2006). Elementos de la teoría de la información (2.ª ed.). Hoboken, Nueva Jersey: Wiley Interscience. 362  págs . ISBN  9780471241959.

• Sanov, IN (1957) "Sobre la probabilidad de grandes desviaciones de variables aleatorias". Mat. Sbornik 42(84), No. 1, 11–44.
• Санов, И. Н. (1957) "О вероятности больших отклонений случайных величин". МАТЕМАТИЧЕСКИЙ СБОРНИК 42(84), núm. 1, 11–44.