Upload
vuthien
View
221
Download
0
Embed Size (px)
Citation preview
1/ 1
Una invitacion al estudio de las cadenas de Markov
Una invitacion al estudio de las cadenas deMarkov
Vıctor RIVERO
Centro de Investigacion en Matematicas A. C.
Taller de solucion de problemas de probabilidad, 21-25 de Enero de2008.
2/ 1
Una invitacion al estudio de las cadenas de Markov
Potencias de una matriz mediante diagonalizacion
Si Xn ,n ≥ 0 es una cadena de Markov (π,P) con espacio de estadosfinitos y P es diagonalizable, es decir existen una matriz diagonal D yuna matriz C con inversa tal que
D = C−1 PC ,
entoncesPn = CD(n)C−1, ∀n ≥ 0.
Ver ejercicio 1 para un ejemplo de este metodo.
3/ 1
Una invitacion al estudio de las cadenas de Markov
Clasificacion de los estados
Clasificacion de los estados
DefinicionSea (Ω,F ,P) un espacio de probabilidad y Xn ,n ∈ N una cadena deMarkov (π,P) definida sobre Ω y con espacio de estado E . Parax , y ∈ E , se dice que:
(i) de x se accede a y si existe un n ≥ 0 tal que P(n)x ,y > 0 y esto se
denota por x → y .(ii) x y y se comunican entre si x → y y y → x , esto se denota por
x ↔ y .
4/ 1
Una invitacion al estudio de las cadenas de Markov
Clasificacion de los estados
Ejemplo
Sea Xn ,n ∈ N una cadena de Markov con espacio de estadosE = 1, 2, . . . , 6 y matriz de transicion
P =
1/2 1/2 0 0 0 00 0 1 0 0 0
1/3 0 0 1/3 1/3 00 0 0 1/2 1/2 00 0 0 0 0 10 0 0 0 1 0
Determinar cuales estados se comunican entre si.
Es claro que 1↔ 2, 2↔ 3, 1, 2, 3→ 4, 3→ 5, 4→ 5, 5↔ 6.
5/ 1
Una invitacion al estudio de las cadenas de Markov
Clasificacion de los estados
Hay otras definiciones equivalentes.
TeoremaPara cualesquiera x , y ∈ E , se tiene que las siguientes afirmaciones sonequivalentes:
(i) x → y .(ii) Px ,x1 Px1,x2 ·Pxn−2,xn−1 Pxn−1,y > 0, para algunos
x1, . . . , xn−1 ∈ E ; o dicho de otro modo, con probabilidad positivaexiste una trayectoria que lleva de x a y .
(iii) P(Xn = y para algun n ≥ 1|X0 = x ) > 0.
6/ 1
Una invitacion al estudio de las cadenas de Markov
Clasificacion de los estados
Encontrar los estados que se comunican entre si para la cadena deMarkov con matriz de transicion
P =
1/2 0 1/8 1/4 1/8 0 00 0 1 0 0 0 00 0 0 1 0 0 00 1 0 0 0 0 00 0 0 0 1/2 0 1/20 0 0 0 1/2 1/2 00 0 0 0 0 1/2 1/2
.
Se ve que 1→ 2→ 3→ 1 y por lo tanto 1↔ 2↔ 3↔ 1; 0→ 0, 0→ 2,0→ 3, 0→ 4, 4↔ 5↔ 6
7/ 1
Una invitacion al estudio de las cadenas de Markov
Clasificacion de los estados
Proposicion
↔ es una relacion de equivalencia y da lugar a una particion del espaciode estados E en clases de equivalencia.
Definicion
• Diremos que un subconjunto C ⊆ E es una clase de comunicacion sicualesquiera dos estados x , y ∈ C se comunican entre si. Para todox ∈ E la clase de comunicacion de x se denota por C (x ) y estaformada por
C (x ) = y ∈ E : x ↔ y.
• Se dice que un conjunto de estados de B ⊆ E es cerrado si ningunestado de E \ B puede ser accedido desde un estado de C .
• Un estado x es absorbente si el conjunto x es cerrado, o
equivalentemente P(1)x ,x = 1.
• Diremos que una cadena es irreducible si E es la unica clase decomunicacion.
8/ 1
Una invitacion al estudio de las cadenas de Markov
Clasificacion de los estados
Ejemplo
Sea Xn ,n ∈ N una cadena de Markov con espacio de estadosE = 1, 2, . . . , 6 y matriz de transicion
P =
1/2 1/2 0 0 0 00 0 1 0 0 0
1/3 0 0 1/3 1/3 00 0 0 1/2 1/2 00 0 0 0 0 10 0 0 0 1 0
Determinar cuales estados se comunican entre si.
Es claro que 1↔ 2, 2↔ 3, 1, 2, 3→ 4, 3→ 5, 4→ 5, 5↔ 6. Se tieneque los estados de la cadena se pueden agrupar en las clases decomunicacion 1, 2, 3, 4, 5, 6 que estan compuestas por los estadosque se comunican entre si. Observemos que una vez que llegamos alestado 5 o 6 ya no podemos salir de dichos estados, es decir la clase deestados 5, 6 es cerrada.
9/ 1
Una invitacion al estudio de las cadenas de Markov
Clasificacion de los estados
La cadena de Markov con matriz de transicion
P =
1 0 00 2/3 1/30 1/2 1/2
Tiene dos clases de comunicacion 1 y 2, 3, y ambas son cerradas.Sin embargo la cadena con matriz de transicion
P ′ =
1/3 1/3 1/30 2/3 1/30 1/2 1/2
tiene las mismas clases de comunicacion: 1 y 2, 3, pero solo lasegunda de estas es cerrada.
10/ 1
Una invitacion al estudio de las cadenas de Markov
Clasificacion de los estados
Definicion
Diremos que un estado x ∈ E es recurrente si
P(Xn = x para algun n ≥ 1|X0 = x ) = 1.
Diremos que un estado x ∈ E es transitorio si
P(Xn = x para algun n ≥ 1|X0 = x ) < 1.
11/ 1
Una invitacion al estudio de las cadenas de Markov
Clasificacion de los estados
ρx = P(regresar a x en un tiempo finito|X0 = x ) =
< 1 si x transitorio
= 1 si x recurrente.
Proposicion
Si x es recurrente
P(Xn = x para una infinidad de n’s |X0 = x ) = 1
Si x es transitorio
P(Xn = x para una infinidad de n’s |X0 = x ) = 0.
Sea Nx la variable aleatoria que cuenta el numero total de visitas alestado x . Se tiene que Nx sigue una ley geometrica, es decir que
P(Nx = k |X0 = x ) = (ρx )k−1 (1− ρx ), k ≥ 1.
12/ 1
Una invitacion al estudio de las cadenas de Markov
Clasificacion de los estados
En el caso en que X = Xn ,n ≥ 0 es una cadena de Markov comMatriz de transicion
P =
1/2 0 1/8 1/4 1/8 0 00 0 1 0 0 0 00 0 0 1 0 0 00 1 0 0 0 0 00 0 0 0 1/2 0 1/20 0 0 0 1/2 1/2 00 0 0 0 0 1/2 1/2
,
se tienen las clases de comunicacion 0 1, 2, 3 y 4, 5, 6 Las dosultimas son cerradas y todos sus estados son recurrentes y la primera noes cerrada y sus estados son transitorios.
13/ 1
Una invitacion al estudio de las cadenas de Markov
Clasificacion de los estados
Proposicion
Si E es finito toda cadena irreducible tiene todos sus estadosrecurrentes.
Toda clase de comunicacion irreducible y cerrada esta formada porestados recurrentes.
Toda clase de comunicacion irreducible no cerrada es transitoria.
Todos los estados de una misma clase de comunicacion son delmismo tipo, es decir si alguno es recurrente entonces todos sonrecurrentes y si alguno es transitorio todos son transitorios.
14/ 1
Una invitacion al estudio de las cadenas de Markov
Clasificacion de los estados
Proposicion
Si∑∞
n=0 P(n)x ,x =∞ entonces x es recurrente.
Si∑∞
n=0 P(n)x ,x <∞ entonces x es transitorio.
Observacion: Sea Tx el primer tiempo ≥ 1 de regreso a x . Se tiene que
Tx <∞ = Xn = x para algun n ≥ 1,
y por lo tanto x es recurrente si
P(Tx <∞|X0 = x ) = 1
y x es transitorio siP(Tx <∞|X0 = x ) < 1.
Si x es transitorio se tiene que
limn→∞
P(n)x ,x = 0.
15/ 1
Una invitacion al estudio de las cadenas de Markov
Caminatas aleatorias
Caminatas aleatoriasS0 ∈ Z, Yi , i ∈ 1, 2, . . ., v.a.i.i.d. y con ley Binomial(p).
Sn = S0 +n∑
i=1
Yi , n ≥ 1.
LemaSe tiene que para todo a, b enteros y n ≥ 0
P(Sn = j |S0 = a)
=
(n
(n+b−a)/2
)p(n+b−a)/2q(n−b+a)/2 si (n + b − a)/2 ∈ Z
0 en otro caso.
Una trayectoria que lleva de (0, a) a (0, b) en n pasos tiene r pasos paraarriba (+1) y l pasos hacia abajo (−1), estos son tales que r + l = n yr − l = b − a. (Pues Sn = r(+1) + l(−1) = b − a.) Lo que implica quer = (n + b − a)/2 y l = (n − b + a)/2, cada trayectoria que lleva de a ab en n pasos tiene probabilidad prq l , y hay
(n
(n+b−a)/2
)trayectorias
posibles.
16/ 1
Una invitacion al estudio de las cadenas de Markov
Caminatas aleatorias
∑n≥0
P(Sn = 0|S0 = 0) =∞∑
n=0
P(n)0,0 =
∑k≥0
(2kk
)pkqk .
Se tiene que pq ≤ 1/4 con la igualdad si y solamente si p = q = 1/2. Porla identidad de Stirling n! ∼ nn+1/2en
√2π, se tiene que para k
suficientemente grande(2kk
)∼ (2k)2k+1/2e−2k
√2π(kk+1/2e−k
)2 ∼ (√
2π)−122k+1/2k−1/2.
Se sigue que el termino general de la serie esta dado por la aproximacion(2kk
)∼ (√π)−14kk−1/2(pq)k , para k suficientemente grande.
Si p = q = 1/2 es del orden de k−1/2 por lo que en este caso la serie noes convergente. En el caso en que p 6= q se tiene que a = 4pq < 1 lo queimplica que el termino general de la serie es del orden de k−1/2ak ≤ ak ,y por lo tanto la serie es convergente.
17/ 1
Una invitacion al estudio de las cadenas de Markov
Caminatas aleatorias
Sea Tj = infn ≥ 0 : Sn = j, para j ∈ Z .
Lema (Problema de la ruina)
Sea hj la probabilidad de que una caminata aleatoria que parte del estadoj llegue al nivel 0 antes de llegar al nivel N , es decirP(T0 < TN |S0 = j ) = hj . Se tiene que
hj =
( q
p )j−( qp )N
1−( qp )N p 6= q ,
1− jN p = q = 1/2
18/ 1
Una invitacion al estudio de las cadenas de Markov
Caminatas aleatorias
Se obtiene condicionando con respecto al estado visitado al primer pasoque
hj = phj+1 + qhj−1,
si j ∈ 2, . . . ,N − 1 y h0 = 1 y hN = 0. Re-escribiendo esta ecuacion setiene que
hn = phn+1+qhn−1 ⇐⇒ q (hn − hn−1) = p (hn+1 − hn) n ≥ 1.
En el caso en que q = p tenemos que la funcion hn tiene una pendienteconstante c = hn+1 − hn y por lo tanto
hn = 1 +n∑
j=1
hj − hj−1 = 1 + nc, 1 ≤ n ≤ N ,
y puesto que hN = 0 se puede concluir que c = −1/N .
19/ 1
Una invitacion al estudio de las cadenas de Markov
Caminatas aleatorias
Cuando q 6= p, tomamos xn ,n ∈ N definida por x0 ∈ R, yxn = hn − hn−1, 1 ≤ n ≤ N . De lo anterior se deduce que la sucesionxn , 1 ≤ n ≤ N satisface xn+1 = q
p xn , 1 ≤ n ≤ N , es decir que
xn =(
qp
)n
x0, 0 ≤ n ≤ N .
Usando esto se tiene que la sucesion hn esta dada por
hn = h0 +n∑
j=1
(hj − hj−1)
= h0 + x0
n∑j=1
(qp
)j
= h0 + x0
(qp
) 1−(
qp
)n
1−(
qp
) .
20/ 1
Una invitacion al estudio de las cadenas de Markov
Caminatas aleatorias
Sabemos que hN = 0 y que h0 = 1, y en consecuencia x0 es igual a
x0 = −p(
1− qp
)q(
1−(
qp
)N) ,
de donde que
hn = 1−p(
1− qp
)q(
1−(
qp
)N) (q
p
) 1−(
qp
)n
1−(
qp
) =
(qp
)n
−(
qp
)N
1−(
qp
)N.
21/ 1
Una invitacion al estudio de las cadenas de Markov
Cadenas de nacimiento y muerte
Cadenas de nacimiento y muerte
Sean E = 0, 1, 2, . . . ,N con N ≤ ∞, y Xn ,n ≥ 0 una cadena deMarkov con espacio de estados E y matriz de transicion
Px ,y =
qx si y = x − 1rx si y = xpx si y = x + 10 en otro caso,
con 0 ≤ px , rx , qx ≤ 1 y qx + rx + px = 1 para todo x ∈ E y q0 = 0 ypN = 0 si N <∞. Diremos que una cadena de Markov con espacio deestados y matriz de transicion de esta forma pertenece a la clase deCadenas de Nacimiento y Muerte.Ejemplos: Ehrenfest, la ruina del jugador, la caminata aleatoria conbarreras reflejantes...
22/ 1
Una invitacion al estudio de las cadenas de Markov
Cadenas de nacimiento y muerte
Proposicion
Sea Hx el primer tiempo de llegada al estado x
Hx = infn ≥ 0 : Xn = x, x ∈ E .
Supongamos que px > 0 y qx > 0 para todo x ∈ 1, 2, . . . ,N − 1 y quep0 > 0 y qN > 0 si N <∞. Se tiene que la cadena es irreducible y paratodo a < b, a, b ∈ E
Pz (Ha < Hb) =
b−1∑y=z
γy
b−1∑y=a
γy
, Pz (Hb < Ha) =
z−1∑y=a
γy
b−1∑y=a
γy
, para todo a < z < b,
con
γy =y∏
j=1
(qjpj
), y > 0, y γ0 = 1.
23/ 1
Una invitacion al estudio de las cadenas de Markov
Ley fuerte
Sea N yn el numero de visitas al estado y en n pasos.
Teorema (Ley fuerte)
Para y ∈ E estado transitorio N yn <∞ con probabilidad 1.
Para y ∈ E estado recurrente,
limn→∞
1n
N yn =
1Ty<∞
E(Ty |X0 = y), con probabilidad 1.
y
limn→∞
1n
E (N yn |X0 = x ) =
P(Ty <∞|X0 = x )E(Ty |X0 = y)
, ∀x ∈ E .
Si E es finito e irreducible entonces el vector
π(y) =1
E(Ty |X0 = y), x ∈ E ,
es el unico vector de probabilidad invariante.
24/ 1
Una invitacion al estudio de las cadenas de Markov
Ley fuerte
El sistema Bonus-Malus en el seguro de automoviles
En Hong Kong y en otros lugares del mundo, se usa un sistema para fijarlas primas de seguro de automovil conocido como Bonus-Malus queconsiste de 6 clases de tarificacion, de 1 fort bonus a 6 fort malus, que serige por las siguientes reglas:
si un asegurado no tuvo siniestros durante el periodo, entonces pasade la categorıa i a la categorıa max1, i − 1,si el asegurado tiene al menos un siniestro entonces pasa de lacategorıa i a la 6.
Si Xn denota la categorıa en cual se encuentra un individuo al n-esimoperiodo entonces Xn ,n ≥ 0 es una cadena de Markov con espacio deestados 1, 2, . . . , 6
25/ 1
Una invitacion al estudio de las cadenas de Markov
Ley fuerte
La matriz de transicion asociada esta dada por
P =
p 0 0 0 0 1− pp 0 0 0 0 1− p0 p 0 0 0 1− p0 0 p 0 0 1− p0 0 0 p 0 1− p0 0 0 0 p 1− p
.
Si p ∈ (0, 1) el unico vector π = (π(1), π(2), . . . , π(6)) que es invariantepara la matriz P, es decir πP = π, y que satisface queπ(1) + π(2) + · · ·+ π(6) = 1, es el vector dado por
π(1) = p5, π(2) = p4(1− p), π(3) = p3(1− p),
π(4) = p2(1− p), π(5) = p(1− p), π(6) = (1− p).
26/ 1
Una invitacion al estudio de las cadenas de Markov
Ley fuerte
¿Cual es la proporcion de tiempo que un cliente pasa en el estadoj despues de n pasos, n−1N j
n , dado que X0 = j? Dado que la cadenaes irreducible y con espacio de estados finito
1n
N jn ∼ π(j ) =
1E(Tj |X0 = j )
,
con probabilidad 1.¿Cual es la prima promedio que paga un asegurado? Denotemos porc una funcion que determina la prima a pagar en funcion de la categorıa.c es una funcion definida en 1, 2, . . . , 6 no-decreciente que toma solovalores positivos. La prima promedio que pagara un individuo en nperiodos sera entonces:
1n
n∑j=1
c(Xj ),=6∑
j=1
c(j )N (n)
j
n∼
6∑j=1
π(j )c(j ),
con probabilidad 1.
27/ 1
Una invitacion al estudio de las cadenas de Markov
leyes invariantes
DefinicionDiremos que un vector de probabilidad π = (π(x ), x ∈ E ), es unadistribucion o ley invariante para la cadena con matriz de transicion P sila ecuacion πP = π es satisfecha, la ecuacion anterior es la notacionmatricial del sistema de ecuaciones∑
y∈E
π(y)Py,x = π(x ), ∀x ∈ E .
28/ 1
Una invitacion al estudio de las cadenas de Markov
leyes invariantes
Teorema (Estacionaria)
Sea X = Xn ,n ≥ 0 una cadena de Markov con caracterısticas (λ,P) ysupongamos que λ es invariante para P . Entonces se tiene que
• Para todo m ∈ N se tiene λP (m) = λ, es decir que
P(Xm = y) = λ(y), ∀y ∈ E ;
• La cadena de Markov X es estacionaria, es decir que para todom,n ∈ N se cumple que el vector (Xm+1, . . . ,Xm+n) tiene lamisma ley que (X1, . . . ,Xn) , esto es
P (Xm+1 = x1, . . . ,Xm+n = xn) = P (X1 = x1, . . . ,Xn = xn) ,
para todo x1, . . . , xn ∈ E .
29/ 1
Una invitacion al estudio de las cadenas de Markov
leyes invariantes
Teorema (Equilibro)
Sea X = Xn ,n ≥ 0 una cadena de Markov con espacio de estadosfinito y matriz de transicion P . Supongamos que para algun x ∈ E secumple que
limn→∞
P (n)x ,y := π(y), ∀y ∈ E ,
Entonces, el vector (π(y), y ∈ E ) es un vector de probabilidad invariante.
30/ 1
Una invitacion al estudio de las cadenas de Markov
leyes invariantes
Es inmediato que 0 ≤ π(y) ≤ 1, para todo y ∈ E pues esto se vale para
las potencia de la matriz de transicion P , 0 ≤ P (n)x ,y ≤ 1, para todo n ≥ 1
y x , y ∈ E . Es un vector de probabilidad:∑y∈E
π(y) =∑y∈E
limn→∞
P (n)x ,y = lim
n→∞
∑y∈E
P (n)x ,y = 1.
Es invariante: por las ecuaciones de Chapman-Kolmogorov tenemos quepara todo y ∈ E .
π(y) = limn→∞
P (n+1)x ,y = lim
n→∞
∑z∈E
P (n)x ,z Pz ,y
=∑z∈E
limn→∞
P (n)x ,z Pz ,y =
∑z∈E
π(z )Pz ,y
31/ 1
Una invitacion al estudio de las cadenas de Markov
leyes invariantes
Sea X = Xn ,n ≥ 0 una cadena de Markov con matriz de transicion
P =
0 1 00 1/2 1/2
1/2 0 1/2
.
Encontrar una ley invariante para X . Debemos resolver el sistema
(π1, π2, π3)P =
0 1 00 1/2 1/2
1/2 0 1/2
=
π1
π2
π3
,
32/ 1
Una invitacion al estudio de las cadenas de Markov
leyes invariantes
Equivalentemente, resolver el sistemas de ecuaciones
π1 =12π3, π1 +
12π2 = π2,
12π2 +
12π3 = π3.
Su solucion queda determinada en terminos de π3 pues
π1 =12π3, π2 = π3.
Para determinar el valor de π3 se utiliza la condicion,
π1 + π2 + π3 = 1.
Despues de algunos calculos elementales se llega a la solucion:π =
(15 ,
25 ,
25
).
33/ 1
Una invitacion al estudio de las cadenas de Markov
leyes invariantes
La n-esima potencia de la matriz de transicion esta dada por
P(n)1,1 =
15
+(
12
)n (45
cos(nπ
2
)− 2
5sin(nπ
2
)).
Por lo tanto,
limn→∞
P(n)1,1 =
15
= π(1).
34/ 1
Una invitacion al estudio de las cadenas de Markov
leyes invariantes
TeoremaEn el caso en que el espacio de estados E es finito siempre existe una leyinvariante
35/ 1
Una invitacion al estudio de las cadenas de Markov
leyes invariantes
TeoremaSea P una matriz estocastica asociada a una cadena de MarkovXn ,n ∈ N con espacio de estados E finito y supongamos que existe un
entero n tal que P(n) tiene todas sus entradas estrictamente positivas.Se tienen las siguientes propiedades.
• Cuando n tiende a infinito, P(n) converge entrada por entrada a unamatriz Π tal que todos sus renglones son iguales a un mismo vectorde probabilidad π cuyas entradas son estrictamente positivas.
• El vector π es el unico vector de probabilidad invariante para P, esoes πP = π; cualquier otro vector v tal que v P = v es un multiplode π;
• Se tienen las siguientes convergencias:
limn→∞
P(Xn = x ) = π(x ), x ∈ E ,
ylim
n→∞Py(Xn = x ) = π(x ), x , y ∈ E ,
con π(x ) la componente x del vector π.