5. Catene di Markov a tempo discreto
(CMTD)
Definizione: CATENA
• Le catene sono p.s. in cui lo stato è discreto :
X={x1,x2, … }.
• L’insieme X può essere sia finito sia infinito
numerabile.
• Il tempo può essere discreto o continuo.
1
Catene di Markov a tempo discreto
In una CMTD le transizioni di stato possono
verificarsi solo in istanti di tempo discreti.
Inoltre, k N,
Pr{ x(k+1)=xk+1 | x(k)=xk, x(k-1)= xk-1, … , x(0)=x0 }
= Pr{ x(k+1)=xk+1 | x(k)=xk }
[Proprietà di Markov]
2
Una CMTD è una tripla C=(X,P(k),(0)) dove:
• X : insieme degli stati,
• P(k) : matrice delle probabilità di transizione
dello stato all’istante k (kN)
P(k) = [ pij(k) ]
pij(k) = Pr{ x(k+1)=xj| x(k)=xi }
xi,xjX,  kN
• (0): distribuzione di probabilità assoluta
iniziale (vettore riga)
(0)=[ i(0), iN ]
dove i(0)=Pr{ x(0)=xi }, xi  X
3
La matrice P(k) soddisfa le seguenti condizioni k N :
• pij(k) [0,1], xi,xjX
• xj X pij(k) = 1 xiX
la somma degli
elementi lungo
una riga è = 1
Ogni matrice che soddisfa tali condizioni viene detta
matrice stocastica e gode della seguente proprietà:
• almeno un autovalore è = 1,
• tutti gli altri autovalori hanno modulo  1.
4
Se la matrice P(k) = cost. allora la CMTD
ad essa relativa viene detta omogenea.
Esempio: modello meteorologico.
x0 = pioggia, x1 = sole
a = prob. che domani piova se oggi piove
b = prob. che domani ci sia il sole se oggi
c’è il sole
a
P  1 a b 1 
b 

5
Ad una CMTD 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 pij).
Esempio: modello
meteorologico.
x0 = pioggia, x1 = sole
1-a
a
x0
x1
b
1-b
N.B. La somma dei pesi degli archi uscenti da
ciascun vertice deve essere pari a 1.
6
Equazioni di evoluzione
Sia
(k) = [ i(k), iN ]
dove i(k) = Pr{ x(k)=xi }, xi  X,
ossia (k) indica il vettore riga delle probabilità
assolute all’istante k.
Per ogni k > 0 vale la seguente relazione:
xj
(k) = (k-1) P(k-1)
Segue dal fatto che per ogni j:
Equazione di
ChapmanKolmogorov
j(k)= xi X Pij(k-1) i(k-1)
(k) = (0) P(0) P(1) … P(k-1)
7
Nel caso in cui la CMTD è omogenea:
(1) = (0) P
(2) = (1) P = (0) P 2
:
(k) = (k-1) P = (0) P k
Equazione di
ChapmanKolmogorov
per CMTD
omogenea
8
Esempio: si consideri un robot sempre alimentato
che prende i pezzi e li mette in un deposito di
capacità infinita.
I = inattivo,
X={I,T,G}
T = in trasferimento,
G = guasto.
1-p
1-r- q
p
I
r
p: p. che inizi a
lavorare,
T
q
s
G
1-s
r: p. che concluda
la lavoraz.
9
p
0 
1  p
P r
1r q
q 
 s
0
1  s

