CADENAS DE MARKOV

1) Diagrama de transición de estados

Sea Xi una variable aleatoria que caracteriza el estado del sistema en puntos discretos en el tiempo t= 1, 2… . La f
forma un proceso estocástico con una cantidad finita o infinita de estados. Dicho proceso estocástico se puede re
transición de estados, donde se muestra la probabilidad de moverse de un estado a otro dentro del proceso.

EJEMPLO 1.a.
Un profesor de ingeniería adquiere una computadora nueva cada dos años. El profesor puede elegir de entre tre
modelo actual es M1, la siguiente computadora puede ser M2 con probabilidad .2, o M3 con probabilidad .15. Si
probabilidades de cambiar a M1 y M3 son .6 y .25, respectivamente. Pero si el modelo actual es M3, entonces las
modelos M1 y M2 son .5 y .1, respectivamente.

a) Elabore el diagrama de transición de estados.

Para elaborar el diagrama de transición de estados primero se deben reconocer los estados. En este problema ha
por lo modelos de computadora que posee el ingeniero en algún momento del tiempo: M1, M2, M3.
En el diagrama que se desea elaborar cada estado es un círculo y las probabilidad de moverse de un estado a otr

Note como estando en el estado M1, hay una probabilidad de 0,65

0,2 de moverse al estado M2 y de 0,15 de moverse al estado M3, 0,6
falta un 0,65 de probabilidad para sumar 1, la cual corresponde
a mantenerse en el estado M1. De manera similar se calculan M1
las probabilidades para mantenerse en los estados M2 y M3. 0.2

Si se analiza el diagrama mostrado, la M1 es el modelo con el que se

0.15
siente más a gusto el profesor porque es el que tiene mayor probabilidad
de no cambiarlo por otro (0,65), mientras que el que menos le gusta es el 0.5
M2 porque es el que tiene mayor probabilidad de cambio (0,85).

M3

0.4

2) Matriz de transición de un paso

La matriz de transición de un paso es simplemente un arreglo matricial del diagrama de transición de estados. Ca
un estado inicial o actual y las filas representan el estado futuro. Los tipos de estados iniciales y futuros deben se
esta matriz debe ser cuadrada. En el interior de la matriz se presenta la probabilidad de transición de un paso, es
un estado inicial a un estado futuro.

EJEMPLO 1.b.
Partiendo de los datos presentados en el ejemplo anterior, elabore la matriz de transición de un paso.

FUTURO
 M1 M2 M3 Note como las probabilidades de
M1 0.65 0.2 0.15 fila suman 1.

INICIAL
M2 0.6 0.15 0.25
M3 0.5 0.1 0.4

3) Definición de Cadena de Markov

Anteriormente se definió un proceso estocástico como un conjunto de variables que dependen del tiempo, que c
o infinito de estados. Un proceso estocástico es un proceso de Markov si un estado futuro depende sólo del esta
Es decir, el valor de X en el paso siguiente (t+1) va a depender únicamente del valor de X en el tiempo t (estado a
Una cadena de Markov es una matriz P donde se muestran las probabilidades de transición de un paso. Por ejem
de Markov que describe el proceso estocástico que muestra las probabilidades de cambio de computadora por p
Una cadena de Markov tiene la propiedad de que todas sus probabilidades de transición pij son estacionarias e in
tiempo. Aunque una cadena de Markov puede incluir un número infinito de estados, la presentación en este mat
finita de estados, porque es lo requerido para las aplicaciones en la carrera.

EJEMPLO 2

Una patrulla policiaca vigila un vecindario conocido por sus actividades delictivas. Durante un patrullaje hay 60%
oportunamente una llamada de ayuda; si no sucede algo, continuará el patrullaje regular. Después de recibir una
probabilidades de cancelación (en cuyo caso el patrullaje normal se reanuda), y 30% de probabilidad de que la un
llamada anterior. Cuando la patrulla llega a la escena del suceso, hay 10% de probabilidades de que los instigado
caso reanuda su patrullaje), y 40% de probabilidades de que se haga una aprehensión de inmediato. De otro mo
Si ocurre una aprehensión, hay 60% de probabilidades de trasladar a los sospechosos a la estación de policía, de
unidad regresa a patrullar. Exprese las actividades probabilísticas de la patrulla en la forma de una matriz de tran

Lo primero que se debe hacer es reconocer los estados que involucra el proceso, los cuales se resaltaron en el te
E1: Patrullaje regular
E2: Responder llamada de ayuda
E3: Llegar a la escena del suceso
E4: Aprehensión de los sospechosos
E5: Traslado de los sospechosos

Cuando el problema es muy complejo o no se tiene una idea clara de la transición entre los estados, se recomien
transición de estados:

0,1
0,4 0,5
0,3

0,1
E1 E2 0,6 E3 0,4 E4 0,6

0,6

0,4
 E1 E2 0,6 E3 0,4 E4 0,6

0,6

0,4
Con el diagrama anterior se puede construir la matriz de transición de un paso que corresponde a la Cadena de M

FUTURO
E1 E2 E3 E4 E5
E1 0.4 0.6 0 0 0
E2 0.1 0.3 0.6 0 0
INICIAL

