Teoría de la Información

Modulo: Procesos Estocásticos / Cadena de Markov

. Jaime Ramírez Artunduaga (2019-2)

1. Procesos Estocásticos

1.1 Concepto (1):

• En estadística, y específicamente en la teoría de la probabilidad, un

proceso estocástico es un concepto matemático que sirve para caracterizar
una sucesión de variables aleatorias (estocásticas) que evolucionan en función
de otra variable, generalmente el tiempo.

• Cada una de las variables aleatorias del proceso tiene su propia función de
distribución de probabilidad y, entre ellas, pueden estar correlacionadas o no.

• Cada variable o conjunto de variables sometidas a influencias o impactos

aleatorios constituye un proceso estocástico.
1.2 Ejemplos:

Los siguientes son ejemplos dentro del amplio grupo de las series temporales :

• Señales de telecomunicación
• Señales biomédicas (electrocardiograma, encefalograma, etc.)
• Señales sísmicas
• El número de manchas solares año tras año
• El índice de la bolsa segundo a segundo
• La evolución de la población de un municipio año tras año
• El tiempo de espera en cola de cada uno de los usuarios que van llegando a
una ventanilla
• El clima es un gigantesco cúmulo de procesos estocásticos
interrelacionados (velocidad del viento, humedad del aire, etc) que
evolucionan en el espacio y en el tiempo.
El índice de la bolsa es un ejemplo de proceso estocástico de tipo no estacionario
(por eso no se puede predecir).
1.3 Cadenas de Markov (2):

Reciben su nombre del matemático ruso Andrei Andreevitch Markov

• En los procesos estocásticos se pueden usar las matrices para definir el

número de evento, ya que no necesitan la historia para "predecir", sino de los
hechos que están presentes se "predice" un comportamiento: cadenas de
Markov.

• En la teoría de la probabilidad se conoce como cadena de Márkov a un

tipo especial de proceso estocástico discreto en el que la probabilidad de que
ocurra un evento depende del evento inmediatamente anterior.

• En efecto, las cadenas de este tipo tienen memoria. "Recuerdan" el

último
evento y esto condiciona las posibilidades de los eventos futuros. Esta
dependencia del evento anterior distingue a las cadenas de Márkov de las
series de eventos independientes, como tirar una moneda al aire o un dado.
Definición formal de cadena de Markov: (1) (8)

• En matemática: una cadena de Markov se define como un proceso

estadístico discreto que cumple con la propiedad de Markov , es decir, si se
conoce la historia del sistema hasta su instante actual, su estado presente
resume toda la información relevante para describir en probabilidad su estado
futuro.

• Una cadena de Markov es una secuencia X1, X2, X3,... de variables (eventos)
aleatorias.

• El rango de estas variables, es llamado espacio estado, el valor de Xn es el

estado del proceso en el tiempo n. Si la distribución de probabilidad condicional
de Xn+1 en estados pasados es una función de Xn por sí sola, entonces:
1.4 Fuente de Información de Markov (3), (4), (7), (8)

• Una fuente de información de Markov es aquella que contiene un conjunto de:

q símbolos, en la que la presencia de uno de ellos: Xn+1 depende de un número
finito: n de símbolos precedentes.

• En una fuente de Markov de orde n, la probabilidad de que suceda un símbolo

cualquiera depende de los n símbolos precedentes.

• Puesto que existen: q símbolos distintos, una fuente de Markov de orden: n

admitirá: qn estados posibles.

• Un procedimiento simple de entender el comportamiento de la fuente de

Markov consiste en utilizar un diagrama de estados.

• En este diagrama cada uno de los qn estados posibles de la fuente se

representa por un punto, indicándose mediante flechas las transiciones entre
estados.
Ejercicio:

Considérese una fuente de Markov de segundo orden con un alfabeto binario M=(0,1).
Supóngase que las probabilidades condicionales son las indicadas a continuación.
Haga una representación del diagrama de estado de esta fuente:

P(0/00) = P(1/11) = 0.8; P(1/00) = P(0/11) = 0.2

P(0/01) = P(0/10) = P(1/01) = P(1/10) = 0.5

Solución:

Por ser q = 2 y haber supuesto la fuente de Markov de segundo orden se tiene 4

