ING. INDUSTRIAL
INVESTIGACIÓN DE OPERACIONES II
CATEDRATICO:
Zinath Javier Gerónimo
UNIDAD 4
CADENAS DE MARKOV
Clasificación de las cadenas de Markov
EQUIPO 5
MONTEJO ZAPATA MARICELA
BULOS ZAMORA GRACE ANAHI
SALAS ALPUIN LUIS ALFREDO
MERCADO GÁMEZ OMAR
SÁNCHEZ ORTIZ LUIS MANUEL
VÁZQUEZ FLORES LINO MAURICIO
CARRASCO SANCHEZ LIZBETH ARACELY
Villahermosa, Tab. 24 noviembre del 2010
En la sección 19.3 se menciono que después de muchas transiciones, las probabilidades
de transición de n etapas tienden a estabilizarse. Antes de poder describir esto con
mas detalle necesitamos estudiar como los matemáticos clasifican los estados de una
cadena de markov. La siguiente matriz de transición se usara para mostrar la mayoría de
las definiciones siguientes (fig. 6)
4
5
P= 0
0
0
6
5
0
0
0
0
0
3
5
0
0
0
7
4
8
0
0
0
1
2
DEFINICIÓN: Dado dos estados i y j , la trayectoria de i a j es la sucesión de
transiciones que comienza en i y termina en j, de modo que cada transición de
la secuencia que tenga la probabilidad positiva de presentarse.
Figura 6
Representación
Grafica de la
Matriz de
Transición.
1
2
S1
3
4
S2
5
DEFINICIÓN: Un estado j es alcanzable desde un estado i si hay una
trayectoria que vaya de i a j.
DEFINICIÓN: Se dice que dos estados i y j se comunican si j es alcanzable desde
i, e i es alcanzable desde j.
Para la matriz P de probabilidad de transición representada en la fig. 6, el
estado 5 es alcanzable desde el estado 3 (a través de la trayectoria 3-4-5), pero
el estado 5 no es alcanzable desde el estado 1 (no hay trayectoria que vaya de 1
a 5 en la fig. 6) también , los estados 1 y 2 se comunican: podemos pasar de 1 a
2 y de 2 a 1.
DEFINICIÓN: Un conjunto de estados S en una cadena de markov es conjunto
cerrado si ningún estado fuera de S es alcanzable desde un estado en S.
De la cadena de markov con la matriz F de la fig. 6 tanto S1= (1,2)
Como S2 =( 3,4,5) son conjuntos cerrados. Observe que una vez que entramos
a un conjunto cerrado no podemos dejarlo nunca. En la fig. 6 ningún arco
com9ienza en S1 y termina en S2 o principia en S2 y termina en S1.
DEFINICIÓN: Un estado i es estado absorbente S1 pa= 1
Siempre que entramos aun estado de absorción, nunca lo podremos dejar. En
el ejem. 1 la rutina del jugador, los estados 0 y 4 son absorbentes. Es natural
que un estado absorbente sea un conjunto cerrado que solo contenga un
estado.
DEFINICIÓN: Un estado i es un estado transitorio si hay un estado j alcanzable
desde i, pero el estado i no es alcanzable desde el estado j.
En otras palabras, un estado i es un transitorio si hay manera de dejar el estado
i de tal modo que nunca regrese a el. En el ejemplo (fig. 1), desde el estado 2 es
posible pasar por la trayectoria 2-3-4, pero no hay modo de regresar el estado 2
desde el estado 4. igualmente, en el ejem. 2,[2 0 0], [1 1 0] y [1 0 1] son
estados transitorios. En la fig. 2, hay una trayectoria desde [1 0 1] a [0 0 2],
pero una vez que se hayan pintado ambas bolas, no hay manera de regresar a
[1 0 1] .
Después de un gran numero de periodos, la probabilidad de encontrarse en
cualquier estado de transición i es cero. Cada vez que entramos aun estado i de
transición, hay una probabilidad positiva de dejar i para siempre y terminar en
el estado j descrito en la definición de estado transitorio. Así, al final, tenemos
la seguridad de entrar al estado j (y en ese caso nunca regresamos al estado i).
Así, suponga que en el ejem. 2 nos encontramos en el estado transitorio [1 0
1]. Con probabilidad 1, la bola no pintada la pintaremos finalmente y nunca
regresemos a ese estado [1 0 1] (fig.2).
DEFINICIÓN: Si un estado no es transitorio, se llama estado recurrente.
En el ejem. 1, los estados 0 y 4 son estados recurrentes (y también n estados
absorbentes) en el ejem. 2 [0 2 0] y [0 1 1] son estados recurrentes. Para la
matriz de transición de la Fig.6, todos los estados son recurrentes.
DEFINICIÓN: un estado i es periódico con periodo k es el menor numero tal
que todas las trayectorias que parten del estado i y regresan al estado i tienen
una longitud múltiple de k si un estado recurrente no es periódico. se llama
aperiódico.
Para la cadena de Markov cuya transición es:
0 1 0
Q= 0 0 1
1 0 0
Cada estado tiene periodo 3 . Por ejemplo, así comenzamos en el estado 1, la
única manera de regresar a ese estado es seguir la trayectoria 1-2-3 durante
digamos m veces (Fig. 7) por lo tanto, cualquier regreso al estado 1 tomara 3m
transiciones, de modo que el estado 1 tiene periodo 3. donde nos
encontremos, tenemos la seguridad de regresar allí tres periodos después.
Figura 7
Cadena periódica
de Markov con k=3
1
2
3
DEFINICIÓN: Si todos los estados de una cadena son recurrentes,
aperiódicos y se comunican entre si, se dice que la cadena es ergódica.
El ejemplo de la ruina del jugador no es cadena ergódida porqué, por
ejemplo, los estados 3 y 4 no se comunican. El ejem. 2 tampoco es una cadena
ergódida porqué, por ejemplo,[2 0 0] y [0 1 1] no se comunican. El ejem. 4,
el ejemplo de la cola, es cadena ergódica de markov. De las siguientes tres
cadenas de markov,P1 y P3 son ergodicas y P2 no es ergódica.
1 2
3 3
1
1
2
2
1 3
4 4
0
P1 =
0
Ergódica
P2=
0
P3=
1
4
2
3
0
1
2
1
3
1
3
1
2
1
2
1
2
1
2
0 0
0 0
0 0
0 0
2
3
1
4
1
3
3
4
No ergódica
1
4
0 Ergódica
2
3
P2 no es ergódica porque hay 2 clases cerradas de estados (la clase 1=(1,2) y la
clase 2=(3,4) y los estados diferentes nos e comunican.
Descargar

unidad 4 - WordPress.com