Surse discrete Markov cu memorie de ordinul intai

Surse discrete Markov cu memorie de ordinul întâi

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 x₁,x₂,...,x_i,...., pe care le emite, cuvintele care se constituie cu aceste simboluri în numar finit, alfabetul aferent ca totalitatea simboluri 151g620b lor 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₁ => 00, S₂ => 01, S₃ => 10 si S₄ => 11. Se spune ca starii S₁ i se asigneaza dubletul 00, starii S₂ = 01 etc.

O sursa cu memorie de ordinul m este o sursa cu constrângeri probabilistice, distributia de probabilitate având elemente de forma:

,

adica emisia unui simbol este conditionata de m simboluri precedente. Daca alfabetul sursei contine D simboluri, o sursa cu memorie de ordinul m are stari.

Starii sursei i se asigneaza secventa de m simboluri:

.

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 , unde elementele , numite stari, sunt variabile aleatoare discrete care iau valori în alfabetul starilor , iar dependenta satisface conditia Markov:

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

care iau valori în alfabetul finit al sursei

prin tranzitii succesive prin sirul de stari

.

sirul de stari constituie un lant Markov finit, luând valori în alfabetul starilor

cu o distributie de probabilitati a starii initiale S₀

,

adica

.

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

,

astfel încât, pe baza unei functii

,

se obtine

cu distributia de probabilitati simultane având proprietatea de stationaritate

.

Ori de câte ori lantul intern Markov intra într-o noua stare, sursa livreaza la iesire simbolul corespunzator specificat de functia .

Î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 S_j, independente de mometul de timp,

,

constituie matricea de tranzitie T:

.

De exemplu, pentru graful sursei din fig. 1 se obtine

Fig. 1. Sursa ireductibila

Matricea T este o matrice stochastica, deci

,

adica suma elementelor pe fiecare linie este 1.

Distributia de probabilitate a starilor la momentul n este data de matricea

,

unde reprezinta probabilitatea ca sursa sa se gaseasca în starea , la momentul n:

,

sau înca:

.

Rezulta deci:

Daca se noteaza prin P₀ matricea linie a probabilitatilor starilor initiale

,

atunci rezulta

Î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 P_n se poate scrie:

,

unde w_j este independent de i. Numarul w_j se numeste probabilitatea asimptotica pentru starea s_j, iar matricea linie

este distributia de echilibru, unde

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 , atunci

.

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:

si este o marime marginita deoarece

( reprezinta numarul D al simbolurilor alfabetului X)

Entropia unei surse Markov ergodice unifilare este:

,

unde r este numarul de stari si 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₀, 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,

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:

T = , P₀ = .

Dupa 5 pasi se ajunge la vectorul stationar printr-o convergenta monotona. Remarcati rapiditatea convergentei.

4.2.2. Introduceti:

T = , P₀ = .

Convergenta catre vectorul stationar este foarte lenta. De ce ?

4.2.3. Introduceti:

T = , P₀ = .

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:

T = , P₀ = .

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 P₀ 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.

4.3.1. Introduceti:

T = , P .

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:

T = , P₀ = .

Dupa 150 de pasi se ajunge la stationaritate. Convergenta este oscilanta. Perioada oscilatiilor este 3. De ce?

4.3.3. Introduceti:

T = , P₀ = .

Convergenta este monotona si lenta. De ce?

Observati ca p_ii >> p_ij, 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:

T = , P₀ =

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:

T = , P₀ =

Î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:

T = , P₀ =

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₀ pentru care toate componentele vectorului Pn converg monoton. Modificati vectorii P₀ 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₀.

4.5.1. Determinarea vectorului distributiei de echilibru.

4.5.1.1. Introduceti:

T = ; se obtine w = = Pst.

Verificati acest rezultat întorcându-va la optiunea 2 din meniu. Verificarile se pot face în doua feluri. Într-o prima varianta P₀ = 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:

T = ; se obtine w = = Pst.

Verificati aceste valori. Daca verificati prin metoda a doua veti observa o convergenta oscilanta.

4.5.1.3. Introduceti:

T = ; se obtine w = = Pst.

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 = = Pst.

Construiti doua matrici de tranzitie care sa aiba acest vector al distributiei de echilibru.

Daca se alege l = 0.5 rezulta

T₁ = ,

iar daca l = 0.7 rezulta

T₂ = .

Verificati aceste rezultate.

Observati ca matricea T1 este cea indicata pentru studiu la optiunea 2.

4.5.2.2. Se impune:

w = = Pst.

Construiti doua matrici de tranzitie care sa aiba acest vector stationar.

Daca se alege l = 0.5 rezulta

T₁ = ,

iar daca l = 0.1 rezulta

T₂ = .

4.5.2.3. Se impune:

w = = 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:

T = ; se obtine w = = 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:

l l = 0, l l

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

l l l l

l = 0, l l l

l l = 0, l l

l = 0, l = 0, l l

Ce se întâmpla daca se introduce l = 0 în seturile de valori de mai sus?

Verificati rezultatele obtinute. Încercati sa modificati parametrii l si l

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?