Conjunto típico

En teoría de la información , el conjunto típico es un conjunto de secuencias cuya probabilidad es cercana a dos elevado a la potencia negativa de la entropía de su distribución fuente. El hecho de que este conjunto tenga una probabilidad total cercana a uno es una consecuencia de la propiedad de equipartición asintótica (AEP), que es una especie de ley de los grandes números . La noción de tipicidad solo se refiere a la probabilidad de una secuencia y no a la secuencia en sí.

Esto tiene gran utilidad en la teoría de la compresión , ya que proporciona un medio teórico para comprimir datos, lo que nos permite representar cualquier secuencia X ⁿ utilizando nH ( X ) bits en promedio y, por lo tanto, justificar el uso de la entropía como una medida de información de una fuente.

La AEP también se puede probar para una gran clase de procesos ergódicos estacionarios , lo que permite definir un conjunto típico en casos más generales.

Secuencias (débilmente) típicas (tipicidad débil, tipicidad de entropía)

Si se extrae una secuencia x ₁ , ...,  x _n de una variable aleatoria independiente idénticamente distribuida (IID) X definida sobre un alfabeto finito , entonces el conjunto típico, A _ε ^{( n ) ( n ),} se define como aquellas secuencias que satisfacen: ${\displaystyle {\mathcal {X}}}$ ${\displaystyle \in {\mathcal {X}}}$

${\displaystyle 2^{-n(H(X)+\varepsilon )}\leqslant p(x_{1},x_{2},\dots ,x_{n})\leqslant 2^{-n(H(X)-\varepsilon )}}$

dónde

${\displaystyle H(X)=-\sum _{x\in {\mathcal {X}}}p(x)\log _{2}p(x)}$

es la entropía de información de  X. La probabilidad anterior solo necesita estar dentro de un factor de 2 ^{n ε} . Tomando el logaritmo en todos los lados y dividiendo por -n , esta definición se puede expresar de manera equivalente como

${\displaystyle H(X)-\varepsilon \leq -{\frac {1}{n}}\log _{2}p(x_{1},x_{2},\ldots ,x_{n})\leq H(X)+\varepsilon .}$

Para la secuencia iid, ya que

${\displaystyle p(x_{1},x_{2},\ldots ,x_{n})=\prod _{i=1}^{n}p(x_{i}),}$

Además tenemos

${\displaystyle H(X)-\varepsilon \leq -{\frac {1}{n}}\sum _{i=1}^{n}\log _{2}p(x_{i})\leq H(X)+\varepsilon .}$

Por la ley de los grandes números, para n suficientemente grande

${\displaystyle -{\frac {1}{n}}\sum _{i=1}^{n}\log _{2}p(x_{i})\rightarrow H(X).}$

Propiedades

Una característica esencial del conjunto típico es que, si se extrae una gran cantidad n de muestras aleatorias independientes de la distribución X , es muy probable que la secuencia resultante ( x ₁ ,  x ₂ , ...,  x _n ) sea un miembro del conjunto típico, aunque el conjunto típico comprenda solo una pequeña fracción de todas las secuencias posibles. Formalmente, dado cualquier , se puede elegir n tal que: ${\displaystyle \varepsilon >0}$

1. La probabilidad de que una secuencia de X ⁽ⁿ⁾ se extraiga de A _ε ^{( n )} es mayor que 1 −  ε , es decir ${\displaystyle Pr[x^{(n)}\in A_{\epsilon }^{(n)}]\geq 1-\varepsilon }$
2. ${\displaystyle \left|{A_{\varepsilon }}^{(n)}\right|\leqslant 2^{n(H(X)+\varepsilon )}}$
3. ${\displaystyle \left|{A_{\varepsilon }}^{(n)}\right|\geqslant (1-\varepsilon )2^{n(H(X)-\varepsilon )}}$
4. Si la distribución no es uniforme, entonces la fracción de secuencias que son típicas es ${\displaystyle {\mathcal {X}}}$

${\displaystyle {\frac {|A_{\epsilon }^{(n)}|}{|{\mathcal {X}}^{(n)}|}}\equiv {\frac {2^{nH(X)}}{2^{n\log _{2}|{\mathcal {X}}|}}}=2^{-n(\log _{2}|{\mathcal {X}}|-H(X))}\rightarrow 0}$