E3 0.1 0 0.5 0.4 0

E4 0.4 0 0 0 0.6
E5 1 0 0 0 0

Elaborado por: Ing. Angel González

retos en el tiempo t= 1, 2… . La familia de variables aleatorias {Xi}
proceso estocástico se puede representar en un diagrama de
o a otro dentro del proceso.

ofesor puede elegir de entre tres modelos: M1,M2 y M3. Si el

2, o M3 con probabilidad .15. Si el modelo actual es M2, las
odelo actual es M3, entonces las probabilidades de comprar los

os estados. En este problema hay 3 estados, representados

empo: M1, M2, M3.
de moverse de un estado a otro se señalan con flechas, así:

0,6 0,15

M2
0.2

0.15
0.1
0.5
0,25

M3

0.4

ma de transición de estados. Cada fila de la matriz representa

ados iniciales y futuros deben ser los mismos, por lo cual
dad de transición de un paso, es decir, la probabilidad de ir de

ransición de un paso.
ote como las probabilidades de transición de un paso en cada

que dependen del tiempo, que cuentan con un conjunto finito

do futuro depende sólo del estado inmediatamente anterior.
or de X en el tiempo t (estado actual).
transición de un paso. Por ejemplo, la matriz anterior es la cadena
e cambio de computadora por parte del profesor de ingeniería.
nsición pij son estacionarias e independientes a lo largo del
dos, la presentación en este material se limita a una cantidad

Durante un patrullaje hay 60% de probabilidades de responder

regular. Después de recibir una llamada, hay 10% de
0% de probabilidad de que la unidad ya esté respondiendo a la
babilidades de que los instigadores hayan desaparecido (en cuyo
nsión de inmediato. De otro modo, los oficiales rastrearán el área.
osos a la estación de policía, de lo contrario son liberados y la
n la forma de una matriz de transición o cadena de Markov.

los cuales se resaltaron en el texto:

n entre los estados, se recomienda elaborar el diagrama de

4 E4 0,6 E5
4 E4 0,6 E5

ue corresponde a la Cadena de Markov:

PROBABILIDADES DE TRANSICIÓN ABSOLUTA Y N PASOS

Dada la matriz de transición P de una cadena de Markov y el vector de probabilidades iniciales a(0) , las probabili
después de n transiciones se calculan como sigue:

La matriz Pn se conoce como la matriz de transición de n pasos. A partir de los cálculo se puede ver que:

EJEMPLO 3

Datos

Se cuenta con una cuadrícula de cuatro casillas, como se muestra a continuación. La ficha se encuentra en el luga
a cuál casilla se moverá, siguiendo la siguiente secuencia: A-B-C-D-A y repite.

A B
4$ -2$
D C
9$ -6$

a) Exprese el problema como una cadena de Markov.

La construcción de la matriz de transición de un paso correspondiente a la cadena de Markov depende del núme

Iniciando en A:
Número del Dado 1 2 3 4 5
Casilla resultante B C D A B

Probabilidades de transición de un paso, Desde A hasta cada casilla:

A B C D
1/6 2/6=1/3 2/6=1/3 1/6
 Iniciando en B:
Número del Dado 1 2 3 4 5
Casilla resultante C D A B C

Probabilidades de transición de un paso, Desde A hasta cada casilla:

A B C D
1/6 1/6 2/6=1/3 2/6=1/3

De igual manera se calculan las probabilidades iniciando en las casillas C y D. Entonces la cadena de Markov que
es la matriz P:

FUTURO
A B C D
A 0.167 0.333 0.333 0.167
INICIAL

B 0.167 0.167 0.333 0.333

C 0.333 0.167 0.167 0.333
D 0.333 0.333 0.167 0.167

b) Determine la ganancia o pérdida esperadas después de lanzar el dado 5 veces.

Para calcular el valor monetario esperado se necesita conocer la probabilidad absoluta de que la ficha culmine en
de lanzar el dado cinco veces.

Ya que se conoce que la ficha inició en A, la probabilidad absoluta (a(5)) se calcula así:
Donde a(0) es el vector de probabilidades iniciales (1,0,0,0). El valor 1 indica que la ficha inicia en la posición A de
P5: es la matriz de transición después de haber lanzado 5 veces el dado; es decir, después de 5 pasos.

Para calcular la matriz de transición después de 5 pasos, se utilizarán las ecuaciones de Chapman-Kolomogorov:

0.167 0.333 0.333 0.167 0.167

0.167 0.167 0.333 0.333 * 0.167
0.333 0.167 0.167 0.333 0.333
0.333 0.333 0.167 0.167 0.333

0.250 0.222 0.250 0.278 0.250

0.278 0.250 0.222 0.250 * 0.278
0.250 0.278 0.250 0.222 0.250
0.222 0.250 0.278 0.250 0.222
 0.248 0.250 0.252 0.250 0.167
0.250 0.248 0.250 0.252 * 0.167
0.252 0.250 0.248 0.250 0.333
0.250 0.252 0.250 0.248 0.333

Ahora se calcula la probabilidad absoluta a(5)

1 0 0 0 * 0.2503
0.2503
0.2497
0.2497

