INVESTIGACION DE OPERACIONES

Tema IV Cadenas de Markov

Competencias Específicas:

 Utiliza las Cadenas de Markov para la resolución de problemas.

 Utiliza el software específico.

Competencias Genéricas:

 Identifica los procesos de markov y aplica el método de solución al área de la

empresa que requiera describir el comportamiento probabilístico de sus diversas
situaciones.

4.1. Introducción a las cadenas de Markov.

4.2. Probabilidad de transiciones estacionarias de n pasos.

4.3. Estado estable.

4.4. Casos especiales (cadenas absorbentes, cadenas cíclicas).

4.5. Uso de software

 Tema IV Cadenas de Markov

4.1. Introducción a las cadenas de Markov.

Las cadenas de Markov tienen la propiedad particular de que las probabilidades que
describen la forma en que el proceso evolucionara en el futuro dependen solo del estado
actual en que se encuentra el proceso y, por lo tanto, son independientes de los eventos que
ocurrieron en el pasado. Muchos procesos se ajustan a esta descripción, por lo que las
cadenas de Markov constituyen una clase de modelo probabilístico de gran importancia.

Procesos Estocásticos

Un proceso estocástico se define como una colección indexada de variables aleatorias * +,

donde el índice t toma valores de un conjunto T dado. Con frecuencia T se considera el
conjunto de enteros no negativos mientras que representa una característica de interés
cuantificable en el tiempo t. Por ejemplo, puede representar los niveles de inventario al
final de la semana t.

Los procesos estocásticos son de interés para describir el comportamiento de un sistema en

operación durante algunos periodos. Un proceso estocástico tiene la siguiente estructura.
La condición actual del sistema puede estar en una de M + 1 categorías mutuamente
excluyentes llamadas estados. Por conveniencia en la notación, estos estados se etiquetan 0,
1, 2, . . ., M. La variable aleatoria representa el estado del sistema en el tiempo t, de
manera que sus únicos valores posibles son 0, 1, . . ., M. El sistema se observa en puntos del
tiempo dados, etiquetados
t = 0, 1, 2, . . . De esta forma, los procesos estocásticos * + * + proporcionan
una representación matemática de la forma en que evoluciona la condición del sistema
físico a través del tiempo.

Este tipo de procesos se conocen como procesos estocásticos de tiempo discreto con
espacio de estados finito.

Matriz de transición. Es una matriz cuadrada con elementos no negativos tales que la suma
de los elementos de cada renglón es uno.

Matriz estocástica. Es una matriz cuadrada en la que cada una de sus filas es un vector de
probabilidad.
Ejemplo de clima

El clima en el pueblo de Centerville puede cambiar con rapidez de un día a otro. Sin
embargo, las posibilidades de tener clima seco (sin lluvia) mañana es de alguna forma mayor
si hoy está seco, es decir, si no llueve. En particular, la probabilidad de que mañana este seco
es de 0.8 si hoy está seco, pero es de solo 0.6 si hoy llueve. Estas probabilidades no cambian
si se considera la información acerca del clima en los días anteriores a hoy.
La evolución del clima día tras día en Centerville es un proceso estocástico. Si se comienza
en algún día inicial (etiquetado como día 0), el clima se observa cada día t, para t = 0, 1, 2, . .
El estado del sistema en el día t puede ser

Estado 0 = El día t es seco, o bien

Estado 1 =El día t es lluvioso

Así, para t = 0, 1, 2, . . ., la variable aleatoria Xt toma los valores,

{ }

El proceso estocástico * + * + proporciona una representación matemática

de la forma en que evoluciona el clima en Centerville a través del tiempo.

Ejemplo de inventarios

La tienda de fotografía de Dave tiene el siguiente problema de inventario. El negocio tiene

en almacén un modelo especial de cámara que se puede solicitar cada semana. Sean D1, D2,
. . . representan las demandas respectivas de esta cámara (el número de unidades que se
venderían si el inventario no se agota) durante la primera, segunda semanas, . . .,
respectivamente, entonces, la variable aleatoria Dt (para t = 1, 2, . . .) es

= número de cámaras que se venderían en la semana t si el inventario no se agota. (Este

número incluye las ventas perdidas cuando se agota el inventario.)