a medida que n se vuelve muy grande, ya que donde es la cardinalidad de . ${\displaystyle H(X)<\log _{2}|{\mathcal {X}}|,}$ ${\displaystyle |{\mathcal {X}}|}$ ${\displaystyle {\mathcal {X}}}$

Para un proceso estocástico general { X ( t )} con AEP, el conjunto (débilmente) típico se puede definir de manera similar con p ( x ₁ ,  x ₂ , ...,  x _n ) reemplazado por p ( x ₀ ^τ ) (es decir, la probabilidad de la muestra limitada al intervalo de tiempo [0,  τ ]), siendo n el grado de libertad del proceso en el intervalo de tiempo y H ( X ) siendo la tasa de entropía . Si el proceso tiene un valor continuo, se utiliza en su lugar la entropía diferencial .

Ejemplo

Contrariamente a la intuición, la secuencia más probable a menudo no es un miembro del conjunto típico. Por ejemplo, supongamos que X es una variable aleatoria de Bernoulli iid con p (0) = 0,1 y p (1) = 0,9. En n ensayos independientes, dado que p (1) > p (0), la secuencia de resultados más probable es la secuencia de todos los 1, (1, 1,..., 1). Aquí la entropía de X es H ( X ) = 0,469, mientras que

${\displaystyle -{\frac {1}{n}}\log _{2}p\left(x^{(n)}=(1,1,\ldots ,1)\right)=-{\frac {1}{n}}\log _{2}(0.9^{n})=0.152}$

Por lo tanto, esta secuencia no está en el conjunto típico porque su probabilidad logarítmica promedio no puede acercarse arbitrariamente a la entropía de la variable aleatoria X, sin importar cuán grande tomemos el valor de n .

Para las variables aleatorias de Bernoulli, el conjunto típico consiste en secuencias con números promedio de 0 y 1 en n ensayos independientes. Esto se demuestra fácilmente: si p(1) = p y p(0) = 1-p , entonces para n ensayos con m 1, tenemos

${\displaystyle -{\frac {1}{n}}\log _{2}p(x^{(n)})=-{\frac {1}{n}}\log _{2}p^{m}(1-p)^{n-m}=-{\frac {m}{n}}\log _{2}p-\left({\frac {n-m}{n}}\right)\log _{2}(1-p).}$

El número promedio de 1 en una secuencia de ensayos de Bernoulli es m = np . Por lo tanto, tenemos

${\displaystyle -{\frac {1}{n}}\log _{2}p(x^{(n)})=-p\log _{2}p-(1-p)\log _{2}(1-p)=H(X).}$

En este ejemplo, si n = 10, el conjunto típico consta de todas las secuencias que tienen un solo 0 en toda la secuencia. En el caso de que p (0) = p (1) = 0,5, todas las secuencias binarias posibles pertenecen al conjunto típico.

Secuencias fuertemente típicas (fuerte tipicidad, tipicidad de letras)

Si una secuencia x ₁ , ..., x _n se extrae de alguna distribución conjunta especificada definida sobre un alfabeto finito o infinito , entonces el conjunto fuertemente típico, A _ε,strong ^{( n )} se define como el conjunto de secuencias que satisfacen ${\displaystyle {\mathcal {X}}}$ ${\displaystyle \in {\mathcal {X}}}$

${\displaystyle \left|{\frac {N(x_{i})}{n}}-p(x_{i})\right|<{\frac {\varepsilon }{\|{\mathcal {X}}\|}}.}$

donde es el número de ocurrencias de un símbolo específico en la secuencia. ${\displaystyle {N(x_{i})}}$

Se puede demostrar que las secuencias fuertemente típicas también son débilmente típicas (con una constante ε diferente), y de ahí el nombre. Sin embargo, las dos formas no son equivalentes. La tipicidad fuerte suele ser más fácil de utilizar para demostrar teoremas para canales sin memoria. Sin embargo, como se desprende de la definición, esta forma de tipicidad solo se define para variables aleatorias que tienen un soporte finito.

Secuencias conjuntas típicas

