Parte 2 de Las Cadenas de Marcov y Sus Ecuaciones
Parte 2 de Las Cadenas de Marcov y Sus Ecuaciones
Parte 2 de Las Cadenas de Marcov y Sus Ecuaciones
6 j | X0 = i) ,
fij(n) = P (Xn = j, Xr =
∀r = 1, 2, . . . , n − 1 donde n = 1, 2, 3, . . .
— Para n = 1,
ij = P (X 1 = j | X 0 = i) = pij.
f(1)
— Para n = 2,
= P (X2 = j, X1 6
= j | X0 = i) =
(2)
fij
X X
= P (X1 = k | X0 = i) · P (X 2 = j | X1 = k) = pikpkj =
6j
X k= k6
=j
(1)
= p kjf
k6=j
i.k
— Para n > 2,
X X
f ij(n) = P (X1 = k | X0 = i) · fkj(n−1) = pikfkj(n−1).
k6
=j k6
=j
26
En general, se tiene que
⎛ ⎞
(n−1)
⎛ f
⎞ ⎜ 1j
p .. . p 0 p .. . . ⎟
− 1,j+1 ⎜ (n−1) ⎟
⎜ 11 1,j 1
f(n) = ⎜ . . . . .. . . . ⎟ fj−1j
... ... ... ⎟ ⎟
⎜
pi1 . . . pi,j−1 0 pi,j+1 . . . ⎠ ⎜ f (n−1)
⎟
·j ⎝
⎝ jj j+1,j ⎠
. . . . .. ... ... ⎜
... ⎟
...
⎜ f (n−1)
. ⎟
es decir, con la columna j -ésima de la matriz de transición sustituida por una columna
de ceros.
También, se puede generalizar fj cuando se accede a j desde un estado i cualquiera:
X
∞
fij = f ij(n) .
n=0
Estado transitorio
En un estado recurrente, la probabilidad de que se regrese por primera vez a ese estado
en algún paso es 1, pero para otros estados sucede que
∞
X
fj = f(n)
j
<1
n=1
lo que significa es que no se regresa al estado Ej de modo seguro. Un estado así se denomina
transitorio.
Ejemplo.
21 21
0 0
cuyo diagrama es
27
1/2
E1 E2 1/2
1/2
1/4 1/4
E4 E3 1
1/2 1/2
(1)
f1 = 0
1 1 µ 1 ¶2
· =
(2)
f1 =
2 2 2
µ ¶3
(3)
f1 = 1
2
···
µ1 ¶n
(n)
f1 = ,
2
así,
X
∞ X∞ µ ¶n 1 1 1
1
f1 f (n) = = − − 1 = <1
1 − 12
1
= n=1 n=2
2 2 2
luego E1 es un estado transitorio. De hecho no se puede acceder a E1 desde E3 ó E4.
Estado ergódico
28
Ejemplo.
En la cadena de Markov ya estudiada con tres estados y matriz de transición
⎛ ⎞
p 1−p 0
T=⎝ 0 0 1 ⎠,
1−q 0 q
donde 0 <p< 1 y 0 <q < 1. Se puede comprobar que E1 es ergódico.
Se tenía que
(1)
f1 = p
(2)
f1 = 0
(3)
f1 = (1 − p) · 1 · (1 − q)
y, en general (n ≥ 3),
1 = (1 − p) · (1 − q) · q
n−3
f(n) .
Clasificación de cadenas
En esta sección se definen propiedades de las cadenas que, en realidad, son propiedades
comunes de los estados de la cadena.
29
Cadenas irreducibles
Una cadena irreducible es aquella en la que todos los estados son alcanzables desde
cualquier otro estado de la cadena en un número finito de pasos. Eso implica que se puede
entero n.
Una matriz A = [aij] se dice que es positiva si aij(n) > 0 para todos los i, j.
Una matriz de transición T se dice que es regular si existe un número entero N tal
que TN es positivo.
Una cadena regular obviamente es irreducible, sin embargo, lo contrario no tiene por
Ejemplo.
Como
µ1 0¶
T 2n = =I
2
01
y
µ ¶
2n+1 0 1
T = =T
1 0
para n = 1, 2, 3,... entonces ninguna potencia de T es una matriz positiva y por tanto no
es una cadena regular.
Ejemplo.
Se puede ver que una cadena en la tercera etapa, con matriz de transición
⎛ ⎞
1 1 1
T =⎝ 0 0 1 ⎠
3 3 3
1 0 0
30
⎛ 4 1 4
⎞
9 9 9
T 2=⎝ 1 0 0 ⎠
1 1 1
3 3 3
y
⎛ 16 4 7
27 27 27
T3 = ⎝ 1
3
1
3
1
3
⎠
4 1 4
9 9 9
Así, T 3
es una matriz positiva, lo que significa que la cadena es regular.
Una propiedad muy importante de las cadenas irreducibles es que todos sus estados
son del mismo tipo, esto es, o bien todos son transitorios o bien todos son recurrentes
(nulos o no nulos) y todos tienen el mismo periodo. Esto significa que la clasificación de
todos los estados de una cadena se puede deducir a partir de la clasificación conocida de
uno de los estados.
También es obvio que todos los estados de una cadena finita irreducible no pueden ser
transitorios, ya que eso significaría que el regreso a alguno de los estados no sería seguro,
aunque todos los estados fueran accesibles desde cualquiera de ellos en un número finito
de pasos.
Conjuntos cerrados
Una cadena de Markov puede contener algunos estados que sean recurrentes, otros que
sean transitorios y otros que sean absorbentes. Los estados recurrentes pueden ser parte
de subcadenas cerradas.
fuera de C puede ser alcanzado desde cualquier estado dentro de C. Así una condición
necesaria para que esto ocurra es que
Los estados absorbentes son cerrados con sólo un elemento. Se puede ver que un
31
subconjunto cerrado es él mismo una subcadena irreducible de una cadena de Markov
completa.
Ejemplo.
E1 E2
1/2
1/4
1/ 4
1/ 2
1/4
E6 E3
1/4
1/4
1/2
1/4
1/2 1/4
E5 E4
1/2 1/4
⎜ 204 0 0 0
⎝
1
4 4 4
1
2
1
1
2 2
Observando
cerrada el diagrama
e irreducible se tiene
ya que ningún quefuera
estado de E 1 y {E
el conjunto 2} forman
, Epuede
E21se unadesde
alcanzar subcadena
ellos.
De modo similar {E5, E6} forman una subcadena cerrada e irreducible. Los estados E3 y
32
E4 son transitorios. Todos los estados son aperiódicos, lo que significa que E1, E2, E5 y
E6 son ergódicos.
Cadenas ergódicas
Se tenía que todos los estados en una cadena irreducible pertenecen a la misma clase.
Si todos los estados son ergódicos, esto es, recurrentes, no nulos y aperiódicos entonces se
Ejemplo.
λ1 = 1 λ2 = − 25 + 4
5i λ3 = − 25− 45 i
y la matriz de autovectores es
⎛ ⎞
1 − 12
25 + 25 i − 25 − 25 i
16 12 16
C=⎝ 1 −5 2 −54 i −5 2 + 54 i ⎠
1 1 1
y su inversa es
⎛ ⎞
5 4 4
13 13
9 − 1 i
13
⎠
C −1 = ⎝ − 26 − 104 i −132 + 104 i
5 35 37
26 52
− 26 + 104 i − 13 − 104
5 35 2 37 i 9 + 1 i
26 52
33
entonces como
p(n) = p(0)T n,
la distribución límite es
¢
13 13 13
¡ 5 4 4
= 13 13 13 .
E1
4/5 1
1
E2 E3
La probabilidad de primer retorno para cada uno de los estados fi (n) se puede calcular
observando el diagrama de estados previo.
34
Así,
(1)
1
f1 =
5
(2)
f1 =0
4 4
f (3)
1 = 5 · 1 · 1=5
(n)
f1 = 0, n≥4
(1)
f2 = f (1)
3 = 0
(2)
f2 = f (2)
3 = 0
µ ¶n−3 µ ¶
1 4 4 1 n−3
f(n)
2 = f(n)3 = 1 · 1 · 5 ·5=5 5 , n ≥ 3.
X
∞
1 4 13
µ1 = nf 1(n) = +3 = .
n=1
5 5 5
µ ¶n−3
X
∞
4X
∞
1 (∗) 4 65 13
µ=µ = nf2(n)
2 3
=
5 n 5 = ·
5 16
=
4
n=1 n=1
35
Representación Canónica de una matriz de transición
puede ser ∅): uno está formado por los estados transitorios y el otro por los recurrentes,
de modo que los estados transitorios son inaccesibles desde los estados recurrentes.
Los estados recurrentes se pueden subdividir de manera única en conjuntos cerrados
e irreducibles. Dentro de cada conjunto cerrado todos los estados se comunican y son del
mismo tipo (recurrentes positivos o recurrentes nulos) y con el mismo periodo en su caso.
Si dos estados están en distintos conjuntos cerrados, no se pueden comunicar. Además,
fij = fji = 1
fij = fji = 0.
De acuerdo con este resultado se puede hacer una reordenación de los estados, y así
de las filas y columnas de la matriz de transición, colocando los estados transitorios en
último lugar.
P1 0 ··· 0 ··· 0
⎜ 0 P 2 ··· 0 ··· 0 ⎟
P = ⎜ · · · · · · · ·· · · · · ·· · · · ⎟
⎝ 0 0 · · · Pr ············· 0 ⎠
Q1 Q2 · · · Qr·············Q
donde las submatrices Pi (i = 1 , . . . , r) están asociadas a subcadenas recurrentes cerra-
das, Qi (i = 1 , . . . , r) dan la probabilidad de pasar a los estados recurrentes desde los
transitorios y Q da la probabilidad de pasar de transitorios a transitorios.
36
Cadenas Infinitas
j en el proceso.
Distribución de Nj
(ii)
½ m1
jj − (1 − f ) si m = 1,
P (Nj = m | X0 = j) = f
si m = 0
2, 30. . .j j
dado que se parte ya de una visita al estado j.
37
Número medio de visitas la estado j
1
Rjj =
1 − fjj
al número medio de visitas a j partiendo de j.
Proposición
Se cumple que
X
∞
(n)
Rij = Tij
n=0
Demostración
de este modo,
∞
X n
Nj = Nj
n=0
38
entonces
£ ¤
E Nj n | X0 = i = 1 · P (Xn = j | X0 = i) = T
ij
(n)
con lo que
"∞ #
X
E [N j | X 0 = i] = E N jn | X 0 = i =
n=0
X
∞
£ ¤ X∞
= E N jn | X 0 = i = Tij(n).
n=0 n=0
X
∞
R = I +T + T +··· = 2 Tn.
n=0
(i) Si i y j son ambos recurrentes entonces fij = 1 cuando ambos pertenecen al mismo
conjunto cerrado, ó fij = 0 cuando pertenecen a conjuntos cerrados diferentes.
Rij
fij =
Rjj
1
fjj = 1−
R jj
Cálculo de Rij
39
P∞
como R = I + P + P 2 + · · · = n=0 P n , entonces
µ ¶
n Kn 0
P =
Ln Qn
donde Ln 6
= Ln , entonces
µ P∞ ¶
X
∞ K n
0
R= Pn = P∞
n=0 P∞
n=0 Ln
n
n=0 Q
n=0
es la matriz que proporciona el número medio de visitas a cada estado desde otro estado.
X
∞
S = Qn =
n=0
= (I − Q)−1.
Sij
fij =
Sjj
1
fjj = 1−
Sjj
ya que
40
Definición
P1 0 ··· 0 ··· 0
⎜ 0 P 2 ··· 0 ··· 0 ⎟
P = ⎜ · · · · · · · ·· · · · · ·· · · · ⎟
⎝ 0 0 · · · Pr ············· 0 ⎠
Q1 Q2 · · · Qr·············Q
⎛ ⎞ ⎛ ⎞
1 0 ··· 0 ··· 0
⎜ 1 · · · 0
1 ··· 0 ··· 0 ⎟
¯ ⎜ 0 ⎟ ⎜ . ... . 0 ⎟
P = ⎜ ··· ··· ··· ··· ··· ··· ⎟ = ⎜ ⎟
⎝ 0 ⎠ ⎝ 0 ··· 1 ⎠
0 ··· 1 ··· 0
B Q
b1 b2 · · · br · · · Q
de modo que se considera cada conjunto cerrado irreducible como un único estado ab-
sorbente y las matrices Qi pasan a ser vectores columna bi que dan las probabilidades de
∀i ∈ E transitorio.
Así se suman las probabilidades de transición en una etapa, del estado transitorio i a
todos los estados recurrentes que están contenidos en el conjunto cerrado correspondiente
Cj.
41
Proposición
G = (I − Q)−1B = S · B
recoge las probabilidades de absorción de los estados transitorios por los conjuntos cerra-
dos e irreducibles.
Definición
Este número de etapas es la suma de las visitas que se hacen a todos los estados
transitorios, es decir
X
Ai = Rij
j∈D
donde D es el conjunto de los estados transitorios.
j los elementos Sij cuando j ∈ D. Así, Ai se calcula sumando los elementos de la fila i−
ésima de la matriz fundamental S.
Se puede generalizar esta idea, y plantearse calcular el número medio de etapas que
hay que recorrer antes de visitar un estado transitorio j por primera vez. En este caso
42
6 j, es decir si se impone la visita a j por
bastará con sumar sólo aquellos Rik donde k =
primera vez, el número medio de etapas será
X
Rik
k6
=j
donde k ∈ D.
Cadenas periódicas
Si un estado j es periódico con periodo δ y otro estado i comunica con él, entonces
el estado i también es periódico con el mismo periodo. De este modo, el periodo es una
característica común del conjunto irreducible y cerrado y se puede hablar del periodo de
una subcadena irreducible.
Proposición
Ejemplo. En una carrera que dura 3 años, una persona tiene cada año una probabilidad
p de pasar al siguiente curso, una probabilidad q de repetir curso y una probabilidad
43
q
1
p
1-p-q
q
2 1-p-q
A 1
p 1-p-q
T 1
3
p
q
1
⎛ q p 0 1− p− q 0 ⎞
2 ⎜ 0 q p 1− p− q 0 ⎟
T = ⎜ 0 0 q 1− p− q p ⎟
⎜ ⎟
3
A ⎝ 0 0 0 1 0⎠
T 0 0 0 0 1
donde los estados absorbentes son {A, T } y los estados transitorios son {1, 2, 3} . Se re-
ordena la matriz y se obtiene la matriz en forma canónica, poniendo primero los estados
recurrentes y luego los transitorios:
A
⎛ 1 0 0 0 0 ⎞
T ⎜ 0 1 0 0 0 ⎟
P= 1 −p − q 0 q p 0
1
⎜ ⎟
2 ⎝ 1−p−q 0 0 q p ⎠
3 1−p−q p 0 0 q
Se puede preguntar alguien por cosas como: cuál es la probabilidad de acabar los
estudios? ¿cuál es el número medio de años que pasa una persona estudiando en el centro?
Así, nos planteamos:
(i) ¿cuál es el número medio de años que pasa una persona estudiando en el primer curso?
44
En este caso, ⎛
⎞
q p 0
Q=⎝ 0 q p ⎠
0 0 q
luego ⎛ ⎞
(1 − q)2 p(1 − q) p2
1
S = (I − Q)−1 = ⎝ 0 (1 − q)2 p(1 − q) ⎠
(1 − q)3 0 0 (1 − q)2
Se pide calcular R11.
Como el estado 1 es transitorio
(1 − q)2 1
R11 = S11 = = .
(1 − q)3 1−q
Así, si suponemos que la probabilidad de pasar de curso es p = 0,4, la de repetir curso
1 1
R11 = = = 4 años.
1−q 1 − 0,75
S13
f13 =
S33
Si p = 0,4, y q = 0,55
p2 0,16
f13 = = = 0,7901
(1 − q) 2 0,2025
45
Si se toma p = 0,2, y q = 0,75 esta probabilidad disminuye
p2 0,04
f13 = = = 0,64
(1 − q) 2 0,0625
Se pide (1 − f12).
Como
p(1−q)
S (1−q) 3
p
f12 = 12 = (1−q) 2
= ,
S22
(1−q) 3
1−q
luego
p
(1 − f12) = 1 −
1−q
En el caso de tomar p = 0,2, y q = 0,75
0,05
(1 − f12) = = 0,111.
0,45
Los estados {A, T } son recurrentes, de modo que se busca f1T donde 1 es un estado
transitorio y T es recurrente. Como T es absorbente (sólo él forma un conjunto cerrado
46
p3
Por lo tanto, la probabilidad de acabar la carrera (pasar de 1 a T ) es .
(1−q) 3
Se trata de calcular, en realidad, el número medio de etapas que se pasa en los estados
transitorios, cuando se parte del estado transitorio 1. Esto es equivalente a calcular el
Se tiene que calcular el número medio de etapas que se tienen que hacer desde primero
antes de llegar a tercero.
(1 − q)2 p(1 − q)
τ 13 = R11 + R12 = +
(1 − q)3 (1 − q)3
Si p = 0,4, y q = 0,55,
0,2025 + 0,4 · 0,45
τ 13 = = 4,1975 años.
0,091125
47
Distribuciones estacionarias
π = πT
Teorema
para todo i, j = 1 ,. .. , m.
Observaciones.
— Este teorema asegura que si una cadena es finita, irreducible y aperiódica (así es ergódica)
existe una única distribución estacionaria que se obtiene resolviendo el correspondiente
sistema de ecuaciones.
48
— El hecho de que para todo i = 1 , . . . , m resulta que πj = l´ımn→∞ Tij(n) implica que
Proposición
Observaciones.
— Esto indica que cuanto mayor es el tiempo medio de recurrencia del estado j, menor es
la probabilidad de que nos encontremos en ese estado j, cuando pase un tiempo suficien-
temente grande.
En general, dada una matriz en forma canónica P se puede estudiar qué valores tomaría
P ∞ = l´ım Pn
n→∞
49
donde P es la matriz de transición de una cadena de Markov finita, no necesariamente
irreducible y aperiódica.
⎜ ...
P =⎜ 0
⎟
⎝ Pr ⎠
L Q
Casos:
(ii) ) En los estados transitorios las distribuciones límite asignan probabilidad 0, luego
(n)
l´ım P
ij
=0
n→∞
∀j transitorio.
donde
∞
X (k)
fij = f ij .
k=0
Ejemplo.
Un grupo de personas elige un lugar de viaje de fin de fin curso entre Bahamas, Europa
o Hawai utilizando las siguientes reglas:
3 1
πB = πE + πH
8 2
2 1 1
πE = πB +
πE + πH
3 8 2
1 1
π =
H πB + πE
3 2
πB + πE + π H = 1
dado que las tres primeras ecuaciones son linealmente dependientes. Se obtiene
πB = 0,3
πE = 0,4
πH = 0,3
Se puede interpretar que después de un largo periodo de tiempo se prefiere Europa con
probabilidad 0,4, y después Bahamas y Hawai con probabilidad 0,3.
51