Se supone que las son variables aleatorias independientes e idénticamente distribuidas

que tienen una distribución Poisson con media de 1. Sea el número de cámaras que se
tiene en el momento de iniciar el proceso, el número de cámaras que se tienen al final de
la semana 1, el número de cámaras al final de la semana 2, etc., entonces la variable
aleatoria (para t = 0, 1,2, . . .) es

= número de cámaras disponibles al final de la semana t.

Suponga que , de manera que la semana 1 se inicia con tres camaras a mano.

* +
es un proceso estocástico donde la variable aleatoria representa el estado del sistema en
el tiempo t, a saber

Estado en el tiempo t = número de cámaras disponibles al final de la semana t.

Como propietario de la tienda, Dave desearía aprender más acerca de cómo evoluciona este
proceso estocástico a través del tiempo mientras se utilice la política de pedidos actual que
se describe a continuación
.
Al final de cada semana t (sabado en la noche), la tienda hace un pedido que le entregan en
el momento de abrir la tienda el lunes. La tienda usa la siguiente política para ordenar:

En consecuencia, el nivel de inventarios fluctúa entre un mínimo de cero y un máximo de

tres cámaras, por lo que los estados posibles del sistema en el tiempo t (al final de la semana
t) son

Estados posibles = 0, 1, 2, o 3 cámaras disponibles.

Como cada variable aleatoria (t = 0, 1, 2, . . .) representa el estado del sistema al final de la

semana t, sus únicos valores posibles son 0, 1, 2, 3. Las variables aleatorias son
dependientes y se pueden evaluar en forma iterativa por medio de la expresión

𝑚𝑎𝑥* − 𝐷𝑡+ + 𝑆 𝑋𝑡
𝑋𝑡+
𝑚 𝑥*𝑋𝑡 − 𝐷𝑡+ + 𝑆 𝑋𝑡 ≥

Para t = 0, 1, 2, . . .

Definición de una Cadena de Markov

Sea Xi una variable aleatoria que caracteriza el estado del sistema en puntos discretos en el
tiempo t = 1, 2… . La familia de variables aleatorias {Xi} forma un proceso estocástico con
una cantidad finita o infinita de estados.

Proceso de Markov. Un proceso estocástico es un proceso de Markov si un estado futuro

depende sólo del estado inmediatamente anterior. Esto significa que dados los tiempos
cronológicos , la familia de variables aleatorias { } * + es
un proceso de Markov si
 { } { }

En un proceso Markoviano con n estados exhaustivos y mutuamente excluyentes, las

probabilidades en un punto específico del tiempo t = 0,1,2,… se definen como

* +

Esto se conoce como probabilidad de transición en un paso al ir del estado i en el instante t -

1 al estado j en el instante t. Por definición, tenemos

≥ ( )

La notación utilizada en la matriz es una forma conveniente de resumir las probabilidades de

transición en un paso:

( )

La matriz P define una cadena de Markov. Tiene la propiedad de que todas sus
probabilidades de transición son estacionarias e independientes a lo largo del tiempo.

Ejemplo # 1 (Problema del jardinero)

Cada año, durante la temporada de siembra de marzo a septiembre, un jardinero realiza una
prueba química para verificar la condición de la tierra. Según el resultado de la prueba, la
productividad en la nueva temporada puede ser uno de tres estados: (1) buena, (2) regular y
(3) mala. A lo largo de los años, el jardinero ha observado que la condición de la tierra del
año anterior afecta la productividad del año actual y que la situación se describe mediante la
siguiente cadena de Markov:

Estado del sistema

Este año
1 2 3

1 5
Estado del sistema
2 ( 5 5)
el siguiente año
3
Las probabilidades de transición muestran que la condición de la tierra puede o deteriorarse
o permanecer como está pero nunca mejorar. Por ejemplo, si la condición de la tierra es
buena en este año (estado 1) hay 20% de que no cambie el año siguiente, 50% de
probabilidad de que sea regular (estado 2), y 30% de probabilidad de que se deteriorará a
una condición mala (estado 3). El jardinero modifica las probabilidades de transición P
utilizando un fertilizante orgánico. En este caso, la matriz de transición se vuelve:

