CADENAS DE MARKOV

PROCESOS DE MARKOV

Andréi Andréyevich Márkov (Андре́й Андре́евич Ма́рков) (14 de junio de 1856 - 20 de julio de 1922) fue un matemático ruso conocido por sus trabajos en la teoría de los números y la teoría de probabilidades.

Márkov nació en Riazán, Rusia. Antes de los 10 años su padre, un funcionario estatal, fue trasladado a San Petersburgo donde Andréi entró a estudiar en un instituto de la ciudad. Desde el principio mostró cierto talento para las matemáticas y cuando se graduó en 1874 ya conocía a varios matemáticos de laUniversidad de San Petersburgo, donde ingresó tras su graduación. En la Universidad fue discípulo de Chebyshov y tras realizar sus tesis de maestría y doctorado, en 1886 accedió como adjunto a la Academia de Ciencias de San Petersburgo a propuesta del propio Chebyshov. Diez años después Márkov había ganado el puesto de académico regular. Desde 1880, tras defender su tesis de maestría, Márkov impartió clases en la Universidad y, cuando el propio Chebyshov dejó la Universidad tres años después, fue Márkov quien le sustituyó en los cursos de teoría de la probabilidad. En 1905, tras 25 años de actividad académica, Márkov se retiró definitivamente de la Universidad, aunque siguió impartiendo algunos cursos sobre teoría de la probabilidad.

A parte de su perfil académico, Andréi Márkov fue un convencido activista político. Se opuso a los privilegios de la nobleza zarista y llegó a rechazar las condecoraciones del propio zar en protesta por algunas decisiones políticas relacionadas con la Academia de Ciencias. Hasta tal punto llegó su implicación en la política que llegó a ser conocido con el sobrenombre de "el académico militante".

Márkov arrastró durante toda su vida problemas relacionados con una malformación congénita en la rodilla que le llevaría varias veces al quirófano y que, con el tiempo, fue la causa de su muerte cuando el 20 de julio del año 1922 una de las muchas operaciones a las que se sometió le produjo una infección generalizada de la que no pudo recuperarse.

Aunque Márkov influyó sobre diversos campos de las matemáticas, por ejemplo en sus trabajos sobre fracciones continuas, la historia le recordará principalmente por sus resultados relacionados con la teoría de la probabilidad. En 1887 completó la prueba que permitía generalizar el teorema central del límite y que ya había avanzado Chebyshov. Pero su aportación más conocida es otra.

Su trabajo teórico en el campo de los procesos en los que están involucrados componentes aleatorios (procesos estocásticos) darían fruto en un instrumento matemático que actualmente se conoce como cadena de Márkov: secuencias de valores de una variable aleatoria en las que el valor de la variable en el futuro depende del valor de la variable en el presente, pero es independiente de la historia de dicha variable. Las cadenas de Márkov, hoy día, se consideran una herramienta esencial en disciplinas como la economía, la ingeniería, la investigación de operaciones y muchas otras.

 PROCESOS MARKOV

ESTADOS DEL SISTEMA:

Serie de eventos en el cuales la probabilidad de que ocurriria algo entre ellos depende del evento inmediato anterior se representan por diagramas de estado o por una matriz transacción Aplicaciones: análisis de compra, de compradores, pronostico de concesión a deudores morosos planeación de personales de necesidad.

Un modelo de Markov consiste en un conjunto de estados discretos. Este conjunto es exhaustivo y describe todos los posibles estados donde el sistema puede estar. La transición del estado i a j ocurre con una probabilidad  p_ij

Podemos pensar en un modelo de Markov como una simple línea de transferencia.

Cuando una probabilidad condicional depende únicamente del suceso inmediatamente anterior, cumple con el Principio de Markov de Primer Orden, es decir.

P(X(t+1)=j|X(0)=K0,X(1)=K1,…..,X(t)=i)=P(X(t+1)=j|X(t)=i)=pij

Definiciones en los Procesos de Markov de Primer Orden:

Estados: Las condiciones en las cuales se encuentra un ente ó sucesos posibles.

Ensayos: Las ocurrencias repetidas de un evento que se estudia.

Probabilidad de Transición: La probabilidad de pasar de un estado actual al siguiente en un período ó tiempo, y se denota por p­_ij ( la probabilidad de pasar del estado i al estado j en una transición ó período)

Características de los Procesos de Markov de Primer Orden:

Se pueden usar como modelo de un proceso físico ó económico que tenga las siguientes propiedades:

a)    Que la probabilidad cumpla con el principio de Markov.

