distribución estacionaria Archivos - Gestión de Operaciones

Distribución Estacionaria de una Cadena de Markov en Tiempo Continuo

En la Teoría de Probabilidades, una Cadena de Markov en Tiempo Continuo (CTMC – Continuous Time Markov Chain) corresponde a un modelo matemático donde una variable aleatoria toma valores en un espacio finito y donde el tiempo en que la variable se encuentra en un determinado estado adopta valores reales no negativos que siguen una Distribución Exponencial. Dicha característica denominada Propiedad de No Memoria determina que el comportamiento a futuro del proceso estocástico depende sólo del estado actual y no del comportamiento histórico de dicha variable.

En este contexto a continuación presentamos un ejemplo del cálculo de una Distribución Estacionaria o de Largo Plazo para una Cadena de Markov en Tiempo Continuo. Nuestro objeto de análisis en términos intuitivos es similar al caso de la Distribución Limite de una Cadena de Markov en Tiempo Discreto, es decir, estimar en el largo plazo (e independiente de la distribución inicial) cuál es la probabilidad que el proceso estocástico se encuentre en uno de los N estados posibles.

Distribución Estacionaria Cadena de Markov en Tiempo Continuo

Aves arriban a uno de los 4 alimentadores (comederos) ubicados en el patio de una casa de acuerdo a un Proceso de Poisson con tasa promedio de un ave por minuto. Si todos los alimentadores (4 en total) están ocupados, el ave se va sin esperar que un alimentador se desocupe y en caso contrario el ave come de un alimentador por un tiempo determinado que sigue una Distribución Exponencial con media de un minuto. Se desea modelar la cantidad de alimentadores o comederos ocupados $X(t)$ a través de una Cadena de Markov en Tiempo Continuo.

Sea $X(t)$ la variable aleatoria que representa el número de alimentadores ocupados. En este contexto $X(t)$ representa el número de entidades presentes en los alimentadores en el instante t, cuyo tamaño aumenta con la llegada (nacimiento) de entidades (aves) o disminuye con la salida (muerte) de entidades (aves).

Al existir 4 alimentadores, la cantidad de éstos que se pueden encontrar ocupados en un instante del tiempo son 0, 1, 2, 3 o 4, ( $X(t)\in\begin{Bmatrix}0,1,2,3,4\end{Bmatrix}t\geq 0$ ) según se representa en el diagrama de transición a continuación:

Los valores en las flechas que unen los estados 0 con el 1, 1 con el 2, 2 con el 3 y 3 con el 4, corresponden a la tasa de llegada λ (tasas de nacimiento) que en este caso corresponde a $\lambda_{i}=1[\frac{ave}{minuto}]$ para todo i.

Por otro lado las tasas de servicio (salida o muerte) µ corresponderán a $\mu_{i}=i\mu$ , de modo que de esta forma se obtienen las tasas indicadas en la parte inferior del diagrama en aquella transiciones que consisten en disminuir el número de alimentadores ocupados. Notar que en este caso $\mu=1[\frac{ave}{minuto}]$ .

La cadena propuesta es claramente irreducible (es decir, todos los estados se comunican entre sí y existe por tanto una única clase de estados), de modo que podemos estimar una distribución estacionaria o de largo plazo. En este sentido la ecuación correspondiente es:

Donde por cierto $\sum\pi _{i}=1$ . La Matriz General G, que tiene como característica que la sumatoria de los valores en sus respectivas filas corresponde a cero, a su vez queda definida por:

De este modo se obtiene el siguiente sistema de ecuaciones:

La solución del sistema corresponde a:

Que representa para cada estado la proporción del tiempo (en el largo plazo) que cada uno de ellos se encontrará ocupado, por ejemplo, se espera que en el 36,92% del tiempo no se encuentren alimentadores (comederos) ocupados.

Los resultados anteriores han sido corroborados haciendo uso de una planilla de Simulación de Sistemas de Espera disponible en el Libro Investigación de Operaciones de H. Taha. Notar que se ha establecido un límite de 4 entidades (en este caso aves) para el sistema:

El número de alimentadores ocupados en el largo plazo son:

Se concluye que en el largo plazo se encuentren ocupados 0,9845 comederos. Cabe destacar que según el resultado de la simulación anterior $L_{s}=0,98462$ y por cierto la diferencia respecto a nuestro resultado obedece exclusivamente a la cantidad de decimales utilizados para la estimación.

Preguntas Frecuentes de Cadenas de Markov

Una Cadena de Markov en tiempo discreto consiste en una clase particular de un proceso estocástico donde se verifica el cumplimiento de la propiedad markoviana (en términos simples establece que el futuro es independiente del pasado dado el presente) y la propiedad estacionaria (la probabilidad de transición de un estado i a un estado j al cabo de una etapa no depende de la etapa n). En este contexto a continuación presentamos 3 preguntas de selección múltiple que permite reforzar algunos conceptos básicos sobre las Cadenas de Markov.

