1
6. Catene di Markov a tempo continuo (CMTC)
Definizione
Una CMTC è un processo stocastico definito come segue:
• lo spazio di stato è discreto: X={x1,x2, … }.
L’ insieme X può essere sia finito sia infinito numerabile.
• L’ insieme dei tempi è continuo.
• È un processo markoviano.
2
La differenza essenziale tra una CMTD e una CMTC sta quindi nel fatto che in una CMTC una transizione di stato può avvenire in un qualunque istante di tempo t, mentre in una CMTD una transizione può verificarsi solo in istanti di tempo discreti.
La proprietà di markovianeità implica che
}xx(t)|xdt)Pr{x(t ij
è uguale alla probabilità condizionata con tutti gli istanti precedenti.
3
L’evoluzione dinamica di una CMTC è regolata dalle funzioni di transizione.
La generica funzione di transizione è definita come la probabilità di transizione da uno stato xi all’istante t1 ad uno stato xj all’istante t2:
21i1j221ij tt}x)x(t|x)Pr{x(t)t,(tp
Chiaramente
21i21ijXx
ttX,x1)t,(tpj
4
Definiamo la matrice delle probabilità di transizione:
It)P(t,)]t,(t[p)t,P(t 21ij21
Definiamo inoltre il vettore delle probabilità assolute all’istante t:
}xPr{x(t)(t)Π(t)][ΠΠ(t) jjj
5
Problema: esistono infinite matrici delle probabilità di transizione (una per ogni coppia t1 e t2 o equivalentemente per ogni coppia t e t).
L’equazione che regola l’evoluzione dinamica della CMTC è:
Segue dal fatto che per ogni j:
0t(t)Δt)Πt(t,pΔt)(tΠ iXx
ijji
0tt)tΠ(t)P(t,t)Π(t
6
Definiamo ora la matrice delle frequenze (o tassi) di transizione:
ΔtIΔt)tP(t,
limQ(t)0Δt
Per definizione, il generico elemento qij(t) della matrice Q(t) rappresenta la frequenza di transizione dallo stato xi all’istante t allo stato xj in un istante di tempo infinitamente vicino (t+ dt). Infatti, dalla relazione sopra segue che
t
}xx(t)|xt)Pr{x(tlim(t)q ij
0tij
7
n
ij1j
ij
n
ij1j
ij
ii
t(t)q1 }xx(t)|xt)Pr{x(t1
}xx(t)|xt)Pr{x(t
Per quanto riguarda il generico elemento qii lungo la diagonale, osserviamo invece che
t
t(t)q1
lim (t)q
n
ij1j
ij
0tii
1
n
ij1j
ijii (t)q (t) q
8
La matrice Q(t) soddisfa quindi le seguenti proprietà:
Xx0(t)qXx0(t)q
jiXx,x0(t)q
iXx
ij
iii
jiij
j
Q(t) ha sempre un autovalore = 0 e tutti gli altri hanno parte reale 0.
La somma degli elementi di ciascuna riga è = 0.
9
Lo studio delle CMTC si semplifica notevolmente nel caso in cui il processo sia tempo-invariante.
In questo caso la CMTC viene detta omogenea e
P(t,t+t) P(t)
ossia la matrice delle probabilità di transizione dipende dalla sola differenza t, e
Q(t) Q
ossia la matrice delle frequenze di transizione è costante.
10
Una CMTC viene pertanto definita come una tripla C=(X,Q(t),(0)) dove:
• X : insieme degli stati,
• Q(t) : matrice delle frequenze di transizione all’istante t (t0)
• (0) : distribuzione di probabilità assoluta iniziale (vettore riga)
N.B. Nel seguito ci limiteremo a considerare CMTC omogenee.
11
Esempio: Una macchina può trovarsi in due stati: funzionante o guasta. La frequenza con cui la macchina si guasta è pari a 0.01 giorni-1. La frequenza con cui viene riparata è invece pari a 1 giorni-1.
X={x1,x2} x1 = funzionante, x2 = guasta
11
0.010.01Q CMTC omogenea
12
Ad una CMTC omogenea è possibile associare una rappresentazione grafica data da un grafo orientato e pesato G=(V,A) dove:
• V = X (ad ogni stato corrisponde un vertice)
• A X X insieme degli archi dove:
• il peso del generico arco a = (xi,xj) è pari a qij;
• non esistono archi da xi ad xi (cappi)
Esempio precedente:
x1 x2
0.01
1
x1 = funzionante, x2 = guasta
13
Equazione di evoluzione (di Chapman-Kolmogorov)
n
ik1k
kki
iiii
}xPr{x(t) }xx(t)|xdt)Pr{x(t
}xPr{x(t)}xx(t)|xdt)Pr{x(t}xdt)Pr{x(t
}xdt)Pr{x(tdt)(t ii
n
ik1k
kkii
n
ij1j
iji (t)Πdt q(t)Πdtq1dt)(tΠ
14
dt(t)Π q(t)Π
dt(t)Π q(t)Πdt)q(1dt)(tΠ
n
1kkkii
n
ik1k
kkiiiii
i(t)Π q(t)Πdt
(t)Π-dt)(tΠlim
n
1kkkii
ii
0dt
che in forma matriciale diventa:
Q Π(t)(t)Π Equazione diChapman-Kolmogorov (per CMTC omogenee)
15
Questa equazione è l’analogo di
P Π(k)1)Π(K per le CMTD.
Osservazione: l’equazione di Chapman-Kolmogorov non è sempre di agevole risoluzione (in particolare per sistemi di ordine elevato) e questo rende difficile lo studio del transitorio.
Soluzione analitica: tQeΠ(0)Π(t)
16
1Q][sIΠ(0)Π(s)
Π(0)Q][sIΠ(s)
QΠ(s)Π(0)Π(s)s
Un approccio utile per la risoluzione dell’eq.ne di C.K. può essere quello di ricorrere alle trasformate di Laplace.
Date le condizioni iniziali (0) e indicata con (s) la trasformata di Laplace di (t):
(t) = L-1{ (s) }
17
Esempio:
x1 x2
0.01
1
11
0.010.01Q
1.01)s(s0.01
1.01)s(s1s
Π(s)
0.01s10.011s
1.01)s(s1
Q][sI
1.01)s(sQ)det(sI1s1-
0.01-0.01sQ][sI
Q][sIΠ(0)Π(s)01Π(0)
1-
1
18
1.01s1
1011
s1
1011
1.01s1
1011
s1
101100
Π(s)
0te1011
1011
e1011
101100
Π(t) t1.01t1.01
19
Distribuzione stazionaria
Una distribuzione di probabilità assoluta s viene detta stazionaria se e solo se sono verificate le seguenti condizioni:
i is,s
s
1Π11Π0QΠ
Se s è una distribuzione stazionaria, ciò significa che se tale distribuzione viene raggiunta in un dato istante, allora questa rimarrà inalterata in tutti gli istanti successivi.
20
Distribuzione limite
Una CMTC ha una distribuzione limite se per t , la distribuzione di probabilità assoluta tende ad un vettore costante, ossia
Π(t)limΠt
l
Chiaramente anche per le CMTC vale la seguente proprietà
21
Proposizione: Se l è una distribuzione limite, allora essa è anche stazionaria.
(la dimostrazione è del tutto analoga a quella vista per le CMTD)
Q Π(t)(t)Π
0(t)Πlim
Q ΠQ Π(t)lim(t)Πlim
t
ltt
0Q (t)Πl
22
Ergodicità
Una CMTC è ergodica se e solo se:
1) esiste
2) tale limite è unico e non dipende dalla particolare distribuzione iniziale (0).
Π(t)limt
Esistono due diverse tecniche che permettono di studiare l’ergodicità di una CMTC omogenea.
Criterio degli autovalori
Criterio grafico
23
Criterio degli autovalori
Teorema: Una CMTC omogenea è ergodica se e solo se gli autovalori della matrice Q hanno tutti parte reale < 0, tranne uno che chiaramente è = 0.
Criterio grafico
Teorema: Una CMTC omogenea è ergodica se e solo se il grafo ad essa associato ammette un’unica componente ergodica.
24
Esempio:
x1 x2
0.01
1
11
0.010.01Q
1.0101.01)(Q)Idet(
21
λλλλλ La catena è
ergodica.
Criterio degli autovalori:
Criterio grafico:
Il grafo presenta un’unica componente ergodica.
25
La distribuzione limite può essere agevolmente calcolata tenendo conto che, essendo la catena ergodica, questa coincide con la distribuzione stazionaria.
i il,
l
1Π0QΠ
1011
101100
Πl
N.B. Non è stato detto nulla a proposito della classificazione degli stati in quanto è possibile ripetere esattamente le stesse definizioni viste nel caso di CMTD (tranne naturalmente che per le definizioni relative alla periodicità).
26
Processi di nascita morte (CMTC-NM)
I processi di nascita morte a tempo continuo sono delle CMTC che godono delle seguenti caratteristiche:
• gli stati possono solo assumere valori interi:
X = {0, 1, 2, 3, … }
• sono ammesse solo le transizioni che consentono di passare da uno stato ad uno adiacente.
27
0 1 2 3
0 1 2
1 2 3
i : tasso di nascita dallo stato i
i : tasso di morte dallo stato i
Anche nel caso delle CMTC-NM lo spazio degli stati rappresenta la popolazione del sistema modellato (ad es. i clienti in una coda, i veicoli in un sistema di trasporto, i messaggi in un sistema di comunicazione, … ).
28
• In generale i = i (t) e i = i (t).
Se i e i sono costanti al variare di t allora il processo è omogeneo (Q=cost.).
• Se i = e i= per ogni i allora il processo è anche uniforme. Se i e i sono > 0 per ogni i, la CMTC-NM è irriducibile in quanto tutti gli stati sono mutuamente raggiungibili.
29
4
333
2222
1111
00
0000
0000
Q
μμλμ
λμλμλμλμ
λλ
La matrice delle frequenze di transizione ha la seguente struttura:
Q ha chiaramente dimensione infinita se il numero degli stati è infinito.
30
i is,
s
1Π0QΠ
Calcolo della distribuzione stazionaria (nel caso in cui il numero degli stati sia infinito):
i is,
1is,1iis,iis,i1-is,1-i
s,22s,11s,11s,00
s,11s,00
1Π
0ΠΠΠΠ
0ΠΠΠΠ0ΠΠ
μμλλ
μμλλμλ
31
i is,
1is,1iis,iis,i1-is,1-i
s,22s,11s,11s,00
s,11s,00
1Π
ΠΠΠΠ
ΠΠΠΠΠΠ0
μλμλ
μλμλμλ
Il 1° membro di un’equazione è = al 2° di quella precedente.
i is,
1is,1iis,i
s,22s,11
s,11s,00
1Π
0ΠΠ
0ΠΠ0ΠΠ
μλ
μλμλ
i is,
is,1i
i1is,
s,12
1s,2
s,01
0s,1
1Π
ΠΠ
ΠΠ
ΠΠ
μλ
μλμ
λ
32
se il processo è uniforme, definiamo μ
λρ
i is,
is,1is,
1Π0iρΠΠ
1 s,02
s,0s,0 ΠρΠρΠ
ii
s,0 1ρΠ se questa serie converge, allora la catena è ergodica.
Ciò è vero purché sia
1ρ μλ
33
Se la catena è ergodica, allora la distrubuzione limite coincide con quella stazionaria, che risulta definita come segue:
0iρ)ρΠρΠρΠ
is,0
iis,
s,0
1(
1
ρ)(1ρ
μ
numero medio di utenti a regime
Questo significa che anche nel caso delle CMTC-NM ergodiche :