Catena di Markov tempo discreta

RETI DI TELECOMUNICAZIONE
CATENE DI MARKOV
TEMPO DISCRETE
Definizioni
¾ Catena:
9 Processo stocastico in cui lo spazio degli stati è discreto o numerabile
¾ Processo stocastico tempo discreto:
9 Si considerano i valori del processo X(t) solo per un numero finito o
infinito di istanti fissati tn
9 Indicheremo semplicemente con n i diversi istanti di tempo
t1 < t2 < …< tn <…
¾ Catena tempo discreta:
9 Indicheremo con xn il valore assunto dalla catena all’istante n
¾ Catena di Markov tempo discreta:
9 Una catena tempo discreta in cui al generico istante n, la probabilità di
transizione da uno stato i a uno stato j è fissa e indipendente dalla storia
che ha portato il processo allo stato i
9 Indicheremo con Pij(n) tale probabilità
CATENE DI MARKOV TEMPO DISCRETE
2
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
1
Catena di Markov tempo discreta
¾ Vale la condizione
CATENE DI MARKOV TEMPO DISCRETE
3
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Matrice di transizione ad un passo
¾ Il generico elemento in posizione ij rappresenta la probabilità di
transitare dallo stato i allo stato j al passo n
CATENE DI MARKOV TEMPO DISCRETE
4
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
2
Matrice di transizione a più passi
¾ Considerato n>m
possiamo costruire una matrice di probabilità di transizione a
più passi
il generico elemento in posizione ij rappresenta la probabilità di
transitare dallo stato i allo stato j dal passo m al passo n
CATENE DI MARKOV TEMPO DISCRETE
5
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Proprietà
¾ Valgono le seguenti proprietà
9 La probabilità di raggiungere, partendo dallo stato i all’istante n-1, un
qualunque altro stato all’istante all’istante n è 1
9 La probabilità di raggiungere, partendo dallo stato i all’istante m, un
qualunque altro stato all’istante n>m è 1
¾ La somma per righe delle matrici P(n) e H(m,n) è il vettore colonna
fatto da tutti 1
CATENE DI MARKOV TEMPO DISCRETE
6
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
3
Classificazione
¾ Si effettua una classificazione dei singoli stati di una catena di
Markov
¾ Se è possibile classificare tutti gli stati analogamente allora si
può classificare la catena di Markov con la caratteristica
riscontrata per tutti i singoli stati
¾ La maggior parte delle classificazioni è basata sull’idea di tempo
di “primo passaggio”: il tempo di primo passaggio dallo stato i
allo stato j è il numero di passi necessario per raggiungere lo
stato j partendo dallo stato i
¾ Possiamo calcolare una distribuzione di probabilità dei tempi di
primo passaggio
CATENE DI MARKOV TEMPO DISCRETE
7
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Classificazione
¾ Accessibilità
9 Uno stato j è accessibile da un altro stato i se esiste la probabilità non
nulla di transitare dallo stato i allo stato j in un numero finito di passi
¾ Comunicabilità
9 Due stati i,j comunicano tra di loro se esistono due numeri finiti di passi
m,n tali che
€ Cioè esiste una probabilità non nulla di transitare in un numero finito di passi dallo
stato i allo stato j e successivamente dallo stato j allo stato i
CATENE DI MARKOV TEMPO DISCRETE
8
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
4
Classificazione
¾ Stato transitorio
9 La probabilità di non ritornare mai allo stato i dopo averlo visitato è non
nulla
¾ Stato ricorrente
9 La probabilità di ritornare allo stato i dopo averlo visitato è 1 (anche dopo
un numero infinito di passi)
CATENE DI MARKOV TEMPO DISCRETE
9
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Classificazione
¾ Tempo medio di ricorrenza
9 Dato uno stato ricorrente i rappresenta il numero medio di passi
necessari per ritornarvi dopo averlo visitato
9 A seconda che la media sia un valore finito o infinito distinguiamo in
¾ Stati ricorrenti nulli
¾ Stati ricorrenti non nulli
CATENE DI MARKOV TEMPO DISCRETE
10
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
5
Classificazione
¾ Esempio di stato ricorrente
nullo
….
9 Lo stato 0 è ricorrente
=1 (Serie di Mengoli)
nullo
CATENE DI MARKOV TEMPO DISCRETE
11
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Classificazione
¾ Stato periodico
9 Uno stato ricerrente non nullo si dice periodico se la probabilità di
ritornarvi dopo averlo visitato in n passi è non nulla solo per valori di n
multipli di un certo periodo d
9 Il periodo di ricorrenza d può essere definito come
¾ Stato aperiodico
9 Uno stato ricerrente non nullo si dice aperiodico se non è periodico
€ d=1
CATENE DI MARKOV TEMPO DISCRETE
12
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
6
Classificazione
¾ Esempio di stato ricorrente
non nullo periodico
CATENE DI MARKOV TEMPO DISCRETE
13
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Classificazione
¾ Se tutti gli stati godono della stessa proprietà allora la catena di
Markov può essere classificata come lo stato:
9 Catene di Markov ricorrenti non nulle
9 Catene di Markov periodiche
9 Catene di Markov aperiodiche
¾ Inoltre
9 Quando tutti gli stati comunicano tra di loro la catena di Markov si dice
irriducibile (ergodica)
CATENE DI MARKOV TEMPO DISCRETE
14
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
7
Probabilità di stato
¾ Rappresenta la probabilità di trovarsi ad un determinato
istante n in un certo stato i
¾ Si può quindi definire un vettore riga di probabilità di stato
Nel quale l’elemento i-esimo rappresenta la probabilità di
trovarsi nello stato i all’istante n
CATENE DI MARKOV TEMPO DISCRETE
15
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Equazione di Chapman-Kolmogorov
¾ La probabilità di transitare dallo stato i (al passo m) allo stato j
(al passo n) può essere calcolata come la somma delle
probabilità di transitare dallo stato i verso un qualunque altro
stato k (ad un passo intermedio m<q<n) e quindi dallo stato k
allo stato j
n
q
CATENE DI MARKOV TEMPO DISCRETE
m
16
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
8
Dimostrazione equazione di
Chapman-Kolmogorov
Bayes
CATENE DI MARKOV TEMPO DISCRETE
17
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Forma matriciale dell’equazione di
Chapman-Kolmogorov
¾ Le equazioni di Chapman-Kolmogorov possono essere scritte in
forma matriciale
posto q=n-1
sarà
Quindi
CATENE DI MARKOV TEMPO DISCRETE
18
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
9
Calcolo probabilità di stato al passo n nota la
probabilità di stato al passo n-1
CATENE DI MARKOV TEMPO DISCRETE
19
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Calcolo probabilità di stato al passo n nota la
probabilità di stato iniziale (passo 0)
CATENE DI MARKOV TEMPO DISCRETE
20
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
10
Catene di Markov omogenee
¾ In una catena di Markov omogenea le probabilità di transisizione
sono costanti al variare del tempo (passo)
9 Per cui sarà
9 La probabilità di transizione al passo n sarà quindi
CATENE DI MARKOV TEMPO DISCRETE
21
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Catene di Markov omogenee
¾ Inoltre sarà
¾ Quindi
CATENE DI MARKOV TEMPO DISCRETE
22
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
11
Catene di Markov omogenee
¾ Da cui
¾ Inoltre per le catene di Markov omogenee sarà
9 Ossia la probabilità di primo passaggio dallo stato i allo stato j in n passi
corrisponde all’elemento (i,j) della matrice Pn
CATENE DI MARKOV TEMPO DISCRETE
23
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Probabilità di stato limite
¾ Una distribuzione di probabilità di stato
si dice stazionaria per la catena di Markov se
9 Cioè, una volta raggiunta, la distribuzione delle probabilità di stato
rimane costante
¾ In forma matriciale
CATENE DI MARKOV TEMPO DISCRETE
24
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
12
Probabilità di stato limite per
catene di Markov omogenee
¾ Se la catena è omogenea sarà
quindi
da cui
o anche
CATENE DI MARKOV TEMPO DISCRETE
25
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Probabilità di stato limite per
catene di Markov omogenee
rappresenta la quota parte di tempo in cui il processo visita lo
stato j
è il tempo medio di ricorrenza
9 Numero atteso di passi tra due successive visite allo stato j
CATENE DI MARKOV TEMPO DISCRETE
26
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
13
Probabilità di stato limite per catene di
Markov omogenee, irriducibili e aperiodiche
¾ Si ha che
¾ Si può dimostrare che in una catena di Markov omogenea,
irriducibile e aperiodica si possono avere solo due diverse
condizioni:
1.
per tutti gli stati j≥0
allora la catena di Markov non ha distribuzione stazionaria
2.
per tutti gli stati j≥0
allora la distribuzione è l’unica possibile per la catena
CATENE DI MARKOV TEMPO DISCRETE
27
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Equazioni di bilanciamento globale
¾ Se per una data catena esiste la distribuzione stazionaria può
essere calcolata attraverso le equazioni di bilanciamento
globale
moltiplicando entrambi i membri per
CATENE DI MARKOV TEMPO DISCRETE
28
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
14
Equazioni di bilanciamento globale
sarà
da cui
CATENE DI MARKOV TEMPO DISCRETE
29
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Equazioni di bilanciamento globale
¾ Il primo termine rappresenta la probabilità di andare dallo stato j
verso qualunque altro stato
¾ Il secondo termine rappresenta la probabilità di arrivare allo
stato j da qualunque altro stato
¾ Quindi in condizioni di equilibrio la probabilità di lasciare un
qualunque stato j eguaglia la probabilità di arrivare allo stesso
stato j
¾ Il concetto può essere generalizzato ad un insieme di stati
CATENE DI MARKOV TEMPO DISCRETE
30
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
15
Esempio 1
¾ Si consideri una “Land of Oz” in cui le condizioni meteorologiche:
9 Possano essere rappresentate esclusivamente dagli stati
€ [S]oleggiato
€ [N]uvoloso
€ [P]iovoso
9 Le condizioni di un dato giorno dipendono probabilisticamente esclusivamente
dalle condizioni del giorno precedente
In particolare:
€
€
€
€
€
€
€
€
€
Se oggi è soleggiato la probabilità che domani sia soleggiato è 0.7
Se oggi è soleggiato la probabilità che domani sia nuvoloso è 0.2
Se oggi è soleggiato la probabilità che domani sia piovoso è 0.1
Se oggi è nuvoloso la probabilità che domani sia nuvoloso è 0.5
Se oggi è nuvoloso la probabilità che domani sia soleggiato è 0.3
Se oggi è nuvoloso la probabilità che domani sia piovoso è 0.2
Se oggi è piovoso la probabilità che domani sia piovoso è 0.2
Se oggi è piovoso la probabilità che domani sia soleggiato è 0.2
Se oggi è piovoso la probabilità che domani sia nuvoloso è 0.6
CATENE DI MARKOV TEMPO DISCRETE
31
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Esempio 1
¾ Diagramma delle transizioni
e matrice di transizione P
9 Lo stato [S] corrisponde a 1
9 Lo stato [N] corrisponde a 2
9 Lo stato [P] corrisponde a 3
CATENE DI MARKOV TEMPO DISCRETE
32
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
16
Esempio 1
¾ Matrice di transizione a più passi
9 La matrice Pn indica la probabilità di transizione in n passi
€ P2 indica ad esempio nella posizione (3,3) che se oggi è piovoso la probabilità che
dopodamani sia ancora piovoso è 0.18
 Questo non implica che anche domani sia piovoso (ma non lo esclude)
 Possibili transizioni:
P→P→P = 0.22=0.04
P→N→P = 0.6·0.2=0.12
P→S→P = 0.2·0.1=0.02
CATENE DI MARKOV TEMPO DISCRETE
33
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Esempio 1
¾ Al crescere di n la matrice di transizione tende a stabilizzarsi
i valori tendono alle probabilità di stato limite
¾ Le probabilità di stato limite possono essere calcolate
risolvendo il sistema di equazioni
considerando che deve essere
CATENE DI MARKOV TEMPO DISCRETE
34
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
17
Esempio 1
¾ Sarà infatti
dove I è la matrice identica e t indica la matrice trasposta
¾ La matrice A avrà rango N-1 (se N è il numero degli stati)
9 Una delle equazioni scritte è combinazione lineare delle rimanenti N-1
9 Possiamo sostituire una delle equazioni (l’ultima) con la relazione
CATENE DI MARKOV TEMPO DISCRETE
35
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Esempio 1
¾ Il sistema diviene
posto
possiamo risolvere il sistema
CATENE DI MARKOV TEMPO DISCRETE
36
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
18
Esempio 1
¾ Nel nostro caso la matrice A assume la forma
da cui
la soluzione del sistema sarà ponendo
CATENE DI MARKOV TEMPO DISCRETE
37
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Esempio 1
¾ Grandezze a regime
9 Probabilità che un giorno sia soleggiato ≅ 0.475
9 Probabilità che un giorno sia nuvoloso ≅ 0.373
9 Probabilità che un giorno sia piovoso ≅ 0.152
9 Tempo medio di ricorrenza di un giorno soleggiato ≅ 2.1
9 Tempo medio di ricorrenza di un giorno nuvoloso ≅ 2.7
9 Tempo medio di ricorrenza di un giorno piovoso ≅ 6.6
CATENE DI MARKOV TEMPO DISCRETE
38
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
19
Esempio 1 (usando MatLab)
¾ Costruzione matrice di transizione P
9 P=[[0.7 0.2 0.1]; [0.3 0.5 0.2]; [0.2 0.6 0.2]]
€ Ogni gruppo di numeri fra parentesi [] indica una riga della matrice
€ Il simbolo “;” serve a separare le varie righe
¾ Costruzione della matrice identica I di dimensioni 3x3
9 Impostiamo il valore della variabile N (rappresenterà il numero di stati) a
3 con il comando
€ N=3
9 Per creare la matrice identica utilizziamo la funzione eye
€ I=eye(N,N)
¾ Costruzione della matrice A
9 A=(P-I)'
€ Il simbolo ' indica la matrice trasposta
¾ Rango e determinante della matrice A
9 rank(A)
det(A)
CATENE DI MARKOV TEMPO DISCRETE
39
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Esempio 1 (usando MatLab)
¾ Costruzione della matrice A1
9 A1=[A(1:end-1,:); ones(1,N)]
€ La funzione ones(n,m) crea una matrice costituita da tutti 1 di dimensioni n · m
€ L’operatore end rappresenta la dimensione della matrice per quel particolare indice
€ Il simbolo : serve ad indicare un range di valori
 [1:10] = [1 2 3 4 5 6 7 8 9 10]
 Quando si specifica senza valore iniziale e finale permette di selezionare tutti gli elementi in
