L1 - Platforma

Lucrarea nr. 1. Surse Markov 1. Obiectivul lucrarii În aceasta lucrare se studiaza sursele discrete Markov cu memorie de ordinul întâi cu 2, 3 si 4 stari si modul în care acestea evolueaza pornind de la conditii impuse. De asemenea, în lucrare sunt prezentate exemple de stationarizare a surselor cu doua si trei stari.

2. Introducere teoretica O sursa discreta de informatie debiteaza mesaje la momente discrete de timp, fiecare mesaj fiind reprezentat printr-un numar finit de simboluri. Multimii de simboluri i se pune în corespondenta o multime finita de semnale sub forma de impulsuri. Rata de emisie a unei surse discrete este deci finita. Sursa discreta se caracterizeaza prin simbolurile x1,x2,...,xi,...., pe care le emite, cuv intele care se constituie cu aceste simboluri în numar finit, alfabetul aferent {x1 ,K , xn } ca totalitatea simbolurilor si limba sursei ca totalitatea cuvintelor pe care le poate debita sursa în alfabetul sau. O sursa discreta cu memorie furnizeaza câte un simbol a carui probabilitate de aparitie depinde de simbolul precedent sau de un sir de simboluri precedente, numarul acestora determinând ordinul memoriei. O sursa discreta stationara sau omogena genereaza simboluri ale caror probabilitati nu depind de originea timpului, ci doar de pozitiile lor relative. Probabilitatile sunt invariante la orice translatie de-a lungul sirului. Într-o diagrama a tranzitiilor de stare, nodurile reprezinta starile, iar arcele, tranzitiile. Arcele sunt etichetate prin probabilitatile conditionate asociate tranzitiilor p(x i/x j). Daca un simbol este conditionat de mai multe simboluri precedente, numarul de stari creste. Astfel, o sursa binara care furnizeaza simboluri conditionate de câte doua simboluri precedente se caracterizeaza prin patru stari corespunzatoare grupurilor de câte doua simboluri precedente: S 1 => 00, S2 => 01, S3 => 10 si S4 => 11. Se spune ca starii S1 i se asigneaza dubletul 00, starii S2 = 01 etc. O sursa cu memorie de ordinul m este o sursa cu constrângeri probabilistice, distributia de probabilitate având elemente de forma:

(

)

p xi j / xi j −1 , xi j − 2 , K, xi j− m , adica emisia unui simbol este conditionata de m simboluri precedente. Daca alfabetul sursei contine D simboluri, o sursa cu memorie de ordinul m are r ≤ D m stari. Starii sursei i se asigneaza secventa x j i , L, x j j −m de m simboluri:

(

(

)

S = s i → xi j− 1 , xi j − 2 , L,

)

xi j− m .

Daca emiterea unui simbol de iesire este conditionata numai de starea precedenta, sursa poate fi modelata cu ajutorul unui lant Markov finit si se numeste sursa Markov. Un lant Markov finit este definit ca un proces aleator discret {L , S − 2 , S −1 , S0 , S1 , S 2 , L} , unde elementele Si, numite stari, sunt variabile aleatoare discrete care iau valori în alfabetul starilor {s0 , s1 ,L, sr −1 } , iar dependenta satisface conditia Markov:

3

p (S 1 = s j / S 0 , S −1 , L) = p (S 1 = s j / S 0 ) = p (S 1 / S 0 )

Aceasta înseamna ca probabilitatea ca o variabila aleatoare sa ia valoarea unei stari, conditionata de un trecut infinit, este egala cu probabilitatea conditionata de cel mai recent trecut (ultima stare parasita). Daca probabilitatea de trecere dintr-o stare în alta nu depinde de timp, lantul Markov este omogen (stationaritatea conditiei Markov). O sursa Markov consta într-un lant Markov intern împreuna cu o functie care aplica alfabetul starilor în alfabetul sursei. O sursa de informatie Markov este un sir de v.a. discrete

{L , X 0 , X 1 , X 2 , X 3 , X 4 ,L} care iau valori în alfabetul finit al sursei X = {x1 , x2 , L, x D }

prin tranzitii succesive prin sirul de stari

{S 0 , S1 , S 2 , S 3 ,L}. Sirul de stari constituie un lant Markov finit, luând valori în alfabetul starilor

S = {s1 , s2 ,L , sr } cu o distributie de probabilitati a starii initiale S0 P0 = {p 01 , p 02 , L , p 0 r },

adica

P(S 0 = s j ) = p 0 j , (∀ j ) .

