Catene di Markov
Ricerca operativa – Met. e mod. per le decisioni
(Informatica – Matematica)
Pierluigi Amodio
Dipartimento di Matematica
Università di Bari
Catene di Markov – p.1/19
definizione del problema
processo stocastico: successione di variabili aleatorie
che descrivono un processo empirico governato da
leggi probabilistiche
(xt )t , dove xt é una variabile aleatoria
processo markoviano: processo stocastico con
proprietà markoviana (assenza di memoria)
catena di Markov: processo markoviano con t
parametro discreto e xt che può assumere un numero
di valori finito (ciascun valore è detto stato ed il
processo si dice a numero di stati finito)
Catene di Markov – p.2/19
obiettivo
studiare come può evolvere questo sistema dinamico;
calcolare la probabilità che in un certo istante la v.a. sia
in un certo stato p(xt ) = i, per i = 1, . . . , s dove
S = {1, 2, . . . , s} è l’insieme degli stati;
Catene di Markov – p.3/19
esempio: passeggiata aleatoria
ci sono s città lungo una strada e ciascuna di esse è
collegata solo con la precedente e la seguente (tranne
la prima e l’ultima che sono collegate solo con la
successiva o la precedente);
una persona può spostarsi da una città alla precedente
con probabilità p o alla successiva con probabilità 1 − p;
se questa persona arriva nella prima o nell’ultima città
si ferma.
fissata la città di partenza, determinare la probabilità di
essere in una certa città dopo t istanti di tempo.
Catene di Markov – p.4/19
proprietà
p(b|a) probabilità condizionata: probabilità che si
verifichi l’evento b condizionata al verificarsi dell’evento
a; vale la seguente relazione
p(a, b) = p(b|a)p(a)
proprietà markoviana:
p(xk = ik |xk−1 = ik−1 , . . . , x0 = i0 ) = p(xk = ik |xk−1 =
ik−1 )
probabilità stazionarie:
p(xk = j|xk−1 = i) = p(x1 = j|x0 = i); in questo caso la
catena si dice omogenea nel tempo
Catene di Markov – p.5/19
matrice di transizione
la matrice P i cui elementi pij = p(x1 = j|x0 = i) è detta
matrice di transizione
questi valori, insieme al vettore Π0 = (p1 , . . . , ps ) delle
probabilità iniziali (pi = p(x0 = i)), è sufficiente a
descrivere l’intero sistema
Catene di Markov – p.6/19
principali risultati
probabilità di un evento congiunto:
p(x0 = i0 , i1 = i1 , . . . , xk = ik ) = pi0 pi0 ,i1 pi1 ,i2 . . . pik−1 ,ik
probabilità dopo k istanti di tempo: Πk = P k Π0
probabilità di transizione dopo k passi: P (k) = P k
equazione di Chapman-Kolmogorov:
P (m+n) = P (m) P (n)
P (n) = P (n−k) P (k)
Catene di Markov – p.7/19
esempio: mercato azionario
studiamo (positivo/negativo) l’andamento del mercato
azionario
supponiamo che se l’andamento attuale è positivo, nel
futuro sarà positivo nel 70% dei casi; se è negativo, lo
sarà nuovamente nel 50% dei casi
S = {x1 , x2 } dove x1 indica un andamento positivo e x2
un andamento negativo
!
0.7 0.3
P =
0.5 0.5
Catene di Markov – p.8/19
esempio: carta più alta
due giocatori estraggono una carta dal mazzo: vince un
euro chi ha la carta più alta
si parte con il giocatore 1 con un euro in mano; si
termina quando questo giocatore ha 0 o 5 euro
xt indica la somma in tasca al giocatore 1 dopo t partite
Π0 = (0, 1, 0, 0, 0, 0)
P è la matrice della passeggiata aleatoria con p = 1/2
variante: il giocatore 1 estrae da un mazzo che non
contiene carte basse (per aumentare la sua probabilità
di vittoria)
Catene di Markov – p.9/19
esempio: problema di scorte
un negozio di macchine fotografiche ha a disposizione
3 macchine fotografiche; al termine della settimana, se
le vende tutte, ne ordina altre 3; altrimenti non ordina
xt (compreso tra 0 e 3) rappresenta il numero di
macchine fotografiche dopo t settimane
la domanda dt è una variabile aleatoria con una certa
p.d.f.; ad esempio con distribuzione di Poisson
λk e−λ
p(d = k) = k! con λ = 1
(
max(3 − dt+1 , 0) se xt = 0
xt+1 =
max(xt − dt+1 , 0) se xt 6= 0
Catene di Markov – p.10/19
soluzione problema di scorte
Π0 = (0, 0, 0, 1)
pij = p(xt = j|xt−1 = i)
p00 = p(xt+1 = 0|xt = 0) = p(dt+1 ≥ 3) ≈ 0.08
p10 = p(xt+1 = 0|xt = 1) = p(dt+1 ≥ 1) ≈ 0.632
...


0.080 0.184 0.368 0.368
 0.632 0.368

0
0


P =

 0.264 0.368 0.368
0 
0.080 0.184 0.368 0.368
Catene di Markov – p.11/19
definizioni
P è detta strettamente positiva (e si scrive P > 0) se
pij > 0;
uno stato j è accessibile da uno stato i se esiste k tale
(k)
che pij > 0
due stati sono comunicanti se esistono k1 , k2 tali che
(k )
(k )
pij 1 > 0 e pji 2 > 0
il concetto di comunicazione è una relazione di
equivalenza (valgono le proprietà riflessiva, simmetrica
e transitiva)
la proprietà di essere comunicanti permette di definire
delle classi di stati comunicanti
Catene di Markov – p.12/19
definizioni (2)
una catena di Markov è irriducibile se esiste una sola
classe di stati comunicanti (ad esempio una catena
strettamente positiva è irriducibile)
una catena di Markov è riducibile se esistono almeno
due classi di stati comunicanti ed una non è accessibile
dall’altra
uno stato si dice assorbente se per ogni k ≥ 0 si ha
(k)
pii = 1 (ad esempio il primo ed ultimo stato della
passeggiata aleatoria)
un insieme di stati si dice chiuso quando nel momento
in cui si entra in uno stato dell’insieme, si rimane
all’interno di esso
Catene di Markov – p.13/19
definizioni (3)
periodo dello stato i: d(i) = mcd(k
30
(k)
pii
> 0)
se d(i) = 1 lo stato si dice a-periodico; una catena con
stati a-periodici è detta a-periodica
tempo di primo passaggio:
(n)
fij = p(xn = j|x0 = i, xk 6= j, k = 1, . . . , n − 1),
probabilità di passare dallo stato i a j per la prima volta
(1)
(0)
dopo n passi (fij = pij , fij = 0 se i 6= j )
(n)
(0)
tempo di ritorno: fii (fii = 1)
Catene di Markov – p.14/19
proprietà
(n)
pij =
n
X
(m) (n−m)
fij pjj
m=1
(n)
fij
=
(n)
pij
−
n−1
X
(m) (n−m)
fij pjj
m=1
fii∗ =
∞
X
(m)
fii
probabilità di tornare prima o poi nello
m=1
stato i
fii∗ < 1: stato i transiente
fii∗ = 1: stato i ricorrente (ad esempio lo stato
assorbente)
Catene di Markov – p.15/19
proprietà
uno stato i è ricorrente quando se
k2 tale che
se
e
∞
X
(m)
pii
m=1
∞
X
(m)
pii
m=1
se
∞
X
> 0, allora esiste
>0
< ∞, allora lo stato i è transiente,
(m)
pii
→0
1
=
1 − fii∗
(m)
pii
(k2 )
pji
(k1 )
pij
diverge, allora lo stato i è ricorrente
m=1
Catene di Markov – p.16/19
proprietà stati ricorrenti
per gli stati ricorrenti
(tempo di ricorrenza)
(n)
fii
p.d.f. di una v.a. discreta
tempo medio di ricorrenza: valore atteso mi =
∞
X
(n)
nfii
n=1
i stato ricorrente a-periodico ⇒
(n)
lim pii
n→+∞
1
=
mi
se il limite è positivo lo stato si dice fortemente
ergodico; viceversa (il limite è nullo) debolmente
ergodico
se uno stato è fortemente ergodico
(n)
lim pji
n→+∞
1
=
mi
Catene di Markov – p.17/19
matrici di transizione con stati ergodici
se tutti gli stati di una catena di Merkov sono ergodici
esiste n tale che P n > 0
esiste Π tale che Π = ΠP ; Π è un punto fisso della
successione (Πk ) ed inoltre P n tende alla matrice
T
T
T
T
Q = Π ,Π ,...,Π
Catene di Markov – p.18/19
esempio



P =


0 1/3 1/3 1/3
1/2 0
0 1/2 


2/3 0
0 1/3 
1
0
0
0
tutti gli stati sono ergodici
Pn > 0
da Π = ΠP si ha Π = (18/41, 6/41, 6/41, 11/41)
la matrice P n tende ad una matrice costante
Catene di Markov – p.19/19