(0) = [1 0 0]
(1) = (0) P = [1-p p 0]
(2) = (1) P = [(1-p)2 + rp p(1-p) + p(1-r-q) pq]
In tal modo posso studiare il transitorio
della CMTD.
10
Ricordiamo ora le seguenti definizioni:
T
T
E
3 componenti
fortemente
connesse
T: componente transitoria o transiente
E: componente ergodica o assorbente
11
N.B.
Dato un grafo orientato, un sottoinsieme di nodi costituisce una
componente fortemente connessa se e
solo se ogni nodo è raggiungibile da un
qualunque altro nodo seguendo un
cammino orientato.
12
Definizione: probabilità di transizione ad n passi
pij(k,k+ n) = Pr{ x(k+n)=xj | x(k)=xi },
Se la catena è omogenea, chiaramente tale probabilità
non dipende da k, ma solo da n.
Notazione: pij(n) = pij(k,k+ n)
13
Classificazione degli stati di una CMTD
Uno stato xjX è detto raggiungibile o accessibile da
un altro stato xiX, se è possibile che una sequenza
di transizioni di stato porti la CMTD dallo stato xi
allo stato xj, ossia se  n: pij(n) > 0.
Due stati mutuamente raggiungibili sono detti
comunicanti.
Se ogni stato in X è comunicante con ciascuno degli
altri stati, la CMTD è detta irriducibile.
In caso contrario è detta riducibile.
14
Tali proprietà sono facilmente verificabili a partire
dal grafo associato alla CMTD:
• uno stato è raggiungibile da un altro in n passi se
esiste almeno un cammino orientato dal
primo al secondo di lunghezza n;
• Due stati comunicanti appartengono alla stessa
componente fortemente connessa;
• la CMTD è irriducibile se il grafo ad essa associato
è fortemente connesso.
15
Per ogni stato xi X la probabilità di ritorno in n
passi, ossia la probabilità che il primo ritorno nello
stato xi lasciato all’istante k avvenga all’istante
k+ n, è definita come
i(n) = Pr{ x(k+1)  xi, … , x(k+n-1)  xi, x(k+n) = xi |
x(k) = xi }
La probabilità di ritorno allo stato xi è

ρi   ρi (n)
n 1
16
Uno stato xi X è detto:
• transiente, se i < 1;
• ricorrente, se i = 1 (il ritorno a xi è certo);
• ricorrente con periodo d se esiste un d > 1
massimo comune divisore dell’insieme
{ n>0 | pii(n) > 0 };
• ricorrente aperiodico, se d=1 è il massimo
comune divisore dell’insieme { n>0 | pii(n) > 0 };
17
Dall’osservazione del grafo, possiamo invece dedurre
quanto segue.
In una CMTD uno stato è:
• transiente se e solo se appartiene ad una
componente transiente;
• ricorrente se e solo se appartiene ad una
componente ergodica.
18
Esempi: Date le seguenti CMTD, vogliamo capire
se lo stato ricorrente x1 è periodico
1)
x1
x2
1
1
2)
{ n>0 | p11(n) > 0 } = {3, 6, 9, … }
1
MCD=3 --> x1 è periodico di
periodo 3
x3
x1
0.5
1
x2
1
1
x3
0.5
{ n>0 | p11(n) > 0 } = {3, 6, 9, … ,
4, 8, 12, … , 7, 11, … }
x4
MCD=1 --> x1 è aperiodico
19
3)
0.3
0.7
x3
1
x1
x2
1
1
x4
{ n>0 | p11(n) > 0 } = {3, 6, 9, … ,
2, 4, 8, … , 5, 7, ... }
MCD=1 --> x1 è aperiodico
4)
x3
1
x4
0.3
0.7
1
x1
x2
1
1
x5
{ n> 0 | p11(n) > 0 } =
{2, 4, 6, 8, … }
MCD=2 --> x1 è
periodico di periodo 2
{ n>0 | p44(n) > 0 } = {4, 6, 8, 10, … }
MCD=2 --> x4 è periodico di periodo 2
20
Interpretazione fisica:
Se uno stato ricorrente xi è periodico di periodo d,
allora tutte le sequenze che hanno origine da xi e
terminano in xi hanno lunghezza multipla del
periodo d. Inoltre, qualunque sequenza che abbia
origine in xi ma la cui lunghezza non è un multiplo
del periodo, certamente non termina in xi.
Se invece uno stato ricorrente xi è aperiodico, è
possibile che le sequenze che hanno origine in xi e
la cui lunghezza è pari ad multiplo intero di una
certa costante terminino ancora in xi. Tuttavia tali
sequenze non sono le sole che terminano in xi.
21
Osservazione:
La periodicità di uno stato dipende solo dalla
struttura del grafo non dal particolare valore
che dei pesi associati agli archi.
22
Periodicità di una componente ergodica
Sia P la matrice delle probabilità di transizione
relativa alla sola componente ergodica.
Sia  = { n | p(n)ii > 0  i }.
• Se D = MCD {  } > 1, la componente ergodica è
periodica di periodo D.
• Se D=1 la componente ergodica è aperiodica.
23
Es. n3
1   P3  P 5
P  0
 1 0 
