Cadenas de Markov (preliminar)

UABC VALLE DORADO FCAYS 2.

MÉTODOS CUANTITATIVOS AVANZADOS

2.12.

2.12.3.

©

LECTURAS

Cadenas de Markov

Prof. Raúl Espejo Rodarte

UABC

FCAyS (795)

1

Son sistemas matemáticos que experimentan transiciones de un estado a otro en un espacio de estados. Una cadena de Markov es una serie de eventos aleatorios, en la cual la probabilidad de que ocurra un evento depende del evento inmediato anterior. En efecto, las cadenas son procesos caracterizados por su falta de memoria. “olvidan” toda la cadena de eventos anteriores, y solamente el último evento condiciona las posibilidades del próximo evento. 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. Tienen muchas aplicaciones como modelos estadísticos de procesos del mundo real. 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 característica más importante que hay que buscar en la memoria de un evento a otro. 2.12.3.1.

Ejemplos:

1. El movimiento aleatorio en la recta numérica, en cada periodo la posición puede cambiar con la misma probabilidad hacia adelante o hacia atrás. Las probabilidades de incrementar son las mismas que de decrementar. Desde cada posición hay dos posibles transiciones: el siguiente entero o el anterior. Por ejemplo si la posición actual es la 7, entonces la transición a 6 tiene una probabilidad de .5, sin importar que haya sucedido antes. 2.12.3.1.1.

Aplicación a la administración:

2.12.3.1.1.1.

Planeación de Personal.

El análisis de transición puede ser útil al planear satisfacer las necesidades de personal. Muchas firmas emplean trabajadores de diferentes niveles de clasificación dentro de la misma categoría de trabajo. Esto es común para personal de confianza, oficinistas, obreros calificados, no calificados y personal profesional. La firma debe tener el número de empleados en cada nivel de clasificación para proporcionar la oportunidad de promoción adecuada, cumplir con las habilidades necesarias para el trabajo y controlar la nómina. Una planeación de personal a largo plazo apropiada requiere que se considere el movimiento de personas tanto hacia arriba en el escalafón de clasificación como hacia afuera de la organización. El análisis de Markov puede ayudar en este esfuerzo de planeación. El movimiento de personal a otras clasificaciones puede considerarse como una cadena de Markov.

©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC

FCAyS (795)

2

Se supone que hay tres clasificaciones; el grado 1 es la más baja. Además, los descensos se consideran raros y se omiten. El estado “salen” es absorbente, el cual incluye renuncias, ceses, despidos, jubilaciones y muertes. Por supuesto, todos los empleados finalmente alcanzan este estado. Las transiciones del grado 1 al grado 2 y del grado 2 al grado 3 representan promociones. Como transiciones de probabilidad, están controladas por la firma, puede establecerse el nivel que la firma determine que es necesario para cumplir sus objetivos. Como ejemplo, supóngase que la firma tiene en este momento 30 empleados del nivel 3, 90 empleados del grado 2 y 300 empleados del grado 1 y que desea mantener este nivel de empleados durante el próximo año. Por experiencia, se espera que salgan el 30% de los empleados de grado 1 al año, el 20% de los empleados de grado 2 y el 10% de aquellos que están en el grado 3. ¿Si la política es contratar sólo en los niveles de clasificación más bajos, cuántos se deben contratar y cuántos se deben promover el siguiente año para mantener estables los niveles? Este problema puede resolverse sin el análisis de Markov, pero el modelo es útil para ayudar a conceptualizar el problema. Como se trata sólo de un ciclo, se usa el análisis de transición. El análisis comienza con el grado más alto. No se hacen promociones pero el 10%, o sea 3, sale. Todos ellos deben de reemplazarse por promociones del grado 2. En el nivel de clasificación 2, el 20% sale y se deben promover 3, con una pérdida de 21. Esto se debe compensar por promoción del grado 1. Al pasar al grado 1, el 30% sale y 21 deben promoverse, lo cual una pérdida total de 111. Por tanto, el siguiente año se deben contratar 111 empleados del nivel 1. En este ejemplo se derivan algunas tasas de transición a partir de consideraciones externas. 2.12.3.1.2.

2.12.3.1.2.1.

Otras Aplicaciones

Economía y finanzas

Las cadenas de Markov se pueden utilizar en modelos simples de valuación de opciones para determinar cuándo existe oportunidad de arbitraje, así como en el modelo de colapsos de una bolsa de valores o para determinar la volatilidad de los precios. 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. 2.12.3.1.2.2.

2.12.3.1.2.2.1.

Biología

Hábitos Alimenticios.

Una creatura que come frutas, carne y verduras, con las siguientes reglas: solo come una vez al día, si ayer comió carne, ahora no y comer frutas o verduras tiene la misma probabilidad. Si ahora come frutas, mañana comerá frutas con una probabilidad de .1, verduras con probabilidad de .5 o carne con una probabilidad de .4. Cuando coma verduras, al día siguiente consumirá exclusivamente frutas (40% de probabilidad), o carne con un 60% de probabilidad. Su régimen alimenticio puede ser modelado con una cadena de Markov, ya que su selección actual solo depende de la selección anterior. Una propiedad estadística que se podría calcular es el porcentaje esperado de tiempo en que esta criatura come carne, en un periodo de tiempo muy largo. 2.12.3.1.2.2.2.

©

Prof. Raúl Espejo Rodarte (11950)

Estrategia Alimenticia.

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC

3

FCAyS (795)

La estrategia de la araña. En un cuarto que dividimos en tres espacios: A la entrada B la vecindad de la telaraña, T la telaraña, Con dimensiones A >> B >> T. La mosca presenta un vuelo errático (para confundir a sus depredadores). Estando en A, tiene probabilidades de permanecer en A (90%), pasar a B (10%) y no tiene forma de llegar a la telaraña. Estando en B, tiene probabilidad de pasar a A (40%), permanecer en B (45%), caer en la telaraña (5%). Estando en la telaraña significa su muerte, por lo que las posibilidades de pasar a las zonas A y B es 0 y la de permanecer en T es de 100%. En este ejemplo el estado T (†la muerte) es un estado absorbente, porque una vez que el sistema se encuentra en ese estado, no lo abandona jamás. Se demuestra, por cadenas de Markov, que todas las moscas que entren al cuarto cerrado, tarde o temprano caen en la telaraña, que a pesar de estar escondida y ser pequeña, demuestra ser una estrategia infalible. (Recordemos que el metabolismo de la araña es muy lento y puede vivir en estado suspendido, casi sin consumir alimento durante mucho tiempo, el movimiento en la telaraña la reanima, bajando rápidamente por su alimento). Muchos depredadores tienen esta estrategia: Tortuga caimán, los cocodrilos, muchos peces, etc.

T

A

2.12.3.1.2.3.

B

Meteorología

Si consideramos el clima de una región a través de distintos días, es claro que el estado actual solo depende del último estado y no de toda la historia en sí, de modo que se pueden usar cadenas de Markov para formular modelos climatológicos básicos. Por ejemplo se han desarrollado modelos de recurrencia de las lluvias basados en cadenas de Markov.3 2.12.3.1.2.3.1.

Determinación del clima

En Ensenada, BC, México llueve después de un día soleado en aproximadamente 20 días al año, y en 5 ocasiones de esos días lluviosos, también llueve al día siguiente. Soleado Lluvioso S L Soleado 345/365=0.9452 20/365=0.0548 rrrrrrrrrrrrrrrr S 0.9452 0.0548 Lluvioso 15/20=.75 5/20=.25 L .75 .25 Dadas la condición actual puede predecirse la siguiente: . 𝟗𝟒𝟓𝟐 . 𝟎𝟓𝟒𝟖 Ahora está lloviendo x0=[0, 1]; mañana: 𝐱 𝟏 = [𝟎 𝟏] [ ] = [. 𝟕𝟓 . 𝟐𝟓] hay una . 𝟕𝟓 . 𝟐𝟓 probabilidad de 75% que mañana esté soleado. En el análisis se obtiene que se llega al estado estable, que indica que la probabilidad de lluvias es de 6.8% y de que no llueva 93.2%

©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC 2.12.3.1.2.4.

FCAyS (795)

4

Simulación

Las cadenas de Markov son utilizadas para proveer una solución analítica a ciertos problemas de simulación, por ejemplo en teoría de colas el Modelo M/M/14 es de hecho un modelo de cadenas de Markov. 2.12.3.1.2.1.

Física

Se usan en muchos problemas de la termodinámica y la física estadística. 2.12.3.1.2.1.1.

Cadena de Ehrenfest

Modela el intercambio de moléculas de gas entre dos urnas. Apéndice 2.12.3.1.2.1.2.

Modelo de Difusión de Laplace

Apéndice 2.12.3.1.2.2.

Juegos de azar

Son muchos los juegos de azar que se pueden modelar a través de una cadena de Markov. El modelo de la ruina del jugador, que establece la probabilidad de que una persona que apuesta en un juego de azar finalmente termine sin dinero, es una de las aplicaciones de las cadenas de Markov en este rubro. Los juegos de tablero jugados con dados: Turista, Monopolio, Serpientes y Escaleras, la Oca, etc. en los que la próxima casilla solo depende de la casilla en que se encuentre actualmente el jugador, y un evento probabilístico normado por el (los) dado(s). Pueden determinarse las probabilidades de ocurrencia de las diferentes celdas, en las que hay algunas que tienen una probabilidad mayor y son en las que se ubican penalidades o castigos. 2.12.3.1.2.3.

Genética

Se emplean cadenas de Markov en teoría de genética de poblaciones, para describir el cambio de frecuencias génicas en una población pequeña con generaciones discretas, sometida a deriva genética. Ha sido empleada en la construcción del modelo de difusión de Motō Kimura. 2.12.3.1.2.4.

Música

Diversos algoritmos de composición musical usan cadenas de Markov, por ejemplo el software Csound o Max 2.12.3.1.2.5.

Operaciones

Se emplean cadenas de Markov en inventarios, mantenimiento, flujo de proceso 2.12.3.1.2.6.

Redes Neuronales

Se utilizan en las máquinas de Boltzmann (redes neuronales) 2.12.3.1.2.1.

Modelos epidemiológicos

Una importante aplicación de las cadenas de Markov se encuentra en el proceso Galton-Watson. Éste es un proceso de ramificación que se puede usar, entre otras cosas, para modelar el desarrollo de una epidemia (véase modelaje matemático de epidemias).

©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC 2.12.3.1.2.2.

FCAyS (795)

5

Internet

El pagerank de una página web (usado por Google en sus motores de búsqueda) se define a través de una cadena de Markov, donde la posición que tendrá una página en el buscador será determinada por su peso en la distribución estacionaria de la cadena. 2.12.3.1.2.3.

2.12.3.1.2.3.1.

