Lanturi Markov. Definitie, proprietati, simulare.

Algoritmul PageRank-Google

10.1 Definitia si simularea lanturilor Markov

Lanturile Markov discrete se folosesc n practica modelarii si simularii sistemelor n care seproduc evenimente la momente discrete de timp t = 0, 1, 2, . . . , n, . . .. Ele modeleaza sis-teme de comunicatii, sistemul calculator, piata financiara, sisteme biologice, etc. LanturileMarkov se folosesc n design-ul algoritmilor de rutare n retele, n simularea cozilor laun server. Exista chiar si un limbaj de modelare pentru sisteme hardware/software ntimp real, numit POOSL, Parallel Object Oriented Specification Language, caregenereaza un lant Markov, ca model al sistemului. Studiul modelului permite evaluareaperformantelor si fiabilitatii sistemului.

Elemente definitorii ale lantului Markov

O multime finita S = {1, 2, . . . ,m} numita spatiul starilor (se considera S, unsistem ce poate avea un numar finit de stari). Schimbarile de stare se produc la ntamplare,la momente discrete de timp t = 0, 1, 2, . . . , n, . . ..

Starea la momentul n este descrisa de o variabila aleatoare discreta Xn.Multimea valorilor variabilei aleatoare Xn este deci S = {1, 2, . . . ,m}.

Definitia 10.1.1 Sirul de variabile aleatoare (Xn), n N, defineste un lant Markovdiscret daca probabilitatea ca la momentul (n + 1) sistemul sa se afle n starea j, stiindca n momentele de timp precedente se afla respectiv n starile s0, s1, . . . sn1, i este:

P (Xn+1 = j|X0 = s0, X1 = s1, . . . Xn = i) = P (Xn+1 = j|Xn = i) (10.1)

P (Xn+1 = j|Xn = i) se citeste: probabilitatea ca sistemul sa treaca n starea j la momen-tul n+ 1, stiind ca se afla n starea i la momentul n.

Relatia (10.1) se numeste proprietate markoviana. Proprietatea markoviana ca-racterizeaza lipsa partiala de memorie a lantului: cunoscand succesiunea de stari,s0, s1, . . . , sn1, i, prin care a trecut sistemul pana la momentul n, doar starea prezenta(Xn = i) influenteaza probabilitatea de trecere, n momentul urmator, la o noua stare, nusi drumul parcurs pana la momentul curent n (cu alte cuvinte doar istoria recenta, nu sicea trecuta, influenteaza evolutia viitoare).

1

2In mod normal probabilitatile P (Xn+1 = j|Xn = i) depind n, adica

P (Xn+1 = j|Xn = i) = pij(n)

Un lant Markov discret (Xn) se numeste lant Markov omogen, daca probabilitatile conditionate:

P (Xn+1 = j|Xn = i)

nu depind de n.

Pentru un lant Markov omogen, notam cu pij = P (Xn+1 = j|Xn = i), i, j = 1,mprobabilitatea ca la momentul n + 1 lantul Markov sa treaca n starea j stiind ca lamomentul n se afla n starea i. pij se numeste probabilitate de trecere ntr-un singur pasdin starea i n starea j , iar matricea Q de elemente Q(i, j) := pij, i, j = 1,m, se numestematricea de tranzitie a lantului Markov.

Matricea de tranzitie Q = (pij)i,jS verifica proprietatile:1) pij 0, (i, j) S S2)m

j=1 pij = 1, i S, adica suma elementelor de pe fiecare linie este 1.

O astfel de matrice se numeste matrice stochastica, iar liniile ei, vectori stochastici.Practic (pi1, pi2, . . . , pim), i = 1,m, indica probabilitatile ca din starea i sistemul sa treacarespectiv n starile 1, 2, . . . ,m.453.707 Inverse Problems, G.K. Nicholls, The University of Auckland 7-2

i jP

i j

1

0.4

0.1

0.4

0.4

0.5

0.7

0.1

0.2

0.2

2 3

Figure 7.1 Digraph corresponding to the transition matrix of Example 1.

1. Pick X0 using the initializing distribution Pr (X0 = i) =13 ;13 ;13

. Since we have a = b = c =

13 and u1 = 0:429; we select X0 = 2:

2. We are now in state 2. We must choose a new state by jumping from state 2. Since P2j =15 ;

710 ;

110

; we have a = 15 ; b =

710 and c =

110 : Since u2 = 0:"56 < a; we select X1 = ":

3. We are now in state 1. Iterating, since P1j =25 ;12 ;

110

; we have a = 25 ; b =

12 and c =

110 :

Since u3 = 0:"46 < a; we select X2 = ":

We thus obtain

X0 X1 X2 X3 X4 X5 : : :

2 " " 3 3 2 : : :

which we call a a realization of the chain. By simulating the process we obtain a realization ofthe process. We see from the simulation procedure that the stochastic process satises the Markovcondition: we only used the value of the last state Xn to calculate the distribution forXn+1.

7.1.2 The Distribution of Xn

Consider Pr (Xn = j) ; which is the probability that after a simulation of a Markov chain for nsteps, the state reached is Xn = j: These probabilities may be arranged in a row vector

(n)

where, by denition (n)j = Pr (Xn = j) : When n = "; we see that

Pr (X1 = j) =Xi2!

Pr (X1 = j; X0 = i)

=Xi2!

Pr (X1 = jjX0 = i)Pr (X0 = i) : (7.5)

This may be written in matrix form as

(1)j =

Xi2!

(0)i Pij or

(1) = (0)P: (7.6)

Fig.10.1:

Multimea starilor S, a unui lant Markov si matricea de tranzitie definesc un graf orien-tat ale carui varfuri sunt starile. Exista arc orientat de la starea i la j, daca probabilitateapij este nenula. Graful astfel asociat se numeste graf de tranzitie al lantului Markov.

3Exemplul 1. Fie S = {1, 2, 3} multimea starilor unui sistem si matricea de tranzitie dela o stare la alta definita de:

Q =

0.4 0.5 0.10.2 0.7 0.1

0.4 0.4 0.2

Graful asociat este vizualizat n Fig. 10.1.

Proprietati ale matricilor stochastice Notam cu e vectorul de elemente e = [1, 1, . . . , 1]T . Produsul Qe este:

p11 p12 . . . p1m...pk1 pk2 . . . pkm...

pm1 pm2 . . . pmm

1...1...1

=

p11 + p12 + + p1m...

pk1 + pk2 + + pkm...

