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.
1
La proprietà di markovianeità implica che
Pr{x(t  dt)  xj | x(t)  xi }
è uguale alla probabilità condizionata con tutti gli
istanti precedenti.
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.
2
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:
p ij(t1 , t2 )  Pr{x(t2 )  xj | x(t1 )  xi }
t1  t2
Chiaramente
 p ij(t1 , t2 )  1
xjX
xi  X,
t1  t2
3
Definiamo la matrice delle probabilità di transizione:
P(t1, t2 )  [p ij(t1, t2 )]
P(t, t)  I
Definiamo inoltre il vettore delle probabilità
assolute all’istante t:
Π(t)  [Π j(t)]
Π j(t)  Pr{x(t)  xj }
4
L’equazione che regola l’evoluzione dinamica
della CMTC è:
Π(t  t)  Π(t)P(t, t  t)
t0
Segue dal fatto che per ogni j:
Πj (t  Δt)   pij (t, t  Δt)Π i(t)
xiX
t0
Problema: esistono infinite matrici delle probabilità
di transizione (una per ogni coppia t1 e t2 o
equivalentemente per ogni coppia t e t).
5
Definiamo ora la matrice delle frequenze (o tassi)
di transizione:
P(t, t  Δt)  I
Δt
Δt 0
Q(t)  lim
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
q ij(t)  lim
t 0
Pr{x(t  t)  xj | x(t)  xi }
t
6
Per quanto riguarda il generico elemento qii
lungo la diagonale, osserviamo invece che
Pr{x(t  t)  xi | x(t)  xi } 
n
n
j1
ji
j1
ji
 1   Pr{x(t  t)  xj | x(t)  xi }  1   q ij(t)t
n
1   q ij(t)t  1
q ii(t)  lim
t 0
j1
ji
t
n
q ii (t)    q ij(t)
j1
ji
7
La matrice Q(t) soddisfa quindi le seguenti
proprietà:
La somma
degli elementi
di ciascuna
riga è = 0.
q ij (t)  0
xi, xj  X i  j
q ii (t)  0
xi  X
 q ij (t)  0 xi  X
xjX
Q(t) ha sempre un autovalore
= 0 e tutti gli altri hanno
parte reale  0.
8
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.
9
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 (t0)
• (0) : distribuzione di probabilità assoluta
iniziale (vettore riga)
N.B. Nel seguito ci limiteremo a considerare
CMTC omogenee.
10
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
Q   0.01 0.01
 1 
 1
CMTC omogenea
11
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 = funzionante,
x2 = guasta
0.01
x1
x2
1
12
Equazione di evoluzione (di Chapman-Kolmogorov)
i (t  dt)  Pr{x(t  dt)  xi }
Pr{x(t  dt)  xi }  Pr{x(t  dt)  xi |x(t)  xi }  Pr{x(t)  xi } 
n
  Pr{x(t  dt)  xi | x(t)  xk }  Pr{x(t)  xk }
k 1
k i


n
n


Πi (t  dt)   1   q ij dt Πi (t)   q ki  dt  Πk (t)
k 1
 jj1i

k i


13
n
Πi (t  dt)  (1  q ii  dt)  Πi (t)   q ki  Πk (t)  dt 
k 1
k i
n

 Πi (t)    q ki  Πk (t)   dt
 k 1

n
Πi (t  dt) - Πi (t) 
 Πi (t)   q ki  Πk (t)
lim
dt
k 1
dt0
i
che in forma matriciale diventa:
 (t)  Π(t)  Q
Π
Equazione di
Chapman-Kolmogorov
(per CMTC omogenee)
14
Questa equazione è l’analogo di
Π(K  1)  Π(k)  P 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:
Π(t)  Π(0)  eQ t
15
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):
s  Π(s)  Π(0)  Π(s)  Q
Π(s)  [sI  Q]  Π(0)
Π(s)  Π(0)  [sI  Q] 1
(t) = L-1{ (s) }
16
Esempio:
0.01
x1
x2
Q   0.01 0.01
 1 
 1
1
Π(0)  1 0
Π(s)  Π(0)  [sI  Q] 1
[sI  Q]  s  0.01 - 0.01
s  1 
 - 1
det(sI  Q)  s(s  1.01)
1
0.01 
[sI  Q]-1 
 s  1
s  0.01
s(s  1.01)  1
0.01 
 s 1
Π(s)  

 s(s  1.01) s(s  1.01) 
17
100 1 1
1
Π(s)  
 

 101 s 101 s  1.01