1 2 3

1
2 ( )
3 5 55

El uso de fertilizante puede conducir a mejorar las condiciones del suelo.

4.2. Probabilidad de transiciones estacionarias de n pasos.

Dada la matriz de transición P de una cadena de Markov y el vector de probabilidades

( ) ( ) ( ) ( )
iniciales { }, las probabilidades absolutas {
} después de ( ) transiciones se calculan como sigue:

( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )

( ) ( )

La matriz Pn se conoce como la matriz de transición de n pasos. A partir de estos cálculos,

podemos ver que

Éstas se conocen como ecuaciones de Chapman-Kolomogorov.

Ejemplo #2: La siguiente matriz de transición es aplicable al problema del jardinero con
fertilizante.

1 2 3
1 33
2 ( )
3
5 55

La condición inicial de la tierra es buena, es decir a(0) = (1,0,0). Determine las probabilidades
absolutas de los tres estados del sistema después de 1,8 y 16 temporadas de siembra.

5 5 55
( ) ( 5 5 5 )
5 55 5 5

5 5 5
( ) ( 5 5 5 )
5 55 5 5 5

Por lo tanto, las probabilidades absolutas requeridas se calculan como

( )
( ) ( ) ( )
5 55

5 5 55
( ) ( )( ( )
5 5 5 ) 5 5 55
5 5

5 5 5
( ) ( ) ( ( )
5 5 5 ) 5 5 5
5 5 5

Las filas de P8 y el vector de probabilidades absolutas a(8) son casi idénticos. El resultado es
más evidente para P(16). Ello las probabilidades absolutas se vuelven independientes del a(0)
inicial. Las probabilidades resultantes se conocen como probabilidades de estado estable.
Ejemplo #3 Autobuses del sureste es una compañía de arrendamiento de autobuses que los
renta en 3 regiones: Norte, Central y Sur; de datos estadísticos se ha determinado que de los
autobuses que se rentan cada mes, en el norte 40% van a una región del norte, 20%
terminan en la región central y 40% van la región del sur. De manera similar la compañía ha
determinado que cada mes 50% de los autobuses que se rentan en la región central se
devuelven en la misma, 20% van a la región del norte y el 30% restante van a la región del
sur. Por último de los autobuses que se rentan en la región del sur, 35% van a la región del
norte, 50% van a la región central y 15% se devuelven en la región del sur. Determinar la
matriz de transición de un paso y de n pasos.

Matriz de transición de un paso:

N C S
N
C ( )
S

Matriz de transición de n pasos:

( )( ) ( )

En la matriz de transición P2, se puede apreciar que un autobus que parte de la región norte,
al siguiente mes la probabilidad de estar en la región norte es de 0.34, en la región central
de 0.38 y en la región del sur de 0.28. De igual manera se obtiene las probabilidades para las
regiones central y sur. A continuación se calculan las matrices de transición de P3, P4 y de
P8, redondeando las probabilidades a 5 dígitos.

( )( ) ( )

( )( ) ( )

( )( )

( )
La matriz de transición de ocho pasos tiene la característica de que los tres renglones poseen
elementos idénticos, lo que significa que la probabilidad de que un autobús esté en un
estado en particular es independiente del estado en que estaba ocho pasos antes. A estas
probabilidades a las que se llegan después de n pasos, se les denomina probabilidades de
estado estable y en algunas ocasiones probabilidades en equilibrio o probabilidades a largo
plazo. En la siguiente sección se utilizará un procedimiento más directo para calcular estas
probabilidades.

4.3. Estado estable

Estado Estable: Se puede decir que el estado estable es la distribución de probabilidades
que en cierto punto quedará fija para el vector P y no presentará cambios en periodos
posteriores.

El comportamiento de largo plazo de una cadena de Markov se describe mediante el estado

estacionario. Si P es la matriz de transición de una cadena de Markov ergódica deM estados,
entonces existe un vector tal que:

( )

El término probabilidad de estado estacionario significa que la probabilidad de encontrar el

proceso en un cierto estado, por ejemplo j , después un número grande de transiciones
tiende al valor y es independiente de la distribución de probabilidad inicial definida para
los estados. El vector es llamado distribución de estado estacionario o distribución de
equilibrio de la cadena de Markov.

