CDSP: Practico 3 ejercicio 4

Buenas, me trabe en la parte del ejercicio que me pide calcular la cantidad media asintotica de bits de codigo por simbolo de la fuente.

Esto es lo que tengo hecho hasta ahora:

Otra consulta que me surgio: Los procesos de Markov estacionarios no tienen porque tener una unica distribucion estacionaria, verdad? eso solo se asegura en el caso de que la cadena sea aperiodica y aciclica?

Re: Practico 3 ejercicio 4

de Alvaro Martin - miércoles, 21 de abril de 2021, 15:24

Hola.
Después de la primera línea, podrías aplicar la linealidad de la esperanza para expresar esa esperanza como una suma de esperanzas, con un término para cada

$X_i$ . La

$X_1$ la manejás por separado; para las demás usás la estacionariedad. La probabilidad de que

$X_i$ se codifique con una palabra de largo

$\ell$ es la probabilidad de que el par

$(X_{i-1}, X_i)$ sea tal que

$| C_{X_{i-1}} (X_i)| = \ell$ . Una forma de expresarlo es como la suma entre todos los pares (y,z) de

$P(X_{i-1} = y, X_i = z) | C_y(z)|$ .

Con respecto a la unicidad de la distribución estacionaria, lo que decís es correcto (pero creo que quisiste escribir irreducible en vez de acíclica). Por ejemplo, si el grafo dirigido que representa la cadena tiene dos componentes fuertemente conexas que no son accesibles una desde la otra, y cada componente es irreducible y aperiódica, la cadena va a tener dos distribuciones estacionarias, una correspondiente a cada componente conexa.
Podés jugar con un ejemplo en http://markov.yoriz.co.uk/ , yendo a Examples / Two communication classes.
Dicho sea de paso, ese proceso no es ergódico. Es un ejemplo un poco más complicado del mismo tipo del que les comenté hace unos días para ilustrar el concepto de ergodicidad.

Saludos,
Álvaro

Re: Practico 3 ejercicio 4

de Rafael Agustin Castelli Ottati - jueves, 22 de abril de 2021, 11:25

Salio con lo que me comentaste, gracias.
Igualmente me quedaron algunas dudas:

1) (Capaz que esta pregunta se sale de lo que es relevante para el curso) En el ejercicio 1 se dedujo una formula para la tasa de entropia de un proceso de Markov estacionario. Dicha formula depende de la distribucion estacionaria. Entonces, si me enfrento a un proceso con mas de una distribucion estacionaria, la formula me podria dar 2 tasas de entropias distintas, lo cual no tiene sentido. Se puede probar que el valor de dicha expresion es el mismo sin importar la distribucion estacionaria elegida? Ademas, las distribuciones estacionarias aparecen como solucion de un sistema lineal (imponiendo las condiciones que se presentaron en las diapositivas del tema), que en caso de tener mas de una distribucion estacionaria, deberia ser compatible indeterminado, entonces como se podrian tener exactamente 2 distribuciones estacionarias?

2) En este caso llegue a que la tasa de entropia es igual a la esperanza del largo de codigo medio, esto significa optimalidad? (El ejercicio 5 habla un poco de esto, pero no termino de ver si cae dentro de el caso del ejercicio)

3) En este caso, como el proceso (de las X) no es ergodico, significaria que no tengo garantizado la optimalidad de LZ77-LZ78? (voy mas por el lado de que los procesos Markovianos parecerian lo suficientemente genericos o practicos como para aplicarse como modelos de varias situaciones, por ejemplo archivos de texto(en un lenguaje dado) o imagenes, entonces seria util tener alguna garantia de optimalidad de LZ77-LZ78 para estos procesos)

Saludos,
Rafael

Re: Practico 3 ejercicio 4

de Rafael Agustin Castelli Ottati - jueves, 22 de abril de 2021, 12:09

PD: lo de que la tasa de entropia sea igual a la esperanza del largo de codigo medio supongo que sucede porque las probabilidades son potencias de 2, lo que hace que los codigos de Huffman sean codigos de Shannon y a su vez los codigos de Shannon alcancen la entropia.