1
x2
x1
1
1 0  P 4  P6
P2  0
1 

 = { n | p(n)ii > 0  i } = {2, 4, 6, … }
D=2
24
Proposizione:
Una componente ergodica è periodica se solo se
tutti i suoi stati sono periodici. Ciò significa che gli
stati di una componente ergodica possono essere
• o tutti periodici
• o tutti aperiodici
Si può inoltre dimostrare che nel caso in cui tutti
gli stati sono periodici, questi hanno lo stesso
periodo e tale periodo coincide con il periodo D
della componente ergodica.
25
1
Esempio
x1
0.4
x2
0.6
1
x4
1
x3
Tutti gli stati sono periodici di periodo 2
per cui la componente ergodica è anch’essa
periodica di periodo 2.
26
Come caso particolare di quanto sopra:
Se una CMTD è irriducibile allora
• o tutti gli stati sono aperiodici,
• o tutti gli stati sono periodici con lo stesso
periodo.
Se in una CMTD lo spazio X è finito, allora
almeno uno degli stati è ricorrente (il ritorno ad
esso è certo).
27
Esempio
0.3
0.6
0.4
x0
0.7
0.1
0.5
1
x1
0.1
x5
x2
0.1
0.1
x3
1
0.1
x4
1
La CMTD è riducibile: non tutti gli stati sono
comunicanti ossia mutuamente raggiungibili.
28
• Vi sono 4 componenti fortemente connesse:
3 egodiche ({x0, x1}, {x2, x3}, {x4}) e
una transiente ({x5}).
• Tutti gli stati sono ricorrenti tranne x5 che è
transiente.
• Gli stati x0, x1 e x4 sono aperiodici.
• Gli stati x2 e x3 sono periodici di periodo d=2.
29
Consideriamo ora CMTD omogenee.
Distribuzione stazionaria
Una distribuzione di probabilità assoluta s viene
detta stazionaria se e solo se sono verificate le
seguenti condizioni:
Πs ΠsP
Π  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.
30
Osservazione:
Non e’ detto che una CMTD ammetta
distribuzione stazionaria.
Non e’ detto che se esiste una certa
distruzione stazionaria questa sia unica.
31
Distribuzione limite
Una CMTD ha una distribuzione limite se per
k , la distribuzione di probabilità assoluta
tende ad un vettore costante, ossia
Πl  lim Π(k)
k 
Proposizione: Se l è una distribuzione limite, allora
essa è anche stazionaria.
Dim.
(k) = (k-1) P
lim Π(k  1)  lim Π(k)P
k 
k 
Πl  ΠlP
32
Ergodicità
Una CMTD è ergodica se e solo se:
1) esiste lim Π(k)
k 
2) tale limite è unico e non dipende dalla
particolare distribuzione iniziale (0).
Se tali condizioni sono verificate, è sufficiente
studiare una qualunque realizzazione per capire il
comportamento della catena a regime.
33
Osservazione:
Se una CMTD è ergodica, il calcolo della
distribuzione limite si riduce al calcolo di una
componente stazionaria (ossia alla risoluzione di
un sistema lineare di equazioni di primo grado).
34
Esempio n1
x1
0.1
1
0.9
P  0.9 0.1
1 
 0
3

0.9
P 
 0
3
0.9k
Pk  
 0
2

0.9
P 
 0
2
x2
0.9  0.1  0.1