estados diferentes ( 22 ) : 00, 01,10, 11

En la figura No.2.4 se representa el diagrama se estados de la fuente de Markov

(ergódica). Los cuatro estados se representan por cuatro puntos. Las transacciones
posibles, mediante flechas entre estados, indicándose sobre cada una ellas la
Probabilidad asociada.
Por ejemplo: si se está en el estado 00 se puede pasar al 01 ó al 00, pero nunca a los
estados 10 y 11. La probabilidad de permanecer en el estado 00 es 0.8 y la de pasar
al
01 es de 0.2.
Ejercicio
La probabilidad de recibir de manera errónea un bit transmitido por un canal de
transmisión digital, es 0.1. Además, supóngase que los ensayos de transmisión son
independientes. Sea X= número de bits recibidos con error en los próximos cuatro bits
que serán transmitidos. Descríbase el espacio el muestral de este experimento e
indíquese el valor de X en cada resultado. Calcúlese P(X=2).

Solución:

• Tomemos : E como bit errado y C como bit sin error (correcto).

Combinación X Combinación X
CCCC 0 ECCC 1
CCCE 1 ECCE 2
CCEC 1 ECEC 2
CCEE 2 ECEE 3
CECC 1 EECC 2
CECE 2 EECE 3
CEEC 2 EEEC 3
CEEE 3 EEEE 4
• El evento en que X=2 (dos bits con error), esta formado por 6 resultados:

(CCEE, CECE, CEEC, ECCE, ECEC, EECC)

• Entonces tomemos cualquiera de los 6 eventos ( grupos de 4 bits con dos bits
errados): EECC, su probabilidad es:

P(EECC) = P(E)P(E)P(C)P(C) = (0.1)(0.1)(0.9)(0.9) = 0.0081

• Como los eventos (grupos de 4 bits) son mutuamente excluyentes, la

probabilidad de suceso de cada uno de ellos es igual, por lo tanto:

P(X=2) = 6(0.0081) = 0.0486 (4.86%)

Ejercicio

Una fuente de información dispone de cuatro mensajes diferentes que puede generar
(entregar) durante un determinado tiempo. Estos mensajes pueden sufrir errores que
requieren ser reparados. Supóngase que cada mensaje que sale tiene,
independientemente de los otros, una probabilidad 0.1 de sufrir un error, de tal forma que
el número de mensajes a ser reparados fuera del tiempo de generación, sigue una
distribución binomial. La fuente sólo puede hacer las reparaciones durante el tiempo de no
generación , las cuales requieren de todo un tiempo igual a la de generación , por mensaje
errado. Además la demanda (solicitud) de mensajes es siempre suficiente para que
puedan entregarse los mensajes disponibles durante el tiempo de generación establecido.
Determinar la matriz de probabilidades de transición de la cadena de Markov. Los tiempos
de generación y reparación son iguales y sucesivos.

Solución:

• Como la fuente repara un mensaje errado durante todo el periodo de reparación,

jamás va tener 0 mensajes disponibles , durante el tiempo de generación . De esta
forma el espacio de los estados de la cadena es: S= (1,2,3,4) (número posible de
mensajes disponibles al inicio de cada periodo de generación)
• Con el fin de obtener la matriz de probabilidades de transición en un paso de la
cadena de Markov, se considera las probabilidades:

p i j  P  X n 1  j / X n  i , i, j  1, 2, 3, 4

• Donde X n indica el número de mensajes disponibles a comienzo del periodo de

generación (entrega o suministro)

• Sea, Yn la variable aleatoria que indica el número de mensajes con error durante el
n-ésimo periodo de generación . Entonces:

Yn  B i; 0,1

:
• Donde i representa el número de mensajes disponibles , durante al comienzo
del tiempo de Generación (entrega o envío). En esta forma, para las tres primeras filas
de la matriz, tenemos:

pi j  P Yn  i  1  j , i  1, 2, 3; j  1,  , i  1

• para , porque si hay mensajes disponibles y por el

pi j de0 reparación
periodo j sólo
i  2se repara máximo un i mensaje, es posible tener un número
superior a mensajes disponibles al comienzo del periodo de generación.
i 1

• Para la cuarta fila tenemos las probabilidades:

