UNIVERSITATEA POLITEHNICA DIN TIMIOARA FACULTATEA DE ELECTRONIC I TELECOMUNICAII DEPARTAMENTUL DE COMUNICAII

MODELARE STATISTIC I STOCASTIC

Lanuri Markov- Proiect -

Coordonator: Conf. Dr. ROMEO NEGREA Studeni: GIEA IRINA, an I Master, IRT GROZA ALIN, an I Master, IRT

TIMIOARA 2011

1. IntroducereLanurile Markov finite i omogene reprezint modelul matematic care pstreaz numai amintirea cea mai recent despre trecut (proprietatea Markov) i ale crei probabiliti condiionate sunt invariante n timp (omogenitate). Exist 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 urn fr revenire). n cazul acestui din urm tip de experiment se pot distinge dou subcazuri extreme: - O extrem e reprezentat de faptul c probabilitile rezultatelor la un moment dat depind 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. Fie sursa de informaie S cu alfabetul finit S = { , , }. Pentru a studia evoluia n timp a sursei se definete o variabil aleatoare X( ) = X(n) cu valori n S (unde sau n indic momentele de timp). Nu se cunoate n general evoluia n timp sub forma: Sau X( ), X( ), X( ) X(0), X(1), X(n)

Ci doar probabilitile: P{X( ) = , , X( ) = , , X( ) = }

Lanul Markov finit i omogen este un ir de variabile aleatoare dependente, care au proprietile: P{X( ) = / X( ) = , X( ) = , , X( ) = }= = P{X( ) = /X( ) = } proprietatea Markov = P{ / } proprietatea de omogenitate

Proprietatea Markov indic existena memoriei cu un singur pas, adic ntreg trecutul sursei este cuprins n starea cea mai recent. Omogenitatea indic independena de timp a tranziiilor. Matricea Markov (a tranziiilor/ a probabilitilor de trecere) cuprinde toate probabilitile 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 strile i arcele sunt tranziiile. Exemplu:S p111

p1/1

p2/1 sau p12 p1/2 sau 1/3S 1 1

S 2 p21p22

p2/2

1/2S 3

2/3S 2

Unde T =

1/2

1

Dac unei stri i se asigneaz un singur simbol de ieire, adic numrul strilor este egal cu numrul simbolurilor alfabetului, sursa Markov este de ordinul 1, un simbol emis fiind condiionat doar de simbolul precedent. Exemplu: sursa Markov binar simetricS 0

1-p 1-p

p

S 1

p

T=

Dac un simbol este condiionat de mai multe simboluri precedente, numrul strilor crete. Astfel, o surs binar care furnizeaz un simbol condiionat de dou simboluri precedente se caracterizeaz prin 4 stri, condiionate de dou simboluri precedente. s1 00, s2 01, s3 10, s4 11 n general ( , ). Numrul de stri poate fi mai mare dect numrul elementelor alfabetului sursei, caz n care un simbol de ieire poate corespunde la mai multe stri. La sursa Markov de ordinul 2, unei stri i se asigneaz 2 simboluri de ieire. 1.1 Probabiliti de trecere n mai muli pai: Probabilitatea de trecere din starea = p(X(n+m) = extinde i n acest caz Probabilitatea de trecere din starea = sau = n starea n 2 pai: n starea n m pai:

/ X(n) =

) omogenitatea se

Probabilitatea de trecere n 2 pai pe orice cale: = Se observ c trecere): . sau =

