• Author / Uploaded
• Ysmar Laisney Lucena Perdomo

Citation preview

Cadenas Markov

Índice 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

Introducción Cadenas de Markov Ecuaciones de Chapman-Kolmogorov Clasificación de los estados en una cadena de Markov Tiempos de primera pasada Estados Absorbentes Cadenas de Markov en tiempo continuo Algunas v. a. importantes Probabilidades de estado estable Ejemplos explicativos

Introducción Las cadenas de Markov se incluyen dentro de los denominados procesos estocásticos. Dichos estudian el comportamiento de variables aleatorias a lo largo del tiempo X(t,w). Se definen como una colección de variables aleatorias {X(t,w), t  I}, donde X (t,w) puede representar por ejemplo los niveles de inventario al final de la semana t. El interés de los procesos estocásticos es describir el comportamiento de un sistema e operación durante algunos periodos. Los procesos estocásticos se pueden clasificar atendiendo a dos aspectos: si el espacio de estados posibles de la variable aleatoria contiene valores discretos o continuos y de si los valores del tiempo son discretos o continuos. Las cadenas de Markov es un proceso estocástico en el que los valores del tiempo son discretos y los estados posibles de la variable aleatoria contiene valores discretos, es decir, es una cadena estocástica de tiempo discreto. Las cadenas de Markov, se clasifican, además, dentro de los procesos estocásticos de Markov, que son aquellos en el que el estado futuro de un proceso es independiente de los estados pasados y solamente depende del estado presente. Por lo tanto las probabilidades de transición entre los estados para los tiempos k-1 y k solamente depende de los estados que la variable adquiere dichos tiempos.

INDICE

Cadenas de Markov Las cadenas de Markov están constituidas por un conjunto de valores {Xn , n :0,1,2...} que cumplen la probabilidad de alcanzar cualquier estado j de la variable depende exclusivamente del estado i alcanzado en el instante de tiempo anterior. P[Xn+1= j / Xn = i, Xn-1 = i1,..., X0=in]=P[Xn+1=j / Xn=i]  i,j Se define para cada par de estados (i, j) que se alcanzan en dos pasos consecutivos de n y n+1 una probabilidad condicional denominada probabilidad de transición pij. P[X+1=j / Xn=i] = pij Las probabilidades de transición de un paso son estacionarias, es decir, que no cambian con el tiempo. Si pij no depende del instante n se dice que la cadena de Markov es homogénea. Las probabilidades de transición estructuradas en forma matricial da lugar a lo que se denomina matriz de transición. Dicha matriz relaciona los estados de la variable en dos pasos consecutivos y n+1 a través de sus probabilidades de transición. Periodo n+1

Periodo n

Estado 1

...

Estado M

Estado 1

p11

p1*

p1M

....

P*1

p**

p*M

Estado M

pM 1

pM*

pMM

Una probabilidad de transición pij ^(n) de n pasos entre los estados i y j indica la probabilidad de que partiendo del estado i en pasos se llegue al estado j. INDICE

Ecuaciones de Chapman-Kolmogorov

Estas ecuaciones proporcionan un método para determinar las probabilidades de que un proceso del estado i notada por pij ^(n). pij ^(n) = k=0..K pik ^(m) pkj ^(-m) ;  i,j,n; 00. Una cadena de Markov se puede dividir en clases. Una clase está formada por todos los estados que son accesibles entre sí . Considerando las probabilidades fii de que el proceso regrese al estado i comenzando en el estado i se puede clasificar los estados en recurrente sí fii =, transitorio sí fii 0. Todos los estados que se comunican forman una clase. Si todos los estados en una cadena forman una clase, entonces la cadena será irreducible, por lo que: pij(t)>0, para todo t>0 y todos los estados i,j , y más aún:

lim pij(t)=j estacionarias). t

llamadas

probabilidades

Las probabilidades estacionarias satisfacen: j qj= i qij para j=0,1,…,M y ij j=0

de

estado