Caso de Aplicación:

Análisis de Participación de Mercado.

El análisis de transición puede ser útil para analizar la lealtad del público. La fidelidad de un cliente a un mercado particular solo se puede manejar de manera estadística y por tanto, probabilística. En el devenir del tiempo, este estadístico aleatorio corresponde a una variable estocástica. Se trata de estimar la probabilidad de que un cliente que usó un mercado, regrese a ese mercado. La investigación pretende contabilizar cuantos clientes de un supermercado (Suriana), hacen su siguiente compra en dicho almacén. Una planeación de lealtad comercial a largo plazo apropiada requiere que se considere el movimiento de clientes tanto hacia otra tienda como hacia ésta, pues no se puede estimar el costo de la pérdida de un cliente. El análisis de Markov puede ayudar en este esfuerzo de planeación: El movimiento de clientes a otros mercados puede considerarse como una cadena de Markov. Se ha determinado que del seguimiento de los clientes del almacén Suriana Bahía, indica que el 93% de ellos hicieron su compra anterior en esta misma tienda. Y que 8% de los clientes hicieron sus compras en esta tienda pero la vez anterior no. . 𝟗𝟑 . 𝟎𝟕 0 1 Suriana Otro 𝑴=[ ] . 𝟎𝟖 . 𝟗𝟐 0 .93 .07 Suriana .93 1-.93=.07 1 .08 .92 Otro .08 1 - .08 = .92 En este ejemplo se derivan algunas probabilidades de transición a partir de consideraciones externas. 2.12.4.

Conceptos básicos 2.12.4.1.

Estados

Llamamos un estado a la condición única de un elemento del espacio de estados que denotaremos por S: un conjunto exhaustivo y mutuamente excluyente de todas las posibilidades en que puede estar el sistema. A los diferentes estados los nombraremos si donde i es un elemento del conjunto formado por todos los números enteros no negativos desde 1 hasta n, que es el número de estados posibles. Al estado inicial, si se requiere, lo llamaremos s1. 2.12.4.1.1.

Ejemplo

Todos los estados posibles son S= {1, 2, 3, 4,5}. Generalizando S= {s1, s2,…s5}, en donde n es 5. Otra forma de escribirlo es S= {si}, con i є {1, 2, 3, 4, 5}.1

1

i es un elemento del conjunto cuyos elementos son 1, 2, 3, 4 y 5 ©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC

FCAyS (795)

6

st, representa el estado del sistema en el tiempo t, una categoría mutuamente exclusiva y colectivamente exhaustiva con característica de interés medible en el tiempo t, Por ejemplo, el proceso estocástico, s1, s2, s3, … 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. 2.12.4.2.

Tiempos Discretos

Aunque es posible definir procesos de Markov en tiempo continuo, se simplifican los problemas si establecemos que el sistema solo es evaluado en momentos precisos, sin poder decir nada de las condiciones y posibles situaciones que pudieran suceder entre observaciones del sistema. Podemos asumir que los cambios que suceden entre observaciones no son significativos en relación al cambio que hay entre dichos instantes. 2.12.4.3.

Espacio de Estados

Un modelo de Markov consiste en una serie de eventos aleatoriamente seleccionados de un conjunto de estados discretos (Espacio de Estados). Este conjunto (S) es colectivamente exhaustivo2 y mutuamente excluyente3. Describe todos los posibles estados donde el sistema puede estar y cada estado excluye la ocurrencia de todos los demás. La transición del estado i a j ocurre con una probabilidad Pi,j Podemos pensar en un modelo de Markov como una simple línea de transferencia. 2.12.4.4.

Proceso Estocástico

Un proceso estocástico se define como una colección indexada de variables aleatorias {St}= {s0, s1, s2,…, st,…}, donde el subíndice t toma valores de un conjunto T dado, que frecuentemente se toma como el conjunto de los enteros no negativos (como el tiempo discreto). 2.12.4.5.

Procesos de Markov

Se dice que un proceso estocástico tiene la propiedad markoviana (de primer orden) si el estado en el lapso de tiempo t (actual) es st, en el próximo lapso de tiempo P{ st+1 = j | s0 =k0, s1 =k1, s2 =k2 , … st-1 = kt-1 , st= i}= P {st+1 =j | st = i }4, Para toda t = 1, 2, … y para toda sucesión { k0, k1, k2 , … , kt-1, i, j}5. (Historia previa de estados). El siguiente estado solo depende del estado actual, y su probabilidad de llegar al siguiente estado. Se puede demostrar que esta propiedad markoviana es equivalente a establecer una probabilidad condicional de cualquier “evento” futuro dados cualesquier “eventos“ pasados y el estado actual xt+1, es independiente de todo evento anterior a xt. Las probabilidades condicionales P{st+1 = j | st = i} se llaman probabilidades de transición. Si para cada i y j, P{st+1=j | st=i}=p{s2=j|s1=i}, para toda t = 1, 2, …

2

Que todos los estados posibles son elementos de dicho conjunto Que solo existe posibilidad de estar en uno (y sólo uno) de los estados factibles en un tiempo dado. 4 Probabilidad de que el siguiente estado sea j dado que todos los estados anteriores fueron conocidos, es igual a la probabilidad de que el estado siguiente sea i solamente está condicionada al estado actual __________________________________________________________________________________________________ 5 Toda la historia previa del sistema 3

©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC

FCAyS (795)

7

Entonces se dice que las probabilidades de transición (de un paso) son estacionarias (La probabilidad de pasar de un estado i a un estado j siempre es la misma), y por lo general se denotan por pi,j. Así, tener probabilidades de transición estacionarias implica que las probabilidades de transición no cambian con el tiempo. En otras palabras, el siguiente estado solo depende del estado actual. La existencia de probabilidades de transición estacionarias (de un paso) también implica que, para cada i, j y n (n=1,2,…): P{st+n=j|st=i}=P{sn=j|s1=i}, para toda t=1,2,⋯. Estas probabilidades condicionales casi siempre se denotan por pi,j y se llaman probabilidades de transición de n pasos. Así, pi,j es simplemente la probabilidad condicional de que la variable aleatoria s, comenzando en el estado i, se encuentre en el estado j después de n pasos (unidades de tiempo). Como la pi,j son probabilidades condicionales, deben satisfacer las propiedades: (𝐧) 𝟎 ≤ 𝐏𝐢,𝐣 ≤ 𝟏 ∀ 𝐢, 𝐣; 𝐧 = 𝟏, 𝟐, ⋯ 6 (𝐧)

𝟏 = ∑𝐧𝐣=𝟏 𝐏𝐢,𝐣 7 Condiciones suficientes para definir una distribución de probabilidad. 2.12.4.1.

Orden

Es el número de estados previos que definen el nuevo estado, aquí solo discutimos cadenas de primer orden pues sólo dependen del estado anterior. 2.12.4.2.

Ensayos

Llamamos un ensayo a la observación del estado en el momento oportuno. Es un elemento del espacio de estados. 2.12.4.3.

Transiciones

Es el cambio de un estado a otro. Dentro del espacio de estados, el proceso empieza en algún estado, y se mueve sucesivamente de un estado a otro. Cada uno de estos cambios de estado le llamamos etapa, si actualmente se encuentra en el estado i, y consecuentemente se moverá al estado j, con una probabilidad pi,j, que no depende de que estados antecedieron al estado actual. Si esta es constante se dice que el sistema es estacionario. La probabilidad pi,j, se llama probabilidad de transición. El estado puede permanecer en ese mismo estado con probabilidad pi,i. Una distribución de probabilidad inicial, definida en S, especifica el estado inicial. Usualmente se establece que es un estado inicial 2.12.4.3.1.

Homogeneidad

Una cadena de Markov se dice homogénea si la probabilidad de ir del estado i al estado j en un paso no depende del tiempo en el que se encuentra la cadena, esto es: 𝐏(𝐱 𝐧 = |𝐱 𝐧−𝟏 = 𝐢) = 𝐏(𝐱 𝟏 = 𝐣|𝐱 𝟎 = 𝐢) Para todo n y para cualquier i, j. Si para alguna pareja de estados y para algún tiempo n la propiedad antes mencionada no se cumple diremos que la cadena de Markov es no homogénea

6 7

Todos son números positivos menores o iguales que 1 Todas juntas suman 1 ©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC 2.12.4.3.2.

FCAyS (795)

8

Recurrente

En una cadena de Markov con espacio de estados E, si x ∈ E se define la probabilidad de recurrencia del estado x (que eventualmente pueda a volver a estar en ese estado) 𝐿𝑥 = 𝑃(𝑥𝑛 = 𝑥 𝑝𝑎𝑟𝑎 𝑎𝑙𝑔𝑢𝑛𝑎 𝑛 ∈ 𝑁 | 𝑥0 = 𝑥) Es la probabilidad de que estando en algún estado, pueda volver a estar en él, en algún periodo futuro. Y diremos que: x es estado recurrente si Lx = 1 es seguro que estando en algún estado, pueda volver a estar en él. 2.12.4.3.2.1.

Transitorio

x es transitorio si Lx < 1 hay estados en los que la posibilidad de volver a suceder no es seguro. 2.12.4.3.2.2.

Absorbente

Un estado x es absorbente si 𝑝𝑥,𝑥 = 1 Una clase de comunicación es clase recurrente si todos sus estados son recurrentes. Sea , si x∈Ediremos que: x es cero-recurrente si x es positivo-recurrente si El real se interpreta como el tiempo promedio de recurrencia. 2.12.4.3.3.

Periódico

El periodo de un estado x∈E se define como: donde denota el máximo común divisor. Si d(x)=1 diremos que x es un estado aperiódico. Una cadena de Markov se dice aperiódica si todos sus estados son aperiódicos. 2.12.4.4.

Cadenas irreducibles

Una cadena de Markov se dice irreducible si se cumple cualquiera de las siguientes condiciones (equivalentes entre sí): Desde cualquier estado de E se puede acceder a cualquier otro. Todos los estados se comunican entre sí. C(x)=E para algún x∈E. C(x)=E para todo x∈E. El único conjunto cerrado es el total. La cadena de Ehrenfest o la caminata aleatoria sin barreras absorbentes son ejemplos de cadenas de Markov irreducibles. 2.12.4.5.

Cadenas positivo-recurrentes

Una cadena de Markov se dice positivo-recurrente si todos sus estados son positivo-recurrentes. Si la cadena es además irreducible es posible demostrar que existe un único vector de probabilidad invariante y está dado por:

©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC 2.12.4.6.

FCAyS (795)

9

Cadenas regulares

Ergódico Una cadena de Markov se dice regular (también primitiva o ergódica) si existe alguna potencia positiva de la matriz de transición cuyas entradas sean todas estrictamente mayores que cero. Cuando el espacio de estados E es finito, si P denota la matriz de transición de la cadena se tiene que: donde W es una matriz con todos sus renglones iguales a un mismo vector de probabilidad w, que resulta ser el vector de probabilidad invariante de la cadena. En el caso de cadenas regulares, éste vector invariante es único.