pm1 + pm2 + + pmm

=

1...1...1

Aceasta relatie ne permite exprimarea concentrata a proprietatii lui Q de a avea toateliniile vectori stochastici:

Qe = e

In continuare o vom folosi ca relatie definitie a unei matrici stochastice (subantelegandca elementele ei sunt mai mari sau egale cu zero).

Produsul a doua matrici stochastice P,Q, este o matrice stochastica, deoarece Pe =e si Qe = e implica (PQ)e = P (Qe) = Pe = e.

Daca P,Q sunt matrici stochastice si (0, 1) atunci combinatia convexa:

M = P + (1 )Q

este matrice stochastica.

O realizare a lantului Markov (Xn), sau o observatie asupra lantului este un sirde stari posibile, (s0, s1, . . . , sn, . . .), sk S, si se numeste traiectorie a lantului.

Pentru a putea analiza si simula un lant Markov, trebuie precizata distributia initialade probabilitate, 0 = [0(1), 0(2), . . . , 0(m)], cu 0(k) 0 si

mk=1 0(k) = 1, unde

0(k) = P (X0 = k) este probabilitatea ca la momentul t = 0 lantul sa porneasca dinstarea k. Cu alte cuvinte, distributia initiala de probabilitate a lantului Markov estedistributia de probabilitate a variabilei aleatoare discrete X0:

X0 =

(1 2 . . . m

0(1) 0(2) . . . 0(m)

)(10.2)

Daca pentru lantul Markov din Exemplul 1 distributia initiala de probabilitate este:

X0 =

(1 2 30.2 0.5 0.3

)atunci nseamna ca probabilitatea ca un mers (drum) aleator n multimea S = {1, 2, 3}sa porneasca din starea 2 este 0.5.

410.1.1 Simularea unei traiectorii a lantului Markov

Un lant Markov discret este simulat n mod iterativ. Algoritmul de simulare este pro-totip pentru clasa algoritmilor iterativi aleatori. Avand dat spatiul starilor S ={1, 2, . . . ,m}, distributia initiala de probabilitate 0 = [0(1), 0(2), . . . , 0(m)] si ma-tricea de tranzitie a Q = (pij), i, j = 1,m,a unui lant Markov (Xn), putem genera o traiectorie aleatoare s0, s1, . . . , sN , astfel:

construim simulatorul unei variabile aleatoare discrete arbitrare:

Y =

(1 2 . . . mp1 p2 . . . pm

)pe care l notam simbolic

{1, 2, . . . , m;p}

p este vectorul de probabilitate al variabilei aleatoare discrete ce ia valori n {1, 2, . . . ,m}.jR {1, 2, . . . , m;p} simbolizeaza faptul ca simulatorul genereaza o valoare j.

Se genereaza starea initiala s0, din care porneste traiectoria, simuland variabilaaleatoare X0 definita n (10.2).

Probabilitatile de trecere din starea i = s0 n una din starile sistemului sunt date deelementele din linia i a matricii de tranzitie Q = (pij). Astfel starea la momentul t = 1, s1,este valoare de observatie asupra variabilei aleatoare discrete, ce ia valorile {1, 2, . . . ,m}cu probabilitatile din linia i a matricii de tanzitie p = [pi1, pi2, . . . , pm], etc.

Algoritmul de generare a segmentului de traiectorie s0, s1, . . . , sN, este atunci:

s0 R {1, 2, . . . , m;0};j s0;for i=1:N {p [linia j din matricea Q];si R {1, 2, . . . , m; p};j si;}return s0, s1, . . . , sNVizualizarea traiectoriei unui lant Markov se face astfel: se marcheaza n plan

punctele de coordonate (i, si) si se unesc punctele consecutive (i, si), (i+ 1, si+1).In Fig. 10.2 este vizualizata o traiectorie de lungime 100 a lantului Markov cu 3

stari, avand matricea de tranzitie din Exemplul 1 si distributia initiala de probabilitate,distributia uniforma.

In concluzie, un lant Markov discret defineste o lege de evolutie la ntamplare pemultimea starilor.

10.2 Analiza unui lant Markov

Pe langa tranzitia ntr-un singur pas a unui lant Markov, suntem interesati si de tranzitiadintr-o stare n alta, n n pasi. Notam cu:

P nij = P (Xn = j|X0 = i), i, j S,

520 40 60 80 1000

0.5

1

1.5

2

2.5

3

3.5

Fig.10.2:

probabilitatea ca sistemul sa treaca din starea initiala i n starea j la momentul n sau dupan pasi. Se demonstreaza ca matricea de tranzitie n n pasi, adica matricea de elementeP nij, este chiar Q

n matricea de tranzitie ntr-un pas, ridicata la puterea n.Pentru a putea face predictii asupra evolutiei sistemului sa calculam cateva proba-

bilitati ale unor evenimente de interes. Si anume calculam probabilitatea ca sistemul saevolueze pe traiectoria s0, s1, . . . , sn:

P (X0 = s0, X1 = s1, . . . Xn1 = sn1, Xn = sn) =

P (X0 = s0, X1 = s1, . . .Xn1 = sn1, Xn = sn)

P (X0 = s0, X1 = s1, . . . Xn1 = sn1)

P (X0 = s0, X1 = s1, . . .Xn1 = sn1)

P (X0 = s0, X1 = s1, . . .Xn2 = sn2)

P (X0 = s0, X1 = s1, X2 = s2)

P (X0 = s0, X1 = s1)

P (X0 = s0, X1 = s1)

P (X0 = s0) P (X0 = s0)

(10.3)

Din definitia probabilitatii conditionate P (A|B) =P (A B)

P (B), si a proprietatii markoviene

(10.1) rezulta ca fractiile de mai sus, n ordinea de la dreapta spre stanga, conduc la:

P (X0 = s0, X1 = s1, . . . Xn1 = sn1, Xn = sn) =pi0(s0) P (X1 = s1|X0 = s0) P (X2 = s2|X0 = s0, X1 = s1) P (Xn = sn|X0 = s0, X1 = s1 . . . Xn1 = sn1) =pi0(s0)P (X1 = s1|X0 = s0) P (X2 = s2|X1 = s1) P (Xn = sn|Xn1 = sn1) =pi0(s0)Q(s0, s1) . . . Q(sn1, sn)

(10.4)

Deci, probabilitatea ca lantul sa admita segmentul de traiectorie s0, s1, . . . , sneste:

P(X0 = s0,X1 = s1, . . .Xn1 = sn1,Xn = sn) = pi0(s0)Q(s0, s1) . . . Q(sn1, sn). (10.5)

6Exemplul 2. Consideram lantul Markov din exemplul 1, avand distributia initiala deprobabilitate 0 = [0.2, 0.35, 0.45]. Sa se calculeze probabilitatea ca lantul sa evolueze dinstarea s0 = 2, n starea s11 = 3 pe traiectoria: 2, 1, 3, 2, 1, 2, 3, 1, 3, 2, 1, 3.

Conform formulei deduse probabilitatea ca lantul sa aiba traiectoria 2, 1, 3, 2, 1, 2, 3, 1, 3, 2, 1, 3este P = 0(2)Q(2, 1)Q(1, 3)Q(3, 2)Q(2, 1)Q(1, 2)Q(2, 3)Q(3, 1)Q(1, 3)Q(3, 2)Q(2, 1)Q(1, 3).Calculul numeric al acestui produs conduce la: P (X0 = 2, X1 = 1, X2 = 3, X3 = 2, X4 =1, X5 = 2, X6 = 3, X7 = 1, X8 = 3, X9 = 2, X10 = 1, X11 = 3) = 8.9600000000e 09.

10.2.1 Determinarea distributiei de probabilitate n a variabilei de stare Xn,la momentul n

In definitia lantului Markov (Xn) nu se precizeaza si distributia de probabilitate a vari-abilei aleatoare de stare Xn. Variabila aleatoare Xn ia valorile {1, 2, . . . ,m} si evenimen-tul (Xn = j) este evenimentul ca la momentul n traiectoria aleatoare sa ajunga n stareaj S.

Vom arata ca daca se cunoaste distributia initiala de probabilitate 0 si matricea detranzitie Q a lantului Markov (Xn) atunci putem determina si distributia de probabilitaten = [n(1), n(2), . . . , n(m)] a variabilei aleatore Xn, n > 0. Precizam ca n(j) =P (Xn = j).

Propozitia 10.2.1 Distributia de probabilitate a starii la momentul n este:

n = 0Qn

sau detaliat: [n(1) n(2) . . . n(m)

]=[0(1) 0(2) . . . 0(m)

]Q

Demonstratie: Notam cu B evenimentul (Xn = j) si cu Ai = (X0 = i), i = 1, 2, . . . ,m.Evident ca A1, A2, . . . , Am constituie o o descompunere a evenimentului sigur n m eveni-mente mutual exclusive doua cate doua. Conform formulei probabilitatii totale avem:

P (B) =ni=1

P (Ai)PAi(B) (10.6)

Rescriem formula probabilitatii totale nlocuind B cu (Xn = j) si Ai cu (X0 = i):

P (Xn = j) =mi=1

P (X0 = i)P (Xn = j|X0 = i), (10.7)

adica

P (Xn = j) =mi=1

0(i)Pnij =

mi=1

0(i)Qn(i, j). (10.8)

7Rezulta astfel ca:

n(j) =mi=1

0(i)Qn(i, j), (10.9)

ceea ce ne conduce la relatia matriciala:

[ n(1) n(2) . . . n(m) ] = [ 0(1) 0(2) . . . 0(m) ]Qn (10.10)

sau concentratn = 0Q

n (10.11)

Din relatia (10.10) rezulta ca distributia de probabilitate a starii la momentul n, Xnse poate calcula recursiv pornind de la distributia initiala 0:

1 = 0Q

2 = 0Q2 = 1Q

...

n = n1Q (10.12)

Aceasta metoda se recomanda pentru calculul numeric al distributiei de probabilitate na starii n.

Exemplul 3. Pentru lantul Markov din Exemplul 1 avand distributia initiala de prob-abilitate 0 = [0.2, 0.35, 0.45] distributiile de probabilitate ale starilor pana la momentuln = 100, X1, X2, . . . , X100, calculate conform relatiei de recurenta de mai sus, sunt:

1 = [0.330000000000.5250000000000.145000000000];2 = [0.295000000000.5905000000000.114500000000];3 = [0.281900000000.6066500000000.111450000000];4 = [0.278670000000.6101850000000.111145000000];5 = [0.277963000000.6109225000000.111114500000];6 = [0.277815500000.6110730500000.111111450000];7 = [0.277785390000.6111034650000.111111145000];8 = [0.277779307000.6111095785000.111111114500];9 = [0.277778084300.6111108042500.111111111450];10 = [0.277777839150.6111110497050.111111111145];

Pentru variabilele aleatoare X50, . . . , X100 obtinem cu 15 zecimale, distributia de prob-abilitate :

50 = 51 = = 100 = [0.277777777778, 0.611111111111, 0.111111111111]

Observam ca P (X50 = k) = = P (X100 = k), k = 1, 2, 3. Aceste egalitati au locpentru trunchierea la 15 zecimale. Orice distributie de probabilitate n, cu n 50, amcalcula cu 15 zecimale, am obtine toate distributiile identice.

In continuare interpretam semnificatia acestui comportamnet.

810.2.2 Distributie de echilibru a unui lant Markov

Faptul ca ncepand de la n = 50 distributiile de probabilitate trunchiate la 15 zecimalecoincid, adica, de exemplu, 50 = 51 si 51 = 50Q, implica notand ambele distributii cu ca = Q.

Definitia 10.2.1 O distributie de probabilitate , pe spatiul starilor unui lant Markovcu proprietatea ca = Q, unde Q este matricea de tranzitie a lantului, se numestedistributie invarianta sau stationara sau nca distributie de echilibru.

Se poate verifica ca daca sirul (n) al distributiilor de stare este convergent, atunci limitasa este un vector probabilist , adica un vector de coordonate 0 si suma coordonateloreste 1.

Interpretarea distributiei stationare: Daca la un moment dat n, n = , atuncidin n+1 = nQ = Q = , rezulta ca n orice moment n+ k, k 1, ulterior lui n, lantulva avea aceeasi distributie de probabilitate a starilor, n+k = , adica dupa momentul ndistributia este stationara, nu se mai modifica si deci sistemul a ajuns ntr-un echilibru.De-a lungul oricarei traiectorii, sn, sn+1, . . . sn+N , de orice lungime N+1, starea 1 estevizitata de lantul Markov n proportie de 100(1)%, starea 2 de 100(2)%, . . . , staream n proportie de 100(m)%.

