Capítulo 10 Cadenas de Markov

1 Cap tulo 10 Cadenas de MarkovPROCESOS ESTOC STICOSUna sucesi n de observacionesX1,X2,..se denominaproceso estoc s-tico Si los valores de estas observaciones no se pueden predecir exactamente Pero se pueden especificar las probabilidades para los distintos valoresposibles en cualquier instante de : que define elestado inicial del procesoXn: que define elestado del proceso en el instante de tiemponPara cada posible valor del estado inicials1y para cada uno de los sucesivosvaloressnde los estadosXn,n=2,3,.., especificamos:P(Xn+1=sn+1|X1=s1,X2=s2,.. ,Xn=sn)103104 Cadenas de MarkovCADENAS DE MARKOVUna cadena de Markov es un proceso estoc stico en el queSi el estado actualXnylosestadospreviosX1,..,Xn 1son conocidos La probabilidad del estado futuroXn+1 FNo depende de los estados anterioresX1,..,Xn 1,yFSolamente depende del estado decir, Paran=1,2.

2 Y Para cualquier sucesi n de estadoss1,..,sn+1P(Xn+1=sn+1|X1=s1,X2=s2 ,..,Xn=sn)==P(Xn+1=sn+1|Xn=sn) Cadenas de Markov105 EJEMPLOC onsideremos que en un locutorio telef nico con 5 l neas de tel fono enun instante de tiempo dado puede haber un n mero cualquiera de l neasocupadas. Durante un periodo de tiempo se observan las l neas telef nicasa intervalos de 2 minutos y se anota el n mero de l neas ocupadas en cadainstante. SeaX1la que representa el n mero de l neas ocupadas al principio delperiodo. SeaX2la que representa el n mero de l neas ocupadas cuando seobserva en el segundo instante de tiempo, 2 minutos m s tarde. En general,n=1,2,.. Xnes una que representa el n mero del neas ocupadas cuando se observan en el instante de tiempon simo. El estado del proceso en cualquier instante de tiempo es el n mero de l neasque est n siendo utilizadas en ese instante.

3 Un proceso estoc stico como el que acabamos de describir se llamaprocesode par metro discreto, ya que las l neas se observan en puntos que el proceso estoc stico del n merode l neas ocupadas sea una cadena de Markoves necesario que la probabilidad de cada posible n mero del neas ocupadas en cualquier instante de tiempodependa solamente del n mero del neas ocupadas 2 minutos de MarkovCADENAS DE Markov FINITASCON PROBABILIDADES DETRANSICI N ESTACIONARIASCADENA DE Markov FINITAEs una cadena de Markov para la que existe s lo un n merofinitokdeestados posibless1,..,sky en cualquier instante de tiempo la cadena est en uno de DE TRANSICI NEs la probabilidad condicionadaP(Xn+1=sj|Xn=si)PROBABILIDAD DE TRANSICI N ESTACIONARIAU nacadenadeMarkovtieneprobabilidades de transici n estaciona-riassi para cualquier par de estadossiysjexiste una probabilidad detransici npijtal queP(Xn+1=sj|Xn=si)=pijparan=1,2.

4 Cadenas de Markov107 MATRIZ DE TRANSICI NMATRIZ ESTOC STICAEs una matriz cuadrada cuyos elementos son no negativos y tal que lasuma de los elementos de cadafila es igual a DE TRANSICI N EN UN SOLO PASODada una cadena de Markov conkestados posibless1,..,sky probabili-dades de transici n (Xn+1=sj|Xn=si)= P= p11 p1kp21 pkk La matriz de transici nPde cualquier cadena de Markovfinita conprobabilidades de transici n estacionarias es una matriz estoc sticaEJEMPLOS upongamos que el clima de una determinada regi n s lo puede ser soleado(s1)o nublado (s2) y que las condiciones del clima en ma anas sucesivas formanuna cadena de Markov con probabilidades de transici n estacionarias. La matrizde transici n est dada por:P= Si un d a concreto est nublado, cu l es la probabilidad de que est nubladoel d a siguiente?p22= de MarkovMATRIZ DE TRANSICI N EN VARIOS PASOSDada una cadena de Markov conkposibles estadoss1.

