La entropía es una medida de información.
Para poder entender el concepto que encierra vamos primero a ver un ejemplo:

Ejemplo 1: Tenemos una fuente de información, F, que nos va diciendo quien ha ganado un partido de fútbol, si el equipo A, con una probabilidad de 3/4, o el B, con probabilidad 1/4, de tal manera que la situación que tenemos es la siguiente:

A la hora de transmitir esta información a través del canal podemos hacerlo de muchas maneras. Supongamos que mandamos los resultados de tres partidos a la vez dando lugar a una codificación como la que sigue:

Observando nuestro código vemos que mandamos una mayor cantidad de bits en aquellas cadenas que tienen menor probabilidad de ocurrir. La longitud media del código es:

De acuerdo con este nuevo código ahora lo que tenemos es p(0) = 0.36 y p(1) = 0.63.

Vemos que tras la codificación binaria las probabilidades de 0 y 1 están más balanceadas que las A y B; lo perfecto sería que lo estuviesen totalmente.

Ya comprendido este ejemplo pasemos a definir entropía:

Definición 1: Dada una variable aleatoria discreta X que tiene una determinada distribución de probabilidades, p(x), entropía de X es:

Así, la entropía es una medida de la información que recibimos cuando nos mandan un dato. La unidad en que se mide depende de la base del logaritmo utilizada. Si es dicha base es 2, entonces medimos en BITS o si es el número "e", en NATS, etc. (véase Unidades de la entropía H(X)).

Ejemplo 2: De acuerdo con el ejemplo anterior, la medida de la entropía de la fuente sería:

Nota: El resultado esperado más probable es el que, obviamente, menos contribuye al valor de la entropía; luego esta puede entenderse como una ponderación de las contribuciones de cada suceso.

1.1.1. Unidades de la Entropía H(X)

Nota: La forma de calcular los logaritmos que no son en base decimal es teniendo en cuenta que:

1.1.2. Propiedades de la Entropía H(x)

1. H(X)0
   Demostración: 0p(x)1 implica que
   
2. 

Ejemplo 3: Si F es una fuente binaria tal que p(0)=p y p(1)=1-p=q:

A esta H(X) podemos llamarla H(p) o también H(p,q). Su representación gráfica será:

Observando la gráfica nos damos cuenta de algunas propiedades de la entropía. Vemos que H(X) es cero cuando p=0 ó p=1 porque entonces la variable deja de ser aleatoria, ya que no hay incertidumbre sobre el valor que tomará X. Por otra parte la incertidumbre es máxima cuando p=1/2, lo que consecuentemente coincide con el máximo de H(X).

1.1.3. Entropía con dos variables discretas X e Y

La entropía conjunta de dos variables aleatorias se calcula (en este caso, en bits) de la siguiente manera:

Ejemplo 4: Sean X e Y dos variables aleatorias discretas con la siguiente función de distribución:

H(X,Y)= 27/8 = 3.375 bits, donde H(X) = 7/4 = 1.75 bits y H(Y)= 2 bits.

1.1.4. Entropía Condicionada

1.1.5. Regla de la Cadena

Si X e Y son independientes, entonces: H(X,Y)=H(X)+H(Y)

Demostración:

H(X,Y) = –p(x,y)·log₂p(x,y) = – E[log₂p(x,y)] = – E[log₂p(x) + log₂p(y/x)] =
= – E[log₂p(x)] – E[log₂p(y/x)] = H(X) + H(Y/X)

Corolario: H(X,Y/Z)=H(X/Z)+H(Y/X,Z)

Ejemplo 5: Continuando con el ejemplo anterior:

H(Y/X=1) = 7/4 = 1.75 bits.
H(Y/X=2) = 3/2 = 1.5 bits.
H(Y/X=3) = 3/2 = 1.5 bits.
H(Y/X=4) = 3/2 = 1.5 bits.
H(X/Y) = H(X,Y) - H(Y) = 27/8-2 = 11/8 = 1.375 bits.

