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

...