”Viitorul incepe astazi, nu maine.”

Papa Ioan Paul al II-lea

13Lanturi Markov

Algoritmul PageRank

Succesul extraordinar si dominatia motorului Google se datoreaza in prin-cipal algoritmului PageRank, care exploateaza structura link-urilor din wwwpentru a determina un indice de popularitate al fiecarei pagini, independent deinterogarea formulata de utilizator.

Documentele de pe web (paginile web) sunt identificate de aplicatiile softwareale motorului, numite roboti sau crawlere. Documentele sunt apoi indexate.Modulul de indexare extrage cuvintele cheie constituind asa numitul sac decuvinte. Un alt modul, numit query module (modulul de interogare), convertestecererea formulata de utilizator in limbaj natural, intr-un vector cerere, cu careconsulta indexul de continut si extrage paginile relevante cererii. Modulul de

1

ierarhizare ordoneaza aceste pagini in ordinea descrescatoare a popularitatii lor.PageRank-ul este un vector ale carui coordonate sunt coeficientii de popularitateai paginilor web identificate de crawler. Acest vector este distributia de echilibrua unui lant Markov definit pe graful web.

Sa definim mai precis lantul Markov ce sta la baza algoritmului PageRank.Fie 𝑊 = {1, 2, ...,𝑚}, multimea tuturor paginilor web, 𝐻 = (ℎ𝑖𝑗) matricea deconectivitate a lui 𝑊 , sau matricea hyperlink:

ℎ𝑖𝑗 =