Entonces, iniciando en la casilla A, la probabilidad de que el dado culmine en A, B, C, D, luego de 5 lanzamientos e

A B C D
0.2503 0.2497 0.2497 0.2503

Para calcular la ganancia esperada se multiplica la probabilidad de cada casilla por su valor monetario y se totaliz

A B C D
Probabilidad 0.2503 0.2497 0.2497 0.2503
Valor ($) 4 -2 -6 9
Valor Esperado ($) 1.0010 -0.4995 -1.4985 2.2523

Valor esperado total ($) 1.2554

Análisis: Iniciando en la casilla A, la ganancia esperada luego de 5 lanzamientos del dado es de 1,2554 $.

Elaborado por: Ing. Angel González

bilidades iniciales a(0) , las probabilidades absolutas a(n)

os cálculo se puede ver que:

ción. La ficha se encuentra en el lugar A y se lanza un dado para determinar

dena de Markov depende del número que obtenga el dado:

6
C
 6
D

Entonces la cadena de Markov que representa el proceso

d absoluta de que la ficha culmine en cada casilla: A, B, C, D; después

que la ficha inicia en la posición A de la cuadrícula.

ecir, después de 5 pasos.

aciones de Chapman-Kolomogorov:

0.333 0.333 0.167 0.250 0.222 0.250 0.278

0.167 0.333 0.333 = 0.278 0.250 0.222 0.250
0.167 0.167 0.333 0.250 0.278 0.250 0.222
0.333 0.167 0.167 0.222 0.250 0.278 0.250

0.222 0.250 0.278 0.248 0.250 0.252 0.250

0.250 0.222 0.250 = 0.250 0.248 0.250 0.252
0.278 0.250 0.222 0.252 0.250 0.248 0.250
0.250 0.278 0.250 0.250 0.252 0.250 0.248
 0.333 0.333 0.167 0.2503 0.2497 0.2497 0.2503
0.167 0.333 0.333 = 0.2503 0.2503 0.2497 0.2497
0.167 0.167 0.333 0.2497 0.2503 0.2503 0.2497
0.333 0.167 0.167 0.2497 0.2497 0.2503 0.2503

0.2497 0.2497 0.2503 0.2503 0.2497 0.2497 0.2503

0.2503 0.2497 0.2497 =
0.2503 0.2503 0.2497
0.2497 0.2503 0.2503

A, B, C, D, luego de 5 lanzamientos es:

a por su valor monetario y se totaliza:

os del dado es de 1,2554 $.

CLASIFICACIÓN DE LOS ESTADOS EN UNA CADENA DE MARKOV

Los estados de una cadena de Markov se clasifican con base en la probabilidad de transición pij de P.
a) Un estado j es absorbente si está seguro de regresar a sí mismo en una transición; es decir, pij= 1
b) Un estado j es transitorio si puede llegar a otro estado pero no puede regresar desde otro estado
matemática la probabilidad de regreso a este estado después de infinitos pasos es 0.
c) Un estado j es recurrente si la probabilidad de ser revisitado desde otros estados es 1. Esto puede
el estado no es transitorio.
d) Un estado j es periódico con periodo de t >1 si es posible un retorno sólo en t, 2t, 3t,… pasos. Est
de ocurrencia pjj en el estado n es cero, cuando n no es divisible entre t.

Se dice que una cadena de Markov es ergódica si todos los estados son recurrentes y aperiódica (no periódica). E
absolutas después de n transiciones, a(n)=a(0)*Pn, siempre convergen de forma única a una distribución limitant
independiente de las probabilidades iniciales a(0).

EJEMPLO 4

Clasifique los estados de la siguiente Cadena de Markov.

E1 E2 E3 E4
E1 0.50 0.25 0.25 0.00
E2 0.00 0.00 1 0.00
E3 0.33 0.00 0.33 0.33
E4 0.00 0.00 0.00 1

Para identificar los estados se recomienda realizar el diagrama de transición de estados:

E1 E2 E3 E4

ESTADO CLASIFICACIÓN EXPLICACIÓN

E1
Son estados de paso, el proceso llega a ellos pero se mueven a un estado siguien
E2 TRANSITORIO
culminar en el estado absorbente.
E3
ABSORBENTE Una vez que se llega a él no se puede salir porque regresa hacia sí mismo en f
E4 RECURRENTE recurrente.

EJEMPLO 5

Clasifique los estados de la siguiente Cadena de Markov.

 E1 E2 E3 E4
E1 1 0 0 0
E2 0 0.5 0.5 0
E3 0 0.5 0.5 0
E4 0.5 0 0 0.5

Para identificar los estados se recomienda realizar el diagrama de transición de estados:

E1 E2 E3 E4

ESTADO CLASIFICACIÓN EXPLICACIÓN

ABSORBENTE Una vez que se llega a él no se puede salir porque regresa hacia sí mismo en f
E1
RECURRENTE recurrente.
E2 Estos estados forman un conjunto cerrado o bucle. Son recurrentes porque n
RECURRENTES posibilidad de estancamiento. En algún momento se va a llegar a alguno de e
E3
E4 TRANSITORIO Es un estado de paso, el proceso llega allí pero se mueven a un estado siguient
culminar en el estado absorbente.

