Cadenas de Markov

Universidad de San Carlos de Guatemala

Facultad de Ingeniería

Escuela de Mecánica Industrial

Investigación de Operaciones 2, A+

Ing. Marco Vinicio Monzón

CADENAS DE

MARKOV

Saúl Santiago Sandoval González. 2011-13834

Erick Alexander Velásquez de León. 2011-13856

José Andrés Maldonado. 2011-13990

María Marcella Chávez Gutiérrez. 2011-22840

Guatemala de la Asunción, 11 de septiembre de 2013.

CADENAS DE MARKOV 2013

INTRODUCCIÓN

Las cadenas de Markov fueron creadas por el matemático ruso Andrei

Markov, las cuales se usan para estudiar ciertos comportamientos a largo y corto

plazo de sistemas estocásticos. Cabe mencionar que un sistema estocástico son

sucesiones de eventos gobernados por leyes probabilísticas que evolucionan a lo

largo del tiempo en un conjunto de estados.

Algunos ejemplos de sus aplicaciones es el análisis de mercados, predicción de

ventas, reparto de mercaderías, mantenimiento de maquinaria, etc. y que puede

ser aplicado en varios campos como la biología, finanzas, astrología, meteorología

y muchas más.

Las cadenas de Markov se utilizan, más que todo, para hacer aproximaciones y

previsiones de factores que puedan ser útiles en la gestión de una empresa, a

pesar de no ser un método exacto, sus resultados son útiles para hacer

previsiones a largo plazo.

En este documento se detalla brevemente lo que son cadenas de Markov, su

definición, aplicaciones y se muestra la manera de cómo se resuelven problemas

utilizando este método.


OBJETIVOS

General

Explicar que es una Cadena de Markov y como está estructurada.

Específicos

1. Conocer cómo debe estructurarse la matriz de transición de una cadena de

Markov.

2. Conocer los diferentes tipos de estado de una matriz

3. Conocer qué es un grafo asociado.


MARCO TEÓRICO

“CADENAS DE MARKOV”

Las cadenas de Markov, reciben su nombre en honor al matemático ruso

Andrei Markov (creador de la “Teoría de los números” y de la “Teoría de las

probabilidades”), son herramientas que sirven para analizar el comportamiento de

diferentes tipos de procesos estocásticos, los cuales son procesos en donde se

representan todos y cada uno de los estados, una sucesión de observaciones.

Estas cadenas representan un sistema que varía su estado a lo largo del tiempo,

siendo cada cambio una transición de dicho sistema. Solamente dependen del

estado actual, nunca de los anteriores.

MATRIZ DE TRANSICIÓN

En el instante que se utilizan las cadenas de Markov es conveniente hacer uso de

un sistema físico de planteamento donde se presenten las probabilidades de

transición estacionarias.

Se representa por medio de estados que ocurren en un lugar determinado que

puede ir desde 1 hasta k eventos.

La matriz de transición debe cumplir con ciertas restricciones para que funcione

como una cadena de Markon, estas son:

1. La suma de las probabilidades debe ser igual a 1.

2. Las probabilidades de cada estado debe estar entre 0 y 1.

3. La matriz debe ser cuadrada.


REPRESENTACIÓN GRÁFICA DE UNA MATRIZ DE TRANSICIÓN

Es un arreglo sistemático donde se representan las probabilidades de pasar de un

estado a otro. Esto ayuda a tener una mejor visualización del panorama de la

situación y su comportamiento.

CADENAS DE MARKOV ABSORBENTES

Una matriz absorbente tiene la siguiente forma:

x Y

x Q Ry ceros I

Donde los estados X representan, estados transitorios y Y representa estados

absorbentes.


PROCESO ESTOCÁSTICO

Es la relación entre las variables aleatorias, es decir el proceso necesario de cierta

cantidad de eventos para cumplir con objetivo.

ESTADO TRANSITORIO

Un estado transitorio es aquel que después de haber entrado en este estado

jamás regresará a él.

ESTADO RECURRENTE

Estado donde después de haber entrado a él el proceso definitivamente regresará

al mismo.

EJEMPLOS

EJEMPLO 1