2.12.4.7.

Cadenas absorbentes

Una cadena de Markov con espacio de estados finito se dice absorbente si se cumplen las dos condiciones siguientes: 1. La cadena tiene al menos un estado absorbente. 2. De cualquier estado no absorbente se accede a algún estado absorbente. Si denotamos como A al conjunto de todos los estados absorbentes y a su complemento como D, tenemos los siguientes resultados: 

Su matriz de transición siempre se puede llevar a una de la forma

donde la submatriz Q corresponde a los estados del conjunto D, I es la matriz identidad, 0 es la matriz nula y R alguna submatriz. 

, esto es, no importa en donde se encuentre la cadena, eventualmente terminará en un estado absorbente. 2.12.4.8.

Diagramas de transiciones

Es un grafo dirigido en el que los estados se representan como globos y las transiciones como flechas, rotuladas con una probabilidad, como el que se muestra en la figura siguiente, en la que se ilustra un sistema de Markov con cinco estados posibles: S= {s1, s2, s3, s4 y s5}. La probabilidad condicional o de transición de moverse de un estado a otro se indica en el diagrama como p1,2 (probabilidad de ir al estado 1 al estado 2). Significan una herramienta idónea para entender el problema y asignarle las características de diseño como fase inicial para la elaboración de la matriz de transición.

©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC

FCAyS (795)

10

P2,2

P1,1

P24

P1,2

S1

S2 P2,5

P5,5 S5

P1,5 P3,4

P2,3

P3,2

P3,5 P3,4

S4

S3

P3,3

P3,3

2.12.4.8.1.

Probabilidades de transición

La medida de posibilidades de cambiar de un estado a otro le llamamos probabilidad de transición. Son probabilidades de estar en un nuevo estado, condicionadas de haber estado en otro. La probabilidad de que i sea el siguiente evento generado es una probabilidad condicional: probabilidad de estar en el estado j dado que estaba en el estado i: P(j | i). Esto se llama probabilidad de transición del estado i al estado j que denotaremos por pij. Para describir completamente una cadena de Markov es necesario conocer todos los estados y todas las probabilidades de transición. Todas las posibilidades de salir de un estado hacen el evento seguro, esto es, la suma de las probabilidades de salir de un estado es 1. Esto hace de cada estado y sus posibles transiciones una Distribución de Probabilidad 2.12.4.9.

Matriz de transición

Otro recurso para definir 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 a continuación: Estado Final Inicial 1 2 3 4 5

1 P1,1 0 0 0 0

2

3

4

5

P1,2 0 0 P1,5 P1,1+p1,2+p1,5=1 P2,2 P2,3 0 P2,5 P2,2+p2,3+p2,5=1 P3,2 P3,3 P3,4 P3,5 P3,2+p3,3+p3,4+p3,5=1 0 0 P4,4 P4,5 P4,4+p4,5=1 0 0 0 P5,5 P5,5=1

Generalizando para una matriz de transición de m estados:

©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC

Estado Final Inicial

FCAyS (795)

1

2

11

3 … m

1 P1,1 P1,2 P1,3 … P1,m P= 2 P2,1 P2,2 P2,3 … P2,m 3 P3,1 P3,2 P3,3 … p2m … … … … … … m pm1 pm2 pm2 … pmm 8 Si se define a M como la matriz de transición de un paso : 𝐩𝟏,𝟏 𝐩𝟏𝟐 ⋯ 𝐩𝟏,𝐦 𝐩𝟐,𝟏 𝐩𝟐,𝟐 ⋯ 𝐩𝟐,𝐦 𝐌(𝟏) = 𝐌 = [ ⋮ ⋮ ⋱ ⋮ ] 𝐩𝐦,𝟏 𝐩𝐦,𝟐 ⋯ 𝐩𝐦,𝐦 Donde Pi,j es la probabilidad (condicional) de pasar al estado j habiendo estado en el estado i , lo que ocasiona una suma horizontal de 1 pues hay una certeza de que habiendo estado en el estado i pase a cualquier estado, lo que significa que los estados son mutuamente excluyentes y colectivamente exhaustivos. Cada renglón constituye una distribución de probabilidad, que como tal tiene las siguientes características: 𝟎 ≤ 𝐩𝐢,𝐣 ≤ 𝟏 ∀ 𝐢, 𝐣 ∈ {𝟏, 𝟐, ⋯ , 𝐧} 9 𝟏 = ∑𝐧𝐣=𝟏 𝐩𝐢,𝐣 ∀ 𝐢 ∈ {𝟏, 𝟐, ⋯ , 𝐧} 10 La matriz M, proporciona una completa descripción del proceso de Markov la cual se usará para hacer los análisis correspondientes para responder numerosas preguntas sobre el sistema. 2.12.4.9.1.

Vector de Estados Iniciales

Es un renglón que indica una distribución de probabilidad de estar en los diferentes estados en este ⃗ (𝟎) . Si se multiplica por M, se obtiene las probabilidades en el periodo siguiente. momento 𝐕

⃗ (𝟏) = 𝐕 ⃗ (𝟎) 𝐌 𝐕 Así, empezando en el estado [1,0], que significa haber sido cliente en Suriana, la probabilidad para la etapa siguiente es [𝟏, 𝟎] [ 2.12.4.9.2.

. 𝟗𝟑 . 𝟎𝟖

. 𝟎𝟕 ]=[.93, 07] . 𝟗𝟐

Probabilidad de transición de n pasos.

Una vez que se ha definido la matriz de transición, que es de un solo lapso de tiempo (se trata de una cadena de Markov de primer orden), es posible obtener la matriz de transición a dos o más periodos de tiempo. Para ello hay que considerar todos los estados intermedios posibles

8

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

0 menor o igual que la probabilidad de pasar del estado i al estado j menor o igual que 1 para toda i y j elementos del conjunto cuyos elementos son 1, 2, etcétera, hasta en número m 10 1 es igual a la suma de todas las transiciones posibles desde un estado i, para todos los estados posibles. 9

©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC 2.12.4.9.2.1.

FCAyS (795)

12

Representación de árbol

Para mostrar cómo es que para cada transición se deben tomar los estados intermedios factibles presentamos el siguiente diagrama de árbol. Como todos estos son procesos independientes, pues no hay ninguna relación entre si, las probabilidades de dos eventos consecutivos se multiplican para obtener la probabilidad de que así suceda.

©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC

S1

S2 S1 ⁞ ⁞ Sm

S1

S2 S2 ⁞ ⁞ Sm ⁞ ⁞

⁞ ⁞ S1

Sm

S2 ⁞ ⁞ Sm

©

S1 S2 ⁞ Sm S1 S2 ⁞ Sm ⁞ ⁞ S1 S2 ⁞ . Sm S1 S2 ⁞ Sm S1 S2 ⁞ Sm ⁞ ⁞ S1 S2 ⁞ Sm ⁞ ⁞ S1 S2 ⁞ Sm S1 S2 ⁞ Sm ⁞ ⁞ S1 S2 ⁞ Sm

P11*P11 P11*P12 ⁞ P11*P1m P12*P21 P12*P22 ⁞ P12*P2m ⁞ ⁞ P1m*Pm1 P1m*Pm2 P1m*Pmm P21*P11 P21*P12 ⁞ P21*P1m P22*P21 P22*P22 ⁞ P22*P2m ⁞ ⁞ P2m*Pm1 P2m*Pm2 ⁞ P2m*Pmm ⁞ ⁞ Pm1*P11 Pm1*P12 ⁞ Pm1*P1m Pm2*P21 Pm2*P22 ⁞ Pm2*P2m ⁞ ⁞ Pmm*Pm1 Pmm*Pm2 ⁞ P2m*Pmm

Prof. Raúl Espejo Rodarte (11950)

FCAyS (795)

13

P(S1|S1)= P11*P11 + P12*P21 + … +P1m*Pm1 𝐧

𝐏(𝐒𝟏 | 𝐒𝟏 ) = ∑ 𝐏𝟏,𝐤 ∙ 𝐏𝐤,𝟏 𝐤=𝟏

P(S1|S2)= P11*P12 + P12*P22 + … +P1m*Pm2 𝐧

𝐏(𝐒𝟏 | 𝐒𝟐 ) = ∑ 𝐏𝟏,𝐤 ∙ 𝐏𝐤,𝟐 𝐤=𝟏

P(S1|Sm)= P11*P1m + P12*P2m + … +P1m*Pmm 𝐧

𝐏(𝐒𝟏 | 𝐒𝐧 ) = ∑ 𝐏𝟏,𝐤 ∙ 𝐏𝐤,𝐧 𝐤=𝟏

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC

𝐧

14

FCAyS (795)

𝐏(𝐬𝐢 |𝐬𝐣 ) = ∑ 𝐩𝐢,𝐤 ∙ 𝐩𝐤,𝐣 ∀ 𝐢, 𝐣 ∈ {𝟏, 𝟐, 𝟑. ⋯ , 𝐦} 11 𝐤=𝟏