estable(o

M

 j=0

(éstas ecuaciones se suelen llamar de balance). INDICE

Ejemplos explicativos 



Problema de ratón: o Texto (.doc) o Transparencias (.ppt) Problema de la telefonía móvil

Cadenas de Markov Un proceso estocástico en tiempo discreto es una Cadena de Markov en la medida que se verifiquen las siguientes propiedades: Propiedad Markoviana:

Donde i0, i1, ..., in-1, i, j son posibles “ estados” o valores que puede tomar el proceso estocástico en las distintas etapas. Esto consiste básicamente en afirmar que el futuro (t=n+1) es independiente del pasado dado el presente (t=n). Propiedad Estacionaria: La probabilidad

No depende de la etapa n. Por ejemplo, la probabilidad de pasar del estado i al estado j será siempre la misma no importando el número de la etapa. Si consideramos que la variable aleatoria asociado a este proceso markoviano toma un número finito de estados (digamos M) las probabilidades de transición de un estado a otro se pueden resumir en una matriz P denominada matriz de transición de probabilidades en una etapa. Adicionalmente si conocemos la distribución de probabilidad para la etapa inicial (que denotamos por f0) estamos en condiciones de conocer el proceso estocástico, que consiste en determinar la distribución de probabilidad en cada etapa.

Ejemplo Cadena de Markov en Tiempo Discreto Suponga que en un juego existen 2 jugadores, cada uno de los cuales dispone inicialmente de 2 monedas. En cada jugada se gana una moneda con probabilidad ½ o se pierde una moneda con probabilidad ½. El juego termina cuando un jugador tiene 4 monedas o se queda con ninguna. Modele como una Cadena de Markov la situación descrita. Desarrollo: El primer caso consiste en identificar la variable aleatoria la cuál debe representar el problema planteado, en este caso la evolución del juego al cabo de cada etapa o jugada. Se define la variable aleatoria en tiempo discreto Xn : Cantidad de monedas que tiene uno de los jugadores (digamos el jugador A) al cabo de la enésima jugada. Luego se debe identificar los posibles valores o estados que puede tomar esta variable aleatoria para una etapa n cualquiera. Sabemos que el jugador A comienza el juego con 2 monedas y el juego termina cuando pierde todo (y por tanto el jugador B gana) o cuando gana todo (y por tanto el jugador B pierde). En consecuencia, los valores posibles para Xn son{0,1,2,3,4}. A continuación se debe determinar las probabilidades de transición (en una etapa). Por ejemplo, si actualmente el jugador A tiene 2 monedas, la probabilidad que tenga 3 monedas al cabo de una jugada es ½ (probabilidad de ganar) y la probabilidad de que tenga 1 moneda es ½ (probabilidad de perder). De esta forma se identifican las distintas combinaciones o probabilidades de que comenzando en un estado "i" se pueda pasar a un estado "j" al cabo de una etapa. Notar que si el jugador A tiene 0 monedas la probabilidad que continue en ese estado es 1 (o 100%) dado que no tiene monedas para seguir jugando. De la misma forma si el jugador A tiene 4 monedas el jugador B tiene 0 y por tanto la probabilidad de que el jugador A se mantenga en ese estado es de 1 (o 100%).

Las probabilidades de transición en una etapa se pueden representar haciendo uso de un grafo o en forma resumida a través de la matriz de transición de probabilidades.

Cabe destacar que la suma de las probabilidades para cada fila en la matriz de transición P es de un 100%. Podemos responder preguntas adicionales cómo por ejemplo ¿Cuál es la probabilidad de que el jugador A tenga 2 monedas al cabo de 2 jugadas? Haciendo uso del grafo y dado que actualmente el jugador A tiene 2 monedas, se busca identificar las combinaciones que permitan a este jugador mantener esta cantidad de monedas al cabo de 2 etapas. Esto se logra ganando la próxima jugada (con probabilidad ½) y perdiendo la jugada que sigue (con probabilidad ½). También se llega al mismo resultado perdiendo la próxima jugada pero luego ganando en la jugada que sigue. Por tanto la probabilidad de tener 2 monedas al cabo de 2 etapas es P(X2=2/X0=2) = ½*½ + ½*½ = ½.

Clasificación de estados de una Cadena de Markov Para la clasificación de estados de una Cadena de Markov en tiempo discreto utilizaremos 2 ejemplos: Ejemplo 1:

Ejemplo 2:

Si existe una probabilidad no nula que comenzando en un estado i se pueda llegar a un estado j al cabo de un cierto número de etapas (digamos n) se afirma que el estado j es accesible desde el estado i. Si consideramos el ejemplo 1 podemos afirmar que el estado 3 es accesible desde el estado 1. Aún cuando en una etapa no podemos llegar desde el estado 1 al estado 3, si podemos hacerlo al cabo de 2, 3, ..., n etapas. Cabe destacar en este punto que es relevante que exista una probabilidad no nula que comenzando en 1 se pueda llegar a 3 al cabo de un cierto número de etapas no importando el valor exacto de esta probabilidad para un n cualquiera. En cuanto al ejemplo 2, se puede verificar que el estado 2 es accesible desde el estado 3, sin embargo, el estado 2 no es accesible desde el estado 4 (esto porque una vez que se llega al estado 4 no se sale de ese estado). Finalmente, dos estados que son accesibles viceversa se dice que se comunican y que pertenecen a una misma clase de estados. Una Cadena de Markov donde todos sus estados son accesibles entre sí y por tanto se comunican se dice que es irreducible, es decir, que existe una única clase de estados. Este es el caso del ejemplo 1. En cambio si al menos existen 2 clases de estados la cadena ya no es irreducible. Si tenemos 2 estados que no se comunican (esto porque no son accesibles viceversa) estos estadosperteneceran a distintas clases de estados. En el ejemplo 2 existen 3 clases de estados {0}, {1,2,3}, {4} (en consecuencia no es una cadena irreducible). En cuanto al estado 0 y estado 4, estos son estados absorventes debido a que una vez que se accede a ellos la probabilidad de seguir en ese estado es de un 100%. Un estado absorvente define una clase de estados por si mismo. Una definición adicional es la periodicidad de un estado. Un estado se dice que tiene periodo d, para el mayor valor entero de d que cumpla:

sólo para valores de n pertenecientes al conjunto {d, 2d, 3d, ....}. Si d=1 decimos que el estado es aperiódico. En otras palabras, un estado es periódico si, partiendo de ese estado, sólo es posible volver a él en un número de etapas que sea múltiplo de un cierto número entero mayor que uno En el ejemplo 1 todos los estados son aperiódicos. En el ejemplo 2 los estados 1, 2 y 3 son periódicos con periodo d=2, es decir, que comenzando, por ejemplo, en el estado 1, la probabilidad de volver al mismo estado es sólo no nula para una cierta cantidad de pasos o etapas múltiplo de 2. Un estado es recurrente en la medida que comenzando en él se tenga la certeza de volver en algun momento del tiempo (una determinada cantidad de etapas) sobre si mismo.

Alternativamente, un estado es transciente si no se tiene la certeza de volver sobre si mismo. En el ejemplo 1 todos los estados son recurrentes. En el ejemplo 2 los estados 1, 2 y 3 son transcientes debido a que si se comienza en cualquiera de ellos no se puede asegurar con certeza que se volverá al mismo estado en algún momento (esto debido a que existe una probabilidad no nula de acceder a un estado absorvente: 0 o 4). Los estados absorventes por definición son estados recurrentes. Si tenemos una Cadena de Markov que tiene una cantidad finita de estados e identificamos un estado recurrente, este será recurrente positivo. Si la cantidad de estados es infinito entonces un estado recurrente será recurrente nulo.

Distribución estacionaria de una Cadena de Markov Se dice que una Cadena de Markov en tiempo discreto admite una distribución estacionaria en la medida que las probabilidades de largo plazo existen y es independiente de la distribución inicial (f0). En este sentido se deben verificar ciertos requisitos para la existencia de esta distribución de probabilidades de largo plazo: la cadena debe ser irreducible y sus estados deben ser recurrentes positivos aperiódicos. Se recomienda revisar en detalle la clasificación de estadosantes del cálculo de la distribución estacionaria. La distribución estacionaria se obtiene a través de la solución única del siguiente sistema de ecuaciones:

Ejemplo cálculo distribución estacionaria de una Cadena de Markov Considere la siguiente matriz de transición de probabilidades para un proceso markoviano en tiempo discreto:

Calcule la probabilidad de encontrarse en cada uno de los estados en el largo plazo. Desarrollo: Para verificar la existencia de una distribución estacionaria debemos analizar si la cadena es irreducible (es decir, existe una única clase de estados) y los estados que la

componen son recurrentes positivos aperiódicos. Para facilitar este proceso se recomienda utilizar una representación gráfica o grafo:

El estado 2 es accesible desde el estado 1, es decir, existe una probabilidad no nula que comenzando en el estado 1 se pueda llegar al estado 2 al cabo de n etapas (no necesariamente esto debe ser al cabo de una etapa). También se puede verificar que el estado 1 es accesibledesde el estado 2, por tanto se concluye que el estado 1 y 2 se comunican. Cabe destacar que2 estados que se comunican pertenecen a una misma clase de estados. Adicionalmente se puede demostrar que el estado 3 es accesible desde el estado 2 y el estado 2 es accesible desde el estado 3. Por tanto el estado 2 y 3 se comunican y por transitividad el estado 1 y 3 se comunican. Se concluye entonces que existe una sola clase de estados que contiene a {1,2,3} y por tanto la cadena es irreducible. Los estados 1, 2 y 3 son recurrentes y dado que la cadena tiene una cantidad finita de estados se puede afirmar que éstos son recurrentes positivos. Finalmente los estados son aperiódicos, es decir, no existe una secuencia de pasos tal para que comenzando en uno de ellos se pueda volver sobre si mismo (con probabilidad no nula) al cabo de un cierto número de pasos o etapas. Una vez que se han verificado las condiciones necesarias para la existencia de una distribución estacionaria se formula el sistema de ecuaciones que permitirá encontrar las probabilidades de estado de largo plazo. En nuestro ejemplo el sistema queda definido por:

La resolución del sistema anterior permite encontrar que:

Se concluye que en el largo plazo la probabilidad de estar en el estado 1 es de un 25% y la probabilidad de estar en el estado 2 y 3 es de un 37,5%.

Distribución Estacionaria y Distribución Límite Distribución Límite Tenemos una matriz de Markov con una distribución límite

inicial

entonces

la

distribución

será:

si llamamos Q al límite de Tk cuando k∞ entonces

Observación: La manera de calcular la matriz Q es un tanto complicado para hacer a mano, la manera más práctica es tomando valores de k altos y comprobando que Tk permanece estable.

Distribución Estacionaria La distribución estacionaria es una distribución de probabilidad  que cumple:

y por tanto es solución del siguiente sistema

La distribución estacionaria será pues una distribución estable que no cambia con el transcurrir de las etapas.

Propiedades de las Cadenas Regulares Si una cadena de Markov es regular entonces cumple las siguientes propiedades: 

Existe la distribución límite ql , la cual será independiente del estado inicial y además será igual a la distribución estacionaria .



La matriz Q límite de Tk cuando k∞ tiene todas las filas iguales y esas filas serán precisamente la distribución estacionaria-límite.



La componente i de la matriz estacionaria representa la probabilidad de que eligiendo una etapa al azar la cadena se encuentre en el estado ei Observación:

Como en las cadenas regulares la distribución límite es equivalente a la estacionaria tenemos dos formas de calcular esta distribución 

De forma manual, resolviendo el sistema visto anteriormente



Utilizando software que permita realizar potencias de matrices. Lo que deberemos hacer será Tk con un k “suficientemente grande” obtendremos la distribución límite-estacionaria si el resultado es una matriz con las filas iguales

Ejemplos de Cálculo de Distribuciones Estacionarias y Límite 

Consideremos el ejemplo de las compañías telefónicas cuya matriz de transición era

En este caso estamos tratando con una cadena regular ya que T tiene todos los elementos positivos, por tanto la distribución estacionaria será igual a la distribución límite, podemos por tanto utilizar el software para calcular T100:

Por lo tanto la distribución buscada será Y la interpretación que le podemos dar es que la empresa A se acabará quedando con un 21,429% de la cuota de mercado, la empresa B con un 23,214% y la C con un 55,357% 

Consideremos ahora la cadena definida por el siguiente grafo

La matriz de transición en este caso será

Esta cadena no será regular ya que si partimos por ejemplo del estado E1 no podremos estar en E3 después de un número impar de etapas. Al no ser regular la cadena no tenemos garantizado que exista una distribución límite ni que coincida con la estacionaria, por lo que habrá que calcularlas de manera independiente. Para calcular la distribución deberemos resolver el sistema

estacionaria

cuya solución es

y

por

tanto

la

distribución

estacionaria

será Por otra parte si intentamos calcular la distribución límite observaremos que

si k es par y

si k es impar Con lo cual deducimos que el límite no existe ya que la distribución de probabilidades va oscilando.

Ejercicios Propuestos 1.- En cierto mercado compiten tres marcas de cierto producto de consumo que se adquiere semanalmente. Efectuando un sondeo entre los establecimientos minoristas en los que se vende se

estima que, de cada cien consumidores del producto, en la semana que ahora termina diez adquirieron la marca 1, veinte la marca 2 y setenta la marca 3. Se ha realizado, además, un sondeo sobre la intención de compra de los consumidores y se ha llegado a la conclusión de que: De cada 100 consumidores que adquirieron la marca 1 la pasada semana, 50 volverán a adquirirla, 10 cambiarán a la 2 y el resto adquirirá la tres. Con relación a la marca 2, de cada 100 que la adquirieron la pasada semana, 80 la volverán a adquirir, 10 cambiarán a la 1, y otros 10 a la 3. En cuanto a la marca 3, de cada 100 adquirientes la última semana, 30 cambiarán a la 1, 20 a la 2 y el resto volverán a adquirir la misma. Se desea estimar las cuotas de mercado de las tres marcas en la semana finalizada y prever las de la próxima. Suponiendo que las proporciones de consumidores que cambian de marca permanezcan estables, calcula la cuota de mercado a largo plazo.

2.- Una persona puede escoger entre tres restaurantes para comer diariamente. si un día escoge el restaurante A, al día siguiente escoge el B y al día siguiente del B siempre el C, pero cuando va a C es igualmente probable que al día siguiente vaya a A o a B. Escribir la matriz de transición del proceso y calcular: a. la probabilidad de que vaya a B tres días después de ir a A. b. Las probabilidades absolutas de ir a cada restaurante cuatro días después de ir a B. c. El promedio de veces que va a cada restaurante.

3.- Dado el sistema de la figura calcula: a. La

matriz de transición b. La distribución estacionaria. c. La probabilidad de estar en el estado 6 dentro de 5 etapas si ahora está en el estado 3 d. El promedio de veces que el sistema se encuentra en el estado 4.

4.- Un agente comercial realiza su trabajo en tres ciudades gallegas: La Coruña, Ferrol y Santiago. Para evitar desplazamientos innecesarios está todo el día en la misma ciudad y duerme en ella,

desplazándose a otra al día siguiente, si no tiene suficiente trabajo. Después de estar trabajando un día en La Coruña, la probabilidad de tener que seguir trabajando en ella al día siguiente es de 0.4, la de tener que viajar a Santiago es 0.4y la de tener que ir a Ferrol es de 0.2. si el viajante duerme un día en Santiago, con probabilidad del 20% tendrá que seguir trabajando en la misma ciudad al día siguiente, en el 60% de los casos viajará a La Coruña, mientras que irá a Ferrol con probabilidad 0.2. Por último, si el agente comercial trabaja todo un día en Ferrol, permanecerá en al misma ciudad , al día siguiente, con una probabilidad de 0.1, irá a Santiago con una probabilidad de 0.3 y a La Coruña con probabilidad 0.6. ¿Cuáles son los porcentajes de días en los que el agente comercial está en cada una de las tres ciudades?.

5.- Pedro es un lector aficionado a la ciencia ficción, novela policíaca y astronomía. Cada semana se compra un libro. Si ahora está leyendo novela policíaca, hay un 70% de probabilidades de que la semana que viene lea astronomía. Nunca lee dos novelas policíacas seguidas. Si está leyendo ciencia ficción hay un 75% de que lea astronomía y un 25% de que lea una novela policíaca. Después de leer astronomía siempre lee una novela policíaca. a. Calcula el porcentaje de libros de astronomía que tiene en casa después de 5000 semanas. b. Calcula la probabilidad de leer ciencia ficción en cualquiera de las tres semanas siguientes a la lectura de un libro de astronomía.

6.- Una centralita telefónica se revisa cada día, pudiendo estar en perfectas condiciones o bien presentar dos tipos distintos de avería (leve o importante). Se supone que el estado de la centralita en un día depende del estado del último día observado. Así, si un día la centralita funciona correctamente, la probabilidad de que al día siguiente también lo haga es de 0.95, la de que tenga avería leve es de 0.04 , mientras que la de avería importante es de 0.01. En el 75% de los casos en los que la centralita tenga una avería leve, esta es reparada de manera que funcione correctamente al día siguiente. En el 20% de los casos, la avería leve persiste al siguiente día, mientras que en el restante 5% se agravará. Cuando la centralita tiene una avería importante pueden ocurrir dos cosas: se repara al día siguiente (con una probabilidad de 0.2) o sigue teniendo la avería grave. Se pide: a. Encontrar el grafo y la matriz de transición de la cadena de Markov asociada al enunciado. b. Si la centralita funciona correctamente un día, ¿cuál es la probabilidad de que dentro de 8 días también esté en perfectas condiciones? c. A largo plazo, ¿cuánto valen las probabilidades de que la centralita funcione bien, la de que tenga avería leve y la de que tenga avería grave?

7.- En un instituto hay dos fotocopiadores iguales, que inicialmente se suponen en funcionamiento. A lo largo de un día, cada fotocopiadora se avería con una probabilidad de ¼. Al final de la jornada laboral se da parte de las averías producidas a la empresa de mantenimiento que las repara en 24 horas (pero no antes).

a. ¿Cuál es la distribución del número de fotocopiadoras que están en servicio en el cuarto día? b. ¿Cuál es el porcentaje de días en los que el instituto no tiene ninguna fotocopiadora disponible?

8.- En la maravillosa tierra de Oz el tiempo funciona de la siguiente manera: Hay tres posibilidades, bien nieva, bien llueve o bien hace sol. Nunca nieva dos días seguidos y si un día lo hace la probabilidad de que al siguiente llueva es de 1/3. Después de llover no nieva nunca y hay una probabilidad de 3/4 de que haga sol. Si un día hace sol al día siguiente nieva un 20% de las veces y llueve un 25%. a. Dibuja un grafo que represente el clima en la tierra de Oz. b. Obtén la matriz de probabilidades. c. Calcula el porcentaje de días que nieva. d. Si hoy hace sol ¿cuál es la probabilidad de que dentro de 2 días llueva?. ¿Y dentro de 10 días?. ¿Qué observas? 4- Cadenas de Markov Editar 3 34…

Para muchos, en un principio lo relacionado con esta temática fue totalmente nuevo, o quizás desconocían por completo que más que un tema a tratar en clase, es algo con lo que diario nos tropezamos. Alguna vez hemos escuchado las predicciones de algún meteorólogo a través de la radio o la televisión, o durante su vida crediticia ha tenido que estar pendiente de una certificación de Data-crédito para el estudio y aprobación de un crédito. Analicemos lo que en ambos casos se da: el meteorólogo seguramente consulta las imágenes satelitales; pero también sabe que el clima en un día del año corresponde de alguna manera a un fenómeno aleatorio, es así como hoy puede ser soleado (temperaturas altas), ser lluvioso o fresco sin lluvia, y que el clima estaría en una y solo una de estas tres posibilidades y que la ocurrencia de una de ellas excluye a las demás. También es fácil ver que la probabilidad de que en un día específico llueva, o sea soleado o fresco sin lluvia, está muy relacionada con lo ocurrido al clima el día anterior. En la situación de Data-crédito las entidades financieras saben que sus

clientes pueden ser fácilmente clasificados de acuerdo al manejo de sus créditos en excelentes, buenos o deficientes, y que si un cliente es clasificado en alguna de ellas en un mes específico, entonces se excluye de las otras posibilidades; y que estas clasificaciones obedecen a cierta aleatoriedad; estos sencillamente son fenómenos relacionados con cadenas de markov. Lo correspondiente a cadenas de markov se lo debemos al matemático ruso Andrei Markov quien desarrolló la actual teoría de procesos estocásticos en el campo de la teoría de la probabilidad. De manera muy exacta, una cadena de markov es una serie de eventos, en la cual la probabilidad de que ocurra un evento depende del evento inmediato anterior (tal como nos muestra los ejemplos anteriormente mencionados).En efecto, las cadenas de este tipo tienen memoria, "Recuerdan" el último evento y esto condiciona las posibilidades de los eventos futuros. Como toda herramienta, por muy útil que parezca ser, mantiene su margen de error, o lo que en otras palabras consideraríamos como desventajas, y por otro lado ventajas, tales como: Ventajas  

Pueden describir sistemas muy complejos. Pueden ser usados para experimentar con sistemas que existan o que no existan sin alterarlos. Desventajas:

  

No existe un conjunto de soluciones cerradas. Cada cambio en las variables de entrada requiere una solución separada o conjunto de ejecuciones. En los modelos de simulación, pueden requerir mucho tiempo para construirlos y ejecutarlos.

Finalmente las cadenas de markov, se pueden aplicar en áreas como la educación, comercialización, servicios de salud, finanzas, contabilidad y producción.

CADENAS DE MARKOV

En los problemas de toma de decisiones, con frecuencia surge la necesidad de tomar decisiones basadas en fenómenos que tienen incertidumbre asociada a ellos. Esta incertidumbre proviene de la variación inherente a las fuentes de esa variación que eluden el control o proviene de la inconsistencia de los fenómenos naturales. En lugar de manejar esta variabilidad como cualitativa, puede incorporarse al modelo matemático y manejarse en forma cuantitativa. Por lo general, este tratamiento se puede lograr si el fenómeno natural muestra un cierto grado de regularidad, de manera que sea posible describir la variación mediante un modelo probabilístico.

Antes de abordar el tema de las cadenas de markov, debemos tener en cuenta que existen modelos de probabilidad para procesos que evolucionan en el tiempo de una manera probabilística, tales procesos se llaman Procesos Estocásticos.

Después de abordar el tema de procesos Estocásticos, hablaremos de las cadenas de markov.

Las Cadenas de Markov tienen la propiedad particular de que las probabilidades que describen la forma en que el proceso evolucionara en el futuro dependen solo del estado actual en que se encuentra el proceso y, por lo tanto, son independientes de los eventos ocurridos en el pasado. Muchos procesos se ajustan a esta descripción por lo que las cadenas de Markov constituyen una clase de modelos probabilísticas de gran importancia. El creador de las cadenas de Markov fue Andrei Andreevich Markov, nació en Ryazan (Rusia) el 14 de junio de 1856 y muere en San Petersburgo en 1914. Este, es uno de los conceptos más importantes en la construcción de modelos en gran cantidad de campos que abarcan desde la sociología a la física teórica, pasando por la ingeniería y la matemática.Markov estudió en San Petersburgo y era mal estudiante en todo menos en matemáticas. Inició sus estudios universitarios de matemáticas en 1874 que acabó en 1878, siendo premiado con una medalla de oro al terminarlos. Su tesis doctoral estuvo en el ámbito de la teoría de números, pero con la retirada de Chebychev (quien fue su maestro y mentor), en 1883, Markov pasó a encargarse del curso sobre la teoría de la probabilidad continuando con el mismo incluso después de su retirada de la universidad en 1905.Sus primeras contribuciones son relativas al teorema límite central para variables independientes pero no idénticamente distribuidas. Sin duda la más grande de sus contribuciones, fue la introducción del concepto de cadena de Markov, como un modelo para el estudio de variables dependientes, el cual dio lugar a una gran cantidad de investigaciones posteriores en la teoría de los procesos estocásticos. Fuentes: http://www.ugr.es/~eaznar/markov.htm

PROCESOS ESTOCÁSTICOS Es un conjunto o sucesión de variables aleatorias: {X(t)CG } definidas en un mismo espacio de probabilidad. En donde: • El índice t representa un tiempo y X(t) el estado del proceso estocástico en el instante t. • El proceso puede ser de tiempo discreto o continuo si G es discreto o continuo. • Si el proceso es de tiempo discreto, usamos enteros para representar el índice: {X1, X2, ...} Ejemplos de procesos estocásticos 1.Serie mensual de ventas de un producto 2. Estado de una máquina al final de cada semana (funciona/averiada) 3. Nº de clientes esperando en una cola cada 30 segundos 4. Marca de detergente que compra un consumidor cada vez que hace la compra. Se supone que existen 7 marcas diferentes 5. Nº de unidades en almacén al finalizar la semana CADENAS DE MARKOV Una cadena de markov es un caso especial de los procesos estocásticos que cumplen la propiedad de markov. Se utilizan para estudiar el comportamiento a corto y largo plazo de ciertos sistemas estocásticos. En otras palabras las cadenas de markov sirven para determinar futuras acciones solamente dependiendo del estado inmediatamente anterior y solo de este (no se tiene en cuentas otros estados en el pasado). Estas pueden ser con tiempo continuo o discreto. Matemáticamente seria:

A la hora de representar una cadena de markov , esta puede representarse por medio de grafos o en forma matricial. Los grafos son conjuntos de nodos (vértices) unidos por enlaces llamados arcos (aristas), estos enlaces representan una probabilidad de transición (probabilidad de pasar de un estado a otro estado o quede en el mismo), mientras que los nodos representan los estados que posee la situación a representar. Es usual hacer primero la representación por medio de grafos y luego representarlo en forma de matriz, Ejemplo:

Esta matriz lleva como nombre matriz de transición Y debe satisfacer las siguientes condiciones:

Forma general de una matriz de transición:

Generalmente pensamos que una cadena de markov describe el comportamiento de transición de un sistema en intervalos iguales. Existen situaciones donde la longitud del intervalo depende de las características del sistema y, por tanto, puede tal vez no ser igual. En este caso se denomina cadenas de markov encajadas. Probabilidades de transición: es la probabilidad de estaren un estado después de un numero determinado de transiciones, donde:

Estas ecuaciones se conocen como las ecuaciones de chapman-kolomogorov. Ejemplo:

Y, en general:

ELEMENTOS DE UNA CADENA DE MARKOV –Un conjunto finito de M estados, exhaustivos y mutuamente excluyentes (ejemplo: estados de la enfermedad) –Ciclo de markov (“paso”) : periodo de tiempo que sirve de base para examinar las transiciones entre estados (ejemplo, un mes) –Probabilidades de transición entre estados, en un ciclo (matriz P) –Distribución inicial del sistema entre los M estados posibles ECUACIONES DE CHAPMAN-KOLMOGOROV Las ecuaciones de chapman-kolmogorov proporcionan un método para calcular la probabilidad de que una variable aletoria, comenzando en el estado i se encuentre en el estado j después de n pasos. La matriz de probabilidad de transición de n pasos se puede obtener la n-esima potencia de la matriz de transición de un paso. NOTA: una probabilidad incondicional es la probabilidad que despues de n pasos el proceso se encuentre en el estado i

ESTADOS DE LAS CADENAS DE MARKOV

1. Estado Absorbente. Este es un estado en el cual, no se puede salir de ese estado, es decir: Pii = 1, Pij = 0 2. Estado Periódico. Este estado se caracteriza porque despues de cada n-periodos, se repite la misma matríz, es decir: Pii = 0, Pij 0 3. Estado Recurrente. Este es un estado en el cual puedo volver al mismo estado, cuando quiera en n-pasos. Se puede hacer esto infinitamente. NOTA: Todos los estados periódicos son recurrentes, pero no todos los estados recurrentes son periódicos" 4. Estado Transitorio. No regresa al estado de modo seguro, es decir, un estado b tiene dos caminos por donde coger(a y c), si coge por el camino del estado a, no puede volver al estado b, y por consiguiente, tampoco puede pasar al estado c, y si coge por el camino del estado c, no puede volver al estado b, y por consiguiente, tampoco puede pasar al estado a. 5. Estado Ergódico.

 

Son estados No nulos, Recurrentes y Periódicos. En este estado es posible ir de un estado i a cualquier otro estado j, y por eso se dice que cumple las condiciones de estado estable, es decir, estas probabilidades cuando pase el tiempo, tienden a converger a medida que se incremente el numero de pasos (aplicando ecuaciones de Chapman-Kolmogorov) y cuando las probabilidades convergen, a estas se le llaman probabilidades de estado estable.

PROPIEDADES DE LAS CADENAS DE MARKOV EN EL LARGO PLAZO Son aquellas que después de un numero grande de pasos, se encuentre en un estado i. π i= Probabilidad de estado estable, que después de n-pasos, el sistema se encuentre en i.

Tiempo de recurrencia:

  

Numero esperado de transiciones para que regrese al estado estable. Cuantos pasos se deben dar en promedio, para que si un estado salio de i, vuelva a ese estado i. Es el inverso de las probabilidades de estado estable.

Continuando con el tema de las cadenas de Markov, y sabiendo que es el proceso por medio del cual, podemos estudiar el comportamiento de ciertos sistemas estocásticos a corto y largo plazo. Mostraremos un ejemplo.

Como ya hemos observado una cadena de markov puede clasificarse en los siguientes estados: - Estado ergódico - Estado periódico - Estado recurrente - Estado absorbente

Para estudiar las propiedades a largo plazo de las cadenas de Markov nos basamos específicamente en las cadenas de Markov ergódicas. Recordemos que una C.M ergódica es aperiódica, recurrente y no nula (si hay estados absorbentes no es una cadena ergódica). En este tipo de cadenas se puede ir de un estado i a un estado j en n pasos, aunque no exista un arco dirigido de un estado i a un estado j, es decir, tiene la libertad de ir de un estado a cualquier otro en n pasos. Esto nos lleva a afirmar que hay una evidencia de que existen condiciones de estado estable, por lo tanto, las probabilidades cada vez que avance el tiempo van a tender a converger en cierto punto, como se desarrolló en la clase y lo recordaremos a continuación. Lo anterior se resuelve cuando aplicamos las ecuaciones de Chapman-Kolmogorov. Para tener una idea más clara de ello, podemos remitirnos al ejemplo realizado en clase, donde para n pasos las probabilidades se repetían. Entonces, tenemos la matriz de transición P:

Ahora hallamos en excel la matriz P en dos pasos:

Por último obtenemos P en cuatro pasos, y como podemos ver los valores tienden a tener las mismas probabilidades. A estas les llamamos probabilidades de estado estable, ya que mantienen valores fijos que a su vez nos indican donde encontrar el proceso después de un gran número de transiciones.

en donde, para una cadena de markov irreducible ergódica

donde las πj satisface las siguientes ecuaciones de estado estable:

además, las πj pueden ser interpretadas como las probabilidades estacionarias, las cuales se pueden expresar para la matriz anterior de la siguiente manera:

Para obtener los resultados de arriba, podemos aplicar el producto cruz, o bien resolverlas por medio de la herramienta de excel llamada solver,

muy útil para obtener al final el valor de las probabilidades estacionarias.

TIEMPO PROMEDIO DE PRIMER PASAJE

En una cadena ergódica, sea número esperado de transiciones antes de alcanzar por primera vez el estado j, dado que estamos actualmente en el estado i.

se llamatiempo promedio de primer pasaje del estado i al estado j.

Suponga que estamos ahora en el estado i. Entonces, con probabilidad

,

necesitaremos una transición para pasar del estado i al estado j. Para pasamos a continuación, con probabilidad necesitará un promedio de de pensar indica que:

, al estado k. En este caso, se

transiciones para pasar de i a j. Este modo

Como

Podemos reformular la ultima ecuación como

Al resolver las ecuaciones lineales representadas en , podemos encontrar todos los tiempos promedios de primer pasaje. Se puede demostrar que

Con ello se puede simplificar el uso de las ecuaciones

.

Fuente: WINSTON Wayle L. Investigación de operaciones aplicaciones y algoritmos

Tiempos de la primera o las (n) pasadas

También se ve en algunos libros como tiempo de primer regreso

donde

Que se halla por medio de la ecuación:

Para el mismo ejemplo queriendo hallar la matriz f(3), comenzaríamos diciendo que la primera matriz para

Luego para encontrar la probabilidad de ir desde i hasta j en 2 pasos, aplicamos la fórmula (1), y para tener un orden, comenzaremos por

Por lo tanto

. Así se sigue calculando hasta que sale la matriz:

Ahora, para la de 3 pasos, utilizamos el mismo procedimiento, PERO con los datos para 2 pasos. Es decir:

ESTADOS ABSORBENTESLos estados bsorbentes son aquellos estados que cuando el proceso entra a ellos nunca vuelve a salir; un estado k se llama estado absorbente si Pkk = 1, de manera que una vez que la cadena llega a un estado k permanece ahi para siempre. si k es un estado absorbente y el proceso comienza en el estado i, l probabilidad de llegar en algun momento a k se llama probabilidad de absorcion al estado k.El estudio de estos estados son muy importantes y nos permiten determinar el numero esperado de pasos antes de que el proceso sea absorbido. Es importante identificar en una matriz cuales son los estados absorbentes y se busca una solucion a partir de ella, la matriz de probabilidades de absorcion es la siguiente:

figura 1 En la matriz P, el lugar donde se encuentra situado Q colocamos las probabilidades de los estados no absorbentes , en R las probabilidades de absorcion, mientra que en I encontramos las probabilidades de los estados absorbentes y 0 es una matriz nula.Para resolver esta matriz utilizamos las ecuaciones de chapman-kolmogorov y si hallamos P^2 sera

figura 2

y asi P^n sera: figura3 si hallamos el limite cuando n tiende a infinito nos queda

figura 4: este es el limite de las probabilidades de absorcionla matriz (I-Q)^-1 se le llama la matriz fundamental de la cadena de markov y en esta matriz nos indican que si estamos en un estado transitorio ti el numero de periodos que pasaran en un estado transitorio tj antes de la absorcion es el ij-esimo elemento de la matriz (I-Q)^-1.en definición son las veces que habra que pasar por un estadoo transitorio antes de llegar a un estado absorbente).Y si estamos en el estado transitorio ti la probabilidad ser absorbido por un estado absorbente aj es ij-esimo elemento de la matriz (IQ)^-1R en definición son las probabilidad de terminar en cada uno de los estados absorbentes.Es importante tener claro que en el momento de restar I-Q, esta matriz I debe ser del mismo rango que Q, y no es la misma matriz identidad de la figura 1, esta puede tener un rango (mxn) diferente.