In continuare evidentiem conditii care asigura ca lantul Markov admite distributiede echilibru, iar apoi precizam cand astfel de conditii sunt ndeplinite.

Propozitia 10.2.2 Daca sirul n converge la , atunci este distributie de echilibru alantului Markov.

Demonstratie: Daca limn n = atunci si limn n1 = . Trecand la limita candn n relatia:

n = n1Q

obtinem:

= Q,

adica este distributie de echilibru a lantului Markov.

Observatia 10.2.1 Sirul (n) fiind construit recursiv, pornind de la distributia initiala0, n = 0Q n = n1Q, este evident ca n general fiecare distributie initiala conducela un alt sir (n) si daca acesta este convergent, la alta limita . Cu alte cuvinte un lantMarkov poate admite mai multe distributii invariante.

Propozitia 10.2.3 Daca sirul n converge la , indiferent de distributia initiala de prob-abilitate, 0, atunci sirul de matrici (Q

n) converge la o matrice care are pe fiecare liniecoordonatele vectorului probabilist .

9Demonstratie: Avem relatian = 0Q

n

Deoarece n , oricare ar fi 0, n particular n si pentru 0 = [0, 0, . . . , 1k

, . . . , 0, 0].

In acest caz,

0Qn =

[0, 0, . . . , 1

k

, . . . , 0, 0

]

q11 q12 . . . q1m...qk1 qk2 . . . qkm...

qm1 qm2 . . . qmm

= [ qk1 qk2 . . . qkm ]

linia k din Qn

Prin urmare n = [ qk1 qk2 . . . qkm ]. Trecand la limita cand n obtinem ca liniak din matricea Qn tinde la (deoarece n ). Cum k a fost ales arbitrar, rezulta catoate liniile din Qn tind la = [(1), (2), . . . , (n)]. Prin urmare

Qn

...

(1) (2) . . . (n)(1) (2) . . . (n)...

(1) (2) . . . (n)

Propozitia precedenta are o ipoteza greu de ndeplinit la prima vedere, adica indiferent dedistributia initiala 0, cerem ca sirul corespunzator (n), cu n = 0Q, sa fie convergent sisa aiba aceeasi limita . Vom arata n continuare ca exista lanturi Markov care au aceastaproprietate si mai mult ca pe multimea tuturor paginilor WEB, ca spatiul al starilor, sepoate defini un lant Markov (ale carui traiectorii sunt traiectoriile unui navigator peWWW), ce are o distributie de echilibru.

Exemplul 4. In Exemplul 3 am ilustrat ca distributiile de probabilitate n tind la =[0.277777777778, 0.611111111111, 0.111111111111] pentru o anumita distributie initiala.Prin experimente numerice se poate vedea ca limita este aceeasi orice distributie initialaam lua lua (aici facem abuz de limbaj: ceea ce numim limita este n realitate o aproximatiea ei, adica un N cu proprietatea ca ||N || < ).

Calculand Qn, pentru n = 100 obtinem:

Q100 =

0.277777777778 0.611111111111 0.1111111111110.277777777778 0.611111111111 0.111111111111

0.277777777778 0.611111111111 0.111111111111

Remarcam ca pe fiecare linie a matricii Q100 avem coordonatele vectorului probabilist50 = = 100 = , ce pare sa fie distributia de echilibru a lantului Markov considerat.

Sa evidentiem acum conditiile pe care trebuie sa le ndeplineasca matricea de tranzitieQ a unui lant Markov, pentru ca pentru orice distributie initiala de probabilitate a starilor,0, sirul (n) asociat sa fie convergent si sa aiba aceeasi limita .

10

10.2.3 Lanturi Markov ireductibile

Fie S = {1, 2, . . . ,m} spatiul starilor unui lant Markov. Definim pe S o relatie deechivalenta: starea i intercomunica cu starea j daca probabilitatea de tranzitie de lai la j ntr-un numar de pasi este pozitiva, la fel ca si probabilitatea de tranzitie de la jla i, adica exista n > 0 si k > 0, astfel ncat Qn(i, j) > 0 si Qk(j, i) > 0. Notam aceastarelatie prin:

i j

Clasa de echivalenta a unei stari, notata C(i), este formata din multimea starilor cu carei intercomunica.

Un lant Markov cu o singura clasa este lant ireductibil, adica oricare doua stariintercomunica.

Daca matricea de tranzitie are toate elementele Q(i, j) > 0, i, j 1,m, atunci lantulMarkov este ireductibil. Daca exista un n > 1 astfel ncatQn(i, j) > 0, i, j 1,m, lantulMarkov este de asemenea ireductibil (conditia precedenta corespunde cazului n = 1).

Exemplul 5. Lantul Markov avand spatiul starilor S = {1, 2, 3, 4} si matricea detranzitie:

Q =

0.3 0.7 0 00.45 0.55 0 00 0 0.6 0.40 0 0.2 0.8

nu este un lant ireductibil, asa cum se poate observa mai simplu din graful asociat.Multimile de stari {1, 2} si {3, 4} nu comunica ntre ele.

Observatia 10.2.2 Simplul fapt ca Q(i, j) = 0 nu asigura ca i nu comunica cu j. Celedoua stari nu comunica ntr-un pas, dar pot comunica n mai multi pasi, adica s-ar putea

ca Qn(i, j) > 0, pentru un n > 1.

Un lant Markov poate avea si traiectorii periodice (Fig.10.3).

1

3

4

2

Fig.10.3: Graful asociat unui lant Markov ce are traiectoria (1,3,4) periodica

11

Din analiza grafului din figura rezulta ca probabilitatile Q3(1, 1) > 0, Q6(1, 1) > 0 sin general Q3k(1, 1) > 0, ceea ce ilustreaza ca, cu o probabilitate pozitiva, o traiectorie ceporneste din 1 se rentoarce n 1 dupa 3, pasi, 6 pasi, sau mai general un multiplu de 3pasi. Aceasta proprietate indica ca traiectoria ce porneste din 1 este periodica. Analogpentru 3 si 4.

Definitia 10.2.2 Perioada unei stari i, este numarul

i = c.m.m.d.c{n N |Qn(i, i) > 0}

In cazul exemplului nostru cel mai mare divizor comun al numerelor de forma 3k, k Neste 3, deci starea 1 este periodica de perioada 3, si analog starile 3 si 4.

O stare i a carei perioada este 1 se numeste stare aperiodica, iar un lant Markovcare are toate starile aperiodice se numeste lant Markov aperiodic.