Pobabilitatile de tranzitie directe între stari sunt independente de momentele de timp (omogeneitate)

P(S n +1 = s j / S n = si ) = p(s j / si ) = pij ,

astfel încât, pe baza unei functii f :S → X ,

se obtine

X 0 = f (S0 ), X 1 = f (S1 ),L cu distributia de probabilitati simultane având proprietatea de stationaritate

(

) (

)

p x j1 , x j 2 ,L = p x j1+ k , x j2 + k ,L . Ori de câte ori lantul intern Markov intra într-o noua stare, sursa livreaza la iesire simbolul corespunzator specificat de functia f (•). În general, numarul de stari r poate fi mai mare decât numarul simbolurilor alfabetului sursei, D, caz în care un simbol de iesire poate corespunde mai multor stari. În fiecare moment de timp lantul Markov trece într-o noua stare, sursa livrând la iesire un simbol apartinând alfabetului sursei în conformitate cu functia specificata. Probabilitatile de trecere dintr-o stare S i în alta stare Sj, independente de mometul de timp,

4

p ij = p (S 1 = s j / S 0 = si ) = p (s j / si ) ,

constituie matricea de tranzitie T:

 p 11 p T =  21 L   p r1

p1 r  L L L L p 2 r   = L p ij L .  L L   L L L L p rr 

p 12 L p 22 L pr 2

De exemplu, pentru graful sursei din fig. 1 se obtine 1 3 T = 1 1   2

 0 0 1  2 

2 3 0 0

1/3 s1 1/2

2/3 1

1/2

s3

s2

Fig. 1. Sursa ireductibila

Matricea T este o matrice stochastica, deci r

∑p

= 1, (∀i ) ,

ij

j =1

adica suma elementelor pe fiecare linie este 1. Distributia de probabilitate a starilor la momentul n este data de matricea

[( ) ( )

( )]

Pn = p s1n , p s 2 n ,L , p srn ,

( )

unde p s jn reprezinta probabilitatea ca sursa sa se gaseasca în starea s j , la momentul n:

( )

r

(

) ∑ p(s )⋅ p(s r

p s jn = ∑ p s j n , sin − 1 = i =1

i =1

i n −1

sau înca:

( )

( )

r

p s jn = ∑ p si n −1 ⋅ p ij . i =1

Rezulta deci: Pn = Pn− 1 ⋅ T 5

jn

)

/ s in − 1 , (∀j ),

Daca se noteaza prin P 0 matricea linie a probabilitatilor starilor initiale P0 = p01, p02 , L, p0 r ,

atunci rezulta Pn = P0 .T n

În cazul unei surse stationare, P n = P n-1, adica probabilitatile de aparitie ale starilor nu depind de n, iar probabilitatile de tranzitie cu atât mai mult nu depind de n. Daca unei stari i se asigneaza un singur simbol de iesire, adica numarul starilor este egal cu numarul simbolurilor alfabetului, sursa Markov este de ordinul 1, un simbol emis fiind conditionat de simbolul precedent. Daca unei stari i se asigneaza doua simboluri de iesire, sursa Markov este de ordinul al doilea. În acest caz, unei stari îi corespunde cea mai recenta pereche de simboluri emise. O sursa Markov ergodica se bucura de proprietatea ca secventa distributiilor de probabilitate P n pentru n = 1, 2, ... pe toata multimea de stari tinde catre o distributie de probabilitate limita w independenta de distributia initiala de probabilitati. Aceasta distributie limita w se numeste distributie de echilibru sau de regim stationar sau, înca, distributie asimptotica, adica P n → w. Pentru fiecare element al lui Pn se poate scrie:

lim p ij ,n = P (S n = s j / S 0 = si ) = w j , i, j = 1,2, L, r , n →∞

unde w j este independent de i. Numarul wj se numeste probabilitatea asimptotica pentru starea sj, iar matricea linie w = w1, w2 ,L, wr

este distributia de echilibru, unde r

∑wj =1 j =1

Conditia necesara si suficienta ca w sa fie distributia de echilibru a unei surse Markov este wT = w, adica w este un vector propriu al matricii de tranzitie T. Daca distributia initiala P0 = w , atunci

Pn = w , (∀n). Entropia unei surse cu memorie se defineste ca entropia unui simbol oarecare al sursei dupa observarea tuturor simbolurilor anterioare. Cantitatea medie de informatie prin emisia unui simbol în cazul unei surse cu memorie este, prin urmare: H ∞ ( X ) = lim H ( X n / X 1 ,L , X n −1 ) n →∞