Este experimento tiene como fin la demostración de la propiedad que poseen las cadenas de Markov llamada estadosestable, donde las propiedades absolutas son independientes de a(0). Dicha propiedad se empieza a manifestar a partir de un número considerable de periodos (pasos), donde la probabilidad de encontrarse en cualquier estado es aproximadamente la misma. Para la ejecución del experimento se utiliza un reproductor de música (Windows Media Player); una vez abierto el programa se debe realizar una lista de reproducción, preferiblemente de 3 o 4 canciones, debido a que si se escoge un número mayor el espacio muestral (todos los posibles resultados que puede tener una variable) del experimento será muy grande. Del ejemplo, el espacio muestral se determina por la siguiente expresión: n2, donde n es el número de canciones en la lista de reproducción. Ejemplo: si se escogen 3 canciones, el espacio muestral para el experimento sería 32=9, si son 5 canciones el espacio será 52=25 y así sucesivamente. Para tener una idea más clara observe las siguientes representaciones: Para n igual a 3:

Para n igual 5:

En este link podemos encontrar Todo lo relacionado con Propiedades a largo plazo de las Cadenas de Markov

http://www.investigacion-operaciones.com/Libro/Cadenas%20de%20Markov.pdf

APLICACIONES DE LA CADENA DE MARKOV METEOROLOGIA: En los estudios meteorologicos que hacen para las regiones por varios dias, pues el estado actual depende del ultimo estado y no de la historia en si, y como sabemos que la cadena de Markov no tiene memoria, ya que solo tiene en cuenta exactamente el episodio inmediatamente anterior, entonces aqui se pueden usar los modelos metodologicos un poco mas basicos de los usados. JUEGOS DE AZAR: Existen muchos juegos de azar que se pueden modelar por medio de la cadena de Markov, como por ejemplo el modelo de la ruina del jugador, que ayuda a conocer la probabilidad de una persona que apueste en un juego de azar pierda todo su dinero. NEGOCIOS: Aqui se utilizan para analizar los patrones de compra de las personas que estan en mora con algun pago establecido, tambien para saber cuales son las necesidades del personal y para organizar los reemplazos del equipo. NOTAS DE CLASE:Probabilidad de Transición: Probabilidad de pasar de un estado i a un estado j en un determinado periodo.



UN PROCESO DE MARKOV ES UN MODELO ADECUADO PARA DESCRIBIR EL COMPORTAMIENTO DE SISTEMAS DONDE: EL SISTEMA ESTA SITUADO EN UNO DE UN CONJUNTO DE ESTADOS DISCRETOS MUTUAMENTE EXCLUYENTES Y COLECTIVAMENTE EXHAUSTIVOS S0,S1, S2,...., Sn.

 

EL ESTADO PRESENTE DEL SISTEMA Y LAS PROBABILIDADES DE TRANSICION ENTRE VARIOS ESTADOS DEL SISTEMA: CARACTERIZAN EL COMPORTAMIENTO FUTURO DEL SISTEMA. DADO QUE UN PROCESO DE MARKOV SE ENCUENTRA EN UN ESTADO DETERMINADO, SU COMPORTAMIENTO FUTURO NO DEPENDE DE SU HISTORIA ANTERIOR A SU ENTRADA A ESE ESTADO.

 

MUCHOS PROCESOS DE MARKOV EXHIBEN UN COMPORTAMIENTO DE ESTADO ESTABLE: LAS PROBABILIDADES DE QUE EL PROCESO SE ENCUENTRE EN UN ESTADO DETERMINADO SON CONSTANTES EN EL TIEMPO. SE DICE QUE UN ESTADO “Sj” ES TRANSITORIO SI DESDE UN ESTADO “Sk” QUE PUEDE SER ALCANZADO DESDE “Sj”, EL SISTEMA NO PUEDE REGRESAR A “Sj”.



SE DICE QUE UN ESTADO “Sj” ES RECURRENTE SI DESDE CADA ESTADO “Sk” ALCANZABLE DESDE “Sj”, EL SISTEMA PUEDE REGRESAR A “Sk”. UNA CADENA SENCILLA ES UNA SERIE DE ESTADOS RECURRENTES TAL QUE EL SISTEMA PUEDE LLEGAR A CUALQUIER ESTADO DE LA CADENA DESDE CUALQUIER OTRO ESTADO DE ESTA. UN CAMBIO DE ESTADO EN UN PROCESO DE MARKOV DE TRANSICION CONTINUA PUEDE PRODUCIR CAMBIOS DE ESTADO EN CUALQUIER INSTANTE DE UNA ESCALA DE TIEMPO CONTINUA. APLICACIONESJ APLICACIÓN DE LAS CADENAS DE MARKOV A LOS PROCESOS DE SERVICIOS HOSPITALARIOS PARA LA TOMA DE DECISIONES EN LA ADMINISTRACIÓN DE LA SALUD Teniendo en cuenta la necesidad imperiosa de satisfacer las necesidades de los pacientes cuando se encuentran recibiendo un servicio dentro de un centro hospitalario, se aplica la cadena de markov para determinar el tiempo promedio de estancia de los pacientes en una sala determinada, con un determinado nivel de probabilidad en dichos estados transitorios. Se arriba a los resultados para dar a los directivos de la institución una herramienta para la toma de decisiones dentro del campo de la administración en salud, lo cual pudiera contribuir a conocer los costos hospitalarios de estadía, optimizar los recursos disponibles, perfeccionar los servicios de salud y lograr la excelencia en los servicios prestados. Se hace énfasis en el uso de la cadena de markov como herramienta estadística que permite determinar la ocurrencia de un evento futuro en dependencia de la ocurrencia del evento inmediatamente anterior, y tiene como bondades que permite encontrar la probabilidad de que un sistema se encuentre en un estado particular en un momento dado y más importante aún, el promedio a la larga o las probabilidades de estado estable para cada estado analizado, prediciendo el comportamiento del sistema a través del tiempo. Dicha herramienta de análisis a pesar de haber surgido a principios del siglo pasado es una técnica novedosa, de gran utilidad y rigor científico que sirve tanto para economistas, sociólogos, físicos, y otros investigadores que analicen un proceso dado bajo ciertas circunstancias probabilísticas. NOTA: AQUI dejo el link para que todos puedan leer este interesante articulo sobre las aplicaciones de las cadenas de markov. http://www.eumed.net/cursecon/ecolat/cu/2011/pdc.htm USO DE CADENAS DE MARKOV PARA LA PREDICCIÓN DE LA DINÁMICA DEL COMPORTAMIENTO DE PACIENTES EN UNA UNIDAD DE CUIDADO INTENSIVO CARDIOLÓGICA En este proyecto se presenta un modelo probabilístico que contribuye al estudio de la dinámica en el comportamiento y permanencia de pacientes en una unidad de cuidados intensivos cardiológica. El modelo utilizado corresponde a una Cadena de Markov en tiempo discreto, que mediante la definición de determinados niveles de gravedad de un paciente (estados) y la obtención de las correspondientes probabilidades de transición entre un nivel de gravedad y otro, permite predecir los tiempos de permanencia. Los diferentes estados empleados se basan en la construcción de un nuevo score creado para este propósito. Se muestran los detalles de la metodología adoptada y los principales resultados alcanzados en la aplicación del modelo empleado.

NOTA: AQUI dejo el link para que todos puedan leer este interesante articulo sobre las aplicaciones de las cadenas de markov. http://www.scielo.cl/pdf/ingeniare/v14n2/art09.pdf

Aplicaciones

En su afán por encontrar nuevas formas de energía el hombre a explorado muchos campos, así definió la energía eólica, molecular, hidráulica, solar, entre otras. La base de esta aplicación se utiliza en encontrar la velocidad del viento en intervalos de tiempos pequeños e intervalos muy pequeños, es decir en Δt de una hora (intervalos pequeños) y de minutos (intervalos muy pequeños). Se han hecho muchos estudio acerca del comportamiento del viento, ya que es de vital importancia para el manejo de las turbinas en estas centrales, para disminuir el voltaje y frecuencia en la maquina. El objetivo de este algoritmo además del control de las turbinas de viento en los regímenes operacionales es el minimizar los efectos en los sistemas de poder mientras se optimiza la producción de energía, también se debe minimizar los cambios de conexión/desconexión de los generadores, para obtener tiempos estándares de producción.

Este estudio se puede llevar por dos formas:

1. Predicción del clima por agencias meteorológicas 2. Redes artificiales, modelos estadísticos

Se ha desarrollado un nuevo modelo para la predicción de la velocidad del viento a muy corto plazo ANN, utilizando la cadena de marcok (MC) por sus siglas en ingles, y regresión lineal. El modelo propuesto utiliza ANN para la predicción de la velocidad principal del viento. Entonces, MC de segundo orden se aplica para calcular la matriz de probabilidades de transición (TPM, por sus siglas en ingles) de los valores previstos. Finalmente, la regresión lineal entre las predicciones primarias y los valores de probabilidad obtenidas por el MC se utilizan hacia la predicción final. Estos valores se utilizan para modificar los valores previstos en el modelo de datos del viento a largo plazo.Para más información, les recomiendo leer el siguiente articulo

science.pdf   

Details Download 919 KB

EJEMPLOS 1. Ejemplo : Una tienda de cámaras tiene en almacén un modelo especial de cámara que se puede ordenar cada semana. Sean D1, D2, … las demandas de esta cámara durante la primera, segunda, … , semana, respectivamente. Se supone que las Di son variables aleatorias independientes e idénticamente distribuidas que tienen una distribución de probabilidad conocida. Sea X0 el número de cámaras que se tiene en el momento de iniciar el proceso, X1 el número de cámaras que se tienen al final de la semana uno, X2 el número de cámaras al final de la semana dos, etc. Suponga que X0 = 3 . El sábado en la

noche la tienda hace un pedido que le entregan el lunes en el momento de abrir la tienda. La tienda hace un pedido que le entregan el lunes en el momento de abrir la tienda. La tienda usa la siguiente política ( s, S)1 para ordenar : si el número de cámaras en inventario al final de la semana es menor que s =1 (no hay cámaras en la tienda), ordenar (hasta) S=3. De otra manera, no coloca la orden (si se cuenta con una o más cámaras en el almacén, no se hace el pedido). Se supone que las ventas se pierden cuando la demanda excede el inventario. Entonces, {X1} para t = 0, 1, .. es un proceso estocástico de la forma que se acaba de describir. Los estados posibles del proceso son los enteros 0, 1, 2, 3 que representan el número posible de cámaras en inventario al final de la semana. Observe que {Xi}, en donde Xi es el número de cámaras en el almacén al final de la semana t ( antes de recibir el pedido }), es una cadena de Markov. Se verá ahora cómo obtener las probabilidades de transición (de un paso), es decir, los elementos de la matriz de transición ( de un paso). Suponiendo que cada Dt tiene una distribución Poisson con parámetro . Para obtener es necesario evaluar . Si , Entonces . Por lo tanto, significa que la demanda durante la semana fue de tres o más cámaras. Así, , la probabilidad de que una variable aleatoria Poisson con parámetro tome el valor de 3 o más; y se puede obtener de una manera parecida. Si , entonces . Para obtener , la demanda durante la semana debe ser 1 o más. Por esto, . Para encontrar , observe que si . En consecuencia, si , entonces la demanda durante la semana tiene que ser exactamente 1. por ende, . Los elementos restantes se obtienen en forma similar, lo que lleva a la siguiente a la siguiente matriz de transición ( de un paso):

Más y Más Aplicaciones De Las Cadenas De Markov ¿Crees que los ingenieros industriales son los que aplican el conocimiento de las cadenas de markov únicamente? Si pensaste que solo los ingenieros industriales son los que aplican las cadenas de markov en su campo laboral, estas errado ya que las cadenas de markov tiene múltiples aplicaciones como las que vienen a contuniacion: Física: Las cadenas de Markov son usadas en muchos problemas de la termodinámica y la física estadística. Ejemplos importantes se pueden encontrar enla Cadenade Ehrenfest o el modelo de difusión de Laplace.

Meteorología: Si consideramos el clima de una región a través de distintos días, es claro que el estado actual solo depende del último estado y no de toda la historia en sí, de modo que se pueden usar cadenas de Markov para formular modelos climatológicos básicos. Modelos epidemiológicos Una importante aplicación de las cadenas de Markov se encuentra en el proceso Galton-Watson. Éste es un proceso de ramificación que se puede usar, entre otras cosas, para modelar el desarrollo de una epidemia Internet: El pagerank de una página web (usado por Google en sus motores de búsqueda) se define a través de una cadena de Markov, donde la posición que tendrá una página en el buscador será

determinada por su peso en la distribución estacionaria de la cadena. Simulación: Las cadenas de Markov son utilizadas para proveer una solución analítica a ciertos problemas de simulación tales como el Modelo M/M/1. Juegos de azar: Son muchos los juegos de azar que se pueden modelar a través de una cadena de Markov. El modelo de la ruina del jugador, que establece la probabilidad de que una persona que apuesta en un juego de azar finalmente termine sin dinero, es una de las aplicaciones de las cadenas de Markov en este rubro. Economía y Finanzas: Las cadenas de Markov se pueden utilizar en modelos simples de valuación de opciones para determinar cuándo existe oportunidad de arbitraje, así como en el modelo de colapsos de una bolsa de valores o para determinar la volatilidad de precios. En los negocios, las cadenas de Márkov se han utilizado para analizar los patrones de compra de los deudores morosos, para planear las necesidades de personal y para analizar el reemplazo de equipo. Música; Diversos algoritmos de composición musical usan cadenas de Markov, por ejemplo el software Csound o Max Probabilidad de transición estacionaria de n pasos.

Las ecuaciones de Chapman-Kolmogorov proporcionan un método para calcular estas probabilidades de transición de n pasos :

Estas ecuaciones simplemente señalan que al ir de un estado i al estado j en n pasos, el proceso estará en algún estado k después de exactamente m ( menor que n) pasos. Así,Es solo las probabilidad condicional de que, si se comienza en el estado i, el proceso vaya al estado k despues de m pasos y después al estado j en n- m pasos.

Los casos especiales de m=1 y m=n-1 conducen a las expresiones

Para toda i, j, y n de lo cual resulta que las probabilidades de transición de n pasos se pueden obtener a partir de las probabilidades de transición de un paso de manera recursiva. Para n=2, estas expresiones se vuelven :

Note que las son los elementos de la matriz P(2) , pero también debe de observarse que estos elementos, se obtienen multiplicando la matriz de transición de un paso por sí misma; esto es , P(2) = P * P = P2 .

En términos más generales, se concluye que la matriz de probabilidades de transición de n pasos se puede obtener de la expresión : P(n) = P * P …. P = Pn = PPn−1 = Pn-1 P.

Entonces, la matriz de probabilidades de transición de n pasos se puede obtener calculando la n-ésima potencia de la matriz de transición de un paso. Para valores no muy grandes de n, la matriz de transición

de n pasos se puede calcular en la forma que se acaba de describir, pero cuando n es grande, tales cálculos resultan tediosos y, más aún, los errores de redondeo pueden causar inexactitudes.

1 Ejemplo : Una tienda de cámaras tiene en almacén un modelo especial de cámara que se puede ordenar cada semana. Sean D1, D2, … las demandas de esta cámara durante la primera, segunda, … , semana, respectivamente. Se supone que las Di son variables aleatorias independientes e idénticamente distribuidas que tienen una distribución de probabilidad conocida. Sea X0 el número de cámaras que se tiene en el momento de iniciar el proceso, X1 el número de cámaras que se tienen al final de la semana uno, X2 el número de cámaras al final de la semana dos, etc. Suponga que X0 = 3 . El sábado en la noche la tienda hace un pedido que le entregan el lunes en el momento de abrir la tienda. La tienda hace un pedido que le entregan el lunes en el momento de abrir la tienda. La tienda usa la siguiente política ( s, S)1 para ordenar : si el número de cámaras en inventario al final de la semana es menor que s =1 (no hay cámaras en la tienda), ordenar (hasta) S=3. De otra manera, no coloca la orden (si se cuenta con una o más cámaras en el almacén, no se hace el pedido). Se supone que las ventas se pierden cuando la demanda excede el inventario. Entonces, {X1} para t = 0, 1, .. es un proceso estocástico de la forma que se acaba de describir. Los estados posibles del proceso son los enteros 0, 1, 2, 3 que representan el número posible de cámaras en inventario al final de la semana. Así, dado que tiene una cámara al final de una semana, la probabilidad de que no haya cámaras en inventario dos semanas después es 0.283; es decir, De igual manera, dado que se tienen dos cámaras al final de una semana, la probabilidad de que haya tres cámaras en el almacén dos semanas después es 0.097; esto es, La matriz de transición de cuatro pasos también se puede obtener de la siguiente manera : P(4) = P4 = P(2) * P(2) Así, dado que queda una cámara al final de una semana, 0.282 es la probabilidad de que no haya cámaras en inventario 4 semanas más tarde; es decir, De igual manera, dado que quedan dos cámaras en el almacén final de una semana, se tiene una probabilidad de 0.171 de que haya tres cámaras en el almacén 4 semanas después; esto es,Probabilidades de transición estacionaria de estados estables. Teorema Sea P la matriz de transición de una cadena de M estados . Existe entonces un vector tal que Se establece que para cualquier estado inicial i , . El vector a menudo se llama distribución de estado estable, o también distribución de equilibrio para la cadena de Markov. Para encontrar la distribución de probabilidades de estacionario para una cadena dada cuya matriz de transición es P, según el teorema, para n grande y para toda i , (1) Como Pij (n + 1) = ( renglón i de Pn )(columna j de P), podemos escribir (2) Ejemplo : Suponga que toda la industria de refrescos produce dos colas. Cuando una persona ha comprado la cola 1, hay una probabilidad de 90 % de que su siguiente compra se de cola 1. Si una persona compró cola 2, hay un 80 % de probabilidades que su próxima compra sea de cola 2. Entonces : Al reemplazar la segunda ecuación por la condición , obtenemos el sistema Al despejar resulta que Por lo tanto, después de largo tiempo, hay probabilidad 2/3 de que una persona

dada compre cola 1 y 1/3 de probabilidad de que una persona compre cola 2. Tiempos de primer paso. Con frecuencia es conveniente poder hacer afirmaciones en términos de probabilidades sobre el número de transiciones que hace el proceso al ir de un estado i a un estado j por primera vez . este lapso se llama tiempos de primer paso al ir del estado i al estado j. cuando J=i, esta tiempo de primer paso es justo el número de transiciones hasta que el proceso regresa al estado inicial i. En este caso, el tiempo de primer paso se llama tiempo de recurrencia para el estado i. Para ilustrar estas definiciones, reconsidérese el ejemplo siguiente : Una tienda de cámaras tiene en almacén un modelo especial de cámara que se puede ordenar cada semana. Sean D1, D2, … las demandas de esta cámara durante la primera, segunda, … , semana, respectivamente. Se supone que las Di son variables aleatorias independientes e idénticamente distribuidas que tienen una distribución de probabilidad conocida. Sea X0 el número de cámaras que se tiene en el momento de iniciar el proceso, X1 el número de cámaras que se tienen al final de la semana uno, X2 el número de cámaras al final de la semana dos, etc. Suponga que X0 = 3 . El sábado en la noche la tienda hace un pedido que le entregan el lunes en el momento de abrir la tienda. La tienda hace un pedido que le entregan el lunes en el momento de abrir la tienda. La tienda usa la siguiente política ( s, S)1 para ordenar : si el número de cámaras en inventario al final de la semana es menor que s =1 (no hay cámaras en la tienda), ordenar (hasta) S=3. De otra manera, no coloca la orden (si se cuenta con una o más cámaras en el almacén, no se hace el pedido). Se supone que las ventas se pierden cuando la demanda excede el inventario. Entonces, {X1} para t = 0, 1, .. es un proceso estocástico de la forma que se acaba de describir. Los estados posibles del proceso son los enteros 0, 1, 2, 3 que representan el número posible de cámaras en inventario al final de la semana. Donde Xt es el número de cámaras en inventario al final de la semana t y se comienza con , Suponga que ocurrió lo siguiente: En este caso, el tiempo de primer paso para ir al estado 3 al estado 1 es dde 2 semanas, el tiempo de primer paso para ir del estado 3 al estado 0 es de 3 semanas y el tiempo de recurrencia del estado 3 es de 4 semanas. En general, los tiempos de primer paso son variables aleatorias y, por lo tanto, tienen una distribución de probabilidad asociada a ellos. Estas distribuciones de probabilidad dependen de las probabilidades de transición del proceso. En particular, denota la probabilidad de que el tiempo de primer paso del estado i al j sea igual a n. Se puede demostrar que estas probabilidades satisfacen las siguientes relaciones recursivas: Entonces se puede calcular la probabilidad de un tiempo de primer paso del estado i al j en n pasos, de manera recursiva, a partir de las probabilidades de transición de un paso. En el ejemplo, la distribución de probabilidad de los tiempos de primer paso del estado 3 al estado 0 se obtiene como sigue: Para i y j fijos, las son números no negativos tales que Esta suma puede ser menor que 1, lo que significa que un proceso que el iniciar se encuentra en el estado i puede no llegar nunca al estado j . Cuando la suma es igual a 1, las pueden considerarse como una distribución de probabilidad para la variable aleatoria, el tiempo de primer paso. Para obtener el tiempo esperado de primer paso del estado i al estado j. Sea , que se define como: entonces satisface, de manera única, la ecuación: Cuando i=j, se llama tiempo esperado de recurrencia. Al aplicarlo al ejemplo del inventario, estas ecuaciones se pueden usar para calcular el tiempo esperado hasta que ya no se tengan cámaras en el almacén, suponiendo que el proceso inicia cuando se tienen

tres cámaras; es decir, se puede obtener el tiempo esperado de primer paso . Como todos los estados son recurrentes, el sistema de ecuaciones conduce a las expresiones La solución simultánea de este sistema es De manera que el tiempo esperado hasta que la tienda se queda sin cámaras es de 3.50 semanas. Caso de Aplicación. Aplicación a la administración : Planeación de Personal. El anális de transición puede ser útil al planear satisfacer las necesidades de personal. Muchas firmas emplean trabajadores de diferentes niveles de clasificación dentro de la misma categoría de trabajo. Esto es común para personal de confianza, oficinistas, obreros calificados, no calificados y personal profesional. La firma debe tener el número de empleados en cada nivel de clasificación para proporcionar la oportunidad de promoción adecuada, cumplir con las habilidades necesarias para el trabajo y controlar la nómina. Una planeación de personal a largo plazo apropiada requiere que se considere el movimiento de personas tanto hacia arriba en el escalafón de clasificación como hacia afuera de la organización. El análisis de Markov puede ayudar en este esfuerzo de planeación. El movimiento de personal a otras clasificaciones puede considerarse como una cadena de Markov. Se supone que hay tres clasificaciones; el grado 1 es la más baja. Además, los descensos se consideran raros y se omiten. El estado “salen” es absorbente, el cual incluye renuncias, ceses, despidos y muertes. Por supuesto, todos los empleados finalmente alcanzan este estado. Las transiciones del grado 1 al grado 2 y del grado 2 al grado 3 representan promociones. Como transiciones de probabilidad, están controladas por la firma, puede establecerse el nivel que la firma determine que es necesario para cumplir sus objetivos. Como ejemplo, supóngase que la firma tiene en este momento 30 empleados del 3, 90 empleados del grado 2 y 300 empleados del grado 1 y que desea mantener este nivel de empleados durante el próximo año. Por experiencia, se espera que salgan el 30 % de los empleados de grado 1 al año, el 20 % de los empleados de grado 2 y el 10 % de aquellos que están en el grado 3. Si la política es contratar sólo en los niveles de clasificación más bajos, cuántos se deben contratar y cuántos se deben promover el siguiente año para mantener estables los niveles ?. Este problema puede resolverse sin el análisis de Markov, pero el modelo es útil para ayudar a conceptualizar el problema. Como se trata sólo de un ciclo, se usa el análisis de transición. El análisis comienza con el graado más alto. No se hacen promociones pero el 10 %, o sea, 3, sale. Todos ellos deben de reemplazarse por promociones del grado 2. En el nivel de clasificación, el 20 % sale y se deben promover 3, con una pérdida de 21. Esto se debe compensar por promoción del grado 1. Al pasar al grado 1, el 30 % sale y 21 deben promoverse, lo cual una pérdida total de 111. Por tanto, el siguiente año se deben contratar 111 empleados del nivel 1.

TIPOS DE MODELOS OCULTOS DE MARKOV· HMM DISCRETOS· HMM CONTINUOS· HMM SEMICONTINUOS HMM DiscretosEn éste, las observaciones son vectores de símbolos de un alfabeto finito con M+1 elementos diferentes. HMM ContinuosSe asume que las distribuciones de los símbolos observables son densidades de probabilidad definidas sobre espacio de observación continuos. HMM Semicontinuos Al igual que los continuos, pero con la diferencia en que las funciones bases son comunes a todo los modelos.

Cadena de Markov

En la teoría de la probabilidad, se conoce como cadena de Márkov a un tipo especial de proceso estocástico discreto en el que la probabilidad de que ocurra un evento depende del evento inmediatamente anterior. En efecto, las cadenas de este tipo tienen memoria. "Recuerdan" el último evento y esto condiciona las posibilidades de los eventos futuros. Esta dependencia del evento anterior distingue a las cadenas de Márkov de las series de eventos independientes, como tirar una moneda al aire o un dado. Reciben su nombre del matemático ruso Andréi Márkov (1856-1922), que las introdujo en 1907.1 Estos modelos muestran una estructura de dependencia simple, pero muy útil en muchas aplicaciones. Índice [mostrar]

Definición formal [editar] En matemática se define como un proceso estocástico discreto que cumple con la propiedad de Márkov, es decir, si se conoce la historia del sistema hasta su instante actual, su estado presente resume toda la información relevante para describir en probabilidad su estado futuro. Una cadena de Márkov es una secuencia X1, X2, X3,... de variables aleatorias. El rango de estas variables, es llamado espacio estado, el valor de Xn es el estado del proceso en el tiempo n. Si la distribución de probabilidad condicional de Xn+1 en estados pasados es una función de Xn por sí sola, entonces:

Donde xi es el estado del proceso en el instante i. La identidad mostrada es la propiedad de Márkov.

Notación útil [editar] Cadenas homogéneas y no homogéneas [editar] 

Una cadena de Márkov se dice homogénea si la probabilidad de ir del estado i al estado j en un paso no depende del tiempo en el que se encuentra la cadena, esto es: para todo n y para cualquier i, j. Si para alguna pareja de estados y para algún tiempo n la propiedad antes mencionada no se cumple diremos que la cadena de Márkov es no homogénea.

Probabilidades de transición y matriz de transición [editar] 

La probabilidad de ir del estado i al estado j en n unidades de tiempo es

, en la probabilidad de transición en un paso se omite el superíndice de modo que queda



Un hecho importante es que las probabilidades de transición en n pasos satisfacen la ecuación de Chapman-Kolmogórov, esto es, para cualquier k tal que 0 < k < n se cumple que

donde E denota el espacio de estados.



Cuando la cadena de Márkov es homogénea, muchas de sus propiedades útiles se pueden obtener a través de su matriz de transición, definida entrada a entrada como

esto es, la entrada i, j corresponde a la probabilidad de ir del estado i a j en un paso. Del mismo modo se puede obtener la matriz de transición en n pasos como: , donde

.

Vector de probabilidad invariante [editar] 

Se define la distribución inicial



Diremos que un vector de probabilidad (finito o infinito numerable) es

.

invariante para una cadena de Márkov si

donde P denota la matriz de transición de la cadena de Márkov. Al vector de probabilidad invariante también se le llama distribución estacionaria o distribución de equilibrio.

Clases de comunicación [editar] 

Para dos estados i,j en el espacio de estados E, diremos que de i se accede a j (y se denotará

) si

para algún n, si

y

denotará i↔j.

entonces diremos que i comunica con j y se

La propiedad "↔" es una relación de equivalencia. Esta relación induce una partición en el espacio de estados. A estas clases de equivalencia las llamaremos clases de comunicación. Dado un estado x, denotaremos a su clase de comunicación como C(x).



Diremos que un subconjunto C del espacio de estados (al que denotaremos E) es cerrado si ningún estado de E-C puede ser accedido desde un estado de C, es decir, si

para

todo x∈C, para todo y∈E-C y para todo natural m>0.

Tiempos de entrada [editar] Si

, definimos el primer tiempo de entrada a C como

la variable aleatoria

esto es,

denota la primera vez que la cadena entra al conjunto

de estados C.

Recurrencia [editar] En una cadena de Márkov con espacio de estados E, si x∈E se define y diremos que:



x es estado recurrente si



x es transitorio si



x es absorbente si



Una clase de comunicación es clase recurrente si todos sus

.

estados son recurrentes. Sea

, si x∈Ediremos que:



x es cero-recurrente si



x es positivo-recurrente si

El real

se interpreta como el tiempo promedio de recurrencia.

Periodicidad [editar]



El periodo de un estado x∈E se define como:

donde

denota el máximo común divisor.



Si d(x)=1 diremos que x es un estado aperiódico.



Una cadena de Márkov se dice aperiódica si todos sus estados son aperiódicos.

Tipos de cadenas de Márkov [editar] Cadenas irreducibles [editar] Una cadena de Márkov se dice irreducible si se cumple cualquiera de las siguientes condiciones (equivalentes entre sí): 1.

Desde cualquier estado de E se puede acceder a cualquier otro.

2.

Todos los estados se comunican entre sí.

3.

C(x)=E para algún x∈E.

4.

C(x)=E para todo x∈E.

5.

El único conjunto cerrado es el total.

La cadena de Ehrenfest o la caminata aleatoria sin barreras absorbentes son ejemplos de cadenas de Márkov irreducibles.

Cadenas positivo-recurrentes [editar] Una cadena de Márkov se dice positivo-recurrente si todos sus estados son positivo-recurrentes. Si la cadena es además irreducible es posible demostrar que existe un único vector de probabilidad invariante y está dado por:

Cadenas regulares [editar] Una cadena de Márkov se dice regular (también primitiva o ergódica) si existe alguna potencia positiva de la matriz de transición cuyas entradas sean todas estrictamente mayores que cero. Cuando el espacio de estados E es finito, si P denota la matriz de transición de la cadena se tiene que:

donde W es una matriz con todos sus renglones iguales a un mismo vector de probabilidad w, que resulta ser el vector de probabilidad invariante de la cadena. En el caso de cadenas regulares, éste vector invariante es único.

Cadenas absorbentes [editar] Una cadena de Márkov con espacio de estados finito se dice absorbente si se cumplen las dos condiciones siguientes: 1.

La cadena tiene al menos un estado absorbente.

2.

De cualquier estado no absorbente se accede a algún estado absorbente.

Si denotamos como A al conjunto de todos los estados absorbentes y a su complemento como D, tenemos los siguientes resultados:



Su matriz de transición siempre se puede llevar a una de la forma

donde la submatriz Q corresponde a los estados del conjunto D, I es la matriz identidad, 0 es la matriz nula y R alguna submatriz.



, esto es, no importa en donde se encuentre la cadena, eventualmente terminará en un estado absorbente.

Cadenas de Márkov en tiempo continuo [editar] Si en lugar de considerar una secuencia discreta X1, X2,..., Xi,.. con i indexado en el conjunto

de números naturales, se consideran

las variables aleatorias Xt con t que varía en un intervalo continuo del conjunto

de números

reales, tendremos una cadena en tiempo continuo. Para este tipo de cadenas en tiempo continuo la propiedad de Márkov se expresa de la siguiente manera:

tal que Para una cadena de Márkov continua con un número finito de estados puede definirse una matriz estocástica dada por:

La cadena se denomina homogénea si

. Para una

cadena de Márkov en tiempo continuo homogénea y con un número finito de estados puede definirse el llamado generador infinitesimal como:2

Y puede demostrarse que la matriz estocástica viene dada por:

Aplicaciones [editar] Física [editar] Las cadenas de Márkov son usadas en muchos problemas de la termodinámica y la física estadística. Ejemplos importantes se pueden encontrar en la Cadena de Ehrenfest o el modelo de difusión de Laplace.

Meteorología [editar] Si consideramos el clima de una región a través de distintos días, es claro que el estado actual solo depende del último estado y no de toda la historia en sí, de modo que se pueden usar

cadenas de Márkov para formular modelos climatológicos básicos.

Modelos epidemiológicos [editar] Una importante aplicación de las cadenas de Márkov se encuentra en el proceso GaltonWatson. Éste es un proceso de ramificación que se puede usar, entre otras cosas, para modelar el desarrollo de una epidemia (véase modelaje matemático de epidemias).

Internet [editar] El pagerank de una página web (usado por Google en sus motores de búsqueda) se define a través de una cadena de Márkov, donde la posición que tendrá una página en el buscador será determinada por su peso en la distribución estacionaria de la cadena.

Simulación [editar] Las cadenas de Márkov son utilizadas para proveer una solución analítica a ciertos problemas de simulación tales como el Modelo M/M/1.3

Juegos de azar [editar] Son muchos los juegos de azar que se pueden modelar a través de una cadena de Márkov. El modelo de la ruina del jugador, que establece la probabilidad de que una persona que apuesta en un juego de azar finalmente termine sin dinero, es una de las aplicaciones de las cadenas de Márkov en este rubro.

Economía y Finanzas [editar] Las cadenas de Márkov se pueden utilizar en modelos simples de valuación de opciones para determinar cuándo existe oportunidad dearbitraje, así como en el modelo de colapsos de una bolsa de valores o para determinar la volatilidad de precios. En los negocios, las cadenas de Márkov

se han utilizado para analizar los patrones de compra de los deudores morosos, para planear las necesidades depersonal y para analizar el reemplazo de equipo.

Genética [editar] Se emplean cadenas de Márkov en teoría de genética de poblaciones, para describir el cambio de frecuencias génicas en una población pequeña con generaciones discretas, sometida a deriva genética. Ha sido empleada en la construcción del modelo de difusión de Motō Kimura.

Música [editar] Diversos algoritmos de composición musical usan cadenas de Márkov, por ejemplo el software Csound o Max