sunt elementele lui M (puterea a 2-a a matricii de

Se demonstreaz c: , n, m N, i, j S relaiile Chapman Kolmogorov

Sau Fiind dat un lan Markov prin repartiia de probabilitate iniial =[ ] i matricea M de trecere, atunci probabilitatea ca sistemul s ajung n n pai/treceri, ntr-o anumit stare , pornind din starea iniial este:

Tipuri de stri: Staionar: , deoarece probabilitile condiionate de tranziie 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 lanurilor Markov:1.

Regulat: dac N a.. s fie o matrice regulat (s aib toate elementele strict cresctoare). Ergotic/Staionar: probabilitile de trecere n n pai converg, cnd n, spre limite independente de starea iniial. = unde = probabilitatea asimptotic a strii; nu depinde de starea iniial/de pornire. Matricea strii staionare este: =[ ],j= i =1

2.

i reprezint repartiia de echilibru/de probabilitate a strii staionare, fiind o matrice cu toate liniile identice cu :

Condiia necesar i suficient ca s fie distribuia de echilibru a unei surse Markov este ca: *M= sau *T= , =1 Adic este un vector propriu al matricii de tranziie. Se demonstreaz c: Pentru un lan Markov staionar, repartiia de probabilitate a strii staionare este unic. Dac un lan Markov e regulat, atunci el admite stare de staionaritate.3.

Absorbant: dac are cel puin o stare absorbant, pentru care (acest tip de lan nu poate fi regulat).

=1

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. Notm succesiunea = i= (numrul total de succesiuni distincte i de lungime m fiind ). Rezult urmtoarele relaii: Cantitatea de informaie obinut la emisia lui : i( )= Cantitatea medie de informaie obinut la emisia oricrui simbol condiionat de succesiunea : Unde c = chain Cantitatea medie de informaie obinut la emisia oricrui simbol condiionat de orice succesiune reprezint entropia sursei cu memorie de m pai:

Unde

=

Observaii: Dac = regsim formula pentru surse discrete fr memorie. este ntotdeauna mai mic dect cea corespunztoare aceleiai surse, dar fr memorie, deoarece nedeterminarea medie referitoare la simbolul scade datorit corelaiei dintre simbolurile . Aplicaii ale surselor Markov: Modelarea unei limbi naturale Modelarea semnalului vocal Modelarea imaginilor TV Observaii: Cunoaterea entropiei sursei permite compresia sursei Lanurile Markov sunt aplicate n dispozitivele de sincronizare din telefonia numeric, recunoaterea semnalului vocal, reele de comunicaii de date.

2.Aplicaii1. Se consider lanul Markov avnd distribuia iniial p0 i matricea probabilitilor de trecere M.

0 1 2 p0 = 1 1 1 2 4 4 0 1 M= 4 1 4Rezolvare Se calculeaz probabilitile1 1 p 0 , p1

3 4 1 4 1 2

1 4 1 2 1 4

S se calculeze p1 i s se reprezinte graful tranziiilor.

i

p1 . 2

0 1 2 p1 = 1 1 1 p0 p1 p2 Probabilitatea1 p0

se calculeaz cu formula:1 1 1 1 1 1 0 + + = = 0.1250 2 4 4 4 4 8

1 0 0 p0 = P( X 1 = 0) = p0 p00 + p10 p10 + p2 p20 =

Probabilitatea

1 p1

se calculeaz cu formula:1 3 1 1 1 1 9 + + = = 0.5625 2 4 4 4 4 2 16

1 0 0 p1 = P ( X 1 = 1) = p0 p01 + p10 p11 + p2 p21 =

Probabilitatea

p1 2

se calculeaz cu formula:1 1 1 1 1 1 5 + + = = 0.3125 2 4 4 2 4 4 16

0 0 p1 = P ( X 1 = 2) = p0 p02 + p10 p12 + p2 p22 = 2

Se obine p1:

0 1 2 p1 = 1 9 5 8 1 16 6n figura urmtoare se prezint graful tranziiilor:

1/4 1/4 3/4 0 1/4 1/4 1/2 2 1/4 1/2 1

Programul MATLAB care rezolv Aplicaia 1 este prezentat n Anexa 1.

2. Juctorul A dispune de a RON, iar juctorul B de b RON. A ctig o partid cu probabilitatea p i primete 1 RON de la B, iar B ctig o partid cu probabilitatea q = 1 - p i n acest caz A i pltete 1 RON. Jocul se oprete cnd unul din juctori rmne fr bani. Care este probabilitatea ca juctorul A s fie cel ruinat i care este durata medie a jocului ? (numeric: a=30, b=10, p=1/3, q=2/3) Rezolvare Notm cu c = a + b capitalul cumulat al celor doi juctori i c=a+b suma de care dispune juctorul A dup partida a n-a. Evident{Xn} formeaz un lan Markov cu mulimea strilor {0, 1, 2...c}. Strile 0 i c formeaz dou clase de stri tranziente. Lanul fiind finit, jocul se va termina mai devreme sau mai trziu prin ruinarea unuia din juctori (la juctorul A dac absorbia se produce n {0} sau a lui B, dac absorbia are loc n {c}).a c Determinm probabilitatea p a = p(a,0) =x a = , 1 c

unde

=q / p .

Pentru cazul particular n care p=q=1/2, se obine

p ( a,0) =1 a / c .

Valoarea medie a jocului se determin cu formulama = p ( a,0) + (c a )

unde

= c (q p ) 1

i

= q p ) 1 . (m a = a (c a ) .

Pentru cazul particular n care p=q=1/2, se obine

Numeric: Pentru a=30, b=10, p=1/3, q=2/3 rezult c jocul dureaz ma= 89.8 partide. Programul MATLAB care rezolv Aplicaia 2 este prezentat n Anexa 2.

3. Evoluia vremii: ntr-o staie meteo vremea este observat zilnic la aceiai or: s1=soare, s2=nori, s3=ploaie. Pe baza observaiilor zilnice se determin matricea probabilitilor de trecere dintr-o starea n alta, M.

0.6 0.2 0.2 M = 0.3 0.4 0.3 0.2 0.2 0.6 a) Considernd c azi este o zi cu soare, s se determine probabilitatea ca prognoza urmtoarelor 7 zile s fie: soare soare nori soare nori ploaie soare. b) S se calculeze probabilitatea ca timpul s rmn 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 probabiliti: prima este cea aferent primei zile (are valoarea 1 deoarece timpul zilei anterioare este cunoscut), urmtoarele 3 sunt probabilitile determinate de strile anterioare corespunztoare celor 3 zile de soare i ultima probabilitate presupune schimbarea vremii din cele 3 zile de soare. Probabilitatea se calculeaz utiliznd formula: p = p( ) p( = 1 0,2 ) p( 0,6 ) p( 0,6 ) [1 - p( [1 - 0,6] = )] =