{1, daca exista hyperlink in pagina 𝑖 catre pagina 𝑗

0, daca nu exista hyperlink in pagina 𝑖 catre pagina 𝑗

H este o matrice rara, adica cu foarte multe zerouri (in medie cu 3−10 elementenenule pe o linie). Suma elementelor de pe linia 𝑖 a matricii 𝐻 indica numarulde out-linkuri, adica numarul de linkuri din pagina 𝑖, catre alte pagini sau catreea insasi. Notam aceasta suma cu:

𝑟𝑖 =

𝑚∑𝑗=1

ℎ𝑖𝑗

si 𝑟𝑖 se numeste ordinul iesirilor din pagina. Suma elementelor de pe coloana 𝑖a matricii hyperlink indica numarul de in-linkuri ale paginii 𝑖, adica numarul delinkuri catre pagina 𝑖.

Larry Page si Serghei Brin au definit un mers aleator pe graful WEB, con-siderand ca un surfer ajuns in pagina 𝑖 alege cu aceeasi probabilitate oricare dinpaginile catre care aceasta are linkuri, prin urmare probabilitatea de a trece dinpagina 𝑖 in pagina 𝑗 este:

𝑃𝑖𝑗 =ℎ𝑖𝑗

𝑟𝑖=

{1𝑟𝑖, daca exista link in pagina 𝑖 catre pagina 𝑗

0, daca nu exista link in pagina 𝑖 catre pagina 𝑗

De exemplu daca:

𝐻 =

⎛⎜⎜⎜⎜⎜⎜⎝0 0 1 1 0 0 1 0 0 1

1 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 𝑟2 = 3 si deci probabilitatea de a

trece din pagina 2 in oricare din paginile {1, 2, ..., 10} este 𝑃2𝑗 =ℎ2𝑗

3 , adica cuaceeasi probabilitate de 1

3 un surfer poate trece din pagina 2 in pagina 1, 5 sau 8.Vom exemplifica constructia propusa de L. Page si S. Brin prin modelul simplu,de retea izolata, de pagini WEB (retea intranet), din figura ce va urma. Notam

cu 𝑃 = (𝑃𝑖𝑗) matricea probabilitatilor de tranzitie 𝑃𝑖𝑗 =ℎ𝑖𝑗

𝑟𝑖, 𝑖, 𝑗 = 1, 6. Se

observa din structura grafului de conectivitate ca paginile 2 si 6 sunt paginice nu contin link-uri catre alte pagini. Acestea se numesc dangling pages. Deexemplu fisierele pdf, ps sau fisierele imagine sunt pagini dangling. Prin urmareliniile 2 si 6 din matricea de tranzitie au toate elementele nule si astfel 𝑃 nueste o matrice stochastica, deci nu poate fi interpretata ca matricea de tranzitiea unui lant Markov cu spatiul starilor 𝑆 = {1, 2, 3, 4, 5, 6}:

2

Pentru a remedia aceasta situatie, L. Page si S. Brin au propus ca vector deprobabilitate de tranzitie dintr-o pagina dangling 𝑖, distributia uniforma:

𝑃𝑖𝑗 =1

𝑚, ∀, 𝑗 = 1,𝑚.

Adica, in mod artificial se adauga link-uri dintr-o pagina dangling catre toatepaginile web sau echivalent, ajuns intr-o pagina dangling, un navigator poateapoi alege cu o probabilitate uniforma orice pagina din www. Astfel matriceastochastica 𝑄 obtinuta din matricea 𝑃 este:

iar graful asociat va fi:

Lantul Markov definit de matricea stochastica, 𝑄, nu este in general ire-ductibil (adica nu exista drum de link-uri intre orice doua pagini sau echivalent,graful WEB nu este tare conex) si pot exista traiectorii periodice, adica surferulnavigand conform matricii de tranzitie 𝑄 ar putea fi prins ca intr-o capcana,intr-o miscare aleatoare ciclica. Din acest motiv, dar si pentru ca la un mo-ment dat si in realitate, orice surfer renunta sa navigheze urmand linkurile dinpagini, cei doi, L. Page si S. Brin, au introdus ipoteza ca doar cu probabili-tatea 𝛼 ∈ (0, 1), surferul navigheaza conform matricii 𝑄 si cu probabilitateacomplementara, 1 − 𝛼, ignora hyperlink-urile si alege cu probabilitate uniforma

3

oricare din paginile de pe web, introducand adresa URL in linia de comanda abrowser-ului. Probabilitatea 𝛼 se numeste factor de damping si in lucrarea ini-tiala a fondatorilor Google, 𝛼 era mentionat ca avand valoarea 0.85. Cu aceastamodificare matricea de tranzitie este:

𝐺 = 𝛼𝑄 + (1 − 𝛼)

⎛⎜⎜⎜⎜⎜⎜⎝1𝑚

1𝑚 . . . 1

𝑚

1𝑚

1𝑚 . . . 1

𝑚

. . . . . . . . . . . .

1𝑚

1𝑚 . . . 1

𝑚

⎞⎟⎟⎟⎟⎟⎟⎠Matricea 𝐺 se numeste matricea Google, iar matricea de elemente identice 1

𝑚 ,notata 𝐸, se numeste matricea de teleportare, deoarece surferul se teleporteazadin navigarea aleatoare urmand link-uri intr-o ”navigare artificiala”. Evidentca si matricea 𝐸 este o matrice stochastica pe linii, iar 𝐺 fiind o combinatieconvexa de astfel de doua matrici este o matrice stochastica. Mai mult:

𝐺𝑖𝑗 > 0, ∀ 𝑖, 𝑗 = 1,𝑚

si deci matricea Google este ireductibila si aperiodica. Se presupune ca matriceaGoogle este cea mai ”uriasa” matrice cu care se lucreaza in vreo aplicatie la oraactuala.

Lantul Markov avand spatiul starilor constituit din:∙ multimea paginilor web la un moment dat, de cardinal 𝑚,∙ matricea de tranzitie de tipul 𝐺, cu 𝛼 fixat∙ distributia initiala de probabilitate 𝑝(0) (distributia uniforma, de exemplu)

este un lant ireductibil si aperiodic, deci are o unica distributie de echilibru 𝑣,numita vectorul PageRank.

PageRank–ul 𝑣 este este limita sirului 𝑝(𝑛), cu 𝑝(𝑛) = 𝑝(0)𝐺𝑛. Limita esteaceeasi indiferent de distributia initiala de probabilitate 𝑝(0) adica indiferent cuce probabilitate surferul alege pagina din care incepe navigarea. 𝑝(𝑗) se numestePageRank-ul paginii 𝑗 si reprezinta sansa asimptotica pe care o are pagina 𝑗de a fi vizitata de navigatorul aleator sau proportia din timpul de navigarepe care surferul ar petrece-o vizitand pagina 𝑗. Deci 𝑝(𝑗) este un indice depopularitate al paginii. Cand un utilizator introduce cuvinte cheie in bara decautare, motorul Google cauta paginile ce contin cuvintele cheie si le afiseazain ordinea descrescatoare a PageRank-ului lor. Remarcam ca PageRank-ul uneipagini este independent de interogarea formulata de utilizator. Ea depinde doarde structura grafului WEB si se poate calcula offline.

PageRank-ul se calculeaza la intervale regulate de timp. Pana in 2008 secalcula lunar, dar acum se actualizeaza la intervale mai scurte de timp. VectorulPagerank se calculeaza numeric, folsind asa numita metoda a puterii, adicase calculeaza recursiv, pornind de la 𝑝(0) si 𝐺, distributiile (sau PageRankulla 𝑛 pasi de navigare) 𝑝(𝑛) = 𝑝(𝑛 − 1)𝐺. Se considera ca metoda a atinsstadiul de convergenta (adica s-a ajuns la echilibru) intr-o etapa 𝑛, in care‖𝑝(𝑛) − 𝑝(𝑛− 1)‖ < 𝜀, unde 𝜀 este un numar pozitiv foarte mic, prescris.

S-a demonstrat ca viteza de convergenta a metodei puterii este aceeasi curata de convergenta a lui 𝛼𝑛, unde 𝛼 este factorul de damping. Implicatiiasupra PageRankului. Din punctul de vedere al vitezei de convergenta ar fipreferabil un factor 𝛼 cat mai apropiat de zero. In acest caz insa tinand seama

4

ca matricea Google este 𝐺 = 𝛼𝑄 + (1 − 𝛼)𝐸, ar rezulta ca se acorda o pondereredusa 𝛼 navigarii conform linkurilor din graful WEB (cu modificarea pentrupagini dangling) si o pondere mai mare navigarii artificiale, conform matricei deteleportare 𝐸. Cu alte cuvinte in acest caz PageRank–ul asociat nu ar reflectapopularitatea reala a paginilor web. De aceea o valoare rezonabila, asa cuma fost ea aleasa init ial de Larry Page si Serghei Brin, 𝛼 = 0.85, conduce larezultate mai apropiate de realitate si la o viteza de convergenta suficient de buna(un reprezentant Google a declarat ca metoda puterii converge dupa 100 − 200de iteratii). Daca vreti sa aflati Pagerankul unor pagini WEB intrati aici.

Pentru o ierarhizare personalizata a paginilor web, matricea de teleportare𝐸, se calculeaza luand in considerare vectorul personalizat 𝑤, ce este un vectorprobabilist ale carui coordonate 𝑤 = (𝑎1, 𝑎2, ...𝑎𝑚), reprezinta probabilitatea casurferul, ce iese din navigarea conform linkurilor, sa aleaga pagina 1, 2, ...,𝑚, dinweb. Cu alte cuvinte el nu alege o pagina in mod uniform, ci are anumite prefer-inte, identificate de motor in decursul timpului. Astfel matricea de teleportareva fi 𝐸 = 𝑒𝑤 , unde 𝑒 = (1, 1, ..., 1)𝑡 , si matricea Google, corespunzatoare:

𝐺 = 𝛼𝑄 + (1 − 𝛼)𝑒𝑤

iar distributia de echilibru corespunzatoare este Pagerank-ul personalizat.

Notiuni teoretice

Notiuni utile: proces stocastic, stare esentiala, stare tranzienta, stare ape-riodica, stare absorbanta, clasa, perioada unei stari esentiale, lant Markov ire-ductibil, vezi curs

Lanturi Markov finite

∙ evolutia in timp a unui sistem (𝑋𝑘)𝑘≥0 reprezinta un lant Markov finitdaca

=⇒ starile posibile ale sistemului apartin unei multimi numita multimeastarilor

𝑆 = {𝑠1, 𝑠2, . . . 𝑠𝑛}.

=⇒ starea viitoare a sistemului depinde doar de starea prezenta nu si destarile trecute

𝑃 (𝑋𝑘+1 = 𝑠𝑘+1|𝑋𝑘 = 𝑠𝑘, 𝑋𝑘−1 = 𝑠𝑘−1, . . . , 𝑋0 = 𝑠0) = 𝑃 (𝑋𝑘+1 = 𝑠𝑘+1|𝑋𝑘 = 𝑠𝑘)

pentru niste stari 𝑠0, 𝑠1, . . . , 𝑠𝑘+1 din 𝑆.

Interpretare intuitiva: viitorul depinde doar de prezent, trecutul nu conteaza!

Lanturi Markov omogene

Vom lucra cu lanturi Markov omogene, aceasta insemnand ca matricea 𝑃 aprobabilitatilor de trecere nu depinde de 𝑘 si astfel

5

𝑃 =

⎛⎜⎜⎜⎝𝑃11 𝑃12 . . . 𝑃1𝑛

...... . . .

...

𝑃𝑛1 𝑃𝑛2 . . . 𝑃𝑛𝑛

⎞⎟⎟⎟⎠unde 𝑃𝑖𝑗 := 𝑃 (𝑋𝑘+1 = 𝑗|𝑋𝑘 = 𝑖).

∙ probabilitatea ca sistemul sa se afle in starea 𝑖 dupa 𝑘 pasi (unitati detimp) se noteaza

𝑝𝑖(𝑘) = 𝑃 (𝑋𝑘 = 𝑖)

uneori vom folosi notatia

𝑝𝑠𝑖(𝑘) = 𝑃 (𝑋𝑘 = 𝑠𝑖)

aceasta insemnand ca avem urmatoarea distributie pentru variabilele aleatoare𝑋𝑘

𝑋𝑘 :

⎛⎝ 𝑠1 𝑠2 . . . 𝑠𝑛

𝑝1(𝑘) 𝑝2(𝑘) . . . 𝑝𝑛(𝑘)

⎞⎠ , 𝑘 ≥ 0.

∙ are loc relatia Chapman-Kolmogorov intre vectorii de probabilitate si ma-tricea de tranzitie

𝑝𝑖(𝑘) =

𝑛∑𝑗=1

𝑝𝑗(𝑘 − 1) · 𝑃𝑗𝑖

sau scrisa vectorial

𝑝(𝑘) = 𝑝(𝑘 − 1) · 𝑃∙ probabilitatea ca lantul sa evolueze pe traiectoria 𝑠0, 𝑠1, 𝑠2, ..., 𝑠𝑘 ∈ 𝑆 este

𝑃 (𝑋0 = 𝑠0, 𝑋1 = 𝑠1, 𝑋2 = 𝑠2, . . . , 𝑋𝑘 = 𝑠𝑘) = 𝑝𝑠0(0) · 𝑃𝑠0𝑠1𝑃𝑠1𝑠2 . . . 𝑃𝑠𝑘−1𝑠𝑘

∙ daca un lant Markov omogen are vectorul initial de stare (distributia ini-tiala de probabilitate)

𝑝(0) = (𝑝𝑠1(0), 𝑝𝑠2(0), . . . , 𝑝𝑠𝑛(0))

si matricea de tranzitie 𝑃, atunci probabilitatile corespunzatoare starilor saledupa 𝑛 unitati de timp sunt date de

𝑝(𝑛) = 𝑝(0) · 𝑃𝑛

Calculul puterilor unei matrice

Pentru a calcula 𝑃𝑛 putem utiliza transformata 𝑍 si anume

𝑃𝑛 = 𝑍−1{𝑧(𝑧𝐼 − 𝑃 )−1

}(𝑛), 𝑧 ∈ C

6

Lanturi Markov absorbante

∙ stare absorbanta: o stare 𝑖 este absorbanta daca 𝑃𝑖𝑖 = 1∙ un lant Markov este un lant Markov absorbant daca lantul are cel putin o

stare absorbanta si este posibil sa ajungem din orice stare neabsorbanta intr-ostare absorbanta.

∙ fie 𝑃 matricea de tranzitie a unui lant Markov absorbant, rearanjand liniilesi coloanele astfel ca starile absorbante se fie primele matricea 𝑃 se poate scriesub forma

𝑃 =

⎛⎝𝐼 0

𝑅 𝑄

⎞⎠∙ matricea fundamentala este definita prin 𝐹 = (𝐼 −𝑄)−1 si se poate arata

ca

𝑃𝑛 →

⎛⎝ 𝐼 0

𝐹𝑅 0

⎞⎠ , 𝑛 → ∞

∙ matricea 𝐹𝑅 este matricea probabilitatilor ca plecand dintr-o stare initialneabsorbanta sistemul sa ajunga intr-o stare absorbanta.

Lanturi Markov regulate

∙ un lant Markov este un lant Markov regulat daca matricea sa de tranzitieeste regulata i.e. o putere a acesteia are toate elementele strict pozitive.

∙ pentru un lant Markov regulat exista un unic vector de stare 𝑣 astfel capentru orice vector initial de stare 𝑣0

𝑣0𝑃𝑛 → 𝑣, 𝑛 → ∞

∙ vectorul 𝑣 se numeste distributia de echilibru si furnizeaza trend-ul petermen lung al lantului Markov

∙ vectorul 𝑣 = (𝑣1, 𝑣2, . . . , 𝑣𝑛) se poate afla folosind identitatile:

𝑣𝑃 = 𝑣

si𝑣1 + 𝑣2 + . . . + 𝑣𝑛 = 1.

∙ un lant Markov finit este aperiodic si ireductibil daca si numai daca esteregulat.

7

Probleme rezolvate

Problema 1. Intr-o tara europeana, la finalul lui mai 2018, 40% dintrevotantii inregistrati erau liberali, 45% erau conservatori iar 15% erau in-dependenti. Dupa o perioada de o luna liberalii si-au pastrat 80% din elec-torat, in timp ce 15% au migrat la conservatori si 5% au devenit indepen-denti. Conservatorii s-au pastrat 70% si au pierdut 30% in favoarea lib-eralilor. Independentii au pastrat 60% si au pierdut cate 20% in favoarealiberalilor si conservatorilor. Presupunem ca aceste trenduri vor continua.a) Scrieti o matrice de tranzitie folosindu-va de aceste informatii.b) Aflati procentele corespunzatoare fiecarui tip de votant la finalul luiaugust.c) Daca alegerile ar fi in octombrie 2019, care partid are sanse mai marisa castige ?