b)    Existencia de un número finito de estados.

c)     Las p­_ij son constante con respecto al tiempo ó período.

d)    Ensayos en períodos iguales.

Si un suceso depende de otro además del inmediatamente anterior, este es un proceso de Markov de mayor orden. Por ejemplo, Un proceso de segundo orden describe un proceso en el cual el suceso depende de los dos sucesos anteriores.

Los procesos de Markov también se les llama Cadenas de Markov.

Notaciones que utilizaremos:

p­_ij = probabilidad de transición en un período.

P = [p­_ij]_nxn matriz de transición formada por los valores de p­_ij , donde cada fila representa el estado inicial donde se parte y las columna el estado al que se ira en un período.

Pij=P(X(k)=j|X(0)=i) representa la probabilidad de ir del estado i al estado j en k períodos.  

P^(k)=[ Pij]_nxn la matriz de transición de k períodos.

S_i(t) = probabilidad de encontrarse en el estado i en el período t.

S(t) =(S₁(t) , S₂(t) , . . . . , S_n(t)) vector de probabilidad de estado en el período t.  Para n estados.

Los sucesos que cumplan con un proceso de Markov, se pueden representar por medio de un esquema donde los nodos indique los estados y arcos dirigidos de nodo a nodo con un número que representa la probabilidad de transición de ir de un estado a otro, ó por medio de una matriz de transición.

Ejemplo:

	P=  0,2     0,3     0,5         0,3     0,4     0,3         0,2     0,4     0,4

 

                                                                                                                                

                                   

  

Para calcular:

P(2)11= p₁₁.p₁₁+ p₁₂.p₂₁+ p₁₃.p₃₁

      = 0,2.0,2+0,3.0,3+0,5.0,2 = 0,23

P(2)12= p₁₁.p₁₂+ p₁₂.p₂₂+ p₁₃.p₃₂

      = 0,2.0,3+0,3.0,4+0,5.0,4 = 0,38

P(2)13= p₁₁.p₁₃+ p₁₂.p₂₃+ p₁₃.p₃₃

      = 0,2.0,5+0,3.0,3+0,5.0,4 = 0,39

luego P(2)11+P(2)12+P(2)13 =1

Otra forma es usando el vector de probabilidades y la matriz de transición, es decir:

S(0) = (1, 0, 0)      S(1) = S(0).P = (0,2; 0,3; 0,5)  

S(2) =S(1).P =(0,23; 0,38; 0,39)

 CLASIFICACIÓN DE LOS ESTADOS

Limite de las probabilidades de estado:

Ø Si k tiende a infinito, P(k) llega a una constante, entonces el limite de las probabilidades de estado existe y son independientes de la condición inicial.

Si p es un vector 1 x m  definido como,

Lim_kàinfinito P(k)= p

Entonces p puede satisfacer  p =pP.

Para el ejemplo, esta ecuación se puede ser resueltacon la restricción

S_i^m p_i =1  para obtener (p₁       p₂)

Estado transitorio

Ø S_i  es un estado transitorio si se puede dejar el estado pero nunca retornar a él.

Estado absorbente

Ø S_i es un estado absorbente si el sistema entra al estado y permanece ahí. Y el limite de la probabilidad de estado es 1. este estado es conocido también como estado trampa.

Cadena recurrente

Ø Una cadena recurrente es un conjunto de estados de los que el sistema no puede salir. Un estado transitorio conduce al sistema dentro de este conjunto de estados. El sistema hace saltos dentro de este conjunto indefinidamente. La cadena recurrente es también llamada subcadena de Markov irreducible o de clases recurrentes.

Finalmente se presentan unos útiles factores de las cadenas de Markov:

Ø Cada cadena de Markov debe tener al menos una cadena recurrente

Ø Una cadena recurrente es un estado absorbente generalizado

Ø Un proceso de Markov que tiene una cadena recurrente será completamente ergódica desde dondequiera que el inicie finalizara en cadena recurrente

Ø Si un proceso tiene dos o más cadenas recurrentes, entonces la propiedad ergódica no se mantiene en el tiempo

Ø Un estado transitorio es un estado que ocupa el sistema antes de convertirse en una cadena recurrente

Cadenas de Markov Ergódicas ó cadenas irreductibles.

Describen matemáticamente un proceso en el cual es posible avanzar desde un estado hasta cualquier otro estado. No es necesario que esto sea posible en un paso.