El vector a menudo se llama distribución de estado estable, o

también distribución de equilibrio para la cadena de Markov. Para encontrar la distribución
de probabilidades de estado estacionario para una cadena dada cuya matriz de transición es
P, se utiliza la siguiente expresión:

( ) ( ) ( ) ( + ) ( + ) ( + ) ( + )
( )( ) ( )

Esta expresión se puede utilizar para calcular las probabilidades para cada periodo, dado
una probabilidad inicial, por ejemplo si las probabilidades iniciales de cada una de las tres
regiones es de:

( 5 )
Calcular la probabilidad de que los autobuses se encontrarán en cada región después de un
periodo y después dos periodos.

Probabilidad después de un periodo:

Periodo 0 N C S Periodo 1

( )( ) ( )

Probabilidad después de dos periodos:

Periodo 1 N C S Periodo 2

( )( ) ( )

Si se siguen realizando estos cálculos, la probabilidad que se obtendrá, después de n

periodos será equivalente a las probabilidades obtenidas en cada renglón de la matriz de
transición P8 en la sección anterior.

Una manera directa de encontrar el vector es de la siguiente

manera:

( )( ) ( )

Multiplicando el vector por la matriz e igualando al vector, se obtiene el sistema de M

ecuaciones simultáneas con M incógnitas.

Una de las M ecuaciones es redundante y para resolver el sistema se agrega la ecuación:

Para el ejemplo 3 se tiene:

 ( )( 5 ) ( )
5 5 5

5
5 5
5

El sistema de tres ecuaciones con tres incógnitas se escribe como:

− 5
− 5 5

Resolviendo el sistema de ecuaciones por el método de Gauss-Jordan.

(− ⁄5 ⁄5 ⁄ | ) ( ⁄5 ⁄ | ⁄5 )
⁄5 − ⁄ ⁄ − ⁄ ⁄ − ⁄5

− ⁄ ⁄ 55⁄

⁄ || ⁄ || ⁄
⁄ ⁄ 5 ⁄
( )
( )

La solución del sistema es: , resultado que

es idéntico a los renglones de la matriz de transición P8 obtenido en la sección anterior.

Ejemplo #4 Tres operadores de telefonía celular que se encuentran en el mercado, Tigo,

Movistar y Comcel; se distribuyen según un estudio realizado, la población de
consumidores de la siguiente manera

Movistar presenta el 30% de los consumidores

Tigo posee en 30% de los consumidores totales
Comcel tiene el 40% restante de los clientes del mercado
El mismo estudio permitió determinar que:

Los individuos que están en Movistar tienen una probabilidad de 30% de quedarse en la
misma operadora, una de 50% de cambiar a Tigo, y una de 20% para pasarse a Comcel.
Los individuos que están en Tigo tienen una probabilidad de 70% de quedarse en la misma
operadora, una de 10% de cambiarse a Movistar, y una de 20% para pasarse a Comcel.
Los individuos que están en Comcel tienen una probabilidad de 50% de quedarse en la
misma operadora, una de 30% de cambiar a Tigo , y una de 20% para pasarse a Movistar.

Solución

Con la información suministrada podemos diseñar tanto nuestro vector de probabilidad P 0

así como la matriz de transición.

Matriz T M T C
M 0.3 0.5 0.2
T 0.1 0.7 0.2
C 0.2 0.3 0.5
Matriz de Transición

Vector P0 0.3 0.3 0.4

Vector de Probabilidad P0

Si queremos saber como será la distribución de probabilidades en el periodo siguiente

tenemos que:

Si queremos conocer la distribución de probabilidad en el periodo 2 procedemos de la

misma manera

Y así sucesivamente

Entonces para conocer cuál sería la distribución de los clientes por operador en el periodo
uno, procedemos así:

5
( )( )
5

( )
Por lo tanto en el periodo siguiente Movistar tendrá en 20% de los clientes, tigo el 48% y
Comcel 32% restantes

Así mismo podemos proceder para los siguientes periodos, encontrando que

M T C
P0 0.3 0.3 0.4
P1 0.2 0.48 0.32
P2 0.172 0.532 0.296
P3 0.164 0.5472 0.2888
P4 0.16168 0.55168 0.28664
P5 0.161 0.553008 0.285992
P6 0.1607992 0.5534032 0.2857976
P7 0.1607396 0.55352112 0.28573928
P8 0.160721848 0.553556368 0.285721784
P9 0.160716548 0.553566917 0.285716535
P10 0.160714963 0.553570076 0.285714961
P11 0.160714489 0.553571023 0.285714488
P12 0.160714347 0.553571307 0.285714346
P13
P14
P15
P16

Como observamos a partir del periodo 9 los cambios en la distribución de los clientes es
mínima, por lo cual se asume que el valor del estado estable es [ 0.1607 0.5535 0.2857]
Tomando valores aproximados y de 4 dígitos.

4.4. Casos especiales (cadenas absorbentes, cadenas cíclicas).

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.

1. Un estado j es absorbente si está seguro de regresar a sí mismo en una transición; es

decir, pij =1
2. Un estado j es transitorio si puede llegar a otro estado pero no puede regresar desde
( )
otro estado. Matemáticamente, esto sucederá si, , para todas las i.
3. Un estado j es recurrente si la probabilidad de ser revisitado desde otros estados es
1. Esto puede suceder si, y sólo si, el estado no es transitorio.
4. Un estado j es periódico con periodo de t > 1 si es posible un retorno sólo en t, 2t,
( )
3t,… pasos. Esto significa que cuando n no es divisible entre t.
Con base en las definiciones dadas, una cadena de Markov finita no puede constar de todos
los estados transitorios porque, por definición, la propiedad transitoria requiere entrar a
otro estado de “atrapamiento” y nunca volver a visitar el estado transitorio. El estado de
“atrapamiento” no necesita ser un solo estado absorbente. Por ejemplo, considere la cadena

( )

Los estados 1 y 2 son transitorios porque no se puede volver a entrar a ellos una vez que el
sistema se queda “atrapado” en los estados 3 y 4. Un conjunto cerrado lo constituyen los
estados 3 y 4, que en cierta forma desempeñan el papel de un estado absorbente. Por
definición, todos los estados de un conjunto cerrado deben comunicarse, lo cual significa
que es posible ir de cualquier estado a cualquier otro estado del conjunto en una o más
( )
transiciones; es decir, para todas las ≥ . Observe que cada uno de los
estados 3 y 4 puede ser absorbente si p33 =p44.

Se dice que una cadena de Markov es ergódica si todos los estados son recurrentes y
aperiódica (no periódica). En este caso las probabilidades absolutas después de n
( )
transiciones, ( ) , siempre convergen de forma única a una distribución limitante
(estado estable) que es independiente de las probabilidades iniciales a(0).

Ejemplo #4 (Estados absorbentes y transitorios)

Considere la cadena de Markov del jardinero sin fertilizante:

( )
5 55
Para demostrar el cálculo del tiempo del primer paso a un estado específico desde todos los
demás, considere el paso de los estados 2 y 3, (regular y malo) al estado 1 (bueno).Por lo
tanto, j=1 y

( − ) − 5 5
( ) ( ) ( )
55 − 5

De modo que
5 5 5
( ) ( )( ) ( )
Por lo tanto, se requerirán 12.5 temporadas en promedio, para pasar la tierra regular a tierra
buena, y 13.34 temporadas para ir de la tierra mala a la tierra buena. Pueden realizarse
cálculos similares para obtener desde ( − ) ( − )

Análisis de los estados absorbentes

En el problema del jardinero, sin fertilizante la matriz de transición se da como

5
( 5 5)

Los estados 1 y 2 (condiciones de tierra buena y regular) son transitorios, y el estado 3

