En teoría de la información , el conjunto típico es un conjunto de secuencias cuya probabilidad es cercana a dos elevada 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 real en sí.
Esto tiene un gran uso 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 n usando nH ( X ) bits en promedio y, por lo tanto, justifica el uso de la entropía como una medida de información de un fuente.
El AEP también se puede probar para una gran clase de procesos ergódicos estacionarios , lo que permite definir conjuntos típicos en casos más generales.
(Débilmente) secuencias típicas (tipicidad débil, tipicidad de entropía)
Si una secuencia x 1 , ..., x n se extrae de una distribución iid X definida sobre un alfabeto finito, entonces el conjunto típico, A ε ( n )( n ) se define como aquellas secuencias que satisfacen:
dónde
es la entropía de la información de la 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 puede expresarse de manera equivalente como
Para la secuencia iid, desde
además tenemos
Por la ley de los grandes números, para n suficientemente grandes
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 1 , x 2 , ..., x n ) sea un miembro del conjunto típico, aunque el conjunto típico comprende sólo una pequeña fracción de todas las secuencias posibles. Formalmente, dado cualquier, se puede elegir n tal que:
- La probabilidad de que una secuencia de X (n) se extraiga de A ε ( n ) es mayor que 1 - ε , es decir
- Si la distribución termina no es uniforme, entonces la fracción de secuencias que son típicas es
- a medida que n se vuelve muy grande, ya que dónde es la cardinalidad de .
Para un proceso estocástico general { X ( t )} con AEP, el conjunto típico (débilmente) se puede definir de manera similar con p ( x 1 , x 2 , ..., x n ) reemplazado por p ( x 0 τ ) (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 es de valores continuos, en su lugar se utiliza 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, suponga que X es una variable aleatoria de Bernoulli iid con p (0) = 0.1 yp (1) = 0.9. En n ensayos independientes, dado que p (1)> p (0), la secuencia de resultado 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
Entonces, 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
El número medio de unos en una secuencia de ensayos de Bernoulli es m = np . Por lo tanto, tenemos
Para este ejemplo, si n = 10, entonces el conjunto típico consta de todas las secuencias que tienen un solo 0 en toda la secuencia. En el caso de p (0) = p (1) = 0.5, entonces todas las secuencias binarias posibles pertenecen al conjunto típico.
Secuencias fuertemente típicas (tipicidad fuerte, tipicidad de letras)
Si una secuencia x 1 , ..., x n se extrae de alguna distribución conjunta especificada definida sobre un alfabeto finito o infinito, entonces el conjunto fuertemente típico, A ε, fuerte ( n ) se define como el conjunto de secuencias que satisfacen
dónde es el número de apariciones 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 ε), y de ahí el nombre. Sin embargo, las dos formas no son equivalentes. A menudo es más fácil trabajar con la tipicidad fuerte 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 típicas conjuntas
Dos secuencias y son conjuntamente ε-típicos si el par es ε-típico con respecto a la distribución conjunta y ambos y son ε-típicos con respecto a sus distribuciones marginales y . El conjunto de todos esos pares de secuencias se denota por . Las secuencias de tuplas n típicas de ε se definen de manera similar.
Dejar y Ser dos secuencias independientes de variables aleatorias con las mismas distribuciones marginales. y . Entonces, para cualquier ε> 0, para n suficientemente grande , las secuencias típicas en conjunto satisfacen las siguientes propiedades:
Aplicaciones de la tipicidad
Codificación típica de conjuntos
En la teoría de la información , la codificación de conjuntos típica 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, mientras que al mismo tiempo se asegura que las posibilidades de error de codificación se limiten a ε. Asintóticamente, según la AEP, no tiene pérdidas y alcanza la tasa mínima igual a la tasa de entropía de la fuente.
Decodificación típica de conjuntos
En la teoría de la información , la decodificación de conjuntos típica se usa junto con la codificación aleatoria para estimar el mensaje transmitido como el que tiene una palabra de código que es junto con la observación típica. es decir
dónde son la estimación del mensaje, palabra clave del mensaje y la observación respectivamente. se define con respecto a la distribución conjunta dónde es la probabilidad de transición que caracteriza las estadísticas del canal, y es una distribución de entrada que se utiliza para generar las palabras de código en el libro de códigos aleatorio.
Prueba universal de hipótesis nula
Código de canal universal
Ver 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
- 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 e hijos. 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