Cada familia norteamericana se puede clasificar como habitante de una zona

urbana, rural o suburbana. Durante un año determinado, el 15% de las familias

urbanas se cambiaron a la zona suburbana y el 5% a la zona rural. El 6% de las

familias suburbanas pasan a la zona urbana y el 4% a la rural, el 4% de las

familias rurales pasan a la zona urbana y el 6% a la suburbana.

Encontrar:

a) La matriz de transición.

b) Realizar el gráfico asociado.

c) ¿Cuál es la probabilidad de que una familia rural en 3 años viva en una

zona urbana?

d) La matriz estable.

SOLUCIÓN


ε 1=urbano

ε 2=suburbano

ε 3=rural

a) La matriz de transición para el orden ε 1, ε2 y ε 3 es:

P=(0.80 0.15 0.050.06 0.90 0.040.04 0.06 0.90)

b) Gráfico asociado

c) Probabilidad de que una familia rural en 3 años viva en una zona urbana.

P3=(0.5399 0.3353 0.12470.1351 0.7593 0.10550.0966 0.1622 0.7411)

E2 E3

E1

0.8

0.90.9

0.06

0.04

0.040.050.06

0.15


La probabilidad de que una familia rural viva en una zona urbana en 3 años es del

9.66%.

d) Matriz estable

P100=(0.2076 0.4918 0.30060.2076 0.4918 0.30060.2076 0.4918 0.3006)

EJEMPLO 2

En una población de 10,000 habitantes, 5000 no fuman, 2500 fuman uno o menos

de un paquete diario y 2500 fuman más de un paquete diario. En un mes hay un

5% de probabilidad de que un no fumador comience a fumar un paquete diario, o

menos, y un 2% de que un no fumador pase a fumar más de un paquete diario.

Para los que fuman un paquete, o menos, hay un 10% de probabilidad de que

dejen el tabaco, y un 10% de que pasen a fumar más de un paquete diario. Entre

los que fuman más de un paquete, hay un 5% de probabilidad de que dejen el

tabaco y un 10% de que pasen a fumar un paquete, o menos. ¿Cuántos individuos

habrá de cada clase el próximo mes?

SOLUCIÓN

NF = no fuman

F1 = fuman uno o menos de un paquete diario

F2 = fuman más de un paquete diario

La matriz de transición para el orden NF, F1 y F2 es:

P=(0.93 0.05 0.020.10 0.80 0.100.05 0.10 0.85)


(NF , F1 ,F 2 )=(5000 2500 2500 )

T=(NF , F1 ,F 2 )∗P

T=(5000 2500 2500 )∗(0.93 0.05 0.020.10 0.80 0.100.05 0.10 0.85)=¿

Después de un mes habrán 5,025 individuos que no fuman, 2,500 que fuman uno

o menos de un paquete diario y 2,475 que fuman más de un paquete diario.

EJEMPLO 3

La Universidad LA SAPIENZA di ROMA ha estudiado el comportamiento general

de sus estudiantes a través de datos recogidos en el departamento de admisiones

y registro estudiantil y obtuvo los siguientes datos: A) 65% de los estudiantes de

nuevo ingreso regresan al año siguiente a realizar el segundo año de ciclo

básico, 15% de segundo año retornará como estudiante de nuevo ingreso y el

resto desertará del Alma Mater. B) El 71% de los estudiantes de segundo año

volverán al año siguiente como estudiantes de tercer año de estudios ya en la

profundización profesional, el 22% regresará a repetir segundo año y el resto no

regresará. C) El 83% de los estudiantes de tercer año regresaran al año siguiente

como estudiantes de último año, 9% volverá como estudiante de tercer año y el

resto no regresará. D) El 87% de los estudiantes de último año se graduarán, el

9% volverá como estudiante de último año y el resto no regresará. Se desea

conocer: a) ¿Cuánto tiempo se espera de estudiantes de primer y segundo año

para que puedan graduarse? b) ¿Cuál es la probabilidad de estudiantes de primer

y segundo año de graduarse? c) ¿Cuál es la probabilidad de un estudiante de

tercer y último año de retirarse?

SOLUCIÓN