Solutie: 𝑎) Matricea de tranzitie folosind starile L (liberal), C (conservativ)si I (independent), este:

𝑃 =

⎛⎜⎜⎜⎝0.80 0.15 0.05

0.30 0.70 0

0.20 0.20 0.60

⎞⎟⎟⎟⎠∙ vectorul initial de probabilitate este

𝑝(0) = (0.40 0.45 0.15)

𝑏) Dupa trei luni (august) vectorul de stare corespunzator se calculeaza dupaformula

𝑝(3) = 𝑝(0) · 𝑃 3

𝑐) Observam ca 𝑃 2 este o matrice regulata si prin urmare lantul Markovatasat problemei este regulat.

∙ proprietatea principala a lanturilor Markov regulate estePentru un lant Markov regulat exista un unic vector de stare 𝑣 astfel ca

pentru orice vector initial 𝑣0 :

𝑣0𝑃𝑛 → 𝑣, 𝑛 → ∞

∙ gasim aceasta distributie de echilibru 𝑣 = (𝑣1, 𝑣2, 𝑣3) care da trendul petimp lung al lantului Markov din ecuatiile

𝑣𝑃 = 𝑣

si𝑣1 + 𝑣2 + 𝑣3 = 1.

∙ vectorul 𝑣 va da situatia din octombrie 2019.