p4 j  P Yn  5  j , j  1, 2, 3 y p4 4  PYn  1
• Por lo tanto la matriz de transferencia de la cadena de Markov, es:

0.1000 0.9000 0  0
0.0100 0.1800 0.8100  0
P  
0.0010 0.0270 0.2430 0.7290 
 
0.0001 0.0036 0.0486 0.9477 

Ejercicio

Considérese una cadena de Markov con el espacio de los estados S=(0,1.2, 3,4,5,6) y con
una matriz de probabilidades de transición, indicada a continuación. Determinar el
diagrama de estados correspondiente.
Solución:
1.5 Definición de Información (3) , (5)

“Sea E un suceso que puede presentarse con probabilidad P(E). Cuando E

tiene lugar, decimos que hemos recibido: I(E) = log (1/P(E)) unidades de
información”

Si el logaritmo esta en base 2, la unidad de información es bit :

I(E) = log2 (1/P(E)) bits

 
Si el logaritmo esta en base natural, la unidad de información es nats:
 
I(E) = ln (1/P(E)) nats

Si el logaritmo esta en base 10, la unidad de información es Hartleys:

 
I(E) = log10 (1/P(E)) Hartleys
Ejercicio

Determinar las unidades de información de un suceso a la salida de una fuente

binaria, si la probabilidad de los dos sucesos es igual.

Solución:

I(E) = log2 (1/P(E)) = log2 (1/1/2) = log2 (2)= 1 bit

Es decir : un bit es la cantidad de información obtenida al especificar una de

posibles alternativas igualmente probables. Esta situación se presenta por ejemplo:
al lanzar una moneda al aire o al examinar la salida de un sistema de comunicación
binaria.

Ejercicio

Considérese una imagen de televisión formada por una estructura de puntos

(pixeles), dispuestos en 500 filas y 600 columnas. Supongamos que cada uno de
esos 500X600 = 300.000 puntos pude adoptar uno de 10 niveles de brillo diferentes.
Determinar la información que contiene cada imagen (pantallazo en bits), si todas
son igualmente probables.
Solución:

Cantidad de símbolos: q = 10 (niveles de brillo)

Orden de agrupamiento: 300.000 (puntos: pixeles)
Cantidad de imágenes distintas de TV: 10300.000
Probabilidad de una imagen cualquiera: P(E) = 1/ 10300.000

I(E) = log2 (1/P(E)) = log2 (1/ 1/ 10300.000)) = log2 ( 10300.000) = 300.000 log2 10 = 104 bits

1.6 Fuente de información de memoria nula (3) , (4)

• Es aquella fuente donde sus símbolos emitidos : S (S1, S2, ….. ) son
estadísticamente independientes:

Fuente S1, S2, …..

• Esta fuente puede describirse completamente mediante la fuente: S y las
probabilidades con que los símbolos se presentan: P(s 1), P(s2), ….. P(sq)

• La cantidad de información dada por la presencia de un símbolo s i , esta

dada por:
1
I ( s i )  log 2 bits
P( si )

• A medida que la probabilidad de presencia de un símbolo sea menor ,

mayor es la información que genera cuando este símbolo se presenta.

• La cantidad de información media dada por la fuente de memoria nula, para

símbolos independientes, esta dada por:

1
H ( s)   P( si ) I ( si )  P( si ) log 2 bits
s s P( si )

• Esta cantidad de información de la fuente, recibe el nombre de entropía H(s)

Ejercicio

Determinar la cantidad de entropía H(s), dada por la fuente S (S1, S2, S3 ) con P(s1) =
1/2 y P(s2) = P(s3) = 1/4.

Solución:

H ( s )  1 / 2 log 2 2  1 / 4 log 2 4  1 / 4 log 2 4  3 / 2 bits

1.7 Propiedades de la entropía (3)

1. Si todos los q símbolos de la fuente de memoria nula son equiprobables:

el valor máximo de su entropía H(s) es log2 (q).

2. La cantidad máxima de información dada por una fuente de memoria nula

de q símbolos, crece lentamente al aumentar q
Ejercicio

Comprobar para el caso del ejercicio inmediatamente anterior el cumplimiento de la

primera propiedad.

Solución:

P(s1) = P(s2) = P(s3) = 1/3 y q = 3. Entonces:

H ( s )  1 / 3 log 2 3  1 / 3 log 2 3  1 / 3 log 2 3  log 2 3 bits

1.8 Función entropía H(w) (3), (4)

En una fuente binaria de memoria nula los símbolos se reducen a S =(0.1) . Sí

la P(0) = w y la P(1) = 1- w, se tiene la función entropía:

1 1
H ( w)  w log 2  (1  w) log 2
w 1 w
Sí w  0  H ( w)  0 : entonces la fuente no suministra ninguna información
(solo existe la probabilidad absoluta que salga un 1)

Sí w  1 / 2  H ( w)  1 : entonces símbolos equiprobables. Información

máxima.

Sí w  1  H ( w)  0 : entonces la fuente no suministra ninguna

información (solo existe la probabilidad absoluta que salga un 0)

En la siguiente figura se representa la curva de variación de la función

entropía H(w)

• La salida de una fuente binaria está constituida por dígitos binarios o

binits.

• Una secuencia de binits producida por una fuente de información binaria

de memoria nula, de 0s y de 1s equiprobables, suministra un bit de
información por binit .
Función entropía H(w)
• Si los 0s y los 1s , de una fuente binaria, no son igualmente probables, la
cantidad de información dada por un binit será menor ó mayor de 1 bit
dependiendo de los valores de las probabilidades.

• Sin embargo, la cantidad media de información suministrada por un binit de

tal fuente será siempre menor o igual a un bit por binit (ver figura anterior).

1.9 Cantidad de información de una fuente de Markov de orden n (3), (5)

• Si nos encontramos en el estado definido por: ( s , s ,  , s )

j1 j2 jn

• La probabilidad condicional de recibir el símbolo si es:

P ( si / s j1 , s j2 , , s jn )
• La información suministrada si : s i se presenta cuando estamos en el
estado ( s i / s j , s j ,  , s jn ) es:
1 2

1
I ( si / s j1 , s j2 ,  , s jn )  log 2
P( si / s j1 , s j2 , , s jn )

• Por lo tanto, la cantidad media de información ó entropía de la fuente de

Markov de orden n , es dado:

1
H ( s )   P( s j1 , s j2 ,  , s jn , si )  log 2
m 1 P( si / s j1 , s j2 , , s jn )
Ejercicio
Determinar la cantidad media de información (entropía) de la fuente de Markov,
cuyo diagrama de estados se indica en la figura No. 2.4.

Solución:
Teníamos: P(0/00) = P(1/11) = 0.8; P(1/00) = P(0/11) = 0.2
P(0/01) = P(0/10) = P(1/01) = P(1/10) = 0.5

1
Entonces: H ( s )   P( s
s
j , s k , s i )  log 2
P( si / s j , s k )
1 1
 P (000)  log 2  P (001)  log 2
P (0 / 00) P (1 / 00)
1 1
 P (010)  log 2  P (011)  log 2
P (0 / 01) P (1 / 01)
1 1
 P (100)  log 2  P (101)  log 2
P (0 / 10) P (1 / 10)
1 1
 P (110 )  log 2  P (111 )  log 2
P (0 / 11) P (1 / 11)
Reemplazando valores:

1 1
H ( s )  0.8  log 2  0.2  log 2
0.8 0.2
1 1
 0.5  log 2  0.5  log 2
0.5 0. 5
1 1
 0.5  log 2  0.5  log 2
0.5 0. 5
1 1
 0.2  log 2  0.8  log 2
0.2 0.8
Factorizando:

1 1 1
H ( s )  2  0.8  log 2  2  0.2  log 2  4  0.5  log 2
0.8 0.2 0. 5

Aplicando: log10 x
log 2 x   3.32 log 10 x
log10 2

Tenemos:
H ( s )  0.514  0.928  1.999  3.44 bits
1.10 Canales de información (3), (6)

Un canal de información viene determinado por:

• Un conjunto de símbolos de entrada A   ai  , i  1, 2,  , r

•  
Un conjunto de símbolos de salida B  b j , j  1, 2,  , s

• 
Un conjunto de probabilidades condicionales P b j / a i 
P b j / ai  es la probabilidad de recibir a la salida el símbolo b j cuando
se envía el símbolo de entrada a
i