Pregunta N°1: En la matriz de probabilidades de transición:

a) La suma de cada columna debe ser igual a 1
b) La suma de cada columna y cada fila debe ser igual a 1
c) Por lo menos debe haber un 0 en cada fila
d) La suma de cada fila debe ser igual a 1
e) Por lo menos debe haber un 0 en cada columna

Respuesta: Alternativa d). La matriz de probabilidades de transición o matriz P resume las probabilidad de transición en una etapa de un estado i a un estado j. La matriz P tiene la misma cantidad de filas y columnas. Por ejemplo a continuación de presenta la matriz de transición que corresponde a uno de los casos discutidos en el artículo Cadenas de Markov (Ejercicios Resueltos) donde se corrobora que la sumatoria de los valores de cada fila corresponde a un 100%.

Pregunta N°2: Si la distribución de probabilidad de la variable $X_{n}$ no cambia de una etapa a otra:

a) Cada probabilidad debe ser igual a 1
b) Debe haber al menos una probabilidad igual a 0
c) La probabilidad debe ser la misma para cada estado
d) Dicha distribución coincide con la distribución estacionaria
e) Debe haber al menos una probabilidad igual a 1

Respuesta: Alternativa d). En este caso estamos frente a la distribución estacionaria o de largo plazo la cual como hemos discutido previamente es independiente de la distribución inicial para la variable aleatoria. Antecedentes adicionales y un ejemplo con el detalle del cálculo se puede consultar en Distribución Límite de una Cadena de Markov en Tiempo Discreto.

Pregunta N°3: Cuál de las siguientes alternativas no es un supuesto de las cadenas de Markov:

a) Existe un número finito de estados
b) Existe un número finito de etapas
c) Las probabilidades de la variable de estado $X_{n}$ se pueden calcular usando únicamente la matriz de probabilidades de transición
d) La distribución de probabilidades de una etapa no cambia de una etapa a la otra
e) Todas la anteriores no son supuestos del análisis

Respuesta: Alternativa e). Se descarta a) y b) debido a que puede existir un número infinito de estados y etapas. En cuanto a las probabilidades de la variable de estado $X_{n}$ , se requiere conocer una distribución de estado actual o inicial para que luego, haciendo uso de las ecuaciones matriciales se pueda estimar las probabilidades de estado.

Cadenas de Markov (Ejercicios Resueltos)

Un proceso estocástico en tiempo discreto se denomina una Cadena de Markov en tiempo discreto si y solo sí se satisface la Propiedad Markoviana (esto es básicamente que el futuro t=n+1 es independiente del pasado dado el presente t=n) y Propiedad Estacionaria (la probabilidad de pasar de un estado i a un estado j al cabo de una etapa no depende de la etapa n). A continuación presentamos un conjunto de problemas resueltos de Cadenas de Markov que sirvan de complemento para los estudios de nuestros usuarios.

Ejercicios Resueltos de Cadenas de Markov

Ejercicio N°1: Una empresa esta considerando utilizar Cadenas de Markov para analizar los cambios en las preferencias de los usuarios por tres marcas distintas de un determinado producto. El estudio ha arrojado la siguiente estimación de la matriz de probabilidades de cambiarse de una marca a otra cada mes:

Si en la actualidad la participación de mercado es de 45%, 25% y 30%, respectivamente. ¿Cuales serán las participaciones de mercado de cada marca en dos meses más?.

En primer lugar definimos la variable aleatoria $X_{n}$ que representa la marca que adquiere un cliente cualquiera en el mes n. Dicha variable aleatoria puede adoptar los valores 1,2,3 en el mes n=0,1,2,3,..

Adicionalmente conocemos cuál es la distribución inicial y la matriz de probabilidades de transición en una etapa tal como se observa a continuación:

Luego para conocer la distribución de las participaciones de mercado al cabo de 2 meses (2 etapas) podemos utilizar la fórmula $f^{n}=P^{T}*f^{n-1}$ :

Se concluye que las cuotas de mercado (participaciones de mercado) en dos meses a cambiado de un 45% a un 40.59%; de un 25% a un 33.91% y de un 30% a un 25.50%, para las marcas 1,2 y 3 respectivamente.

Ejercicio N°2: ¿Cuál es la cuota de mercado en el largo plazo para cada una de las marcas descritas en el Ejercicio N°1?.

La Cadena de Markov del Ejercicio N°1 es irreducible (es decir todos los estados se comunican entre sí) con estados recurrentes positivos y aperiódicos. Lo anterior se concluye luego de la Clasificación de Estados de una Cadena de Markov en Tiempo Discreto. Verificado lo anterior podemos obtener la Distribución Límite de una Cadena de Markov en Tiempo Discreto a través del siguiente sistema de ecuaciones:

La solución del sistema corresponde a: $\pi _{1}=0,2373$ , $\pi _{2}=0,6184$ y $\pi _{3}=0,1443$ , que representan las cuotas de mercado en el largo plazo para las marcas 1,2 y 3, respectivamente. Notar que las actuales participaciones de mercado difieren significativamente de las cuotas obtenidas en el largo plazo lo cual sugiere que de alguna manera deban ser corregidas las probabilidades de transición.

Ejercicio N°3: En una Unidad de Cuidados Intensivos en un determinado hospital, cada paciente es clasificado de acuerdo a un estado crítico, serio o estable. Estas clasificaciones son actualizadas cada mañana por un médico internista, de acuerdo a la evaluación experimentada por el paciente. Las probabilidades con las cuales cada paciente se mueve de un estado a otro se resumen en la tabla que sigue:

¿Cuál es la probabilidad que un paciente en estado crítico un día Jueves esté estable el día Sábado?.

Sea $X_{n}$ la variable aleatoria que indica el estado que se encuentra un paciente cualquiera en el hospital en el día n. Los valores posibles para dicha variable son C, S y E, representando los estados crítico, serio y estable, respectivamente. Un grafo que representa dicho proceso estocástico dada la tabla anterior es:

La probabilidad de que un paciente esté en estado crítico el día Jueves y que el día Sábado esté estable, esta dado por: $\mathbb{P}_{CE}^{2}$ , es decir, la probabilidad de pasar del estado crítico al estado estable al cabo de 2 etapas (días).

$\mathbb{P}_{CE}^{2}=0,3*0,2+0,1*0,5+0,6*0,1=0,17$

Notar que de forma equivalente se pueden utilizar las ecuaciones matriciales $f^{n}=P^{T}*f^{n-1}$ :

Se comprueba que la probabilidad de pasar del estado crítico al estado estable al cabo de 2 etapas es de un 17%.

¿Cuál es la probabilidad que un paciente que está en estado estable el Lunes experimente alguna complicación y no esté estable nuevamente el Miércoles?.

En este caso cambia la distribución inicial respecto al escenario anterior (ahora el paciente está en estado estable), no obstante, también resulta de nuestro interés analizar qué sucede al cabo de 2 etapas.

Con color verde se marca la probabilidad de que comenzando en un estado estable al cabo de 2 días un paciente se encuentre en estado crítico o serio. La suma de dichas probabilidades es un 66% que da respuesta a la interrogante anterior.

¿Qué porcentaje de la Unidad de Cuidados Intensivos usted diseñaría y equiparía para pacientes en estado crítico?.

Naturalmente se desea estimar la probabilidades de estado en el largo plazo independiente de la distribución inicial. La cadena es irreducible con estados recurrentes positivos aperiódicos. Utilizando las ecuaciones de estado estable presentadas en el Ejercicio N°2 se obtiene que $\pi _{C}\cong0,2373$ , $\pi _{S}\cong0,6184$ y $\pi _{E}\cong0,1443$ , que representan la probabilidad de que un individuo se encuentre en estado crítico, serio y estable, respectivamente.

El software Interactive Operations Research Tutorial (IORTutorial) permite estimar las probabilidades de largo plazo luego de ingresar la matriz de probabilidades de transición según se muestra a continuación:

Comentarios: En el Blog hemos desarrollado otros ejercicios resueltos que recomendamos revisar, entre ellos uno que aborda una Política de Gestión de Inventarios a través de Cadenas de Markov en Tiempo Discreto y Ejemplo de una Cadena de Markov en Tiempo Discreto. Adicionalmente en la categoría de contenidos de Cadenas de Markov periódicamente estamos publicando nuevo material didáctico sobre dicha materia. Esperamos que este material sea de utilidad para tus estudios y te agradecemos puedas ayudarnos a difundir éste a través de las redes sociales.

Gestión de Inventarios a través de Cadenas de Markov en Tiempo Discreto

La gestión de inventarios hace uso de distintas herramientas metodológicas que abordan 2 preguntas básicas: ¿de qué tamaño debe ser un pedido? y ¿cada cuánto tiempo se debe realizar un pedido?. En el siguiente artículo se propone la utilización de una Cadena de Markov en tiempo discreto para determinar la política de reposición de inventarios de una empresa: Una tienda que mantiene un inventario de un producto dado para satisfacer una demanda (aleatoria). La demanda diaria D, tiene la siguiente distribución de probabilidades:

Consideremos una política de inventarios denominada (q,Q), que indica que si el nivel de inventarios al final de cada día es menor a q=2 se ordenan Q=1 unidades adicionales (las cuales se asumen disponibles al inicio del día siguiente), en caso contrario no se hace ninguna orden. La demanda no satisfecha es venta perdida y hay 2 unidades al final en n=0 (distribución inicial). Sea Xn el nivel de inventario al final del día n (esto corresponde a la definición de la variable aleatoria), interesa modelar el problema mediante una Cadena de Markov.

