Sgsdgs

Investigación Operativa 2
Capítulo 2: Cadenas de Markov Profesor: Eduardo Carbajal

ÍNDICE
1. 2. 3. 4. 5. 6. 7. 8. Definición de procesos estocásticos. Definición de cadenas de Markov. Probabilidad de transición de n etapas. Clasificación de estados de una cadena de Markov. Probabilidades de estado estable. Tiempo promedio de primera pasada. Cadenas de Markov con recompensa. Cadenas deMarkov absorbentes.
2

1. Definición de procesos estocásticos
Un proceso estocástico discreto en el tiempo es una descripción de la relación entre las variables aleatorias X0, X1, X2 ….. Xn
Ejemplo 2.1 Xt = Temperatura máxima registrada en cada día del año en la ciudad de Lima. Ejemplo 2.2 Xt = Cantidad de alumnos que egresan semestralmente en la especialidad de ingeniería industrial (PUCP).Ejemplo 2.3 Xt = El precio de una acción en la BVL al inicio del día.
3

2. Definición de cadenas de Markov (1)
Un tipo especial de procesos estocásticos de tiempo discreto se llama cadena de Markov.
Para simplificar supondremos que en cualquier tiempo, el proceso estocástico de tiempo discreto puede estar en uno de un número finito de estados identificados por 1,2,...s. Un proceso estocásticode tiempo discreto es una cadena de Markov, si para t = 0,1,2… y todos los estados P(Xt+1 = it+1|Xt = it, Xt-1=it-1,…,X1=i1, X0=i0) = P(Xt+1=it+1|Xt = it) En esencia, la distribución de probabilidad del estado en el tiempo t+1 depende del estado t (en it) y no depende de los estados por los cuales pasó la cadena para llegar a it en el tiempo t.
4

2. Definición de cadenas de Markov (2)
En elestudio de las cadenas de Markov, se hace la suposición adicional de que para los estados i y j y todo t, P(Xt+1 = j|Xt = i) es independiente de t. Esta suposición permite escribir P(Xt+1 = j|Xt = i) = pij donde pij es la probabilidad de que dado que el sistema está en el estado i en el tiempo t, estará en el estado j en el tiempo t+1. Si el sistema se mueve del estado i durante un periodo alestado j durante el siguiente periodo, se dice que ocurrió una transición de i a j.

5

2. Definición de cadenas de Markov (3)
Las pij’s se denominan probabilidades de transición para la cadena de Markov. Esta ecuación implica que la ley de probabilidad que relaciona el estado del siguiente periodo con el estado actual no cambia en el tiempo. Por esta razón se le llama Suposición Estacionaria ycualquier cadena de Markov que satisface esta condición es llamada cadena de Markov estacionaria. También definimos qi como la probabilidad de que la cadena esté en el estado i en el tiempo 0; en otras palabras, P(X0=i) = qi.
6

2. Definición de cadenas de Markov (4)
Llamamos al vector q= [q1, q2,…qs] distribución de probabilidad inicial para la cadena de Markov. En la mayoría de lasaplicaciones, las probabilidades de transición se muestran como una matriz de probabilidades de transición P de orden s x s. La matriz de probabilidad de transición P se puede escribir como
 p11 p P   21     ps1 p12  p1s  p22  p2 s       ps 2  pss 
7

2. Definición de cadenas de Markov (5)
Dado que el estado es i en el tiempo t, el proceso debe estar en algún lugar en el tiempot+1. Esto significa que para cada i, ∑j=1,s P(Xt+1=j / Xt=i) = ∑j=1,s pij = 1 También sabemos que cada elemento de la matriz P debe ser no negativo (pij  0). Por lo tanto, todos los elementos de la matriz de probabilidad de transición son no negativos; los elementos de cada fila deben sumar 1.

8

2. Definición de cadenas de Markov (6)
Problema 2.1 Supongamos, que en Lima, si un día estánublado, el 90% del tiempo será nublado al día siguiente y que si un día está soleado, con probabilidad 30% será soleado al día siguiente. Halle la Matriz de Probabilidades de Transición.

9

2. Definición de cadenas de Markov (7)
Problema 2.2 El estado de ánimo de Juan puede ser, alegre, triste o molesto. Si está alegre, habrá una probabilidad de 80% de que siga alegre al día siguiente y 15%...