Cadena de Markov

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 30

PROGRAMACIÓN

DINAMICA ESTOCASTICA
CONCEPTOS

 La programación dinámica brinda la teoría matemática


necesaria para la toma secuencial de decisiones bajo
incertidumbre. El matemático Richard Bellman inventó la
programación dinámica en 1953 y desde allí ha sido
utilizada con éxito en campos como la física, biología,
computación, economía, administración y cualquier clase
de problema estocástico factible de ser discretizado y
secuencializado, en donde la información acerca de los
parámetros con incertidumbre se vuelven disponibles en
etapas.
CONCEPTOS
 PROCESOS ESTOCASTICOS: modelos de probabilidad de procesos que
evolucionan en el tiempo de una manera probabilística
 Un proceso estocástico se define como una colección indexada de variables
aleatorias {Xt}, donde el índice t toma valores de un conjunto T dado. Con
frecuencia T se considera el conjunto de enteros no negativos mientras que
Xt representa una característica de interés cuantificable en el tiempo t.
 Por ejemplo, Xt puede representar los niveles de inventario al final de la
semana t.
 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 Xt 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 {Xt}={X0,
X1, X2, . . .} proporcionan una representación matemática de la forma en que
evoluciona la condición del sistema físico a través del tiempo.
EJEMPLO DEL 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 esta seco, es decir, si no llueve. En particular, la probabilidad de que
mañana este seco es de 0.8 si hoy esta 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
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 numero 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
 Dt=numero de cámaras que se venderían en la semana t si el inventario no se
agota. (Este numero incluye las ventas perdidas cuando se agota el
inventario.)
 Se supone que las Dt son variables aleatorias independientes e idénticamente
distribuidas que tienen una distribución Poisson con media de 1. Sea X0 el
numero de cámaras que se tiene en el momento de iniciar el proceso, X1 el
numero de cámaras que se tienen al final de la semana 1, X2 el numero de
cámaras al final de la semana 2, etc., entonces la variable aleatoria Xt (para
t=(0, 1,2, . . .) es
EJEMPLO DE INVENTARIOS
 Xt=numero de cámaras disponibles al final de la semana t.
 Suponga que X0= 3, de manera que la semana 1 se inicia con tres cámaras a
mano.
 {Xt}={X0, X1, X2, . . .}
 es un proceso estocástico donde la variable aleatoria Xt representa el estado
del sistema en el tiempo t, a saber
 Estado en el tiempo t=numero de cámaras disponibles al final de la semana t.
 Como propietario de la tienda, Dave desearía aprender mas acerca de como
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.
EJEMPLO DE INVENTARIOS
 Al final de cada semana t (sábado 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:
 Si Xt=0, ordena 3 cámaras.
 Si Xt>0, no ordena ninguna cámara.
 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 Xt (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 Xt son dependientes y se pueden evaluar en forma iterativa por medio
de la expresión
CADENAS DE MARKOV
CONCEPTOS

 Las cadenas de Markov tienen la propiedad particular


de que las probabilidades que describen la forma en
que el proceso evolucionará 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.
CONCEPTOS
CONCEPTOS
CONCEPTOS
CONCEPTOS
EJEMPLO DEL 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 esta seco, es decir, si no llueve. En particular, la probabilidad de que
mañana este seco es de 0.8 si hoy esta 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
EJEMPLO DEL CLIMA
EJEMPLO DEL CLIMA
EJEMPLO DE INVENTARIO
EJEMPLO DE INVENTARIO
 Distribución de Poisson

𝑘
−𝜆
𝜆
𝑃 𝑥 = 𝑘 = 𝑒 𝑘!
0
EJEMPLO DE INVENTARIO
EJEMPLO DE INVENTARIO
EJEMPLO DE INVENTARIO

 de regreso al mismo estado, cuando la tienda de cámaras transita del final de


una semana al final de la siguiente. El numero junto a cada flecha
proporciona la probabilidad de que ocurra esa transición en particular cuando
la tienda de cámaras tiene el estado que esta en la base de la flecha.
EJEMPLO DE ACCIONES
EJEMPLO DE ACCIONES
EJEMPLO DE ACCIONES
PROBABILIDAD DE TRANSICIÓN DE n
pasos pijn
 ECUACIONES DE CHAPMAN-KOLMOGOROV: Esta ecuación me permite
calcular la matriz de transición de n pasos
EJEMPLO DEL CLIMA

 Si el clima esta en el estado 0 (seco) en el estado inicial, cual es la


probabilidad de estar dos días después en el estado 0 (seco).

 Si el clima esta en el estado 1, la probabilidad de estar en el estado 0 dos días


después.
EJEMPLO DEL CLIMA
EJEMPLO DE INVENTARIOS
EJEMPLO DE INVENTARIOS

También podría gustarte