100 1
Π(t)  

 e 1.01 t
 101 101
1 1 1
1 
 

101 s 101 s  1.01 
1
1

 e 1.01 t 
101 101

t0
18
Distribuzione stazionaria
Una distribuzione di probabilità assoluta s viene
detta stazionaria se e solo se sono verificate le
seguenti condizioni:
ΠsQ  0
Π  1  1 
iΠs,i  1
 s
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.
19
Distribuzione limite
Una CMTC ha una distribuzione limite se per t ,
la distribuzione di probabilità assoluta tende ad un
vettore costante, ossia
Πl  lim Π(t)
t
Chiaramente anche per le CMTC vale la
seguente proprietà
20
Proposizione: Se l è una distribuzione limite, allora
essa è anche stazionaria.
(la dimostrazione è del tutto analoga a quella vista
per le CMTD)
 (t)  Π(t)  Q
Π
 (t)  lim Π(t)  Q  Π  Q
lim Π
l
t 
t 
 (t)  0
lim Π
Πl (t)  Q  0
t 
21
Ergodicità
Una CMTC è ergodica se e solo se:
1) esiste lim Π(t)
t 
2) tale limite è unico e non dipende dalla
particolare distribuzione iniziale (0).
Esistono due diverse tecniche che permettono di
studiare l’ergodicità di una CMTC omogenea.
Criterio degli
autovalori
Criterio
grafico
22
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.
23
Esempio:
0.01
x1
1
x2
Q   0.01 0.01
 1 
 1
Criterio degli autovalori:
det(λ I  Q)  λ (λ  1.01)
λ 1  0 λ 2  1.01
La catena è
ergodica.
Criterio grafico:
Il grafo presenta un’unica componente
ergodica.
24
La distribuzione limite può essere agevolmente
calcolata tenendo conto che, essendo la catena
ergodica, questa coincide con la distribuzione
stazionaria.
Πl Q  0
 Π  1
 i l,i
100 1 
Πl  
 101 101 
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à).
25
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.
26
0
0
1
1
1
2
2
2
3
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, … ).
27
• 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.
28
La matrice delle frequenze di transizione ha la
seguente struttura:
 λ 0
 μ1
 0
Q
 0

 
λ0
λ 1 μ 1
μ2
0
0

0
λ1
λ 2 μ 2
μ3
0

0

0


λ2

λ 3 μ 3

μ4



Q ha chiaramente dimensione infinita se
il numero degli stati è infinito.
29
Calcolo della distribuzione stazionaria (nel caso
in cui il numero degli stati sia infinito):
ΠsQ  0
 Π  1
 i s,i
 λ 0Πs,0  μ 1Πs,1  0
 λ 0Πs,0  λ 1Πs,1  μ 1Πs,1  μ 2Πs,2  0
 
 λ Π λ Π μ Π  μ Π  0
i s,i
i s,i
i1 s,i1
 i-1 s,i-1
 
iΠs,i  1
30
 0  λ 0Πs,0  μ 1Πs,1
Il 1° membro di
 λ 0Πs,0  μ 1Πs,1  λ 1Πs,1  μ 2Πs,2
 
un’equazione è =
 λ Π μ Π  λ Π μ Π
al 2° di quella
i
1
s,
i
1
i
s,
i
i
s,
i
i

1
s,
i

1

precedente.


iΠs,i  1
λ0

Π

 s,1 μ Πs,0
1

 λ 0Πs,0  μ 1Πs,1  0
 Πs,2  λ 1 Πs,1
 λ 1Πs,1  μ 2Πs,2  0
μ2

 
 
 λ Π μ Π
i1 s,i1  0

 i s,i
λi
 Πs,i1  μ Πs,i
 
i1

iΠs,i  1
 
iΠs,i  1
31
se il processo è uniforme, definiamo
Πs,i1  ρΠs,i
 Π 1
i s,i
λ
ρ
μ
i0
Πs,0  ρ Πs,0  ρ2 Πs,0    1
Πs,0  iρi  1
se questa serie converge,
allora la catena è ergodica.
Ciò è vero purché sia
ρ
λ
1
μ
32
Se la catena è ergodica, allora la distrubuzione
limite coincide con quella stazionaria, che risulta
definita come segue:
Πs,0  1  ρ

i
i
Π

ρ

Π

ρ
 (1  ρ)
s,0
 s,i
i0
Questo significa che anche nel caso delle CMTCNM ergodiche :
ρ
μ
(1  ρ)
numero medio di
utenti a regime
33