Concepto conjunto típico

Pensé que el concepto de conjunto típico era bastante intuitivo: una secuencia de longitud pertenecería al conjunto típico si la probabilidad de que la secuencia saliera fuera alta. Entonces, cualquier secuencia que probablemente esté en . (Estoy evitando la definición formal relacionada con la entropía porque estoy tratando de entenderla cualitativamente).A ( n ) ϵ A ( n )$n$$A_\epsilon ^{(n)}$$A_\epsilon ^{(n)}$

Sin embargo, he leído que, en general, la secuencia más probable no pertenece al conjunto típico. Esto me confundió a lo grande.

¿Existe una definición intuitiva de conjunto típico? ¿O es solo una herramienta matemática que no tiene mucho que ver con el sentido común?

Sé que ha pedido explícitamente una explicación intuitiva y dejar de lado la definición formal, pero creo que están bastante relacionados, así que permítanme recordar la definición de conjunto típico:

$X_1, X_2 ,...$soniidvariables aleatorias$\sim$ $p(x)$ a continuación, el conjunto típico$A_\epsilon^{(n)}$ con respecto a$p(x)$ es el conjunto de secuencias$(x_1,x_2,...,x_n) \in \chi^n$ con la propiedad

$$2^{-n(H(X)+\epsilon)}\le p(x_1,x_2,...,x_n) \le 2^{-n(H(X)-\epsilon)} \tag{1}$$ esto significa que para un fijo$\epsilon$, el conjunto típico se compone de todas las secuencias de cuyas probabilidades soncercanasa$2^{-nH(X)}$. Entonces, para que una secuencia pertenezca al conjunto típico, solo tiene que tener una probabilidad cercana a$2^{-nH(X)}$ , generalmente no lo hace. Para entender por qué, déjame reescribir la ecuación 1 aplicando$log_2$ sobre ella.

$$H(X)-\epsilon\le \frac{1}{n}\log_2\left(\frac{1}{p(x_1,x_2,...,x_n)}\right) \le H(X)+\epsilon \tag{2}$$

Ahora, la definición típica del conjunto está más directamente relacionada con el concepto de entropía, o dicho de otra manera, la información promedio de la variable aleatoria. El término medio puede ser pensado como la entropía de la muestra de la secuencia, por lo tanto el conjunto típico se realiza por todas las secuencias que nos están dando una cantidad de información cerca de la información promedio de la variable aleatoria $X$ . La secuencia más probable generalmente nos da menos información que el promedio. Recuerde que cuanto menor sea la probabilidad de un resultado, mayor será la información que nos brinde. Para entender por qué déjame darte un ejemplo:

Supongamos que vive en una ciudad cuyo clima es muy probable que sea soleado y cálido, entre 24 ° C y 26 ° C. Puede ver el informe meteorológico todas las mañanas, pero no le importaría mucho, quiero decir, siempre está soleado y cálido. Pero qué pasa si algún día el hombre / mujer del clima te dice que hoy lloverá y hará frío, eso cambiará el juego. Tendrás que usar ropa diferente, llevar un paraguas y hacer otras cosas que normalmente no haces, por lo que el hombre del clima te ha dado una información realmente importante.

En resumen, la definición intuitiva del conjunto típico es que consiste en secuencias que nos dan una cantidad de información cercana a la esperada de la fuente (variable aleatoria).

La respuesta de Diegobatt hace un buen trabajo al explicar intuitivamente cuál es el conjunto típico. Esta respuesta abordará la otra pregunta del OP, con el eco de @tomwesolowski: ¿por qué definirías el conjunto típico de una manera que pueda excluir los elementos más probables?

La respuesta corta es que el conjunto típico es principalmente una herramienta matemática. Fue definido para ayudar a probar algo, y esta definición es la más conveniente para la prueba. Es un buen ejemplo de cómo las necesidades teóricas a veces pueden superar las preferencias intuitivas en matemáticas.

El conjunto típico fue definido por el padre de la teoría de la información , Claude Shannon . Quería determinar qué tan eficientemente uno podría codificar una secuencia de símbolos de un alfabeto fijo, suponiendo que cada símbolo sea una muestra aleatoria iid de alguna distribución. Sus ideas clave fueron que:

1. Hay un conjunto relativamente pequeño de secuencias "típicas" fácilmente identificables que aparecen desproporcionadamente a menudo en la secuencia.
2. Al asignar este "conjunto típico" de secuencias, las codificaciones más cortas producen una codificación óptimamente eficiente (asintóticamente, a medida que la salida de la secuencia crece arbitrariamente larga).

El conjunto típico que descubrió Shannon se compone precisamente de las secuencias cuya autoinformación , o "sorprendente", es casi la misma que la autoinformación esperada , en promedio, para la distribución de la fuente del flujo. Dichas secuencias son "típicas" en el sentido de que su información es sobre el promedio, pero esta definición excluye implícitamente aquellas secuencias que tienen significativamente menos información que el promedio. Estas secuencias menos informativas son también las más probables.

Como señala el OP, ¡esto no es intuitivamente atractivo! A primera vista, el conjunto típico parece que debería contener todas las secuencias más probables hasta cierto umbral. Eso representaría mejor lo que normalmente se ve en la transmisión.

Pero Shannon no quería el conjunto típico más "típico" posible; quería uno que facilitara probar el resultado que quería probar. Se garantiza que el conjunto típico definido por Shannon existe, se garantiza que es pequeño y se garantiza que es casi tan pequeño como cualquier otro conjunto que pueda proponer, como señala esta respuesta . Agregar los elementos más probables hace que el conjunto sea más probable, lo cual es bueno, pero también lo hace más grande, lo cual es malo. Si todo lo que le importa es hacer su prueba, ¿por qué arreglar lo que no está roto?

Si tiene objetivos diferentes a los de Shannon, su concepto preferido de tipicidad también podría ser diferente. Por ejemplo, en la codificación de Huffman , los símbolos más probables (o secuencias de símbolos) obtienen los códigos más cortos. En cierto sentido técnico, la codificación de Huffman es la solución óptima para el problema original de Shannon, y capta mejor nuestra intuición sobre la tipicidad. Por otro lado, la definición de tipicidad de Shannon es más conveniente para probar cosas.

La idea de un conjunto típico trata implícitamente las secuencias de resultados como conjuntos múltiples, es decir, supone que solo le importa el histograma de cada secuencia, por ejemplo, considera las 10 secuencias de lanzamiento de monedas con 7 caras y 3 colas como equivalentes.

Imagine que tiene una moneda muy sesgada, digamos $p(H) = .9$. Esta es solo la distribución binomial. La secuencia más probable de 100 lanzamientos es de 100 cabezas, pero solo hay una secuencia de 100 cabezas. Hay exponencialmente muchas más secuencias que contienen 10 colas, pero estas son mucho menos probables individualmente. El mayor número de secuencias es con medias cabezas y medias colas, pero estas son aún menos probables. Por lo tanto, existe una tensión entre la probabilidad de secuencias individuales y el número de secuencias equivalentes en una clase. La probabilidad máxima se alcanza cuando las frecuencias en las secuencias coinciden con las probabilidades.

El resultado importante es que para secuencias suficientemente largas, casi todas las secuencias muestreadas se encontrarán arbitrariamente cerca de las frecuencias esperadas, es decir, la distribución se vuelve extremadamente alta a medida que aumenta la longitud de las secuencias consideradas.

Por ejemplo observado $10^5$ lanzar secuencias de la $P(H)=.9$ la moneda obtendrá secuencias con $10^4{+/-}300$ colas el 99% del tiempo desde que la desviación estándar en el número de colas en una secuencia es aproximadamente 100. La probabilidad de todas las caras es insignificante a pesar de ser la secuencia específica más probable.

El conjunto típico es una versión más general, información teóricamente definida de esta idea.

De acuerdo con el teorema 6.3 en estas notas de clase, no importa si tomamos un subconjunto de secuencias con mayor probabilidad o aquellas con probabilidad cercana a$2^{-nH(X)}$ (del conjunto típico) tenemos que tomar aproximadamente $2^{nH}$para asegurarse de que el subconjunto elegido contiene una secuencia aleatoria con alta probabilidad. Por lo general, tomamos elementos de conjunto típicos, porque podemos limitar su tamaño más fácilmente.