UNIVERSIDAD NACIONAL DEL SANTA

Escuela Profesional de Ingeniería de Sistemas e Informática

(EPISI)
(CURRÍCULO 2008)

CURSO: INVESTIGACIÓN DE OPERACIONES II

CADENAS DE MARKOV

MODULO UNS 2017

FACILITADOR

Juan Pablo Sánchez Chávez

NVO. CHIMBOTE - 2017

 SEMANA 12
INTRODUCCIÓN, CADENAS DE MARKOV,
PROBABILIDADES DE TRANSICIÓN, DIAGRAMA
DE ESTADOS

Introducción
La cadena de Markov, o modelo o proceso de Markov, es un concepto desarrollado dentro
de la teoría de probabilidad y la estadística que establece una fuerte dependencia entre:
Que tenga lugar un evento y un evento anterior. Su principal utilidad es el análisis del
comportamiento de procesos estocásticos. Un proceso estocástico es aquel que no se puede
predecir. Se mueve al azar. Esta constituido por un conjunto de variables aleatorias que
depende de un parámetro por ejemplo el tiempo.

Una cadena de Markov es una serie de eventos, en la cual la probabilidad de que ocurra un
evento depende del evento inmediato anterior. En efecto, se podría decir que, las cadenas
de este tipo tienen memoria, es decir “Recuerdan” el ultimo evento y esto condiciona las
posibilidades de los eventos futuros. 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, es decir, el resultado del último evento no influye en el resultado de un nuevo
evento. El juego de casinos, es un ejemplo en el que el pasado condiciona al futuro.
Conforme se van jugando las cartas, las probabilidades en las siguientes manos se van
modificando. Las posibilidades en el juego dependen del estado o las condiciones en que se
encuentre el manojo de cartas. Lo mismo es cierto para el pócker, cuando se juegan abiertas
algunas cartas. Nadie apostaría a una carta cuando otro jugador la tiene.

En los negocios, las cadenas de Markov se han utilizado para analizar los patrones de
compra de los consumidores, para pronosticar las concesiones por deudores morosos, para
planear las necesidades de personal y para analizar el reemplazo de equipo. Aunque no es
una herramienta que se use mucho, el análisis de Markov puede proporcionar información
importante cuando es aplicable a una de las situaciones antes mencionada.

El análisis de Markov, es llamado así en honor al matemático ruso Andréi Markov 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. Más importante aún, 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.

Es importante indicar que se analizara por separado la teoría y las aplicaciones, pues estas
últimas son muy variadas. En este sentido, el análisis de Markov es similar a la
programación lineal (PL), aunque no se usa tanto. La tarea más difícil es reconocer cuándo
puede aplicarse. La característica más importante que hay que buscar es la memoria de un
evento a otro.

En la figura 1 se muestra el proceso para generar una cadena de Markov. El generador de

Markov produce uno de n eventos posibles, Ei, donde i = 1, 2, . . . , n, a intervalos

discretos de tiempo (que no tienen que ser iguales). Las probabilidades de ocurrencia para
cada uno de estos eventos dependen del estado del generador. Este estado se describe por el
último evento generado. En la figura 1, el último evento generado fue Ei, de manera que el
generador se encuentra en el estado Si.
La probabilidad de que Ek sea el siguiente evento generado es una probabilidad
condicional: P(Ek / Si). Esto se llama probabilidad de transición del estado Si al estado Ek.
Para describir completamente una cadena de Markov es necesario saber el estado actual y
todas las probabilidades de transición.

En esta sección se presentan dos formas fáciles de exponer las probabilidades de transición.

DIAGRAMA DE ESTADOS: PROBABILIDADES DE TRANSICION (pij / pji)

p31
p33
S1 S3
p13

p12 p21 p43 p34

p42
S2 S4 P44
p24

Figura 2
Un diagrama de estados

Una forma para describir una cadena de Markov es con un diagrama de estados, como el
que se muestra en la figura 2. En ésta se ilustra un sistema de Markov con cuatro estados
posibles: S1, S2, S3 y S4. La probabilidad condicional o de transición de moverse de un
estado a otro se indica en el diagrama. Para simplificar la notación se usan subíndices para
el estado actual y el siguiente. Es decir, p12 = P( S2 / S1). Las flechas muestran las
trayectorias de transición que son posibles. Nótese que no aparecen algunas trayectorias
como por ejemplo de S1 a S4, de S2 a S3, etc. Su ausencia significa que esas trayectorias
tienen probabilidad de ocurrencia igual a cero.

Otro método para exhibir 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 en la tabla 1.
Nótese que, como existen cuatro estados posibles, se necesitan 4 x 4 = 16 probabilidades.
También nótese que cada renglón de la matriz suma 1. Esto se debe a que el sistema debe
hacer una transición.
A:

S1 S2 S3 S4 Total
De: S1 0 p12 p13 0 1

S2 p21 0 0 p24 1

S3 p31 0 p33 p34 1

S4 0 p42 p43 p44 1

Tabla 1
Una matriz de Transición
Las probabilidades de transición son datos para el análisis. Se deben conocer, no existe
manera de derivarlas. En algunas aplicaciones esto puede ser una limitación.

CALCULO DE LAS PROBABILIDADES DE TRANSICIÓN

Ahora que se sabe cómo presentar los datos, ¿qué puede hacerse? Un análisis útil es
pronosticar el estado del sistema después de 1, 2, 3 o más periodos. Esto se llama análisis
de transición, debido a que es a corto plazo y está enfocado a periodos cortos.

