2. definición de cadena de markov propiedad …. i.o.e. diplomatura de estadística. cadenas de...

U P C I.O.E. Diplomatura de Estadística U P C I.O.E. Diplomatura de Estadística Cadenas de Markov. Introducción. SEMANA 1

SESIÓN 2.a

CADENAS DE MARKOV. INTRODUCCIÓN

1. Noción de Proceso Estocástico. Definición. P.E. asociados a un sistema.

2. Definición de Cadena de Markov Propiedad Markoviana y estacionariedad

3. Matriz de Probabilidades de transición y Diagrama de estados.

4. Ejemplos de Cadenas de Markov.

tresteve

Cap. 14 Hillier F.S., Lieberman G.J. “Introduction to Operations Research” Holden day Inc. 1986.

Identificar elproblema

Planificación delestudio

Recogida de datos

Formular eImplementar el

modelo

Pruebasdel

modeloValidar elmodelo

Ensayo dealternativasAnálisis deresultados

ResultadosInsatisfactorios

Ciclo metodológico de la I.O.

U P C I.O.E. Diplomatura de Estadística U P C I.O.D. Diplomatura de Estadística

Implementar lassoluciones

SISTEMA REAL

MODELO(s)

U P C I.O.E. Diplomatura de Estadística U P C I.O.E. Diplomatura de Estadística Cadenas de Markov. Introducción

Definición de proceso estocástico.

Es una colección indexada de variables aleatories { }TtXt ∈ ,

t pertenece a un conjunto T conocido.

Espacio de Estados I : Conjunto de valores que puede tomar cada Xt

Conjunto de Índices T

Discreto Continuo

Discreto Cadena de parámetro discreto

Cadena de

parámetro continuoEspacio

deEstados I

Continuo Proceso estocástico deparámetro discreto y deestados continuo

Proceso estocástico deparàmetre continuo yestados continuo

Clasificación de los procesos estocásticos


SISTEMA FÍSICO. PROCESOS ESTOCÁSTICOS INVOLUCRADOS

- { }K,,21=kNk Número de clientes en la cola al salir de la tienda el k-ésimo. { }K,,, 210=I ,.

- { }TtX t ∈ Número de clientes en el instante t.

{ }K,,, 210=I , { }∞<≤= ttT 0 ,- { }TkWk ∈ Tiempo que espera el cliente k antes de ser atendido:

{ }∞<≤= wwI 0 , { }K,,, 321=T- { }TtYt ∈ Tiempo total de trabajo del empleado hasta el instante t :

),0[ ∞=I , { }∞<≤= ttT 0 .

CLIENTES

COLA

EMPLEADO

TIENDA


x

y(xk,yk)(xk-1,yk-1)

(xk+1,yk+1) ??

Se registra su posicióncada 0,5 seg.

P(xk+1=x , yk+1=y | (xk , yk), (xk-1 , yk-1), … )


CADENA de MARKOV FINITA ( I Finito )

1. Propiedad Markoviana:

El proceso ha tomado una secuencia de valores: x0 , x1, x2, … xk-1=j ∈ I

=

=Ρ=

=

======Ρ

+

−−−−

+

iXjX

xXxXxXxXiXjX

k

k

kkkkk

k

1

00112211

1

,,,,, K

para todo valor k y toda secuencia de estados x0 , x1, x2, … xk-1= j , xk= i ∈ I.

2. Estacionariedad:

Para todo par de estados Iji ∈, se cumple:

pijk

kiX

jXiX

jX =

=

=Ρ=

=

=Ρ +

0

11 K,,,, 210=k


CADENA de MARKOV FINITA.

Las probabilidades pij forman una matriz de Probabilidades de Transición: Para I={0,1,2,3,…M}

Mipppp

pp

ij

M

jij

MMM

M

,...,,,,, 21001Ρ0

0

000

=≥=

= ∑

=L

MOM

L

(Matriz estocástica) .

Diagrama de transiciones:

i

j

pij > 0

pji = 0


CADENA de MARKOV FINITA. (Ejemplos)

Aprobar una asignatura

Xk = Resultado del examen final en el k-ésimo intento. 1= suspender, 0= aprobar.

Si Xk-1=1 presenta una distribución de Bernuoilli: P(Xk =0| Xk-1=1 )=α P(Xk =1| Xk-1=1 )=1-αSi Xk-1=0 P(Xk =0| Xk-1=0 )=1 P(Xk =1| Xk-1=0 )=0

−

=

=

αα 101

2221

1211

pppp

P 0 1

α α−1

1



Ejemplo de la Ruina del jugador.

Dos jugadores A, B de poker. A tiene una probabilidad p de ganar una mano (q de perder)Apuestan 1 € en cada mano. Entre los dos tienen 4 €{Xk}, Colección de variables aleatorias.Xk = cantidad en el bolsillo del jugador A tras la k-ésima mano. Inicio de partida X0 =2

=

10000000

00000000001

pqpq

pqP

0 1 2 3 4 1

1

p p

q

p

q q

Supongamos que en la mano k, Xk = 2,

P(Xk+1=4| Xk = 2) = 0 P(Xk+1=3| Xk = 2) = p P(Xk+1=2| Xk = 2) = 0 P(Xk+1=1| Xk = 2) = q P(Xk+1=0| Xk = 2) = 0

A pierdela partida A gana la

partida



Tiempo de funcionamiento de un aparato. ( Limitada a < k+1 periodos )

−

=

−−

00001000

0000000000

1

210

P

11

22

11

00

LL

LL

MOOMMM

MOOMMM

L

LL

LL

M

M

pq

pqpq

pq

kk kk

0 1 2 3 k-1 k k+1

Averíasegura

3k-1

kkkk

…

q0

0 1 2 p0 p1 p2 pk-1 (pk=0)

q1 q2 q3 qk-1 qk=1

U P C I.O.E. Diplomatura de Estadística U P C I.O.E. Diplomatura de Estadística Clasificación de Cadenas de Markov

ECUACIONES DE CHAPMAN KOLMOGOROV

Probabilidades condicionales en n transiciones:

0≥nijp (

para K,2,1,0=n ∀ i,j 11

=∑=

M

j

nijp(

para

K,2,1,0=n ∀ i.

FORMA MATRICIAL DE LAS EC. DE CHAPMAN KOLMOGOROV:

PPPPPPP (( ⋅==⋅= −1nnn L

nij

n piXjX (=

==Ρ

0

=

nMM

nM

nM

n

n

pp

pp

((

((

(PL

MOM

L

1

111

tresteve

Siguiente Tema


CLASES DE EQUIVALENCIA DE UNA CADENA DE MARKOV .

1

2

3

4

5

6

78

9.2

.1

1.

.3

.8.4

.4

.6

.6

.2

.6

.6

.6

.3 .6

.6

.4

1.

.

Accesibilidad: un estado j es accesible desde el i si ∃ n tal que 0>p nij(

( Notación: i → j )

Es posible encontrar un paso que conecte i con j sobre el diagrama de transiciones. Ejemplo: 2 → 7, pero 7 → 2 Dos estados i, j comunican entre sí si i → j & j → i ( Notación: i ↔ j ) • ↔ es relación de equivalencia: a) i ↔j ⇒ j ↔i b) i ↔ j , j ↔ k ⇒ i ↔ k (Se admite i ↔i )

Definición de clase:

C(i )={ j | i ↔ j }

j ∈ C(i) ⇒ C(i) = C(j)j ∉ C(i) ⇒ C(i) ∩ C(j) =Ø


PROBABILIDADES DE ABSORCIÓN

Presencia de clases absorbentes.Estructura de la matriz de probabilidades de transición.

Estados 1, 2 Contrato eventualEstado 3 DespedidoEstados 4,5 Contrato fijoEstado 6 Excedencia.

1

2

3

4

5

6

=

=QRR

PP

P

BA

B

A

0000

6.01.0002.008.02.02.02.0002.008.05.0

002/102/10003/13/13/10003/13/13/10000001

216543

0

=

QRPP Abs

BA

U P C I.O.E. Diplomatura de Estadística U P C I.O.E. Diplomatura de Estadística Estado Estacionario en C. de M. SEMANA 3

PROBABILIDADES A LARGO TÉRMINO

Para los estados i,j dentro de una clase C cerrada se verifica:

[ ] Cjpn

limn

Elim j

n

k

kijn

nij

nY ∈=

= ∑

=∞→∞→ ,(

(

π1

1

Interpretación: πj = fracción de los periodos en que se visita j. 1/ πj = µjj = tiempo medio de recurrencia del estado j

verifican:

CiiCi

i ∈≥=∑∈

,, 0 1 ππ.

Ejemplo:

1 2 3

1. 1.

1.

π1 =1/3 π2 =1/3 π3 =1/3

No depende de i

U P C I.O.E. Diplomatura de Estadística U P C I.O.E. Diplomatura de Estadística Estado Estacionario en C. de M. SEMANA 3

CADENAS ERGÓDICAS.

1

4

2

3Tras 8 transiciones, las probabilidades

condicionales p nij(

de los estados nodependen de la situación inicial.

Las filas de la matriz 8(P son idénticas

(a 3 dígitos de precisión).

Ejemplo de la tienda de cámaras:

==⋅=

1660264028502860166026402850286016602640285028601660264028502860

448

....

....

....

....

PPPP 8(((

Definición. Sólo hay una clase y ésta es aperiódica.

El estado inicial es irrelevante:

( ) ( ) ( ) [ ] [ ]1660264028502860081660264028502860166026402850286016602640285028601660264028502860

8 ....****P................

=

=⋅= TT pp


SESION DE PROBLEMAS

Una tienda de fotografía almacena un modelo particular de cámaras. Para reponer elstock puede efectuar pedidos semanales a su distribuidor. La demanda Dk de unidadesdel modelo en la semana k es una v.a. Poisson con E[Dk] = 1.

Sea Y0=3 el número inicial de cámaras, Y1 el número de cámaras al final de la 1ªsemana, Y2 al final de la segunda etc.

Los sábados por la noche se efectúa un pedido de S = 3 cámaras al distribuidor si latienda el nivel de existencias es <s (=1). El pedido es servido puntualmente el lunespor la mañana.

Si durante una semana no pueden satisfacerse las demandas de los clientes, éstas sepierden.


( ) { }( ) ( ) ( ) 08001111121313 21112

000 .

!=++−=−=−=<−=≥= −−

=∑ ee

kFDPDPp

k

k

Dtt t

( ) ( ) ( ) 184011122 11

0

12

001 .

!!=−=−=== −

=

−

=∑∑ e

ke

kFFDPp

k

k

k

k

DDt tt

( ) ( ) ( ) 368011011 10

0

11

002 .

!!=−=−=== −

=

−

=∑∑ e

ke

kFFDPp

k

k

k

k

DDt tt

( ) ( ) 3680100 10

003 .

!===== −

=∑ e

kFDPp

k

k

Dt t

( ) ( ) 632001110 .=−=≥=tDt FDPp

( ) ( ) 3680100 10

011 .

!===== −

=∑ e

kFDPp

k

k

Dt t , 0231312 === ppp

( ) ( ) 264011112 11

020 .

!=−=−=≥= −

=∑ e

kFDPp

k

k

Dt t

( ) ( ) ( ) 368011011 10

0

11

021 .

!!=−=−=== −

=

−

=∑∑ e

ke

kFFDPp

k

k

k

k

DDt tt

( ) ( ) 3680100 10

022 .

!===== −

=∑ e

kFDPp

k

k

Dt t

( ) { }( ) ( ) ( ) 08001111121313 21112

030 .

!=++−=−=−=<−=≥= −−

=∑ ee

kFDPDPp

k

k

Dtt t


( ) ( ) ( ) 184011122 11

0

12

031 .

!!=−=−=== −

=

−

=∑∑ e

ke

kFFDPp

k

k

k

k

DDt tt

( ) ( ) ( ) 368011011 10

0

11

032 .

!!=−=−=== −

=

−

=∑∑ e

ke

kFFDPp

k

k

k

k

DDt tt,

{ }( ) ( ) 3680100 10

033 .

!===== −

=∑ e

kFDPp

k

k

Dt t

=

=

3680368018400800036803680264000368063203680368018400800

33323130

23222120

13121110

03020100

.......

......

P

pppppppppppppppp

1

4

2

3

2. definición de cadena de markov propiedad …. i.o.e. diplomatura de estadística. cadenas de...

Documents