EJEMPLO 6

Demuestre que la siguiente cadena de Markov posee estados periódicos e indique cuáles son y su periodo.

E1 E2 E3
E1 0.00 0.60 0.40
E2 0.00 1.00 0.00
E3 0.60 0.40 0.00

Se puede comprobar la periodicidad de los estados calculando la matriz de transición de n pasos y observar los p
las pjj sean positivas, porque solo serán positivas en los periodos correspondientes:

0.00 0.60 0.40 0.00 0.60

0.00 1.00 0.00 * 0.00 1.00
0.60 0.40 0.00 0.60 0.40
 0.24 0.76 0 0.00 0.60
0 1 0 * 0.00 1.00
0 0.76 0.24 0.60 0.40

0 0.904 0.096 0.00 0.60

0 1 0 * 0.00 1.00
0.144 0.856 0 0.60 0.40

0.0576 0.9424 0 0.00 0.60

0 1 0 * 0.00 1.00
0 0.9424 0.0576 0.60 0.40

Note como p11 y p33 son positivas solo en los tiempos pares; entonces, los estados 1 y 3 son estados periódicos

Elaborado por: Ing. Angel González

 nsición pij de P.
na transición; es decir, pij= 1.
e regresar desde otro estado. Desde una perspectiva

ros estados es 1. Esto puede suceder si, y sólo si,

sólo en t, 2t, 3t,… pasos. Esto significa que la probabilidad

aperiódica (no periódica). En este caso las probabilidades

a a una distribución limitante (estado estable) que es

mueven a un estado siguiente, para

orbente.

regresa hacia sí mismo en forma

 E4

regresa hacia sí mismo en forma

e. Son recurrentes porque no hay

o se va a llegar a alguno de ellos.
mueven a un estado siguiente, para
orbente.

cuáles son y su periodo.

de n pasos y observar los pasos en la que

0.40 0.24 0.76 0

0.00 = 0 1 0
0.00 0 0.76 0.24
 0.40 0 0.904 0.096
0.00 = 0 1 0
0.00 0.144 0.856 0

0.40 0.0576 0.9424 0

0.00 = 0 1 0
0.00 0 0.9424 0.0576

0.40 0 0.97696 0.02304

0.00 = 0 1 0
0.00 0.03456 0.96544 0

1 y 3 son estados periódicos con t=2.

PROBABILIDADES DE ESTADO ESTABLE Y TIEMPOS DE RETORNO MEDIO DE CADENAR ERGÓDICAS

En una cadena ergódica, las probabilidades de estado estable se definen como

Un subproducto directo de las probabilidades de estado estable es la determinación del número esperado de tra
regrese a un estado j por primera vez. Esto se conoce como tiempo medio del primer retorno o tiempo medio de
cadena de Markov de n estados como:

EJEMPLO 7

Problema de inventario

Demanda 0 1 2 3 4
Probabilidad 0.15 0.2 0.35 0.25 0.05

Inventario inicial 3 unidades

Punto de reorden 3 unidades
Inventario max 5 unidades

a) Exprese la situación como una cadena de Markov.

Los estados están representados por los niveles de inventario posibles : 3, 4, 5.

Para determinar la matriz de transición de primer paso, se utilizan las probabilidades de cada demanda:

Iniciando con 3 unidades:

Inventario final Probabilidad Explicación
posible
3 0.15 Si inicia con 3 dos semanas seguidas es porque la demanda fue
4 0 Es imposible porque es mayor al inicial y cuando se reabastece se
5 0.85 Se calcula por complemento

Iniciando con 4 unidades:

 Inventario final Probabilidad Explicación
posible
3 0.2 Se inicio con 4 y en la siguiente semana baja a 3, la demanda
4 0.15 Si inicia con 4 dos semanas seguidas es porque la demanda fue
5 0.65 Se calcula por complemento

Iniciando con 5 unidades:

Inventario final Probabilidad Explicación
posible
3 0.35 Se inicio con 5 y en la siguiente semana baja a 3, la demanda
4 0.2 Se inicio con 5 y en la siguiente semana baja a 4, la demanda
5 0.45 Se calcula por complemento

Cadena de Markov:

Inv=3 Inv=4 Inv=5

Inv=3 0.15 0.00 0.85
Inv=4 0.20 0.15 0.65
Inv=5 0.35 0.20 0.45

b) Suponga que la semana se inicia con 4 PC. Determine la probabilidad de que un pedido se coloque al final de

La matriz de probabilidad absoluta al final de dos semanas se calcula así:

Si se inicia con 4 PC en inventario la matriz de probabilidad inicial es:

Para calcular la matriz de probabilidades de transición luego de dos pasos:

0.15 0 0.85 0.15

0.2 0.15 0.65 * 0.2
0.35 0.2 0.45 0.35

Entonces:

0 1 0 * 0.32
0.2875
0.25

La matriz de probabilidad absoluta al final de dos semanas si se inicia con 4PC es:

Inv=3 Inv=4 Inv=5

0.2875 0.1525 0.56

La probabilidad de que un pedido se coloque al final de dos semanas, si se inició con 4 PC, es equivalente a la pro
de dos semanas se cuente con 5 PC; es decir, 0,56.