si este o marime marginita deoarece H ∞ ( X ) ≤ H ( X n ) ≤ log X = log D ( X reprezinta numarul D al simbolurilor alfabetului X) Entropia unei surse Markov ergodice unifilare este: 6

H ∞ ( X ) = ∑ w j ⋅ H (S j ) , r

j =1

unde r este numarul de stari si w = w1, L, w j ,L, wr reprezinta vectorul distributiei de echilibru. În majoritatea cazurilor întâlnite, sursele Markov nu sunt stationare. Modul în care o sursa poate fi stationarizata prezinta interes teoretic, dar este si o necesitate practica. Daca într-o stare a sursei nu se poate ramâne (sau se poate ramâne doar un numar relativ mic de pasi), acea stare se numeste stare tranzitorie. Daca o stare a sursei, odata atinsa, nu mai poate fi parasita (sau poate fi parasita numai dupa un numar relativ mare de pasi), acea stare se numeste stare absorbanta. Daca sirul valorilor succesive de probabilitate este convergent, atunci limita acestuia reprezinta vectorul distributiei de echilibru. În functie de viteza cu care se atinge acest vector, convergenta poate fi rapida sau lenta. În functie de modul de variatie a valorilor de probabilitate fata de limita, convergenta poate fi monotona sau oscilanta. Lucrarea arata ca un asemenea proces este asimptotic stationar, cu exceptia rarelor cazuri când apar oscilatii permanente ale unor componente din P n. Obtinerea unui proces de emisie stationar se face în functie de ceea ce se impune. Daca se impune matricea de tranzitie, este necesara determinarea vectorului distributiei de echilibru care, daca este luat drept P 0, determina un proces de emisie permanent stationar. În asemenea situatii nu mai exista un regim tranzitoriu de atingere a stationaritatii. În alte situatii se impune vectorul distributiei de echilibru si se cere una din matricile de tranzitie a caror stationaritate este caracterizata de acest vector. Câteva modalitati de stationarizare ale surselor Markov de ordinul întâi sunt prezentate în anexa teoretica din programul de simulare.

3. Descrierea evolutiei programului Programul contine o prezentare teoretica, calcule si exemple. Folosirea acestui program necesita câteva precizari legate de accesul la diferite parti ale acestuia. Lucrarea de laborator se prezinta sub forma unor succesiuni de ecrane care sunt ordonate într-o structura de tip arbore. Primul ecran este ecranul generic, care contine titlul lucrarii. Acest ecran se afla la baza arborelui. Imediat dupa acesta se afla ecranul care contine meniul. Intrarea si iesirea din program se fac numai prin generic. În meniu sunt prezentate sapte optiuni de studiu. Fiecare optiune contine un numar de ecrane alocate studiului. Iesind din aceste optiuni se ajunge în meniu apasând tasta Q (Quit), indiferent daca s-au epuizat sau nu ecranele acestora. La terminarea lucrarii, iesirea din program în DOS se face apasând succesiv aceeasi tasta Q. Alegerea unei optiuni din meniu se face apasând tasta având marcata cifra înscrisa în dreptul acesteia. În interiorul optiunii se pot executa deplasari înainte apasând tasta N (Next), sau înapoi, apasînd tasta P (Previous). Schimbarea sensului de miscare se poate face în orice moment. În partea de calcul exista comenzi suplimentare celor de deplasare printre ecranele lucrarii. Acestea sunt: • C (Change) - schimbarea datelor, • Enter - declansarea citirii datei introduse, - executia unui pas de calcule,

7

•

V (Vector)

- aflarea vectorului distributiei de echilibru,

• M (Matrix) - aflarea unei matrici cu vectorul distributiei de echilibru impus. Modul de folosire a programului este amintit de-a lungul lucrarii prin texte încadrate sau mesaje antet. Este indicat ca datele introduse sa respecte toate conditiile impuse; altfel ele vor fi refuzate, precizându-se greseala facuta.

4. Desfasurarea lucrarii 4.1. Cititi introducerea teoretica din lucrare. 4.2. Sursa Markov cu doua stari. Pentru a ilustra câteva aspecte ale emisiei unei surse cu 2 stari, parcurgeti urmatoarele exemple si retineti concluziile acestora. 4.2.1. Introduceti: 0 .99 0.01 T=  , 0   1

P0 = [1 0].

Dupa 5 pasi se ajunge la vectorul stationar printr-o convergenta monotona. Remarcati rapiditatea convergentei. 4.2.2. Introduceti: 0 .99 0.01 T=  , 1   0

P0 = [1 0].

