Captulo 10

Cadenas de Markov

PROCESOS ESTOCSTICOS

Una sucesin de observaciones X1 , X2 , . . . se denomina proceso estocs-

tico
Si los valores de estas observaciones no se pueden predecir exactamente

Pero se pueden especificar las probabilidades para los distintos valores

posibles en cualquier instante de tiempo.

X1 : v.a. que define el estado inicial del proceso

Xn : v.a. que define el estado del proceso en el instante de tiempo n

Para cada posible valor del estado inicial s1 y para cada uno de los sucesivos
valores sn de los estados Xn , n = 2, 3, . . ., especificamos:

P (Xn+1 = sn+1 | X1 = s1 , X2 = s2, . . . , Xn = sn )

103
104 Cadenas de Markov

CADENAS DE MARKOV

Una cadena de Markov es un proceso estocstico en el que

Si el estado actual Xn y los estados previos X1 , . . . , Xn1 son conocidos

La probabilidad del estado futuro Xn+1

F No depende de los estados anteriores X1, . . . , Xn1 , y

F Solamente depende del estado actual Xn .

Es decir,

Para n = 1, 2, . . . y

Para cualquier sucesin de estados s1 , . . . , sn+1

P (Xn+1 = sn+1 | X1 = s1 , X2 = s2, . . . , Xn = sn ) =

= P (Xn+1 = sn+1 | Xn = sn )
Cadenas de Markov 105

EJEMPLO

Consideremos que en un locutorio telefnico con 5 lneas de telfono en

un instante de tiempo dado puede haber un nmero cualquiera de lneas
ocupadas. Durante un periodo de tiempo se observan las lneas telefnicas
a intervalos de 2 minutos y se anota el nmero de lneas ocupadas en cada
instante.

Sea X1 la v.a. que representa el nmero de lneas ocupadas al principio del

periodo.

Sea X2 la v.a. que representa el nmero de lneas ocupadas cuando se

observa en el segundo instante de tiempo, 2 minutos ms tarde.

En general, n = 1, 2, . . . Xn es una v.a. que representa el nmero de

lneas ocupadas cuando se observan en el instante de tiempo nsimo.

El estado del proceso en cualquier instante de tiempo es el nmero de lneas

que estn siendo utilizadas en ese instante.

Un proceso estocstico como el que acabamos de describir se llama proceso

de parmetro discreto, ya que las lneas se observan en puntos discretos
a lo largo del tiempo.

Para que el proceso estocstico del nmero

de lneas ocupadas sea una cadena de Markov
es necesario que la probabilidad de cada posible nmero de
lneas ocupadas en cualquier instante de tiempo
dependa solamente del nmero de
lneas ocupadas 2 minutos antes.
106 Cadenas de Markov

CADENAS DE MARKOV FINITAS

CON PROBABILIDADES DE
TRANSICIN ESTACIONARIAS

CADENA DE MARKOV FINITA

Es una cadena de Markov para la que existe slo un nmero finito k de

estados posibles s1 , . . . , sk y en cualquier instante de tiempo la cadena est
en uno de estos k estados.

PROBABILIDAD DE TRANSICIN

Es la probabilidad condicionada

P (Xn+1 = sj | Xn = si )

PROBABILIDAD DE TRANSICIN ESTACIONARIA

Una cadena de Markov tiene probabilidades de transicin estaciona-

rias si para cualquier par de estados si y sj existe una probabilidad de
transicin pij tal que

P (Xn+1 = sj | Xn = si ) = pij para n = 1, 2, . . .

Cadenas de Markov 107

MATRIZ DE TRANSICIN
MATRIZ ESTOCSTICA
Es una matriz cuadrada cuyos elementos son no negativos y tal que la
suma de los elementos de cada fila es igual a 1.

MATRIZ DE TRANSICIN EN UN SOLO PASO

Dada una cadena de Markov con k estados posibles s1 , . . . , sk y probabili-
dades de transicin estacionarias.

p11 p1k
p21 p2k

Si pij = P (Xn+1 = sj |Xn = si ) = P = .. ..
. .
pk1 pkk

La matriz de transicin P de cualquier cadena de Markov finita con

probabilidades de transicin estacionarias es una matriz estocstica

