Cadenas de Markov DiscretasCadenas de MarkovCuando, conociendo el pasado y el presente, el comportamiento probabilstico del futuro inmediato slo depende del estado presentePropiedad Markoviana Sea {Xn: n > 0} un proceso estocstico discreto (es decir, cada Xnes una variable aleatoria discreta). Diremos que tiene la propiedad de markoviana si se cumple: P{Xn+1= j / X0= i0, X1= i1. . . Xn= in } =P{Xn+1= j / Xn= in }=pi,j(n)Probabilidades de Transicinpi,j(n)= la probabilidad de que el proceso, estando en el estado i en el tiempo n, pase al estado j en el instante siguienteCuando pi,j(n) = pi,j(esto es, no depende de n) sedice que las probabilidades de transicin son estacionarias. Lo supondremos de ahora enadelante.Matriz de TransicinLas probabilidades de transicin definen la matrizP = [pij] que satisface1) pij> 0para todo i, j2) para todo i1 pjij= Matriz de Transicin: ejemplo.Tiempo n+1Estado 0 Estado 1 Estado 2 Estado 3Estado 00,20 0,65 0,15 0Tiempo nEtado 10 0,60 0 0,40Estado 20,15 0,15 0,30 0,40Estado 30 0 0 1Clasificacin de Procesos Markovianos Los procesos Markovianos se clasifican de acuerdo al tipo de espacio y tipo de parmetro. Si el espacio de estados es discreto el proceso recibe el nombre de Cadena de Markov, en el otro caso, de espacio continuo, se conoce como Proceso de Markov. Segn el parmetro temporal, en ambos casos se dividen en procesos o cadenas de Tiempo Continuo oTiempo Discreto.7Introduccin a las Cadenas de Markov Introduccin a las Cadenas de MarkovClasificacin de Procesos Markovianos8Cadena de Markov de tiempo discretoEspacioDiscretoTiempo ContinuoEspacio ContinuoTiempo DiscretoCadena de Markov de tiempo continuoProceso de Markov de tiempo discretoProceso de Markov de tiempo continuoEn este documento se describir en profundidad este tipo de cadenas.Introduccin a las Cadenas de Markov Introduccin a las Cadenas de MarkovConceptos bsicos Como las cadenas de Markov poseen espacio de estados discreto, estos se pueden nombrar: {E0, E1, E2, ...} Sin embargo, para simplificar la notacin, se asocian a los nmeros naturales: Para el caso general el entero i representa al estado Ei.9Cadenas de Markov discretasCadenas de Markov discretas Conceptos bsicos Para denotar el estado en que se encuentra la cadena en un tiempo n se utilizar la siguiente notacin: Xn=i , estar en el estado i en el tiempo n. La probabilidad de transicin para ir desde el estado ial estado j en un paso es: Pij = P[Xn+1 =j | Xn =i]10Cadenas de Markov discretasCadenas de Markov discretas Conceptos bsicos En general Pij(n) depende de n. Cuando Pij(n) no depende de n, la probabilidad de transicin desde el estado i al j no varia en el tiempo. 11Cadenas de Markov discretasCadenas de Markov discretas Conceptos bsicos Es posible representar una cadena de Markov por un grafo. Cada nodo representa a un elemento del espacio muestral. Cada arco dirigido representa a la probabilidad de transicin Pij( desde i a j) asociada al par de estados que conecta (i , j)12Representacin grfica:012P00P01P10P02P20P22P11P21P12Cadenas de Markov discretasCadenas de Markov discretas Conceptos bsicos Las probabilidades de transicin Pijse pueden representar en una matriz cuadrada llamada Matriz de Probabilidad de Transicin de la cadena.13Matriz de Probabilidad de Transicin:!KK KKP PP PP P P011 100 01 00P1 /1 /. .TCadenas de Markov discretasCadenas de Markov discretas Desde el estado iHasta el estado jPij14 O O equivalentemente, equivalentemente, el el diagrama diagramade deestados estados puede puederepresentarse representarse en en forma forma matricial matricial de de la la siguiente siguientemanera manera::Representacin Matricial Representacin Matricial11 22 33 44 551122334455P =Conceptos bsicos Las propiedades de la matriz de transicin de probabilidad son:1.Como cada elemento de la matriz representa una probabilidad, sta debe tener un valor entre 0 y 1.15Matriz de Probabilidad de Transicin:.... , 2 , 1 , 0 , ; 0 1 ! > > j i PijCadenas de Markov discretasCadenas de Markov discretas Conceptos bsicos Las propiedades de la matriz de transicin deprobabilidad son:2. Esto significa que para cada estado la suma detodas las probabilidades de transicin sean 1. Adems, dentro de cada fila los valores son nonegativos, estos valores estn entre 0 y 1. La sumade los valores de la fila es1, luego, se dice que lamatrizesde tipoestocstica.16Matriz de Probabilidad de Transicin:== =0.... , 2 , 1 , 0 ; 1jiji para PCadenas de Markov discretasCadenas de Markov discretas Ejemplo:Como se representa una Cadena de Markov? Existen dos formas de representar una cadena de Markov; en forma GRFICA y en forma MATRICIAL17!2 / 1 4 / 1 4 / 14 / 3 0 4 / 14 / 1 4 / 3 0P0121/43/41/41/41/43/41/218 El El diagrama diagramade deestados estados puede puede representarse representarse en en forma forma de detabla tabla de de la la siguiente siguiente manera manera:: En En la la posicin posicin ( (i i,,j j) ) de de la la matriz matriz se se coloca coloca la la probabilidad probabilidad de detransitar transitar desde desde el el estado estado i i al al estado estado j j2100. .97 974ij1. Representacin Grfica 1. Representacin Grfica11 22 33 44 55110.97 0.97 0.03 0.0322334455P =19 El El diagrama diagrama transicin transicinde deestados estados :: Matriz Matriz de deProbabilidad Probabilidadde de transicin transicin entre entre estados estados::2 10.9730.954 50.050.930.0711. Representacin Grfica 1. Representacin Grfica11 22 33 44 5511 000.97 0.97 00 0.03 0.030022 00 00 0.95 0.95 0.05 0.05 0033 00 00 00 0.07 0.07 0.93 0.9344 00 00 00 11 0055 00 00 00 00 11P = Dada , que corresponde a la probabilidad detransicin del estado i al estado j en1 paso, sepuede generalizar a que representa laprobabilidad de ir del estado i al estado j en ntransiciones como:20Cadenas de Markov discretasCadenas de Markov discretas ijPnijP0{ | }; 0 = = =nij nP PX j X i nAdems i,j pertenecen al espacio de estados Si las probabilidades de transicin sonestacionarias, podemos generalizar la expresinanterior a:Esto representa la probabilidad de pasar desde elestado i al estado j en n pasos, partiendo desde elestado i, sin importar como se lleg a este estado(en general, en m pasos).21Cadenas de Markov discretasCadenas de Markov discretas { | }; 0nij n m mP PX j X i n

