Lanturile lui Markov

nmatematic, unproces Markov, sau unlan Markov, este unproces stochasticcare are proprietatea c, dat fiind starea sa prezent, strile viitoare sunt independente de cele trecute.[1]Aceast proprietate se numeteproprietatea Markov. Cu alte cuvinte, starea curent a unui astfel de proces reine toat informaia despre ntreaga evoluie a procesului. Lanurile Markov au fost denumite dup matematicianul rusAndrei Markov.ntr-un proces Markov, la fiecare moment, sistemul i poate schimba sau pstra starea, n conformitate cu o anumit distribuie de probabilitate. Schimbrile de stare sunt numitetranziii. Un exemplu simplu de proces Markov este parcurgerea aleatoare a nodurilor unuigraf, tranziiile fiind trecerea de la un nod la unul din succesorii si, cu probabilitate egal, indiferent de nodurile parcurse pn n acel moment.

Lanturile Markov sunt larg folosite ca modele probabilistice. In aplicatii, lanturile Markov sunt adesea intalnite in spatii de dimensiuni mari. Adesea se doreste sa se calculeze distributia probabilista a acestor lanturi, si acest calcul necesita o implementare paralela. Fie P matricea de tranzitie probabilista a unui lant Markov cu n stari. Matricea P are urmatoarele proprietati: P 0 n j=1 pij = 1 Definition 2.1 Orice matrice care indeplineste cele doua proprietati se numeste matrice stocastica. Definition 2.2 Un vector linie nenegativ care are suma componentelor egala cu 1 si are proprietatea = P se numeste distributie invarianta a lantului Markov asociata lui P. Consideram urmatorul algoritm pentru determinarea distributiei invariante: consideram (0) 0 cu suma componentelor egala cu 1, si calculam iterativ (t + 1) = (t)P echivalent cu (t) = (0)P t , t 0. Dandu-se o matrice stocastica P, avem un graf direct orientat G = (N, A), unde N este multimea de stari si A = {(i, j), pij > 0, i = j} multimea de arce (multimea tuturor tranzitiilor de stari care au o probabilitate pozitiva). 2 Definition 2.3 Spunem ca matricea P este ireductibila daca pentru orice i, j N exista un drum pozitiv in graf de la i la j. Definition 2.4 Matricea P se numeste periodica daca exista un k > 1 si niste multimi disjuncte N0, . . . , Nk1 astfel incat daca i Nl si pij > 0 atunci j Nl+1(modk) . Definition 2.5 Spunem despre multimea P ca este aperiodica daca ea nu este periodica. Definition 2.6 Spunem despre multimea P ca este primitiva daca exista un intreg pozitiv t astfel incat P t > 0. Cateva exemple pot fi observate in figura 1. Figure 1: Graf direct orientat asociat unei matrici stocastice Proposition 2.1 O matrice stocastica P este primitiva daca si numai daca este ireductibila si aperiodica. Proposition 2.2 Fie P o matrice stocastica. raza spectrala a lui P este egala cu 1 ((P) = 1); daca este un vector cu suma elementelor egala cu 1, atunci vectorul P are aceeasi proprietate. Convergenta sirului iterativ (t + 1) = (t)P se obtine folosind urmatoarea teorema: Theorem 2.1 Fie P o matrice stocastica primitiva. Atunci: Exista un unic vector astfel incat = P si n i=1 i = 1. Limita lui P t cand t tinde la infinit exista si este o matrice cu toate randurile egale cu . Daca n i=1 i(0) = 1, atunci iteratia (t + 1) = (t)P converge la . Procesul iterativ = P admite o implementare paralela in care fiecare procesor i calculeaza componenta i a vectorului si la fiecare pas comunica valoarea nou calculata procesorelor j pentru care pij = 0. Se presupune ca fiecare procesor j cunoaste elementele coloanei j din matricea P. O alta implementare se obtine daca fiecare procesor j cunoaste elementele liniei j din matricea P.