c) Determine la probabilidad a largo plazo de que no se coloque ningún pedido en cualquier semana.

Las probabilidades a largo plazo son las probabilidades de estado estable de una cadena ergódica. La cadena de M
ergódica ya que sus estados son recurrentes y no periódicos (lo puede comprobar).

Las probabilidades de estado estable se calculan así:

Entonces:

Una de las 3 primeras ecuaciones es redundante por lo cual se puede obviar cualquiera de ellas y resolver el siste

Se aplicará SOLVER para resolver el sistema, obviando la ecuación 1:

π1 π2 π3 Valor Lado derecho

Ecuación 2 0 -0.85 0.2 3E-12 0
Ecuación 3 0.85 0.65 -0.55 -1E-06 0
Ecuación 4 1 1 1 1 1
Solución 0.2744 0.1382 0.5874 1

Entonces las probabilidades de estado estable para cada nivel de inventario es:

Inv=3 Inv=4 Inv=5

0.2744 0.1382 0.5874

La probabilidad a largo plazo de que no se coloque ningún pedido en la semana equivale a la probabilidad de no
siguiente con 5 PC en inventario; es decir: 1-0,5874=0,4126.

d) Determine la cantidad de semanas promedio en que se retorna a cada nivel de inventario.

La cantidad de semanas promedio de retorno a cada nivel de inventario es el tiempo de retorno medio a cada es
 Tiempo de
retorno medio
Nivel de inventario (semanas)
3 3.64 Si se inicia con 3 PC en inventario, pasarán 3,64 semanas para iniciar nuev
4 7.24 Si se inicia con 4 PC en inventario, pasarán 7,24 semanas para iniciar nuev
5 1.70 Si se inicia con 5 PC en inventario, pasarán 1,7 semanas para iniciar nueva

Análisis: El inventario se reabastece en promedio cada 1,7 semanas, alcanzando el nivel máximo deseado de 5 PC

e) Si el costo fijo de colocar un pedido es de $200, el costo de retención por PC por semana es de $5, y el costo
faltante es de $20, determine el costo de inventario esperado por semana.

Para determinar el costo de inventario esperado por semana se deben considerar todas las situaciones posibles e
y la demanda:

Costo de ordenar 200 $/sem *Este costo solo se activa cuando el nivel de inventario es me
Costo de almacenar 5 $/sem-PC
Costo de penalizar 20 $/sem-PC

Nivel de inventario inicial Demanda semanal Costo de almacenar ($/sem)

Cantidad Probabilidad Cantidad Probabilidad Inventario final Costo
0 0.15 3 15
1 0.2 2 10
3 0.2744 2 0.35 1 5
3 0.25 0 0
4 0.05 0 0
0 0.15 4 20
1 0.2 3 15
4 0.1382 2 0.35 2 10
3 0.25 1 5
4 0.05 0 0
0 0.15 5 25
1 0.2 4 20
5 0.5874 2 0.35 3 15
3 0.25 2 10
4 0.05 1 5

Costo de total 112.516

esperado ($/sem)

Elaborado por: Ing. Angel González

R ERGÓDICAS

el número esperado de transiciones antes de que el sistema

etorno o tiempo medio de recurrencia, y se calcula en una

e cada demanda:

ción

s es porque la demanda fue cero

y cuando se reabastece se lleva a 5.
omplemento
ción

mana baja a 3, la demanda fue 1

s es porque la demanda fue cero
omplemento

ción

mana baja a 3, la demanda fue 2

mana baja a 4, la demanda fue 1
omplemento

edido se coloque al final de dos semanas.

0 0.85 0.32 0.17 0.51

0.15 0.65 = 0.2875 0.1525 0.56
0.2 0.45 0.25 0.12 0.63

0.17 0.51 0.288 0.153 0.560

0.1525 0.56 =
0.12 0.63

PC, es equivalente a la probabilidad de que al final

alquier semana.

na ergódica. La cadena de Markov del ejemplo es

a de ellas y resolver el sistema de ecuaciones.

ale a la probabilidad de no iniciar la semana

e retorno medio a cada estado y se calcula así:

semanas para iniciar nuevamente la semana con 3 PC.
semanas para iniciar nuevamente la semana con 4 PC.
emanas para iniciar nuevamente la semana con 5 PC.

el máximo deseado de 5 PC.

emana es de $5, y el costo de penalización por computadora

as las situaciones posibles entre el nivel de inventario

el nivel de inventario es menor a 3 PC

Costo de ordenar Costo penalización ($/sem) Costo de total Costo esperado

($/sem) Faltantes Costo ($/sem) ($/sem)
0 0 0 15 0.617
200 0 0 210 11.524
200 0 0 205 19.687
200 0 0 200 13.719
200 1 20 220 3.018
0 0 0 20 0.415
0 0 0 15 0.415
200 0 0 210 10.159
200 0 0 205 7.083
200 0 0 200 1.382
0 0 0 25 2.203
0 0 0 20 2.350
0 0 0 15 3.084
200 0 0 210 30.838
200 0 0 205 6.021
TIEMPO DEL PRIMER PASO

