Informe Markov 4f6120

“Año de la consolidación del Mar de Grau” UNIVERSIDAD NACIONAL DEL SANTA ESCUELA ACADÉMICO INFORMÁTICA

PROFESIONAL

DE

INGENIERÍA

DE

SISTEMAS

CURSO: INVESTIGACIÓN DE OPERACIONES II TEMA: Cadenas de Markov, probabilidades de transición y diagrama de estados INTEGRANTES: AGUILAR VILLEGAS VICTOR AGUIRRE CORTEZ ISAAC RAMOS RAMIREZ ANDERSSON CASTILLO ALEJOS LUIS JARA LÁZARO ADERSON REYES VENANCIO JHONN SAAVEDRA ZEGARRA MELVIN

NUEVO CHIMBOTE 2016

E

CADENAS DE MARKOV DEFINICIÓN DE CADENAS Básicamente, una cadena es un proceso en tiempo discreto (también se puede suponer su continuidad, pero esta tarea sobrepasa el ámbito en el que se enmarca esta publicación) en el que una variable aleatoria va cambiando de estado con el paso del tiempo. O, en otras palabras, una cadena representa un sistema que varía su estado a lo largo del tiempo. Un estado es una caracterización de la situación en la que se halla un determinado sistema en un instante dado, y puede ser tanto cuantitativo como cualitativo. En términos coloquiales, un estado es la respuesta a la pregunta ¿Cómo están las cosas? En términos más formales, el estado de un sistema en un determinado instante es una variable aleatoria cuyos valores sólo pueden pertenecer al conjunto de posibles estados del sistema, que son mutuamente excluyentes. El sistema que pretende modelizar una cadena es, por consiguiente, una variable aleatoria que cambia de valor (cuantitativo o cualitativo) en el tiempo. A dicho cambio se le denomina transición. DEFINICIÓN DE CADENA DE MARKOV Las cadenas de Markov tienen la propiedad de que la probabilidad de que la variable aleatoria en cuestión se encuentre en un estado j en el instante t sólo depende del estado en que se encontraba el sistema en el instante t-1, y no de los anteriores a este último. En este sentido, las cadenas de Markov tienen memoria, si bien dicha memoria está restringida al último estado de la variable. A modo de ejemplo: La probabilidad de que el valor de una acción bursátil evolucione al alza, a la baja o repita en una determinada sesión bursátil depende únicamente de si subió, bajó o permaneció constante en la sesión precedente. Las cadenas de Markov han sido ampliamente utilizadas en numerosos campos de la Ciencia, y en particular en el de las Ciencias Sociales. DEFINICIÓN FORMAL Una sucesión de observaciones X1, X2,... se denomina proceso estocástico ¨ Si los valores de estas observaciones no se pueden predecir exactamente ¨ Pero se pueden especificar las probabilidades para los distintos valores posibles en cualquier instante de tiempo. X1 : v.a. que define el estado inicial del proceso Xn : v.a. que define el estado del proceso en el instante de tiempo n Para cada posible valor del estado inicial s1 y para cada uno de los sucesivos valores sn de los estados Xn, n = 2, 3,..., especificamos: P(Xn+1 = sn+1 | X1 = s1, X2 = s2, ..., Xn = sn) Una cadena de Markov es un proceso estocástico en el que Si el estado actual Xn y los estados previos X1,...,Xn−1 son conocidos La probabilidad del estado futuro Xn+1 No depende de los estados anteriores X1,...,Xn−1, y Solamente depende del estado actual Xn. Retomando la terminología formal, considérese una sucesión de variables aleatorias {Xt}, t = 0,1, 2, ...., n-2, n-1, n,...

Pues bien, dicha sucesión de variables aleatorias constituirá una cadena de Markov si se verifica que: P (Xn = j/X0 = i0, X1 = i1,...., Xn-1 = ii-1)= P (Xn= j/Xn-1 = ii-1) En caso de que P (Xn = j/X0 = i0, X1 =i1,...., X n-1= ii-1, Xn-2=ii-2) la cadena se denominaría de segundo orden. Es decir, en el ejemplo utilizado anteriormente, si la probabilidad de evolución al alza, a la baja o de mantenimiento, del valor de una acción bursátil dependiese únicamente de si dicha acción subió o bajó o repitió valor en las dos sesiones precedentes. De manera análoga se definirían las cadenas de Markov de tercer, cuarto,.... orden. Por otra parte, una cadena de Markov se califica de homogénea si las probabilidades de paso de un estado a otro no dependen del instante temporal que se considere. P(Xn = j/ Xn-1 = ii-1) Pij ∀n

