Teorema de Sanov - Enciclopedia

En matemáticas y teoría de la información, el teorema de Sanov proporciona un límite sobre 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 desviaciones grandes, el teorema de Sanov identifica la función de tasa para las desviaciones grandes 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

x^n = (x_1, x_2, …, x_n).

Entonces, tenemos el siguiente límite sobre la probabilidad de que la medida empírica

\hat{p}_{x^n}

de las muestras caiga dentro del conjunto A:

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

donde

q^n

es la distribución de probabilidad conjunta sobre X^n, y

p^*

es el proyector de información de q sobre A.

La divergencia de Kullback-Leibler (KL), dada por

D_{\mathrm{KL}}(P \parallel Q) = \sum_{x \in \mathcal{X}} P(x) \log \frac{P(x)}{Q(x)},

es:

D_{\mathrm{KL}}(P \parallel Q) = \sum_{x \in \mathcal{X}} P(x) \log \frac{P(x)}{Q(x)}.

En términos, la probabilidad de extraer una distribución atípica está limitada por una función de la divergencia de KL desde la distribución verdadera hasta la atípica; en el caso de considerar un conjunto de posibles distribuciones atípicas, hay una distribución atípica dominante, dada por el proyector de información.

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

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

Explicación técnica

Definir:

\text{Σ} es un conjunto finito con tamaño \geq 2. Entendido como "alfabeto".

\Delta(\text{Σ}) es el simplex generado por el alfabeto. Es un subconjunto de \mathbb{R}^{\text{Σ}}.

L_n es una variable aleatoria que toma valores en \Delta(\text{Σ}). Extraiga n muestras de la distribución \mu, luego L_n es el vector de probabilidad de frecuencia para la muestra.

\text{L}_n es el espacio de valores que puede tomar L_n. En otras palabras, es

\left\{ \left( \frac{a_1}{n}, \ldots, \frac{a_{|\Sigma|}}{n} \right): \sum_i a_i = n, a_i \in \mathbb{N} \right\}

Entonces, el teorema de Sanov establece:

Para cada subconjunto medible S \in \Delta(\text{Σ}),

-\inf_{\nu \in int(S)} D(\nu \parallel \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 \parallel \mu)

Para cada subconjunto abierto U \in \Delta(\text{Σ}),

-\lim_{n} \lim_{\nu \in U \cap \text{L}_n} D(\nu \parallel \mu) = \lim_{n} \frac{1}{n} \ln P_{\mu}(L_n \in S) = -\inf_{\nu \in U} D(\nu \parallel \mu)

Aquí, int(S) significa el interior, y cl(S) significa el cierre.