Investigacion De Operaciones

UNIDAD 3.- Cadenas de Markov

41. Introducción.

Una cadena de Markov es una serie de eventos, en la cual la probabilidad de que ocurra un evento depende del evento inmediato 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 Markov de las series de eventos independientes, como tirar una moneda al aire o un dado.

Una cadena de Markov es un caso especial de los procesos de Markov. Se utiliza para estudiar el comportamiento a corto y largo plazo de ciertos sistemas estocásticos.

En los negocios, las cadenas de Markov 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.

El análisis de Markov, llamado así en honor de un matemático ruso que desarrollo el método en 1907, permite encontrar la probabilidad de que un sistema se encuentre en un estado en particular en un momento dado. Algo más importante aún, es que permite encontrar el promedio a la larga o las probabilidades de estado estable para cada estado. Con esta información se puede predecir el comportamiento del sistema a través del tiempo.

La tarea más difícil es reconocer cuándo puede aplicarse. La caracteristica más importante que hay que buscar en la memoria de un evento a otro.

4.2 Formulación de las cadenas de Markov.

Una cadena de Markov es una serie de eventos, en la cual la probabilidad de que ocurra un evento depende del evento inmediato 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 Markov de las series de eventos independientes, como tirar una moneda al aire o un dado.

En la figura 4.1.1 se muestra el proceso para formular una cadena de Markov. El generador de Markov produce uno de n eventos posibles, Ej , donde j = 1, 2, . . . , n, a intervalos discretos de tiempo (que no tiene que ser iguales ). Las probabilidades de ocurrencia para cada uno de estos eventos depende del estado del generador. Este estado se describe por el último evento generado. En la figura 4.1.1, el último evento generado fue Ej , de manera que el generador se encuentra en el estado Mj .

La probabilidad de que Ek sea el siguiente evento generado es una probabilidad condicional : P ( Ek / Mj ). Esto se llama probabilidad de transición del estado Mj al estado Ek. Para describir completamente una cadena de Markov es necesario saber el estado actual y todas las probabilidades de transición.

Probabilidades de transición.

La probabilidad de transición Pxn-1,xn = P tn = Xn tn-1 = Xn – 1 se llama probabilidad de transición. Representa la probabilidad condicional del sistema que está en xn en tn, dado que estuvo en Xn – 1 en tn – 1. Esta probabilidad también se denomina transición de un paso porque describe el sistema entre tn – 1 y tn . De esta forma, una probabilidad de transición de m pasos se define por:

Pxn, xn + m = P tn + m = xn + m tn = xn

Una forma de describir una cadena de Markov es con un diagrama de estados, como el que se muestra en la figura 4.1.2. En ésta se ilustra un sistema de Markov con cuatro estados posibles : M1, M2 , M3 y M4 . La probabilidad condicional o de transición de moverse de un estado a otro se indica en el diagrama

Otro método para exhibir las probabilidades de transición es usar una matriz de transición. . La matriz de transición para el ejemplo del diagrama de estados se muestra en la tabla 4.1.1 .

Otro método para exhibir las probabilidades de transición es usar una matriz de transición. .

Para n = 0, 1, 2, ....

El superíndice n no se escribe cuando n = 1.

Defina Pi j = P tn = j tn – 1 = I

como la probabilidad de transición de un paso de ir del estado i en tn – 1 al estado j en tn – 1 al estado j en tn, y supongamos que estas probabilidades son estacionarias a través del tiempo. Las probabilidades de transición del estado Ei al estado Ej se arreglan de manera más conveniente en forma matricial como sigue:

P =

La matriz P se llama transición homogénea o matriz estocástica porque todas las probabilidades de transición pi j son fijas e independientes del tiempo. Las probabilidades pi j deben satisfacer las condiciones

pi j = 1, para toda i

j

pi j 0, para toda i y j

Ahora se define la cadena de Markov . Una matriz de transición P junto con las probabilidades iniciales aj(0) asociadas con los estados EJ definen completamente una cadena de Markov. 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. Este caso se denomina cadenas de Markov encajadas.

Clasificación de estados en cadenas de Markov. Estas definiciones serán útiles en el estudio del comportamiento del sistema a largo plazo.

Cadena de Markov irreducible. Se dice que una cadena de Markov es irreducible si cada estado Ej se puede alcanzar desde cualquier otro estado EJ después de un número finito de transiciones, es decir, para i j,

PI J(n) > 0, para 1 n <

En este caso todos los estados de la cadena se comunican.

Estados de conjunto cerrado y absorbentes. En una cadena de Markov, se dice que un conjunto C de estados está cerrado si el sistema, una vez en uno de los estados de C, permanecerá en C indefinidamente

Tiempos de primer regreso. Una definición importante en la teoría de las cadenas de Markov es el tiempo de primer regreso. Dado que el sistema está inicialmente en el estado EJ, éste puede regresar a EJ por primera vez en el paso n, n 1. El número de pasos antes de que el sistema regrese a EJ se llama tiempo de primer regreso.

Cadenas de Markov Ergódicas. Si todos los estados de una cadena de Markov son ergódicos, entonces la cadena es irreducible. En este caso, las probabilidades absolutas a(n) = a(0) Pn siempre convergen de forma única a una distribución limitante conforme n , donde la distribución limitante es independiente de las probabilidades iniciales a(0).

El siguiente teorema es ahora oportuno:

Todos los estados en una cadena de Markov infinita irreducible pueden pertenecer a una, y sólo una, de las siguientes tres clases: estado transitorio, estado recurrente nulo o estado recurrente no nulo. En cada caso todos los estados se comunican y tienen el mismo periodo. Para el caso especial donde la cadena tiene un número finito de estados, la cadena no puede consistir sólo en estados transitorios ni puede contener estados nulos.

4.3 Procesos estocásticos.

Un proceso estocástico se define sencillamente como una colección indexada de variables aleatorias { X1 }, donde el subíndice t toma valores de un conjunto T dado. Con frecuencia T se toma como el conjunto de enteros no negativos y X, representa una característica de interés medible en el tiempo t. Por ejemplo, el proceso estocástico, X1 , X2 , X3, .., Puede representar la colección de niveles de inventario semanales (o mensuales) de un producto dado, o puede representar la colección de demandas semanales (o mensuales) de este producto.

Un estudio del comportamiento de un sistema de operación durante algún periodo suele 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 lo s M + 1 estados del proceso.

4.4 Propiedad Markoviana de primer orden.

Se dice que un proceso estocástico tiene la propiedad markoviana si

P { Xt+1 = j | X0 = K0 , X1 = K1 , . ., Xt-1 = Kt-1 , = Kt-1, Xt=1}= P {X t+1 | X1 = i }, para toda t = 0, 1, . . y toda

sucesión i, j , K0 , K1 , . . , Ki-1 .

Se puede demostrar que esta propiedad markoviana es equivalente a establecer una probabilidad condicional de cualquier "evento" futuro dados cualquier "evento " pasado y el estado actual Xi = i , es independiente

...