EJEMPLO
Supongamos que el clima de una determinada regin slo puede ser soleado
(s1) o nublado (s2 ) y que las condiciones del clima en maanas sucesivas forman
una cadena de Markov con probabilidades de transicin estacionarias. La matriz
de transicin est dada por:

0.7 0.3
P =
0.6 0.4
Si un da concreto est nublado, cul es la probabilidad de que est nublado
el da siguiente?

p22 = 0.4
108 Cadenas de Markov

MATRIZ DE TRANSICIN EN VARIOS PASOS

Dada una cadena de Markov con k posibles estados s1 , . . . , sk
y matriz de transicin P
(2)
Si notamos pij = P (Xn+2 = sj |Xn = si )

(2)
pij : Elemento de la isima fila y jsima columna de la matriz P 2
P m : Potencia msima de P , con (m = 2, 3, . . .) y
(m)
F pij : Elemento de la fila i y de la columna j de la matriz P m

GENERALIZANDO
(m)
P m es la matriz de probabilidades pij de que la cadena pase del estado si
al estado sj en m pasos; para cualquier valor de m, (m = 2, 3, . . .).

P m es la matriz de transicin de m pasos de la cadena de Markov

EJEMPLO
En el ejemplo del clima con matriz de transicin

0.7 0.3
P =
0.6 0.4
Si un mircoles est nublado, cul es la probabilidad de que el viernes
siguiente haga sol?
Calculamos la matriz de transicin en dos pasos,

0.67 0.33
2
P =
0.66 0.34
= Probabilidad pedida es 0.66
Cadenas de Markov 109

VECTOR DE PROBABILIDADES INICIALES

VECTOR DE PROBABILIDADES

w = (w1 , . . . , wk ) se llama vector de probabilidades si

N wi 0 para i = 1, . . . , k, y
k
X
N wi = 1.
i=1

Consideramos una cadena de Markov con:

1. s1 , . . . , sk posibles estados en los que la cadena puede estar en el tiempo

de observacin inicial n = 1

2. Para i = 1, . . . , k; P (X1 = si ) = vi , con vi 0 y v1 + . . . + vk = 1

VECTOR DE PROBABILIDADES INICIALES

El vector de probabilidades v = (v1 , . . . , vk ) se llama vector de proba-

bilidades iniciales de la cadena.

El vector de probabilidades iniciales y

la matriz de transicin determinan la probabilidad
para el estado de la cadena en el segundo instante de tiempo,
dicha probabilidad viene dada por el vector vP

Adems, si las probabilidades de los diversos estados en el instante n se

especifican por el vector de probabilidades w, entonces

Las probabilidades en el instante n + 1

se especifican por el vector de probabilidades wP
110 Cadenas de Markov

EJEMPLO

En el ejemplo del clima con matriz de transicin:

0.7 0.3
P =
0.6 0.4

Suponemos que la probabilidad de que el mircoles haga sol es 0.2 y la

probabilidad de que est nublado es 0.8.
Calcular:
1. Probabilidad de que est nublado el jueves.
2. Probabilidad de que est nublado el viernes.
3. Probabilidad de que est nublado el sbado.

Solucin

1. Mircoles: v = (0.2, 0.8) = w = vP = (0.62, 0.38)

P [ est nublado el jueves] = 0.38

2. w = vP = (0.62, 0.38) = vP 2 = vP P = wP = (0.662, 0.338)

P [ est nublado el viernes] = 0.338

3. vP 2 = (0.662, 0.338) = vP 3 = vP 2P = (0.6662, 0.3338)

P [ est nublado el sbado] = 0.3338

Cadenas de Markov 111

EJEMPLO

Suponemos que en el ejemplo del locutorio telefnico los nmeros de lneas

que estn siendo utilizadas en los instantes de tiempo 1, 2, . . . constituyen
una cadena de Markov con probabilidades de transicin estacionarias.
Sea bi el estado en el que se estn utilizando exactamente i lneas en un
instante de tiempo determinado (i = 0, 1, . . . , 5)

Matriz de transicin P

0.1 0.4 0.2 0.1 0.1 0.1
0.2 0.3 0.2 0.1 0.1 0.1

0.1 0.2 0.3 0.2 0.1 0.1
P =