8

Problema 2. Un grup de soareci se afla intr-o cusca care are trei com-partimente conectate intre ele A, B si C. Soarecii din compartimentul Ase muta in compartimentul B cu o probabilitate 0.3 si in C cu o probabili-tate 0.4. Cei din compartimentul B se muta in A sau C cu probabilitatile0.2 si 0.25, respectiv. Usa compartimentului C nu poate fi deschisa dininterior. Aflati probabilitatea cu care un soarece din compartimentul Ava ajunge in cele din urma blocat in compartimentul C.

Solutie: Matricea de tranzitie, asociata lantului Markov cu ajutorul caruiamodelam matematic problema, este

𝑃 =

𝐴 𝐵 𝐶

𝐴

𝐵

𝐶

⎛⎜⎜⎜⎝0.3 0.3 0.4

0.2 0.55 0.25

0 0 1

⎞⎟⎟⎟⎠Se observa ca starea C este o stare absorbanta, 𝑃𝐶𝐶 = 1. Conform teoriei

lanturilor Markov absorbante daca reanranjam matricea de tranzitie sub forma:

𝑃 =

𝐶 𝐴 𝐵

𝐶

𝐴

𝐵

⎛⎜⎜⎜⎝1 0 0

0.4 0.3 0.3

0.25 0.2 0.55