Evident ca daca matricea de tranzitie are toate elementele de pe diagonala principalastrict pozitive, Q(i, i) > 0, atunci lantul este aperiodic.

Remarcam ca proprietatile de ireductibilitate si aperiodicitate ale unui lant Markovsunt proprietati ale matricii de tranzitie.

Se poate demonstra urmatoarea proprietate:Toate starile dintr-o clasa de echivalenta, relativ la relatia de intercomunicare, au

aceeasi perioada.

Un lant Markov n timp discret, ireductibil are toate starile de aceeasi perioada d.Prin urmare daca o stare a unui lant ireductibil este aperiodica, atunci toate starile suntaperiodice. Astfel pentru a arata ca un lant ireductibil este aperiodic este suficient saidentificam o stare i pentru care Q(i, i) > 0 (probabilitatea de trecere de la starea i la eansasi este nenula), pentru a concluziona ca starea i este aperiodica si deci toate starilelantului sunt aperiodice.

Dupa aceasta clasificare a starilor unui lant Markov sa caracterizam lanturile Markovireductibile si aperiodice.

Teorema 10.2.1 Daca un lant Markov cu o multime finita de stari S este ireductibil siaperiodic, atunci el admite o unica distributie de echilibru si sirul (n) al distributiilorde stare la momentul n este convergent oricare ar fi distributia initiala 0.

Conform propozitiilor 10.2.2, 10.2.2, limita sirului (n) este distributia de echilibru sisirul (Qn) este convergent, limita sa fiind matricea ale carei linii coincid toate cu vectorulprobabilist .

Aceasta teorema sta la baza algoritmului PageRank pe care se bazeaza motorul decautare Google.

10.2.4 Algoritm de determinare a distributiei invariante a unui lant Markovireductibil si aperiodic

Presupunem ca lantul Markov definit pe spatiul starilor S, |S| = m, are matricea Qireductibila si aperiodica. Conform Teoremei 10.2.1, lantul are o unica distributie de

12

echilibru = ((1), (2), . . . , (n)), adica:

= Q si(j) 0,

mj=1 (j) = 1

(10.13)

Prima conditie scrisa detaliat:

[ (1) (2) . . . (m) ] = [ (1) (2) . . . (m) ]Q

este echivalenta (aplicand transpunerea ambilor membri ai egalitatii) cu:

QT

(1)(1)...(m)

=

(1)(1)...(m)

ceea ce nseamna ca vectorul Rm este vector propriu al transformarii liniare de matriceQT corespunzator valorii proprii 1, pentru ca QT = 1 .

Teorema din algebra liniara cunoscuta ca teorema lui PerronFrobenius afirmaca transpusa matricii de tranzitie a unui lant Markov ireductibil si aperiodic admite pe1 ca valoare proprie, cu ordinul de multiplicitate 1 si subspatiul propriu corespunzatoreste generat de un vector v = (x1, x2, . . . , xm) avand toate coordonatele strict pozitive.Evident ca si v este vector propriu corespunzator valorii proprii 1, pentru ca QT (v) =QT (v) = 1 v = 1 (v).

Rezulta astfel urmatorul algoritm de determinare a distributiei invariante a unui lantMarkov ireductibil si aperiodic:

se determina un vector propriu, v = (x1, x2, . . . , xm), corespunzator valo-rii proprii 1 a matricii QT;

se calculeaza suma coordonatelor r = x1 + x2 + + xm; vectorul = v/r = (x1/r, x2/r, . . . , xm/r) reprezinta distributia de echilibru

a lantului Markov.

Precizam ca conform teoremei Frobenius un vector propriu corespunzator valorii pro-prii 1 are fie toate coordonatele strict pozitive, fie toate strict negative. Deci v/r are sigurcoordonatele pozitive si mai mult este un vector probabilist.

10.3 Algoritmul PageRankGoogle

Google este un motor de cautare foarte performant datorita algoritmului PageRank, dez-voltat de fondatorii Google, Larry Page si Sergei Brin, n 1998, cand nca erau studentila Stanford. Ei au exploatat ideea mersului aleator definit de un lant Markov n scopulierarhizarii paginilor WEB n ordinea descrescatoare a unui indice numit rangul paginii(PageRank). PageRank este distributia de echilibru a unui lant Markov definit pespatiul starilor ce consta din toate paginile WEB. Aceasta distributie de probabilitateeste calculata o data pe luna.

13

Sa definim mai precis lantul Markov ce sta la baza algoritmului PageRank. Fie W ={1, 2, . . . ,m} multimea tuturor paginilor WEB, H = (hij) matricea de conectivitate a luiW , sau matricea hyperlink:

hij =