5 ,skymatrizdetransici nPSi notamosp(2)ij=P(Xn+2=sj|Xn=si) p(2)ij:Elemento de lai simafila yj sima columna de la matrizP2 Pm:Potenciam sima deP,con(m=2,3,..)yFp(m)ij:Elemento de lafilaiy de la columnajde la matrizPmGENERALIZANDOPmes la matriz de probabilidadesp(m)ijde que la cadena pase del estadosial estadosjenmpasos; para cualquier valor dem,(m=2,3,..).Pmes la matriz de transici n dempasosdelacadenadeMarkovEJEMPLOEn el ejemplo del clima con matriz de transici nP= Si un mi rcoles est nublado, cu l es la probabilidad de que el viernessiguiente haga sol? Calculamos la matriz de transici n en dos pasos,P2= = Probabilidad pedida es de Markov109 VECTOR DE PROBABILIDADES INICIALESVECTOR DE PROBABILIDADESw=(w1,..,wk)se llamavector de probabilidadessiNwi 0parai=1,..,k,yNkXi=1wi= una cadena de Markov ,..,skposibles estados en los que la cadena puede estar en el tiempode observaci n inicialn=.

6 ,k;P(X1=si)=vi,convi 0yv1+..+vk=1 VECTOR DE PROBABILIDADES INICIALESEl vector de probabilidadesv=(v1,..,vk)se llamavector de proba-bilidades inicialesde la vector de probabilidades iniciales yla matriz de transici n determinan la probabilidadpara el estado de la cadena en el segundo instante de tiempo,dicha probabilidad viene dada por el vectorvP Adem s, si las probabilidades de los diversos estados en el instantenseespecifican por el vector de probabilidadesw, entoncesLas probabilidades en el instanten+1se especifican por el vector de probabilidadeswP110 Cadenas de MarkovEJEMPLOEn el ejemplo del clima con matriz de transici n:P= Suponemos que la probabilidad de que el mi rcoles haga sol es y laprobabilidad de que est nublado es de que est nublado el de que est nublado el de que est nublado el s rcoles:v=( , )= w=vP=( , )P[est nublado el jueves]= ( , )= vP2=vPP=wP=( , )P[est nublado el viernes]= ( , )= vP3=vP2P=( , )P[est nublado el s bado]= de Markov111 EJEMPLOS uponemos que en el ejemplo del locutorio telef nico los n meros de l neasque est n siendo utilizadas en los instantes de tiempo1,2.

7 Constituyenuna cadena de Markov con probabilidades de transici n estado en el que se est n utilizando exactamenteil neas en uninstante de tiempo determinado (i=0,1,..,5)Matriz de transici nPP= FSi las cinco l neas est n ocupadas en un instante de tiempo [Exactamente 4 l neas ocupadas en el siguiente instante de tiempo]==p65= en un instante de tiempo no hay ninguna l nea [Al menos una l nea ocupada en el siguiente instante de tiempo]==1 p11= de MarkovMatriz de transici n en dos pasosP2= FSi dos l neas est n ocupadas en un instante de tiempo [Cuatro l neas ocupadas dos instantes despu s]= en un instante de tiempo concreto hay tres l neas [Dos instantes despu s haya de nuevo tres l neas ocupadas]= FSi las 5 l neas est n ocupadas en un instante de tiempo [No haya l neas ocupadas tres instantes despu s]

8 = de Markov113 FSi una l nea est ocupada en un instante de [Tres instantes despu s haya de nuevo una l nea ocupada]= inicio del proceso de observaci n (instanten=1)P[No haya l neas ocupadas]= [Haya una l nea ocupada]= [Haya dos l neas ocupadas]= de probabilidades iniciales:v=( , , ,0,0,0) vP=( , , , , , )= P[No haya l neas ocupadas en el instante 2]= vP2=vPP=( , , , , , )= P[Haya 2 l neas ocupadas en el instante 3]= de MarkovSUPUESTO PR CTICO DECADENA DE Markov Consideremos el laberinto siguiente Supongamos que introducimos un rat n de forma aleatoria en una de lasceldas de dicho laberinto . Este rat n se traslada aleatoriamente de cada celda a una de las DE LA CADENA DE MARKOVYESTUDIO Definici n de las variables aleatoriasXn celda ocupada en el instantenCadenas de Markov115 EstadosLosposiblesestadosson:1,2,3,4,5y6 Comprobar que se trata de una cadena de Markov (comprobar la condici nde Markov )