0.1 0.1 0.2 0.3 0.2 0.1
0.1 0.1 0.1 0.2 0.3 0.2
0.1 0.1 0.1 0.1 0.4 0.2

F Si las cinco lneas estn ocupadas en un instante de tiempo concreto.

P [ Exactamente 4 lneas ocupadas en el siguiente instante de tiempo] =

= p65 = 0.4

F Si en un instante de tiempo no hay ninguna lnea ocupada.

P [ Al menos una lnea ocupada en el siguiente instante de tiempo] =

= 1 p11 = 0.9
112 Cadenas de Markov

Matriz de transicin en dos pasos

0.14 0.23 0.2 0.15 0.16 0.12
0.13 0.24 0.2 0.15 0.16 0.12

0.12 0.2 0.21 0.18 0.17 0.12
P2 =



0.11 0.17 0.19 0.2 0.2 0.13
0.11 0.16 0.16 0.18 0.24 0.15
0.11 0.16 0.15 0.17 0.25 0.16

F Si dos lneas estn ocupadas en un instante de tiempo concreto.

P [ Cuatro lneas ocupadas dos instantes despus] = 0.17

F Si en un instante de tiempo concreto hay tres lneas ocupadas.

P [ Dos instantes despus haya de nuevo tres lneas ocupadas] = 0.2

0.123 0.208 0.192 0.166 0.183 0.128
0.124 0.207 0.192 0.166 0.183 0.128

0.120 0.197 0.192 0.174 0.188 0.129
P3 =



0.117 0.186 0.186 0.179 0.199 0.133
0.116 0.181 0.177 0.176 0.211 0.139
0.116 0.180 0.174 0.174 0.215 0.141

F Si las 5 lneas estn ocupadas en un instante de tiempo concreto.

P [ No haya lneas ocupadas tres instantes despus] = 0.116

Cadenas de Markov 113

F Si una lnea est ocupada en un instante de tiempo.

P [Tres instantes despus haya de nuevo una lnea ocupada] = 0.207

F Al inicio del proceso de observacin (instante n = 1)

P [ No haya lneas ocupadas] = 0.5

P [ Haya una lnea ocupada] = 0.3

P [ Haya dos lneas ocupadas] = 0.2

Vector de probabilidades iniciales: v =(0.5, 0.3, 0.2, 0, 0, 0)

vP =(0.13, 0.33, 0.22, 0.12, 0.1, 0.1) =

P [No haya lneas ocupadas en el instante 2] = 0.13

vP 2 = vP P = (0.1333, 0.227, 0.202, 0.156, 0.162, 0.12) =

P [Haya 2 lneas ocupadas en el instante 3] = 0.202

114 Cadenas de Markov

SUPUESTO PRCTICO DE
CADENA DE MARKOV

Consideremos el laberinto siguiente

Supongamos que introducimos un ratn de forma aleatoria en una de las

celdas de dicho laberinto.
Este ratn se traslada aleatoriamente de cada celda a una de las con-
tiguas.

PLANTEAMIENTO DE LA CADENA DE MARKOV

Y ESTUDIO

Definicin de las variables aleatorias

Xn celda ocupada en el instante n

Cadenas de Markov 115

Estados
Los posibles estados son: 1, 2, 3, 4, 5 y 6

Comprobar que se trata de una cadena de Markov (comprobar la condicin

de Markov)

Conocido el presente,
el futuro no depende del pasado

Se cumple la condicin de Markov

Es una cadena de Markov

Probabilidades de transicin

pij = P [Xn+1 = j|Xn = i]

Matriz de transicin

p11 p12 p13 p14 p15 p16
p21 p22 p23 p24 p25 p26

p31 p32 p33 p34 p35 p36

p41 p42 p43 p44 p45 p46

p51 p52 p53 p54 p55 p56
p61 p62 p63 p64 p65 p66
116 Cadenas de Markov

Desde el estado 1

p11 = P [Xn+1 = 1|Xn = 1] p12 = P [Xn+1 = 2|Xn = 1]

p13 = P [Xn+1 = 3|Xn = 1] = 0 p14 = P [Xn+1 = 4|Xn = 1]
p15 = P [Xn+1 = 5|Xn = 1] = 0 p16 = P [Xn+1 = 6|Xn = 1] = 0