DESCRIPCIÓN DE UNA CADENA DE MARKOV En la figura 11-1 se muestra el proceso para generar una cadena de Mar-kov. El generador de Markov produce uno de n eventos posibles, Ej, donde j = 1, 2, . . . , n, a intervalos discretos de tiempo (que no tienen que ser iguales). Las probabilidades de ocurrencia para cada uno de estos eventos dependen del estado del generador.

FIGURA 11-1 Generador de Markov.

Este estado se describe por el último evento generado. En la figura 11-1, el último evento generado fue Ej de manera que el generador se encuentra en el estado Sj. La probabilidad de que Ek sea el siguiente evento generado es una pro-babilidad condicional: P(Ek/Sj). Esto se llama probabilidad de transición del estado Sj al estado Ek .. Para describir completamente una cadena de Markov es necesario saber el estado actual y todas las probabilidades de transición. En esta sección se presentan dos formas fáciles de exponer las probabilidades de transición. Probabilidades de transición Una forma para describir una cadena de Markov es con un diagrama de estados, como el que se muestra en la figura 11-2. En ésta se ilustra un sistema de Markov con cuatro estados posibles: S1;

S2, S3 y S4. La probabilidad condicional o de transición de moverse de un estado a otro se indica en el diagrama. Para simplificar la notación se usan subíndices para el estado actual y el siguiente. Es decir, p14 = P(S4/S1). Las flechas muestran las trayectorias de transición que son posibles. Nótese que no aparecen algunas trayectorias como la de S2 a S3. Su ausencia significa que esas trayectorias tienen probabilidad de ocurrencia igual que cero.

FIGURA 11-2 Un diagrama de estados.

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 tabal 11-1. Nótese que, como existen cuatro estados posibles, se necesitan 4 x 4 = 16 probabilidades. También nótese que cada renglón de la matriz suma 1. Esto se debe a que el sistema debe hacer una transición.

Las probabilidades de transición son datos para el análisis. Se deben conocer, no existe manera de derivarlas. En algunas aplicaciones esto puede ser una limitación. 2. PROBABILIDADES DE TRANSICION Es la probabilidad condicionada P (Xn+1 = sj | Xn = si ) PROBABILIDAD DE TRANSICIÓN ESTACIONARIA

Una cadena de Markov tiene probabilidades de transición estacionarias si para cualquier par de estados si y sj existe una probabilidad de transición pij tal que P (Xn+1 = sj | Xn = si) = pij para n = 1, 2, . . . Las probabilidades de transición se utilizan para describir la manera en que el sistema cambia de un período al siguiente. Se representan por medio de matrices de transición. MATRIZ DE TRANSICIÓN Al trabajar con cadenas de Markov, a menudo es útil pensar la sucesión de ensayosb como experimentos efectuados en cierto sistema físico, cada resultado dejando a este sistema en cierto estado. Por ejemplo, consideremos una sucesión de elecciones políticas en cierto país: el sistema podría tomarse como el país mismo y cada elección lo dejaría en cierto estado, es decir en el control del partido ganador. Si sólo hay dos partidos políticos fuertes, llamados A y B, los que por lo regular controlan el gobierno, entonces podemos decir que el país se encuentra en el estado A o B si el partido A o B ganara la elección. Cada ensayo (o sea cada elección), coloca al país en uno de los dos estados A o B. Una sucesión de 10 elecciones podría producir resultados tales como los siguientes: A, B, A, A, B, B, B, A, B, B La primera elección en la sucesión deja en el poder al partido A, la segunda fue ganada por el partido B, y así sucesivamente, hasta que la décima elección la gane el partido B. Supongamos que las probabilidades de que el partido A o B ganen la próxima elección son determinadas por completo por el partido que está en el poder ahora. Por ejemplo podríamos tener las probabilidades siguientes: • Si el partido A está en el poder, existe una probabilidad de ¼ que el partido A ganará la próxima elección y una probabilidad de ¾ de que el partido B gane la elección siguiente. • Si el partido B está en el poder, hay una probabilidad de 1/3 de que el partido A gane la elección siguiente y una probabilidad de 2/3 que el partido B permanezca en el poder. En tal caso, la sucesión de elecciones forma una cadena de Markov, dado que las probabilidades de los dos resultados de cada elección están determinadas por el resultado de la elección precedente. Lo descrito anteriormente puede representarse gráficamente usando la siguiente red:

1/4

B

3/4

2/3

A 1/3

Los círculos A y B se denominan nodos y representan los estados del proceso, las flechas que van de un nodo a si mismo o al otro son los arcos y representan la probabilidad de cambiar de un estado al otro.

La información probabilística que se acaba de dar se puede representar de manera conveniente por la siguiente matriz: Resultado de la próxima elección A

B

Resultado de la

A

1/4

3/4

ultima elección

B

1/3

2/3

Esta matriz se denomina matriz de transición. Los elementos de la matriz de transición representan las probabilidades de que en el próximo ensayo el estado del sistema del partido indicado a la izquierda de la matriz cambie al estado del partido indicado arriba de la matriz. 