Dos secuencias y son conjuntamente ε-típicas si el par es ε-típico con respecto a la distribución conjunta y ambas y son ε-típicas con respecto a sus distribuciones marginales y . El conjunto de todos esos pares de secuencias se denota por . Las secuencias de n -tuplas conjuntamente ε-típicas se definen de manera similar. ${\displaystyle x^{n}}$ ${\displaystyle y^{n}}$ ${\displaystyle (x^{n},y^{n})}$ ${\displaystyle p(x^{n},y^{n})=\prod _{i=1}^{n}p(x_{i},y_{i})}$ ${\displaystyle x^{n}}$ ${\displaystyle y^{n}}$ ${\displaystyle p(x^{n})}$ ${\displaystyle p(y^{n})}$ ${\displaystyle (x^{n},y^{n})}$ ${\displaystyle A_{\varepsilon }^{n}(X,Y)}$

Sean y dos secuencias independientes de variables aleatorias con las mismas distribuciones marginales y . Entonces, para cualquier ε>0, para n suficientemente grande , las secuencias conjuntamente típicas satisfacen las siguientes propiedades: ${\displaystyle {\tilde {X}}^{n}}$ ${\displaystyle {\tilde {Y}}^{n}}$ ${\displaystyle p(x^{n})}$ ${\displaystyle p(y^{n})}$

1. ${\displaystyle P\left[(X^{n},Y^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\geqslant 1-\epsilon }$
2. ${\displaystyle \left|A_{\varepsilon }^{n}(X,Y)\right|\leqslant 2^{n(H(X,Y)+\epsilon )}}$
3. ${\displaystyle \left|A_{\varepsilon }^{n}(X,Y)\right|\geqslant (1-\epsilon )2^{n(H(X,Y)-\epsilon )}}$
4. ${\displaystyle P\left[({\tilde {X}}^{n},{\tilde {Y}}^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\leqslant 2^{-n(I(X;Y)-3\epsilon )}}$
5. ${\displaystyle P\left[({\tilde {X}}^{n},{\tilde {Y}}^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\geqslant (1-\epsilon )2^{-n(I(X;Y)+3\epsilon )}}$

Aplicaciones de la tipicidad

Codificación de conjunto típica

En teoría de la información , la codificación de conjuntos típicos codifica solo las secuencias en el conjunto típico de una fuente estocástica con códigos de bloque de longitud fija. Dado que el tamaño del conjunto típico es de aproximadamente 2 ^nH(X) , solo se requieren nH(X) bits para la codificación, al mismo tiempo que se garantiza que las posibilidades de error de codificación se limiten a ε. Asintóticamente, según el AEP, no tiene pérdidas y logra la tasa mínima igual a la tasa de entropía de la fuente.

Decodificación de conjunto típico

En la teoría de la información , la decodificación de conjuntos típicos se utiliza junto con la codificación aleatoria para estimar el mensaje transmitido como aquel con una palabra de código que es conjuntamente ε-típica con la observación, es decir

${\displaystyle {\hat {w}}=w\iff (\exists w)((x_{1}^{n}(w),y_{1}^{n})\in A_{\varepsilon }^{n}(X,Y))}$

donde son la estimación del mensaje, la palabra código del mensaje y la observación respectivamente. se define con respecto a la distribución conjunta donde es la probabilidad de transición que caracteriza las estadísticas del canal, y es una distribución de entrada utilizada para generar las palabras código en el libro de códigos aleatorio. ${\displaystyle {\hat {w}},x_{1}^{n}(w),y_{1}^{n}}$ ${\displaystyle w}$ ${\displaystyle A_{\varepsilon }^{n}(X,Y)}$ ${\displaystyle p(x_{1}^{n})p(y_{1}^{n}|x_{1}^{n})}$ ${\displaystyle p(y_{1}^{n}|x_{1}^{n})}$ ${\displaystyle p(x_{1}^{n})}$

Prueba de hipótesis nula universal

Código de canal universal

Véase también

• Propiedad de equipartición asintótica
• Teorema de codificación de fuentes
• Teorema de codificación de canal ruidoso

Referencias

• CE Shannon , "Una teoría matemática de la comunicación", Bell System Technical Journal , vol. 27, págs. 379-423, 623-656, julio, octubre de 1948
• Portada, Thomas M. (2006). "Capítulo 3: Propiedad de equipartición asintótica, Capítulo 5: Compresión de datos, Capítulo 8: Capacidad del canal". Elementos de la teoría de la información . John Wiley & Sons. ISBN 0-471-24195-4.
• David JC MacKay . Teoría de la información, inferencia y algoritmos de aprendizaje. Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1