Conjunto típico

En teoría de la información , el conjunto típico es un conjunto de secuencias cuya probabilidad es aproximadamente 2⁻ⁿH(X), donde H(X) es la entropía de la fuente y n es la longitud de la secuencia. Que este conjunto tenga una probabilidad total cercana a uno es consecuencia de la propiedad de equipartición asintótica (PEA), que es una especie de ley de los grandes números . La noción de tipicidad se refiere únicamente a la probabilidad de una secuencia y no a la secuencia en sí.

Esto es de gran importancia en la teoría de la información y la codificación de fuentes, ya que proporciona un medio teórico para comprimir datos, lo que nos permite representar casi todas las secuencias X^n usando nH ( X ) bits en promedio y, por lo tanto, justifica el uso de la entropía como una medida de la información de una fuente.

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

Además, el concepto de conjunto típico es fundamental para comprender los límites de la transmisión de datos y la corrección de errores en los sistemas de comunicación. Aprovechando las propiedades de las secuencias típicas, se desarrollan esquemas de codificación eficientes, como el teorema de codificación de fuente de Shannon y el teorema de codificación de canal , que permiten una compresión de datos casi óptima y una transmisión fiable a través de canales ruidosos.

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

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

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

dónde

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 ⁿ^ε . Tomando el logaritmo en todos los lados y dividiendo por -n , esta definición se puede enunciar de forma equivalente como

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, dado que

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

Además tenemos

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

-{\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 un gran número n de muestras aleatorias independientes de la distribución X , es muy probable que la secuencia resultante ( x₁ , x₂ , _... , xn ₎_{sea un miembro del conjunto típico, aunque este solo comprende una pequeña fracción de todas las} secuencias posibles. Formalmente, dado cualquier $\varepsilon >0$ , se puede elegir n de tal manera que:

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

{\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

H(X)<\log _{2}|{\mathcal {X}}|,

dónde

|{\mathcal {X}}|

es la cardinalidad de

{\mathcal {X}}

.

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

Ejemplo

Contrariamente a la intuición, la secuencia más probable a menudo no pertenece al conjunto típico. Por ejemplo, supongamos que X es una variable aleatoria de Bernoulli i.i.d. 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 1, (1,1,...,1). Aquí la entropía de X es H ( X )=0,469, mientras que

-{\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 un número 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

-{\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

-{\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, entonces 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 ${\mathcal {X}}$ , entonces el conjunto fuertemente típico, A _ε,strong^{( n )} $\in {\mathcal {X}}$ se define como el conjunto de secuencias que satisfacen

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

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

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

Secuencias típicas conjuntas

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

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

$P\left[(X^{n},Y^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\geqslant 1-\epsilon$
$\left|A_{\varepsilon }^{n}(X,Y)\right|\leqslant 2^{n(H(X,Y)+\epsilon )}$
$\left|A_{\varepsilon }^{n}(X,Y)\right|\geqslant (1-\epsilon )2^{n(H(X,Y)-\epsilon )}$
$P\left[({\tilde {X}}^{n},{\tilde {Y}}^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\leqslant 2^{-n(I(X;Y)-3\epsilon )}$
$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 conjuntos típica

En teoría de la información , la codificación de conjuntos típicos codifica únicamente las secuencias del 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 aproximadamente 2 ^nH(X) , solo se requieren nH(X) bits para la codificación, asegurando al mismo tiempo que la probabilidad de error de codificación se limite a ε. Asintóticamente, según el AEP, es sin pérdidas y alcanza una tasa mínima igual a la tasa de entropía de la fuente.

Decodificación de conjuntos típicos

En 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 clave que es conjuntamente ε-típica con la observación.

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

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

Prueba de hipótesis nula universal

Código de canal universal

Véase también

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.
Cover, 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