Conforme al algoritmo de multiplicación de matrices: C=A·B Matrices de dimensiones a * b y b * c, dan como resultado una matriz a * c. En matrices, el orden de los factores si altera el producto. Hay matrices que no se pueden multiplicar 𝐚𝟏,𝟏 𝐚𝟏,𝟐 ⋯ 𝐚𝟏,𝐧 𝐛𝟏,𝟏 𝐛𝟏,𝟐 ⋯ 𝐛𝟏,𝐪 𝐚𝟐,𝟏 𝐚𝟐,𝟐 ⋯ 𝐚𝟐,𝐧 𝐛𝟐,𝟏 𝐛𝟐,𝟐 ⋯ 𝐛𝟐,𝐪 𝐜=[ ⋮ ⋮ ⋱ ⋮ ]∙ ⋮ ⋱ ⋮ ⋮ 𝐚𝐦,𝟏 𝐚𝐦,𝟐 ⋯ 𝐚𝐦,𝐧 [𝐛𝐧,𝟏 𝐛𝐧,𝟐 ⋯ 𝐛𝐧,𝐪 ] 𝐚𝟏,𝟏 ∙ 𝐛𝟏,𝟏 + 𝐚𝟏,𝟐 ∙ 𝐛𝟐,𝟏 + ⋯ + 𝐚𝟏,𝐧 ∙ 𝐛𝐧,𝟏 𝐚𝟏,𝟏 ∙ 𝐛𝟏,𝟐 + 𝐚𝟏,𝟐 ∙ 𝐛𝟐,𝟐 + ⋯ + 𝐚𝟏,𝐧 ∙ 𝐛𝐧,𝟐 𝐚𝟐,𝟏 ∙ 𝐛𝟏,𝟏 + 𝐚𝟐,𝟐 ∙ 𝐛𝟐,𝟏 + ⋯ + 𝐚𝟐,𝐧 ∙ 𝐛𝐧,𝟏 𝐚𝟐,𝟏 ∙ 𝐛𝟏,𝟐 + 𝐚𝟐,𝟐 ∙ 𝐛𝟐,𝟐 + ⋯ + 𝐚𝟐,𝐧 ∙ 𝐛𝐧,𝟐 𝐂= ⋮ ⋮ 𝐚 ∙ 𝐛 + 𝐚 ∙ 𝐛 + ⋯ + 𝐚 ∙ 𝐛 𝐚 ∙ 𝐛 + 𝐚 ∙ 𝐛 [ 𝐦,𝟏 𝟏,𝟏 𝐦,𝟐 𝟐,𝟏 𝐦𝐧 𝐧,𝟏 𝐦,𝟏 𝟏,𝟐 𝐦,𝟐 𝟐,𝟐 + ⋯ + 𝐚𝐦,𝐧 ∙ 𝐛𝐧,𝟐 𝐧

𝐂=

𝐧

∑ 𝐚𝟏,𝐣 ∙ 𝐛𝐣,𝟐

𝐣=𝟏 𝐧

𝐣=𝟏 𝐧

∑ 𝐚𝟐,𝐣 ∙ 𝐛𝐣,𝟏

∑ 𝐚𝟐,𝐣 ∙ 𝐛𝐣,𝟐

𝐣=𝟏

𝐣=𝟏

⋮

𝐧

∑ 𝐚𝐦,𝐣 ∙ 𝐛𝐣,𝟏

[ 𝐣=𝟏

]

𝐧

∑ 𝐚𝟏,𝐣 ∙ 𝐛𝐣,𝟏

𝐧

⋯ ⋯ ⋱ ⋯

⋯

∑ 𝐚𝟏,𝐣 ∙ 𝐛𝐣,𝐪 𝐣=𝟏 𝐧

⋯

∑ 𝐚𝟐,𝐣 ∙ 𝐛𝐣,𝐪 𝐣=𝟏

⋮

⋱

∑ 𝐚𝐦,𝐣 ∙ 𝐛𝐣,𝟐

𝐧

⋮

⋯ ∑ 𝐚𝐦,𝐣 ∙ 𝐛𝐣,𝐪

𝐣=𝟏

𝐣=𝟏

]

Al producto de una matriz cuadrada (necesariamente) por si misma le llamamos cuadrado (notación que se extiende a cualquier potencia). Observando la analogía con las fórmulas obtenidas del árbol anterior: 𝐧

𝐌𝟐 = 𝐌 ∙ 𝐌 =

𝐧

𝐧

∑ 𝐩𝟏,𝐣 ∙ 𝐩𝐣,𝟏

∑ 𝐩𝟏,𝐣 ∙ 𝐩𝐣,𝟐

𝐣=𝟏 𝐧

𝐣=𝟏 𝐧

∑ 𝐩𝟐,𝐣 ∙ 𝐩𝐣,𝟏

∑ 𝐩𝟐,𝐣 ∙ 𝐩𝐣,𝟐

𝐣=𝟏

𝐣=𝟏

⋮

𝐧

∑ 𝐩𝐧,𝐣 ∙ 𝐩𝐣,𝟏

[ 𝐣=𝟏

𝐧

⋯

∑ 𝐩𝟏,𝐣 ∙ 𝐩𝐣,𝐧 𝐣=𝟏 𝐧

⋯

∑ 𝐩𝟐,𝐣 ∙ 𝐩𝐣,𝐧 𝐣=𝟏

⋮

∑ 𝐩𝐧,𝐣 ∙ 𝐩𝐣,𝟐

⋱

⋮

⋯ ∑ 𝐩𝐧,𝐣 ∙ 𝐩𝐣,𝐧

𝐣=𝟏

𝐏(𝐬𝟏 → 𝐬? → 𝐬𝟏 ) 𝐏(𝐬𝟏 → 𝐬? → 𝐬𝟐 ) 𝐏(𝐬𝟐 → 𝐬? → 𝐬𝟏 ) 𝐏(𝐬𝟐 → 𝐬? → 𝐬𝟐 ) 𝐌𝟐 = [ ⋮ ⋮ 𝐏(𝐬𝐦 → 𝐬? → 𝐬𝟏 ) 𝐏(𝐬𝐦 → 𝐬? → 𝐬𝟐 )

𝐧

𝐣=𝟏

]

⋯ 𝐏(𝐬𝟏 → 𝐬? → 𝐬𝐦 ) ⋯ 𝐏(𝐬𝟐 → 𝐬? → 𝐬𝐦 ) ] ⋱ ⋮ ⋯ 𝐏(𝐬𝐦 → 𝐬? → 𝐬𝐦 )

Sj, es igual a la suma desde k=1 hasta k=n de los productos de las probabilidades de transición 𝐩𝐢,𝐤 𝑝𝑜𝑟 𝐩𝐤,𝐣 , para toda i, j elementos del conjunto {1, 2,3,…, n}. 11

Probabilidad de que suceda Si dado que sucedió

©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC

𝐌𝟐 =

(𝟐) 𝐩𝟏,𝟏 (𝟐) 𝐩𝟐,𝟏

(𝟐) 𝐩𝟏,𝟐 (𝟐) 𝐩𝟐,𝟐

(𝟐) [𝐩𝐦,𝟏

(𝟐) 𝐩𝐦,𝟐

⋮

⋮

FCAyS (795)

⋯

15

(𝟐) 𝐩𝟏,𝐧 (𝟐) 𝐩𝟐,𝐧

⋯ ⋱ ⋮ (𝟐) ⋯ 𝐩𝐦,𝐦 ]

Las ecuaciones de Chapman-Kolmogorov proporcionan un método para calcular estas probabilidades de transición de n pasos: 𝐦

(𝐧) 𝐏𝐢,𝐣

(𝐦)

(𝐧−𝐦)

= ∑ 𝐏𝐢,𝐤 ∙ 𝐏𝐤,𝐣

∀ 𝐢, 𝐣, 𝐤

𝐲𝟎≤𝐦≤𝐧

𝐤=𝟎

Estas ecuaciones simplemente señalan que al ir de un estado i al estado j en n pasos, el proceso estará en algún estado k después de exactamente m (menor que n) pasos. Es solo la probabilidad condicional de que, si se comienza en el estado i, el proceso vaya al estado k después de m pasos y después al estado j en n- m pasos. Los casos especiales de m=1 y m=n-1 conducen a las siguientes expresiones, para toda i, j, y n de lo cual resulta que las probabilidades de transición de n pasos se pueden obtener a partir de las probabilidades de transición de un paso de manera recursiva. Para n=2, 𝐧

(𝟐) 𝐌𝐢,𝐣

= ∑ 𝐩𝐢,𝐤 ∙ 𝐌𝐤,𝐣 ∀ 𝐢, 𝐣, 𝐧 𝐤=𝟏

(𝟐)

Note que las 𝐩𝐢,𝐣 son los elementos de la matriz 𝐌𝟐 , pero también debe de observarse que estos elementos, se obtienen multiplicando la matriz de transición de un paso por sí misma; esto es: 𝐌𝟐 = 𝐌 ∗ 𝐌. En términos más generales, se concluye que la matriz de probabilidades de transición de n pasos se puede obtener de la expresión: M(n) = M * M .... M = Mn = MMn-1 = Mn-1 M. Entonces, la matriz de probabilidades de transición de n pasos se puede obtener calculando la n-ésima potencia de la matriz de transición de un paso. Para valores no muy grandes de n, la matriz de transición de n pasos se puede calcular en la forma que se acaba de describir, pero cuando n es grande, tales cálculos resultan tediosos y, más aún, los errores de redondeo pueden causar inexactitudes. 2.12.4.9.2.1.1.

Vector de estados en el periodo k ⃗ (𝟐) 𝐕

⃗ (𝟏) = 𝐕 ⃗ (𝟎) 𝐌 𝐕 ⃗ (𝟏) 𝐌 = (𝐕 ⃗ (𝟎) 𝐌) 𝐌) = 𝐕 ⃗ (𝟎) 𝐌 𝟐 =𝐕 ⃗ 𝐕

©

Prof. Raúl Espejo Rodarte (11950)

(𝐤)

… ⃗ (𝟎) 𝐌 𝒌 =𝐕

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC 2.12.4.9.2.2.

FCAyS (795)

16

Ejemplo : 12