⎞⎟⎟⎟⎠

obtinem 𝑅 =

⎛⎝ 0.4

0.25

⎞⎠ si 𝑄 =

⎛⎝0.3 0.3

0.2 0.55

⎞⎠Prin calcul matricea fundamentala este 𝐹 ≈

⎛⎝1.76 1.17

0.78 2.74

⎞⎠ si matricea prob-

abilitatilor de a ajunge in starea absorbanta C este 𝐹𝑅 ≈

⎛⎝0.99

0.99

⎞⎠Asadar un soarece din compartimentul A are o sansa 99% sa ajunga blocat

in compartimentul C. (rezultat identic pentru un soarece aflat initial in com-partimentul B)

Problema 3. Sa se determine distributia la momentul 𝑛 = 12 a unuilant Markov cu distributia initiala 𝜋0 si matricea probabilitatilor de trecere𝑃 = (𝑝𝑖𝑗) de mai jos

𝜋0 :

⎛⎝ −1 1

0.65 0.35

⎞⎠ , 𝑃 =

⎛⎝0.15 0.85

0.3 0.7

⎞⎠

9

Solutie: Distributia la momentul 𝑛 se afla cu formula

𝑝(𝑛) = 𝑝(0) · 𝑃𝑛

unde 𝑝(0) = (0.65 0.35) este vectorul de probabilitate corespunzator distributiei𝜋0 iar pentru calculul puterilor lui 𝑃 se recomanda utilizarea transformatei 𝑍,obtinandu-se o metoda generala de calcul