Condición suficiente: si existe un n>0 tal que P_ijⁿ >0, i, j=0,1,2....m. la cadena de Markov, con esta propiedad, se llama ergódica. Entonces, P_ijⁿ = S_k=0 (P_ikⁿ * P_kj), luego p_j =  S_k=0 (p_k * P_kj) y como S_j=0 P_ijⁿ = 1, entonces S_j=0 p_j =1

Teorema. Para una cadena de Markov ergódica, p_j =Lim _nàinfinito P_ijⁿ existe y p_j (j pertenece {0,..,m}) es la única solución no negativa de p_j. Entonces:

p_j =  S_k=0 (p_k * P_kj) y S_j=0 p_j =1.

Una cadena ergódica es regular: Si para alguna potencia de la matriz de transición tiene únicamente elementos positivos de probabilidad (diferente de cero)

Ejemplo 1:

     

Esta matriz repite continuamente este patrón para todas las potencias de P; por consiguiente no es regular ni tampoco ergódica.

Propiedades de las Cadenas de Markov.

1.-  Las probabilidades de estados deben ser igual a uno, es decir.

       S₁(t)+S₂(t)+ . . . . ,+S_n(t) = 1  para n estados.

2.-  Para cada fila de la matriz P se cumple: p_i1+p_i2+...... +p_in = 1  para todo

       i = 1, 2, ..., n

3.-  Las transiciones de un período al siguiente se obtienen de la siguiente      ecuación: S(t) = S(t-1).P   por lo tanto S(t) = S(0).P^t

4.-  Si S(t+1) = S(t)   para t ³ K, Entonces se dice que el sistema se estabiliza ó   que los estados son estacionarios ó estables. Esto implica que S = S.P , es decir.  El vector de estado estacionario sigue siendo igual después de la transición t.

Ejemplo para calcular el vector de equilibrio o de estado estacionario.

Sea :

   

  

cuya solución es: S₁ = 2/3    y  S₂ = 1/3

Observación:  Las ecuaciones que se obtienen del desarrollo de S =S.P  Siempre hay una ecuación que es combinación lineal de las demás ecuaciones, por lo tanto se omite para que el sistema quede con n  ecuaciones y n  variables.

Estados Absorbentes:

Es aquel estado que tiene una probabilidad  de ser abandonado igual a cero, es decir. Una vez en él es imposible dejarlo. Esto quiere decir:

Si i es un estado absorbente si se cumple que  p_ij =0  si i ¹ j  y p_ii =1.

Una cadena de Markov es Absorbente:

Si se cumple:

a)    Tiene por lo menos un estado Absorbente.

b)    Es posible ir de cada estado no absorbente hasta por lo menos un estado absorbente. No es necesario efectuar esta transición en un paso; ni es necesario tener la posibilidad de alcanzar cada estado absorbente a partir de cualquier estado no absorbente.

Análisis de las cadenas de Markov Absorbentes.

A partir del análisis de estas cadenas, es posible determinar los siguientes datos:

1)    El número esperado de pasos antes de que el proceso sea absorbido.

2)    El número esperado de veces que el proceso está en cualquier estado dado no absorbente.

3)    La probabilidad de absorción por cualquier estado absorbente dado.

El primer paso del análisis es construir una submatriz  H de P  formada de estados no absorbentes a estados no absorbentes. Luego H da las probabilidades de ir desde cualquier estado no absorbente hasta otro estado no absorbente en un paso exactamente, H² da las probabilidades de ir desde cualquier estado no absorbente hasta otro estado no absorbente en dos pasos exactamente. H³ da información similar para tres pasos, etc. Por lo tanto, Hⁿ da esta misma información  para n pasos.

Para hallar el número esperado de pasos antes que el proceso sea absorbido, consiste en calcular el número esperado de veces que el proceso puede estar en cada estado no absorbente y sumarlos. Esto totalizaría el número de pasos antes de que el proceso fuera absorbido y por consiguiente el número esperado de pasos hacia la absorción. Luego:

I+H+H²+H³+ ….. = (I-H)^-1 =Q Por consiguiente  Q representa el número esperado de períodos que el sistema estará en cada estado no absorbente antes de la absorción, por lo tanto la suma de cada fila de Q representa el promedio de períodos que transcurren antes de ir a un estado absorbente.

Para hallar la probabilidad de absorción por cualquier estado absorbente dado, se emplea una lógica similar en el análisis. Se construye una submatriz G de P  formada de estados no absorbente a estados absorbentes y representa la probabilidad de ir de un estado no absorbente a un estado absorbente en un paso exactamente, H.G representa la probabilidad de ir de un estado no absorbente a un estado absorbente en dos pasos exactamente y así sucesivamente. Por lo tanto  G+H.G+H².G+..... =( I+H+H²+H³+ …..).G =(I-H)^-1.G = Q.G =R, Y esta  matriz representa la proporción ó probabilidad en que un estado no absorbente pasa a un estado absorbente.

