¡Bienvenidos!
pitagoras Tresfonsitas

ENTROPÍA

Las 4 letras.

I Sea una variable aleatoria X con valores {A,B,C,D} todos de igual probabilidad P(xi)=1/4.

Supongamos que tenemos una realización de X; por ejemplo, hemos sacado una bola de una urna con 4 bolas marcadas con las 4 letras.

Nos planteamos el problema siguiente: ¿cuántas preguntas debo hacer para saber cuál es el resultado?

Una buena estrategia sería la busqueda binaria consistente en dividir el conjunto en dos mitades y preguntar si el resultado está en la primera de ellas; y así se sigue en la mitad definida por la respuesta, tal como se ve en el siguiente árbol:

Como se ve son necesarias 2 preguntas.

La entropía de Shannon mide esta característica.

II Sea ahora una variable aleatoria X con valores {A,B,C,D} de probabilidades P(A)=0,4; P(B)=0,3; P(C)=0,2; P(D)=0,1.

Sea una realización de X; por ejemplo, hemos sacado una bola de una urna con 10 bolas marcadas 4 con la A; 3 con la B; 2 con la C y una con la D.

Nos planteamos el mismo problema: ¿cuántas preguntas debo hacer para saber cuál es el resultado?

Una buena estrategia sería la búsqueda jerárquica consistente en preguntar si la bola es la de mayor probabilidad y así sucesivamente:

El número de preguntas necesarias varía entre 1 y 3, con una media igual a 1,9.

III Podemos ya fácilmente estudiar otros casos, por ejemplo, una distribución muy alejada de la equiprobable: P(A)=0,94; P(B)=0,03; P(C)=0,02; P(D)=0,01.

La media de preguntas en la estrategia jerárquica sería:1*0,94+2*0,03+3*0,03=1,09

Entropía: H(x)=0,415

O una distribución muy próxima de la equiprobable: P(A)=0,27; P(B)=0,26; P(C)=0,24; P(D)=0,23.

La media de preguntas en la estrategia jerárquica sería: 2,2

Entropía: H(x)=1,997

El dado.

I Sea una variable aleatoria X con valores {1,2,3,4,5,6} todos de igual probabilidad P(xi)=1/6.

Supongamos que tenemos una realización de X; por ejemplo, hemos tirado un dado.

Nos planteamos el problema: ¿cuántas preguntas debo hacer para saber cuál es el resultado?

Una buena estrategia sería de nuevo la busqueda binaria consistente en dividir el conjunto en dos mitades y preguntar si el resultado está en la primera de ellas; y así se sigue en la mitad definida por la respuesta, tal como se ve en el siguiente árbol:

Como se ve son necesarias 2 preguntas para dar con el dos y el as y 3 preguntas para los otros 4 valores.

La media del número de preguntas sería 2,66.

La entropía: H(x)=2,585

II

Sea ahora una variable aleatoria X con valores {1,2,3,4,5,6} de probabilidades P(1)=0,05; P(2)=0,1; P(3)=0,12; P(4)=0,15; P(5)=0,18; P(6)=0,4.

Sea una realización de X; por ejemplo, hemos tirado un dado cargado según la distribución anterior.

¿Cuántas preguntas debo hacer para saber cuál es el resultado?

Una buena estrategia sería ahora la búsqueda jerárquica consistente en preguntar si la puntuación es la de mayor probabilidad y así sucesivamente:

El número de preguntas necesarias varía entre 1 y 5, con probabilidades

P(1)=0,4; P(2)=0,18; P(3)=0,15; P(4)=0,12 y P(5)=0,1+0,05.

La media de preguntas necesarias será: 2,44

Entropía: 2,3

III

Podemos ya estudiar otros casos, por ejemplo, una distribución muy alejada de la equiprobable:

P(6)=0,9; P(1)=P(2)=P(3)=P(4)=P(5)=0,02.

La media de preguntas será: 1*0,9+2*0,02+3*0,02+4*0,02+5*0,04=1,28

La entropía vale 0,701.

En el extremo tendríamos un dado que sólo produjera seises: P(6)=1; P(1)=P(2)=P(3)=P(4)=P(5)=0.

Las preguntas necesarías serían cero, obviamente.

La entropía valdría: H(x)=1 log2 (1/1)=0

Si por el contrario consideramos una distribución muy próxima de la equiprobable:

P(1)=0,14; P(2)=0,15; P(3)=0,16; P(4)=0,17;P(5)=0,18;P(6)=0,2.

La media de preguntas en la estrategia jerárquica sería: 1*0,2+2*0,18+3*0,17+4*0,16+5*0,29=3,16