Nota: Por convenio se tiene:

1.2. INFORMACIÓN MUTUA ENTRE X E Y: I(X;Y)

Veamos previamente otro concepto necesario para la explicación de este.

1.2.1. Entropía Relativa o Entropía Diferencial D(p||q)

(A veces también llamada Distancia de Kullback-Leibler).
Es una medida de la distancia entre dos distribuciones de probabilidades de una misma variable aleatoria.

Ejemplo 6: Si conocemos la distribución verdadera de una variable aleatoria, podríamos construir un código usando H(p); pero si construyéramos ese código basándonos en q(x), entonces su longitud sería de H(p) + D(p||q) [bits].

Definición 2: La entropía relativa o diferencial se define como:

Propiedades:

1. D(p||q)0
2. D(p||q) = 0 si y sólo si p(x) = q(x)
3. D(p||q) D(q||p)

La tercera propiedad nos lleva a la posibilidad de equivocarnos si entendemos la entropía relativa como una distancia métrica. Es mejor que tengamos el siguiente concepto: D(p||q) es la medida de la ineficiencia de asumir que la distribución correcta es "q" cuando en realidad es "p". De esta forma comprendemos que efectivamente D(p||q) D(q||p).

Ejemplo 7: Dadas las distribuciones p y q

sus entropías relativas son:

1.2.2. Información Mutua entre X e Y: I(X;Y)

Definición 3: Es la medida de la cantidad de información que una variable aleatoria contiene sobre la otra. Aunque I(X;Y)=I(Y;X), en concreto I(X;Y) es la cantidad de información que X contiene sobre Y.

1.2.3. Relación entre Información Mutua y Entropía

Dado que: p(x,y) = p(y)·p(x/y), entonces:

luego:

Por simetría hemos obtenido que: I(X;Y) = H(Y) - H(Y/X)

Ejemplo 8: Si H(Y) = 2 bits y H(Y/X) = 13/8, calcular I(X;Y).

Como H(X,Y) = H(X) + H(Y/X) entonces:

Resumiendo, nos queda la siguiente tabla de relaciones:

Representación con diagramas de Venn de la relación entre la entropía de dos variables aleatorias:

De los diagramas de Venn podemos concluir:

• Si X e Y son variables aleatorias independientes, la incertidumbre de una no depende de la incertidumbre de la otra. Por lo tanto, I(X;Y)=0.
• En términos generales, la condición de una variable sobre la otra quita incertidumbre de esta variable. Es decir, que H(X/Y)H(X), y también H(Y/X)H(Y).

1.3. Entropía, Entropía Relativa e Información Mutua Condicionadas. Regla de la Cadena.

1.3.1. Entropía Condicionada

La entropía condicionada H(X/Y) ya se vio en el apartado 1.1.4.

1.3.2. Regla de al Cadena para la Entropía

La regla de la cadena para la entropía entre 2 variables aleatorias X e Y ya se vio en el apartado 1.1.5.

Para n variables aleatorias llegamos a:

Demostración: La demostración para n variables se realiza como para 2 variables aleatorias mediante la conocida regla de la cadena para probabilidades

Si tenemos n variables aleatorias condicionadas a otra variable aleatoria Y, la entropía de esta relación se podrá expresar como:

1.3.3. Entropía Relativa (o Diferencial) Condicional

Definición 4: La entropía relativa condicional se define a partir de la entropía relativa como:

1.3.4. Regla de la Cadena para la Entropía Relativa (o Diferencial)

Aplicando la regla de la cadena:

1.3.5. Informació´n Mutua Condicional

Definición 5: La información mutua condicional se relaciona con la entropía análogamente a la información mutua sin condicionar, de tal manera que:

1.3.6. Regla de la Cadena para la Información Mutua

Aplicando de igual manera que antes la regla de la cadena de las probabilidades:

1.4. Desigualdad de Jensen y sus Consecuencias