𝑃𝑛 = 𝑍−1{𝑧(𝑧𝐼 − 𝑃 )−1

}(𝑛), 𝑧 ∈ C

Vom aplica aceasta formula pentru 𝑛 = 12, in cele ce urmeaza. Transformata Zse aplica unei matrice aplicand-o fiecarui element al matricei. Asadar in primafaza vom calcula 𝑧(𝑧𝐼 − 𝑃 )−1 si apoi aplicam celor patru elemente ale saletransformata inversa, prin formula de inversare cu poli

𝑥𝑛 =∑

toti polii lui 𝑋(𝑧)

Rez(𝑋(𝑧)𝑧𝑛−1

)Inainte de toate sa observam ca 𝑧(𝑧𝐼 − 𝑃 )−1 =

(𝐼 − 1

𝑧𝑃)−1

si avem exactforma data in curs. Sa incepem prin a calcula inversa lui 𝑧𝐼 − 𝑃 .

det (𝑧𝐼 − 𝑃 ) =

𝑧 − 0.15 0.85

0.3 𝑧 − 0.7

= (𝑧 − 0.7)(𝑧 − 0.15) − 0.3 · 0.85

Aceasta expresie va trebui descompusa in factori caci va genera polii din formulade inversare.

(𝑧 − 0.7)(𝑧 − 0.15) − 0.3 · 0.85 = 𝑧2 − 0.85𝑧 − 0.15 = (𝑧 − 𝑧1)(𝑧 − 𝑧2)

unde 𝑧1 si 𝑧2 sunt cele doua radacini ale polinomului

𝑧1,2 =0.85 ±

√1.3225

2