La entropía vale H=2,57.

La estrategia Shannon-Fano consiste en hacer las preguntas de modo que las probabilidades del SI y del NO sean lo más cercanas posible al 50%.

Volvamos al dado cargado de probabilidades P(1)=0,05; P(2)=0,1; P(3)=0,12; P(4)=0,15; P(5)=0,18; P(6)=0,4.

La primera pregunta será si la puntuación es 2 o 6.

El número de preguntas sería 2 (prob. 0,5) o 3 (prob. 0,5); luego la media sería 2,5 preguntas.

No hemos mejorado a la estrategia jerárquica (2,44 de media). Recordemos que la entropía era 2,3.

Estudiemos la distribución muy alejada de la equiprobable:

P(6)=0,9; P(1)=P(2)=P(3)=P(4)=P(5)=0,02.

La primera pregunta sigue siendo la misma, "¿es un 6?"; pero la segunda sería "¿es un 1 o un 2?".

El número de preguntas será 1 (prob. 0,9); 3 (prob. 0,06); o 4 prob. (0,04). La media valdrá: 0,9+0,18+0,16=1,24.

Hemos mejorado la estrategia jerárquica (1,28). Entropía: 0,7.

Pasemos a la distribución muy próxima de la equiprobable:

P(1)=0,14; P(2)=0,15; P(3)=0,16; P(4)=0,17;P(5)=0,18;P(6)=0,2.

La primera pregunta debería ser "¿es un 1, un 3 o un 6?".

Los números de preguntas pueden ser 2 (prob. 0,38) o 3 (prob. 0,62); la media valdrá: 0,76+1,86=2,62.

La mejora respecto del método jerárquico es grande (3,16). Entropía, 2,57.

La estrategia Huffman construye el árbol desde abajo.

En el primer paso toma los dos valores de menor probabilidad y los sustituye por su asociación con probabilidad igual a la suma. Esto se repite hasta terminar.

Tomemos el dado "cargado" P(1)=0,05; P(2)=0,1; P(3)=0,12; P(4)=0,15; P(5)=0,18; P(6)=0,4.

Primera etapa: P(3)=0,12; P(1,2)=0,15; P(4)=0,15; P(5)=0,18; P(6)=0,4.

Segunda etapa: P(4)=0,15; P(5)=0,18; P(3,1,2)=0,27; P(6)=0,4.

Tercera etapa: P(3,1,2)=0,27; P(4,5)=0,33; P(6)=0,4.

Final: P(3,1,2,4,5)=0,6; P(6)=0,4.

Tenemos la posibilidad de 1 pregunta (prob. 0,4); 3 preguntas (prob. 0,45) y 4 preguntas (prob. 0,15). La media será: 0,4+1,35+0,6= 2,35.

Media jerárquica: 2,44. Media S-F: 2,5. Entropía: 2,3.

Estudiemos el dado muy cargado: P(6)=0,9; P(1)=P(2)=P(3)=P(4)=P(5)=0,02.

Primera etapa: P(3)=P(4)=P(5)=0,02; P(1,2)=0,04; P(6)=0,9

Segunda etapa: P(5)=0,02; P(1,2)=0,04; P(3,4)=0,04; P(6)=0,9

Tercera etapa: P(3,4)=0,04; P(5,1,2)=0,06; P(6)=0,9

Final: P(3,4,5,1,2)=0,10; P(6)=0,9

Tenemos la posibilidad de 1 pregunta (prob. 0,9); 3 preguntas (prob. 0,06) y 4 preguntas (prob. 0,04). La media será: 0,9+0,18+0,16= 1,24.

Media jerárquica: 1,28. Media S-F: 1,24. Entropía: 0,7.

Vayamos al dado poco cargado: P(1)=0,14; P(2)=0,15; P(3)=0,16; P(4)=0,17;P(5)=0,18;P(6)=0,2.

Primera etapa: P(3)=0,16; P(4)=0,17;P(5)=0,18;P(6)=0,2; P(1,2)=0,29

Segunda etapa: P(5)=0,18;P(6)=0,2; P(1,2)=0,29; P(3,4)=0,33

Tercera etapa: P(1,2)=0,29; P(3,4)=0,33; P(5,6)=0,38

Final: P(1,2,3,4)=0,62; P(5,6)=0,38

Tenemos 2 preguntas (prob. 0,38) y 3 preguntas (prob. 0,62). La media será: 0,76+1,86= 2,62.

Media jerárquica: 3,16. Media S-F: 2,62. Entropía: 2,57.

Hoja de cálculo Estudio 14

Seguimos con la memorización.

¡Hola!
¡Un saludo!