= = =Adems i,j pertenecen al espacio de estadosEjemplo 1: caminata aleatoria con barreras absorbentesEn el tiempo 0 tengo $ 2 y en los tiempos 1,2,3,... participo en un juego en el que apuesto $1. Gano el juego (y gano $1) con probabilidad p y lo pierdo (perdiendo lo apostado) con probabilidad 1-p. Mi meta es aumentar mi capital hasta $4 y tan prontolo logre me salgo del juego. Tambin salgo cuando me arruine (capital $0).Ejemplo 1 (cont)- Xn: mi capital inmediatamente despus deljuego n-Estados del proceso = {0,1,2,3,4}- Matriz de transicin:

!1p00000p000p 10p000p 100000p 11PEjemplo 2: un modelo para el desplazamiento poblacionalPara efectos de una investigacin, en un determinado pas, una familia puede clasificarse como habitante de zona urbana, rural o suburbana. Se ha estimado que durante un ao cualquiera, el 15% de todas las familias urbanasse cambian a zona suburbana y el 5% a zona rural. El 6% de las familias suburbanas pasan a zona urbana y el 4% a zona rural. El 4% de las familiasrurales pasan a zona urbana y el 6% a zona suburbana.Cadenas de Markov: ejemplo 2Tendremos la siguiente matriz de transicinUrb.Surb. Rur.!90 0 06 0 04 004 0 90 0 06 005 0 15 0 80 0, , ,, , ,, , ,PCadenas de MarkovUrbSurb.Rural0,150,040,050,040,060,060,80,900,90Probabilidades de transicin en n etapasPregunta: si en el tiempo t el proceso de Markov se encuentra en el estado i, cul es la probabilidad de que n pasos despus se encuentre en el estado j ?Resp:P{Xn+t= j /Xt= i }= P{Xn= j /X0= i } (estacionaria)=p(n)i,j(notacin)= elemento (i,j) de la matriz PnConsecuencia de los resultados anterioresPregunta: cul es la probabilidad de que el sistema se encuentre en el estado j en el tiempo n?Resp.Sea a = (a0, a1,...,am)la distribucin inicial de la Cadena de Markov (con m estados) , entonces:P{Xn= j}= elemento j del vectora PnAplicacin de resultados anterioresConsideremos el ejemplo 2, y supongamos que al inicio de la investigacin, el 35% de la poblacin viva en reas urbanas, el 45% en rea suburbana, y el resto en rea rural.a) Si inicialmente una familia vive en un rea rural, cul es la probabilidad de que tres aos despus esta familia viva en un rea urbana?b) Cual es la probabilidad de que tres aos despus de iniciada la investigacin una familia viva en el rea urbana?Aplicacin de resultados anterioresa) 0,0967b) 0,2691) , , , ( a, , ,, , ,, , ,Pt20 0 45 0 35 07411 0 1622 0 0967 01055 0 7593 0 1352 01248 0 3353 0 5399 03!!Ecuaciones de Chapman-Kolmogorov La forma obtener la probabilidad de ir del estado i al estado fen n pasos, es la expresada en esta ecuacin: Pero lo que se est buscando es una forma ms general deexpresar esta probabilidad.\ u=

f k ik n P P Pkfkniknif, ,0 ,131Cadenas de Markov discretasCadenas de Markov discretas Ecuaciones de Chapman-Kolmogorovi32Cadenas de Markov discretasCadenas de Markov discretas fE1E2E3ElEcuaciones de Chapman-Kolmogorov Se desea generalizar el resultado anterior, o sea, obtener laprobabilidad de estar en el estado f en el tiempo b dado quese estuvo en el estado i en el tiempo a. Lo anterior queda representado por la siguiente expresin:? A i f X P Pa bb aif! ! ! |) , (33Cadenas de Markov discretasCadenas de Markov discretas Ecuaciones de Chapman-Kolmogorov Si en el tiempo a se estuvo en el estado i y en el tiempo b seest en el f, entonces en un tiempo intermedio q se pas poralgn estado k. As es posible rescribir la expresin anterior como: ? A= = = =ka q bb aifi X k X f X P P |,34Cadenas de Markov discretasCadenas de Markov discretas Ecuaciones de Chapman-Kolmogorovi35Cadenas de Markov discretasCadenas de Markov discretas fE1E2E3Ela q b ? A= = = =ka q bb aifi X k X f X P P |,Ecuaciones de Chapman-Kolmogorov La expresin anterior es independiente del tipo de procesoestocstico que se presente, por el hecho de contarabsolutamente todos los casos. Usando las propiedades de las probabilidades condicionales puedeescribirse de la siguiente manera: ? A ? A k X i X f X P i X k X P Pq a bka qb aif! ! ! ! ! !| |,36Cadenas de Markov discretasCadenas de Markov discretas Ecuaciones de Chapman-Kolmogorov Esta expresin puede simplificarse, pero debe ser acotada alas cadenas de Markov. Aplicando la propiedad de que el estado actual dependeexclusivamente del estado anterior, se llega a la siguienteexpresin:? A? A !! ! ! ! !kb qkfq aikb aifkq b a qb aifP P Pk X f X P i X k X P P, , ) , () , (| |37Cadenas de Markov discretasCadenas de Markov discretas Ecuaciones de Chapman-Kolmogorov Sean i, k, f \, estados genricos de la cadena deMarkov, se define la ecuacin de Chapman-Kolmogorov : PikmPkfnrepresenta la probabilidad de ir desde elestado i al estado f en m+n transiciones a travs deuna ruta en la que, en el tiempo q, la Cadena deMarkov se encuentra en el estado k. \ > V ! f k in m k P P Pnkfkmikn mif, ,0 , ,,38Cadenas de Markov discretasCadenas de Markov discretas Ecuaciones de Chapman-Kolmogorovi39Cadenas de Markov discretasCadenas de Markov discretas fE1E2E3Ela q bm nCadenas de Markov discretasEcuaciones de Chapman-Kolmogorov Tenemos por lo tanto un procedimiento que nospermite calcular la probabilidad de ir de i a f en n+mpasos, considerando todos los posibles estadosintermedios Es conveniente en este punto introducir notacin matricial: Se tiene la matriz P= {pij} con M estados (matriz de MxM), donde pij es la probabilidad de ir de un estado i a un estado j en un paso, independiente de las anteriores transiciones. 40Cadenas de Markov discretasEcuaciones de Chapman-Kolmogorov =

kmkf ikmfiP P P1 141 Considerando Considerando que que en en el el primer primer paso paso se se efectu efectu la latransicin transicin desde desde el el estado estado k k al al estado estado f, f, tenemos tenemosla la siguiente siguiente forma forma para para la la ecuacin ecuacin de deChapman Chapman--Kolmogorov Kolmogorov:: Para Para el el caso caso especial especial de de m= m=1 1,, es es decir decir se se llega llega al alestado estado f f en en dos dos pasos pasos se se tiene tiene la la siguiente siguiente forma forma:: !kkf ikfiP P P2Cadenas de Markov discretasEcuaciones de Chapman-KolmogorovMf iM f i f ifiMef e iefip p p p p p PP P P + ++! ! !....2 2 1 1211 1 222 2!MM MMijp ppp pp P... .... .. .. .... ...) (1221 1142Descomponiendo:Matriz de transiciones de un paso del sistemaCadenas de Markov discretasEcuaciones de Chapman-Kolmogorov Se observa que la probabilidad de ir de i a f en 2 pasos es: Por lo que se puede extender este resultado para obtener de unavez las probabilidades de ir de un estado i cualquiera a un estado jcualquiera, en dos pasos utilizando la operacin multiplicacinentre dos matrices? A =MffiM i f ippp p p...... ..11) 2 (43Cadenas de Markov discretasEcuaciones de Chapman-Kolmogorov21221 111221 11) 2 (.. ... .. .. ... .... ... .. .. ... ..Pp ppp pp ppp pPMM MM pMM MM p!

!2 ) 2 () 2 ( ) 2 (} {P Pp Pif==44Que es la matriz de transiciones de 2 pasos:Utilizando este resultado se puede extender elanlisis al caso en que n+m=3, es decir calcular laprobabilidad de ir de i a j en 3 pasosCadenas de Markov discretasEcuaciones de Chapman-Kolmogorov! !Memf eniefiP P P1322 2! !Mef e iefiP P P12 1 322 245Para el caso de n+m =3 y siguiendo con el caso en que elestado intermedio e2se alcanza en un paso, para ir de unestado i cualquiera a j tenemos que la ecuacin de Ch-K nosqueda:Descomponiendo en casos podemos escribir la siguienteecuacin:Cadenas de Markov discretasEcuaciones de Chapman-Kolmogorov Utilizando el resultado obtenido anteriormente podemos escribir la ecuacin:? A==MeMffM e e ie f ippp p p P111322 2 2...... ..? A ? A =MffMM M iMMffM i f ippp p pppp p p P...... .. ......... ..1111 11 1346 Desarrollando la expresi Desarrollando la expresi n resulta: n resulta:Cadenas de Markov discretasEcuaciones de Chapman-Kolmogorov Se puede ver que es equivalente a:=MM MiM iMp pp pp pP.. .. .... .... .. .... .... .. ..111 11!MM M MM fp p pp p pP) 2 (1) 2 (1) 2 (1) 2 (1) 2 (11) 2 () 2 (.. .... .. .... .. .. .. .... .. .... ..47p(3)if =*Cadenas de Markov discretasEcuaciones de Chapman-Kolmogorov Por lo tanto podemos obtener la matriz de transicin de 3 pasos, es decir:} {) 3 ( ) 3 (if p P =3 ) 3 (P P =48Que Que entrega entrega las lasprobabilidades probabilidades p p((33))if ifde de ir irde de i i aa ff en en tres tres pasos pasos2 ) 2 ( ) 3 (P P P P P!!Cadenas de Markov discretasEcuaciones de Chapman-Kolmogorov Generalizando este resultado para n pasos, vemos queresolver la ecuacin de Chapman-Kolmogorov esequivalente a encontrar la matriz de transiciones de npasos P(n):n nP P !) (49Notacin Se define la probabilidad de estar en el estado een el n-simo paso, y se anota:50Cadenas de Markov discretas Cadenas de Markov discretas( )[ ],ne nPX e e T \ ! ! Se define el vector al que se asocia la probabilidadde estar en cualquiera de los estados existentesen la cadena en el n-simo, y se anota:T T 4 = ( ) ( ) ( )1. . . . . .n n nENotacin Se define la probabilidad inicial del sistema, comola probabilidad de estar en el estado e en elcomienzo del anlisis, y se anota:51Cadenas de Markov discretasCadenas de Markov discretas ( 0) ( 0) ( 0)1. . . . . .ET T 4 = Anlisis Transiente Ahora se puede generalizar la expresin a:52Cadenas de Markov discretasCadenas de Markov discretas Ejemplo:Este vector indica la probabilidad de estar encualquiera de los estados de la cadena despusde n pasos, con la condicin inicial ( quedefine el estado en el cual se inicia el proceso).( ) ( 1) n nP

4 = 4 ( ) (0) ( ) n nP 4 = 4 (0)4Anlisis Transiente Sea, la probabilidad de estar en el estado een un tiempo n. Sea, , el vector que indicala probabilidad de estar en cualquier estadodespus de n pasos. Sea, P la matriz de transicin de estados: donde Pijes la probabilidad de ir desde el estado i al estadoj, en un paso.53Cadenas de Markov discretasCadenas de Markov discretas T( ) neT T 4 = ( ) ( ) ( )1. . . . . .n n nEAnlisis Transiente La ecuacin deChapman-Kolmogorov en el ltimopaso, en forma matricial, es:54Cadenas de Markov discretasCadenas de Markov discretas ( ) ( 1) n nP

4 = 4 ( ) (0) ( ) n nP 4 = 4 (3)(4)Obs: La ecuacin (3) presenta un mejor desempeo al realizarclculos cuando el nmero de pasos es muy grande.Anlisis Estacionario Una cadena de Markov con probabilidad estacionariacumple:es decir, la probabilidad de estar en el estado e esindependiente del tiempo (n), y es constante.55Cadenas de Markov discretasCadenas de Markov discretas Definicin:T T \pg! ( )lim ;ne eneAnlisis Estacionario Se define el vector de probabilidad estacionariacomo: Se dice que la cadena de Markov tiene probabilidadde transicin estacionaria si se cumple la ecuacinmatricial:56Cadenas de Markov discretasCadenas de Markov discretas Definicin:; ,1,2....,j i iji para j T T ! ! !pg !( )limnnEjemplo (desplazamiento poblacional: ejemplo 2)Dado que la matriz del ejemplo 3 es ergdica, podemos hacer:190 0 06 0 04 004 0 90 0 06 005 0 15 0 80 03 2 13 2 1 3 2 1! T + T + TT T T ! T T T, , ,, , ,, , ,) , , ( ) , , (continuacinUna opcin es: 3 2 13 2 1 23 2 1 1106 0 90 0 15 004 0 06 0 80 0T + T + T !T + T + T ! TT + T + T ! T, , ,, , ,continuacinCuya solucin es (T1, T2, T3) = (0.2077 , 0.4918 , 0.3005)Es decir, si con el paso del tiempo se mantiene el comportamiento descrito por el modelo (lo cual es muy poco probable) despus de muchos aos,aproximadamente, el 21% de la poblacin ocupar las zonas urbanas, el 49% las suburbanas y el 30% la rural.Tiempo de primera pasadaEstamos interesados en tener informacin respecto al nmero de pasos (transiciones) que hace el proceso al ir de un estado i a un estado j por primera vez. Se defineTi,j= tiempo de primera pasada al ir del estado i alestado jTiempo de primera pasadaDefinimos el tiempo esperado de recurrenciaE(Ti,j) = QijSe puede demostrar que se cumple:{Q + ! QT! Qj nnj in ijjjjp 11EjemploEn el ejemplo anterior1/T1= 1/0,2077 = 4,8146 = Q11Es decir, el nmero promedio de aos para que, partiendo de vivir en una zona urbana, una familia regrese a vivir en una zona urbana por primera vez es 4,8 aos.continuacinCul es el nmero promedio de aos para que, partiendo de vivir en zona urbana, una familia llegue a vivir en zona suburbana, por primera vez?. Hacemos primero32 33 22 32 12 31 3232 23 22 22 12 21 2232 13 22 12 12 11 12111QQQ= QQQQ= QQQQ= Qp p pp p pp p pcontinuacinLuego, ignoramos todas las filas y columnas que tengan Q22 y queda el sistema33 13 33 810 0 04 0 105 0 20 0 11132 1232 1232 1232 33 12 31 3232 13 12 11 12, y , es resultado cuyo, ,, ,agrupa y sustituye sep pp p! Q ! QQQ ! Q + Q! Q + Q + ! QQ + Q + ! QcontinuacinEntonces, en promedio transcurren 8,33 aos para que una familia que inicialmente vive en una zona urbana llegue a vivir en zona suburbana, por primera vez.Anlisis Estacionario Se dispone de 4 mdulos de atencin quese van activando secuencialmente amedida que la cantidad de usuarios quedeben ser atendidos aumenta. Cada mdulo tiene un mximo deusuarios a los que puede entregarservicio. Cuando un mdulo est completamenteutilizado, entra en servicio el siguientemdulo. Si un mdulo deja de ser utilizado, elmdulo se desactiva temporalmente,quedando en servicio los mdulosanteriores.66Cadenas de Markov discretasCadenas de Markov discretas Ejemplo:Central TelefnicaG1 G2 G3 G4Anlisis Estacionario Interesa conocer: Cul es la probabilidad deque cada mdulo est enuso?. Es decir, se desea conocer,con que probabilidad se utilizacada mdulo, en cualquierinstante de tiempo.67Cadenas de Markov discretasCadenas de Markov discretas Ejemplo:Central TelefnicaG1 G2 G3 G4Anlisis Estacionario La definicin de estados para el ejemplo ser: Estado 1: El mdulo 1 est siendo utilizado. Estado 2: El mdulo 2 est siendo utilizado. Estado 3: El mdulo 3 est siendo utilizado. Estado 4: El mdulo 4 est siendo utilizado. 68Cadenas de Markov discretasCadenas de Markov discretas Ejemplo:Central TelefnicaG1 G2 G3 G4Anlisis Estacionario Las probabilidades de transicin, asociada a cadamdulo son:69Cadenas de Markov discretasCadenas de Markov discretas Ejemplo:Desde el 1 al 1: 0.3Desde el 1 al 2: 0.7Desde el 1 al 3: 0Desde el 1 al 4:0Desde el 2 al 1: 0.4Desde el 2 al 2: 0.2Desde el 2 al 3: 0.4Desde el 2 al 4: 0Desde el 3 al 1: 0Desde el 3 al 2: 0.3Desde el 3 al 3: 0.1Desee el 3 al 4: 0.6Desde el 4 al 1: 0Desde el 4 al 2: 0Desde el 4 al 3: 0.5Desee el 4 al 4: 0.5Anlisis Estacionario El diagrama de estados que representa la situacinantes descrita es el siguiente:70Cadenas de Markov discretasCadenas de Markov discretas Ejemplo:1 2 3 40.3 0.70.20.40.10.6 0.50.3 0.50.4Anlisis Estacionario La matriz de transicin asociada al ejemplo es:71Cadenas de Markov discretasCadenas de Markov discretas Ejemplo:El vector de probabilidad de transicin estacionariaes:!5 . 0 5 . 0 0 06 . 0 1 . 0 3 . 0 00 4 . 0 2 . 0 4 . 00 0 7 . 0 3 . 0P? A4 3 2 1T T T T !

Anlisis Estacionario Considerando las ecuaciones matricial:72Cadenas de Markov discretasCadenas de Markov discretas Ejemplo:! P1 1 2 3 42 1 2 3 43 1 2 3 44 1 2 3 40 . 3 0 . 7 0 00 . 4 0 . 2 0 . 4 00 0 . 3 0 . 1 0 . 60 0 0 . 5 0 . 5!+++ !+++ !+++ !+++ (1)1 2 3 3 41 ! + + + (2)Condicin de probabilidades totalesEn estado estacionario la probabilidad de estar en estado i en el paso n, es igual a la probabilidad de estar en estado i en el paso n+1Anlisis Estacionario Resolviendo el sistema de ecuaciones anteriores, seobtiene:73Cadenas de Markov discretasCadenas de Markov discretas Ejemplo:12340.0270.1890.3510.433====Anlisis Estacionario Finalmente respondiendo a la pregunta original,Cul es la probabilidad de que cada mdulo esten uso?. La probabilidad de que el mdulo 1 est en uso es 0.027 La probabilidad de que el mdulo 2 est en uso es 0.189 La probabilidad de que el mdulo 3 est en uso es 0.351 La probabilidad de que el mdulo 4 est en uso es 0.43374Cadenas de Markov discretasCadenas de Markov discretas Ejemplo: Se desea estudiar el nmero de alumnos que estnestudiando en la enseanza media de un colegio enparticular. Se considerar que un alumno en un ao en particular puedepasar de curso, repetir el curso cuantas veces seanecesario o retirarse del establecimiento sin posibilidadesde regresar.75Ejemplo 3:Ejemplo 3: Alumno de Enseanza Media Alumno de Enseanza Media Si consideramos los siguientes porcentajes, para pasar de curso, repetir o retirarse en cada ao: 76Repetir 1 ao: 2%Pasar a 2 ao: 97%Retirarse al final del 1 ao: 1%Repetir 2 ao: 3%Pasar a 3 ao: 95%Retirarse al final del 2 ao: 2%Repetir 3 ao: 4%Pasar a 4 ao: 92%Retirarse al final del 3 ao: 2%Repetir 4 ao: 1%Egresar: 96%Retirarse al final del 4 ao: 3%Ejemplo 3:Ejemplo 3: Alumno de Enseanza Media Alumno de Enseanza Media Definicin de estados:Estado 1: Estar en primer ao.Estado 2: Estar en segundo ao.Estado 3: Estar en tercer ao.Estado 4: Estar en cuarto ao.Estado 5: Egresar del establecimiento.Estado 6: Retirarse del establecimiento.77Ejemplo 3:Ejemplo 3: Alumno de Enseanza Media Alumno de Enseanza Media La representacin grfica de los estados definidos es:781 2 36 54Ejemplo 3:Ejemplo 3: Alumno de Enseanza Media Alumno de Enseanza Media Asociando las probabilidades, se grafica de la siguiente forma:791 26Repetir 1 ao: 2%Pasar a 2 ao: 97%Retirarse al final del 1 ao: 1%0.020.010.97Nota: La suma de las probabilidades asociadas a las flechas salientes del estado 1 suman 1.Ejemplo 3:Ejemplo 3: Alumno de Enseanza Media Alumno de Enseanza Media El diagrama de estados completo es:801 263540.020.020.020.030.030.010.01 0.040.97 0.95 0.940.961 1Ejemplo 3:Ejemplo 3: Alumno de Enseanza Media Alumno de Enseanza Media A partir del diagramade estados, se obtiene la siguiente matriz de transicin asociada al sistema.81Ejemplo:1 263540.020.020.020.030.030.010.01 0.040.97 0.95 0.940.961 10.02 0.97 0 0 0 0.010 0.03 0.95 0 0 0.020 0 0.04 0.94 0 0.020 0 0 0.01 0.96 0.030 0 0 0 1 00 0 0 0 0 1P ! Resumen sobre las RepresentacionesResumen sobre las Representaciones 82Cadenas de Markov discretasCadenas de Markov discretas Luego obtenemos el mismo resultado expresadocaso por caso:(5) (4) (4)15 14 45 15 55P P P P P !+ Ejemplo:Anlisis Transiente83Cadenas de Markov discretasCadenas de Markov discretas Ejemplo:1234567C1C2C3C4C5C600.10.20.30.40.50.60.70.80.91ProbabilidadPasosEspacio de Estados Dos Posibles estados: 0 Llueve 1 No llueve Supuesto:El tiempo de maana slo depende del de Hoy.Llueve Hoy Prob. que llueva maana No llueve HoyProb. que llueva maana 84Prediccin del Tiempo Prediccin del TiempoCadenas de Markov: OtrosCadenas de Markov: Otros Ejemplos Ejemplos

F =

E = La matriz de transicin P queda: Grficamente:85P =

E EF F110 10101EF1 E1 FCadenas de Markov: Otros Cadenas de Markov: OtrosEjemplos EjemplosPrediccin del Tiempo Prediccin del Tiempo Sea la probabilidad que llueva hoy de 0.286 Cual es la Probabilidad incondicional de que maana llueva?P ! 07 0304 06. .. .Cadenas de Markov: OtrosCadenas de Markov: Otros Ejemplos EjemplosPrediccin del Tiempo Prediccin del TiempoAplicando el Teorema de Probabilidades Totales:Sea: Probabilidad incondicional de que llover maana.= P(maana llover /hoy llueve) +P(maana llover /hoy no llueve) 87NNN=02 0800 10. . P PN== 0 2 0 7 080 4 0 46 . . . . .Cadenas de Markov: Otros Cadenas de Markov: OtrosEjemplos EjemplosPrediccin del Tiempo Prediccin del Tiempo88? A ? A0 1 0 111 =

E EF F0 0 1= E F1 0 11 1 = ( ) ( ) E F10 1= Cadenas de Markov: Otros Cadenas de Markov: OtrosEjemplos EjemplosPrediccin del Tiempo Prediccin del TiempoEn el caso General: Si a = 0.7 y b = 0.4, entonces la probabilidad lmite que llover ser:es decir:8904 7 !

/13 7 !

/? A ? A! ! 0 14 7 3 7 / /Cadenas de Markov: Otros Cadenas de Markov: OtrosEjemplos EjemplosPrediccin del Tiempo Prediccin del TiempoClasificacin de estados en Cadenas de Markov Estado Alcanzable:El estado j es alcanzable desde el estado i si existe n > 0 tal que p(n)i,j> 0 ; es decir es posible que el proceso llegue al estado j desde el estado i. Se denota i pj.Clasificacin de estados en Cadenas de MarkovEstados que se comunican:Los estados i, j se comunican siinpj.Atencin:la relacin np es una relacin de equivalencia (reflexiva, simtrica y transitiva). Me permite dividir el conjunto de estados en clases de equivalenciaClasificacin de estados en Cadenas de Markov: ejemploEjemplo 4: consideremos una cadena de Markov con matriz de transicina bcd!1 0 0 00 1 , 0 5 , 0 4 , 01 , 0 9 , 0 0 00 0 8 , 0 2 , 0PClasificacin de estados en Cadenas de Markov: ejemploLos estados {a,b,c} se comunican y forman una clase de equivalencia. El estado {d} es otra clase de equivalencia.Atencin: cuando una cadena de Markov tiene slo una clase de equivalencia, se dice que es irreducibleClasificacin de estados en Cadenas de Markovf(n)jk=probabilidad de que, partiendodel estadoj , la cadena llegue al estado kpor primera vez en el tiempo nClasificacin de estados en Cadenas de MarkovProbabilidad de llegar a k (en un tiempo finito), partiendo de j g!!1 njk) n (jkf fClasificacin de estados en Cadenas de MarkovEstado Recurrente. Se dice que el estado i es recurrente sifii= 1.Esto significa lo siguiente: siempre que parta del estado i, podr regresar a el (en un tiempo finito)Clasificacin de estados en Cadenas de MarkovEstado Transitorio (no recurrente)Se dice que el estado i es transitorio si fii< 1.(Esto significa lo siguiente: hay manera de abandonar el estado i, de tal modo que nunca regrese a el)Estado Absorbente:Se dice que el estado i es absorbentesi pii= 1.En el ejemplo 4, a,b y c son transitorios, d es recurrente y tambin absorbenteClasificacin de estados en Cadenas de Markov: ejemploEstado PeridicoUn estado recurrente i es peridico, con periodo k > 1, si k es el menor nmero tal que todas las trayectoria que parte dei y regresan a i, tienen longitud mltiplo de k.Si no es periodico se le dice aperidicoClasificacin de estados en Cadenas de MarkovCadena ErgdicaSi todos los estados de una Cadena de Markov son recurrentes, aperidicos y se comunican entre si, se dice que la cadena es Ergdica. Propiedades a largo plazo de una Cadena de MarkovPregunta interesanteExiste una probabilidad lmite de que el sistema se encuentre en el estado j, despus de muchas transiciones, y que esta probabilidad sea independiente del estado inicial.?Tiempo de primera pasadaDefinimos el tiempo esperado de recurrenciaE(Ti,j) = QijSe puede demostrar que se cumple:{Q + ! QT! Qj nnj in ijjjjp 11basado en el problema de las colas Suponga que cada cliente hace una compra de cola durante cualquier semana (52 semanas por ao). Suponga que hay 100 millones de clientes de cola. La produccin de una unidad de cola es de $1 y se vende a $2. Una empresa de publicidad garantiza, por 500 millones de dlares al ao, un decremento del 10% al 5% de la fraccin de consumidores de cola 1, que se cambian a cola 2 despus de una compra.Debe contratar a la empresa de publicidad la compaa que fabrica cola 1?Ejemplos Ejemplo: Hallar, si existe, la distribucin estacionaria para esta CM con S={1, 2, 3}:!6 , 0 4 , 0 04 , 0 0 6 , 02 , 0 5 , 0 3 , 0QEjemplos13 2 1 Dibujamos el DTE y as comprobamos ms fcilmente que la CM es finita y ergdica:Ejemplos 2 y 3 Planteamos las ecuaciones:=3213216 , 0 4 , 0 2 , 04 , 0 0 5 , 00 6 , 0 3 , 0pppppp13 2 1! + + p p p 4 Resolvemos. Para ello fijamos p1=1 y hallamos una solucin para las ecuaciones de equilibrio:Ejemplos6 , 07 , 06 , 0 3 , 0 12 2= = p p6 , 014 , 0 6 , 03 , 0 7 , 04 , 0 5 , 06 , 07 , 03 3=

= = p p TTk k k P P P , 7 ' 0 , 6 ' 06 ' 01,6 ' 07 ' 0, !Por tanto la solucin verdadera ser de la forma:Normalizamos y obtenemos la solucin verdadera:3 211 7 0 6 0 = = P P P P TT=2310,237,236, 7 0 , 6 0 P P PClasificacin Clasificacin de de los los est est. . yy distribucin distribucin lmite lmite. .Ejemplo:Una compaa esta considerando emplear cadenas demarkov para analizar los cambios en las preferencias delos usuarios por tres marcas distintas de undeterminado producto. El estudio ha arrojado lasiguiente estimacin de la matriz de probabilidades decambiarse de una marca a otra cada mes:1 2 31 0.8 0.1 0.12 0.03 0.95 0.023 0.2 0.05 0.75Clasificacin Clasificacin de de los los est est. . yy distribucin distribucin lmite lmite. .En la actualidad los porcentajes de mercado son 45%,25% y 30%, respectivamente.Cuales sern los porcentajes de mercado de cadamarca en dos meses ms?xn{1,2,3}: marca que adquiere un cliente cualquieraen el mes n=0,1,2,3,...== == == ==75 . 0 05 . 0 . 00 . 0 95 . 0 03 . 0. 0 . 0 8 . 0P30 . 0 ) 3 X ( IP5 . 0 ) X ( IP45 . 0 ) X ( IPf0000Clasificacin Clasificacin de de los los est est. . yy distribucin distribucin lmite lmite. .Al trmino del mes siguiente:Y dos meses despus:= == == == =2750 . 0 ) 3 X ( IP2975 . 0 ) 2 X ( IP4275 . 0 ) X ( IPf P f1110 T 1! !! !! !! !2550 . 0 ) 3 X ( IP3391 . 0 ) 2 X ( IP4059 . 0 ) 1 X ( IPf P f2221 T 2Clasificacin Clasificacin de de los los est est. . yy distribucin distribucin lmite lmite. .De aqu las cuotas de mercado en dos meses acambiado de un 45% a un 40.59%; de un 25% a un33.91% y de un 30% a un 25.50%, para las marcas 1,2 y3 respectivamente.Cul es la cuota de mercado en el largo plazo para cadauna de las marcas?La cadena resultante es irreducible con estadosrecurrentes positivos y aperidicos . Denotando porT=(T1,T2,T3)T, las probabilidades estacionarias de largoplazo, las cuales satisfacen:Clasificacin Clasificacin de de los los est est. . yy distribucin distribucin lmite lmite. .T=PTT7 Ti = 1 ; i = 1,2,3.T1=0.8 T1+ 0.03 T2+0.20 T3T2=0.10T1+ 0.95 T2+0.05 T3T3=0.10 T1+ 0.02 T2+0.75 T3T1 +T2+ T3 =1Cuya solucin resulta:T1= 0.2373T2= 0.6184T3= 0.1443Clasificacin Clasificacin de de los los est est. . yy distribucin distribucin lmite lmite. .De aqu que la cuotas de mercado en el largo plazoresultan ser 23.73%, 61.84% y 14.43% para las marcas1,2 y 3 respectivamente.Notar que las actuales cuotas difieren significativamentede las cuotas obtenidas en el largo plazo lo cual puedeimplicar que de alguna manera deban ser corregidas lasprobabilidades de transicin.Concepto de cadena absorbente Sea X una CM cuyos estados son todos transitorios o absorbentes. En tal caso diremos que X es absorbente. Si X es finita y absorbente, reordenamos S poniendo primero los estados transitorios y obtenemos:!IR QQ0'Resultados sobre cadenas absorbentes Proposicin: El nmero medio de etapas que se estar en el estado transitorio jS antes de la absorcin, suponiendo que empezamos en el estado transitorio iS, viene dado por el elemento (i,j) de (IQ)1 Nota: La etapa inicial tambin se cuenta, es decir, en la diagonal de (IQ)1todos los elementos son siempre mayores o iguales que 1Resultados sobre cadenas absorbentes Proposicin: La probabilidad de ser absorbido por un estado absorbente jS, suponiendo que empezamos en el estado transitorio iS, viene dada por el elemento (i,j) de la matriz (IQ)1 R, que se denomina matriz fundamental de la CMEjemplo de CM absorbente En un juego participan dos jugadores, A y B. En cada turno, se lanza una moneda al aire. Si sale cara, A le da 1 a B. Si sale cruz, B le da 1 a A. Al principio, A tiene 3 y B tiene 2 . El juego contina hasta que alguno de los dos se arruine o alcance a tener 5. Calcular: La probabilidad de que A termine arruinndose. La probabilidad de que B termine arruinndose. El nmero medio de tiradas que tarda en acabar el juego. Ejemplo de CM absorbente Tendremos una CM con un estado por cada posible estado de cuentas de A: S={1, 2, 3, 4, 5, 0}. Descomponemos Q:=0 5 , 0 0 05 , 0 0 5 , 0 00 5 , 0 0 5 , 00 0 5 , 0 04321' Q!0 5 , 00 00 05 , 0 04321R!1 0 0 0 0 00 1 0 0 0 00 5 , 0 0 5 , 0 0 00 0 5 , 0 0 5 , 0 00 0 0 5 , 0 0 5 , 05 , 0 0 0 0 5 , 0 0054321Q1 2 345 01 2 34 50Ejemplo de CM absorbente Realizamos los clculos necesarios: =

=

6 , 1 2 , 1 8 , 0 4 , 02 , 1 4 , 2 6 , 1 8 , 08 , 0 6 , 1 4 , 2 2 , 14 , 0 8 , 0 2 , 1 6 , 143211 5 , 0 0 05 , 0 1 5 , 0 00 5 , 0 1 5 , 00 0 5 , 0 14321'11Q I =

2 , 0 8 , 04 , 0 6 , 06 , 0 4 , 08 , 0 2 , 04321'1R Q I123 4 123 450 Ejemplo de CM absorbente Probabilidad de que A termine arruinndose. La ruina de A est representada por el estado 0, que es el 2 estado absorbente. Como empezamos en el 3erestado transitorio (A empieza con 3 ), debemos consultar la 3 fila, 2 columna de (IQ)1R, que nos da una probabilidad de 0,4 de que A empiece con 3 y termine en la ruina. Probabilidad de que B termine arruinndose Como es el suceso contrario del apartado a), su probabilidad ser 10,4=0,6. Tambin podramos haber consultado la 3 fila, 1 columna de (IQ)1R.Ejemplo de CM absorbente Nmero medio de tiradas que tarda en acabar el juego Sumamos los nmeros medios de etapas que se estar en cualquier estado transitorio antes de la absorcin, suponiendo que empezamos en el 3erestado transitorio. Dichos nmeros medios son los que forman la 3 fila de la matriz (IQ)1. El promedio es: 0,8+1,6+2,4+1,2=6 tiradas. Nota: si observamos la 1 columna de (IQ)1R,vemos que los valores van creciendo. Esto se debe a que, cuanto ms dinero tenga al principio A, ms probabilidad tiene de ganar el juego.Ejemplo Cuentas por cobrar El estado de cuentas por cobrar en una empresa se modela con frecuencia como CM. Una cuenta se considera incobrable si han transcurrido mas de 3 meses de su fecha de vencimiento. Entonces al principio de cada mes una cuenta se puede clasificar en cualquiera de los siguientes estados:ctas nuevas, ctas. atrasadas un mes, ctas. atrasadas 2 meses, ctas. atrasadas 3 meses, ctas. saldadas, ctas incobrables. Suponga que los ltimos datos indican que la siguiente cadena de markov describe como cambia una cuenta de un mes al siguiente: (el orden esta de acuerdo al listado) Tendremos una CM con un estado por cada posible estado de cuentas de A: S={cn, a1m, a2m, a3m, pag, incob}. Descomponemos Q:=0 0 0 04 , 0 0 0 00 5 , 0 0 00 0 6 , 0 0' Q=3 , 0 7 , 00 6 , 00 5 , 00 4 , 0R!1 0 0 0 0 00 1 0 0 0 03 , 0 7 , 0 0 0 0 00 6 , 0 4 , 0 0 0 00 5 , 0 0 5 , 0 0 00 4 , 0 0 0 6 , 0 0321incobpagm am am acnQEjemplo Cuentas por cobrarcn a1ma2m a3m pag incobEjemplo Cuentas por cobrar Realizamos los clculos necesarios: !

!

1 0 0 040 , 0 1 0 020 , 0 5 , 0 1 012 , 0 30 , 0 6 . 0 13211 0 0 04 , 0 1 0 00 5 , 0 1 00 0 6 , 0 1321'11m am am acnm am am acnQ Ia3ma2ma1mcna3m a2m a1mcn =

300 , 0 700 , 0120 , 0 880 , 0060 , 0 940 , 0036 , 0 964 , 0321'1m am am acnR Q Ii cob agEjemplo Cuentas por cobrar Cual es la probabilidad que una cuenta nueva sea cobrada alguna vez. Cual es la probabilidad que una cuenta atrasada un mes se vuelva finalmente incobrable. Si las ventas de la empresa son 100 000 $ en promedio mensual Cunto dinero ser incobrable cada ao?.Ejemplo Planificacin de personal La empresa de abogados emplea 3 categoras deabogados: principiantes con experiencia y socios.Durante un ao determinado hay una probabilidad del15% que un abogado principiante sea ascendido aabogado con experiencia y una probabilidad del 5% quedeje la empresa. Tambin hay una probabilidad del 20%que un abogado con experiencia sea ascendido a socio yuna probabilidad del 10% que deje la empresa. Tambinhay una probabilidad del 5% que un socio deje laempresa. La empresa nunca degrada a un abogado.Ejemplo Planificacin de personal Surgen muchas preguntas interesantes que laempresa podra contestar. Por ejemplo, cual esprobabilidad que un abogado principianterecin contratado se vaya antes de ser socio?Enpromedio Cunto tiempo permanece unabogado principiante recin contratado en laempresa? El modelamiento como cadena absorbente demarkov a continuacin:(el orden esta de acuerdo al listado) Tendremos una CM con un estado por cada posible estado de cuentas de A: S={princ, exp, asoc, sale_socio, sale_sinsoc}. Descomponemos Q:=1 0 0 0 00 1 0 0 005 , 0 0 95 , 0 0 00 10 , 0 20 , 0 70 , 0 00 05 , 0 0 15 , 0 80 , 0//exp c/ss/s salesaleasocexri c s scs ssasocprinQEjemplo Planificacin de personal!95 , 0 0 020 , 0 70 , 0 00 15 , 0 80 , 0' Q=05 , 0 00 10 , 00 05 , 0REjemplo Planificacin de personal Realizamos los clculos necesarios: =

=

20 0 03 / 40 3 / 10 010 5 , 2 5exp05 , 0 0 020 , 0 30 , 0 00 15 , 0 20 , 0exp '11asocprinasocprinQ Iasocex ri asoci ex er ri c !

1 03 / 2 3 / 150 , 0 50 , 0exp '1asocprinR Q Ic/socs/socsale saleEjemplo Planificacin de personal Cual es la duracin promedio de un abogado joven recin contratado en la empresa Cual es la probabilidad que un abogado joven llegue a ser socio. Cual es la duracin promedio que pasa un socio en el bufete.