View
218
Download
0
Category
Preview:
Citation preview
7/22/2019 1. Introduccin a las Cadenas de Markov
1/22
INTRODUCCIN A LASCADENAS DE MARKOV
Antonio Hoyos Chaverra
Departamento de Ingeniera Industrial
Facultad de IngenieraUniversidad de Antioquia
Antonio Hoyos Chaverra. Cadenas de Markov
7/22/2019 1. Introduccin a las Cadenas de Markov
2/22
Agenda
1. Objetivo
2. Introduccin
3. Conceptos bsicos
4. Qu es un proceso estocstico?5. Definicin formal de un proceso estocstico
6. Qu es una cadena de Markov?
7. Ejemplos de cadenas de Markov
Antonio Hoyos Chaverra. Cadenas de Markov
7/22/2019 1. Introduccin a las Cadenas de Markov
3/22
Objetivo
Definir lo qu es un proceso estocstico e introducir losconceptos de cadena de Markov y matriz de transicin.
Antonio Hoyos Chaverra. Cadenas de Markov
7/22/2019 1. Introduccin a las Cadenas de Markov
4/22
IntroduccinDeterminismo Indeterminismo
Antonio Hoyos Chaverra. Cadenas de Markov
Racionalidad limitada
No se tiene toda la informacin
No se puede procesar toda la informacin
Toma de decisiones
7/22/2019 1. Introduccin a las Cadenas de Markov
5/22
Conceptos bsicos Espacio muestral: es el conjunto de posibles valores
resultados de un experimento
Probabilidad: es la posibilidad de ocurrencia de un evento
Evento: subconjunto del espacio muestral
Funcin de distribucin: funcin que asigna a cada evento
una probabilidad
Variable aleatoria: una funcin que asigna valores reales a losresultados de un experimento.
Antonio Hoyos Chaverra. Cadenas de Markov
7/22/2019 1. Introduccin a las Cadenas de Markov
6/22
Qu es un proceso estocstico?
Es un proceso que se desarrolla de manera aleatoria en eltiempo.
Mutaciones de un virus
Antonio Hoyos Chaverra. Cadenas de Markov
7/22/2019 1. Introduccin a las Cadenas de Markov
7/22
Qu es un proceso estocstico?
Los ingresos por ventas de una compaa
El desarrollo del trfico en una ciudad
Cantidad de productos en inventario
ndice de homicidios de una regin
La demanda de la energa elctrica.
Estabilidad poltica de una regin
Asistentes a la universidad el da de parcial
Por qu son
procesos
estocsticos?
Otros ejemplos:
Antonio Hoyos Chaverra. Cadenas de Markov
7/22/2019 1. Introduccin a las Cadenas de Markov
8/22
Definicin formal
Proceso estocstico: es una familia de variablesaleatorias , en donde t toma valoresdel conjunto T.
Antonio Hoyos Chaverra. Cadenas de Markov
7/22/2019 1. Introduccin a las Cadenas de Markov
9/22
Descripcin de un proceso estocstico
,
Para describir un proceso estocstico basta conocer la distribucinde probabilidad conjunta de dichas variables.
Para cada tel sistema se encuentra en uno de un nmero finito deestados mutuamente excluyentes; 0, 1, 2, , M
Si T es finito se trata de un proceso discreto
Si T es un subconjunto de los reales se trata de un proceso continuo
Antonio Hoyos Chaverra. Cadenas de Markov
7/22/2019 1. Introduccin a las Cadenas de Markov
10/22
Cadenas de Markov
Una cadena de Markov es un proceso estocstico quecumple con la propiedad de perdida de memoria.
Los estados futuros del proceso dependen nicamente delpresente, por lo mismo son independientes del pasado.
Antonio Hoyos Chaverra. Cadenas de Markov
7/22/2019 1. Introduccin a las Cadenas de Markov
11/22
Cadenas de MarkovDefinicin formal de un proceso markoviano:
Considere el proceso ( +,,,,,)Si
el proceso se encuentra en el estado i en el tiempo
o etapa n.
Un proceso cumple con la propiedad markoviana si:
(+ / , ,, , )
(+ / )
Presente Pasado
Antonio Hoyos Chaverra. Cadenas de Markov
7/22/2019 1. Introduccin a las Cadenas de Markov
12/22
Cadenas de MarkovProbabilidad de transicin
La probabilidad (+ / )se denomina probabilidad de transicin.
Probabilidades estacionarias
Si(+ / )( / ) ( / )se dice que laprobabilidad es estacionaria y se denota como
Probabilidad de transicin en n pasos
(+ / )( / ) () para toda t: 0,1,2
Se cumple:0 1 , , 0,1,2,
=
1
Antonio Hoyos Chaverra. Cadenas de Markov
7/22/2019 1. Introduccin a las Cadenas de Markov
13/22
Cadenas de MarkovMatriz de transicin de una etapa: matriz cuadrada formada por lasprobabilidades de transicin.
Resume todas las probabilidades de transicin para las los M estadosposibles del sistema.
Antonio Hoyos Chaverra. Cadenas de Markov
0 1 , 0,1,2,
=
1
7/22/2019 1. Introduccin a las Cadenas de Markov
14/22
Cadenas de Markov
Representacin grfica de un proceso de Markov
Antonio Hoyos Chaverra. Cadenas de Markov
0 1
1
1 1 1 01
0 1
Un proceso de Markov puede representarse grficamente si seconocen los M estados posibles del sistema y las probabilidades detransicin asociadas a ellos.
7/22/2019 1. Introduccin a las Cadenas de Markov
15/22
Ejemplo: problema del climaConsidere el clima de la ciudad de Manhattan durante el mes de noviembre,los das son lluviosos y soleados. Si el da es soleado la probabilidad de que elsiguiente sea un da soleado es de 0.4, si el da es lluvioso la probabilidad deque el siguiente sea lluvioso es de 0.7.
1. Se trata de una cadena de Markov?2. Si lo es cul es la matriz de transicin?
3. Si lo es represente grficamente la cadena de Markov?
Sea Xn el estado del clima en el da n. Este es una cadena de Markov pues el
clima actual depende del anterior. ,
Antonio Hoyos Chaverra. Cadenas de Markov
S LL
0.4
0.7
0.6
0.3 0.4 0.6
0.3 0.7S
LL
S LL
A i H Ch C d d M k
7/22/2019 1. Introduccin a las Cadenas de Markov
16/22
Ejemplo: problema del jugadorConsidere un jugador cuyo capital inicial es de USD 1, la probabilidad deganar es p con una recompensa de USD 1, la posibilidad de perder es deq=1-p y con un costo de USD 1. El juego termina cuando tiene un capitalde USD 3 o cuando pierde todo su dinero.
1. Se trata de una cadena de Markov?2. Si lo es cul es la matriz de transicin?3. Si lo es represente grficamente la cadena de Markov?
Sea el capital del jugador despus de n juegos dado por:
+ + ,en donde es el resultado del i-simo juego.
Dado que + +
Tenemos que
+
Antonio Hoyos Chaverra. Cadenas de Markov
Si es una cadena de Markov
A t i H Ch C d d M k
7/22/2019 1. Introduccin a las Cadenas de Markov
17/22
Ejemplo: problema del jugadorEl problema del jugador si es una cadena de Markov y su matriz detransicin es:
1 0
1 00 0 00 1
0 00 0 1
Antonio Hoyos Chaverra. Cadenas de Markov
0 1 2 3
1 1
1
1
Esta cadena puede representarse grficamente de la siguiente manera:
0
123
0 1 2 3
A t i H Ch C d d M k
7/22/2019 1. Introduccin a las Cadenas de Markov
18/22
Ejemplo: problema de inventarios Considere un sistema de inventarios (s,S) donde se pide la cantidad
necesaria para elevar el inventario al nivel S = 3 cuando el inventarioes menor que s = 1, en caso contrario no se pide nada. Los pedidosse entregan al principio de la siguiente semana. La demandasemanal tiene la siguiente distribucin de probabilidad (Poisson con
tasa 1.5)
Sea Xn el inventario al final de la semana n.
1. Se trata de una cadena de Markov?
2. Si lo es cul es la matriz de transicin?
Demanda 0 1 2 3 4 5
Probabilidad 0.223 0.335 0.251 0.126 0.047 0.018
Antonio Hoyos Chaverra. Cadenas de Markov
A t i H Ch C d d M k
7/22/2019 1. Introduccin a las Cadenas de Markov
19/22
Ejemplo: problema de inventariosEl inventario final de la semana n esta dado por:
+ : demanda atendida en la semana n: cantidad pedida al final de la semana n-1
Dado que la cantidad mxima en inventario es de 3 unidades, losposibles estados son: 0,1,2,3 Calculemos las probabilidades de transicin:
( 0/ 0) 3 0.126 0.047 0.018 0.191 ( 1/ 0) 2 0.251 ( 2/ 0) 1 0.335 ( 3/ 0) 0 0.223
1
Antonio Hoyos Chaverra. Cadenas de Markov
Si es una cadena de Markov
Antonio Ho os Cha erra Cadenas de Marko
7/22/2019 1. Introduccin a las Cadenas de Markov
20/22
Ejemplo: problema de inventarios
Calculemos las probabilidades de transicin:
( 0/ 1) 1 0.335 0.251 0.126 0.047 0.018 0.777 ( 1/ 1) 0 0.223 ( 2/ 1) 0 ( 3/ 1) 0
1
( 0/ 2) 2 0.251 0.126 0.047 0.018 0.442 ( 1/ 2) 1 0.335 ( 2/ 2) 0 0.223 ( 3/ 2) 0
1
Antonio Hoyos Chaverra. Cadenas de Markov
Antonio Hoyos Chaverra Cadenas de Markov
7/22/2019 1. Introduccin a las Cadenas de Markov
21/22
Ejemplo: problema de inventariosCalculemos las probabilidades de transicin:
( 0/ 3) 3 0.126 0.047 0.018 0.191 ( 1/ 3) 2 0.251 ( 2/ 3
)
1 0.335
( 3/ 3) 0 0.223
1La matriz de transicin es:
0.191 0.2510.777 0.223 0.335 0.2230 00.442 0.3350.191 0.251
0.223 00.335 0.223
Antonio Hoyos Chaverra. Cadenas de Markov
0 1 2 3
0
1
2
3
Antonio Hoyos Chaverra Cadenas de Markov
7/22/2019 1. Introduccin a las Cadenas de Markov
22/22
Bibliografa Hillier, Frederick S., and Gerald J. Lieberman. Introduction to Operations
Research. McGraw-Hill, 2001.
Schwartz, B. (2004). The Paradox of Choice: Why More Is Less.New York:Ecco.
Simon, H. (1957)."A Behavioral Model of Rational Choice", in Models of Man,
Social and Rational: Mathematical Essays on Rational Human Behavior in aSocial Setting.New York: Wiley
Calderon, B. (2006) Cadenas de Markov. Notas de clase.
Antonio Hoyos Chaverra. Cadenas de Markov
Recommended