{1 daca exista hyperlink n pagina i catre pagina j0 daca nu exista hyperlink n pagina i catre pagina j

H este o matrice sparse, adica cu foarte multe zerouri (n medie cu 3-10 elemente nenulepe o linie). Suma elementelor de pe o linie a matricii hyperlink, ri =

mj=1 hij indica

numarul de hyperlink-uri din pagina i. ri se numeste outdegree (gradul, ordinul iesirilordin pagina) al paginii i. L. Page si S. Brin au considerat ca un surfer ajuns n pagina ialege cu aceeasi probabilitate oricare din paginile catre care pagina i are link-uri, adicaprobabilitatea de trecere de la pagina i la pagina j este pij = hij/ri. De exemplu daca

H =

0 0 1 1 0 0 1 0 0 11 0 0 0 1 0 0 1 0 0...

...0 0 1 0 0 1 0 1 0 0

atunci ordinul de iesire din pagina 2 este r2 = 3 si deci probabilitatea de a trece din pagina2 n oricare din paginile {1, 2, . . . , 10} este p2j = h2j/3, adica cu aceeasi probabilitate de1/3, un surfer poate trece din pagina 2 n pagina 1, 5 sau 8.

Vom exemplifica constructia propusa de L. Page si S. Brin prin modelul simplu deretea izolata de pagini WEB (retea intranet), din Fig.10.4. Notam cu Q = (pij) matriceaprobabilitatilor de tranzitie pij = hij/ri, i, j = 1, 6. Se observa din structura grafului deconectivitate ca paginile 1 si 4 sunt pagini ce nu contin link-uri catre alte pagini. Acestease numesc dangling pages. De exemplu fisierele pdf, ps sau fisierele imagine suntpagini dangling. Prin urmare liniile 1 si 4 din matricea de tranzitie au toate elementelenule si astfel Q nu este o matrice stochastica, deci nu poate fi interpretata ca matricea detranzitie a unui lant Markov cu spatiul starilor {1, 2, 3, 4, 5, 6}. Pentru a remedia aceastasituatie, L. Page si S. Brin au propus ca vector de probabilitate de tranzitie dintr-opagina dangling, i, distributia uniforma pij = 1/m, , j = 1,m. Adica, n mod artificial seadauga link-uri dintr-o pagina dangling catre toate paginilie WEB sau echivalent, ajunsntr-o pagina dangling, un navigator poate apoi alege cu o probabilitate uniforma oricepagina din WWW.

Q=

1 2 3 4 5 61 0 0 0 0 0 02 0 0 0 0 1/2 1/23 0 1/4 0 1/4 1/4 1/44 0 0 0 0 0 05 1/2 0 0 0 0 1/26 1/3 0 1/3 1/3 0 0

Matricea stochastica obtinuta din matricea Q este:

14

P1 P2

P3

P4

P5

P6

Fig.10.4: Graf orientat ilustrand link-urile din 6 pagini WEB ce constituie o retea izolata.

Q1=

1 2 3 4 5 61 1/6 1/6 1/6 1/6 1/6 1/62 0 0 0 0 1/2 1/23 0 1/4 0 1/4 1/4 1/44 1/6 1/6 1/6 1/6 1/6 1/65 1/2 0 0 0 0 1/26 1/3 0 1/3 1/3 0 0

Matricea Q1 astfel obtinuta se exprima astfel:

Q1 = Q+ avT

unde a = [a1, a2, . . . , am]T , cu

ai =

{1 daca i este o dangling page0 n rest

,

iar v = [1/m, 1/m, . . . 1/m]T

Lantul Markov avand matricea Q1 poate sa nu fie ireductibil ( adica pornind dintr-opagina nu se poate ajunge n orice alta pagina n mersul aleator definit de matricea Q1)sau navigand pe WWW conform matricii de tranzitie Q1 un surfer poate intra ntr-unciclu infinit pentru ca matricea Q1 poate conduce la traiectorii periodice. Din aceastacauza, dar si pentru ca pentru ca uneori surferul se plictiseste sa urmeze link-uri, seconsidera ca doar cu probabilitatea (0, 1) (prescrisa), un navigator ajuns n pagina ialege uniform una din paginile catre care pagina i are hyperlink-uri si cu probabilitateacomplementara 1 ignora hyperlink-urile si alege uniform oricare din cele m paginidin WWW (inserand o adresa URL n linia de comanda a browser-ului). se numestedamping factor. Astfel matricea de tranzitie devine:

15

G = Q1 + (1 )

1/m 1/m . . . 1/m1/m 1/m . . . 1/m...1/m 1/m . . . 1/m

(10.14)

Matricea G se numeste la ora actuala matricea Google, iar matricea stochastica detip m m si elemente identice, (1/m) se numeste matricea de teleportare, deoarecedatorita ei surferul se teleporteaza din mersul urmand link-uri.

Matricea Google se exprima concentrat astfel:

G = (Q+ avT ) + (1 )evT . (10.15)

Aceasta modalitate de exprimare permite o stocare redusa a ei. Se crede ca la ora actualamatricea Google este cea mai uriasa matrice cu care se opereaza n vreo aplicatie (areaproximativ 9 miliarde linii si 9 miliarde coloane!)

Lantul Markov avand spatiul starilor constituit din: multimea paginilor WEB la un moment dat, de cardinal m, matricea de tranzitie de tipul G cu fixat, si distributia initiala de probabilitate 0, distributia uniforma,este un lant ireductibil si aperiodic, deci are o unica distributie de echilibru , numita

vectorul PageRank.Deoarece matricea Google, G, este o matrice patratica de tip m m, cu m > 9

miliarde, distributia de echilibru se calculeaza numeric folosind asa numita metoda aputerii, ca limita a sirului n = 0G

n a distributiilor de probabilitate la momentul n:

0 [1/m, 1/m, . . . , 1/m];eps 107;do { 0;0 G;} while(0 > eps);return 0;

Cum n = 0Gn, se considera ca metoda puterii a atins stadiul de convergenta ntr-o

etapa n n care n n1 < .Se demonstreaza ca rata de convergenta a sirului (n) este rata cu care

k 0,unde este probabilitatea din definita matricii Google G. In primul raport tehnic algrupului Page-Brin, era 0.85. La ora actuala nu se cunoaste daca Google folosesteacelasi parametru sau nu.

Interpretarea vectorului PageRank . Vectorul Pagerank este distributia deechilibru a lantului Markov ce modeleaza navigarea aleatoare prin WWW. Cum el esteun vector de probabilitate, deci are coordonate subunitare, coordonata j reprezintaproportia din timpul de navigare pe care surferul ar petrece-o vizitand pagina j. Prinurmare j este votul, nota acordata paginii j sau n limbaj de WWW, j este o masura a

16

autoritatii paginii j. La o cerere particulara (concretizata n cuvantul/cuvinte de cautare)din partea unui navigator, Google cauta paginile ce contin cuvintele cheie si apoi le listeazan ordinea descrescatoare a PageRank-ului lor.

Se pare ca Google afiseaza n Google toolbar drept Pagerank al paginii j (vizitate),

10*j, deoarece coeficientii j fiind numere subunitare si

9109

j=1 j = 1, chiar si petrupaginile cu autoritate mare j este un numar subunitar suficient de mic. Pagerank-ulunei pagini j este o masura globala a autoritatii ei, care este influentata doar de numarulde inlink-uri ale paginii respective si de autoritatea paginilor care au link spre pagina j, nusi de numarul de outlink-uri (care poate fi controlat de designerul paginii). Pagerank-uleste query independent si depinde doar de structura link-urilor. Google are implementatsi un detector de spamlinks, care ar forta cresterea PageRank-ului anumitor pagini.

10.4 Modele de lanturi Markov si Probleme

1. . Lant Markov ce modeleaza schimbarile n volumul traficului ntr-o reteainternet. Se monitorizeaza o lunga perioada volumul V al traficului n retea, masuratn Mbiti/secunda si se constata ca exista trei nivele: volum redus, codificat cu L, volummediu, codificat M , si volum mare, cod H. Pentru fiecare nivel, volumul V este cuprinsntre doua limite bine precizare si intervalele pentru L,M,H sunt adiacente. Mai mult,trecerea de la o stare la alta are probabilitatile probabilitatile:

Q =

0 3/4 1/41/3 0 2/3

0 1 0

(10.16)

Observam urmatoarea caracteristica: de la volum mare, traficul trece mereu la unul mediu(probabilitatea p32 = 1).

Daca la momentul n = 0 ncepe monitorizarea volumului traficului, si se constata caV0 = M , care este probabilitatea ca V5 = R? Dar probabilitatea sa avem (V0 = M,V1 =R, V2 = M,V3 = H,V4 = M,V5 = R)? Calculati aceste probabilitati scriind codul Cadecvat.

Admite acest lant Markov o distributie de echilibru? Ce interpretare dati acesteidistributii?

2. Un lant Markov cu 2 stari {1, 2}, are matricea de tranzitie:

Q =

(0.8 0.20.4 0.6

)

a) Sa se calculeze P (X5 = 2|X0 = 1, X1 = 2, X2 = 2, X3 = 2, X4 = 1).b) Determinati distributia de probabilitate a starilor la momentul n = 3 si calculatistiind ca distributia initiala de probabilitate este distributia uniforma pe spatiul starilor.Deduceti si P (X3 = 1|X0 = 1),