a1  b1 
a  b 
A    Pb j / ai    2  B
 2  
  
ar  bs 
• La descripción del canal se hace de forma más conveniente disponiendo
las probabilidades condicionales, como se indica a continuación, teniendo
en cuenta que: P (b j / ai )  Pi j

P11 P12  P1S

P21 P22  P2 S
P

Pr1 Pr 2  PrS

• Un canal de información está completamente definido por su matriz de

probabilidades. Por lo tanto, se usa indistintamente P para representar un
canal o su matriz.

• Cada fila de la matriz corresponde a una entrada del canal y cada columna
a una salida.

• La suma de los términos de una fila cualquiera es igual a la unidad.

1.11 Canal binario simétrico (3), (5)

• Un canal binario simétrico (BSC: Binary Symmetric Channel) es de gran

importancia teórica.

P
0 0
P

P
1
1
P

• Tenemos que: P  1  P

• Este canal tiene dos símbolos de entrada (a1  0, a 2  1) y dos

símbolos de salida .
(b1  0, b2  1)
• Si las probabilidades de recibir un 0 al enviar un 1 y viceversa son iguales a:
P
, entonces el canalPes simétrico. Por lo tanto la probabilidad de que
exista un error es de .

• La matriz del canal BSC es:

p p
P
p p 

1.12 Probabilidad total (6)

• La probabilidad total para dos eventos cualquiera A y B, esta dada por:

P( B)  P( B  A)  P( B  A )  P( B / A) P ( A)  P( B / A ) P( A )
• En la siguiente figura se hace una representación de un evento en dos
subconjuntos mutuamente excluyentes:

Ejercicio

Supongamos que la probabilidad de que exista una falla en el envío de un

paquete de datos, en una red de transmisión de datos, sea de 0.10, si hay un
alto grado de congestión de la red. Por otro lado que, la probabilidad
de que el envío falle sea de 0.005 cuando no hay alto grado de congestión. El 20%
de los envíos está sujeto a altos grados de congestión . ¿Cuál es la probabilidad de
que el envío falle?.
Solución:

Supongamos:
B: el evento donde el envío falle
A: el evento donde el envío esta expuesto a alto grado de congestión
A : el evento donde el envío no esta expuesto a alto grado de congestión

La probabilidad solicitada es: P(B)

La información que se dispone es:

P( B / A)  0.10 P ( B / A )  0.005 P ( A)  0.20

Por lo tanto: P ( A )  0.80

Entonces:
P ( B )  P ( B / A) P ( A)  P ( B / A ) P ( A )

P( B)  (0.10)(0.20)  (0.005)(0.80)  0.024  (2.4%)

1.13 Teorema de Bayes (7), (9)

• De la definición de probabilidad condicional:

P( A  B)  P( A / B ) P ( B )  P ( B  A)  P( B / A) P( A)

• Si se consideran los términos segundo y último de las expresión

inmediatamente anterior:

P ( B / A) P ( A)
P( A / B) 
P( B)

• La anterior expresión es el Teorema de Bayes: mediante lo cual se puede

determinar una probabilidad condicional ( dado la presencia del evento B
cual es la probabilidad que suceda el evento A)
Ejercicio:

Para el ejercicio inmediatamente anterior, se desea saber: ¿cuál es la probabilidad

de que la red este congestionada si el envió del paquete falla?.

Solución:

Se tiene según el ejercicio anterior:

B: el evento donde el envío falle

A: el evento donde el envío esta expuesto a alto grado de congestión

P( A / B)
Se desea conocer:

Se conoce desde el ejercicio anterior por enunciado y por resultado:

P ( B / A)  0.10 P ( A)  0.20 P ( B)  0.024

P( B / A) P ( A) (0.10)( 0.20)
P( A / B)    0.0833 (8.33%)
Entonces: P( B) 0.024
Preguntas y ejercicios

1. ¿Qué se entiende por variable aleatoria?. De algunos ejemplos prácticos.

2. ¿ Qué se entiende por proceso estocástico?. De algunos ejemplos prácticos.

3. Defina la cadena de Markov. Haga una representación de la cadena de

Markov para un caso especifico.

4. Defina en que consiste una fuente de información de Markov. ¿Cuál es la