Convergenta catre vectorul stationar este foarte lenta. De ce ? 4.2.3. Introduceti: 0 .2 0 .8  T=  , 0  1

P0 = [1 0].

Convergenta este oscilanta. Dupa 30 de pasi amplitudinea oscilatiilor este mai mica decât 0.001. Care este cauza acestor oscilatii atenuate ? 4.2.4. Introduceti: 0 .01 0.99  T=  , 0   1

P0 = [1 0].

Dupa 450 de pasi, amplitudinea oscilatiei ramîne relativ mare. Ea este mai mica doar decât 0.01. Care este cauza acestei convergente încetinite? Modificati vectorul P0 schimbând valorile între ele. Ce diferenta se observa? Remarcati ca dupa 1000 de pasi doar primele 3 zecimale ale probabilitatilor sunt stationare. Reprezentati grafic variatia probabilitatilor în timp. 4.3. Sursa Markov cu trei stari. Parcurgeti urmatoarele exemple si retineti concluziile acestora.

8

4.3.1. Introduceti: 0.01 0 .98 0.01  T = 0 .98 0.01 0.01  , 0.01 0.01 0 .98 

P0 = [0 1 0].

Dupa 150 de pasi se ajunge la stationaritate. Convergenta este oscilanta. Perioada oscilatiilor este 2. De ce? Observati ca Pn(3) converge monoton. 4.3.2. Introduceti: 0.01 0 .98 0.01  T = 0.01 0.01 0 .98  , 0 .98 0.01 0.01 

P0 = [0 1 0].

Dupa 150 de pasi se ajunge la stationaritate. Convergenta este oscilanta. Perioada oscilatiilor este 3. De ce? 4.3.3. Introduceti: 0 .98 0.01 0.01  T = 0.01 0 .98 0.01  , 0.01 0.01 0 .98 

P0 = [0 1 0 ].

Convergenta este monotona si lenta. De ce? Observati ca p ii >> pij, i ≠ j. În cazurile anterioare când aparea convergenta oscilanta lenta se remarca o preponderenta a valorilor unor probabilitati. Schimbati vectorii initiali pentru fiecare caz. Ce diferente apar? Ce diferente apar daca valorile preponderente devin unitare? 4.4. Sursa Markov cu patru stari. Parcurgeti urmatoarele exemple si retineti concluziile acestora. 4.4.1. Introduceti: 0 .01 0 .01 T=  0 .01  0 .97

0.01 0 .01  0 .01 0 .97 0 .01  , 0 .01 0.01 0 .97   0 .01 0.01 0 .01  0.97

P0 = [1 0 0 0]

Convergenta este oscilanta cu perioada 4. Toate valorile converg oscilant. Convergenta este mai rapida decât la sursa cu trei stari. Explicati aceste observatii. 4.4.2. Introduceti: 0 .01 0 .01 T=  0 .97  0 .01

0.01 0 .01  0 .01 0 .97 0 .01  , 0 .01 0.01 0 .01   0 .01 0.01 0 .97  0.97

P0 = [1 0 0 0 ]

În timp ce Pn(1), Pn(2) si Pn(3) converg oscilant cu perioada 3, Pn(4) converge monoton. De ce? Vectorul stationar este atins dupa aproximativ 100 de pasi. 4.4.3. Introduceti:

9

0 .01 0 .97 T=  0 .01  0 .01

0.01 0 .01  0 .01 0.01 0 .01  , 0 .01 0 .97 0 .01   0 .01 0.01 0 .97  0.97

P0 = [1 0 0 0 ]