MATRIZ ESTOCÁSTICA

Es una matriz cuadrada cuyos elementos son no negativos y tal que la suma de los elementos de cada fila es igual a 1. MATRIZ DE TRANSICIÓN EN UN SOLO PASO

Dada una cadena de Markov con k estados posibles s1, . . . , sk y probabilidades de transición estacionarias.

Si pij = P (Xn+1 = Sj |Xn = Si ) =⇒

La matriz de transición P de cualquier cadena de Markov finita con probabilidades de transición estacionarias es una matriz estocástica MATRIZ DE TRANSICIÓN EN VARIOS PASOS Dada una cadena de Markov con k posibles estados S1, . . . , Sk y matriz de transición P Si notamos 𝑃2 𝑖𝑗 = P (Xn+2 = Sj |Xn = Si) 𝑃2 ij: Elemento de la i−ésima fila y j−ésima columna de la matriz 𝑃𝑚 𝑃𝑚 : Potencia m−ésima de P, con (m = 2, 3, . . .) y 𝑃𝑚 ij: Elemento de la fila i y de la columna j de la matriz 𝑃𝑚 GENERALIZANDO

𝑃𝑚 es la matriz de probabilidades 𝑃𝑚 𝑖𝑗 de que la cadena pase del estado Si al estado Sj en m pasos; para cualquier valor de m, (m = 2, 3, . . .). 𝑃𝑚 es la matriz de transición de m pasos de la cadena de Markov

CALCULO DE LAS PROBABILIDADES DE TRANSICIÓN Ahora que se sabe cómo presentar los datos, ¿qué puede hacerse? Un análisis útil es pronosticar el estado del sistema después de 1, 2, 3 o más periodos. Esto se llama análisis de transición, debido a que es a corto plazo y está enfocado a periodos cortos. Considérese la cadena de Markov que se describe en la figura 11-3. Esta podría representar una copiadora de oficina, poco segura. Si está fun-cionando un día, existe un 75% de posibilidades de que al día siguiente funcione y un 25% de posibilidades de que no funcione. Pero si no está funcionando, hay 75% de posibilidades de que tampoco funcione al día siguiente y sólo un 25% de que si lo haga (se lleva mucho tiempo la repa-ración).

Para comenzar un análisis de transición, se deben conocer el estado actual. Supóngase que se está comenzando y que hay 75% de posibilidades de estar en el estado 1 y 25 % de estar en el estado 2. Esto define el estado actual en forma probabilista. ¿Cuál es la probabilidad de estar en el estado 1 al día siguiente? Si se comienza en el estado 1 hay 75 % de posibilidades de seguir ahí. Si se comienza en el estado 2, sólo hay 25 % de cambiar el estado 1. Así:

Un ejemplo de dos estados.

P(S1)= P(comiénceseS1)p11P(comiénceseS2)p21 = (0.75)(0.75) + (0.25)(0.25) = 0.625 Como sólo hay dos estados, entonces P(S2) = 0.375.

Después de dos días: P(S1) = 0.625p11 + 0.375p21 = 0.625(0.75) + 0.375(0.25) = 0.567

Este método para hacer cálculos puede representarse por un diagrama de árbol, como se muestra en la figura 11-4. Como puede observarse, la co-piadora no es muy segura. Los resultados de los primeros cuatro días son:

En los sistemas con más estados, los cálculos se vuelven más largos, pero el procedimiento es el mismo. Considérese el sistema de tres estados que se, muestra en la figura 11-5. Supóngase que el sistema se encuentra en el es-tado S1. En el diagrama puede observarse que para el siguiente ciclo:

Para el segundo ciclo: P(S1) = 0.4p11 + 0.3p21 + 0.3p31 = 0.4(0.4) + 0.3(0.1) + 0.3(0.1) = 0.22

335

P(S2) = 0.4p12 + 0.3p22 + 0.3p32 = 0.4(0.3) + 0.3(0.8) + 0.3(0.3) = 0.45 P(S3) = 0.4p13 + 0.3p23 + 0.3p33 = 0.4(0.3) + 0.3(0.1) + 0.3(0.6) = 0.33 Por supuesto, como el sistema se debe encontrar en algún estado, sólo es necesario calcular dos de estas probabilidades y la tercera puede encontrarse con la siguiente relación: P(S1) + P(S2) + P(S3) = 1

Los resultados para los primeros cuatro ciclos son:

Segundo ejemplo: Las granjas de cierta región se pueden clasificar con 3 tipos: agrícolas, pecuarias o mixtas. Actualmente 30% son agrícolas, 40% pecuarias y 30% son mixtas. La matriz de transición de un año al siguiente es:

De acuerdo a la información dada, el Po es:

Para hallar el valor de las probabilidades en el año siguiente hacemos uso de la multiplicación de las matrices, como sigue Para el estado A:

Por lo que el vector para el año siguiente es:

De igual manera calculamos el porcentaje para cada tipo de granja para el periodo 2, 3, 4 y 5

Obsérvese que el valor de la probabilidad de un estado n está dado por la siguiente expresión: 𝑃𝑛 = 𝑃0 𝑇 𝑛

Con este análisis puede encontrarse la probabilidad de que el sistema se encuentre en un estado determinado en cualquier periodo futuro.

CÁLCULO DE LAS PROBABILIDADES DE ESTADO ESTABLE Las cadenas de Markov poseen una propiedad notable en cuanto a que tienden a aproximarse a lo que se llama estado estable. Considérense los dos ejemplos anteriores de análisis de transición. En el sistema de dos estados, P(S1) resultó ser 0.75 al principio y después 0.625, 0.567, 0.531 y 0.516. Estas probabilidades se mueven hacia un límite. En forma análoga, en el sistema de tres estados puede observarse que P(S2 ), por ejemplo, adquiere los valores 0.3, 0.45, 0.53, 0.565 y 0.58. Después de unos cuantos ciclos nada más, las probabilidades de estado comienzan a asentarse o estabilizarse. Cuando una cadena de Markov ha llegado lo suficientemente lejos como para estar cerca de estos límites, se dice que ha alcanzado un estado estable. Además, estos límites son los mismos, independientemente del punto de partida del sistema. Es importante hacer notar que la existencia de una condición de estado estable es una propiedad adicional de las cadenas de Markov. De ninguna manera afecta las probabilidades de transición o la dependencia de cada estado en el estado anterior. Los límites de estado estable se refieren sólo al porcentaje de tiempo a largo plazo que el sistema se encontrará en cada estado particular. En la mayoría de las aplicaciones el estado estable tiene una gran im-portancia, esto puede apreciarse más adelante. En esta sección se describen dos métodos para determinar estos límites y se presenta una aplicación a comercialización.

Método de la suma de flujos

Este método está basado en el concepto de que todo lo que entra debe salir. El diagrama de estados se usa para presentar los flujos. En la figura 11-6 se muestra de nuevo el ejemplo anterior de dos estados. Para cada estado puede escribirse una ecuación tal que para el estado k se cumpla:

Esta ecuación se ve peor de lo que en realidad es. Observando el estado S, en la figura 11-6, póngase atención sólo en las flechas entre los estados. Para los flujos que llegan, se tiene

El ejemplo de dos estadas.

Para los flujos que salen, se suman las probabilidades de transición a todos los otros estados. En este caso sólo hay una, 0.25. Así, la ecuación para S1 es 0.25P(S2) = 0.25P(S1) De igual manera, el flujo hacia adentro para el estado S2 es 0.25P(S1) y el flujo hacia afuera es 0.25P(S2). Esto da para S2 0.25P(S1) = 0.25P(S2)

El hecho de que estas dos ecuaciones sean iguales es una coincidencia. Pero no son independientes; así, se necesita una relación más: P(S1) = P(S2) = 1

Esto proporciona tres ecuaciones con dos incógnitas que pueden resolverse por eliminación. El resultado es P(S1) = P(S2) = 0.5

El procedimiento no cambia en los sistemas con más estados. Considé-rese el ejemplo de tres estados que se dio antes y que se muestra en la figu-ra 11-7. Para el estado S1 se tiene 0.1P(S2) + 0.1P(S3) = (0.3 + 0.3)P(S1) Para el estado S2 0.3P(S1) + 0.3P(S3) = (0.1 + 0.1)P(S2)

El ejemplo de tres estados.

y para el estado S3 0.3P(S1) + 0.1P(S2) = (0.1 + 0.3)P(S3)

Al poner esto todo junto se tienen cuatro ecuaciones:

Cuando se resuelve un conjunto de ecuaciones como éste, la última ecuación no puede eliminarse. Si se usan sólo las primeras tres, al final se tendrá una identidad ya que no son independientes. Una manera de resolverlas es por eliminación. Se despeja P(S1) en la primera ecuación y después se sustituye el resultado en las últimas dos:

Sumando términos semejantes, resultan dos ecuaciones con dos incógnitas:

Después puede eliminarse P(S3) multiplicando la primera ecuación por 1.17/0.35 y sumando las dos ecuaciones:

Con este resultado se encuentra P(S3):

1.17(0.6) + 1.17P(S3) = 1 P(S3) = 0.26 Por último, se sustituyen los valores en la ecuación de P(S1): P(S1) = 1/6(0.6) + 1/6(0.26) = 0.14

Según los resultados obtenidos en el análisis de transición, puede observarse que el sistema estaba cerca de estos límites después de sólo cinco ciclos.