quella particolare dimensione
¾ Costruzione della matrice B
9 B=[zeros(N-1,1); 1];
€ La funzione zeros(n,m) crea una matrice costituita da tutti 0 di dimensioni n · m
¾ Soluzione del sistema lineare
9 X=A1\B
CATENE DI MARKOV TEMPO DISCRETE
40
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
20
Esempio 2
¾ Si consideri la seguente catena di Markov con p=0.2
Scriviamo una funzione in Matlab che calcoli la probabilità di
stato nei passi 1:n, nota la distribuzione delle probabilità di
stato al passo 0 per una catena di Markov omogenea
CATENE DI MARKOV TEMPO DISCRETE
41
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Esempio 2
¾
function pGreco=pDiStato(pGreco0, P, N)
% pGreco0 = vettore della distribuzione
iniziale delle probabilità di stato
% P = matrice di transizione di stato
% N = mumero di passi
pGreco = [];
% Determino le dimensioni della matrice P
[n, m] = size(P);
% Verifico la correttezza della matrice P
if n~=m
disp('ERRORE: La matrice P deve
essere quadrata');
return;
end
if sum(sum(P') ~= ones(1,n)) ~= 0
disp('ERRORE: la somma di ogni riga
della matrice P deve essere 1');
return
end
% Determino le dimensioni del vettore
pGreco0
[n0, m0] = size(pGreco0);
% Verifico la correttezza della matrice
pGreco0
if n0 ~= 1
disp('ERRORE: il vettore pGreco0 deve
essere tipo riga');
return
end
if m0 ~= n
disp(['ERRORE: il numero di colonne
del vettore pGreco0 deve essere '...
'uguale alle dimensioni della
matrice P']);
return
end
if sum(pGreco0) ~= 1
disp('ERRORE: la somma degli elementi
del vettore pGreco0 deve essere 1');
return
end
% Stato iniziale
pGreco(1,:)=pGreco0;
% Ciclo stati
for i=2:N+1
pGreco(i,:)=pGreco(i-1,:)*P;
end
CATENE DI MARKOV TEMPO DISCRETE
42
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
21
Esempio 2
¾ Costruzione delle matrici di stato iniziale e di probabilità di
transizione
9 pGreco0 = [1 0 0];
9 P=[[0 1 0]; [0.8 0 0.2]; [0 1 0]];
¾ Calcolo delle probabilità di stato per i passi da 1 a 100
9 pGreco=pDiStato(pGreco0, P, 100);
¾ Grafico dell’andamento delle probabilità di stato per i 3 diversi
stati
9 plot(pGreco(:,1), 'b-.')
9 plot(pGreco(:,2), 'r-.')
9 plot(pGreco(:,3), 'g-.')
CATENE DI MARKOV TEMPO DISCRETE
43
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Esempio 2
¾ Si osservi il comportamento periodico
¾ Non ha senso parlare di distribuzione di probabilità di stato limite
CATENE DI MARKOV TEMPO DISCRETE
44
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
22
Esempio 3
¾ Consideriamo nuovamente le condizioni metereologiche
della “Land of Oz”
9 Supponendo che lo stato iniziale sia un giorno seleggiato
¾ Le probabilità di stato tendono rapidamente al valore limite
CATENE DI MARKOV TEMPO DISCRETE
45
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Esempio 4
¾ Graficare l’andamento delle probabilità di stato per i primi 100
passi, si calcoli il valore limite delle probabilità di stato per la
seguente catena di Markov supponendo che al passo 0 il
sistema si trovi allo stato 0
9 Per l’andamento delle probabilità di stato possiamo utilizzare la solita
funzione
€ pGreco=pDiStato(pGreco0, P, n)
9 Per il calcolo delle probabilità di stato a regime possiamo scrivere una
nuova funzione
€ pGrecoStazionaria=pDiStatoStazionaria(P)
CATENE DI MARKOV TEMPO DISCRETE
46
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
23
Esempio 4
¾ Dopo un certo numero di oscillazioni le probabilità di stato
convergono a quelle limite
CATENE DI MARKOV TEMPO DISCRETE
47
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Esempio 4
¾
function pGrecoStazionaria=pDiStatoStazionaria(P)
% P = matrice di transizione di stato
pGrecoStazionaria=[];
% Determino le dimensioni della matrice P
[n, m] = size(P);
% Verifico la correttezza della matrice P
if n~=m
disp('ERRORE: La matrice P deve essere quadrata');
return;
end
if sum(sum(P') ~= ones(1,n)) ~= 0
disp('ERRORE: la somma di ogni riga della matrice P deve essere 1');
return
end
% Creo la matrice identica
I=eye(n,n);
% Calcolo la matrice A
A=(P-I)';
% Sostituisco i coefficienti dell'ultima equazione
A1=[A(1:end-1,:); ones(1,n)];
% Creo la matrice B
B=[zeros(n-1,1); 1];
% Risolvo l'equazione A1 X = B
% Verifico la correttezza del sistema di equazioni
if rank(A1) ~= n
disp('ERRORE: il sistema è non risolvibile');
return
end
pGrecoStazionaria = (A1\B)';
CATENE DI MARKOV TEMPO DISCRETE
Soluzione
Π1 =
0.0909
Π2 =
0.4545
Π3 =
0.4545
48
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
24
Esercizio
¾ Un topo bianco è inserito all’interno del
labirinto mostrato in figura.
Ci sono 9 scomparti con i passaggi
indicati in figura.
Gli scomparti si aprono ad istanti
regolari e, ogni volta che si aprono,
il topo si muove casualmente fra
i vari scomparti: se si trova in
uno scomparto con k vie di uscita ne sceglierà una con
probabilita 1/(k+1) e con la stessa probabilità deciderà di
rimanere in quello scomparto.
¾ Descrivere gli spostamenti del topo attraverso una catena di
Markov (matrice delle probabilità di transizioni) e determinare la
probabilità di stato limite.
CATENE DI MARKOV TEMPO DISCRETE
49
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Soluzione
Π1 = 0.0909
Π2 = 0.1212
Π3 = 0.0909
Π4 = 0.1212
Π5 = 0.1515
Π6 = 0.1212
Π7 = 0.0909
Π8 = 0.1212
Π9 = 0.0909
CATENE DI MARKOV TEMPO DISCRETE
50
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
25
Soluzione
CATENE DI MARKOV TEMPO DISCRETE
51
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Catene di nascita e morte
(birth & death)
¾ E’ una particolare catena di Markov tempo discreta in cui sono
possibili solo incrementi o decrementi unitari dello stato
¾ E’ il modello utilizzato per la rappresentazione dell’evoluzione
del numero di individui di una popolazione
¾ Al generico passo i indicheremo con
9 bi = la probabilità di una nascita
9 di = la probabilità di una morte
¾ Sarà
CATENE DI MARKOV TEMPO DISCRETE
52
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
26
Catene di nascita e morte
(birth & death)
b0
0
1-b0
b1
1
d1
d2
…
1-b0-d0
bi-2
bi-1
i-1
di-1
di
1-bi-1-di-1
bi
i
di+1
…
1-bi-di
¾ La catena è irriducibile se
9 0<bi<1 ∀ i ≥ 0
9 0<di<1 ∀ i > 0
¾ La catena è aperiodica se
9 b0<1 o ∃ i : bi + di <1
¾ La catena è periodica di periodo 2 se
9 bi + di =1 per ∀ i
CATENE DI MARKOV TEMPO DISCRETE
53
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Catene di nascita e morte
(birth & death)
¾ Distribuzione delle probabilità a regime
9 Possiamo calcolarle risolvendo il sistema di equazioni
in cui le generiche equazioni assumono la forma
CATENE DI MARKOV TEMPO DISCRETE
54
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
27
Catene di nascita e morte
(birth & death)
¾ Distribuzione delle probabilità a regime
9 Oppure considerando gli insiemi del tipo S in figura, scrivendo le
equazioni di bilanciamento dettagliate
CATENE DI MARKOV TEMPO DISCRETE
55
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Catene di nascita e morte
(birth & death)
¾ Le equazioni di bilanciamento dettagliate possono essere risolte
in maniera ricorsiva
considerando la normalizzazione delle probabilità di stato
CATENE DI MARKOV TEMPO DISCRETE
56
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
28
Catene di nascita e morte
(birth & death)
¾ Quando la sommatoria al denominatore converge
9 Gli stati sono tutti ricorrenti non nulli
9 Le Πi trovate costituiscono la distribuzione stazionaria delle probabilità di
stato
9 La catena di nascita e morte è ergodica
9 Condizione sufficiente per la convergenza è che
¾ Quando la sommatoria al denominatore non converge
9 La catena di nascita e morte non è ergodica
CATENE DI MARKOV TEMPO DISCRETE
57
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
Catene di nascita e morte
(birth & death)
¾ Frequenza state-independent
9 Le probabilità di nascita e di morte sono costanti per ogni stato
quindi
CATENE DI MARKOV TEMPO DISCRETE
58
Corso "Reti di Telecomunicazione" - CdL Magistrale in Ingegneria Informatica - (Ing. Salvatore Serrano)
29