Una catena di Markov è un processo stocastico a valori discreti caratterizzato dalla proprietà di assenza di memoria, detta anche proprietà di Markov:
Gli stati futuri del processo dipendono solo dallo stato presente e non dagli stati passati.
Detta così sembra una restrizione tecnica; in realtà è ciò che rende il problema risolubile. Nel capitolo 2 abbiamo visto che descrivere completamente un processo stocastico richiederebbe le funzioni di probabilità congiunte di ogni ordine. La proprietà di Markov taglia quella catena: sapere dove si è adesso rende irrilevante tutta la storia precedente, quindi bastano le probabilità di transizione fra coppie di stati.
In base all'ipotesi di evoluzione temporale si distinguono due famiglie:
| Sigla | Nome | Istanti di osservazione |
|---|---|---|
| DTMC | catena di Markov tempo discreta | un insieme numerabile di istanti n = 0, 1, 2, … |
| CTMC | catena di Markov tempo continua | qualunque istante t reale |
Il corso userà quasi esclusivamente le CTMC, perché un sistema a coda cambia stato in istanti qualsiasi; la DTMC serve come passaggio didattico intermedio, e ricomparirà una volta sola ma in modo decisivo nel capitolo 7 con la «catena di Markov nascosta» del sistema M/G/1.
Per ogni coppia di stati i e j si definisce una probabilità di transizione di stato. Nel caso tempo discreto la si riferisce a un generico istante n; nel caso tempo continuo a due generici istanti s e t:
DTMC: pᵢ⫺(n) = Prob{ X(n+1) = j | X(n) = i }
CTMC: pᵢ⫺(s,t) = Prob{ X(t) = j | X(s) = i } s < tUna catena di Markov si dice tempo omogenea se le probabilità di transizione di stato non dipendono da un istante specifico:
DTMC: pᵢ⫺(n) = pᵢ⫺ ∀n
CTMC: pᵢ⫺(s,t) = pᵢ⫺(t − s) dipende solo dalla distanza fra i due istantiDa qui in avanti tutte le catene del corso saranno tempo omogenee. È l'analogo, per le transizioni, di ciò che la stazionarietà è per le probabilità di stato: la regola del gioco non cambia mentre si gioca.
La conoscenza delle probabilità di transizione permette di caratterizzare il comportamento statistico della catena e di ricavarne le probabilità di stato. Nel caso di una DTMC tempo omogenea le si raccoglie nella matrice delle probabilità di transizione:
┌ ┐
│ p₀₀ p₀₁ p₀₂ … │
P = │ p₁₀ p₁₁ p₁₂ … │
│ p₂₀ p₂₁ p₂₂ … │
│ ⋮ ⋮ ⋮ │
└ ┘
∑⫺ pᵢ⫺ = 1 per ogni riga i → P è una matrice stocasticaLa matrice è quadrata (o di dimensione infinita, se gli stati sono infiniti) e stocastica: ogni riga somma a uno, perché da uno stato si deve pur andare da qualche parte, fosse anche restarci.
Alla matrice corrisponde una rappresentazione grafica, il diagramma degli stati: l'insieme degli stati in cui la catena può trovarsi e le possibili transizioni fra di essi.
Si chiama probabilità di stato la probabilità che il sistema si trovi nello stato j all'istante n:
π⫺(n) = Prob{ X(n) = j }Una DTMC si dice stazionaria se esiste il limite di πj(n) per n → ∞, e si dice ergodica se quel limite non dipende dallo stato iniziale. Per una DTMC tempo omogenea l'evoluzione è governata da un prodotto matriciale, e all'equilibrio la distribuzione diventa un punto fisso:
evoluzione: π(n+1) = π(n) P
a regime: π = π P cioè π⫺ = ∑ᵢ πᵢ pᵢ⫺Quest'ultimo è un sistema lineare omogeneo di N equazioni in N incognite. Un sistema omogeneo ammette sempre la soluzione banale nulla, e le sue equazioni non sono linearmente indipendenti: per trovare la soluzione unica occorre un'altra equazione indipendente dalle altre, quella di normalizzazione:
∑⫺ π⫺ = 1Questo è il passaggio che negli esercizi si dimentica più spesso. Le equazioni di equilibrio sono sempre una in meno del necessario: una qualunque di esse è combinazione lineare delle altre. La condizione di normalizzazione non è un dettaglio formale, è l'equazione che chiude il sistema.
Le stesse equazioni si possono scrivere in una forma molto più intuitiva. Si definisce flusso dallo stato j allo stato i il prodotto Fji = πj pji, e vale il principio:
La somma dei flussi uscenti da uno stato è pari alla somma dei flussi entranti nello stesso stato.
È la stessa legge di conservazione incontrata nel capitolo 3 con «ciò che entra esce», applicata però a un singolo stato invece che all'intero sistema. Il vantaggio pratico è enorme: invece di manipolare una matrice, si scrivono direttamente le equazioni guardando le frecce che entrano e quelle che escono da ciascun cerchio del diagramma.
Nel caso tempo continuo si definiscono allo stesso modo le probabilità di essere nello stato j all'istante t, e valgono le stesse definizioni di stazionarietà (esiste il limite) ed ergodicità (il limite non dipende dallo stato iniziale).
Il procedimento con cui si arriva alle equazioni di equilibrio è però diverso: si approssima la CTMC con una DTMC definita su un insieme discreto di intervalli di durata Δt, e si passa al limite per Δt → 0. Il limite fa emergere le frequenze di transizione, che sostituiscono le probabilità:
qᵢ⫺ = lim (Δt → 0) pᵢ⫺(Δt) / Δt i ≠ j
qᵢᵢ = − ∑⫺≠ᵢ qᵢ⫺ (per riga la somma è nulla)Raccolte in una matrice Q, esse portano al sistema di equazioni da risolvere a regime, e al corrispondente bilanciamento dei flussi:
a regime: π Q = 0 con ∑⫺ π⫺ = 1
bilanciamento flussi: ∑⫺≠ᵢ π⫺ q⫺ᵢ = πᵢ ∑⫺≠ᵢ qᵢ⫺La differenza sostanziale rispetto al caso discreto è che qij non è una probabilità ma una frequenza, misurata in transizioni al secondo. Nel diagramma degli stati di una CTMC gli archi non portano più probabilità ma frequenze: nei sistemi a coda saranno λ per gli arrivi e μ per le partenze.
Nel diagramma di una CTMC non esistono autoanelli. Restare nello stato in cui si è non è una transizione: è semplicemente ciò che accade fra una transizione e la successiva. La riga i-esima di Q somma a zero, non a uno.
Si può dimostrare che il tempo di permanenza in uno stato j di una CTMC ha una distribuzione esponenziale negativa, con parametro pari alla somma delle frequenze di transizione uscenti da quello stato.
È una conseguenza inevitabile della proprietà di Markov, non un'ipotesi aggiuntiva: se il futuro non deve dipendere dal passato, allora nemmeno il tempo già trascorso nello stato corrente può portare informazione, e l'unica distribuzione continua senza memoria è l'esponenziale. Il cerchio con il capitolo 2 si chiude qui.
Un processo di nascita e morte è una CTMC tale che le transizioni possono avvenire solo tra stati adiacenti. Con questa restrizione la notazione si semplifica:
λkPk = μk+1Pk+1, e per ricorrenza la formula in fondo alla tavola.Se il processo è ergodico, la soluzione del sistema di equilibrio si può scrivere in forma chiusa: ogni probabilità di stato si ottiene da P0 moltiplicando i rapporti nascita/morte incontrati lungo il cammino, e P0 si ricava dalla normalizzazione. È il risultato più importante del capitolo: da qui in avanti, per studiare un sistema a coda Markoviano, basterà specificare λi e μi e applicare questa formula.
La domanda posta a lezione è: possiamo modellare un sistema a coda tramite un processo di nascita e morte? E quali ipotesi sono necessarie? La risposta è la parte più importante di tutto il capitolo, perché è il ponte fra la teoria astratta e i capitoli 5, 6 e 7.
Si sceglie come variabile di stato k il numero di utenti nel sistema a coda. Servono poi tre ipotesi.
| Ipotesi | Conseguenza |
|---|---|
| Arrivi di Poisson con parametro λ, indipendenti dallo stato del sistema | λ è costante: λk = λ per ogni k |
| Arrivo istantaneo singolo (niente arrivi contemporanei) | un incremento di k può avvenire solo verso lo stato k+1 |
| Tempi di servizio esponenziali con parametro μ; nello stato k ci sono mk servitori occupati | la composizione di mk processi di Poisson di parametro μ dà una frequenza di servizio complessiva μk = mkμ |
| Partenza istantanea singola | un decremento di k può avvenire solo verso lo stato k−1 |
Poiché arrivi e partenze sono entrambi processi senza memoria, lo stato futuro del sistema dipende solo dallo stato presente. Ne segue la conclusione: il sistema a coda è un processo di nascita e morte.
Si noti come la composizione di processi di Poisson del capitolo 3 rientri qui in un ruolo decisivo: mk servitori esponenziali che lavorano in parallelo si comportano, dal punto di vista del sistema, come un unico processo di partenze di frequenza mkμ. È questa proprietà a permettere di descrivere anche un sistema con molti servitori con una catena unidimensionale.
La lezione chiude verificando la coerenza del quadro. Il tempo di permanenza in uno stato k è il tempo che intercorre fra l'evento (arrivo o partenza) che ha portato il sistema in quello stato e l'evento che lo porterà nello stato futuro, k+1 o k−1. Il processo complessivo degli eventi è la composizione di due processi con tempi distribuiti esponenzialmente, quindi la frequenza inter-evento è la somma delle frequenze dei due processi:
tempo di permanenza nello stato k → esponenziale di parametro λ + mₖμChe è esattamente il risultato generale sulle CTMC della sezione 6, applicato al caso particolare del sistema a coda. Le due strade portano allo stesso punto.
Quando un utente che richiede un servizio non può essere soddisfatto immediatamente si ha una condizione di congestione. Le due forme sono l'attesa in coda che si liberi un servitore, oppure il rifiuto di accesso al servizio (blocco).
Si definiscono allora due probabilità distinte, e la distinzione è più sottile di quanto sembri:
| Grandezza | Definizione |
|---|---|
| Time congestion | probabilità che il sistema si trovi in uno stato in cui non può soddisfare nuove richieste di servizio |
| Call congestion | probabilità di time congestion condizionata al fatto che un cliente si presenti al sistema |
Che le due possano differire radicalmente lo mostra il controesempio proposto a lezione. Si consideri un sistema con m servitori, coda nulla e popolazione finita di p = m utenti totali. In questo caso:
Nessun utente sperimenta mai il blocco, benché il sistema passi una frazione non trascurabile del tempo in stato di blocco. Un osservatore esterno e un utente vedono due sistemi diversi.
Con arrivi di Poisson, però, le due probabilità coincidono. La dimostrazione mostrata a lezione è tutta contenuta nella definizione di probabilità condizionata. Il punto di partenza è che un processo degli arrivi di Poisson non dipende dallo stato del sistema a coda:
Pr{ utente in arrivo | sistema congestionato } = Pr{ utente in arrivo }Applicando la relazione Pr{A|B} Pr{B} = Pr{B|A} Pr{A} = Pr{A,B}:
Pr{ congestionato | arrivo } ⋅ Pr{ arrivo }
= Pr{ arrivo | congestionato } ⋅ Pr{ congestionato }
= Pr{ arrivo } ⋅ Pr{ congestionato }
⇒ call congestion = Pr{ congestionato | arrivo }
= Pr{ congestionato } = time congestionIl nome del risultato è PASTA, acronimo di Poisson Arrivals See Time Averages: gli arrivi di Poisson vedono le medie temporali. La conseguenza operativa è che, con arrivi di Poisson, è sufficiente calcolare le probabilità di stato congestionato, senza doversi preoccupare di che cosa veda l'utente che arriva.
Tutte le formule di Erlang del capitolo 5 e 6 calcolano probabilità di stato, cioè time congestion. Il fatto che negli esercizi si possano usare direttamente come «probabilità che una chiamata venga bloccata» dipende interamente da PASTA. La domanda «perché la formula B di Erlang dà la probabilità di blocco vista dal cliente?» ha una sola risposta corretta: perché gli arrivi sono di Poisson.
Si consideri un processo di nascita e morte con frequenza di nascita costante λk = λ per ogni k e frequenza di morte nulla, μk = 0. Un processo siffatto non può essere stazionario, perché il suo stato evolve in un transitorio continuo verso un valore infinito: nessuno esce mai. Di conseguenza non si possono usare le formule di equilibrio, ma occorre usare le equazioni differenziali che descrivono la dinamica temporale della catena.
dP₀(t)/dt = −λ P₀(t)
dPₖ(t)/dt = λ Pₖ₋₁(t) − λ Pₖ(t) ∀k > 0
condizioni iniziali: P₀(0) = 1 Pₖ(0) = 0 ∀k > 0Il sistema si risolve facilmente per sostituzione, ottenendo:
P₀(t) = e⁻ᵏᵗ
Pₖ(t) = (λt)ᵏ e⁻ᵏᵗ / k! k > 0Pk(t) è la probabilità che si siano verificate k nascite nell'intervallo [0 : t]. Indicando con T tale intervallo, si riconosce Pk(T) = (λT)ke−λT/k!, cioè esattamente la formula di Poisson P(k,T) del capitolo 3.
L'esercizio chiude un cerchio concettuale: la formula di Poisson, che nel capitolo 3 era stata ricavata per passaggio al limite da una popolazione grande, si riottiene qui come soluzione di un processo di nascita e morte degenere. Due derivazioni completamente diverse dello stesso oggetto: è il segno che il modello è quello giusto.
Un singolo operatore riceve chiamate su due numeri: il 100 per chiamate ad alta priorità (tipo A) e il 200 per chiamate a bassa priorità (tipo B). Il centralino non può mettere in attesa, quindi:
I dati: λA = 3 ch/h = 0.05 ch/min, λB = 6 ch/h = 0.1 ch/min, &thetas;̄A = 0.5 min e &thetas;̄B = 1 min, da cui μA = 2 ch/min e μB = 1 ch/min. I traffici offerti valgono A0A = 0.025 E e A0B = 0.1 E.
Il sistema si descrive come una catena di Markov a tre stati: 0 (operatore inattivo), A (sta rispondendo a una chiamata di tipo A), B (sta rispondendo a una chiamata di tipo B). La particolarità è che lo stato A è raggiungibile dallo stato B, perché una chiamata A può interrompere una B in corso, ma non vale il viceversa.
Il bilanciamento dei flussi dà tre equazioni, di cui la terza è combinazione lineare delle prime due; si aggiunge quindi la normalizzazione e si ottiene la soluzione in forma chiusa:
P₀ = 0.891 Pᴬ = 0.024 Pᴮ = 0.085Poiché gli arrivi seguono un processo di Poisson, applicando la proprietà PASTA si ricavano direttamente le metriche prestazionali:
| Metrica | Espressione | Valore |
|---|---|---|
| blocco delle chiamate A | πpA = PA = λA/(λA+μA) = A0A/(1+A0A) |
0.024 |
| blocco delle chiamate B | πpB = 1 − P0 = PA + PB |
0.11 |
| interruzione di una B accettata | πs = λA/(λA+μB) |
0.0476 |
| B non completata (bloccata oppure interrotta) | πi = πpB + (1−πpB)πs = πpB + P0πs |
0.15 |
Due osservazioni chiudono l'esercizio, ed entrambe meritano di essere memorizzate.
L'espressione di πpA corrisponde esattamente al valore della formula B di Erlang B(1, A0A), cioè alla probabilità di blocco di un sistema a singolo servitore senza spazio di attesa soggetto al solo traffico A0A. Il motivo è che le chiamate di tipo A non sono soggette in nessun modo al comportamento di quelle di tipo B: esse vedono il sistema come se fosse dedicato esclusivamente a loro. È lo stesso principio che nel capitolo 7 renderà la classe più prioritaria di un sistema M/G/1/PRIO preemptive del tutto immune dalle altre classi.
La probabilità πs si ricava invece integrando: una chiamata B può essere completata se e solo se nessuna chiamata A arriva mentre essa è in corso. Per la formula di Poisson, la probabilità di zero arrivi di tipo A in un tempo &thetas;B vale e−λA&thetas;B; mediando su tutti i possibili valori di &thetas;B pesati dalla densità esponenziale si ottiene λA/(λA+μB).
Un servizio di taxi presso un aeroporto ha un parcheggio limitato a N taxi in attesa di clienti, mentre l'area in cui i clienti aspettano è così grande da potersi considerare illimitata. I clienti arrivano secondo un processo di Poisson di frequenza λc, e anche i taxi arrivano secondo un processo di Poisson di frequenza λt.
L'idea risolutiva è la parte istruttiva dell'esercizio. Definire come variabile di stato semplicemente «il numero di clienti nel sistema» non basterebbe, perché non permetterebbe di rappresentare il caso in cui non ci sono clienti e i taxi sono in coda nel parcheggio. Si estende quindi la definizione dello stato k ai valori negativi:
| Stato k | Significato |
|---|---|
k ∈ [1, ∞] | k clienti sono in coda perché non ci sono taxi disponibili |
k = 0 | nessun cliente in coda e nessun taxi disponibile |
k ∈ [−N, −1] | nt = −k taxi sono nel parcheggio in attesa di clienti |
Con questa definizione k aumenta di uno a ogni arrivo di cliente e diminuisce di uno a ogni arrivo di taxi. Entrambi i processi sono senza memoria e le transizioni avvengono solo fra stati adiacenti: si applicano quindi le formule dei processi di nascita e morte, con λk = λc e μk = λt. L'unica accortezza è che lo stato con l'indice più piccolo è P−N e non P0, quindi l'indice va traslato di N unità:
Pₖ = P₋ᵤ (λᶜ / λᵗ)ᶜᶜᶜ P₋ᵤ = 1 − λᶜ/λᵗLa condizione di esistenza è λc < λt, altrimenti la serie geometrica nell'espressione di P−N non converge. Il significato è immediato: se i clienti arrivassero più in fretta dei taxi, sul lungo termine non ci sarebbero abbastanza taxi per servirli tutti e la coda dei clienti crescerebbe all'infinito. La condizione λc < λt assicura che la catena di Markov sia ergodica.
Due lezioni di metodo da portare via da questo esercizio. Primo: lo stato lo scegli tu, e la scelta giusta è quella che rende il sistema unidimensionale e a transizioni adiacenti. Secondo: la condizione di stabilità non è mai un dettaglio matematico, è sempre traducibile in una frase sul sistema fisico. Chi sa dire a parole che cosa significa una serie che non converge ha capito il modello.
Gli stati futuri del processo dipendono solo dallo stato presente e non dagli stati passati. Semplifica perché, senza di essa, la descrizione completa di un processo stocastico richiederebbe le funzioni di probabilità congiunte di ogni ordine n; con essa bastano le probabilità di transizione fra coppie di stati, e tutte le congiunte si fattorizzano.
Che le probabilità di transizione di stato non dipendono da un istante specifico. Per una DTMC, pij(n) = pij per ogni n; per una CTMC, pij(s,t) dipende solo dalla differenza t − s. È l'analogo, per le transizioni, di ciò che la stazionarietà è per le probabilità di stato.
π = πP non basta a determinare le probabilità di stato?Perché è un sistema lineare omogeneo di N equazioni in N incognite, le cui equazioni non sono linearmente indipendenti: una qualunque di esse è combinazione lineare delle altre, e la soluzione banale nulla è sempre ammessa. Serve un'equazione ulteriore e indipendente, la normalizzazione ∑jπj = 1.
La regola per cui, per ciascuno stato, la somma dei flussi uscenti è pari alla somma dei flussi entranti. Il flusso dallo stato j allo stato i è Fji = πjpji nel caso discreto e πjqji nel caso continuo. È una riscrittura delle equazioni di equilibrio che si legge direttamente sul diagramma degli stati, contando le frecce.
La probabilità pij di una DTMC è adimensionale e le righe della sua matrice sommano a 1. La frequenza qij = limΔt→0 pij(Δt)/Δt di una CTMC si misura in transizioni al secondo, e le righe della matrice Q sommano a zero, con qii = −∑j≠iqij. Nel diagramma di una CTMC non esistono autoanelli.
Esponenzialmente, con parametro pari alla somma delle frequenze di transizione uscenti da quello stato. Non è un'ipotesi aggiuntiva ma una conseguenza della proprietà di Markov: l'unica distribuzione continua senza memoria è l'esponenziale. In un sistema a coda nello stato k il parametro vale λ + mkμ.
È una CTMC in cui le transizioni possono avvenire solo fra stati adiacenti, con frequenza di nascita λi (da i a i+1) e di morte μi (da i a i−1). Se ergodico, le probabilità di stato si scrivono Pk = P0 ∏i=0k−1 (λi/μi+1), con P0 ricavato dalla normalizzazione.
Arrivi di Poisson con parametro λ indipendente dallo stato (quindi λ costante) e istantanei singoli (incremento solo verso k+1); tempi di servizio esponenziali con parametro μ, per cui con mk servitori occupati la frequenza complessiva è mkμ per composizione di processi di Poisson; partenze istantanee singole (decremento solo verso k−1). Essendo entrambi i processi senza memoria, lo stato futuro dipende solo dal presente.
La time congestion è la probabilità che il sistema si trovi in uno stato in cui non può soddisfare nuove richieste. La call congestion è la stessa probabilità condizionata al fatto che un cliente si presenti. Sono grandezze distinte: in un sistema con m servitori, coda nulla e popolazione p = m, la time congestion vale Pm mentre la call congestion vale 0, perché nello stato m tutti gli utenti sono già dentro e un arrivo è impossibile.
Poisson Arrivals See Time Averages: con arrivi di Poisson, call congestion = time congestion. Vale perché un processo degli arrivi di Poisson non dipende dallo stato del sistema, quindi Pr{arrivo | congestionato} = Pr{arrivo}; sostituendo nella relazione di Bayes si ottiene Pr{congestionato | arrivo} = Pr{congestionato}. È la ragione per cui le formule di Erlang, che calcolano probabilità di stato, si possono usare direttamente come probabilità di blocco viste dal cliente.
Perché con μk = 0 nessuno esce mai dal sistema: lo stato evolve in un transitorio continuo verso l'infinito e il processo non è stazionario. Occorre risolvere le equazioni differenziali della dinamica temporale, con condizioni iniziali P0(0) = 1 e Pk(0) = 0. La soluzione è Pk(t) = (λt)ke−λt/k!, cioè la formula di Poisson.
B(1, A0A)?Perché le chiamate di tipo A non sono influenzate in alcun modo dalle chiamate di tipo B: una A viene bloccata solo se l'operatore è già impegnato con un'altra A, e può sempre interrompere una B. Le chiamate A vedono quindi il sistema come se fosse un M/M/1/0 dedicato esclusivamente al loro traffico A0A, la cui probabilità di blocco è A0A/(1+A0A) = B(1, A0A).
Perché il solo «numero di clienti in coda» non distingue fra le due situazioni di sistema scarico: nessun cliente e nessun taxi, oppure nessun cliente e alcuni taxi in parcheggio. Estendendo k a [−N, ∞] si rappresenta con un unico numero sia la coda dei clienti (k > 0) sia la coda dei taxi (k < 0), mantenendo transizioni solo fra stati adiacenti e quindi la struttura di nascita e morte. La condizione di ergodicità è λc < λt.