Vamos a probar alguna de las propiedades de las magnitudes definidas en el apartado anterior. Empezamos con las propiedades de las funciones cóncavas.

NOTA: En inglés, los términos cóncavo y convexo significan lo contrario que en español. Por esto, cuando en el libro de Cover el autor dice convex, en español decimos cóncavo, y cuando se dice en el libro concave, deberemos entender convexo.

1.4.1. Función Cóncava

f (K·x₁+ (1-k)·x₂) K·f (x₁) + (1-K)·f (x₂)

Se dice que una función es estrictamente cóncava si la igualdad se mantiene solamente para K=0 ó para K=1.

Gracias a la propiedad de concavidad se pueden demostrar otras muchas propiedades de las magnitudes fundamentales de la teoría de la información a través de la desigualdad de Jensen.

1.4.2. Desigualdad de Jensen

p_i · f(x_i) f( p_i · x _i)      E[f(X)] f(E[X])

De la misma manera y con las mismas condiciones, si f fuera una función cóncava:

E[f(X)] f(E[X])

Si f es estrictamente convexa o cóncava, entonces se cumple que X=E[X] con probabilidad 1, es decir, X es una constante. Y se tendría:

1.4.3. PROPIEDADES

1. D( p || q ) 0.
   D( p || q ) = 0 si y sólo si p( x ) = q( x ) para todo x.

   Demostración: Sea A = { x .. p(x)>0 }

   
   

2. D( p( x / y ) || q( x / y )) 0.
   

   Demostración:
   

   
   

3. I(X;Y) 0.
   I(X;Y) = 0 si y sólo si X e Y son independientes.

   Demostración:

   I(X;Y) = D( p(x,y) || p(x)·p(y) ) 0 y sólo vale cero si p(x,y) = p(x)·p(y). Esto último se cumple únicamente cuando X e Y son independientes.

   Corolario: I(X;Y/Z) 0.

   Demostración:

   I(X;Y/Z) = H(X/Z) - H(X/Y,Z) = D( p(x,y/z)|| p(x/z)·p(y/z) ) 0
   
   I(X;Y/Z) = 0 p(x,y/z) = p(x/z)·p(y/z)

   Por lo tanto, esta igualdad se dará cuando X e Y sean independientes entre ellas pero condicionadas a Z.
   
   

4. H(X) H(X/Y).
   H(X) = H(X/Y) si y sólo si X e Y son independientes.

   Demostración:

   H(X) - H(X/Y) = I(X;Y) 0

   
   Ejemplo 9:

   Y\X	1	2
   1	0	3/4
   2	1/8	1/8

   Vamos a ir hallando los distintos valores de la entropía:

   

   Con este ejemplo, lo que queremos es demostrar que la propiedad 4 sólo es verdadera en promedio. Lo vemos en, por ejemplo, H(X) = 0.544 H(X/Y=2), pero también vemos que efectivamente, en promedio sí se cumple que H(X) H(X/Y). Esto se produce porque hay condicionamientos que, de forma aislada, aumentan la incertidumbre (entropía) en vez de reducirla, confundiéndonos aún más. Pero en promedio, siempre los condicionamientos nos reducen o dejan igual la entropía (se sabe más de una variable aleatoria condicionada que sin condicionar).
   
   

5. 

   Demostración: Por la regla de la cadena, sabemos que:

   
   
   

6. E[log|X|] H(X)

   Demostración:

   

   Notas:

   • |X| representa el cardinal de X.
   • La igualdad se dará cuando p(x) = q(x) = 1/|X| (i.e. X es uniforme, por lo que H(X) es máximo).
   
   
   

7. Si tenemos una interpolación de dos probabilidades, la entropía aumenta.

   

1.5. Teorema de Procesado de la Información

Nos sirve para demostrar que nunca una manipulación más inteligente de los datos va a mejorar la información mutua entre las v.a. Es decir, dadas X e Y, podemos intentar mejorar I(X;Y) mediante un procesado y obtener Z, pero siempre se va a cumplir que:

I(X;Y) I(X;Z)

1.5.1. Procesos y Cadenas de Markov

Definición 6: Sea la secuencia x₁,...,x_n,...,x_L; x_i X; i {1,...,L}. Para que un proceso sea markoviano de orden n, se tiene que cumplir que:

Aunque el caso que nos ocupa es con índice "i" y variable aleatoria discretos, también hay procesos markovianos con índice y/o variable aleatoria continuos.

Con ayuda de la definición para el orden n, podemos definir en más detalle la cadena de Markov para orden 1:

Definición 7: Un proceso markoviano de orden 1 es un proceso estocástico de orden 1 en el cual su pasado no tiene ninguna influencia en el futuro si su presente está especificado. Es decir:

Si t_n-1 < t_n, entonces:

P{ X(t_n) X_n/X(t) , t t_n-1 } = P{ X(t_n) X_n/X(t_n-1) }

Luego, si t₁ < t₂ < ... < t_n:

P{ X(tn) Xn / X(tn-1),...,X(t1) } = P{ X(tn) Xn / X(tn-1) }

En nuestro objeto de estudio, que son las cadenas markovianas, tenemos que en una cadena markoviana de primer orden se cumplirá:

Ahora definimos un estado como:

Por lo tanto:

De la misma manera obtenemos:

Por lo tanto, según se ha deducido, mediante los estados podemos pasar de una cadena de orden n a otra de orden 1, ya que hemos formado con los estados la cadena

Aclaremos lo anterior con un pequeño ejemplo:

Ejemplo 10: Cadena markoviana de 2º orden.

Si por ejemplo la secuencia es del tipo abaabbaaab..., tendremos:

Por estados:

Cuando ocurre que:

En el ejemplo anterior:

Definición 8: Matriz de probabilidades de transición:

P = , siendo P{x_n+1= j / x_n= i} = p_ij

Propiedades de P:

1. Es una matriz cuadrada.
2. p_ij 0, i,j
3. p_ij = 1

Ahora sean:

_n = ( p(x_n=1) , ... , p(x_n=M) )
_n+1 = ( p(x_n+1=1) , ... , p(x_n+1=M) )
p(x_n+1= j) = p(x_n= i, x_n+1= j) = p(x_n= i)·p_ij

Las probabilidades de transición del estado n+1 son:

n+1 = n·[P]

Por lo tanto, dado ₁, se obtiene

_n = ₁·[P]^n-1

Ejemplo 11:
Dado el diagrama de estados

una secuencia válida podría ser: abadcb...

Como cada estado depende del anterior (cadena markoviana), se observa como una característica de este ejemplo que, si el estado inicial es a, los estados a y c sólo pueden aparecer en posiciones impares de la cadena, y los estados b y d sólo en posiciones pares. Ocurriría lo mismo si el estado inicial fuera el c, y ocurriría lo contrario si el estado inicial fuera b ó d.

Periodicidad

La probabilidad de ir del estado i al estado j en n saltos se expresa como:

Pij(n) = P{xL+n= j / xL= i} = pih·phj(n-1)

La probabilidad de llegar al mismo símbolo (estado i) tras L saltos será P_ii^(L). Si P_ii^(L) , entonces diremos que el estado i es un estado periódico de periodo d=L. Si todos los estados tienen el mismo periodo, la cadena es periódica.

Cadenas de Markov reducibles e irreducibles

Para entenderlo mejor, veamos el siguiente ejemplo:

Ejemplo 12:

Se ve claramente que P_ac⁽ⁿ⁾ 0, pero P_ca⁽ⁿ⁾ = 0, n

Los estados conectados entre sí forman un cluster. En el dibujo hay dos, y están rodeados en rojo y azul.

Un estado es transitorio si, después de pasar por él una o varias veces, no se vuelve a pasar después por él ninguna vez más.

Si todos los estados están conectados entre sí y no son transitorios, se dice que la cadena es irreducible.

