75860846 lanturi markov

UNIVERSITATEA “POLITEHNICA” DIN TIMIŞOARA

FACULTATEA DE ELECTRONICĂ ŞI TELECOMUNICAŢII

DEPARTAMENTUL DE COMUNICAŢII

MODELARE STATISTICĂ ŞI STOCASTICĂ

Lanţuri Markov- Proiect -

Coordonator:Conf. Dr. ROMEO NEGREA

Studenţi:GIEA IRINA, an I Master, IRT

GROZA ALIN, an I Master, IRT

TIMIŞOARA2011

1. Introducere

Lan urile Markov finite i omogene reprezintă modelul matematic careț ș păstrează numai amintirea cea mai recentă despre trecut (proprietatea Markov) i ale cărei probabilită i condi ionate sunt invariante în timp (omogenitate).ș ț ț

Există o succesiune de experimente cu aceleaşi rezultate posibile. Prin urmare, se va considera că t este un moment de timp care ia valorile 1, 2, 3, …, n. Această succesiune redă secvenţa de experimente. Pentru fiecare moment, rezultatele posibile vor fi notate 1, 2, …, m (m - număr finit). Cele m rezultate posibile vor fi numite stările în care se poate afla sistemul la un moment dat. Unitatea de măsură pentru momentele de timp succesive t depinde de sistemul studiat.

Dintre tipurile de astfel de secvenţe îl putem menţiona pe acela în care probabilităţile 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 probabilităţile rezultatelor la un moment dat depind de rezultatele din experienţele anterioare (de exemplu: extragerile succesive din urnă fără revenire). În cazul acestui din urmă tip de experiment se pot distinge două subcazuri extreme:

- O extremă e reprezentată de faptul că probabilităţile rezultatelor la un moment dat depind de rezultatele tuturor experimentelor precedente din secvenţă;

- Cealaltă extremă a nivelului de dependenţă este atunci când probabilităţile rezultatelor la un moment dat depind doar de rezultatele experimentului precedent. În această situaţie secvenţa de experimente se numeşte proces (lanţ) Markov.

Fie sursa de informa ie S cu alfabetul finit S = ț { , , … }. Pentru a studia evolu ia în timp a sursei se define te o variabilă aleatoare X(ț ș ) = X(n) cu valori în S (unde sau n indică momentele de timp). Nu se cunoa te înș general evolu ia în timp sub forma:ț

X( ), X( ), … X( )Sau X(0), X(1), … X(n)

Ci doar probabilită ile:ț

P{X( ) = , … , X( ) = , … , X( ) = }

Lan ul Markov finit i omogen este un ir de variabile aleatoareț ș ș dependente, care au proprietă ile:ț

P{X( ) = / X( ) = , X( ) = , … , X( ) = }= = P{X( ) = /X( ) = } ← proprietatea Markov = P{ / } ← proprietatea de omogenitate

Proprietatea Markov indică existen a memoriei cu un singur pas, adicăț întreg trecutul sursei este cuprins în starea cea mai recentă. Omogenitatea indică independen a de timp a tranzi iilor.ț ț

Matricea Markov (a tranzi iilor/ a probabilită ilor de trecere) cuprindeț ț toate probabilită ile de trecere dintr-o stare ț într-o stare .

M = P( / ) = [ ] =

Unde = 1, ∀ i = este o matrice stochastică.

Sau T = P( / ) = [ ] =

Unde = 1, ∀ i = este o matrice stochastică.O sursă Markov poate fi reprezentată printr-un graf unde nodurile sunt

stările i arcele sunt tranzi iile.ș țExemplu:

p1/1 p2/1 sau p12 p2/2

p11 p1/2 sau p21p22

1/3

1/2 2/3 Unde T =

1/2 1

S1

S2

S11

S3 S

2

Dacă unei stări i se asignează un singur simbol de ie ire, adică numărulș stărilor este egal cu numărul simbolurilor alfabetului, sursa Markov este de ordinul 1, un simbol emis fiind condi ionat doar de simbolul precedent.ț

Exemplu: sursa Markov binară simetrică

1-p

p p T =

1-p

Dacă un simbol este condi ionat de mai multe simboluri precedente,ț numărul stărilor cre te. Astfel, o sursă binară care furnizează un simbolș condi ionat de două simboluri precedente se caracterizează prin 4 stări,ț condi ionate de două simboluri precedente.ț

s1 → 00, s2 → 01, s3 → 10, s4 → 11