Ejemplo de una matriz de transición absorbente

La Universidad Libre a estudiado la trayectoria de sus estudiantes y a descubierto que: 

A) 70% de los estudiantes de nuevo ingreso regresan al año siguiente, de segundo año el 15% volverá como estudiante de nuevo ingreso y el resto no regresara.

B) El 75% de los estudiantes de segundo año volverán al año siguiente como estudiantes de tercer año, el 15% volverán como estudiantes de segundo año y el resto no regresara. 

C) El 80% de los estudiantes de tercer año regresaran al año siguiente como estudiantes de último año, 10% volverá como estudiante de tercer año y el resto no regresara. 

D) El 85% de los estudiantes de ultimo año se graduaran, y el 10% volverá como estudiante de ultimo año y el resto no regresara. 

Nota: Supongamos que la U no permite que un estudiante que se ha dado de baja, vuelva y tampoco permite que se cambie de curso a mitad de curso. 1) Escriba la matriz de transición de estos datos.

 2.    CLASIFICACIÓN DE LOS ESTADOS:

	Recurrentes: Si i=j y  Sinfn=1 fiin =1	·        Absorbentes si pii =1 ·        Recurrentes nulos uii = inf ·        Recurrentes positivos uii < inf ·        Ergódico: recurrente positivo aperiódico
	Transitorio o transiente: si hay alguna probabilidad positiva de no volver allí,  Sinfn=1 fiin <1
Estados	Efímero: no puede ser alcanzado desde ningún otro estado
	J es  Accesible, si pijn >0
	Comunicados	Si i es accesible desde j Si j es accesible desde i
	Pertenecen a una clase: cadena irreductible
	Periódico: tiene periodo
	Aperiódico: no tiene periódo

Proceso Estocástico

Un proceso estocatico discreto en el tiempo es simplemente una descripcion de la relacion entre las variables aleatorias (x_0, x₁, x₂,…)

Estado Transitorio

Un estado es transitorio si, despues de haber entrado a este estado, el proceso nunca regresa a el. Por consiguiente, el estado i es transitorio si y solo si existe un estado j(j≠i)  que es accesible desde el estado j, pero no viceversa, esto es, si el estado i no es accesible desde el estado j.

Estado Recurrente

Un estado es recurrente si, despues de haber entrado a este estado, el proceso definitivamente regresara a ese estado. Por conciguiente, un estado es recurrente si y solo si no es transitorio.

Un estado i es periodico con periodo K > 1 si K es el numero mas pequeño tal que la trayectoria que conducen del estado i de regreso al estado i tienen una longitud que es multiplo de K. si un estado recurrente no es periodico, se conoce como aperiodico.

Matriz Ergódica 

Si los estados en una cadena son recurrentes, aperiodicos y se comunican entre si, se dice que la cadena es ergódica.

Ejemplos

1.        Una computadora se inspecciona cada hora. Se encuentra que está trabajando o descompuesta. Si está trabajando la probabilidad de que siga trabajando la siguiente hora es 0.9 Si está descompuesta, se toman las medidas para repararla lo que puede llevar más de una hora. Siempre que la computadora esté descompuesta, Independientemente de cuanto tiempo haya pasado, la probabilidad de que siga descompuesta  la siguiente hora es 0.35.

A.      Modele el sistema como una cadena de Markov.

Solución:

Debemos definir los estados

Eo = La maquina está trabajando

E1 = La maquina está descompuesta

	Eo	E1
Eo	0.9	0.1
E1	0.65	0.35

B.       Hoy está trabajando, ¿Cuál es la probabilidad de que en 4 hrs sigatrabajando

Solución:

Buscamos T⁴  = P(4) 

T⁴  =

	Eo	E1
Eo	0.85	0.15
E1	0.84	0.16

2.        Un fabricante de grabadoras está tan seguro de su calidad que está ofreciendo garantía de reposición total si el aparato falla en dos años. Basándose en datos compilados la compañía ha notado que solo el 1 % de las grabadoras falla durante el primer año y 5 % durante el segundo. La garantía no cubre grabadoras ya reemplazadas.

A.      Modele el sistema como una cadena de Markov.

 Solución:

Debemos definir los estados

Eo = Está funcionando en su primer año.

E1 = Está funcionando en su segundo año.

E2 = Se reemplaza por garantía.

E3 = Finaliza la garantía.

	Eo	E1	E2	E3
Eo	0	0.99	0.01	0
E1	0	0	0.05	0.95
E2	0	0	1	0
E3	0	0	0	1

   

3.        Cada familia norteamericana se puede clasificar como habitante de una zona urbana, rural ó suburbana, durante un año determinado el 15% de las familias urbanas se cambian a la zona suburbana y el 5 % a la zona rural. El 6% de la familias suburbanas pasan a la zona urbana y el 4% a la rural, el 4% de las familias rurales pasan a la zona urbana y el 6% a la suburbana .   

A.      Construya la matriz de transición

Solución:

Debemos definir los estados 

        Eo = Zona urbana

        E1 = Zona Rural

        E2 = Zona Suburbana

	Eo	E1	E2
Eo	0.8	0.05	0.15
E1	0.04	0.90	0.06
E2	0.06	0.04	0.90

B.       Si una familia vive actualmente en lazona urbana ¿ Cual es la probabilidad que después de dos años viva en la zona urbana?

Solución: 

Buscamos T²                       

	Eo	E1	E2
Eo	0.651	0.091	0.258
E1	0.0716	0.8144	0.114
E2	0.1036	0.075	0.8214

El valor que buscamos se encuentra en azul y este nos indica que la probabilidad que buscamos es del 65.1 %.

   

C.       Suponga que en la actualidad  el 40% de las familias viven en la zona urbana, el 35% en la zona suburbana y el 25 en la zona rural . Después de dos años ¿Qué porcentaje de familias vivira en la zona urbana?

Solución:

Debemos identificar el vector P =

0.4

0.25

0.35

               

              

Que lo tomamos de los porcentajes que nos da el problema.  

                Buscamos P*T² 

	Eo	E1	E2
Eo	0.651	0.091	0.258
E1	0.0716	0.8144	0.114
E2	0.1036	0.075	0.8214

               

0.4

0.25

0.35

           

                                                                                  

Lo que nos da este resultado:

0.31456

0.26625

0.41919

La respuesta se encuentra marcada en azul, lo que nos da un porcentaje de 31.45% de familias que después de dos años vivira el la zona urbana

4.        El departamento de mantenimiento de una empresa da servicio a tres departamentos de ella (A, B, C), sujeto a ciertas restricciones. Nunca se da servicio al mismo departamento en días seguidos. Si se atiende al departamento A, entonces al día siguiente se atiende al B. Sin embargo, si se atiende a uno de los departamentos B ó C, entonces el día siguiente se tiene doble probabilidad de atender a A, que atender a otro departamento.

1. Construya la matriz de transición:  

Solución:  

	A	B	C
A	0	1	0
B	2/3	0	1/3
C	2/3	1/3	0

Ejemplo

Existe un 75% de posibilidades de que el día siguiente funcione y un 25% de que no funcione , pero si no esta funcionando hay un 75% de posibilidades de que tampoco funcione al día siguiente y solo un 25% de que si lo haga para comenzar el análisis se debe de conocer el estado actual supóngase que esta comenzando y que hay un 75% de posibilidades de que este funcionando y un 25% de que no este funcionando ,Cual es la probabilidad de estar funcionando el primero y segundo día.

Inicio
P (f)= .75
P (nf) =.25

Procedimiento para calcular la proporción de estados no absorbentes que terminaron en estados absorbentes

1.    Eliminar los renglones correspondientes, a los estados absorbentes originales.

2.    Dividir la matriz restante en estados absorbentes y no absorbentes, denominar "g "a la parte de la matriz bajo estados absorbentes y "h" a la parte de la matriz bajo estados no absorbentes.

3.    Calcular la matriz fundamental "Q" que es igual a Q =(I-H)-1 , donde I es igual a la matriz original y el exponente -1 , se refiere al inverso de la matriz.

4.    Calcular la matriz de posiciones R =QG.

Ejemplo

Una empresa de abogados emplea 3 categorías de empleados: principiantes, con experiencia y socios como se muestra en la matriz de transición.

a.    Determine la probabilidad de que un abogado principiante, recién contratado deje la empresa antes de ser socio.

b.    Cual es la probabilidad de que un abogado principiante salga siendo socio.

Conclusión:

• 50% de los principiantes sale siendo socio.
• 50% da los principiantes sale sin ser socio.

De los abogados con experiencia:

• 33% sale sin ser socio.
• 66% sale siendo socio.

De los socios:

• 100% sale siendo socio