Un primer desafío consiste en determinar los posibles estados que puede adoptar la variable aleatoria en una etapa n cualquiera. Notar que es posible finalizar un día sin unidades en inventario, dado que si bien esta situación genera una reposición de 1 unidad, ésta se asume disponible al inicio del día siguiente. Adicionalmente también es posible terminar un día con 1 o 2 unidades en inventario (en estos casos no se genera reposición). Sin embargo, no es posible terminar un día con 3 unidades en inventario (recordar que en n=0 se dispone de 2 unidades en inventario y dada la política de reposición, ésta se genera cuando se dispone de menos de 2 unidades en inventario). En resumen, los estados posibles para la variable aleatoria son Xn℮{0,1,2}.

A continuación estimamos las probabilidades de transición en una etapa las cuales se resumen en la siguiente matriz de probabilidades de transición (matriz P):

Por ejemplo, si en un día n en particular se finaliza con 0 unidades en inventarios se genera un pedido que al inicio del día siguiente permitirá disponer de 1 unidad; para que dicho día (n+1) se termine con 0 unidades en inventario se requiere que la demanda sea mayor o igual a 1 unidad (este es el caso de P00).

Adicionalmente se pueden estimar las probabilidades estacionarias, es decir, que en el largo plazo (independiente de la distribución inicial) se disponga al final de un día de 0, 1 o 2 unidades en inventario. Para ello se debe clasificar los estados de la cadena donde en particular se corrobora que ésta es irreducible con estados recurrentes positivos aperiódicos.

En consecuencia la probabilidad de que en el largo plazo se disponga de 0 unidades al final de un día es de un 50% (1/2), tener una unidad es un 37,5% (3/8) y 2 unidades un 12,5% (1/8). Alternativamente podemos hacer uso de las ecuaciones matriciales para que partiendo de la distribución inicial (dato) se estime la probabilidad de encontrarse en cualquiera de los estados al cabo de 1, 2, …, n etapas (con n que tiende a infinito). Dicho resultado corrobora los resultados anteriores:

Se propone al lector comprobar que independiente de la selección de la distribución inicial las probabilidades de largo plazo son las expuestas.

Distribución Límite de una Cadena de Markov en Tiempo Discreto

Una Distribución Límite (estacionaria) de una Cadena de Markov en tiempo discreto consiste en una distribución de estado estable para los estados de una cadena que es independiente de la distribución inicial.

En distintas aplicaciones de esta categoría de procesos estocásticos resulta de interés identificar la probabilidad de que la variable aleatoria «Xn» adopte un valor «j» (entre M estados posibles) al cabo de un número de etapas o transiciones «n» que tiende a infinito. Lo anterior equivale a:

En este contexto existen ecuaciones que permiten encontrar estas probabilidades de largo plazo en la medida que el proceso markoviano en tiempo discreto sea una cadena irreducible con estados recurrentes positivos aperiódicos.

Para ello se requiere en primera instancia Clasificar los Estados de la Cadena de Markov de modo de corroborar las condiciones anteriores.

En forma compacta las ecuaciones que permiten encontrar las probabilidades estacionarias son:

Consideremos el siguiente ejemplo que satisface las condiciones enunciadas previamente. ¿Cuál es la probabilidad de que en el largo plazo el proceso se encuentre en el estado 0, 1 o 2?.

La matriz de probabilidades de transición en una etapa (y su respectiva matriz transpuesta) son las siguientes:

El sistema de ecuaciones que permite encontrar las probabilidades de estado estable queda especificado por:

La resolución del sistema anterior permite obtener:

Es decir, la probabilidad de que en el largo plazo el proceso se encuentre en el estado 0, 1 y 2 es de un 28,57%, 35,71% y 35,71%, respectivamente (las probabilidades han sido aproximadas a dos decimales). Esto es independiente de la distribución inicial, es decir, en qué estado actualmente se encuentre la variable aleatoria.

Conclusión: Se puede corroborar los resultados anteriores utilizando las fórmulas matriciales para encontrar la distribución de estado para una etapa «n». Para ello seleccionamos un valor de «n» relativamente «grande» y una distribución inicial cualquiera (se deben seleccionar valores de a, b y c mayores o iguales a cero tal que a+b+c=1). Con esto se puede verificar que independiente de la distribución inicial las probabilidades de largo plazo convergerán asintóticamente a los valores obtenidos anteriormente.

Por ejemplo, estableciendo (arbitrariamente) a=1, b=0, c=0 se logran las siguientes probabilidades de estado al cabo de 10 transiciones (con color verde se muestra las probabilidades estacionarias).