Ordenamos la matriz en forma canónica

Q R

0 I


La cual quedaría así:

estados 1 año

2

año 3 año 4 Desertarán Graduarán

1 0.15 0.65 0 0 0.2 0

2 0 0.22 0.71 0 0.07 0

3

0 0 0.09

0.8

3 0.08 0

4 0 0 0

0.0

9 0.04 0.87

Desertará

n 0 0 0 0 1 0

Graduarán 0 0 0 0 0 1

Ahora se restan las matrices I y Q

Ahora se calcula la matriz inversa:

P =

(I – Q) =

0.8

5 -0.65 0 0

0 0.78 -0.71 0

0 0 0.91 -0.83

0 0 0 0.91

1.176471 0.980392 0.764921 0.697676

0.000000 1.282051 1.000282 0.912345

0.000000 0.000000 1.098901 1.002294

0.000000 0.000000 0.000000 1.098901


Para encontrar la probabilidad de pasar a un estado absorbente se debe de

multiplicar la matriz inversa por R

RESPUESTAS:

a) ¿Cuánto tiempo se espera de estudiantes de

primer y segundo año para que puedan

graduarse?

R// Sumando la primera y segunda fila de la matriz inversa, se obtiene que los

estudiante de primer año deberán esperar 3.6294 años mientras que los

estudiantes de segundo año deberán de esperar 3.1947 años.

b) ¿Cuál es la probabilidad de estudiantes de primer y segundo año de

graduarse?

R// esta se obtiene de multiplicar la matriz inversa por R, y resulta que hay una

probabilidad del 60.69% de que los estudiantes de primer años se gradúen,

mientras que con los estudiantes de segundo año, esta aumenta hasta un

79.37%

C) ¿Cuál es la probabilidad de un estudiante de tercer y último año de retirarse?

(I – Q) -1 =

(I – Q) -1 * R =

Desertarán Graduarán

1

0.3930223

0

0.6069777

0

2

0.2062599

3

0.7937400

7

3

0.1280038

6

0.8719961

4

4

0.0439560

4

0.9560439

6


R// hay una probabilidad del 4.39% de que se retire.

CONCLUSIONES

1. Una matriz de Markov debe tener probabilidades para poder construir los

estados en los cuales uno dependerá del otro para que pueda tener la

característica de ser una matriz cuadrada.

2. Los tipos de estados que pueden encontrarse en una cadena de Markov

son: Recurrente o final, absorbente o final especial y Transitorio.

3. Un grafo asociado es la representación gráfica de cómo están

representadas las probabilidades de un estado a otro estado.


RECOMENDACIONES

Cuando se construye una matriz debe verificarse que las filas cumplan con

la sumatoria es igual a 1.

Para aplicar cadenas de Markov a un problema asociado a estos debe

tomarse en cuenta que cuente con parámetros de probabilidad en estados

para poder construir la matriz

Cuando se realizan las cadenas de Markov se debe conocer el concepto

que un estado a futuro dependerá de un estado anterior.


FUENTES DE CONSULTA

Métodos estadísticos en ciencias de la vida. Cadenas de Markov. [En línea].

[Fecha de consulta: 10 de septiembre de 2013]. Disponible en:

http://www.bioingenieria.edu.ar/academica/catedras/metestad/Cadenas

%20de%20Markov-1.pdf

Cadenas de Markov. . [En línea]. [Fecha de consulta: 9 de septiembre de

2013]. Disponible en:

http://halweb.uc3m.es/esp/Personal/personas/jmmarin/esp/PEst/

tema4pe.pdf

VALENTINA, María. Cadenas de Markov de tiempo continuo y

aplicaciones. [En línea]. [Fecha de consulta: 10 de septiembre de 2013].

Disponible en:

http://www.cmat.edu.uy/cmat/biblioteca/documentos/copy_of_monografias/

pdfs/valentina.pdf

Cadenas de Markov, teoría y ejemplos. [En línea]. [Fecha de consulta: 9 de

septiembre de 2013]. Disponible en:

http://investigaciondeoperaciones2markov.blogspot.com/p/teoria-y-

ejemplos.html

Documents

Cadenas de Markov