1

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.

5. Catene di Markov a tempo discreto (CMTD)

2

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]

3

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 (kN)

P(k) = [ pij(k) ]

pij(k) = Pr{ x(k+1)=xj| x(k)=xi }

xi,xjX, kN

• (0): distribuzione di probabilità assoluta iniziale (vettore riga)

(0)=[ i(0), iN ]

dove i(0)=Pr{ x(0)=xi }, xi X

4

La matrice P(k) soddisfa le seguenti condizioni k N :

• pij(k) [0,1], xi,xjX

• xj X pij(k) = 1 xiX

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.

la somma degli elementi lungo una riga è = 1

5

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

bb1a1aP

6

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

x1x0

b

1-ba

1-a

N.B. La somma dei pesi degli archi uscenti da ciascun vertice deve essere pari a 1.

7

Equazioni di evoluzione

Sia (k) = [ i(k), iN ]

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:

(k) = (k-1) P(k-1)xj

j(k)= xi X Pij(k-1) i(k-1)

Segue dal fatto che per ogni j:

(k) = (0) P(0) P(1) … P(k-1)

Equazione di Chapman-Kolmogorov

8

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 Chapman-Kolmogorov per CMTD omogenea

9

Esempio: si consideri un robot sempre alimentato che prende i pezzi e li mette in un deposito di capacità infinita.

I = inattivo,

T = in trasferimento,

G = guasto.

X={I,T,G}

TI

1-r- q

r1-p

p

G 1-s

qs

p: p. che inizi a lavorare,

r: p. che concluda la lavoraz.

10

(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]

s10sqqr1r0pp1

P

In tal modo posso studiare il transitorio della CMTD.

11

Ricordiamo ora le seguenti definizioni:

T E

T

T: componente transitoria o transiente

E: componente ergodica o assorbente

3 componenti fortemente connesse

12

N.B.

Dato un grafo orientato, un sotto-insieme di nodi costituisce una componente fortemente connessa se e solo se ogni nodo è raggiungibile da un qualunque altro nodo seguendo un cammino orientato.

13

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)

14

Classificazione degli stati di una CMTD

Uno stato xjX è detto raggiungibile o accessibile da un altro stato xiX, 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.

15

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.

16

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 è

1nii (n)ρρ

17

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 };

18

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.

Dall’osservazione del grafo, possiamo invece dedurre quanto segue.

19

Esempi: Date le seguenti CMTD, vogliamo capire se lo stato ricorrente x1 è periodico

x2x1 1

x3

10.5

x4

1 0.5

x2x1 1

x3

11

{ n>0 | p11(n) > 0 } = {3, 6,

9, … }1)

MCD=3 --> x1 è periodico di periodo 3

2)

{ n>0 | p11(n) > 0 } = {3, 6, 9,

… , 4, 8, 12, … , 7, 11, … }

MCD=1 --> x1 è aperiodico

20

3)

4){ n> 0 | p11

(n) > 0 } = {2, 4, 6, 8, … }

MCD=2 --> x1 è periodico di periodo 2

x2x1

0.3

x3

1

x4

0.7

11

{ n>0 | p11(n) > 0 } = {3, 6,

9, … , 2, 4, 8, … , 5, 7, ... }MCD=1 --> x1 è

aperiodico

x2x1

0.3

x3

1

x4

0.7

11

x5

1

{ n>0 | p44(n) > 0 } = {4, 6, 8,

10, … }MCD=2 --> x4 è periodico di periodo 2

21

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.

22

Osservazione:

La periodicità di uno stato dipende solo dalla struttura del grafo non dal particolare valore che dei pesi associati agli archi.

23

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.

Periodicità di una componente ergodica

24

Es. n3

x2x1

1

1

642

53

PP1001P

PP0110P

= { n | p(n)ii > 0 i } = {2, 4, 6, … }

D=2

25

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.

26

Esempiox2x1

1

0.4

x3x4

0.6

1

1

Tutti gli stati sono periodici di periodo 2 per cui la componente ergodica è anch’essa periodica di periodo 2.

27

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).

Come caso particolare di quanto sopra:

28

Esempio

x1x0

0.3

0.70.4

0.6

x41

0.5

x3x2 1

1

x50.1

0.10.1

0.1 0.1

La CMTD è riducibile: non tutti gli stati sono comunicanti ossia mutuamente raggiungibili.

29

• 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.

30

Distribuzione stazionaria

Consideriamo ora CMTD omogenee.

Una distribuzione di probabilità assoluta s viene detta stazionaria se e solo se sono verificate le seguenti condizioni:

i is,s

ss

1Π11ΠPΠΠ

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.

31

Osservazione:

Non e’ detto che una CMTD ammetta distribuzione stazionaria.

Non e’ detto che se esiste una certa distruzione stazionaria questa sia unica.

32

Distribuzione limite

Una CMTD ha una distribuzione limite se per k , la distribuzione di probabilità assoluta tende ad un vettore costante, ossia

Π(k)limΠk

l

Proposizione: Se l è una distribuzione limite, allora essa è anche stazionaria.