1
0.92  0.1  0.9  0.1  0.1

1
k 1
0.1   0.9i 

i 0

1
k

0.9
P 
 0
k
1  0.9k 
1 
35
Sia
Π(0)  Π0,1
Π0,2 

Π(k)  Π(0) Pk  0.9k  Π0,1 Π0,1  Π0,2  0.9k  Π0,1

lim Π(k)  0 Π0,1  Π0,2   0 1
k 
La CMTD è pertanto ergodica.
N.B. Se avessimo saputo a priori che il sistema è
ergodico, avremmo potuto calcolare la
distribuzione limite tenendo conto che in tal caso
questa coincide con la distribuzione stazionaria
(risolvendo quindi un semplice sistema lineare).
36
Osservazione:
Il risultato ottenuto era del tutto prevedibile in
base alla struttura del grafo.
Se infatti lo stato iniziale è x1 (stato transiente), si
potrà per un certo tempo rimanere in tale stato, ma
prima o poi si effettuerà la transizione che porta
ad x2. Una volta arrivati ad x2 (stato assorbente), lo
stato non può più cambiare.
Se lo stato iniziale è x2 lo stato x1 non verrà invece
mai raggiunto.
37
Esempio n2
Pk  P
0.5
x1
0 0.5 0.5
P  0 1
0 
1 
0 0
0.5
x2
1
x3
1
k  0
Π(k)  Π(0) Pk  0 0.5  Π0,1  Π0,2
0.5  Π0,1  Π0,3 
se Π(0)  1 0 0

(k)  Πl  0 0.5 0.5
se Π(0)  0 1 0

(k)  Πl  0 1 0
Tale CMTD è quindi non ergodica.
38
Osservazioni:
• Anche in questo caso il risultato ottenuto era
del tutto prevedibile in base alla struttura
del grafo.
• È facile verificare che esistono infinite
distribuzioni stazionarie
Πs  0 α 1  α α  [0,1]
39
Esempio n3
1
x2
x1
1
P  0
 1 0
1
P2k 1  P
P2k  P2
1 0
P2  0
1 

Π(0)  Π0,1
Π0,2 
Π0,2 Π0,1  k dispari
Π(k)  Π(0) P  
Π0,1 Π0,2  k pari
k
Quindi, in generale non esiste lim Π(k)
k 
a meno che non sia Π0,1  Π0,2  0.5
La CMTD non è ergodica.
40
N.B. In questo caso esiste una sola distribuzione
stazionaria
Πs  0.5 0.5
Possono pertanto presentarsi tre diverse situazioni:
• la CMTD è ergodica
• la CMTD non è ergodica in quanto la distribuzione
limite esiste ma dipende dalla particolare
distribuzione iniziale
• la CMTD non è ergodica in quanto la distribuzione
limite non esiste (se non per qualche
particolare distribuzione iniziale)
41
Esistono due diverse tecniche che permettono di
studiare l’ergodicità di una CMTD omogenea.
Criterio degli autovalori
Teorema: Una CMTD omogenea finita è ergodica se
e solo se gli autovalori della matrice P hanno tutti
modulo < 1, tranne uno che ha chiaramente modulo
unitario (essendo P una matrice stocastica).
Es. n1
P  0.9 0.1
1 
 0
λ 1  0.9
λ  1
 2
ergodica
42
Es. n2
0 0.5 0.5
P  0 1
0 
1 
0 0
λ 1  0
λ  λ  1
 2
3
non ergodica
Es. n3
1
P  0
 1 0
λ 1  1
λ  1
 2