În general → ( , ). Numărul de stări poate fi mai mare decât numărul elementelor alfabetului sursei, caz în care un simbol de ie ire poateș corespunde la mai multe stări. La sursa Markov de ordinul 2, unei stări i se asignează 2 simboluri de ie ire.ș

1.1 Probabilită i de trecere în mai mul i pa i:ț ț ș

• Probabilitatea de trecere din starea în starea în „m” pa i:ș

= p(X(n+m) = / X(n) = ) omogenitatea se

extinde i în acest cazș

• Probabilitatea de trecere din starea în starea în 2 pa i:ș

= sau =

• Probabilitatea de trecere în 2 pa i pe orice cale:ș

= sau =

Se observă că sunt elementele lui M² (puterea a 2-a a matricii de

trecere): .

S0

S1

Se demonstrează că:

, ∀ n, m ∈ N, ∀ i, j ∈ S

relațiile Chapman – Kolmogorov

Sau

Fiind dat un lan Markov prin reparti ia de probabilitate ini ială ț ț ț =[] i matricea M de trecere, atunci probabilitatea ca sistemul să ajungăș

în „n” pa i/treceri, într-o anumită stare ș , pornind din starea ini ială este:ț

Tipuri de stări:• Sta ionarăț : , deoarece probabilită ile condi ionate deț ț

tranzi ie sunt invariante în timp.ț• Ireductibilă : = 0, starea este tranzitorie, sursa va ajunge la

un moment dat într-o stare din care nu mai poate accesa .• Reductibilă : orice stare este accesibilă din orice altă stare i esteș

descrisă de un lan Markov reductibil.ț

1.2 Clasificarea lan urilor Markov:ț

1. Regulat : dacă ∃ ∈ N a.î. să fie o matrice regulată (să aibă toate elementele strict crescătoare).

2. Ergotic/Sta ionarț : probabilită ile de trecere în n pa i converg, cândț ș n→∞, spre limite independente de starea ini ială.ț

unde = probabilitatea asimptotică a stării; nu depinde de starea ini ială/de pornire.țMatricea stării sta ionare este:ț

= [ ] , j = i ș = 1

=

i reprezintă reparti ia de echilibru/de probabilitate a stăriiș ț sta ionare, fiind o matrice cu toate liniile identice cu ț :

Condi ia necesară i suficientă ca ț ș să fie distribu ia de echilibru aț unei surse Markov este ca:

* M = sau * T = , = 1Adică este un vector propriu al matricii de tranzi ie.țSe demonstrează că:

• Pentru un lan Markov sta ionar, reparti ia deț ț ț probabilitate a stării sta ionare este unică.ț

• Dacă un lan Markov e regulat, atunci el admite stareț de sta ionaritate.ț

3. Absorbant : dacă are cel pu in o stare absorbantă, pentru care ț =1 (acest tip de lan nu poate fi regulat).ț

1.3 Entropia unei surse Markov de ordinul m:

Fie o sursă cu alfabetul finit A = { }, j = , la care emisia simbolului m+1 depinde de m simboluri anterioare. Notăm succesiunea = i = (numărul total de succesiuni distincte i de lungime m fiind ș).

Rezultă următoarele rela ii:ț• Cantitatea de informa ie ob inută la emisia lui ț ț :

i( ) = - • Cantitatea medie de informa ie ob inută la emisia oricăruiț ț simbol condi ionat de succesiunea ț :

Unde c = chain• Cantitatea medie de informa ie ob inută la emisia oricăruiț ț simbol condi ionat de orice succesiune ț reprezintă entropia sursei cu memorie de m pa iș :

Unde =

Observa ii:ț • Dacă = regăsim formula pentru surse discrete fără memorie. • este întotdeauna mai mică decât cea corespunzătoare aceleia i surse, dar fără memorie, deoarece nedeterminarea medie referitoare laș simbolul scade datorită corela iei dintre simbolurile ț .

Aplica ii ale surselor Markov:ț• Modelarea unei limbi naturale• Modelarea semnalului vocal• Modelarea imaginilor TV

Observa ii:ț• Cunoa terea entropiei sursei permite compresia surseiș

• Lan urile Markov sunt aplicate în dispozitivele de sincronizare dinț telefonia numerică, recunoa terea semnalului vocal, re ele de comunica ii deș ț ț date.

2.Aplica iiț