Dim. (k) = (k-1) P

Π(k)Plim1)Π(klimkk

PΠΠ ll

33

Ergodicità

Una CMTD è ergodica se e solo se:

1) esiste

2) tale limite è unico e non dipende dalla particolare distribuzione iniziale (0).

Π(k)limk

Se tali condizioni sono verificate, è sufficiente studiare una qualunque realizzazione per capire il comportamento della catena a regime.

34

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).

35

Esempio n1x2x1

1

0.1

0.9

10

0.10.9P

100.10.10.90.9P

22

100.10.10.90.10.90.9P

233

10

0.90.10.9P1k

0i

ikk

100.910.9P

kkk

36

Sia 0,20,1 ΠΠΠ(0)

0,1k

0,20,10,1kk Π0.9ΠΠΠ0.9PΠ(0)Π(k)

10ΠΠ0Π(k)lim 0,20,1k

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).

37

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.

38

Esempio n2 x2

x1

1

0.5

x3 10.5

100010

0.50.50P

0kPPk

0,30,10,20,1k ΠΠ0.5ΠΠ0.50PΠ(0)Π(k)

se 0.50.50Π(k)001Π(0) l

se 010Π(k)010Π(0) l

Tale CMTD è quindi non ergodica.

39

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

[0,1]αα1α0Πs

40

Esempio n3

x2x1

1

1

01

10P

10

01P222k

12k

PPPP

0,20,1 ΠΠΠ(0)

pari kΠΠdispari kΠΠ

PΠ(0)Π(k)0,20,1

0,10,2k

Π(k)limk

Quindi, in generale non esiste a meno che non sia 0.5ΠΠ 0,20,1

La CMTD non è ergodica.

41

N.B. In questo caso esiste una sola distribuzione stazionaria 0.50.5Πs

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)

42

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

10

0.10.9P

10.9

2

1

λλ

ergodica

43

Es. n2

100010

0.50.50P

10

32

1

λλλ

non ergodica

Es. n3

01

10P

11

2

1

λλ

non ergodica

44

Criterio grafico

x2x1

1

0.1

0.9

Es. n1

La condizione necessaria è verificata essendo {x2} l’unica componente ergodica.

Ciò tuttavia non basta per concludere che tale CMTD è ergodica.

Teorema: Condizione necessaria affinché una CMTD omogenea finita sia ergodica è che il grafo ad essa associato ammetta un’unica componente ergodica.

45

Es. n2

x2

x1

1

0.5

x3 10.5

La condizione necessaria non è verificata in quanto vi sono due componenti ergodiche ({x2} e {x3}). Possiamo subito concludere che tale CMTD non è ergodica.

x2x11

1Es. n3

La condizione necessaria è verificata essendo {x1, x2} una componente ergodica.

Non posso però concludere che tale CMTD è ergodica.

46

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 x2x1

1

0.1

0.9

La CMTD è ergodica in quanto {x2} è l’unica componente ergodica e questa è chiaramente aperiodica.

47

Es. n3x2x1

1

1

La CMTD non è ergodica essendo la componente ergodica periodica di periodo 2.

48

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.

49

0 1 2 3

1 - b0 1 - b1- d1 1 - b2- d2 1 - b3- d3

b0 b1 b2

d1 d2 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, … ).

50

• 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)

aperiodica (è costituita da un’unica componente ergodica e tale

componente è aperiodica: esiste infatti sempre almeno il cappio relativo allo stato 0).

• 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 è

51

4

333

2222

1111

00

d00db1d00

bdb1d00bdb1d00bb1

P

La matrice delle probabilità di transizione ha la seguente struttura:

P ha chiaramente dimensione infinita se il numero degli stati è infinito.

52

Calcolo della distribuzione stazionaria (nel caso in cui il numero degli stati sia infinito):

i is,

ss

1ΠPΠΠ

1Π

Πd

bΠ

Πdb

Π

Πdb

Π

iis,

1is,i

1iis,

s,12

1s,2

s,01

0s,1

se il processo è uniforme, d

bρ

i is,

1-is,is,

1ΠΠρΠ

1ΠΠρΠ

ΠρΠΠρΠ

iis,

s,i

is,

s,02

s,2

s,0s,1

0

53

1 s,02

s,0s,0 ΠρΠρΠ

ii

s,0 1ρΠ se questa serie converge, allora la catena è ergodica.

Ciò è vero purché sia

1db

ρ

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 .

54

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

55

È interessante calcolare il numero medio di utenti a regime:

0 i

is,0 i

il, ΠiΠiμ

Posso usare la funzione generatrice di probabilità:

ρzzρ)(1

zρ

1

1ρ)(1

zρ

ρ)(1

zρ)](1[ρzΠΠ(z)

0i

i

0 i

ii

0 i

iis,

56

ρ)(1ρ

ρ)(11-ρ-1

ρ)(1ρ)(1ρ)(1

ρ)(zρ)z(1ρ)ρ)(z(1

dzdΠ

μ

2

2

1z2

1z

(z)

ρ)(1ρ

μ

numero medio di utenti a regime