[1] [2]Una tienda de cámaras tiene en almacén un modelo especial de cámara que se puede ordenar cada semana. Sean D1, D2, ... las demandas de esta cámara durante la primera, segunda, ... , semana, respectivamente. Se supone que las Di son variables aleatorias independientes e idénticamente distribuidas que tienen una distribución de probabilidad conocida. Sea X0 el número de cámaras que se tiene en el momento de iniciar el proceso, X1 el número de cámaras que se tienen al final de la semana uno, X2 el número de cámaras al final de la semana dos, etc. Suponga que X0 = 3. El sábado en la noche la tienda hace un pedido que le entregan el lunes en el momento de abrir la tienda. La tienda hace un pedido que le entregan el lunes en el momento de abrir la tienda. La tienda usa la siguiente política para ordenar: Si no hay cámaras en inventario al final de la semana, se surten 3. De otra manera, no se surten cámaras. Se supone que las ventas se pierden cuando la demanda excede el inventario. Entonces, {Xt} para t=0, 1, ... es un proceso estocástico de la forma que se acaba de describir. Los estados posibles del proceso son los enteros 0, 1, 2, 3 que representan el número posible de cámaras en inventario al final de la semana. La demanda se conduce de manera exponencial (todos los eventos son independientes entre si), que para explicar el número de clientes que vienen por semana es la distribución de Poisson que tiene dos parámetros: la media (λ que es el promedio de clientes semanales en un largo lapso de tiempo), y el número de clientes semanales, Así la probabilidad de que lleguen x clientes semanales, cuando en promedio llegan λ es: 𝛌𝐱 𝐞−𝛌 𝐏(𝐱; 𝛌) = 𝐱! Se tiene que la demanda cuando se tiene una esperanza (media) de 3, λ=3 A B C D 1 _λ = 3 2 0 0.04978707 =POISSON(B2,$B$1,FALSO) 3 1 0.14936121 =POISSON(B2,$B$1,FALSO) X= 4 2 0.22404181 =POISSON(B2,$B$1,FALSO) 5 3 o mas 0.57680992 =1-SUMA(C2:C4) 6 2 o mas 0.80085173 =1-SUMA(C2:C3) 7 1 o mas 0.95021293 =1- C2 Para que la semana termine con i cámaras, dado que la semana anterior terminó con j cámaras: 0 1 2 3 0 P(DEMANDA ≥3) P(DEMANDA =2) P(DEMANDA =1) P(DEMANDA =0) 1 P(DEMANDA ≥1) P(DEMANDA =0) 0 0 2 P(DEMANDA ≥2) P(DEMANDA =1 P(DEMANDA =0) 0 3 P(DEMANDA ≥3) P(DEMANDA =2) P(DEMANDA =1) P(DEMANDA =0) La matriz de transición es: 0.57680992 0.22404181 0.14936121 0.04978707 0.95021293 0.04978707 0 0 M= 0.80085173 0.14936121 0.04978707 0 0.57680992 0.22404181 0.14936121 0.04978707

{

12

En la resolución numérica de este ejemplo usaremos el ®Excel de ®MicroSoft para su programación ©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC

17

FCAyS (795)

0.69393096 0.17384708 0.10102554 0.03119643 0.59540056 0.21536618 0.14192495 0.04730832 M(2) = M2= 0.64373623 0.19429678 0.12209493 0.03987206 0.69393096 0.17384708 0.10102554 0.03119643 Así, dado que tiene una cámara al final de una semana, la probabilidad de que no haya cámaras en (𝟐) inventario dos semanas después es 0.5954 ; es decir, 𝐏𝟏,𝟎 = 𝟎. 𝟓𝟗𝟓𝟒 . De igual manera, dado que se tienen dos cámaras al final de una semana, la probabilidad de que haya tres cámaras en el almacén dos (𝟐) semanas después es 𝐏𝟐,𝟑 = 𝟎. 𝟎𝟑𝟗𝟖𝟕 La matriz de transición de cuatro pasos también se puede obtener de la siguiente manera: M(4) = M4 = M(2) * M(2) 2.12.4.9.3.

Estado estacionario

El cálculo de la probabilidad de que sistema se encuentre en algún estado, no depende del estado inicial, y puede considerarse que es la tendencia del estado al transcurrir mucho tiempo. En el ejemplo del almacén de cámaras, se observa que ya en la potencia 10 todos los renglones se parecen, esto implica que sin importar como termine en la semana anterior, dentro de diez semanas solo se puede decir cuál es la probabilidad que tiene cada uno de los estados posibles. 0.67026158 0.18374318 0.11087649 0.03511875 0.67026012 0.18374379 0.1108771 0.03511899 M10 = 0.67026085 0.18374349 0.11087679 0.03511887 0.67026158 0.18374318 0.11087649 0.03511875 Siempre y cuando la matriz no sea periódica siempre se llega a la situación de que al multiplicarla una vez más por si misma todos los renglones iguales, ya no cambian. Sea M la matriz de transición de una cadena de m estados. Existe un vector    1 ,  2 ,,  m  Llamado distribución de estado estable o distribución de equilibrio tal que

 1  2 Lim( M )  1  2   k     2  1 k

 m   m        m 

En particular

 1  2   2  1      2  1

M

a

M

a 1

   M

  m   1  2   m   1  2         m   1  2

  m   p1,1 p1, 2  p1,m      m   p 2,1 p 2, 2  p 2,m               m   p m,1 p m, 2  p m,m   0  1 ( p  1)   2 p     m

   p  p  p    p   p     p  0  p   ( p 1

2

1

1, 2

1

2

1,1

2

2, 2

m

2,1

m

m, 2

m,1

1,1

1

1, 2

2

2, 2

2,1

 1)     m p

m, 2

…

p

m,1

…

… ©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

  p m

1

1, m

 2

p

2, m

 m

UABC

p

m,m

 0  1 p   2 1, m

18

FCAyS (795)

p

2, m

 m ( p

m,m

 1)

Y, por tratarse de una distribución de probabilidad: 1   1  2  m Hay m+1 ecuaciones y m incógnitas, desechamos una de ellas, ya que las primeras m ecuaciones no son linealmente independientes y la sustituimos por la propiedad de distribución de probabilidad (los renglones suman 1, última ecuación), y expresando el sistema de ecuaciones matricialmente tenemos

 1

2

 p1,( m1) 1 p1, 2  p1,1  1  p p 2, 2  1  p1,( m1) 1 2 ,1    m   0 0  1         p pm, 2  p m,m 1  m ,1  1

 p1,( m1) 1 p1, 2  p1,1  1  p   1  2   m   0 0  1  2,1 p2,2  1  p1,(m1) 1    p pm, 2  p m,m 1  m ,1  La distribución de probabilidad resultante (el estado estable) es el último renglón de la matriz invertida En el caso de una Cadena de Markov periódica, no existe esta tendencia, pues fluctúa de estado en estado, sin embargo al aplicarle el procedimiento anterior se encuentra en la solución la probabilidad de que el sistema se encuentre en dicho estado. Para el segundo ejemplo periódico se tiene 0.3333333, 0.0333333, 0.3, 0.2166667, 0.1166667 como las probabilidades de que el sistema se encuentre en el estado 1, 2, 4 y 5, respectivamente, como se hace notar el estado 1 se repite cada tres etapas, estando ahí 1 de cada tres: 1/3 del tiempo. La programación ®SciLab es la siguiente: function Mss=MarkovSS(M); Mss=[M-eye(),ones(length(M)^.5,1)]; Mss=inv(Mss(:,2:$)); Mss=Mss($,:); endfunction 2.12.4.9.3.1.

P=

0.57680992 0.95021293 0.80085173 0.57680992

Ejemplos

0.22404181 0.04978707 0.14936121 0.22404181

0.14936121 0 0.04978707 0.14936121

-0.42319008 0.22404181 0.14936121 0.95021293 -0.95021293 0 P-I = 0.80085173 0.14936121 -0.95021293 0.57680992 0.22404181 0.14936121 Sustituyendo la última columna por unos

-0.42319008 0.22404181 0.95021293 -0.95021293 ©

Prof. Raúl Espejo Rodarte (11950)

0.04978707 0 0 0.04978707 0.04978707 0 0 -0.95021293

0.14936121 0

[email protected] 6461766600x173

1 1

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC

0.80085173 0.57680992

19

FCAyS (795)

0.14936121 -0.95021293 0.22404181 0.14936121

1 1

Invirtiendo la matriz -1 -8.763E-17 -8.763E-17 1 -0.29461996 -0.85902501 0.1166861 1.03695887 -0.18374333 0.05834304 -0.91736805 1.04276834 0.67026124 0.18374333 0.11087664 0.0351188 Que después de premultiplicar por [0, 0, 0, 1] obtenemos: 0.67026124 0.18374333 0.11087664 0.0351188 2.12.4.9.3.1.1.

Ejercicio.

.5939942 .2706706 .1353353  entonces 0  .5939942 .2706706 .1353353

Si M  .8646647 .1353353 

- .4060058 .2706706 1  1  2  3  0 0 1  .8646647 - .8646647 1  .5939942 .2706706 1 -1 0 1     0 0 1  - .2384058 - .8807971 1.1192029  .6585236 .2384058 .1030706 



1



 .6585236 .2384058 .1030706

2.12.4.9.3.1.2.

.91 1 .1     entonces     0 1   .8  .2 1

.9 M  .2

  1

©

Ejercicio.

1

2

1

2



  10 10   1 1  3   2  0 1   3     2 1  .3  .2  .1 3   3   3

  0 1 

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

0 1

1  1   .1  .2  .2  .1 

1   .6 .3 3    _

_

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC 2.12.4.9.3.1.3.

FCAyS (795)

Ejercicio.

.1 .6 .3 M  .2 .5 .3 .3 .4 .3 1  .8181... .1818...   0 0 1   .0909...  1.0909... 1   .2 .5 .3  .20909... .49090... .3 2.12.4.9.3.1.4.

20

    1

2

3

.1  1 .6 1  0 0 1  .2 .5  1 1  .3 .4 1

1

Ejercicio.

Una cola M/M/1/n como se verá en la sección 2.12.5, se puede simular de la siguiente manera: Cada estado corresponde a la cantidad de clientes en el sistema, siendo los estados diferentes {0,1,…}, en el que los estados de valores muy grandes se descartan por tener una probabilidad ínfima. La matriz de estados será: Según la distribución de probabilidad de Poisson, con esperanza λ las probabilidades de que ocurra un número de eventos X es de:  x  e P ( ; x )  x! La probabilidad de que no arribe nadie es de:

  P( ;0)  e   e 0! 

0



La probabilidad de que arribe un cliente (es el complemento de que no llegue ningún cliente) 1-eλ. La probabilidad de que uno o más clientes sean atendidos es de 1-eµ. En el estado inicial cuando hay cero clientes en la línea, las flechas que salen del globo 0 deben sumar 1, por lo que la flecha de transición 0,0 tiene una probabilidad de 1-(1-eλ)=eλ.

e -λ

1-e-λ

-λ

-λ

-µ

e + e -1

e-λ+ e-µ-1 1-e

0

-λ

1-e

n

n-1

1

1-e-µ

e -µ

1-e-µ

-µ

1-e

La capacidad del sistema es para n clientes en la cola, por eso la cadena termina ahí…    e  1 e  0     0   0  0  ©



0 1 e   e  e  1 1  e  1 e e  e 1 





 0 0 0

Prof. Raúl Espejo Rodarte (11950)







 0 0 0

      

          e  e   1 1  e     1 1 e e e  1e  0 e  1 e 0 0 0 

[email protected] 6461766600x173

0 0 0 

0 0 0  0

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC

FCAyS (795)

Para programación en SCILAB: la=.3; //λ mu=.375;//μ N=256; mt=zeros(N,N); mt(1,1)=exp(-la); mt(1,2)=1-exp(-la); mt(N,N-1)=1-exp(-mu); mt(N,N)=exp(-mu); for k=2:N-1; mt(k,k)=exp(-la)+exp(-mu)-1; mt(k,k-1)=1-exp(-mu); mt(k,k+1)=1-exp(-la); end; M=(mt-eye()); M=[M(:,1:N-1),ones(N,1)]; M=inv(M); M=M(N,:);plot(M) em=M*(0:N-1)'// Cálculo de la esperanza 7.1735632 vm= (M*((-em:N-1-em)').^2)^.5// Cálculo de la Desviación estándar

21

8.4180513

Conforme a la sección 2.12.4.7 Principales Relaciones,

Lq 



2

  (   )



32 9 9    3.75 * (3.75  3) 3.75 * .75 2.1825 2.12.4.9.3.1.5.

Ejercicio.

Suponga que toda la industria de refrescos produce dos sodas. Cuando una persona ha comprado la sabor 1, hay una probabilidad de 90 % de que su siguiente compra se de sabor 1. Si una persona compró sabor 2, hay un 80 % de probabilidades que su próxima compra sea de sabor 2. 2⁄ −.2 0 ] ∙ [ ] = [ 3] 1⁄ −.1 1 3 Por lo tanto, después de largo tiempo, hay probabilidad 2/3 de que una persona dada compre soda 1 y 1/3 de probabilidad de que una persona compre soda 2. .9 𝑃=[ .2

.1 ] .8

©

𝜋1 1 . 9 − 1 . 2 −1 0 −.1 . 2 −1 0 1 [𝜋 ] = [ ] ∙[ ]=[ ] ∙ [ ] = −.3 [ 2 1 1 1 1 1 1 −1

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC 2.12.4.9.3.1.6.

−5⁄ 5⁄ .1 .9 9 9] ⌈ ⌉ ⇛≫ [ .9 .1 .5 .5

©

.5 ⌈ .9

Prof. Raúl Espejo Rodarte (11950)

22

FCAyS (795)

Ejercicios.

−5⁄ .5 7 ⌉ ⇛≫ [ 9⁄ .1 14

5⁄ 7] 5⁄ 14

[email protected] 6461766600x173

⌈

−2 .4 .6 ⌉ ⇛≫ [ ⁄3 .9 .1 .6

2⁄ 3] .4

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC 2.12.4.9.4.

23

FCAyS (795)

Tiempo de primer paso

Es la esperanza (o promedio a largo plazo) del número de transiciones que tienen que transcurrir para pasar del estado i al estado j, por primera vez. 2.12.4.9.5.

Recurrencia

Es la esperanza del número de transiciones que tienen que transcurrir para regresar a un estado dado. Es el tiempo de primer paso de ir del estado i al estado i. Si todos los estados del sistema tienen tiempos de recurrencia finitos, se dice que es recurrente. Se puede demostrar que es el inverso de πn . (𝐧)

El estado i es Recurrente si ∑∞ 𝐧=𝟏 𝐟𝐢,𝐢 = 𝟏 Siempre hay posibilidad de regresar al estado i

es Absorbente si ∑∞ 𝐧=𝟏 𝒑𝐢,𝐢 = 𝟏 Una vez que el proceso se encuentra en el estado i no abandona (𝐧)

es Transitorio si ∑∞ 𝐧=𝟏 𝐟𝐢,𝐢 < 𝟏 Una vez que el proceso se encuentra en el estado i existe una probabilidad >0 de no regresar 2.12.4.9.5.1.

Tiempo de primer paso

En una secuencia dada, como, por ejemplo: s0=1, s1=3, s2=0, s3=2, s4=1, s5=3, s6=2, … , el tiempo de primer paso para ir al estado 3 al estado 1 es de 1 semana, el tiempo de primer paso para ir del estado 3 al estado 2 es de 2 semanas y el tiempo de recurrencia del estado 3 es de 4 semanas (el tiempo de primera pasada del estado 3 al estado 3). Los tiempos de primer paso son variables aleatorias, que representan el promedio de todos los tiempos de paso del estado i al estado j. Este promedio que es la suma de todos los tiempos posibles multiplicados por su probabilidad se le llama Esperanza matemática. n Sea fi,j la probabilidad de que el tiempo de primera pasada del estado i al estado j sea n. Si n > 1, entonces el tiempo de primera pasada es n si la primera transición es del estado i a otro estado k y el tiempo de pasada del estado intermedio k a estado j es n-1, estas probabilidades obedecen a las siguientes relaciones recursivas: (𝟏)

𝒇𝒊,𝒋 = 𝒑𝟏𝒊,𝒋 = 𝒑𝒊,𝒋 (𝟐)

(𝟏) (𝟏)

𝒇𝒊,𝒋 = ∑ 𝒑𝒊,𝒌 𝒇𝒌,𝒋 𝒌≠𝒋 (𝟑) 𝒇𝒊,𝒋

(𝟏) (𝟐)

= ∑ 𝒑𝒊,𝒌 𝒇𝒌,𝒋 ⋮

©

(𝒏)

𝒌≠𝒋

Estas probabilidades satisfacen las siguientes relaciones recursivas: (𝟏)

𝐟𝐢,𝐣 = 𝐩𝟏𝐢,𝐣 = 𝐩𝐢,𝐣

(𝟐)

(𝟑)

(𝒏)

(𝟏)

𝒇𝒊,𝒋 = 𝒑𝟐𝒊,𝒋 − 𝒇𝒊,𝒋 𝒑𝒊,𝒋 (𝟏) (𝟐)

(𝟐)

𝒇𝒊,𝒋 = 𝒑𝟑𝒊,𝒋 − 𝒇𝒊,𝒋 𝒑𝒊,𝒋 − 𝒇𝒊,𝒋 𝒑𝒊,𝒋 ⋮ (𝟏) (𝒏−𝟏)

𝒇𝒊,𝒋 = 𝒑𝒏𝒊,𝒋 − 𝒇𝒊,𝒋 𝒑𝒊,𝒋 (𝒏) 𝒇𝒊,𝒋

=

(𝒏) 𝒑𝒊,𝒋

(𝟐) (𝒏−𝟐)

− 𝒇𝒊,𝒋 𝒑𝒊,𝒋 𝒏−𝟏

(𝒏−𝟏)

⋯ − 𝒇𝒊,𝒋

𝒑𝒊,𝒋

(𝒌) (𝒏−𝒌)

− ∑ 𝒇𝒊,𝒋 𝒑𝒊,𝒋 𝒌=𝟏

Lo que permite el cálculo recursivo de la probabilidad del tiempo de primer paso del estado i al estado j en n pasos, usando como datos las probabilidades de transición de un paso. En el ejemplo, la distribución de probabilidad de los tiempos de primer paso del estado 3 al estado 0 se obtiene como sigue: En el ejemplo del almacén de fotografía: Con λ=1:

. 𝟎𝟖 𝑴 = [. 𝟔𝟑𝟐 . 𝟐𝟔𝟒 . 𝟎𝟖

𝒌≠𝒋

Prof. Raúl Espejo Rodarte (11950)

(𝟏) (𝒏−𝟏)

𝒇𝒊,𝒋 = ∑ 𝒑𝒊,𝒌 𝒇𝒌,𝒋

[email protected] 6461766600x173

. 𝟏𝟖𝟒 . 𝟑𝟔𝟖 . 𝟑𝟔𝟖 . 𝟑𝟔𝟖 𝟎 𝟎 ] . 𝟑𝟔𝟖 . 𝟑𝟔𝟖 𝟎 . 𝟏𝟖𝟒 . 𝟑𝟔𝟖 . 𝟑𝟔𝟖 (𝟏) (𝟏) 𝒇𝒊,𝒋 = 𝒑𝒊,𝒋

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC (𝟏) 𝒇𝟏,𝟎

=. 𝟔𝟑𝟐

(𝟏) 𝒇𝟐,𝟎

(𝟏) 𝒇𝟑,𝟎

=. 𝟐𝟔𝟒

=. 𝟎𝟖

(𝟐) 𝒇𝒊,𝒋

(𝟐)

𝒇𝟑,𝟎 =

(𝟐)

(𝟏) = ∑ 𝒑𝒊,𝒌 𝒇𝒌,𝒋 𝒌≠𝒋 (𝟐) (𝟏) 𝒇𝟑,𝟎 = ∑ 𝒑𝟑,𝒌 𝒇𝒌,𝟎 𝒌≠𝟎 (𝟏) (𝟏) 𝒑𝟑,𝟏 𝒇𝟏,𝟎 + 𝒑𝟑,𝟐 𝒇𝟐,𝟎 +

(𝟏)

𝒑𝟑,𝟑 𝒇𝟑,𝟎

Que es la probabilidad de pasar del estado 3 al estado 0 en una pasada y en dos pasadas, respectivamente. Para cada transición i,j, las diferentes, tienen las propiedades: (𝒏)

𝟎 ≤ 𝒇𝒊,𝒋 ≤ 𝟏 ∞

(𝒏)

∑ 𝒇𝒊,𝒋 ≤ 𝟏 𝒏=𝟏

Si esta suma es estrictamente menor que uno significa que existe una probabilidad de que el sistema puede nunca alcanzar el estado j desde el estado i. Si la suma si es 1, entonces se dice que esa (𝐧)

transición es recurrente, y las 𝐟𝐢,𝐣 para toda n, constituyen una distribución de probabilidad para la variable aleatoria: tiempo de primera pasada (la esperanza del número de transiciones en que el sistema termina en el estado j empezando en el estado i), que se define como sigue: ∞

𝛍𝐢,𝐣 =

(𝐧)

𝐬𝐢 ∑ 𝐟𝐢,𝐣 < 𝟏 . . 𝐧=𝟏 . . . . . . .

∞

∑𝐧

∞

(𝐧) 𝐟𝐢,𝐣

{𝐧=𝟏 (𝒏) 𝒔𝒊 ∑∞ 𝒏=𝟏 𝒇𝒊,𝒋 = 𝟏,

24

𝛍𝐢,𝐣 = 𝟏 + ∑ 𝐩𝐢,𝐤 𝛍𝐤,𝐣 𝐤≠𝐣

𝒇𝟑,𝟎 =. 𝟏𝟖𝟒 ∗. 𝟔𝟑𝟐+. 𝟑𝟔𝟖 ∗. 𝟐𝟔𝟒+. 𝟑𝟔𝟖 ∗. 𝟎𝟖 =. 𝟐𝟒𝟑

∞

FCAyS (795)

(𝐧)

𝐬𝐢 ∑ 𝐟𝐢,𝐣 = 𝟏 𝐧=𝟏

}

𝝁𝒊,𝒋

satisface

Cuya primera transición puede ser al estado j (1), o a cualquier otro estado k, si la primera transición es a un estado diferente a j (k≠j) lo que ocurre con probabilidad pi,k, sumando todas las posibilidades. 𝝁𝟑,𝟎 = 𝟏 + 𝒑𝟑,𝟏 𝝁𝟏,𝟎 + 𝒑𝟑,𝟐 𝝁𝟐,𝟎 + 𝒑𝟑,𝟑 𝝁𝟑,𝟎 𝝁𝟐,𝟎 = 𝟏 + 𝒑𝟐,𝟏 𝝁𝟏,𝟎 + 𝒑𝟐,𝟐 𝝁𝟐,𝟎 + 𝒑𝟐,𝟑 𝝁𝟑,𝟎 𝝁𝟏,𝟎 = 𝟏 + 𝒑𝟏,𝟏 𝝁𝟏,𝟎 + 𝒑𝟏,𝟐 𝝁𝟐,𝟎 + 𝒑𝟏,𝟑 𝝁𝟑,𝟎 𝟏 = 𝒑𝟑,𝟏 𝝁𝟏,𝟎 + 𝒑𝟑,𝟐 𝝁𝟐,𝟎 + 𝒑𝟑,𝟑 𝝁𝟑,𝟎 − 𝝁𝟑,𝟎 −𝟏 = 𝒑𝟑,𝟏 𝝁𝟏,𝟎 + 𝒑𝟑,𝟐 𝝁𝟐,𝟎 + (𝒑𝟑,𝟑 − 𝟏)𝝁𝟑,𝟎 (𝒑𝟏,𝟏 −𝟏)𝝁𝟏,𝟎 + 𝒑𝟏,𝟐 𝝁𝟐,𝟎 +𝒑𝟏,𝟑 𝝁𝟑,𝟎 = −𝟏 𝒑𝟐,𝟏 𝝁𝟏,𝟎 + (𝒑𝟐,𝟐 − 𝟏)𝝁𝟐,𝟎 +𝒑𝟐,𝟑 𝝁𝟑,𝟎 = −𝟏 𝒑𝟑,𝟏 𝝁𝟏,𝟎 + 𝒑𝟑,𝟐 𝝁𝟐,𝟎 + (𝒑𝟑,𝟑 − 𝟏)𝝁𝟑,𝟎 = −𝟏 𝒑𝟏,𝟏 − 𝟏 𝒑𝟏,𝟐 𝒑𝟏,𝟑 𝝁𝟏,𝟎 −𝟏 𝝁 𝒑 𝒑 − 𝟏 𝒑 [ 𝟐,𝟏 𝟐,𝟐 𝟐,𝟑 ] ∗ [ 𝟐,𝟎 ] = [−𝟏] 𝝁𝟑,𝟎 𝒑𝟑,𝟏 𝒑𝟑,𝟐 𝒑𝟑,𝟑 − 𝟏 −𝟏 𝝁𝟏,𝟎 𝒑𝟏,𝟑 𝟏 𝟎 𝟎 𝒑𝟐,𝟑 ] − [𝟎 𝟏 𝟎]) ∗ [𝝁𝟐,𝟎 ] 𝒑𝟑,𝟑 𝝁𝟑,𝟎 𝟎 𝟎 𝟏 −𝟏 = [−𝟏] −𝟏 Si agregamos el primer renglón por inducción, y reordenamos para evitar los signos: 𝟎 𝒑𝟎,𝟏 𝒑𝟎,𝟐 𝒑𝟎,𝟑 𝟏 𝟎 𝟎 𝟎 𝟎 𝒑𝟏,𝟏 𝒑𝟏,𝟐 𝒑𝟏,𝟑 [𝟎 𝟏 𝟎 𝟎] − 𝟎 𝒑 𝟎 𝟎 𝟏 𝟎 𝟐,𝟏 𝒑𝟐,𝟐 𝒑𝟐,𝟑 𝟎 𝟎 𝟎 𝟏 [𝟎 𝒑𝟑,𝟏 𝒑𝟑,𝟐 𝒑𝟑,𝟑 ]) ( 𝝁𝟎,𝟎 𝟏 𝝁𝟏,𝟎 ∗ [𝝁 ] = [𝟏] 𝟏 𝟐,𝟎 𝝁𝟑,𝟎 𝟏 𝒑𝟏,𝟏 ([𝒑𝟐,𝟏 𝒑𝟑,𝟏

𝒑𝟏,𝟐 𝒑𝟐,𝟐 𝒑𝟑,𝟐

unívocamente la ecuación:

©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC

Que para despejar, la matriz que premultiplica, pasa premultiplicando su inversa: 𝛍𝟎,𝟎 𝛍𝟏,𝟎 [𝛍 ] = 𝟐,𝟎 𝛍𝟑,𝟎

(

𝟏 [𝟎 𝟎 𝟎

𝟎 𝟏 𝟎 𝟎

𝟎 𝟎 𝟏 𝟎

𝟎 𝟎 𝟎] − 𝟎 𝟎 𝟎 𝟏 [𝟎

𝐩𝟎,𝟏 𝐩𝟏,𝟏 𝐩𝟐,𝟏 𝐩𝟑,𝟏

𝐩𝟎,𝟐 𝐩𝟏,𝟐

𝐩𝟎,𝟑 𝐩𝟏,𝟑

𝐩𝟐,𝟐 𝐩𝟑,𝟐

𝐩𝟐,𝟑 𝐩𝟑,𝟑 ] )

𝐩𝟎,𝟐 𝐩𝟏,𝟐

𝐩𝟎,𝟑 𝐩𝟏,𝟑

𝐩𝟐,𝟐 𝐩𝟑,𝟐

𝐩𝟐,𝟑 𝐩𝟑,𝟑 ] )

Y para los demás 𝛍𝟎,𝟏 𝛍𝟏,𝟏 [𝛍 ] = 𝟐,𝟏 𝛍𝟑,𝟏

(

𝟏 [𝟎 𝟎 𝟎

𝟎 𝟏 𝟎 𝟎

𝟎 𝟎 𝟏 𝟎

𝐩𝟎,𝟎 𝟎 𝟎] − 𝐩𝟎,𝟎 𝐩𝟎,𝟎 𝟎 𝟏 [𝐩𝟎,𝟎

𝟎 𝟎 𝟎 𝟎

−𝟏

𝟏 ∗ [𝟏] 𝟏 𝟏 −𝟏

𝟏 ∗ [𝟏] 𝟏 𝟏

𝝁𝟏,𝟎 = 𝟏 + 𝒑𝟏,𝟏 𝝁𝟏,𝟎 + 𝒑𝟏,𝟐 𝝁𝟐,𝟎 + 𝒑𝟏,𝟑 𝝁𝟑,𝟎 𝝁𝟐,𝟎 = 𝟏 + 𝒑𝟐,𝟏 𝝁𝟏,𝟎 + 𝒑𝟐,𝟐 𝝁𝟐,𝟎 + 𝒑𝟐,𝟑 𝝁𝟑,𝟎 𝝁𝟑,𝟎 = 𝟏 + 𝒑𝟑,𝟏 𝝁𝟏,𝟎 + 𝒑𝟑,𝟐 𝝁𝟐,𝟎 + 𝒑𝟑,𝟑 𝝁𝟑,𝟎 𝝁𝟏,𝟎 = 𝟏+. 𝟑𝟔𝟖 𝝁𝟏,𝟎 + 𝟎 𝝁𝟐,𝟎 + 𝟎 𝝁𝟑,𝟎 𝝁𝟐,𝟎 = 𝟏+. 𝟑𝟔𝟖 𝝁𝟏,𝟎 +. 𝟑𝟔𝟖 𝝁𝟐,𝟎 + 𝟎 𝝁𝟑,𝟎 𝝁𝟑,𝟎 = 𝟏+. 𝟏𝟖𝟒 𝝁𝟏,𝟎 +. 𝟑𝟔𝟖 𝝁𝟐,𝟎 +. 𝟑𝟔𝟖 𝝁𝟑,𝟎 𝝁𝟏,𝟎 = 𝟏+. 𝟑𝟔𝟖 𝝁𝟏,𝟎 𝟏 = = 𝟏. 𝟓𝟖𝟐𝟐𝟕𝟖𝟓 𝟏−. 𝟑𝟔𝟖

𝝁𝟐,𝟎 = 𝟏+. 𝟑𝟔𝟖 ∗ 𝟏. 𝟓𝟖𝟐𝟐𝟕𝟖𝟓+. 𝟑𝟔𝟖 𝝁𝟐,𝟎 𝝁𝟐,𝟎 = 𝟏. 𝟓𝟖𝟐𝟐𝟕𝟖𝟓+. 𝟑𝟔𝟖 𝝁𝟐,𝟎 𝟏. 𝟓𝟖𝟐𝟐𝟕𝟖𝟓 𝝁𝟐,𝟎 = = 𝟐. 𝟓𝟎𝟑𝟔𝟎𝟓𝟐 𝟏−. 𝟑𝟔𝟖 𝝁𝟑,𝟎 = 𝟏+. 𝟏𝟖𝟒 ∗ 𝟏. 𝟓𝟖𝟐𝟐𝟕𝟖𝟓+. 𝟑𝟔𝟖 ∗ 𝟐. 𝟓𝟎𝟑𝟔𝟎𝟓𝟐+. 𝟑𝟔𝟖 𝝁𝟑,𝟎 𝝁𝟑,𝟎 = 𝟐. 𝟐𝟏𝟐𝟒𝟔𝟔+. 𝟑𝟔𝟖 𝝁𝟑,𝟎 𝟐. 𝟐𝟏𝟐𝟒𝟔𝟔 𝝁𝟑,𝟎 = = 𝟑. 𝟓𝟎𝟎𝟕𝟑𝟕𝟑 𝟏−. 𝟑𝟔𝟖 La esperanza para saber cuántos periodos se han de esperar hasta que el sistema termine con 0 cámaras: F0= π0μ0,0+ π1μ1,0+ π2μ2,0+ π3μ3,0. F0= .2856541*3.5007373 + .2848349*1.5822785 + .2631808* .5036052 + .1663302*3.5007373 = 2.6918673 ©

Prof. Raúl Espejo Rodarte (11950)

25

Cada 2.7 semanas se termina con 0 artículos.

Programación Scilab //mi ejemplo con lambda =3

p=[0.57680992 0.22404181 0.14936121 0.04978707; 0.95021293 0.04978707 0 0 ; 0.80085173 0.14936121 0.04978707 0 ; 0.5768 0.2240 0.1493 0.0497];

//Ejemplo del Hillier, mi ejemplo con lambda=1

Etcétera Para el ejemplo que estamos usando, todos los estados son recurrentes:

𝝁𝟏,𝟎

FCAyS (795)

P=[.08 .632 .264 .08

.184 .368 .368; .368 0 0; .368 .368 0; .184 .368 .368];

//En el cálculo de fij, probabilidad de una pasada de ir del estado i al estado j

for k=1:4; P0=P;P0(:,k)=[0,0,0,0]’;//lambda=1 P0=inv(eye(4,4)-P0)*ones(4,1); U(:,k)=P0;//Columna k de U P0=p;P0(:,k)=[0,0,0,0]’;//lambda=3 P0=inv(eye(4,4)-P0)*ones(4,1); u(:,k)=P0;//Columna k de u end; pp=diag(u)’;PP=diag(U)’; pi=diag(ones(4,4)./u)’;PI=diag(ones(4,4)./U)’;

Resultados Scilab pp = 1.4919556 4.675136 8.2737728 28.47478

PP

1.0523957 5.4423746 9.3261685 29.527175 1.2178187 4.9926607 9.0190331 29.692599 1.4919556 4.675136 8.2737728 28.47478 = 3.5007373 3.9727943 3.5085305 6.0121357 1.5822785 3.510806 5.090809 7.5944142 2.5036052 3.2418002 3.7996698 8.5157409 3.5007373 3.9727943 3.5085305 6.0121357

u =1.4919556 U =3.5007373 pi =0.6702612 PI =0.2856541 2.12.4.9.6.

5.4423746 9.0190331 28.47478 3.510806 3.7996698 6.0121357 0.1837433 0.1108766 0.0351188 0.2848349 0.2631808 0.1663302

Cadenas Periódicas

Se llama así a la cadena que al cabo de algunos pasos regresa al mismo estado. El número de pasos que tarda en repetirse se llama periodo. A continuación se muestra la matriz de transición de una Cadena de Markov de periodo igual a dos.

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC

0 .1 .9 1 0 0 2 𝑀 = [1 0 0 ] 𝑀 = [0 . 1 . 9] 1 0 0 0 .1 .9 0 .1 .9 𝑀 3 = [1 0 0 ] . . . 1 0 0 Aquí se muestra una cadena de periodo de tres 0 .1 .9 0 0 0 0 0 .2 .8 𝐵 = 0 0 0 .7 .3 1 0 0 0 0 [1 0 0 0 0 ] 0 0 0 . 65 . 35 1 0 0 0 0 0 0 0 𝐵2 = 1 0 0 .1 .9 0 0 [0 . 1 .9 0 0 ] 1 0 0 0 0 0 .1 .9 0 0 0 𝐵3 = 0 . 1 . 9 0 0 0 0 . 65 . 35 [0 0 0 . 65 . 35] 0 .1 .9 0 0 0 0 0 .2 .8 𝐵4 = 0 0 0 . 7 . 3 1 0 0 0 0 [1 0 0 0 0 ] 2.12.4.9.7.

Estados Absorbentes

Un estado de una cadena de Markov se le denomina absorbente si es imposible abandonarlo. Una cadena de Markov se dice absorbente si tiene al menos un estado absorbente accesible desde cualquier estado. Un estado que no es absorbente se dice que es transitorio. 2.12.4.9.7.1.

Ejemplo

El camino de Briagoberto Un borracho solo camina a lo largo de la calle Ruiz. Él vive en la esquina Ruiz y Boulevard Costero y la cantina está en la calle 4. En cualquier esquina su desorientación es tal que puede caminar hacia el Oeste o hacia el Este con la misma probabilidad. Si llega a su casa su vieja lo retiene y lo acuesta a dormir. Si llega al bar, se embriaga de tal modo que se queda tirado ahí. ©

Prof. Raúl Espejo Rodarte (11950)

FCAyS (795)

26

La matriz de transición es la siguiente, con estados absorbentes en 0 y en 4: 0 1 2 3 4 0 1 0 0 0 0 1 ½ 0 ½ 0 0 P= 2 0 ½ 0 ½ 0 3 0 0 ½ 0 ½ 4 0 0 0 0 1

Los estados 1, 2 y 3 son estados transitorios y los estados 0 y 4 son estados absorbentes.

¿Cual es la probabilidad de que eventualmente termine en un estado absorbente? ¿En promedio, cuanto tiempo vagará antes de permanecer en alguno de los estados absorbentes? ¿Cuál es la esperanza de encontrarlo en cada esquina? La respuesta a estas preguntas depende, en general, del estado en que el proceso empieza, así como de las probabilidades de transición. Este es un ejemplo de una matriz de transición absorbente, m=[ .98 .01 0 .01 0 0 0 0 0 .25 .25 .25 0 .25 0 0 0 0 0 1/3 1/3 0 0 1/3 0 0 0 .25 0 0 .25 .25 0 .25 0 0 0 .2 0 .2 .2 .2 0 .2 0 0 0 .25 0 .25 .25 0 0 .25 0 0 0 1/3 0 0 1/3 1/3 0 0 0 0 0 .25 0 .25 .25 .25 0 0 0 0 0 .01 0 .01 .98 ]

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC 2.12.4.9.7.2.

Forma Canónica

Considérese una cadena de Markov absorbente. Renumeramos sus estados para que los estados transiente estén al principio. Si hay r estados absorbentes y t estados transiente, la matriz de transición tendrá la siguiente forma canónica: CONSIDERAR UNA SUBMATRIZ ABSORBENTE.

En la que I es una matriz identidad n*n, 0 es una matriz r*t de ceros y Q es una matriz t*t. Los primeros t estados son transiente y los últimos r estados son absorbentes. In Section 11.1, we saw that the entry p(n)ij of the matrix Pn is the probability of being in the state sj after n steps, when the chain is started in state si. A standard matrix algebra argument shows that Pn is of the form

27

FCAyS (795) 2.12.4.9.7.3.

The Fundamental Matrix

Theorem 11.4 For an absorbing Markov chain the matrix I − Q has an inverse N and N = I + Q + Q2 + · · · . The ij-entry nij of the matrix N is the expected number of times the chain is in state sj , given that it starts in state si. The initial state is counted if i = j. Definition 11.3 For an absorbing Markov chain P, the matrix N = (I − Q)−1 is called the fundamental matrix for P. The entry nij of N gives the expected number of times that the process is in the transient state sj if it is started in the transient state si.

Example 11.14 (Example 11.13 continued) In the Drunkard’s Walk examp transition matrix in canonical form is

P=

. 1 2 3 0 4

1 0 ½ 0 0 0

2 ½ 0 ½ 0 0

3 0 ½ 0 0 0

0 ½ 0 0 1 0

4 0 0 ½ 0 1

From this we see that the matrix Q is

where the asterisk ∗ stands for the t-by-r matrix in the upper right-hand corner of Pn. (This submatrix can be written in terms of Q and R, but the expression is complicated and is not needed at this time.) The form of Pn shows that the entries of Qn give the probabilities for being in each of the transient states after n steps for each possible transient starting state. For our first theorem, we prove that the probability of being in the transient states after n steps approaches zero. Thus, every entry of Qn must approach zero as n approaches infinity (i.e, Qn → 0).

©

Prof. Raúl Espejo Rodarte (11950)

0 ½ 0 Q= ½ 0 ½ 0 ½ 0 and

1 −1/2 0 I − Q = −1/2 1 −1/2 0 −1/2 1 Computing (I − Q)−1, we find

1 2 3 N = (I − Q)−1 = 1 3/2 1 ½ 2 1 2 1 3 ½ 1 3/2 From the middle row of N, we see that if we start in state 2, then the expected number of times in states 1, 2, and 3 before being absorbed are 1, 2, and 1. 2 .

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC 2.12.4.9.7.4.

Probabilidad de Absorción

Teorema: En una cadena de Markov la probabilidad de que el proceso sea absorbido es 1. (siempre y cuando todos los estados sean alcanzables y exista al menos una subcadena absorbente. Theorem 11.3 In an absorbing Markov chain, the probability that the process will be absorbed is 1 (i.e., Qn → 0 as n → ∞). 2.12.4.9.7.5.

1 ½ Hence,

2 1 1 3/2 3/2 1 ½

t=Nc

2.12.4.9.8.

1 2 1

½ 1 3/2

1 * 1 1

=

3 1 3

Costos

Paquete computacional QSA,QSB, Ejercicios de Aplicación 2.12.4.10.

Time to Absorption

We now consider the question: Given that the chain starts in state si, what is the expected number of steps before the chain is absorbed? The answer is given in the next theorem. Theorem 11.5 Let ti be the expected number of steps before the chain is absorbed, given that the chain starts in state si, and let t be the column vector whose ith entry is ti. Then

28

FCAyS (795)

2.12.4.11.

t = Nc , where c is a column vector all of whose entries are 1.

Absorption Probabilities

2.12.4.9.7.6.

Theorem 11.6 Let bij be the probability that an absorbing chain will be absorbed in the absorbing state sj if it starts in the transient state si. Let B be the matrix with entries bij . Then B is an t-by-r matrix, and B = NR , where N is the fundamental matrix and R is as in the canonical form.

Example 11.15 (Example 11.14 continued) In the Drunkard’s Walk example, we found that N= N=

3/2 1 ½ ©

Prof. Raúl Espejo Rodarte (11950)

[email protected] 6461766600x173

Métodos Cuantitativos Avanzados (12464) Lecturas 2.12.4 Cadenas de Markov

UABC 2.12.4.12.

29

FCAyS (795)

Bibliografía

[ F. S. Hillier y G. J. Lieberman, Investigación de Operaciones, 7a ed., México DF, 1] DF: McGraw-Hill, 2002. [ D. R. Anderson, D. J. Sweeney y T. A. Williams, Introducción a los Modelos 2] Cuantitativos para Administración, 3a ed., DF, México: Grupo Editorial Iberoamericano, 1993. [ J. Norris, «Markov Chains,» University of Cambridge, Mayo 2012. [En línea]. 3] Available: http://www.statslab.cam.ac.uk/~james/Markov/. [Último acceso: 06 Mayo 2014].

Apéndice

2.12.5.

2.12.5.1.

Cadena de Ehrenfest

Modela el intercambio de moléculas de gas entre dos urnas. Supongamos que tenemos dos urnas: U1 y U2. En ellas están distribuidas d bolas numeradas; en cada paso, se elige un número al azar entre S={1, 2, ... , d}. A continuación se observa en qué urna está la bola con el número elegido y se cambia de urna. 2.12.5.1.1.

Modelo Ehrenfest

Definimos la variable aleatoria Xn que denota el número de bolas en la urna U1 al tiempo n, el espacio de estados es E={0, 1, 2, … ,d} y la matriz de transición definida por 𝐱⁄ 𝐬𝐢 (𝐱 > 𝟎, 𝐲 = 𝐱 − 𝟏) 𝐝 𝐏𝐱,𝐲 =

(𝐝 − 𝐱)⁄ 𝐝

𝐬𝐢(𝐱 < 𝐝, 𝐲 = 𝐱 + 𝟏)

𝟎

𝐨𝐭𝐫𝐚 𝐜𝐨𝐧𝐝𝐢𝐜𝐢ó𝐧

{

2.12.5.1.1.1.

x

0 1 2 3

©

Ejemplo

Para 3 bolas: 3=d E={0,1,2,3) y 0 1 0/3

(3-0)/3

si 0>0, 2=0-1 si 00, 0=1-1 (3-1)/3 si 10, 0=2-1 (3-2)/3 si 20, 0=3-1 (3-3)/3 si 30, 1=0-1 si 00, 1=1-1 (3-1)/3 si 10, 1=2-1 (3-2)/3 si 20, 1=3-1 (3-3)/3 si 30, 2=0-1 si 00, 2=1-1 (3-1)/3 si 10, 2=2-1 (3-2)/3 si 20, 2=3-1 (3-3)/3 si 30, 3=0-1 si 00, 3=1-1 (3-1)/3 si 10, 3=2-1 (3-2)/3 si 20, 3=3-1 (3-3)/3 si 3