forma más eficiente para entender una fuente de información de Markov?.

5. Considérese una fuente de Markov de segundo orden con un alfabeto binario

M=(0,1). Supóngase que las probabilidades condicionales son las indicadas a
continuación. Haga una representación del diagrama de estado de esta fuente:

P(1/00) = 1.0; P(1/01) = 0.2; P(0/01) = 0.8; P(1/11) = 0.2

P(0/11) = 0.8; P(0/10) =0 .3; P(1/10) = 0.7
6. ¿Qué se entiende por fuente de información de memoria nula?. Haga una relación
de algunos ejemplo prácticos de este tipo de fuente.

7. Determinar la cantidad media de información (entropía) de la fuente de Markov,

cuyo diagrama de estados se indica en la siguiente figura.
8. Describa el significado de la función entropía H(w e indique la importancia conceptual
que esta función representa en la teoría de la información

9. Describa en que consiste una canal de información. ¿Cuál es la información que

nos representa la matriz de probabilidades de un canal de información?

10. ¿Qué se entiende por un canal binario simétrico (BSC: Binary Symmetric Channel)?.
¿Cuál es de gran importancia teórica que este canal tiene?.

11. Supongamos que la probabilidad de que exista una falla en el envío de un

paquete de datos, en una red de transmisión de datos, sea de 0.08, si hay un
alto grado de congestión de la red. Por otro lado que, la probabilidad
de que el envío falle sea de 0.004 cuando no hay alto grado de congestión. El 18%
de los envíos está sujeto a altos grado de congestión . ¿Cuál es la probabilidad de
que el envío falle?.

12. ¿Qué se entiende entropía H(s), de una fuente de información?.

13. Determinar la cantidad de información (entropía) que nos puede generar una fuente de
Información correspondiente al lanzamiento de un dado

14. ¿Cuál es la información que esencialmente nos representa la aplicación del teorema
de Bayes?

15. Para el ejercicio inmediatamente anterior, se desea saber: ¿cuál es la probabilidad de

que la red este congestionada si el envió del paquete falla?.

16. Una fuente de información dispone de cuatro mensajes diferentes que puede
generar (entregar) durante un determinado tiempo. Estos mensajes pueden sufrir
errores que requieren ser reparados. Supóngase que cada mensaje que sale tiene,
independientemente de los otros, una probabilidad 0.08 de sufrir un error, de tal
forma que el número de mensajes a ser reparados fuera del tiempo de generación,
sigue una distribución binomial. La fuente sólo puede hacer las reparaciones durante
el tiempo de no generación , las cuales requieren de todo un tiempo igual a la de
generación , por mensaje errado. Además la demanda (solicitud) de mensajes es
siempre suficiente para que puedan entregarse los mensajes disponibles durante el
tiempo de generación establecido. Determinar la matriz de probabilidades de
transición de la cadena de Markov. Los tiempos de generación y reparación son
iguales y sucesivos.
Referencia Bibliográfica:

(1) http://es.wikipedia.org/wiki/Proceso_estocástico

(2) http://es.wikipedia.org/wiki/Cadena_de_Markov

(3) Abramson, Norman, “Teoría de la Información y Codificación” (sexta edición).

Paraninfo: McGraw-Hill. ISBN 84-283-0232-4

(4) Moreno Osorio,Luis G. , “Procesos Estocásticos”, Universidad Nacional de Colombia,

ISBN 958-9220-08-8

(5) Kijima, Masaaki, “Markov Processes for Stochastic Modeling “ (1st edición).
Cambridge: Chapman & Hall. ISBN 0 412 60660 7.

(6) Fink, A. Gernot, “Markov Models for Pattern Recognition , fromTheory to Apllications
“, Springer, 2011, ISBN 978-3-540-71770-6

(7) Montgomery, Douglas / Runger, George, “ Probabilidad y Estadística: aplicaciones a

la Ingeniería” , McGraw-Hill. ISBN 970-10-1017-5
(8) Liptser, R. / Shiryaer, A., “ Statistics of Radom Processes”, 2004.

(9) Chirikjian, Greory,S., “ Stochastic Models, Information Theory, and Lie Grups” ,
Birkhauser, ISBN 978-0-8176-4802-2