Deoarece arata atat de exotic, fie le aproximam, fie vom lucra mai departe cu𝑧1 si 𝑧2.

Formula inversei este

(𝑧𝐼 − 𝑃 )−1 =1

(𝑧 − 𝑧1)(𝑧 − 𝑧2)

⎛⎝𝑧 − 0.7 −0.85

−0.3 𝑧 − 0.15

⎞⎠Formula lui 𝑃 12 se obtine prin

𝑃 12 = 𝑍−1[𝑧(𝑧𝐼 − 𝑃 )−1

](12) =

⎛⎝𝑍−1[𝑧 · 𝑧−0.7

(𝑧−𝑧1)(𝑧−𝑧2)

](12) 𝑍−1

[𝑧 · −0.85

(𝑧−𝑧1)(𝑧−𝑧2)

](12)

𝑍−1[𝑧 · −0.3

(𝑧−𝑧1)(𝑧−𝑧2)

](12) 𝑍−1

[𝑧 · 𝑧−0.15

(𝑧−𝑧1)(𝑧−𝑧2)

](12)

⎞⎠si tot ce ramane de facut este sa calculam cele patru transformate inverse prinformule de tipul

𝑍−1

[𝑧(𝑧 − 0.7)

(𝑧 − 𝑧1)(𝑧 − 𝑧2)

](12) = Rez

(𝑧(𝑧 − 0.7)

(𝑧 − 𝑧1)(𝑧 − 𝑧2)· 𝑧11, 𝑧1

)+Rez

(𝑧(𝑧 − 0.7)

(𝑧 − 𝑧1)(𝑧 − 𝑧2)· 𝑧11, 𝑧2

)10

Reziduurile se evalueaza usor prin trecere la limita, vezi pagina 25 in seminaruldespre integrare complexa.

Problema 4. Sa se determine clasele unui lant Markov cu distributiainitiala 𝜋0 si matricea probabilitatilor de trecere 𝑃 = (𝑝𝑖𝑗) de mai jos

𝜋0 :

⎛⎝ 0 1 2 3 4

0.1 0.3 0.2 0.2 0.2

⎞⎠

𝑃 =

⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

0.2 0.3 0.5 0 0

0 0.4 0 0 𝑎

0 0.6 0.4 0 0

0 0 0 0 1

0 0 0 0.9 0.1

⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠Determinati valoarea lui 𝑎. Care este perioada starii 𝑠 = 3 ? Care stareeste absorbanta ? Care stare este tranzienta ?

Solutie: Intai de toate trebuie sa aflam elementul lipsa 𝑎. Matricea prob-abilitatilor de trecere a proprietatea ca suma elementelor fiecarei linii este 1.Prin urmare 0.4 + 𝑎 = 1 deci 𝑎 = 0.6. Vom desena acum graful de tranzitiecorespunzator matricei de tranzitie

1

2

3

4

5

0.2

0.3

0.6

0.4

0.6

1

0.6

0.4

0.1

0.9

Starile absorbante sunt starile care nu pot fi parasite. Se recunosc usor caciin matricea de tranzitie apare pe diagonala principala 𝑃𝑖𝑖 = 1 pentru acea stare𝑠𝑖 care este absorbanta. Nu exista stari absorbante.

Starile tranziente sunt acele stari care nu sunt stari recurente. O stare esterecurenta daca atunci cand pornim din ea in oricare directie, data de sagetile

corespunzatoare ei, ne vom putea intoarce inapoi. De exemplu, din 4 nu putem

porni decat inspre 5 dar ne putem intoarce. Deci 4 este recurenta, la fel si

5 . In schimb din 1 putem porni inspre 2 si nu exista drum de intoarcere.

Deci 1 este tranzienta. Analog starile 2 si 3 sunt tranziente.

11

Clasele lantului Markov (formate din starile care comunica) sunt justificate

mai jos. Deoarece din 1 se poate ajunge doar in 2 si 3 dar nu exista un

drum inapoi obtinem Clasa I={

starea 1}

Analog din 2 nu se poate ajunge in starile din care exista drumuri inspre

2 , iar din starea 3 nu se poate ajunge in 1 , prin urmare se pot identificainca doua clase