non ergodica
43
Criterio grafico
Teorema: Condizione necessaria affinché una
CMTD omogenea finita sia ergodica è che il grafo
ad essa associato ammetta un’unica componente
ergodica.
Es. n1
x1
0.9
0.1
x2
1
La condizione necessaria è verificata essendo {x2}
l’unica componente ergodica.
Ciò tuttavia non basta per concludere che tale
CMTD è ergodica.
44
Es. n2
0.5
x1
0.5
Es. n3
x2
1
x3
1
x1
La condizione necessaria
non è verificata in quanto
vi sono due componenti
ergodiche ({x2} e {x3}).
Possiamo subito
concludere che tale
CMTD non è ergodica.
1
1
x2
La condizione necessaria è verificata essendo {x1, x2}
una componente ergodica.
Non posso però concludere che tale CMTD è ergodica.
45
Teorema: Condizione necessaria e sufficiente
affinchè una CMTD omogenea finita sia ergodica
è che il grafo ad essa associato ammetta
un’unica componente ergodica e questa sia
aperiodica.
Es. n1
x1
0.9
0.1
x2
1
La CMTD è ergodica in quanto {x2} è l’unica
componente ergodica e questa è chiaramente
aperiodica.
46
Es. n3
1
x2
x1
1
La CMTD non è ergodica essendo la
componente ergodica periodica di periodo 2.
47
Processi di nascita morte (CMTD-NM)
I processi di nascita morte a tempo discreto sono
delle CMTD 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.
48
b0
0
b1
1
d1
1 - b0
b2
2
d2
1 - b1- d1
3
d3
1 - b2- d2
1 - b3- d3
b : birth (nascita)
d : death (morte)
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, … ).
49
• In generale bi=bi(k) e di=di (k).
• Se bi e di sono costanti per ogni k allora il
processo è omogeneo (P=cost.).
• Se bi e di sono > 0 per ogni i, la CMTD-NM è
irriducibile (tutti gli stati sono
mutuamente raggiungibili)
• Se bi=b e di=d per ogni i allora il processo è
uniforme. In questo caso se b,d > 0, la
catena oltre ad essere irriducibile è
aperiodica (è costituita da un’unica
componente ergodica e tale componente
è aperiodica: esiste infatti sempre
almeno il cappio relativo allo stato 0).
50
La matrice delle probabilità di transizione ha la
seguente struttura:
b0
0
0

1  b0
 d1
1  b1  d1
b1
0

 0

d2
1  b2  d2
b2
P

0
d3
1  b3  d3
 0

0
0
d4


 




P ha chiaramente dimensione infinita se
il numero degli stati è infinito.
51
Calcolo della distribuzione stazionaria (nel caso
in cui il numero degli stati sia infinito):
Πs  Πs P
 Π  1
 i s,i
se il processo è
uniforme,
b0

Πs,1  d  Πs,0
1

Πs,2  b1  Πs,1
d2



b
Πs,i  i1  Πs,i1
di

 Πs,i  1
i
Πs,i  ρ Πs,i-1
 Π  1
 i s,i
b
ρ
d
Πs,1  ρ  Πs,0
Π  ρ2  Π
s,0
 s,2

i
Π

ρ
 Πs,0
 s,i
 Πs,i  1
i
52
Πs,0  ρ Πs,0  ρ2 Πs,0    1
Πs,0  iρi  1
Ciò è vero purché sia
se questa serie converge,
allora la catena è ergodica.
ρ
b
1
d
Questo segue dal fatto che solo in questo
caso il processo può “stabilizzarsi”.
N.B.: Se invece il numero di stati è finito il
processo uniforme è sempre ergodico a
prescindere dal valore di .
53
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
54
È interessante calcolare il numero medio di
utenti a regime:
μ   i  Πl,i   i  Πs,i
i 0
i 0
Posso usare la funzione generatrice di probabilità:
Π(z)   Πs,i  z i   [ρi  (1  ρ)]  z i 
i 0
i 0
i
ρ
1
(1  ρ)  z
 (1  ρ)      (1  ρ) 

ρ
zρ
i 0 z 
1
z
55
μ
dΠ(z)
(1  ρ)(z  ρ)  z(1  ρ)


2
dz z 1
(z  ρ)
z 1
(1  ρ)2  (1  ρ)
1 - ρ -1
ρ



2
(1  ρ) (1  ρ)
(1  ρ)
ρ
μ
(1  ρ)
numero medio di
utenti a regime
56