9 Conocido el presente,el futuro no depende del pasado Se cumple la condici n de Markov Es una cadena de Markov Probabilidades de transici npij=P[Xn+1=j|Xn=i]Matriz de transici n p11p12p13p14p15p16p21p22p23p24p25p26p31p 32p33p34p35p36p41p42p43p44p45p46p51p52p5 3p54p55p56p61p62p63p64p65p66 116 Cadenas de MarkovDesde el estado 1p11=P[Xn+1=1|Xn=1]p12=P[Xn+1=2|Xn=1]p13 =P[Xn+1=3|Xn=1]=0p14=P[Xn+1=4|Xn=1]p15=P [Xn+1=5|Xn=1]=0p16=P[Xn+1=6|Xn=1]=0 Desde el estado 2p21=P[Xn+1=1|Xn=2]p22=P[Xn+1=2|Xn=2]p23 =P[Xn+1=3|Xn=2]=0p24=P[Xn+1=4|Xn=2]=0p25 =P[Xn+1=5|Xn=2]=0p26=P[Xn+1=6|Xn=2]=0 Cadenas de Markov117 Desde el estado 3p31=P[Xn+1=1|Xn=3]=0p32=P[Xn+1=2|Xn=3]= 0p33=P[Xn+1=3|Xn=3]p34=P[Xn+1=4|Xn=3]=0p 35=P[Xn+1=5|Xn=3]=0p36=P[Xn+1=6|Xn=3]Des de el estado 4p41=P[Xn+1=1|Xn=4]p42=P[Xn+1=2|Xn=4]=0p 43=P[Xn+1=3|Xn=4]=0p44=P[Xn+1=4|Xn=4]p45 =P[Xn+1=5|Xn=4]=0p46=P[Xn+1=6|Xn=4]=0118 Cadenas de MarkovDesde el estado 5p51=P[Xn+1=1|Xn=5]=0p52=P[Xn+1=2|Xn=5]= 0p53=P[Xn+1=3|Xn=5]=0p54=P[Xn+1=4|Xn=5]= 0p55=P[Xn+1=5|Xn=5]p56=P[Xn+1=6|Xn=5]Des de el estado 6p61=P[Xn+1=1|Xn=6]=0p62=P[Xn+1=2|Xn=6]= 0p63=P[Xn+1=3|Xn=6]p64=P[Xn+1=4|Xn=6]=0p 65=P[Xn+1=5|Xn=6]p66=P[Xn+1=6|Xn=6]Caden as de Markov119 Son estacionarias las probabilidades de transici n?

10 Pijno depende del instante en quese encuentre el proceso las probabilidades de transici n son estacionarias Matriz de transici nP= p11p120p1400p21p22000000p3300p36p4100p44 000000p55p5600p630p65p66 Matriz de transici n en dos pasosP2 Desde el estado 1120 Cadenas de MarkovMatriz de transici n en dos pasosp(2)11=p211+p14p41+p12p21p(2)12=p12 p22+p11p12p(2)14=p14p44+p11p14p(2)21=p21 p11+p22p21p(2)22=p222+p21p12p(2)24=p21p1 4p(2)33=p233+p36p63p(2)35=p36p65p(2)36=p 36p66+p33p36p(2)41=p41p11+p44p41p(2)42=p 41p12p(2)44=p244+p41p14p(2)53=p56p63p(2) 55=p255+p56p65p(2)56=p55p56+p56p66p(2)63 =p63p33+p66p63p(2)65=p65p55+p66p65p(2)66 =p266+p63p36+p65p56 Vector de probabilidades inicialesv=(p1,p2,p3,p4,p5,p6)P[estar en la celda 1 en el instante 1]=p1P[estar en la celda 2 en el instante 1]=p2P[estar en la celda 3 en el instante 1]=p3P[estar en la celda 4 en el instante 1]=p4P[estar en la celda 5 en el instante 1]=p5P[estar en la celda 6 en el instante 1]=p6 Cadenas de Markov121 Probabilidad de estar en cierta celda en el instante de tiempo 2vP=([p1p11+p2p21+p4p41],[p1p12+p2p22],[ p3p33+p6p63],[p1p14+p4p44],[p5p55+p6p65] ,[p3p36+p5p56+p6p66])