=2,88 10 -2 Programul MATLAB care rezolv Aplicaia 3 este prezentat n Anexa 3.

3.AnexeANEXA 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 castiga 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 plateste 1 RON. Jocul se opreste 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

% Evoluia vremii: ntr-o staie meteo vremea este observat zilnic la aceiai or: s1=soare, s2=nori, s3=ploaie. % Pe baza observaiilor zilnice se determin matricea probabilitilor de trecere dintr-o starea n alta, M. % a)S se determine probabilitatea ca prognoza urmtoarelor 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 rmn nneschimbat un numar exact de zile, dac se cunoaste vremea n ziua anterioar. % Exemplu: S se calculeze probabilitatea ca timpul s rmn 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))*[1M(vreme,vreme)];

4.Bibliografie1.

Negrea Romeo, Modelare statistic i stocastic- suport de curs, Universitatea Politehnica din Timioara, 2011. Gvrua Pacu, Negrea Romeo, Cdariu Liviu, Ciurdariu Loredana, Matematici pentru ingineri,Edirura Politehnica, Timi;oara, 2008. Naforni Miranda, Teoria Informaiei i codrii - suport de curs, Universitatea Politehnica din Timioara, 2009.

2.

3.

4. Vigoda Eric, Markov Chains, University of Chicago, 20035.

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