CADENAS DE MARKOV

Tabla de Contenido Resumen.4 Introduccin...5 Concepto de un proceso estocstico .6 Definiciones de cadenas de Markov..8 Matriz de transicin...9 Clases de cadenas de Markov..13 Cadenas Irreductibles.13 Cadenas positivo-recurrentes.13 Cadenas de Markov en tiempo contino....13 Cadenas absorbentes..14 Cadenas ergdicas o irregulares....15 Cadenas Semiergdicas.15 Cadenas no ergdicas....16 Cadenas cclicas.17

Ejemplos..19 Ejemplo 1..19 Ejemplo 2...21 Ejemplo 3.......23 Ejemplo 4...24 Conclusin...28 Bibliografa..29

CADENAS DE MARKOV

Resumen

En la teora de la probabilidad, se conoce como cadena de Mrkov a un tipo especial de proceso estocstico 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 Mrkov de las series de eventos independientes, como tirar una moneda al aire o un dado. Reciben su nombre del matemtico ruso Andrei Andreevitch Markov (1856-1922), que las introdujo en 1907 Abstract In probability theory, known as Markov chain to a special type of discrete stochastic process in which the probability of an event depends on the event immediately preceding. Indeed, this type chains have memory. "Remember" the last event and this affects the possibilities for future events. This dependence of the previous event distinguishes Markov chains series of independent events, such as a coin toss or a dice. They get their name Andreevitch Russian mathematician Andrei Markov (1856-1922), who introduced them in 1907 Palabras Claves Estocstico, Cadena de Markov, Matriz de transicin.

CADENAS DE MARKOV

Instruccin En el presente trabajo hablaremos sobre las cadenas de Markov, en donde antes de definir este concepto encontraremos la estrecha relacin que tiene con el proceso estocstico, el cual es entendido como una sucesin de variables aleatorias que evolucionan en funcin de otra variable, es decir, cada variable o conjunto de variables sometidas a impactos aleatorios constituirn este proceso de acuerdo al tiempo. Entonces, la cadena de Markov ser entendida como un tipo especial de procesos estocsticos de tiempo discreto, la caracterstica principal es que los estados futuros son independientes de los ltimos estados y las probabilidades no son las mismas de acuerdo a la distribucin. El campo de aplicacin de las cadenas de Markov es amplio, es utilizada en el proceso industrial de fabricacin de tejas, en los negocios para analizar los patrones de compra de los deudores, para planear las necesidades de personal, para analizar el reemplazo de equipo, entre otros. Tambin se usa en disciplinas como la fsica, ingeniera, biologa, medicina y otras ramas de la matemtica. Los temas que se presentan a continuacin nos describirn el proceso de las cadenas con la ayuda de los ejemplos que se desarrollarn ms adelante.

CADENAS DE MARKOV

Cadenas de Markov

Concepto de un Proceso Estocstico Es un proceso o sucesin de eventos que se desarrolla en el tiempo en el cual el resultado en cualquier etapa contiene algn elemento que depende del azar. Frederick & Liberman (9a Ed), introduccin a la investigacin de operaciones, pag 673, Nos afirma que Es una coleccin indexada de variables aleatorias {Xt}, donde el ndice t toma valores de un conjunto T dado. Con frecuencia T se considera el conjunto de enteros no negativos mientras que Xt representa una caracterstica de inters cuantificable en el tiempo t. Por ejemplo, Xt puede representar los niveles de inventario al final de la semana t. Ejemplo: La tienda de fotografa de Dave tiene el siguiente problema de inventario. El negocio tiene en almacn un modelo especial de cmara que se puede solicitar cada semana. Sean D1, D2, . . . representan las demandas respectivas de esta cmara (el nmero de unidades que se venderan si el inventario no se agota) durante la primera, segunda semanas, . . ., respectivamente, entonces, la variable aleatoria Dt (para t = 1, 2, . . .) es Dt = nmero de cmaras que se venderan en la semana t si el inventario no se agota. (Este nmero incluye las ventas perdidas cuando se agota el inventario). Se supone que las Dt son variables aleatorias independientes e idnticamente distribuidas que tienen una distribucin Poisson con media de 1. Sea X0 el nmero de cmaras que se tiene en el momento de iniciar el proceso, X1 el nmero de cmaras que se tienen al final de la semana 1, X2 el nmero de cmaras al final de la semana 2, etc., entonces la variable aleatoria Xt (para t = 0, 1, 2, . . .) es