17

c) Sa se argumenteze ca lantul este ireductibil si aperiodic si sa se determine algebric,distributia de echilibru a lantului.

Rezolvare: a) Datorita lipsei partiale de memorie, P (X5 = 2|X0 = 1, X1 = 2, X2 =2, X3 = 2, X4 = 1) = P (X5 = 2|X4 = 1) = Q(1, 2) = 0.2.

Distributia de probabilitate a starilor la momentul n = 3 este distributia de probabil-itate a variabilei aleatore X3, adica 3. Stiind ca n = 0Q

n, avem ca 3 = 0Q3, unde

0 = [1/2, 1/2]. Deci:[ 3(1) 3(2) ] =

[1/2 1/2

]Q3

P (X3 = 1|X0 = 1) fiind probabilitatea trecerii n 3 pasi de la starea 1 la starea 1, avemca:

P (X3 = 1|X0 = 1) = Q3(1, 1)

c) Lantul este ireductibil deoarece Q(1, 2) > 0 si Q(2, 1) > 0. Fiind ireductibil estesuficient sa aratam ca o singura stare este aperiodica (daca o stare a unui lant ireductibileste aperiodica, atunci toate starile sunt aperiodice). Cum Q(1, 1) = 0.8 > 0 rezulta castarea 1 este aperiodica.

Distributia de echilibru a unui lant ireductibil si aperiodic este vector propriu core-spunzator valorii proprii 1 a matricii Q , deoarece:

Q = , adica [1 2]

(Q(1, 1) Q(1, 2)Q(2, 1) Q(2, 2)

)= [1 2]

este echivalent cu Q = :(Q(1, 1) Q(2, 1)Q(1, 2) Q(2, 2)

)[12

]=

[12

]

Un vector propriu corespunzator valorii proprii 1 se determina ca o solutie nebanalaa sistemului:

(Q I2)

[xy

]=

[00

]adica: (

0.8 1 0.40.2 0.6 1

)[xy

]=

[00

]sau (

0.2 0.40.2 0.4

)[xy

]=

[00

]Alegand y = ca necunoscuta secundara avem x = 2 si deci vectorul propriu

v = (2, 1). Cum distributia de echilibru este un vector probabilist, adica un vector decoordonate din [0, 1] si cu suma coordonatelor egala cu 1, luam = (2/s, 1/s) undes = 2 + 1, suma coordonatelor vectorului v. Prin urmare = (2/3, 1/3).

3. Un lant Markov cu doua stari {1, 2} are matricea de tranzitie:

18

Q =

(0.8 0.20.3 0.7

)Sa se calculeze urmatoarele probabilitati:

i) P (X5 = 2|X4 = 1, X3 = 1);ii) P (X3 = 2|X1 = 1);iii) P (X2 = 1, X1 6= 1|X0 = 2);Rezolvare: i) Trecerea unui lant Markov la starea din momentul n + 1 nu depinde

de starile prin care lantul a trecut n momentele 0, 1, 2, . . . , n 1, ci doar de starea lamomentul n. Prin urmare P (X5 = 2|X4 = 1, X3 = 1) = P (X5 = 2|X4 = 1) = Q(1, 2) =0.2.

ii) Deoarece se cere probabilitatea trecerii n doi pasi din starea 1 n starea 2, avem caP (X3 = 2|X1 = 1) = Q

2(1, 2). Sau folosind definitia probabilitatii conditionate avem:

P (X3 = 2|X1 = 1) =P (X1 = 1 X3 = 2)

P (X1 = 1)=P (X1 = 1, X3 = 2)

P (X1 = 1)

Evenimentul (X1 = 1, X3 = 2) = (X1 = 1, X2 = 1, X3 = 2) (X1 = 1, X2 = 2, X3 = 2) sideci:

P (X1 = 1, X3 = 2) = P (X1 = 1, X2 = 1, X3 = 2) + (X1 = 1, X2 = 2, X3 = 2) == 1(1)Q(1, 1)Q(1, 2) + 1(1)Q(1, 2)Q(2, 2) == 1(1)(Q(1, 1)Q(1, 2) +Q(1, 2)Q(2, 2)) = 1(1)Q

2(1, 2)

Astfel avem:

P (X3 = 2|X1 = 1) =1(1)Q

2(1, 2)

P (X1 = 1)=1(1)Q

2(1, 2)

1(1)= Q2(1, 2)

iii)

P (X2 = 1, X1 6= 1|X0 = 2) = P (X2 = 1, X1 = 2|X0 = 2) =P (X2 = 1, X1 = 2, X0 = 2)

P (X0 = 2)=

=P (X0 = 2, X1 = 2, X2 = 1)

P (X0 = 2)=0(2)Q(2, 2)Q(2, 1)

0(2)=

= Q(2, 2)Q(2, 1) = (0.7)(0.3)

4. Un lant Markov cu starile S = {0, 1, 2, 3, 4, 5, 6} are graful din Fig.10.5: Sa sedetermine din graful asociat urmatoarele probabilitati:

P (X7 = 4|X0 = 2, X1 = 5, X2 = 1, X3 = 2, X4 = 6, X5 = 3, X6 = 2), P (X10 = 6|X8 = 2)

P (X4 = 3, X3 = 1|X2 = 5)

5. In figura Fig. 10.6 este reprezentata o retea nchisa de cozi. Acest tip de retea estecunoscut ca modelul server central si se foloseste pentru a studia performanta sistemului.