Desde el estado 2

p21 = P [Xn+1 = 1|Xn = 2] p22 = P [Xn+1 = 2|Xn = 2]

p23 = P [Xn+1 = 3|Xn = 2] = 0 p24 = P [Xn+1 = 4|Xn = 2] = 0
p25 = P [Xn+1 = 5|Xn = 2] = 0 p26 = P [Xn+1 = 6|Xn = 2] = 0
Cadenas de Markov 117

Desde el estado 3

p31 = P [Xn+1 = 1|Xn = 3] = 0 p32 = P [Xn+1 = 2|Xn = 3] = 0

p33 = P [Xn+1 = 3|Xn = 3] p34 = P [Xn+1 = 4|Xn = 3] = 0
p35 = P [Xn+1 = 5|Xn = 3] = 0 p36 = P [Xn+1 = 6|Xn = 3]

Desde el estado 4

p41 = P [Xn+1 = 1|Xn = 4] p42 = P [Xn+1 = 2|Xn = 4] = 0

p43 = P [Xn+1 = 3|Xn = 4] = 0 p44 = P [Xn+1 = 4|Xn = 4]
p45 = P [Xn+1 = 5|Xn = 4] = 0 p46 = P [Xn+1 = 6|Xn = 4] = 0
118 Cadenas de Markov

Desde el estado 5

p51 = P [Xn+1 = 1|Xn = 5] = 0 p52 = P [Xn+1 = 2|Xn = 5] = 0

p53 = P [Xn+1 = 3|Xn = 5] = 0 p54 = P [Xn+1 = 4|Xn = 5] = 0
p55 = P [Xn+1 = 5|Xn = 5] p56 = P [Xn+1 = 6|Xn = 5]

Desde el estado 6

p61 = P [Xn+1 = 1|Xn = 6] = 0 p62 = P [Xn+1 = 2|Xn = 6] = 0

p63 = P [Xn+1 = 3|Xn = 6] p64 = P [Xn+1 = 4|Xn = 6] = 0

p65 = P [Xn+1 = 5|Xn = 6] p66 = P [Xn+1 = 6|Xn = 6]
Cadenas de Markov 119

Son estacionarias las probabilidades de transicin?

pij no depende del instante en que

se encuentre el proceso

las probabilidades de transicin son estacionarias

Matriz de transicin

p11 p12 0 p14 0 0
p21 p22 0 0 0 0

0 0 p33 0 0 p36
P =
p41 0 0 p44 0 0


0 0 0 0 p55 p56
0 0 p63 0 p65 p66

Matriz de transicin en dos pasos

P2

Desde el estado 1
120 Cadenas de Markov

Matriz de transicin en dos pasos

(2) (2)
p11 = p211 + p14p41 + p12p21 p12 = p12 p22 + p11 p12
(2) (2)
p14 = p14p44 + p11p14 p21 = p21 p11 + p22 p21
(2) (2)
p22 = p222 + p21p12 p24 = p21 p14
(2) (2)
p33 = p233 + p36p63 p35 = p36 p65
(2) (2)
p36 = p36p66 + p33p36 p41 = p41 p11 + p44 p41
(2) (2)
p42 = p41p12 p44 = p244 + p41 p14
(2) (2)
p53 = p56p63 p55 = p255 + p56 p65
(2) (2)
p56 = p55p56 + p56p66 p63 = p63 p33 + p66 p63
(2) (2)
p65 = p65p55 + p66p65 p66 = p266 + p63 p36 + p65 p56

Vector de probabilidades iniciales

v = (p1 , p2 , p3 , p4 , p5, p6)

P [estar en la celda 1 en el instante 1] = p1

P [estar en la celda 2 en el instante 1] = p2
P [estar en la celda 3 en el instante 1] = p3
P [estar en la celda 4 en el instante 1] = p4
P [estar en la celda 5 en el instante 1] = p5
P [estar en la celda 6 en el instante 1] = p6
Cadenas de Markov 121

Probabilidad de estar en cierta celda en el instante de tiempo 2

