Una cadena de Markov es una serie de eventos estadísticamente determinados, en la cual la probabilidad de que ocurra un evento depende del evento inmediato anterior. Estas se dice que tienen memoria. Es decir, recuerdan el último evento y al mismo tiempo condiciona las posibilidades de los eventos futuros subsecuentes. Ésta dependencia del evento anterior distingue a las cadenas de Markov de las series de eventos independientes.
En 1907, A. A. Markov comenzó el estudio de un importante nuevo tipo de cambio de proceso. En este proceso, el resultado de un experimento dado puede afectar el resultado del próximo experimento o evento. A este tipo de proceso es llamado Cadena de Markov.
Uno de los métodos usuales para exhibir las probabilidades de transición de un evento o Estado es usar una Matriz de Transición. La cual debe cumplir con las siguientes condiciones:
1. La Matriz de Transición debe sr Cuadrara, es decir debe tener el mismo número de columnas como de filas.
2. En ella deben estar contenidos tanto en las filas como en las columnas los mismos Estados o Eventos trasitorios.
3. La Suma de los elementos de cada fila debe ser siempre igual a 1, cumpliendo con la teoría de Probabilidades.
4. Cada elemento de la matriz debe ser un número entre cero y 1.
A continuación se muestra la matriz de transición:
En esta están contenidos M estados transitorios con una P de probabilidad.
Las aplicaciones de las Cadenas de Markov son muy variadas, ya que describen satisfacteriamente cualquier tipo de evento estocástico, por lo cual estas son llamadas también Estudios de Comportamiento de un Sistema. Estos durante un período dado suele ser llevar al análisis de un proceso estocástico con la siguiente estructura. En puntos específicos del tiempo t , el sistema se encuentra exactamente en una de un número finito de estados mutuamente excluyentes y exhaustivos, etiquetados 0, 1, . . , S. Los periodos en el tiempo pueden encontrarse a intervalos iguales o su esparcimiento puede depender del comportamiento general del sistema en el que se encuentra sumergido el proceso estocástico. Aunque los estados pueden constituir una caracterización tanto cualitativa como cuantitativa del sistema, no hay pérdida de generalidad con las etiquetas numéricas 0, 1, . . , M , que se usarán en adelante para denotar los estados posibles del sistema. Así la representación matemática del sistema físico es la de un proceso estocástico {Xi}, en donde las variables aleatorias se observan en t = 0, 1, 2,. . ., y en donde cada variable aleatoria puede tomar el valor de cualquiera de los M + 1 enteros 0, 1, .. , M . Estos enteros son una caracterización de los M + 1 estados del proceso.(1)
Ejemplo.
Acorde a Kennedy, Snell y Thompson, la Tierra de Oz es bendecida por muchas cosas pero no por un buen clima. Ellos nunca tienes dos buenos días seguidos. Si ellos tienen un buen día, probablemente tendrán nieve o lluvia al siguiente. Si hay un cambio de lluvia o nieve, solamente la mitad de las veces es para cambiar a un buen día. Con esta información formamos una Cadena de Markov como la que sigue. Tomando como estados los diferentes tipos de clima R (lluvia), S (Snow) y N (normal). Con lo anterior se determina la matriz de transición de probabilidades.
Consideramos la mayoría de las veces la pregunta de determinar la probabilidad que, dada la cadena en un estado i hoy, esta llegue a un estado j dos días después. Normalmente esta probabilidad es denotada por
En el ejemplo planteado, vemos que si llueve hoy el evento que nevara dos días después es la unión separada de los siguientes tres eventos: 1) llueve mañana y neva dos días desde hoy; 2) es un buen día mañana y neva dos días después de hoy, y 3) neva hoy y también dos días después de hoy. La probabilidad del primero de estos eventos es el producto de la probabilidad condicional que llueva mañana, dado que llueve hoy, y la probabilidad condicional de que neve pasado mañana, dado que llueve hoy. Usando la matriz de transición P podemos escribir este producto como: Los otros dos eventos también tienen probabilidades que pueden ser escritas como productos de las entradas de P. Así, tendremos que:
Para se plantea el siguiente teorema para probar lo observado anteriormente.
Teorema 1. Sea P la matriz de transición de una Cadena de Markov. La ij-ésimo entrada Pij^(n) de la matriz P^(n) da la probabilidad que la Cadena de Markov, comenzando en un estado inicial i esté en otro j después de n pasos.
Considerando de nuevo el ejemplo anterior de la Tierra de Oz, sabemos que el poder de la matriz de transición nos brinda información de interés acerca del proceso. Estaremos particularmente interesados en el estado de la cadena después de un largo número de pasos. Para ello es de gran utilidad utilizar cualquier programa que permita estos cálculos iterativos, entre ellos la hoja de cálculo EXCEL.
Tendremos por ejemplo después de 6 pasos lo siguiente:
Teorema 2. Sea P la matriz de transición de una Cadena de Markov y sea u el vector probabilidad el cual representa la distribución inicial de cada uno de los estados. Entonces la probabilidad de que la cadena esté en el estado i después de n pasos es la i-ésima en el vector:
Además de ello, notamos que si queremos examinar el comportamiento de la cadena bajo el supuesto que comienza en un estado inicial i, simplemente se escoge u siendo este el vector de probabilidad con la i-ésima entrada igual a 1 y todas las otras igual a cero.
Ejemplo.
Siguiendo con el ejemplo de la Tierra de Oz, hacer el vector probabilidad inicial u igual (1/3,1/3,1/3). Entonces podremos calcular la distribución de los estados después de tres días usando el teorema 2 y nuestro cálculo previo de P^3, con lo cual obtenemos:
Visualicemos otro claro ejemplo de las aplicaciones de las cadenas de Markov:
Teniendo en cuenta el vector de Estados iniciales que describen el comportamiento de los abonados a las marcas de telefonía celular Movistar, Tigo y Comcel, y la matriz de transición dada, determine el estado estable para este sistema, modelando el problema como una cadena de Markov.
Donde:
M: Movistar
T: Tigo
C: Comcel
P0: Período inicial
Se establecen los estados en los diferentes cambios de período, para ello se utilizará la hoja de cálculo de Excel que facilitará el desarrollo del ejercicio por iteraciones.
Sabemos que el cambio de período se determina multiplicando el vector de estado con la matriz de transición así:
Tendremos entonces que:
Como podemos apreciar en Estado estable no hay cambias significativos en los resultados entre períodos, por lo cual siempre permanecerán en dicho estado.
Otra manera de conseguir dicho estable es apartir de resolución de ecuaciones por cualqueir método algebráico, entre ellos el de Gauss-Jordan. Esto consiste en establecer un sistema de ecuaciones que describa la situación problema. Tendremos a partir del vector de períodos como incógnitas y la matriz de transición dada que:
Multiplicando ambas matrices nos quedará el siguiente sistema:
Sumado a estas se consigna la sumatoria de las 3 incógnitas a partir de la teoría de la probabilidad, esto es:
Tendremos entonces un sistema de ecuaciones 4x3 que puede ser resuelto por cualquier método. Utilizando Excel tendremos que:
Como podemos apreciar se ha conseguido el estado estable directamente sin iterar. Este es otro método para hallar dicho estado.
Entre los conceptos más importantes tenemos lo que se conoce como estados Recurrentes que son aquellos que si después de haber entrado, el proceso definitivamente regresará a este. Por consiguiente un Estado es Recurrente si y sólo si no es transitorio. Además, ya que un estado Recurrente será visitado de nuevo de cada visita, podría ser visitado un número infinito de veces si el proceso continúa por siempre.
Si el proceso entra a cierto estado y permanece en este estado al siguiente paso, se considera un regreso a este estado. Entonces, el siguiente tipo de estado se considera un tipo especial de estado recuerrente, el Estado Absorbente.
Un estado se llama Absorbente, si después de haber estrado en él, el proceso nunca saldrá de este. Por consiguiente, el estado i es un estado absorbente si y sólo si Pij=1.
CADENAS DE MARKOV ABSORBENTE (ABSORBING MARKOV CHAIN)
Un estado inicial i de una cadena de Markov es llamado Absorbente si es imposible dejarlo (por ejemplo Pii=1). Una Cadena de Markov es absorbente si ésta tiene al menos un estado absorbente y si desde todos los estados es posible llegar a dicho estado (no necesariamente en un paso).
Ejemplo:
Almacenes Juanchi´s vende partes de automóviles y camiones a empresas que cuentan con flotas. Cuan las empresas compran a Juanchi´s se le dan 3 meses para pagar si las cuentas no se saldan en ese período, Juanchi´s cancela la cuenta, la remite a una agencia de cobranzas y da por terminadas las transacciones. Por lo tanto Juanchi´s clasifica sus cuentas en nuevas, de un mes de retraso, de dos meses de retraso, de tres meses de retraso, pagadas e incobrables. Juanchi´s investigó sus antiguos recursos y descubrió que:
a) 70% de las cuentas nuevas se pagan en un mes.
b) 60% de las cuentas de 1 mes de retraso se liquidan al final de mes.
c) 50% de las cuentas con 2 meses de retraso se pagan al final de ese último mes.
d) 60% con 3 meses de retraso se remiten a una agencia de cobranza.
1. Forme la matriz de transición con estos datos.
2. ¿Cuál es la probabilidad de una que una cuenta nueva se liquide?
3. ¿Cuál es la probabilidad de que una cuenta con 1 mes de retraso se convierta en incobrable?
4. ¿En cuántos meses debe esperar Juanchi´s para que un cliente nuevo promedio liquidara su cuenta?
5. Si las ventas de Juanchi´s son en promedio US$125000/mes, ¿cuánto dinero se aceptaría como deuda incobrable al mes y cada año?
En primera instancia se plantea a continuación la matriz:
Se debe ahora considerar las matrices absorbente y no absorbe, así como la identidad
Además de ello, se debe tener en cuenta,
A partir de la anterior matriz podemos hallar la matriz fundamental para conseguir las probabilidades, para esto hallamos la matriz inversa de (N - I) por la matriz absorbente, obteniendo las probabilidades de ocurrencia de cada estado contenido en la matriz de no absorbente.
Ahora multiplicamos por la matriz absorbente así:
Con lo cual obtenemos las probabilidades para cada uno de los estados para llegar a cada uno de los estados absorbentes:
2. La probabilidad de que una cuenta nueva se liquide es
96%.
3. La probabilidad de que una cuenta de 1 mes de retraso se convierta en inconbrable es
12%.
4. El tiempo que se espera para que un cliente nuevo promedio liquidara su cuenta está dado por la suma de las probabilidades de la matriz (N - I) inversa, correspondiente a la primera fila. Esto es:
Sumando tendremos que este tiempo en meses es
1+ 0.3 + 0.12 + 0.06 = 1.48 meses.
5. El dinero que se aceptará como deuda incobrable es de:
REFERENCIAS.
(1) Tutorial de Investigación de Operaciones II. Markov Chain. [En línea] [PDF] [Disponible en:
(2) GONZÁLEZ, Medardo. Clase Presencial. Investigación de Operaciones II . Universidad del Atlántico. Mayo de 2011.
