UNIVERSITÀ DEGLI STUDI DI ROMA
“TOR VERGATA”
Corso di laurea
in
Ingegneria dei Modelli e dei Sistemi
Perfect sampling
di processi di coda
Studente:
Relatore:
Paolo Massaro
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
interarrivo
(con tempo medio di
ta )
• Tempi di servizio esponenziali
(con tempo medio di interuscita t s )
• Un solo servente
• Linea illimitata
Processo di coda M/M/1/k
• Arrivi Poissoniani
interarrivo
(con tempo medio di
ta )
• Tempi di servizio esponenziali
(con tempo medio di interuscita t s )
• Un solo servente
• Linea limitata a k utenti
Processo di coda M/D/1
• Arrivi Poissoniani
interarrivo
(con tempo medio di
ta )
• Tempi di servizio deterministici
ts
(con tempo di servizio ts)
• Un solo servente
• Linea illimitata
Processo di coda M/D/1/k
• Arrivi Poissoniani
interarrivo
(con tempo medio di
ta )
• Tempi di servizio deterministici
ts
(con tempo di servizio ts)
• Un solo servente
• Linea limitata a k utenti
Catena di Markov
Processo memory-less a tempo discreto ( X 0 , X 1 ,...)
con spazio degli stati S  {s1 , s2 ,..., sk } e
caratterizzato da una matrice di transizione P:
Pi , j  P( X n  s j | X n 1  si )
Irriducibilità: se è possibile passare da ogni stato a
tutti gli altri in un tempo finito.
Data
una
iniziale le catene
Periodo
diqualsiasi
uno statodistribuzione
i:
irriducibili e aperiodiche tendono
n alla distribuzione
stazionaria
i ,i
La catena è aperiodica se il periodo di tutti gli stati è
pari a 1.
mcd (n : P  0)
Modellizzazione
M/M/1/k
1
ta
1
ts
1 1

ta ts
1 1

ta ts
Valore atteso
del tempo

  1   di
 transizione:



Pi,i 1  λ
Pi,i-1  μ
P0 ,0  μ
1
i  {0 ,1,...,k  1}
1i 1{1,2,...,k}

ta ts
Pk,k  λ
Pi,j  0 altrimenti
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
L’algoritmo
è di
difficile
• Produce
dei risultati
perfettamente
in
implementazione.
accordo alla
distribuzione stazionaria
• Capisce automaticamente quando
terminare.
Modifica di Wilson con
read-once-randomness
La modifica di Wilson
• Funzione di aggiornamento:  : S  [0,1] 
• 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
S
Coalescenza della catena per
la M/M/1/k
Coalescenza
La modifica di Wilson
Coalescenza della
coppia perdente
Coalescenza della
coppia vincente
Perfect sampling al 50%
La modifica di Wilson
Perfect sampling al 50%
Stima del tempo di
convergenza
Il valore atteso del tempo per avere il perfect
sampling è:
E (t p )  E (tl  t w )  E (tl )  E ( ) E (t w ) 
 E (tl )  E (t w )  E (tl  t w )  2 E (tc )
tp
tl
tw
tc
: 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 coalescenza
Stima del tempo di
convergenza
Stima del tempo di
coalescenza
P ( 2n)  0
P(2n  1)   ( ) n c(n)
1  1  2
P ( scontro)  n0 P (n) 
 1 se   
2
1  1  2
1
E (n)  n0 nP (n) 

2 1  2 1  2
Il valore atteso del tempo per avere k scontri è:
k
1 2
Confronto tra stima e valori
simulati
Ponendo
1
 
2
Fenomeno di cutoff
Il fenomeno di cutoff si verifica quando
una catena di Markov converge
improvvisamente alla misura
stazionaria.
Stima della finestra di cutoff:
trel tmix
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
Esempio
Se 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