El tiempo medio del primer paso μij, es definido como el número esperado de transiciones para llegar por primer
Si la cadena de Markov es ergódica, el tiempo medio del primer paso del estado i al estado j se calcula como:

EJEMPLO 8

Un ratón entre en el laberinto por la esquina 1 y sale por la esquina 5. Las probabilidades de seleccionar una ruta

a) Exprese el laberinto como una cadena de Markov.

Lo primero que se debe hacer es determinar cuáles son los estados de la cadena. En este problema cada intersec

La matriz de transición de primer paso se construye considerando las posibles rutas que se pueden seleccionar. P
intersección 1, el ratón se puede mover a las intersecciones 2,3,4. Cada ruta tiene la misma probabilidad.

I1 I2 I3 I4 I5
I1 0 0.33 0.33 0.33 0
I2 0.33 0 0.33 0 0.33
I3 0.33 0.33 0 0 0.33
I4 0.5 0 0 0 0.5
I5 0 0.33 0.33 0.33 0

b) Determine la probabilidad de que, comenzando en la intersección 1, el ratón llegue a la salida después de tr

La matriz de probabilidad absoluta al final de tres intentos se calcula así:

Si se inicia en la intersección 1 la matriz de probabilidad inicial es:

Para calcular la matriz de probabilidades de transición luego de 3 pasos:

0 0.33 0.33 0.33 0 0

0.33 0 0.33 0 0.33 0.33
0.33 0.33 0 0 0.33 * 0.33
0.5 0 0 0 0.5 0.5
0 0.33 0.33 0.33 0 0

0.39 0.11 0.11 0.00 0.39 0

0.11 0.33 0.22 0.22 0.11 0.33
0.11 0.22 0.33 0.22 0.11 * 0.33
0.00 0.33 0.33 0.33 0.00 0.5
0.39 0.11 0.11 0.00 0.39 0

1 0 0 0 0 * 0.07
0.30
0.30
0.39
0.07

La matriz de probabilidad absoluta al final de 3 semanas, si se inicia en la intersección 1 es:

I1 I2 I3 I4 I5
0.0741 0.2963 0.2963 0.2593 0.0741

La probabilidad de que iniciando en la intersección 1 el ratón llegue a la salida, la intersección 5, en 3 intentos es

c) Determine la probabilidad a largo plazo de que el ratón localice la intersección de salida.

Las probabilidades a largo plazo son las probabilidades de estado estable de una cadena ergódica. La cadena de M
ergódica ya que sus estados son recurrentes y no periódicos (lo puede comprobar).

Las probabilidades de estado estable se calculan así:

π1 π2 π3 π4 π5 = π1
Se arma el sistema de ecuaciones:

Una de las 5 primeras ecuaciones es redundante por lo cual se puede obviar cualquiera de ellas y resolver el siste

Se aplicará SOLVER para resolver el sistema, obviando la ecuación 1:

π1 π2 π3 π4 π5 Valor
Ecuación 2 0.33333333 -1 0.33333333 0 0.33333333 0
Ecuación 3 0.33333333 0.33333333 -1 0 0.33333333 0
Ecuación 4 0.33333333 0 0 -1 0.33333333 0
Ecuación 5 0 0.33333333 0.33333333 0.5 -1 0
Ecuación 6 1 1 1 1 1 1
Solución 0.2143 0.2143 0.2143 0.1429 0.2143 1.0000

Entonces las probabilidades de estado estable para cada intersección es:

I1 I2 I3 I4 I5
0.2143 0.2143 0.2143 0.1429 0.2143

La probabilidad a largo plazo de que el ratón localice la intersección de salida 5 es de 0,2143.

d) Determine el promedio de intentos necesario para llegar al punto de salida desde la intersección 1.

Se está solicitando el número esperado de intentos para llegar por primera vez al estado 5 desde el estado 1.
Si la cadena de Markov es ergódica, el tiempo medio del primer paso del estado 1 al estado 5 se calcula como:
La matriz N es una matriz que resulta de eliminar la fila y la columna correspondiente al estado donde se desea ll

Si esta es la matriz de transición de primer paso, se elimina lo señalado:

0 0.33 0.33 0.33 0

0.33 0 0.33 0 0.33
0.33 0.33 0 0 0.33
0.5 0 0 0 0.5
0 0.33 0.33 0.33 0

La matriz N es:

0 0.33 0.33 0.33

0.33 0 0.33 0
0.33 0.33 0 0
0.5 0 0 0

Como indica la formula, se le resta la matriz identidad a la matriz N:

1 0 0 0 0 0.33
0 1 0 0 0.33 0
0 0 1 0 - 0.33 0.33
0 0 0 1 0.5 0

A la matriz resultante se le saca la inversa, resultando:

2.00 1.00 1.00 0.67
1.00 1.63 0.88 0.33
1.00 0.88 1.63 0.33
1.00 0.50 0.50 1.33

La matriz inversa resultante se multiplica por una matriz columna de 1:

2.000 1.000 1.000 0.667 1.000

1.000 1.625 0.875 0.333 * 1.000 =
1.000 0.875 1.625 0.333 1.000
1.000 0.500 0.500 1.333 1.000

La matriz resultante muestra el número de intentos necesarios para llegar desde los estados de intersección 1,2,