(condición de tierra mala) es absorbente, porque una vez que llega a ese estado el sistema
permanecerá allí por tiempo indefinido. Una cadena de Markov puede tener más de un
estado absorbente. Por ejemplo, un empleado puede permanecer con la misma compañía
hasta su retiro o renunciar antes (dos estados absorbentes). En estos tipos de cadenas, nos
interesa determinar la probabilidad de llegar a la absorción y el número esperado de
transiciones para llegar a ella, dado que el sistema se inicia en un estado transitorio
específico.
Por ejemplo, en la cadena de Markov antes dada, si actualmente la tierra es buena, nos
interesará determinar el promedio de temporadas de siembra hasta que la tierra se vuelva
mala, e igualmente la probabilidad asociada con esta transición.
El análisis de las cadenas de Markov con estados absorbentes puede realizarse de forma
conveniente con matrices. En primer lugar, la cadena de Markov se particiona como sigue:

( | )

La disposición requiere que todos los estados absorbentes ocupen la esquina sureste de la
nueva matriz. Por ejemplo, considere la siguiente matriz de transición:

1 2 3 4

1
2
( )
3 5
4
La matriz P puede reacomodarse y particionarse como

1 2 3 4

1
2 (5 | )
3
4

En este caso, tenemos

( ) ( ) ( )
5
Dada la definición de A y N y el vector columna unitario 1 (de todos los elementos1), se
puede demostrar que:

Tiempo esperado en el estado j iniciado en el estado i=elemento (i,j) de (I - N)-1

Tiempo esperado para la absorción = (I - N)-1 1
Probabilidad de la absorción = (I - N)-1 A

Ejemplo # 5 Se procesa un producto en secuencia en dos máquinas, I y II. La inspección se

realiza después de que una unidad del producto se completa en cualquiera de las máquinas.
Hay 5% de probabilidades de que una unidad sea desechada antes de inspeccionarla.
Después de la inspección, hay 3% de probabilidades de que la unidad sea desechada, y 7%
de probabilidades de ser devuelta a la misma máquina para trabajarla de nuevo. De lo
contrario, una unidad que pasa la inspección en ambas máquinas es buena.

(a) Para una pieza que se inicia en la máquina 1, determine el promedio de visitas a cada
estado.
(b) Si un lote de 1000 unidades se inicia en la máquina I, determine el promedio de unidades
buenas completadas.

Para la cadena de Markov, el proceso tiene 6 estados: iniciar en 1(s1), inspeccionar después
de I (i1), iniciar en II (s2), inspección después de II (i2), desechar después de la inspección I o
II (J), y buena después de II (G). Los estados J y G son estados absorbentes. La matriz de
transiciones se da como

S1 i1 s2 i2 J G

S1
I1
S2 |
I2 |
J
G ( )
Por lo tanto,

S1 i1 s2 i2 J G
S1 5 5
I1
S2 ( ) ( )
I2
5 5

Obtenemos

− 5
( − ) (− − ) ( )
− 5
−

5
( − ) ( )( ) ( )
5

La fila superior de (I - N)-1 muestra que, en promedio, la máquina I es visitada 1.07 veces, la
inspección I es visitada 1.02 veces, la máquina II es visitada .98 veces, y la inspección II es
visitada .93 veces. La razón por la que el número de visitas en la máquina I y la inspección I
sea mayor que 1 son el retrabajo y la reinspección. Por otra parte, los valores
correspondientes para la máquina II son menores que 1 porque algunas piezas se desechan
antes de que lleguen a la máquina II. En realidad, en condiciones perfectas (ningunas piezas
se desechan o retrabajan), la matriz (I - N)-1 demostrará que cada estación es visitada
exactamente una vez (compruébelo asignando una probabilidad de transición de 1 a todos
los estados). Por supuesto, la permanencia en cada estado podría diferir. Por ejemplo, si los
tiempos de procesamiento en las máquinas I y II son de 20 y 30 minutos y si los tiempos de
inspección en I y II son de 5 y 7 minutos, entonces una pieza que inicia en la máquina 1 será
procesada (es decir, desechada o terminada) en (1.07 x 20) + (1.02 x 5) + (.98 x 30) + (.93 x 7)
= 62.41 minutos.
Para determinar la cantidad de piezas terminadas en un lote inicial de 1000 piezas, podemos
ver en la fila superior de (I - N)-1 A que

Probabilidad de que una pieza sea desechada = .16

Probabilidad de que una pieza sea terminada = .84

Esto significa que 1000 X .84 = 840 piezas serán terminadas en cada lote inicial de 1000.