0.75
A:
S1 S2
S1

De: S1 0.75 0.25

0.25 0.25
S2 0.25 0.75

S2
Figura 3
0.7
Un ejemplo de dos estados
Considérese la cadena de Markov que se describe en la figura 3. Esta podría representar el
sistema de una copiadora de oficina, poco segura. Si está funcionando un día, existe un 75
% de posibilidades de que al día siguiente funcione y un 25% de posibilidades de que no
funcione. Pero si no está funcionando, hay 75% de posibilidades de que tampoco funcione
al día siguiente y sólo un 25 % de que si lo haga (se lleva mucho tiempo la reparación).

Para comenzar un análisis de transición, se deben conocer el estado actual. Supóngase que
se está comenzando y que hay 75 % de posibilidades de estar en el estado 1 y 25 % de estar
en el estado 2. Esto define el estado actual en forma probabilista. ¿Cuál es la probabilidad
de estar en el estado 1 al día siguiente? Si se comienza en el estado 1 hay 75 % de
posibilidades de seguir ahí. Si se comienza en el estado 2, sólo hay 25 % de cambiar el
estado 1. Así: Hoy Martes 02.07.2019 P(S1)=0.75 y P(S2) = 0.25 → 0.75 + 0.25 = 1
a) Probabilidad de estar el día de mañana (Miércoles 03.07.2019) en el estado 1
P ( S1) = P ( comiencese S1) p11 + P ( comiencese S2)p21 ……… Significa P(S1/S2)
= (0.75) (0.75) + (0.25) (0.25)
= 0.625
Como solo hay dos estados, entonces P ( S2) = 0.375 o sea 1-P(S1) → 1-0625 = 0.375
Después de dos días:
b) Probabilidad de estar después de dos días (Jueves 04.07.2019) en el estado 1
P ( S1) = 0.625 p11 + 0.375 p21
= 0.625 (0.75) + 0.375 (0.25)
= 0.5625 → P(S2) = 0.4375
c) Probabilidad de estar después de tres días (Viernes 05.07.2019) en el estado 1
P ( S1) = 0.5625 p11 + 0.4375 p21
= 0.5625 (0.75) + 0.4375 (0.25)
= 0.53125 → P(S2) = 0.46875
d) Probabilidad de estar después de cuatro días (Sábado 06.07.2019) en el estado 1
P ( S1) = 0.53125 p11 + 0.46875 p21
= 0.53125 (0.75) + 0.46875 (0.25)
= 0.515625 → P(S2) = 0.484375
Como puede observarse, la copiadora no es muy segura. El resumen de los resultados de los
primeros cuatro días son:
P( S1) P( S2 )
Inicio 0.75 0.25
1 (Al día siguiente) 0.625 0.375
2 (Después de 2 días) 0.5625 0.4375
3 (Después de 3 días) 0.53125 0.46875
4 (Después de 4 días) 0.515625 0.484375

Tabla Nº 02

En los sistemas con más estados, los cálculos se vuelven más largos, pero el procedimiento
es el mismo. Considérese el sistema de tres estados que se muestra en la figura 5.
Supóngase que el sistema se encuentra en el estado S1.
P(S1) = p11 = 0.4
P(S2) = p12 = 0.3
P(S3) = p13 = 0.3
Encuentre las probabilidades de transición para los siguientes cuatro ciclos:

Figura 5
Un ejemplo de tres estados
Para el segundo ciclo:
P ( S1) = 0.4 p11 + 0.3 p21 + 0.3 p31
= 0.4 (0.4) + 0.3 (0.1) + 0.3 (0.1)
= 0.22

P ( S2) = 0.4 p12 + 0.3 p22 + 0.3 p32

= 0.4 (0.3) + 0.3 (0.8) + 0.3 (0.3)
= 0.45
P ( S3) = 0.4 p13 + 0.3 p23 + 0.3 p33
= 0.4 (0.3) + 0.3 (0.1) + 0.3 (0.6)
= 0.33

Por supuesto, como el sistema se debe encontrar en algún estado, solo es necesario calcular
dos de estas probabilidades y la tercera puede encontrarse con la siguiente relación:

P( S1) + P( S2) + P( S3) = 1

Ejemplo
P( S1) + P( S2) + P( S3) = 1
0.22 + 0.45 + P( S3) = 1 despejando P( S3) = 1 – 0.22 - 0.45 = 0.33

Los resultados para los primeros cuatro ciclos son:

Inicio P( S1) P( S2 ) P( S3 )
1 0.4 0.3 0.3
2 0.22 0.45 0.33
3 0.166 0.525 0.309
4 0.1498 0.5625 0.2877
5 0.14494 0.58125 0.27381

Tabla Nº 03
Con este análisis puede encontrarse la probabilidad de que el sistema se encuentre en un
estado determinado en cualquier periodo futuro.

Ejercicios:
a) Dada la cadena de Markov siguiente:
A
S1 S2
De S1 0.6 0.4
S2 0.2 0.8

a. Dibújese el diagrama de estados

b. Si el sistema se encuentra en el estado 1, encuéntrese las probabilidades de
transición para los cuatro ciclos siguientes.
b) Considérese el siguiente sistema de tres estados. Supóngase que el sistema se encuentra
en el estado S1.
P(S1) = p11 = 0.5
P(S2) = p12 = 0.2
P(S3) = p13 = 0.3
Encuéntrese las probabilidades de transición para los cuatro ciclos siguientes.