vP = ([p1 p11 + p2p21 + p4 p41 ], [p1 p12 + p2p22], [p3 p33 + p6 p63 ],
[p1 p14 + p4 p44 ], [p5 p55 + p6p65], [p3p36 + p5 p56 + p6p66])

P [estar en la celda 1 en el instante 2] = p1 p11 + p2 p21 + p4 p41

P [estar en la celda 2 en el instante 2] = p1p12 + p2 p22

P [estar en la celda 3 en el instante 2] = p3p33 + p6 p63

P [estar en la celda 4 en el instante 2] = p1p14 + p4 p44

P [estar en la celda 5 en el instante 2] = p5p55 + p6 p65

P [estar en la celda 6 en el instante 2] = p3p36 + p5 p56 + p6p66

CASO A

Consideremos que la probabilidad de introducir el ratn en cada una de las

celdas del laberinto para comenzar el experimento es la misma. Una vez
dentro del laberinto el ratn se va a cualquier celda contigua o se queda
en la celda en la que est con la misma probabilidad.
Probabilidades de transicin

Desde el estado 1

p11 = P [Xn+1 = 1|Xn = 1] = 1/3 p12 = P [Xn+1 = 2|Xn = 1] = 1/3

p13 = P [Xn+1 = 3|Xn = 1] = 0 p14 = P [Xn+1 = 4|Xn = 1] = 1/3
p15 = P [Xn+1 = 5|Xn = 1] = 0 p16 = P [Xn+1 = 6|Xn = 1] = 0
122 Cadenas de Markov

Desde el estado 2

p21 = P [Xn+1 = 1|Xn = 2] = 1/3 p22 = P [Xn+1 = 2|Xn = 2] = 1/3

p23 = P [Xn+1 = 3|Xn = 2] = 0 p24 = P [Xn+1 = 4|Xn = 2] = 1/3
p25 = P [Xn+1 = 5|Xn = 2] = 0 p26 = P [Xn+1 = 6|Xn = 2] = 0

Desde el estado 3

p31 = P [Xn+1 = 1|Xn = 3] = 0 p32 = P [Xn+1 = 2|Xn = 3] = 0

p33 = P [Xn+1 = 3|Xn = 3] = 1/2 p34 = P [Xn+1 = 4|Xn = 3] = 0
p35 = P [Xn+1 = 5|Xn = 3] = 0 p36 = P [Xn+1 = 6|Xn = 3] = 1/2

Desde el estado 4

p41 = P [Xn+1 = 1|Xn = 4] = 1/2 p42 = P [Xn+1 = 2|Xn = 4] = 0

p43 = P [Xn+1 = 3|Xn = 4] = 0 p44 = P [Xn+1 = 4|Xn = 4] = 1/2
p45 = P [Xn+1 = 5|Xn = 4] = 0 p46 = P [Xn+1 = 6|Xn = 4] = 0

Desde el estado 5

p51 = P [Xn+1 = 1|Xn = 5] = 0 p52 = P [Xn+1 = 2|Xn = 5] = 0

p53 = P [Xn+1 = 3|Xn = 5] = 0 p54 = P [Xn+1 = 4|Xn = 5] = 0
p55 = P [Xn+1 = 5|Xn = 5] = 1/2 p56 = P [Xn+1 = 6|Xn = 5] = 1/2
Cadenas de Markov 123

Desde el estado 6

p61 = P [Xn+1 = 1|Xn = 6] = 0 p62 = P [Xn+1 = 2|Xn = 6] = 0

p63 = P [Xn+1 = 3|Xn = 6] = 1/3 p64 = P [Xn+1 = 4|Xn = 6] = 0
p65 = P [Xn+1 = 5|Xn = 6] = 1/3 p66 = P [Xn+1 = 6|Xn = 6] = 1/3

Matriz de transicin

1/3 1/3 0 1/3 0 0
1/2 1/2 0 0 0 0

0 0 1/2 0 0 1/2
P =
1/2 0


0 1/2 0 0
0 0 0 0 1/2 1/2
0 0 1/3 0 1/3 1/3

Vector de probabilidades iniciales

1 1 1 1 1 1
v= , , , , ,
6 6 6 6 6 6

1
F P [estar en la celda 1 en el instante 1] =
6

1
F P [estar en la celda 2 en el instante 1] =
6

