Perfect samplingdi processi di coda

UNIVERSITÀ DEGLI STUDI DI ROMA

“TOR VERGATA”Corso di laurea

in

Ingegneria dei Modelli e dei Sistemi

Studente:

Paolo Massaro

Relatore:

Prof. Benedetto Scoppola

Sommario

• I processi di coda M/M/1 e M/D/1

• Catene di Markov e algoritmi per il perfect

sampling

• Implementazione della modifica di Wilson

per simulare processi di coda

• Conclusioni e sviluppi futuri

Processi di coda

• Popolazione di utenti• Servizio

• Processo di arrivi nel sistema• Tempi di servizio• Numero di serventi• Lunghezza massima della linea

Processo di coda M/M/1

• Arrivi Poissoniani (con tempo medio di

interarrivo )

• Tempi di servizio esponenziali (con tempo medio di interuscita )

• Un solo servente

• Linea illimitata

at

st

Processo di coda M/M/1/k

• Arrivi Poissoniani (con tempo medio di

interarrivo )

• Tempi di servizio esponenziali (con tempo medio di interuscita )

• Un solo servente

• Linea limitata a k utenti

at

st

Processo di coda M/D/1

• Arrivi Poissoniani (con tempo medio di

interarrivo )

• Tempi di servizio deterministici (con

tempo di servizio ts)

• Un solo servente

• Linea illimitata

at

st

Processo di coda M/D/1/k

• Arrivi Poissoniani (con tempo medio di

interarrivo )

• Tempi di servizio deterministici (con

tempo di servizio ts)

• Un solo servente

• Linea limitata a k utenti

at

st

},...,,{ 21 ksssS

)0 :(mcd , niiPn

Data una qualsiasi distribuzione iniziale le catene irriducibili e aperiodiche tendono alla distribuzione stazionaria

Processo memory-less a tempo discreto con spazio degli stati e caratterizzato da una matrice di transizione P:

Irriducibilità: se è possibile passare da ogni stato a tutti gli altri in un tempo finito.Periodo di uno stato i:

La catena è aperiodica se il periodo di tutti gli stati è pari a 1.

Catena di Markov

)|( 1, injnji sXsXPP

,...),( 10 XX

Modellizzazione M/M/1/k

Valore atteso del tempo di transizione:

P

λP

μ P

,...,k,iμ P

,...,k,i λP

i,j

k,k

,

i,i-

i,i

altrimenti0

}21{

}110{

00

1

1

sa

s

tt

t11

1

1

sa

a

tt

t11

1

sa tt11

1

Modellizzazione M/M/1/k

Scontro con la parete in 0

Scontro con la parete in k

Simulazione delle catene di Markov

Ci sono due problemi:

• Si può sempre avere un errore ε rispetto alla distribuzione stazionaria

• Non è facile capire quante iterazioni servono per rendere ε piccolo come desiderato

Algoritmo di Propp-Wilson

• Produce dei risultati perfettamente in accordo alla distribuzione stazionaria

• Capisce automaticamente quando terminare.

L’algoritmo è di difficile implementazione.

Modifica di Wilson conread-once-randomness

La modifica di Wilson

• Funzione di aggiornamento:

• Coalescenza: per ogni stato del sistema si simula la catena, che si evolve tramite una funzione di aggiornamento e una successione di numeri casuali, che sono sempre gli stessi per tutte le k catene, fino a quando tutte le catene terminano nello stesso stato

SS ]1,0[ :

Coalescenza

Coalescenza della catena per la M/M/1/k

La modifica di Wilson

Coalescenza della coppia vincente

Coalescenza della coppia perdente

Perfect sampling al 50%

Perfect sampling al 50%

La modifica di Wilson

)(2)()()(

)()()()()(

cwlwl

wlwlp

tEttEtEtE

tEEtEttEtE

Stima del tempo di convergenza

Il valore atteso del tempo per avere il perfect sampling è:

: tempo per il perfect sampling: tempo per la coalescenza di una coppia

perdente: tempo per la coalescenza di una coppia

vincente: tempo generico per la coalescenzac

w

l

p

t

t

t

t

Stima del tempo di convergenza

)()()12(

0)2(

ncnP

nPn

Stima del tempo di coalescenza

Il valore atteso del tempo per avere k scontri è:

21k

21

1

212

211)()(

12

211)()(

0

0

n

n

nnPnE

nPscontroP se

Confronto tra stima e valori simulati

2

1

Ponendo

Fenomeno di cutoff

Il fenomeno di cutoff si verifica quando una catena di Markov converge improvvisamente alla misura stazionaria.Stima della finestra di cutoff:

mixreltt

Fenomeno di cutoff

Conclusioni

La comprensione dell’algoritmo di Wilson con read-once-randomness ha permesso di:• Simulare la distribuzione stazionaria della M/M/1/k e della M/D/1/k• Trovare una stima analitica del tempo per giungere al regime stazionario

Conclusioni

EsempioSe consideriamo la pista di un aeroporto come una M/D/1, con tempo di servizio 2 minuti, utilizzata al 98% il tempo medio stimato per ottenere un perfect sampling è di circa 6000 minuti ovvero 100 ore.

Sviluppi futuri

• Individuare una stima analitica per la M/D/1/k

• Trovare una stima più precisa quando ε tende a 0

• Approfondire il fenomeno di cutoff

Grazie per l’attenzione