Concepto típico de plató

Question

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

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

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

Answer 1

Respuesta de Diegobatt hace un buen trabajo explicando intuitivamente cuál es el conjunto típico. Esta respuesta responderá a la otra pregunta de la OP, de la que se hizo eco @tomwesolowski: ¿por qué definir 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 ante todo una herramienta teórica. Se definió para ayudar a demostrar algo, y esta definición es la más conveniente para la prueba. Es un buen ejemplo de cómo las necesidades teóricas pueden a veces imponerse a las preferencias intuitivas en matemáticas.

El conjunto típico fue definido por el padre de teoría de la información , Claude Shannon . Quería determinar con qué eficiencia se podía codificar un flujo de símbolos a partir de un alfabeto fijo, suponiendo que cada símbolo es un i.i.d. muestra aleatoria de alguna distribución. Sus ideas clave eran que:

1. Hay un conjunto relativamente pequeño de secuencias "típicas", fácilmente identificables, que aparecen con una frecuencia desproporcionada en el flujo.
2. Asignando a este "conjunto típico" de secuencias las codificaciones más cortas se obtiene un codificación óptima (asintóticamente, a medida que la salida del flujo crece arbitrariamente).

El conjunto típico descubierto por Shannon está compuesto precisamente por las secuencias cuyo autoinformación o "capacidad de sorpresa", es aproximadamente la misma que la autoinformación esperado por término medio, para la distribución de la fuente del flujo. Estas secuencias son "típicas" en el sentido de que su información es aproximadamente la media, pero esta definición excluye implícitamente las secuencias que tienen una información significativamente inferior a la media. Estas secuencias menos informativas son también las más probables.

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

Pero Shannon no quería el conjunto típico más "típico" posible; quería uno que hizo fácil probar el resultado que quería probar. El conjunto típico definido por Shannon está garantizado que existe, está garantizado que es pequeño, y está garantizado que es tan pequeño como cualquier otro conjunto que puedas proponer, como esta respuesta señala. Añadir los elementos más probables hace que el conjunto sea más probable, lo que es bueno, pero también hace que el conjunto sea mayor, lo que es malo. El efecto neto sobre la solidez de la prueba no está claro de inmediato; podría hacer que la prueba fuera más complicada de terminar. Es mejor no arreglar lo que no está roto.

Si sus objetivos son distintos a los de Shannon, su concepto preferido de tipicidad también podría ser diferente. Por ejemplo, en Codificación Huffman los símbolos (o secuencias de símbolos) más probables obtienen los códigos más cortos. En cierto sentido técnico, la codificación de Huffman es la solución óptima al 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 demostrar cosas.

Answer 2

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

$X_1, X_2 ,... $ son i.i.d. variables aleatorias $\sim $ $p(x)$ entonces 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 $\epsilon$ el conjunto típico está formado por todas las secuencias cuyas probabilidades son cerrar a $2^{-nH(X)}$ . Así, para que una secuencia pertenezca al conjunto típico, basta con que tenga una probabilidad cercana a $2^{-nH(X)}$ Pero no suele ser así. Para entender por qué, permítanme reescribir la ecuación 1 aplicando $log_2$ en él.

$$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 de conjunto está más directamente relacionada con el concepto de entropía, o dicho de otro modo, la información media de la variable aleatoria. El término medio puede considerarse como la entropía muestral de la secuencia, por lo que el conjunto típico está formado por todas las secuencias que nos proporcionan una cantidad de información cercana a la información media de la variable aleatoria. $X$ . La secuencia más probable suele darnos menos información que la media. Recuerda que, cuanto menor sea la probabilidad de un resultado, mayor será la información que nos proporcione. Para entender por qué, pongamos un ejemplo:

Supongamos que vives en una ciudad cuyo tiempo es muy probable que sea soleado y cálido, entre 24 °C y 26 °C. Puede que vea el parte meteorológico todas las mañanas, pero no le importaría mucho, es decir, siempre hace sol y calor. Pero, ¿y si un día el hombre o la mujer del tiempo te dice que hoy va a llover y hacer frío? Tendrás que usar ropa diferente, llevar paraguas y hacer otras cosas que normalmente no haces, así que el hombre del tiempo 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).

Answer 3

Según el teorema 6.3 de estas notas de clase no importa si tomamos el 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. Normalmente tomamos elementos típicos del conjunto, porque podemos acotar su tamaño más fácilmente.

Answer 4

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

Imagina que tienes una moneda muy sesgada, digamos $p(H) = .9$ . Esto es sólo la distribución binomial. La secuencia más probable de 100 aciertos es 100 caras, pero sólo hay 1 secuencia de 100 caras. Hay exponencialmente muchas más secuencias que contienen 10 colas, pero éstas son mucho menos probables individualmente. El mayor número de secuencias es con la mitad de caras y la mitad de colas, pero éstas son aún menos probables. Por tanto, existe una tensión entre la probabilidad de las secuencias individuales y el número de secuencias equivalentes de una clase. La probabilidad máxima se alcanza cuando las frecuencias de las secuencias coinciden con las probabilidades.

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

Por ejemplo $10^5$ secuencias de lanzamiento del $P(H)=.9$ moneda obtendrá secuencias con $10^4{+/-}300$ colas el 99% de las veces, ya que la desviación típica del 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, definida en teoría de la información, de esta idea.

Answer 5

Consideremos una moneda sesgada que tiene una probabilidad del 60% de salir cara. Si esta moneda se lanza 100 veces, la secuencia más probable sería 100 caras, pero eso no es "típico". Típico secuencias tendrían unas 60 cabezas.