I1 4.66667
I2 3.83333
I3 3.83333
 I4 3.33333

Se necesitan 4,67 intentos para que el ratón llegue a la intersección 5, partiendo de la intersección 1.

Elaborado por: Ing. Angel González

nsiciones para llegar por primera vez al estado j desde el estado i.
al estado j se calcula como:

ilidades de seleccionar una ruta son iguales.

En este problema cada intersección es un estado: 1,2,3,4,5.

as que se pueden seleccionar. Por ejemplo, desde la

e la misma probabilidad.

llegue a la salida después de tres intentos.

 0.33 0.33 0.33 0 0.3889 0.1111 0.1111
0 0.33 0 0.33 0.1111 0.3333 0.2222
0.33 0 0 0.33 = 0.1111 0.2222 0.3333
0 0 0 0.5 0.0000 0.3333 0.3333
0.33 0.33 0.33 0 0.3889 0.1111 0.1111

0.33 0.33 0.33 0 0.0741 0.2963 0.2963

0 0.33 0 0.33 0.2963 0.1481 0.1852
0.33 0 0 0.33 = 0.2963 0.1852 0.1481
0 0 0 0.5 0.3889 0.1111 0.1111
0.33 0.33 0.33 0 0.0741 0.2963 0.2963

0.30 0.30 0.26 0.07 0.0741 0.2963 0.2963

0.15 0.19 0.07 0.30
0.19 0.15 0.07 0.30 =
0.11 0.11 0.00 0.39
0.30 0.30 0.26 0.07

intersección 5, en 3 intentos es 0,0741.

n de salida.

cadena ergódica. La cadena de Markov del ejemplo es

π2 π3 π4 π5 * 0 0.33 0.33
0.33 0 0.33
 0.33 0.33 0
0.5 0 0
0 0.33 0.33

quiera de ellas y resolver el sistema de ecuaciones.

Lado derecho
0
0
0
0
1

s de 0,2143.

esde la intersección 1.

estado 5 desde el estado 1.

1 al estado 5 se calcula como:
ente al estado donde se desea llegar, el 5:

0.33 0.33 1.00 -0.33 -0.33 -0.33

0.33 0 -0.33 1.00 -0.33 0.00
0 0 = -0.33 -0.33 1.00 0.00
0 0 -0.50 0.00 0.00 1.00

4.666667
3.833333
3.833333
3.333333

los estados de intersección 1,2,3,4 al estado 5.

de la intersección 1.
0.0000 0.3889
0.2222 0.1111
0.2222 0.1111
0.3333 0.0000
0.0000 0.3889

0.2593 0.0741
0.0741 0.2963
0.0741 0.2963
0.0000 0.3889
0.2593 0.0741

0.2593 0.0741

0.33 0
0 0.33
 0 0.33
0 0.5
0.33 0
ANÁLISIS DE LOS ESTADOS ABSORBENTES

Una cadena de Markov puede tener más de un estado absorbente. Por ejemplo, un empleado puede permanece
hasta su retiro o renunciar antes (dos estados absorbentes). En estos tipos de cadenas, es importante determina
absorción y el número esperado de transiciones para llegar a ella, dado que el sistema se inicia en un estado tra
El análisis de las cadenas de Markov con estados absorbentes puede realizarse de forma conveniente con matric
Markov se particiona como sigue:

La disposición requiere que todos los estados absorbentes ocupen la esquina sureste de la nueva matriz.
Dada la definición de las matrices N, A y el vector columna unitario:

Promedio de visitas a cada estado j partiendo del estado i:

Tiempo esperado para la absorción:

Probabilidad de la absorción:

EJEMPLO 9

Se procesa un producto en secuencia en dos máquinas, I y II. La inspección se realiza después de que una unidad
cualquiera de las máquinas. Hay 5% de probabilidades de que una unidad sea desechada antes de inspeccionarla
3% de probabilidades de que la unidad sea desechada, y 7% de probabilidades de ser devuelta a la misma máqui
contrario, una unidad que pasa la inspección en ambas máquinas es buena.

a) Represente el problema como una cadena de Markov.

La descripción indica que hay una secuencia de actividades en el proceso: máquina 1, inspección 1, máquina 2, in
En algún momento la pieza se puede desechar, ya sea porque: se daño en alguna de las máquinas o porque algun
la considera defectuosa e irrecuperable. Solo las piezas que pasan ambas inspecciones se consideran buenas.

Los estados del problema son las seis actividades que se le pueden realizar a la pieza: procesar en máquina 1 (M1
máquina 2 (M2), inspección 2 (I2), desechar (D) y vender la pieza buena (B).

Para entender mejor la dinámica se presenta el diagrama de transición de estados:

0,07 0,07

0,95 0,9 0,95

M1 0,9
I1 M2 I2 B

0,03 0,03
0,4 0,05
0,05
 0,95 0,95
M1 0,9
I1 M2 I2 B

0,03 0,03
0,4 0,05
0,05

Por medio de las transiciones mostradas en el diagrama se puede construir la matriz de transición de un paso qu
Cadena de Markov del problema:

M1 I1 M2 I2 D
M1 0 0.95 0 0 0.05
I1 0.07 0 0.90 0 0.03
M2 0 0 0 0.95 0.05
I2 0 0 0.07 0 0.03
D 0 0 0 0 1
B 0 0 0 0 0

Se puede observar que los estados D y B son absorbentes, una vez que se entra en ellos no se puede mover a otr
Los estados M1, I1, M2, I2 son transitorios.

b) Para una pieza que se inicia en la máquina 1, determine el promedio de visitas a cada estado.