n lumea real, exist o multitudine de fenomene din diferite domenii cum ar fi management, economie, structuri sociale care nu pot fi caracterizate in mod determinist, fiind necesar parcurgerea aleatorie.De aceea, n studierea acestor fenomene se utilizeaz procesele stochastice.Definiia 1. Se numete proces stochastic un experiment aleator care const dintr-o suit de subexperimente aleatoare. O clas special de astfel de procese este reprezentat de lanurile Markov.Multe experimente aleatoare se desfoar n etape. De aceea, un astfel de experimentpoate fi considerat ca fiind o secven de subexperimente i fiecare rezultat al experimentului este determinat de rezultatele subexperimentelor (n ordine).Aadar, un proces stochastic este o mulime indexat de variabile aleatoare, {Xt}, unde t parcurge o mulime T numit mulimea indicilor pozitivi T = N, iar Xt reprezint ocaracteristic cantitativ sau calitativ a sistemului cercetat.Avem o succesiune de experimente cu aceleai rezultate posibile. Prin urmare, se va considera c t este un moment de timp care ia valorile 1, 2, 3, , n. Aceast succesiune red secvena de experimente. Pentru fiecare moment, rezultatele posibile vor fi notate 1, 2, , m (m - numr finit). Cele m rezultate posibile vor fi numite strile n care se poate afla sistemul la un moment dat. Unitatea de msur pentru momentele de timp succesive t depinde de sistemul studiat.Dintre tipurile de astfel de secvene l putem meniona pe acela n care probabilitile rezultatelor la un moment dat sunt independente de rezultatele experimentelor precedente (de exemplu: aruncarea repetat a unui zar, extragerile unei bile din urn cu revenire).Un alt tip de secven este acela n care probabilitile rezultatelor la un moment dat depind de rezultatele din experienele anterioare (de exemplu: extragerile succesive din urnfr revenire). n cazul acestui din urm tip de experiment se pot distinge dou subcazuri extreme: extrem e reprezentat de faptul c probabilitile rezultatelor la un moment datdepind de rezultatele tuturor experimentelor precedente din secven; cealalt extrem a nivelului de dependen este atunci cnd probabilitile rezultatelor la un moment dat depind doar de rezultatele experimentului precedent. n aceast situaie secvena de experimente se numete proces (lan) Markov.Definiia 2. Un proces Markov sau lan Markov este o succesiune de experimente n care fiecare experiment are m rezultate posibile E1, E2,,Em, iar probabilitatea fiecrui rezultat depinde doar de rezultatul experimentului precedent.Definiia 3. Se spune c un proces stochastic are proprietatea lui Markov dac este ndeplinit egalitatea:P(Xt+1= j/X1 = k1, , Xt-1 = kt-1, Xt = i) = P(Xt+1 =j/Xt = i),pentru t =1, 2, ,n i pentru orice succesiune k1, k2, kt-1, i, j de stri din mulimea celor mstri posibile ale sistemului.Fie 2 evenimente, A i B.Notm P(A/B) probabilitatea evenimentului A condiionat de evenimentul B.Proprietatea lui Markov arat faptul c probabilitatea condiionat a oricrui eveniment viitor (Xt+1 = j), date fiind evenimentele trecute X1 = k1, , Xt-1 = kt-1 i starea prezent Xt = i, este independent de strile trecute i depinde doar de starea prezent a procesului.Exist o larg varietate de fenomene care sugereaz o comportare n maniera unui proces Markov. Ca i exemple, am redat urmtoarele situaii: probabilitatea ca o persoan s cumpere un produs de o anumit marc (detergent, bere, cosmetice, nclminte etc.) poate depinde de marca aleas la cumprtura precedent; probabilitatea ca o persoan s aib cazier poate depinde de faptul c prinii au avut sau nu cazier; probabilitatea ca starea de sntate a unui pacient s se mbunteasc, s se nruteasc sau s rmn stabil ntr-o zi poate depinde de ceea ce s-a ntmplat n ziua precedent.Evoluia unui proces Markov poate fi descris prin intermediul unei matrice.Matricea de tranziie este un instrument foarte eficient pentru reprezentarea compartamentului unui proces Markov.Definiia 4. Fie un proces Markov care are m rezultate posibile mutual exclusive E1, E2, , Em. Forma general a unei matrici de tranziie pentru acest gen de experimente are forma:Starea ViitoareStarea Curent =PO dat cu modelarea sistemului, acesta poate fi n una din cele m stri curente posibile. O stare corespunde unui rezultat al experimentului.La finalul experimentului, sistemul se poate afla n una din cele m stri.Matricea de tranziie este formata din elemente pij care reprezinta probabilitatea conditionata ca sistemul sa se modifice de la starea initiala i la starea viitoare j.Observaii1. Pij cu i = j reprezint probabilitatea ca sistemul s rmn n aceeai stare dup efectuarea experimentului, iar Pij cu i j reprezint probabilitatea ca sistemul s treac dintr-o stare n alta.2. Matricea de tranziie este o matrice ptratic de ordin m.ProprietiElementele matricei de tranziie trebuie s satisfac urmtoarele:1. 0 pij 1, i,j = 1,,m (pentru c este vorba de probabiliti),2. , i=1,2,m. Suma pe linie trebuie s dea 1 pentru c E1, E2,Em este un sistem complet de evenimente.Proprietatea 2 asigur c, dat fiind o stare curent i a sistemului, sistemul va trece cu siguran ntr-o stare j din cele m posibile dup efectuarea experimentului.

http://www.tc.etc.upt.ro/teaching/ms-ap/MS%20SEMINAR%203.pdf

http://masterat.fcim.utm.md/masterat/avize/Lanturi%20Markov%20%20si%20sisteme%20de%20asteptare.pdf

http://www.mract.ase.ro/download/anul1/2012/stoc/CAP1-4+refer.pdf