1. Se consideră lanţul Markov având distribuţia iniţială p0 şi matricea probabilităţilor de trecere M.

=

4

1

4

1

2

1

210

0p

=

4

1

2

1

4

12

1

4

1

4

14

1

4

30

M

Să se calculeze p1 şi să se reprezinte graful tranziţiilor.

Rezolvare

Se calculează probabilităţile 1

0p , 1

1p şi 1

2p .

=

1

2

1

1

1

0

1

210

pppp

Probabilitatea 1

0p se calculează cu formula:

1250.08

1

4

1

4

1

4

1

4

10

2

1)0( 20

0

210

0

100

0

01

1

0 ==⋅+⋅+⋅=⋅+⋅+⋅=== ppppppXPp

Probabilitatea 1


5625.016

9

2

1

4

1

4

1

4

1

4

3

2

1)1( 21

0

211

0

101

0

01

1

1 ==⋅+⋅+⋅=⋅+⋅+⋅=== ppppppXPp

Probabilitatea 1


3125.016

5

4

1

4

1

2

1

4

1

4

1

2

1)2( 22

0

212

0

102

0

01

1

2 ==⋅+⋅+⋅=⋅+⋅+⋅=== ppppppXPp

Se obţine p1:

=

1 6

5

1 6

9

8

1

210

1p

În figura următoare se prezintă graful tranziţiilor:

Programul MATLAB care rezolvă Aplicaţia 1 este prezentat în Anexa 1.

2. Jucătorul A dispune de a RON, iar jucătorul B de b RON. A câştigă o partidă cu probabilitatea p şi primeşte 1 RON de la B, iar B câştigă o partidă cu probabilitatea q = 1 - p şi în acest caz A îi plăteşte 1 RON. Jocul se opreşte când unul din jucători rămâne fără bani. Care este probabilitatea ca jucătorul A să fie cel ruinat şi care este durata medie a jocului ? (numeric: a=30, b=10, p=1/3, q=2/3)

Rezolvare

Notăm cu c = a + b capitalul cumulat al celor doi jucători şi c=a+b suma de care dispune jucătorul A după partida a n-a. Evident{Xn} formează un lanţ Markov cu mulţimea stărilor {0, 1, 2...c}. Stările 0 şi c formează două clase de stări tranziente. Lanţul fiind finit, jocul se va termina mai devreme sau mai târziu prin ruinarea unuia din jucători (la jucătorul A dacă absorbţia se produce în {0} sau a lui B, dacă absorbţia are loc în {c}).

Determinăm probabilitatea c

ca

aa xappλλλ

−−===

1)0,( ,

unde pq /=λ .

Pentru cazul particular în care p=q=1/2, se obţine caap /1)0,( −= .

3/4

1/4

1/4

1/2

1/4

1/2

1/4

1/4

1

2

0

Valoarea medie a jocului se determină cu formula

)()0,( acapma −+= βα

unde 1)( −−= pqcα şi 1)( −−−= pqβ .

Pentru cazul particular în care p=q=1/2, se obţine )( acama −= .

Numeric: Pentru a=30, b=10, p=1/3, q=2/3 rezultă că jocul durează ma= 89.8 partide.


3. Evoluţia vremii: Într-o staţie meteo vremea este observată zilnic la aceiaşi oră: s1=soare, s2=nori, s3=ploaie. Pe baza observaţiilor zilnice se determină matricea probabilităţilor de trecere dintr-o starea în alta, M.

=

6.02.02.0

3.04.03.0

2.02.06.0

M

a) Considerând că azi este o zi cu soare, să se determine probabilitatea ca prognoza următoarelor 7 zile să fie: “soare – soare – nori – soare – nori – ploaie – soare”.

b) Să se calculeze probabilitatea ca timpul să rămână însorit doar 3 zile, dacă în ziua anterioară a plouat.

Rezolvare

a) Succesiunea de 7 zile este s1 s1 s2 s1 s2 s3 s1. Probabilitatea se calculează astfel:

p(s1) · p(s1|s1) · p(s1|s1) · p(s2|s1) · p(s1|s2) · p(s2|s1) · p(s3|s2) · p(s1|s3) =

= 1 · 0,6 · 0,6 · 0,2 · 0,3 · 0,2 · 0,3 · 0,2

= 2,592 · 10 -4