1
F P [estar en la celda 3 en el instante 1] =
6

1
F P [estar en la celda 4 en el instante 1] =
6
124 Cadenas de Markov

1
F P [estar en la celda 5 en el instante 1] =
6
1
F P [estar en la celda 6 en el instante 1] =
6

Probabilidad de estar en cierta celda en el instante de tiempo 2

2 5 5 5 5 2
vP = , , , , ,
9 36 36 36 36 9

2 5
P [ Celda 1 en el instante 2] = P [ Celda 2 en el instante 2] =
9 36
5 5
P [ Celda 3 en el instante 2] = P [ Celda 4 en el instante 2] =
36 36
5 2
P [ Celda 5 en el instante 2] = P [ Celda 6 en el instante 2] =
36 9

CASO B

Supongamos que en el laberinto el ratn se traslada a celdas contiguas con

igual probabilidad y que la probabilidad de introducir el ratn en cada una
de las celdas del laberinto para comenzar el experimento es

P [X1 = 1] = 0.2 P [X1 = 2] = 0.2 P [X1 = 3] = 0.1

P [X1 = 4] = 0.05 P [X1 = 5] = 0.05 P [X1 = 6] = 0.4

Cadenas de Markov 125

Matriz de transicin

1/3 1/3 0 1/3 0 0
1/2 1/2 0 0 0 0

0 0 1/2 0 0 1/2
P =
1/2 0

0 1/2 0 0
0 0 0 0 1/2 1/2
0 0 1/3 0 1/3 1/3

Vector de probabilidades iniciales

2 2 1 5 5 4
v= , , , , ,
10 10 10 100 100 10

P [Celda 1 en el instante 1] = 0.2 P [Celda 2 en el instante 1] = 0.2

P [Celda 3 en el instante 1] = 0.1 P [Celda 4 en el instante 1] = 0.05

P [Celda 5 en el instante 1] = 0.05 P [Celda 6 en el instante 1] = 0.4

En el instante 2: Calculamos vP

vP = (0.191666, 0.1666, 0.18333, 0.091666, 0.158333, 0.208333)

P [Celda 1, instante 2] = 0.191666 P [Celda 2, instante 2] = 0.1666

P [Celda 3, instante 2] = 0.1666 P [Celda 4, instante 2] = 0.091666

P [Celda 5, instante 2] = 0.158333 P [Celda 6, instante 2] = 0.208333

126 Cadenas de Markov

CASO C

Supongamos ahora que, en el laberinto el ratn ir a una celda contigua

con probabilidad proporcional al nmero de la celda y que la probabilidad
de introducir el ratn en cada una de las celdas del laberinto para comenzar
el experimento es la misma.

Matriz de transicin

1/7 2/7 0 4/7 0 0
1/3 2/3 0 0 0 0

0 0 3/9 0 0 6/9
P =
1/5 0


0 0 4/5 0
0 0 0 0 5/11 6/11
0 0 3/14 0 5/14 6/14

Vector de probabilidades iniciales

1 1 1 1 1 1
v= , , , , ,
6 6 6 6 6 6

1 1
P [Celda 1 en el instante 1] = P [Celda 2 en el instante 1] =
6 6
1 1
P [Celda 3 en el instante 1] = P [Celda 4 en el instante 1] =
6 6
1 1
P [Celda 5 en el instante 1] = P [Celda 6 en el instante 1] =
6 6
Cadenas de Markov 127

En el instante 2: Calculamos vP

71 10 23 8 125 379
vP = , , , , ,
630 63 252 35 924 1386

71 10
P [Celda 1 en el instante 2] = P [Celda 2 en el instante 2] =
630 63
23 8
P [Celda 3 en el instante 2] = P [Celda 4 en el instante 2] =
252 35
125 379
P [Celda 5 en el instante 2] = P [Celda 6 en el instante 2] =
924 1386

Bibliografa utilizada:

F D.R. Cox, H.D. Miller (1970). The Theory Stochastic Processes. Methuen.

F A.T. Bharucha-Reid (1960). Elements Of The Theory of Markov Processes And

Their Applications. McGraw Hill Series in Probability and Statistics.

Temporalizacin: Cuatro horas