CADENAS DE MARKOV

Xt = nmero de cmaras disponibles al final de la semana t. Suponga que X0 = 3, de manera que la semana 1 se inicia con tres cmaras a mano. {Xt} = {X0, X1, X2,. . .} Es un proceso estocstico donde la variable aleatoria Xt representa el estado del sistema en el tiempo t, a saber Estado en el tiempo t = nmero de cmaras disponibles al final de la semana t. Como propietario de la tienda, Dave deseara aprender ms acerca de cmo evoluciona este proceso estocstico a travs del tiempo mientras se utilice la poltica de pedidos actual que se describe a continuacin. Al final de cada semana t (sbado en la noche), la tienda hace un pedido que le entregan en el momento de abrir la tienda el lunes. La tienda usa la siguiente poltica para ordenar: Si Xt = 0, ordena 3 cmaras. Si Xt > 0, no ordena ninguna cmara. En consecuencia, el nivel de inventarios flucta entre un mnimo de cero y un mximo de tres cmaras, por lo que los estados posibles del sistema en el tiempo t (al final de la semana t) son Estados posibles = 0, 1, 2, o 3 cmaras disponibles. Como cada variable aleatoria Xt (t = 0, 1, 2, . . .) representa el estado del sistema al final de la semana t, sus nicos valores posibles son 0, 1, 2, 3. Las variables aleatorias Xt son dependientes y se pueden evaluar en forma iterativa por medio de la expresin Xt + 1 { { { } }

Para t = 0, 1, 2, . . .

CADENAS DE MARKOV

Definiciones de Cadena de Markov Las cadenas de Markov son una herramienta para analizar el comportamiento y el gobierno de determinados tipos de procesos estocsticos, esto es, procesos que evolucionan de forma no determinstica a lo largo del tiempo en entorno a un conjunto de estados. Por tanto, representa un sistema que vara su estado a lo largo del tiempo. Siendo cada cambio una transicin del sistema. Dichos cambios no estn predeterminados, aunque s lo est la probabilidad del prximo estado en funcin de los estados, probabilidad que es constante a lo largo del tiempo (sistema homogneo en el tiempo). Eventualmente, es una transicin, el nuevo estado puede ser el mismo que el anterior y es posible que exista la probabilidad de influir en las probabilidades de transicin actuando sobre el sistema (decisin).
http://investigaciondeoperaciones2.wordpress.com

Una cadena de Markov es una sucesin de ensayos similares u observaciones en la cual cada ensayo tiene el mismo nmero finito de resultados posibles y en donde la probabilidad de cada resultado para un ensayo dado depende slo del resultado del ensayo inmediatamente precedente y no de cualquier resultado previo.

Esta consta de unos estados E1 E2 E3 E4..En. que inicialmente en un tiempo 0 o paso 0 que se le llama estado inicial, adems de esto consta de una matriz de transicin que significa la posibilidad de que se cambie de estado en un prximo tiempo o paso.

CADENAS DE MARKOV

Matriz de Transicin Una matriz de transicin para una cadena de Markov de n estado es una matriz de n X n con todos los registros no negativos y con la propiedad adicional de que la suma de los registros de cada columna (o fila) es 1. Por ejemplo: las siguientes son matrices de transicin.

Representacin grfica de una matriz de transicin: Es el arreglo numrico donde se condensa las probabilidades de un estado a otro. A travs de una grfica de matriz de transicin se puede observar el comportamiento estacionario representado por una cadena de Markov tal que los estados representan la categora en que se encuentre clasificado. Como se aprecia a continuacin:

PROPIEDADES: 1- la suma de las probabilidades de los estados debe ser igual a 1. 2- la matriz de transicin debe ser cuadrada.

CADENAS DE MARKOV

3- las probabilidades de transicin deben estar entre 0 y 1. Ejemplo: El comportamiento de cambo de marca de los consumidores h sido modelado como una cadena de Markov, para ayudar a desarrollar las estrategias de mercadotecnia. A manera de ejemplo, obsrvese el siguiente comportamiento de cambio de marca descrito en la siguiente tabla para una muestra de 250 consumidores de un producto. Nmero de consumidores que cambian la marca i en la semana 6 j en la semana 7.

El primer rengln indica que, de 80 personas que compraron la marca 1 en la semana 6, 72 volvieron a adquirirla en la semana 7, 4 prefirieron la marca 2 y 4 la marca 3. Sin embargo, ntese que 12 personas cambiaron la marca 2 por la marca 1 y 2 personas cambiaron la marca 3 por la marca 1. A si pues, para la marca 1, la prdida de 8 clientes se compens con creces por la conquista de 14 clientes. Entre la sexta y la sptima semanas, la marca 1 aument su participacin en el mercado de 32%(80/250) a 34,4% (86/250). La matriz de probabilidades de transicin para la tabla de contingencia es P:

CADENAS DE MARKOV

La matriz P es una estimacin de la matriz verdadera, pues solamente representa el comportamiento de una muestra de 250 consumidores, durante a un periodo de dos semanas. Los elementos P11, P22 y P33 de la matriz P son medidas del poder de retencin de las tres marcas; los restantes elementos Pij reflejan el poder de atraccin de la marca j, suponiendo que la compra anterior haya sido a favor de la marca i. Los elementos de cada fila reflejan la probabilidad de que una marca retenga a sus clientes o los pierda frente a otras marcas. Los elementos de cada columna resumen la probabilidad de que una marca retenga a sus clientes o conquiste a otros a costa de cada marca de la competencia. Suponiendo que la participacin en los mercados que tienen la tres marcas del ejemplo son 30%, 38% y 32&, respectivamente, durante la sptima semana. Si la matriz de transicin P (maestral), se considera una buena estimacin de la verdadera matriz de transicin (poblacional), es posible predecir las participaciones de mercado esperada en la octava semana por medio de la multiplicacin de matrices. As entonces:

Las participaciones en el mercado predichas durante la octava semana son 32,08%, 37,64% y 30,28%, respectivamente para la tres marcas. Generalizando, podemos decir que si un proceso de Markov donde el sistema puede encontrarse en cualquiera de m estados posibles, las probabilidades pueden escribirse por medio del vector X=(x1 x2..xn) donde xj representa probabilidad de que el sistema se halle en el

CADENAS DE MARKOV

10

estado j. En los estados actuales de un proceso de Markov Xk, los estados despus del siguiente experimento (transicin) pueden calcularse mediante la multiplicacin con de matrices. Xk+1 = X k P Con base en la ecuacin anterior se puede afirmar que:

Generalizando:

Ya que en este caso X0 corresponde al vector X7.

Fraleigh, John. Algebra Lineal. Editorial Addison Wesley.1989.

CADENAS DE MARKOV

11

Clases de Cadenas de Markov Cadenas irreducibles Una cadena de Markov 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 algn xE. 4. C(x)=E para todo xE. 5. El nico conjunto cerrado es el total. La cadena de Ehrenfest o la caminata aleatoria sin barreras absorbentes son ejemplos de cadenas de Markov irreducibles. Cadenas positivo-recurrentes Una cadena de Markov se dice positivo-recurrente si todos sus estados son positivorecurrentes. Si la cadena es adems irreducible es posible demostrar que existe un nico vector de probabilidad invariante y est dado por: Cadenas de Markov en tiempo continuo Si en lugar de considerar una secuencia discreta X1, X2,..., Xi,.. Con i indexado en el conjunto de nmeros naturales, se consideran las variables Aleatorias Xt con t que vara en un de nmeros reales, tendremos una cadena en tiempo continuo.

intervalo continuo del conjunto

Para este tipo de cadenas en tiempo continuo la propiedad de Markov se expresa de la siguiente manera:

Tal que

CADENAS DE MARKOV

12

Para una cadena de Markov continua con un nmero finito de estados puede definirse una matriz estocstica dada por:

La cadena se denomina homognea si

. Para una cadena de

Markov en tiempo continuo homognea y con un nmero finito de estados puede definirse el llamado generador infinitesimal como:

Y puede demostrarse que la matriz estocstica viene dada por:

Cadenas absorbentes Una cadena de Markov 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 algn 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 transicin siempre se puede llevar a una de la forma

CADENAS DE MARKOV

13

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 ergdicas o regulares La cadena de Markov C1, de dos estados, tiene la matriz de probabilidades de transicin:

Calculemos la potencia decimosexta de esa matriz para aproximar la matriz de probabilidades estacionarias:

Se observa que las probabilidades de estado estable de los diferentes estados son independientes del estado de origen, razn por la que la matriz de probabilidades. Estacionarias tiene todas las filas iguales. Tenemos entonces una cadena de Markov regular en la que las probabilidades estacionarias no dependen del estado inicial. Adems, ninguna de las probabilidades vale cero. Tenemos entonces una cadena de Markov ergdica. Cadenas Semirgodicas Tenemos ahora una cadena de C2 de cuatro estados, de matriz de probabilidades de transicin.

CADENAS DE MARKOV

14

Si se observa la matriz de la transicin decimosexta, se observa como todas las filas tienden a ser iguales (aunque no completamente, especialmente las dos primeras), con una diferencia respecto de las cadenas ergdicas: existen estados cuya probabilidad de estado estable tiende a ser cero (esto es, que no aparecern den el comportamiento a largo plazo). Por lo tanto, no se trata de una cadena ergdica. Sin embargo, sigue siendo cierto que todas las filas tienden hacia un mismo valor, por lo que sigue siendo regular. Las cadenas de Markov regulares (y tambin otras que veremos ms adelante) con algunas de las columnas de la matriz de probabilidades estacionarias igual a cero se llaman semiergdicas. Las cadenas ergdicas pueden considerarse como un caso particular de las cadenas semiergdicas, en las que no existen probabilidades de estado iguales a cero.

Cadenas no ergdicas La cadena C3, de cuatro estados, tiene la siguiente matriz de transicin:

Si observamos la matriz de la transicin 16, podemos ver que, mientras algunas filas tienen el

CADENAS DE MARKOV

15

mismo comportamiento que las de los casos anteriores, vemos que otras tienden a ciertos valores, diferentes de los de las otras filas. Ello quiero decir que, al contrario de lo que sucede con el caso regular, las probabilidades de estado estable si dependen de cul ha sido el estado inicial de la cadena. Se trata de una cadena semirregular

Cadenas Cclicas La cadena C4, cuya matriz de probabilidades de transicin se muestra a continuacin, despus de un nmero elevado de transiciones presenta un comportamiento diferente del de las cadenas anteriores.

Al ir obteniendo matrices de transicin, se observa que estas no convergen a un valor concreto, sino que muestran un comportamiento cclico. En este caso, las transiciones impares tienden a un valor y las pares a otro.

CADENAS DE MARKOV

16

Este tipo de cadenas son cadenas son cadenas cclicas. En este caso particular, nos encontramos ante una cadena de periodo p=2. La columna es siempre cero, por lo que el estado I no aparecer en las probabilidades a largo plazo; quiere ello decir que la cadena considerada no es ergdica, aunque es claro que pueden existir cadenas cclicas ergdicas. Tambin debemos preguntarnos qu ocurre con las probabilidades estacionarias en las cadenas cclicas, ya que si las sucesivas potencias de P no tienden hacia unos valores determinados. Ms adelante, cuando estudiamos el clculo sistemtico de P*.

CADENAS DE MARKOV

17

Ejemplos Ejemplo 1 En un pas como Colombia existen 3 operadores principales de telefona mvil como lo son tigo, Comcel y movistar (estados). Los porcentajes actuales que tiene cada operador en el mercado actual son para tigo 0.4 para Comcel 0.25 y para movistar 0.35. (Estado inicial). Se tiene la siguiente informacin un usuario actualmente de tigo tiene una probabilidad de permanecer en tigo de 0.60, de pasar a Comcel 0.2 y de pasarse a movistar de 0.2; si en la actualidad el usuario es cliente de Comcel tiene una probabilidad de mantenerse en Comcel del 0.5 de que esta persona se cambie a tigo 0.3 y que se pase a movistar de 0.2; si el usuario es cliente en la actualidad de movistar la probabilidad que permanezca en movistar es de 0.4 de que se cambie a tigo de 0.3 y a Comcel de 0.3. Partiendo de esta informacin podemos elaborar la matriz de transicin

La suma de las probabilidades de cada estado en este caso operador deben ser iguales a 1 Po= (0.4 0.25 0.35) estado inicial

CADENAS DE MARKOV

18

Tambin se puede mostrar la transicin por un mtodo grafico

Ahora procedemos a encontrar los estados en los siguientes pasos o tiempos, esto se realiza multiplicando la matriz de transicin por el estado inicial y as sucesivamente pero multiplicando por el estado inmediatamente anterior.

Como podemos ver la variacin en el periodo 4 al 5 es muy mnima casi insignificante podemos decir que ya se ha llegado al vector o estado estable.

CADENAS DE MARKOV

19

Ejemplo 2 Suponga que en el mercado se consiguen 3 tipos de gaseosas colas que son: coca cola, Pepsi cola y big cola cuando una persona a comprado coca cola existe una probabilidad de que la siga consumiendo de el 75%, un 15% de que compre Pepsi cola y un 10% de que compre big cola; cuando el comprador actualmente consume Pepsi existe una probabilidad de que la siga comprando de 60%, un 25% que compre coca cola y un 15% big cola; si en la actualidad consuma big cola la probabilidad de que la siga consumiendo es del 50%, un 30% que compre coca cola y 205 pepsi cola. En la actualidad cada marca coca cola, Pepsi y big cola tienen los siguientes porcentajes en participacin en el mercado respectivamente (60% 30% 10%)

Elaborar la matriz de transicin Hallar la probabilidad que tiene cada marca en el periodo 5

Matriz de transicin

CADENAS DE MARKOV

20

Entonces

CADENAS DE MARKOV

21

Ejemplo 3 La cervecera ms importante del mundo (Guiness) ha contratado a un analista de investigacin de operaciones para analizar su posicin en el mercado. Estn preocupados en especial por su mayor competidor (Heineken). El analista piensa que el cambio de marca se puede modelar como una cadena de Markov incluyendo tres estados, los estados G y H representan a los clientes que beben cerveza producida por las mencionadas cerveceras y el estado I representa todas las dems marcas. Los datos se toman cada mes y el analista ha construido la siguiente matriz de transicin de los datos histricos.

Cules son los porcentajes de mercado en el estado estable para las dos cerveceras grandes?

CADENAS DE MARKOV

22

Solucin Tres estados {G, H, I} El problema consiste en resolver el sistema formado por las ecuaciones siguientes: (x, y, z).P (x, y, z); x y z 1, siendo x la probabilidad de que el consumidor compre G, y de que el consumidor compre H y z la del que consumidor compre I. De ambas expresiones se obtiene el siguiente sistema:

Ejemplo 4 Almacenes xito, Carrefour y Sao han investigado la fidelidad de sus clientes y han encontrado los siguientes datos: E1: xito E2: Carrefour E3: Sao Hallar el estado estable (L)

CADENAS DE MARKOV

23

CADENAS DE MARKOV

24

CADENAS DE MARKOV

25

CADENAS DE MARKOV

26

Conclusin

En conclusin podemos decir que las cadenas de Markov son una herramienta de gran ayuda mediante para la solucin de problemas de la vida diaria, ya que podemos encontrar su implementacin en los juegos de azar, en los algoritmos para la composicin musical, en la medicina para modelar el desarrollo de una epidemia, en la formulacin de modelos climatolgicos y hasta en internet en el uso de una pgina web. Esta herramienta nos es de gran ayuda para todos los ingenieros industriales, ya que nos facilita la toma de decisiones, ya que nos permite analizar los riesgos, agilizar los procesos y ayudar a mejorar los planes trazados.

CADENAS DE MARKOV

27

Bibliografa

Hillier, Frederick S & Liberman, Gerald J.; Introduccin a la Investigacin de Operaciones; Editorial McGraw Hill; 9a Edicin (2010). Wayne L. Winston; Investigacin de operaciones aplicaciones y algoritmos; Editorial Thomson; 4a Edicin (2004) http://www.slideshare.net http://investigaciondeoperaciones2.wordpress.com Joan B. Fonollosa Jos M. Sallan, Albert Su; Mtodos cuantitativos de organizacin industrial II Elmer B. Mode; Elementos de Probabilidad y Estadstica http://materias.fi.uba.ar/6615/Material/markov.pdf
http://www.buenastareas.com

http://invoperacionesid2.blogspot.com/2011/06/cadenas-de-markov.html http://www.bioingenieria.edu.ar