b) Avem o succesiune de 4 zile pentru care se calculează 5 probabilităţi: prima este cea aferentă primei zile (are valoarea 1 deoarece timpul zilei anterioare este cunoscut), următoarele 3 sunt probabilităţile determinate de stările anterioare corespunzătoare celor 3 zile de soare şi ultima probabilitate presupune schimbarea vremii din cele 3 zile de soare.

Probabilitatea se calculează utilizând formula:

p = p( ) · p( ) · p( ) · p( ) · [1 - p( )] =

= 1 · 0,2 · 0,6 · 0,6 · [1 - 0,6] =

=2,88 · 10 -2


3.Anexe

ANEXA 1

% Se considera p0=distributia initiala si M=matricea probabilitatilor de trecere.

% Sa se calculeze p1.

%Exemplu numeric:

%N=3;

%M=[0 3/4 1/4 ; 1/4 1/4 1/2 ; 1/4 1/2 1/4];

%p0=[1/2 1/4 1/4];

function p1=f(N,M,p0)

%initalizare cu zero a fiecarui element din p1 pentru calculul sumei

p1=zeros(1,3);

%utilizare index i pentru parcurgerea elementelor din p0

%utilizare indecsi i si j pentru parcurgerea elementelor din M

for i=1:N

for j=1:N

p1(i)=p1(i)+p0(j)*M(j,i);

end

end

ANEXA 2

% Jucatorul A dispune de a RON, iar jucatorul B de b RON. A ca»stiga o partida cu% probabilitatea p si primeste 1 RON de la B, iar B castiga o partida cu robabilitatea % q = 1 - p si in acest caz A ii plate»ste 1 RON. Jocul se opre»ste cand unul din % jucatori ramane fara bani. Care este probabilitatea ca jucatorul A sa fie cel ruinat si care este durata medie a jocului ?

function y=f(a,b,p,q)

%calcul suma totala de castig

c=a+b;

%verificarea probabilitati de castig a jucatorilor

if p==q

m=a*(c-a);

pa0=1-a/c;

else

lambda=q/p;

pa0=(lambda^a-lambda^c)/(1-lambda^c);

alfa=c*(q - p)^(-1);

beta=-(q - p)^(-1);

m=alfa*pa0+beta*(c-a);

%y(3)=alfa;

%y(4)=beta;

end

%afisare rezultate

y(1)=m;

y(2)=pa0;

ANEXA 3

% Evoluţia vremii: Într-o staţie meteo vremea este observată zilnic la aceiaşi oră: s1=soare, s2=nori, s3=ploaie. % Pe baza observaţiilor zilnice se determină matricea probabilităţilor de trecere dintr-o starea în alta, M.

% a)Să se determine probabilitatea ca prognoza următoarelor zile să fie o succesiune data. % Exemplu: "soare - soare - nori - soare - nori - ploaie - soare".% M=[0.6 0.2 0.2;0.3 0.4 0.3; 0.2 0.2 0.6];% s=[1 1 2 1 2 3 1];

% b) Să se calculeze probabilitatea ca timpul să rămână nneschimbat un numar exact de zile, dacă se cunoaste vremea în ziua anterioară.% Exemplu: Să se calculeze probabilitatea ca timpul să rămână însorit doar 3 zile, dacă în ziua anterioară a plouat.

function p=f(s,M, anterior, numar, vreme)

% punctul a)

% utilizare variabila pentru memorarea rezultatului intermediar

mem=1*M(s(1),s(1));

% parcurgere sir si calculul probabilitatii din matricea de trecere

for i=2:length(s)

mem=mem*M(s(i),s(i-1));

end

p(1)=mem

% punctul b)

% utilizare variabila pentru memorarea rezultatului intermediar

p(2)=1*M(anterior,vreme)*(M(vreme,vreme)^(numar-1))*[1-M(vreme,vreme)];

4.Bibliografie

1. Negrea Romeo, “Modelare statistică şi stocastică”- suport de curs, Universitatea Politehnica din Timişoara, 2011.

2. Găvruţa Paşcu, Negrea Romeo, Cădariu Liviu, Ciurdariu Loredana, “Matematici pentru ingineri”,Edirura Politehnica, Timi;oara, 2008.

3. Naforniţă Miranda, “Teoria Informaţiei şi codării” - suport de curs, Universitatea Politehnica din Timişoara, 2009.

4. Vigoda Eric, “Markov Chains”, University of Chicago, 2003

5. http://en.wikipedia.org/wiki/Markov_chain

http://en.wikipedia.org/wiki/Markov_chain

75860846 lanturi markov

Documents