Para responder a la pregunta se hace el siguiente cálculo:

Primero se debe hacer el siguiente reconocimiento en la cadena de Markov:

M1 I1 M2 I2 D
M1 0 0.95 0 0 0.05
I1 0.07 0 0.90 0 0.03
M2 0 0 0 0.95 0.05
I2 0 0 0.07 0 0.03
D 0 0 0 0 1
B 0 0 0 0 0

Note como los estados absorbentes ocupan la esquina sureste de la matriz. De no estar en esa posición se deben
y columnas para ubicarlas allí. Recuerde que el orden de los estados en las filas y columnas debe ser el mismo.
La matriz N se muestra en azul.
La matriz A se muestra en verde.

Entonces se realiza la resta de las matrices: I-N:

 1 0 0 0 0
0 1 0 0 - 0.07
0 0 1 0 0
0 0 0 1 0

A la matriz resultante se le encuentra la matriz inversa, resultando:

1.071 1.018 0.981 0.932
0.075 1.071 1.033 0.981
0.000 0.000 1.071 1.018
0.000 0.000 0.075 1.071

El promedio de visitas a cada estado de una pieza iniciada en la máquina 1 es:

M1 I1 M2 I2
1.07123727906 1.0176754151 0.98115465838 0.93209692546

c) Si los tiempos de procesamiento en las máquinas I y II son de 20 y 30 minutos y tiempos de inspección en I y

el tiempo que tarda una pieza en ser procesada.

Con la respuesta del inciso anterior se puede encontrar el valor esperado del tiempo de finalización de la pieza:

M1 I1 M2 I2
Nº de visitas 1.07123727906 1.0176754151 0.98115465838 0.93209693
Tiempo (min) 20 5 30 7

Tiempo 21.4247455811 5.08837707552 29.4346397513 6.52467848

esperado (min)

Tiempo
esperado 62.4724
total (min)

El valor esperado de culminación de una pieza es de 62,47 minutos.

d) Determine el número de pasos que deben ocurrir para que una pieza sea considerada buena o desechada.

Se está solicitando el tiempo para la absorción, que se calcula así:

1.071237 1.017675 0.981155 0.932097 * 1

0.074987 1.071237 1.032794 0.981155 1
0.000000 0.000000 1.071237 1.017675 1
0.000000 0.000000 0.074987 1.071237 1

Como todas las piezas inician en la máquina 1, el número de pasos para que la pieza sea declarada buena o mala
e) Si un lote de 1000 unidades se inicia en la máquina I, determine el promedio de unidades buenas completad

Se debe calcular la probabilidad de que ocurra cada estado absorbente D y B:

1.07124 1.01768 0.98115 0.93210 0.05

0.07499 1.07124 1.03279 0.98115 * 0.03
0.00000 0.00000 1.07124 1.01768 0.05
0.00000 0.00000 0.07499 1.07124 0.03

Luego de iniciar en la máquina 1, la probabilidad de que una pieza sea desechada es 0,1611 y de que salga buena
Si el lote es de 1000 unidades, entonces 838,9 saldrán buenas.

Elaborado por: Ing. Angel González

n empleado puede permanecer con la misma compañía
enas, es importante determinar la probabilidad de llegar a la
tema se inicia en un estado transitorio específico.
forma conveniente con matrices. En primer lugar, la cadena de

ste de la nueva matriz.

za después de que una unidad del producto se completa en

echada antes de inspeccionarla. Después de la inspección, hay
ser devuelta a la misma máquina para trabajarla de nuevo. De lo

a 1, inspección 1, máquina 2, inspección 2.

de las máquinas o porque alguna de las inspecciones
ones se consideran buenas.

za: procesar en máquina 1 (M1), inspección 1 (I1), procesar en

1
0,9
2 B
 0,9
2 B

riz de transición de un paso que representa la

B
0
0
0
0.90
0
1

ellos no se puede mover a otro estado.

a cada estado.

B
0
0
0
0.90
0
1

estar en esa posición se deben reacomodar las filas

olumnas debe ser el mismo.
 0.95 0 0 1.00 -0.95 0.00 0.00
0 0.90 0 = -0.07 1.00 -0.90 0.00
0 0 0.95 0.00 0.00 1.00 -0.95
0 0.07 0 0.00 0.00 -0.07 1.00

y tiempos de inspección en I y II son de 5 y 7 minutos, determine

po de finalización de la pieza:

iderada buena o desechada.

4.0022
= 3.1602
2.0889
1.1462

za sea declarada buena o mala es de 4,0022.

e unidades buenas completadas.

D B
0 0.16111 0.83889
0 = 0.11696 0.88304
0 0.08409 0.91591
0.9 0.03589 0.96411

es 0,1611 y de que salga buena es de 0,83889.