En el ejemplo anterior, hay una cadena reducible compuesta por dos cadenas irreducibles (los clusters antes mencionados). Cuando se pasa del estado b al c (transición en color verde), ya no hay manera de volver a los estados a y b. Por lo tanto, estos dos estados son transitorios en la cadena total.

Si la cadena es aperiódica, irreducible y homogénea, entonces

existe un tal que = ·[P]

n+L = , L

Para demostrar el teorema de procesado de información, nos hace falta tener claros unos conceptos:

Una cadena de tres v.a. X, Y, Z es de Markov si cumplen:

• Si Z = f(Y) => X -> Y -> Z
• Independencia condicionada: X y Z condicionadas por Y son independientes. Entonces:
  
  
• Simetría:
  
  

Ejemplo 14::

Ahora podemos probar un importante teorema demostrando que ningún proceso de la v.a. Y, ya sea aleatorio o determinista, va a aumentar la información que Y tiene de X.

1.5.2. Demostración del Teorema de Procesado de Información

Si X -> Y -> Z, entonces I(X;Y) I(X;Z)

Demostración: Usando la regla de la cadena:

I(X;Y,Z) = I(X;Z) + I(X;Y/Z) = I(X;Y) + I(X;Z/Y)
Como I(X;Y/Z)0, y I(X;Z/Y)=0:

I(X;Y) I(X,Z)

Nota: Si Z = f(Y) (proceso de Markov), podemos afirmar que I(X;Y) I(X;f(Y))

Corolario: Si X->Y->Z entonces

I(X;Y/Z)I(X;Y)

Luego la independencia entre X e Y disminuye o permanece igual introduciendo la v.a. Z.

Hay que tener cuidado, pues es posible que ocurra que I(X;Y/Z)I(X;Y) si resulta que X, Y, Z   NO forman una cadena de Markov.

Ejemplos:

1.6. Límite de Fano

Supongamos que conocemos una v.a. Y y que queremos conocer el valor de una v.a. correlada X. Pues bien, la desigualdad o límite de Fano relaciona la probabilidad de error que tenemos en adivinar X a partir de H(X,Y). Ya sabemos que la entropía de una v.a. X dada otra Y es cero si X es función de Y; luego, según Fano, se podría estimar X sin probabilidad de error si ocurre que H(X/Y)=0. Obviamente, X es función de Y y X es lo que deseo hallar, por lo que nosotros esperamos estimar X con una pequeña probabilidad de error si H(X/Y) es pequeña.

Ahora supongamos que queremos estimar una v.a. X con una distribución p(x). Observamos una v.a. Y relacionada con X a través de la distribución condicional p(y/x). A partir de Y, podemos calcular una función f(Y)=X', que es una estimación de la v.a. X. Entonces, ¿cuál es la probabilidad de que XX'? Lo expresaremos como Pe=Pr{xx'}.

Entonces, la cadena X-> Y-> X' es una cadena de Markov. La desigualdad de Fano nos dice que:

Demostración: Definimos una variable E de error aleatorio:

E=1 si xx'; E=0 si x=x'. Si ahora hallo H(E,X/Y), entonces:

H(E,X/Y) = H(X/Y) + H(E/X,Y) = H(E/Y) + H(X/E,Y)

Como H(E/Y)H(E), y H(E,X/Y)=0:

H(X/E,Y) = H(X/Y) - H(E/Y) H(X/Y) - H(E)
H(X/E,Y) = P(E=0)·H(X/Y,E=0) + P(E=1)·H(X/Y,E=1) = Pe·H(X/Y,E=1) Pe·log₂(|X|-1)

De las dos anteriores inecuaciones, y sabiendo que log₂(|X|-1) < log₂(|X|) y que H(E) 1, entonces:

Pe·log₂(|X|-1) H(X/E,Y) H(X/Y) - H(< B>E) H(X/Y) - 1

[Tema anterior] [Temario] [Tema siguiente]