Observati ca Pn(1) si Pn(2) converg oscilant cu perioada 2 pe când Pn(3) si Pn(4) converg monoton. Explicati. Construiti o matrice T si un vector P 0 pentru care toate componentele vectorului Pn converg monoton. Modificati vectorii P 0 pentru fiecare caz si constatati diferentele. Ce se întâmpla daca valorile preponderente devin unitare ? 4.5. Stationarizarea sursei Markov cu 2 stari. Procesul de emisie poate fi facut stationar fie modificând matricea T, fie vectorul initial P 0. 4.5.1. Determinarea vectorului distributiei de echilibru. 4.5.1.1. Introduceti: 0 .5 0.5  T=   ; se obtine w = [0.5 0.5] = Pst. 0 .5 0.5  Verificati acest rezultat întorcându-va la optiunea 2 din meniu. Verificarile se pot face în doua feluri. Într-o prima varianta P 0 = Pst si Pn = Pst în orice moment. A doua varianta permite introducerea unui vector initial oarecare urmând a se determina vectorul limita de convergenta citind Pn pentru valori mari ale lui n. A doua varianta este preferata atunci când convergenta este rapida sau vectorul stationar are multe zecimale nenule. 4.5.1.2. Introduceti: 0 .5 0.5  T=  ; se obtine w = [0.66 0 .33 ] = Pst. 0  1 Verificati aceste valori. Daca verificati prin metoda a doua veti observa o convergenta oscilanta. 4.5.1.3. Introduceti: 0 .5 0.5  T=  ; se obtine w = [0 1] = Pst. 1  0 Explicati acest rezultat. Retineti ca aflarea vectorului distributiei de echilibru se poate face folosind optiunea 2 din meniu, citind vectorul Pn pentru n foarte mare. 4.5.2. Determinarea matricii de tranzitie. 4.5.2.1. Se impune: w = [0.5 0 .5] = Pst. Construiti doua matrici de tranzitie care sa aiba acest vector al distributiei de echilibru. Daca se alege l = 0.5 rezulta 0 .5 0.5  T1 =  , 0 .5 0.5 

10

iar daca l = 0.7 rezulta 0 .7 0.3  T2 =  . 0.3 0 .7  Verificati aceste rezultate. Observati ca matricea T1 este cea indicata pentru studiu la optiunea 2. 4.5.2.2. Se impune: w = [0.6 0.4 ] = Pst. Construiti doua matrici de tranzitie care sa aiba acest vector stationar. Daca se alege l = 0.5 rezulta 0 .66 0.33  T1 =  ,  0 .5 0 .5  iar daca l = 0.1 rezulta 0 .4 0 .6  T2 =  . 0 .9 0.1 4.5.2.3. Se impune: w = [0 1] = Pst. De ce ramân la alegere componentele specificate in mesaj? 4.6. Stationarizarea sursei Markov cu trei stari. 4.6.1. Determinarea vectorului distributiei de echilibru. Introduceti: 0.99 0 .01  0  T = 0 .01 0 0.99  ; se obtine w = [0.3345 0 0 .01 0 .99

0.331 0 .3345 ] = Pst.

Verificati acest rezultat. Convergenta oscilanta lenta întârzie citirea vectorului distributiei de echilibru în cazul folosirii celei de a doua metode de verificare. În aceasta situatie se prefera prima metoda de verificare. 4.6.2. Determinarea matricii de tranzitie. Introduceti vectorul stationar determinat înainte. Construiti 5 matrici de tranzitie care sa aibaa ca vector al distributiei de echilibru vectorul impus. Acest lucru poate fi realizat alegând: λ1 = 0,

λ2 = 0,

λ3 = 0.1,

λ4 = 0.9.

Se va obtine matricea de la care s-a pornit. Valorile parametrilor λk pot fi modificate. Pentru exemplificare, introduceti pe rând: λ1 = 0, λ1 = 0, λ1 = 0, λ1 = 0,

λ2 = 0,

λ3 = 0.1, λ4 = 0.95, λ2 = 0, λ3 = 0.1, λ4 = 0.8, λ2 = 0, λ3 = 0.1, λ4 = 0.3, λ2 = 0, λ3 = 0.1, λ4 = 0.

Ce se întâmpla daca se introduce λ3 = 0 în seturile de valori de mai sus? Verificati rezultatele obtinute. Încercati sa modificati parametrii λ1 si λ 2.

11

Retineti ca, odata cu cresterea numarului de stari, exista tot mai multe posibilitati de construire a unei matrici de tranzitie când se impune Pst. Libertatea de constructie pare diminuata mult de greutatea alegerii parametrilor variabili asa încât matricea T sa fie o matrice de tranzitie.

5. Întrebari 5.1. Ce este o sursa Markov de ordinul 1? 5.2. Care este diferenta între starile si simbolurile unei surse Markov de ordinul 1? Dar pentru o sursa cu memorie de ordin superior? 5.3. Cum evolueaza procesul de emisie al unei asemenea surse? 5.4. Când apare convergenta monotona sau oscilanta? 5.5. În ce conditii o convergenta este lenta? 5.6. Este posibila o convergenta oscilanta cu perioada 4 la o sursa cu doua stari? Dar la o sursa cu trei stari? De ce? 5.7. Cum se poate obtine un proces de emisie stationar? 5.8. De ce exista mai multe matrici de tranzitie care au acelasi vector al distributiei de echilibru? 5.9. Care este diferenta între o stare tranzitorie si o stare absorbanta? 5.10. În ce conditii poate fi calculata entropia unei surse Markov?

12