𝐶𝑙𝑎𝑠𝑎 𝐼𝐼 ={

starea 2}

si 𝐶𝑙𝑎𝑠𝑎 𝐼𝐼𝐼 ={

starea 3}

Starile 4 si 5 sunt singurele care comunica, deci ultima clasa este

𝐶𝑙𝑎𝑠𝑎 𝐼𝑉 ={

starea 4 , starea 5}.

Pentru a stabili perioada unei stari trebuie sa gasim cel mai mare divizorcomun al numerelor 𝑛 de revenire in acea stare. E important de retinut ca toate

starile dintr-o clasa au aceeasi perioada! De exemplu din 4 se poate reveni

in starea 4 dupa un drum de lungime 2 dar si printr-un drum de lungime 3,

facand un loop intermediar in starea 5 . Deci perioada starii 4 este 1 = [2, 3].Toate starile lantului au perioadele 1, deci sunt aperiodice.

12

Probleme propuse

Problema 1. Desenati graful de tranzitie corespunzator matricei de tranzitie

𝑃 =

⎛⎜⎜⎜⎝0.5 0.3 0.2

0 1 0

0.2 0.2 0.6

⎞⎟⎟⎟⎠si reciproc alcatuiti matricea de tranzitie corespunzatoare grafului orientat

1

2

3

4

0.2

0.60.6

0.7

0.3

0.3

0.3

0.4

0.4

0.2

Problema 2. Un computer poate opera in doua moduri diferite. La fiecareora el ramane in acelasi mod sau comuta la modul al doilea conform matriceiprobabilitatilor de tranzitie

𝑃 =

⎛⎝0.4 0.6

0.6 0.4

⎞⎠Daca computerul este in modul 1 la ora 5 : 30 pm, care este probabilitatea sa fiein acelasi mod la ora 7 : 30 pm in aceeasi zi ?

Problema 3. Un analist a pietei este interesat daca consumatorii prefera com-puterele Dell sau pe cele HP. Doua studii de piata, realizate in decursul unuian, au scos la iveala urmatoarele fenomene: 10% dintre detinatorii de computereDell au schimbat si au optat pentru unul HP in timp ce restul nu au avut motivesa renunte la computerele lor Dell. 35% dintre cei care detineau un computerHP au optat pentru unul Dell iar restul si-au pastrat computerele HP. Aflatidistributia pietei pentru o perioada lunga de timp.

13

Problema 4. Probabilitatile de tranzitie pentru un lant Markov sunt caracter-izate prin matricea de tranzitie

𝑃 =

⎛⎝ 25

35

110

910

⎞⎠ .

Calculati atunci 𝜋1000 daca 𝜋0 =

⎛⎝ −5 1

12

12

⎞⎠.

Problema 5. Notam prin 𝑆 = {𝐼, 𝑃, 𝑍,𝐵} multimea starilor vremii, undeInnorat, Ploios, Zapada si Buna. Presupunem ca avem o matrice a probabil-itatilor de tranzitie intre aceste stari dupa cum urmeaza

𝑃 =

⎛⎜⎜⎜⎜⎜⎜⎝0.35 0.25 0.15 0.25

0.35 0.35 0.20 0.10

0.35 0.15 0.45 0.05

0.34 0.05 0.01 0.60

⎞⎟⎟⎟⎟⎟⎟⎠Daca luni vremea este buna care este predictia meteo pentru miercuri? (adica

sansele sa fie innorat, ploios, zapada sau vreme buna). Aflati probabilitatea camarti sa ploua, miercuri sa fie innorat si joi sa ploua din nou.

Problema 6. Simplificam problema anterioara presupunand doar trei stari alevremii Innorata, Ploiosa si Buna cu matricea de tranzitie

𝑃 =

⎛⎜⎜⎜⎝0.5 0.2 0.3

0.4 0.4 0.2

0.3 0.3 0.4

⎞⎟⎟⎟⎠Daca luni este ploios cum va fi vremea de Craciun ?

14

Bibliografie

[1] R. Negrea. Note de curs MS, 2020.

[2] E. Petrisor. Note de curs Probabilitati si statistica, 2016.