19

2 Homework Exercise 6 April 8, 1997

Analysis

[45] g with state space

f

1/7 2/9

3/8 5/61/2

4/7

1/5

1/41/3

1/2

0 1 21/8 1/4

1/6

2/31/5

7/92/7 3/5

5 6

43

A. Give the transition probability matrix for X.

B. Let

i

, for 0 i 6, be the limiting probability that X is in state i. Give a complete

system of equations that these limiting probabilities must satisfy.

C. Solve the system of equations in part B for the limiting probabilities. Use Mathe-

matica to do the actual computations and include the Mathematica dialog in your

solution.

D. Assume that X begins in state 0 at time 0; that is, assume that X

0

= 0. What is

P [X

2

= 4]? What is P [X

3

= 2]? Explain.

Fig.10.5:

Fiecare job solicita serviciul CPU si dupa servire, cu probabilitatea p0 solicita un nouserviciu CPU, iar cu probabilitatea pi, i = 1,m, un serviciu de intrareiesire de la unitateai, din celem unitati I/O existente n retea. Suma probabilitatilor este 1, p0+p1+ +pm =1. Dupa operatiile I/O, orice job se rentoarce cu probabilitatea 1, adica sigur, la CPU.

Joburile care circula n reteaua nchisa se numesc job-uri active Traiectoria unui pro-gram (job) prin retea poate fi modelata ca un lant Markov n timp discret, cu spatiulstarilor {0, 1, 2, 3, . . . ,m}. Sa se scrie matricea de tranzitie a acestui lant Markov si sa searate ca daca probabilitatile pi sunt strict ntre 0 si 1, lantul Markov este ireductibil siaperiodic, deci admite o unica distributie de echilibru = [0, 1, . . . , m]. Determinatiaceasta distributie de probabilitate prin metoda algebrica (ca vector propriu al matricii

Un algoritmo di Metropolis per una rete di ode hiusa

I/O 1

I/O m

CPU

0

1

p

p p0m

1

m

Figura 1: Modello di elaboratore entralizzato

Applihiamo ora l'algoritmo di Metropolis a una rete di ode hiusa. La gura 1 rappresenta

un omputer he puo mantenere in memoria un numero massimo r di lavori attivi. Un singolo

lavoro viene elaborato dalla CPU dopodihe termina on probabilita p

0

, oppure viene inviato

(on probabilita p

i

, i = 1; : : : ;m) ad uno di m anali input/output (I/O) per poi ria

odarsi alla

CPU. Se l'arrivo dei lavori dall'esterno e molto frequente, possiamo assumere he il omputer

lavori sempre alla sua apaita massima, quindi he, appena terminato un lavoro, ne entri

subito un altro, osi

he i sono sempre r lavori attivi. La durata di elaborazione alla CPU ha

distribuzione esponenziale on media

0

, quella alle stazioni I/O on media

i

, i = 1; : : : ;m.

Sia x = (x

0

; x

1

; : : : ; x

m

) il numero di lavori in iasuna stazione, tra quelli in oda e quello he

sta venendo eseguito. Puo essere utile determinare il numero atteso di lavori in iasuna stazione

nel lungo periodo, ad esempio per vedere in quale stazione puo essere neessario diminuire il

tempo di elaborazione. Si puo dimostrare (Trivedi, 1982) he la distribuzione di X si fattorizza

ome segue:

p(x

0

; x

1

; : : : ; x

m

) =

1

Z

m

Y

i=0

i

i

x

i

=

h(x)

Z

;

X

i

x

i

= r ;

dove i parametri (

0

; : : : ;

m

) sono la soluzione del sistema lineare

[

0

1

m

= [

0

1

m

2

6

6

6

4

p

0

p

1

p

n

1 0 0

.

.

.

.

.

.

.

.

.

1 0 0

3

7

7

7

5

1

Fig.10.6: Model de retea nchisa de cozi.

20

Q ). Coordona a i-a a acestei distributii de echilibru reprezinta numarul mediu de viziteale unui program tipic la serverul i al sistemului, i = 0,m.

6. Pipelining este o tehnica folosita de microprocesoare, ce consta n executia uneiinstructiuni nainte ca prima (precedenta) sa fie completa. Adica exista simultan catevainstructiuni n pipeline, fiecare ntr-un stadiu diferit de procesare.

Termenul pipelining s-a extins si la transiterea pachetelor de nformatii. Pentru amodela un astfel de pipeline cu doua stadii (twostage pipeline), printr-un lant Markovdiscret fixam protocolul de transmitere:

fiecare stadiu (etapa) are un singur buffer; Intr-o unitate de timp fixata pachetul poate face o singura tranzitie; intervalul de timp dintre k si k+1 se numeste slot time. Presupunem ca pipeline-ul

evolueaza astfel ntr-un slot: daca la nceputul slot-ului nu exista pachete n stadiul 1, atunci soseste un nou

pachet n acest stadiu cu probabilitatea p, independent de istoria trecuta a pipeline-uluisi de ce se ntampla n stadiul doi;

daca la nceputul unui slot, exista un pachet n stadiul 1 si nici un pachet n stadiul2, atunci pachetul este transferat din stadiul 1 n stadiul 2 cu probabilitatea p1;

daca la nceputul unui slot exista un pachet n stadiul 2, atunci pachetul pleaca dinacest stadiu si paraseste sistemul cu probabilitatea p2, independent de ce se ntampla nstadiul 1.

Starile modelului pipeline sunt S = {00, 01, 10, 11}, unde de bitii din perechea b1b2 Sindica cate pachete exista n stadiul 1, respectiv 2.

Din descrierea protocolului de transmitere a pachetelor avem probabilitatile de tranzitie: p intre starile 00 si 10; p1 ntre 10 si 01; p2 ntre 11 si 10.a) Deduceti probabilitatile de tranzitie corespunzatoare celorlalte arce din graful din

Fig. 10.7:b) Aratati ca lantul Markov este ireductibil precizand traiectoriile care unesc orice

stare b1b2 cu o alta distincta c1c2. Argumentati de ce este lantul si aperiodic. Gasitidistributia de echilibru.

c) In cazul n care p = p1 = p2 = 1/2 sa se scrie matricea de tranzitie si sa se calculezeprobabilitatea P (X3 = 11|X0 = 00, X1 = 10, X2 = 01).

21

00 01

10 11

p

p1

p2

Fig.10.7: