Lanțul Markov
În matematică , un lanț Markov este un proces Markov în timp discret sau timp continuu și spațiu de stare discret. Un proces Markov este un proces stochastic care posedă proprietatea Markov : informațiile utile pentru prezicerea viitorului sunt cuprinse în întregime în starea actuală a procesului și nu depind de stările anterioare (sistemul nu are „memorie”). Procesele Markov sunt numite după inventatorul lor, Andrei Markov .
Un proces Markov în timp discret este o secvență de variabile aleatorii cu valori în spațiul de stare , pe care le vom nota în cele ce urmează. Valoarea este starea procesului în momentul de față. Aplicațiile în care spațiul de stare este finit sau numărabil sunt nenumărate: se vorbește atunci despre lanțul Markov sau despre lanțurile Markov cu spațiu de stare discret . Proprietățile esențiale ale proceselor generale Markov , de exemplu proprietățile recurenței și ergodicității , sunt mai simplu enunțate sau demonstrate în cazul lanțurilor Markov ale spațiului discret . Acest articol se referă tocmai la lanțurile Markov cu spațiu de stare discret .
X0,{\ displaystyle X_ {0},} X1,{\ displaystyle X_ {1},} X2,{\ displaystyle X_ {2},} X3, ...{\ displaystyle X_ {3}, \ \ dots}E{\ displaystyle E}Xnu{\ displaystyle X_ {n}}nu.{\ displaystyle n.}E{\ displaystyle E}
Andrei Markov a publicat primele rezultate despre lanțurile Markov din spațiul de stat finit în 1906 . O generalizare a unui spațiu infinit numărabil de stat a fost publicat de Kolmogorov în 1936 . Procesele Markov sunt legate de mișcarea browniană și ipoteza ergodică , două teme ale fizicii statistice care au fost foarte importante la începutul XX - lea secol .
Proprietate slabă Markov
Definiții
Aceasta este proprietatea caracteristică a unui lanț Markov: predicția viitorului din prezent nu este mai precisă prin informații suplimentare referitoare la trecut, deoarece toate informațiile utile pentru predicția viitorului sunt conținute în starea actuală a procesul. Proprietatea slabă Markov are mai multe forme echivalente care toate se ridică la observarea faptului că legea condițională a cunoașterii timpului trecut, adică cunoașterea este o funcție numai a:
Xnu+1{\ displaystyle X_ {n + 1}}(Xk)0≤k≤nu,{\ displaystyle \ left (X_ {k} \ right) _ {0 \ leq k \ leq n},}Xnu{\ displaystyle X_ {n}}∀nu≥0,∀(eu0,...,eunu-1,eu,j)∈Enu+2,P(Xnu+1=j∣X0=eu0,X1=eu1,...,Xnu-1=eunu-1,Xnu=eu)=P(Xnu+1=j∣Xnu=eu).{\ displaystyle {\ begin {align} \ forall n \ geq 0, \ forall (i_ {0}, \ ldots, i_ {n-1}, i, j) & \ in E ^ {n + 2}, \ \\ mathbb {P} {\ Big (} X_ {n + 1} = j & \ mid \, X_ {0} = i_ {0}, X_ {1} = i_ {1}, \ ldots, X_ {n - 1} = i_ {n-1}, X_ {n} = i {\ Big)} = \ mathbb {P} \ left (X_ {n + 1} = j \ mid X_ {n} = i \ right) . \ end {align}}}
O variantă comună a lanțurilor Markov este lanțul omogen Markov , pentru care probabilitatea de tranziție este independentă de :
nu{\ displaystyle n}∀nu≥1,∀(eu,j)∈E2,P(Xnu+1=j∣Xnu=eu)=P(Xnu=j∣Xnu-1=eu){\ displaystyle \ forall n \ geq 1, \ forall (i, j) \ în E ^ {2}, \ quad \ mathbb {P} (X_ {n + 1} = j \ mid X_ {n} = i) = \ mathbb {P} (X_ {n} = j \ mid X_ {n-1} = i)}
În restul articolului, vor fi luate în considerare numai lanțurile omogene Markov. Pentru o aplicație interesantă a lanțurilor Markov neomogene la optimizarea combinatorie , consultați articolul Recuocare simulată . Există o proprietate puternică Markov , legată de noțiunea de oprire a timpului : această proprietate puternică Markov este crucială pentru dovada rezultatelor importante (diverse criterii de recurență, legea puternică a numărului mare pentru lanțurile Markov). Este menționat în articolul „ Proprietatea Markov ”.
Criteriu
Criteriu fundamental - Fie o secvență de variabile aleatoare independente ale aceleiași legi, cu valori într-un spațiu și fie o hartă măsurabilă a în Să presupunem că secvența este definită de relația de recurență:
Da=(Danu)nu≥1{\ displaystyle Y = (Y_ {n}) _ {n \ geq 1}}F{\ displaystyle F}f{\ displaystyle f}E×F{\ displaystyle E \ times F}E.{\ displaystyle E.}X=(Xnu)nu≥0{\ displaystyle X = (X_ {n}) _ {n \ geq 0}}∀nu≥0,Xnu+1=f(Xnu,Danu+1),{\ displaystyle \ forall n \ geq 0, \ qquad X_ {n + 1} = f \ left (X_ {n}, Y_ {n + 1} \ right),}
și să presupunem că secvența este independentă de Atunci este un lanț Markov omogen.
Da{\ displaystyle Y}X0.{\ displaystyle X_ {0}.}X{\ displaystyle X}
Exemplu:
problema colectorului de autocolante :
Petit Pierre colectează portretele celor unsprezece jucători ai echipei naționale de fotbal, pe care le găsește pe autocolante în ambalajul batoanelor de ciocolată; de fiecare dată când cumpără o tabletă are o șansă de 1 din 11 să găsească portretul jucătorului nr (pentru toate ). Rețineți starea colecției Pierre Petit, după deschiderea ambalajului barei sale de ciocolată e . este un lanț Markov pornind de la , deoarece se încadrează în cadrul anterior pentru alegere de atunci
k{\ displaystyle k}k{\ displaystyle k}Xnu∈P([[1,11]]){\ displaystyle X_ {n} \ in {\ mathcal {P}} ([\! [1,11] \!])}nu{\ displaystyle n}X=(Xnu)nu≥0{\ displaystyle X = (X_ {n}) _ {n \ geq 0}}X0=∅{\ displaystyle X_ {0} = \ emptyset}F=[[1,11]], E=P(F), f(X,y)=X∪{y},{\ displaystyle F = [\! [1,11] \!], \ E = {\ mathcal {P}} (F), \ f (x, y) = x \ cup \ {y \},}Xnu+1=Xnu∪{Danu+1},{\ displaystyle X_ {n + 1} = X_ {n} \ cup \ {Y_ {n + 1} \},}
unde variabilele aleatoare sunt variabile aleatoare independente și uniforme pe : sunt numerele succesive ale vinietelor extrase din batoanele de ciocolată. Timpul mediu necesar pentru a finaliza colecția (aici numărul de comprimate pe care Petit Pierre trebuie să cumpere , în medie , pentru a completa colecția sa) este, pentru o colecție de vignete în total, în cazul în care este mii numărul armonic . De exemplu, batoanele de ciocolată.
Danu{\ displaystyle Y_ {n}}[[1,11]]{\ displaystyle [\! [1,11] \!]}NU{\ displaystyle N}NUHNU,{\ displaystyle N \, H_ {N},}HNU{\ displaystyle H_ {N}}NU{\ displaystyle N}11H11=33,2...{\ displaystyle 11 \, H_ {11} = 33,2 \ dots \ quad}
Note:
- Proprietatea Markov derivă din independența rămâne adevărată atunci când au legi diferite și când „relația de recurență” depinde de ipotezele făcute în plus față de independență sunt doar pentru a asigura omogenitatea lanțului de către Markov.Daeu ;{\ displaystyle Y_ {i} \;}Daeu{\ displaystyle Y_ {i}}Xnu+1=fnu(Xnu,Danu+1){\ displaystyle X_ {n + 1} = f_ {n} \ left (X_ {n}, Y_ {n + 1} \ right)}nu.{\ displaystyle n.}
- Criteriul este fundamental prin faptul că orice lanț omogen de Markov poate fi simulat printr-o recurență a formei pentru o funcție bine aleasă. Putem chiar alege și alege variabile independente și uniforme în intervalul [0,1], ceea ce este convenabil pentru studiul lanțurilor Markov folosind metodele Monte-Carlo .Xnu+1=f(Xnu,Danu+1),{\ displaystyle X_ {n + 1} = f \ left (X_ {n}, Y_ {n + 1} \ right),}f{\ displaystyle f}F=[0,1],{\ displaystyle F = [0,1],}Daj{\ displaystyle Y_ {j}}
Probabilități de tranziție
Definiție
Definiție - Numărul se numește probabilitatea State- la- tranziție de stat într - o singură etapă , sau probabilitatea State- la- tranziție de stat în cazul în care nu există nici o ambiguitate. Observăm adesea acest numărP(X1=j∣X0=eu){\ displaystyle \ mathbb {P} \ left (X_ {1} = j \ mid X_ {0} = i \ right)} eu{\ displaystyle i} j{\ displaystyle j} eu{\ displaystyle i} j,{\ displaystyle j,}peu,j:{\ displaystyle p_ {i, j}:}
peu,j=P(X1=j∣X0=eu).{\ displaystyle p_ {i, j} = \ mathbb {P} \ left (X_ {1} = j \ mid X_ {0} = i \ right).}
Numerele de familie se numește matricea de tranziție , nucleul de tranziție , sau operatorul de tranziție al lanțului Markov.
P=(peu,j)(eu,j)∈E2{\ displaystyle P = \ left (p_ {i, j} \ right) _ {(i, j) \ în E ^ {2}}}
Matricea de tranziție terminologică este cea mai utilizată, dar este adecvată, strict vorbind, numai atunci când, pentru un număr întreg Când este finit, de exemplu cardinal se pot număra întotdeauna elementele arbitrar de la 1 la ceea ce stabilește problema, dar imperfect, deoarece această renumerotare este contra-intuitivă în multe exemple.
nu≥1,{\ displaystyle n \ geq 1,} E={1,2,...,nu}.{\ displaystyle E = \ {1,2, \ ldots, n \}.}E{\ displaystyle E}nu,{\ displaystyle n,}E{\ displaystyle E}nu,{\ displaystyle n,}
Modelul Ehrenfest: cei doi câini și puricii lor:
Doi câini împart puricii după cum urmează: în fiecare moment, unul dintre purici este ales la întâmplare și apoi sare de la un câine la altul. Starea sistemului este descrisă de un element în care
NU{\ displaystyle N}NU{\ displaystyle N}X=(X1,X2,...,XNU)∈{0,1}NU,{\ displaystyle x = (x_ {1}, x_ {2}, \ dots, x_ {N}) \ in \ {0,1 \} ^ {N},}Xeu=0 sau 1 în funcție de cipul n∘ eu este pe primul sau pe al doilea câine.{\ displaystyle x_ {i} = 0 {\ text {sau}} 1 {\ text {în funcție de cipul n}} ^ {\ circ} \ i {\ text {este pe primul sau pe al doilea câine.} }}
La fel și elementele, dar numerotarea lor de la 1 la ar fi incomod să urmăm evoluția sistemului, care constă în alegerea uneia dintre coordonatele lui la întâmplare și schimbarea valorii sale. Dacă vrem să înțelegem sistemul mai puțin detaliat (deoarece nu suntem capabili să recunoaștem un cip de la altul), putem studia pur și simplu numărul de jetoane de pe câinele nr. 1, ceea ce înseamnă a alege din nou, pentru înțelegere, ar fi păcat să renumerotăm stările de la 1 la Notăm că pentru această nouă modelizare,
E{\ displaystyle E}2NU{\ displaystyle 2 ^ {N}}2NU{\ displaystyle 2 ^ {N}}NU{\ displaystyle N}X{\ displaystyle x}E={0,1,2,...,NU}.{\ displaystyle E = \ {0,1,2, \ dots, N \}.}NU+1.{\ displaystyle N + 1.}pk,k+1=NU-kNU și pk,k-1=kNU,{\ displaystyle p_ {k, k + 1} = {\ tfrac {Nk} {N}} {\ text {et}} p_ {k, k-1} = {\ tfrac {k} {N}},}
deoarece, de exemplu, numărul de jetoane de pe spatele câinelui nr. 1 merge de la k la k-1 dacă este unul dintre aceste k jetoane care este ales să sară, printre N jetoane prezente în „sistem”. Acest model este denumit mai des „ Modelul urnelor Ehrenfest ”. A fost introdus în 1907 de Tatiana și Paul Ehrenfest pentru a ilustra unele dintre „paradoxurile” care au apărut în bazele mecanicii statistice nașterii și pentru a modela zgomotul roz . Modelul urnei Ehrenfest a fost considerat de matematicianul Mark Kac ca fiind „probabil unul dintre cele mai instructive modele din toată fizica”.
În loc să renumerotăm stările de la 1, este, prin urmare, mai ergonomic în multe cazuri să acceptăm matrici finite sau infinite ale căror rânduri și coloane sunt „numerotate” folosind elementele Produsului a două astfel de „matrice” și , atunci este definit foarte natural de
E.{\ displaystyle E.}LA=(laeu,j)(eu,j)∈E2{\ displaystyle A = \ left (a_ {i, j} \ right) _ {(i, j) \ în E ^ {2}}}B=(beu,j)(eu,j)∈E2{\ displaystyle B = \ left (b_ {i, j} \ right) _ {(i, j) \ în E ^ {2}}}(LAB)eu,j=∑ℓ∈Elaeu,ℓbℓ,j,{\ displaystyle (AB) _ {i, j} = \ sum _ {\ ell \ in E} a_ {i, \ ell} b _ {\ ell, j},}
prin analogie cu formula mai clasică a produsului a două matrice pătrate de mărime nu,{\ displaystyle n,}
(LAB)eu,j=∑k=1nulaeu,kbk,j.{\ displaystyle (AB) _ {i, j} = \ sum _ {k = 1} ^ {n} a_ {i, k} b_ {k, j}.}
Proprietăți
Propoziție - Matricea de tranziție este stocastică : suma termenilor oricărui rând dă întotdeauna 1.
P=(peu,j)(eu,j)∈E2{\ displaystyle P = \ left (p_ {i, j} \ right) _ {(i, j) \ în E ^ {2}}}P{\ displaystyle P}∀eu∈E,∑j∈Epeu,j=1.{\ displaystyle \ forall i \ in E, \ quad \ sum _ {j \ in E} p_ {i, j} = 1.}
Propoziție - Legea lanțului Markov se caracterizează prin perechea alcătuită din matricea sa de tranziție și legea inițială (legea ): pentru că toată legea comună a este dată de
X=(Xnu)nu≥0{\ displaystyle X = \ left (X_ {n} \ right) _ {n \ geq 0}}P,{\ displaystyle P,}X0{\ displaystyle X_ {0}}nu≥1{\ displaystyle n \ geq 1}(X0,X1,...,Xnu){\ displaystyle (X_ {0}, X_ {1}, \ ldots, X_ {n})}P(X0=eu0,X1=eu1,...,Xnu-1=eunu-1,Xnu=eunu)=P(X0=eu0) peu0,eu1peu1,eu2...peunu-2,eunu-1peunu-1,eunu.{\ displaystyle \ mathbb {P} \ left (X_ {0} = i_ {0}, X_ {1} = i_ {1}, \ ldots, X_ {n-1} = i_ {n-1}, X_ { n} = i_ {n} \ right) = \ mathbb {P} \ left (X_ {0} = i_ {0} \ right) \ p_ {i_ {0}, i_ {1}} \, p_ {i_ { 1}, i_ {2}} \, \ ldots \, p_ {i_ {n-2}, i_ {n-1}} \, p_ {i_ {n-1}, i_ {n}}.}
Demonstrație
Prin inducție, la rangul 0,
P(X0=eu0)=P(X0=eu0).{\ displaystyle \ mathbb {P} \ left (X_ {0} = i_ {0} \ right) = \ mathbb {P} \ left (X_ {0} = i_ {0} \ right).}
La rând prin pozănu,{\ displaystyle n,}Pk=P(X0=eu0,X1=eu1,...,Xk-1=euk-1,Xk=euk),{\ displaystyle P_ {k} = \ mathbb {P} \ left (X_ {0} = i_ {0}, X_ {1} = i_ {1}, \ ldots, X_ {k-1} = i_ {k- 1}, X_ {k} = i_ {k} \ dreapta),}
PnuPnu-1=P(Xnu=eunu∣X0=eu0,X1=eu1,...,Xnu-1=eunu-1)=peunu-1,eunu,{\ displaystyle {\ frac {P_ {n}} {P_ {n-1}}} = \ mathbb {P} {\ Big (} X_ {n} = i_ {n} \ mid \, X_ {0} = i_ {0}, X_ {1} = i_ {1}, \ ldots, X_ {n-1} = i_ {n-1} {\ Big)} = p_ {i_ {n-1}, i_ {n} },}
în virtutea slabei proprietăți Markov, deci dacă are expresia așteptată, atunci și ea.
Pnu-1{\ displaystyle P_ {n-1}}Pnu{\ displaystyle P_ {n}}
Când studiați un anumit lanț Markov, matricea sa de tranziție este, în general, bine definită și fixată pe tot parcursul studiului, dar legea inițială se poate schimba în timpul studiului, iar notațiile trebuie să reflecte legea inițială luată în considerare în momentul respectiv: dacă la un moment al studiul considerăm un lanț Markov de distribuție inițială definit până atunci se notează probabilitățile și se notează așteptările
În special, dacă spunem că lanțul Markov începe de la probabilitățile sunt notate și se notează∀eu∈E,P(X0=eu)=μeu,{\ displaystyle \ forall i \ in E, \ quad \ mathbb {P} \ left (X_ {0} = i \ right) = \ mu _ {i}, \ quad}Pμ(...),{\ displaystyle \ mathbb {P} _ {\ mu} \ left (\ dots \ right), \ quad}Eμ[...].{\ displaystyle \ mathbb {E} _ {\ mu} \ left [\ dots \ right]. \ quad}P(X0=j)=1,{\ displaystyle \ mathbb {P} \ left (X_ {0} = j \ right) = 1, \ quad}j,{\ displaystyle j, \ quad}Pj(...),{\ displaystyle \ mathbb {P} _ {j} \ left (\ dots \ right), \ quad}Ej[...].{\ displaystyle \ mathbb {E} _ {j} \ left [\ dots \ right]. \ quad}
Puterile matricei de tranziție
Pentru probabilitatea de tranziție în pas, nu depinde de :
k≥1,{\ displaystyle k \ geq 1,}k{\ displaystyle k}P(Xnu+k=j∣Xnu=eu),{\ displaystyle \ mathbb {P} \ left (X_ {n + k} = j \ mid X_ {n} = i \ right),}nu{\ displaystyle n}
Propozitia - Matricea de tranziție în trepte , este egală cu puterea lea a matricei de tranziție Notă
k{\ displaystyle k} (P(Xnu+k=j∣Xnu=eu))(eu,j)∈E2,{\ displaystyle \ left (\ mathbb {P} \ left (X_ {n + k} = j \ mid X_ {n} = i \ right) \ right) _ {(i, j) \ în E ^ {2} },}k{\ displaystyle k}P.{\ displaystyle P.}peu,j(k)=P(Xnu+k=j∣Xnu=eu),{\ displaystyle p_ {i, j} ^ {(k)} = \ mathbb {P} \ left (X_ {n + k} = j \ mid X_ {n} = i \ right),}
și
Pk=(peu,j(k))(eu,j)∈E2.{\ displaystyle P ^ {k} = \ left (p_ {i, j} ^ {(k)} \ right) _ {(i, j) \ în E ^ {2}}.}
Demonstrație
Prin recurență. La rangul 1, este o consecință a omogenității lanțului Markov menționat deja în secțiunea Proprietatea Markov slabă :
P(Xnu+1=j∣Xnu=eu)=P(X1=j∣X0=eu).{\ displaystyle \ mathbb {P} \ left (X_ {n + 1} = j \ mid X_ {n} = i \ right) = \ mathbb {P} \ left (X_ {1} = j \ mid X_ {0 } = i \ dreapta).}
Rang k,{\ displaystyle k,}
P(Xnu=eu și Xnu+k=j)=∑ℓ∈EP(Xnu=eu,Xnu+k-1=ℓ și Xnu+k=j)=∑ℓ∈EP(Xnu=eu,Xnu+k-1=ℓ) P(Xnu+k=j∣Xnu=eu,Xnu+k-1=ℓ)=∑ℓ∈EP(Xnu=eu,Xnu+k-1=ℓ) pℓ,j=P(Xnu=eu) ∑ℓ∈Epeu,ℓ(k-1) pℓ,j=P(Xnu=eu) peu,j(k),{\ displaystyle {\ begin {align} \ mathbb {P} \ left (X_ {n} = i {\ text {și}} X_ {n + k} = j \ right) & = \ sum _ {\ ell \ în E} \ mathbb {P} \ left (X_ {n} = i, \, X_ {n + k-1} = \ ell {\ text {și}} X_ {n + k} = j \ right) \ \ & = \ sum _ {\ ell \ în E} \ mathbb {P} \ left (X_ {n} = i, \, X_ {n + k-1} = \ ell \ right) \ \ mathbb {P} \ left (X_ {n + k} = j \ mid X_ {n} = i, \, X_ {n + k-1} = \ ell \ right) \\ & = \ sum _ {\ ell \ in E} \ mathbb {P} \ left (X_ {n} = i, \, X_ {n + k-1} = \ ell \ right) \ p _ {\ ell, j} \\ & = \ mathbb {P} \ left (X_ {n} = i \ right) \ \ sum _ {\ ell \ in E} p_ {i, \ ell} ^ {(k-1)} \ p _ {\ ell, j} \\ & = \ mathbb {P} \ left (X_ {n} = i \ right) \ p_ {i, j} ^ {(k)}, \ end {align}}}
sau
- 1 st egalitatea este a treia axioma de probabilitate ,
- a 2 -a egalitate este definiția unei probabilități condiționate ,
- 3 - lea egalitatea se datorează unei forme de proprietate scăzută Markov,
- a 4- a egalitate nu este proprietatea recurențeik-1,{\ displaystyle k-1,}
- a 5- a egalitate este formula produsului a două „matrice”, aplicate produsului din cuPk-1{\ displaystyle P ^ {k-1}}P.{\ displaystyle P.}
În concluzie, împărțim cei doi termeni extremi ai acestei secvențe de egalități cu excepția cazului în care acest ultim termen este zero, caz în care putem defini în mod arbitrar, prin urmare, de exemplu, egal cuP(Xnu=eu),{\ displaystyle \ mathbb {P} \ left (X_ {n} = i \ right),}P(Xnu+k=j∣Xnu=eu){\ displaystyle \ mathbb {P} \ left (X_ {n + k} = j \ mid X_ {n} = i \ right)}peu,j(k).{\ displaystyle p_ {i, j} ^ {(k)}.}
Printr-o simplă aplicare a formulei probabilității totale , deducem legile marginale ale lanțului Markov.
Corolar - Legea lui este dată de
Xnu+k{\ displaystyle X_ {n + k}}P(Xnu+k=j)=∑eu∈EP(Xnu=eu)peu,j(k).{\ displaystyle \ mathbb {P} \ left (X_ {n + k} = j \ right) = \ sum _ {i \ in E} \ mathbb {P} \ left (X_ {n} = i \ right) p_ {i, j} ^ {(k)}.}
În special,
P(Xnu=j)=∑eu∈EP(X0=eu)peu,j(nu).{\ displaystyle \ mathbb {P} \ left (X_ {n} = j \ right) = \ sum _ {i \ in E} \ mathbb {P} \ left (X_ {0} = i \ right) p_ {i , j} ^ {(n)}.}
În scrierea matricială, dacă legea lui este considerată ca un vector-linie cu care se reformulează în:
Xnu{\ displaystyle X_ {n}}μnu=(μnu,eu)eu∈E,{\ displaystyle \ mu _ {n} = (\ mu _ {n, i}) _ {i \ în E},}μnu,eu=P(Xnu=eu),{\ displaystyle \ mu _ {n, i} = \ mathbb {P} \ left (X_ {n} = i \ right),}μnu+k=μnuPk și μnu=μ0Pnu.{\ displaystyle \ mu _ {n + k} = \ mu _ {n} P ^ {k} \ quad {\ text {and}} \ quad \ mu _ {n} = \ mu _ {0} P ^ { nu}.}
Clasificarea statelor
Căci , spunem că este accesibil din cazul în care și numai dacă există astfel încât să denotăm:
(eu,j)∈E2{\ displaystyle (i, j) \ în E ^ {2}}j{\ displaystyle j}eu{\ displaystyle i}nu≥0{\ displaystyle n \ geq 0}P(Xnu=j∣X0=eu)>0.{\ displaystyle \ mathbb {P} (X_ {n} = j \ mid X_ {0} = i)> 0.}{j←eu}⇔{∃nu≥0 ca peu,j(nu)>0}.{\ displaystyle \ {j \ leftarrow i \} \ quad \ Leftrightarrow \ quad \ left \ {\ există n \ geq 0 {\ text {cum ar fi}} p_ {i, j} ^ {(n)}> 0 \ dreapta \}.}
Spunem asta și comunicăm dacă și numai dacă există astfel încât și denotăm:
eu{\ displaystyle i}j{\ displaystyle j} (nu,m)∈NU2{\ displaystyle (n, m) \ in \ mathbb {N} ^ {2}}P(Xnu=j∣X0=eu)>0{\ displaystyle \ mathbb {P} (X_ {n} = j \ mid X_ {0} = i)> 0}P(Xm=eu∣X0=j)>0.{\ displaystyle \ mathbb {P} (X_ {m} = i \ mid X_ {0} = j)> 0.}{j↔eu}⇔{j←eu și eu←j}.{\ displaystyle \ {j \ leftrightarrow i \} \ quad \ Leftrightarrow \ quad \ left \ {j \ leftarrow i {\ text {și}} i \ leftarrow j \ right \}.}
Relația de a comunica , notată este o relație de echivalență . Când vorbim de clasă atunci când vorbim despre stările unui lanț Markov, în general se referă la clasele de echivalență pentru relația . Dacă toate statele comunică, se spune că lanțul Markov este ireductibil .
↔,{\ displaystyle \ leftrightarrow,}↔{\ displaystyle \ leftrightarrow}
Relația de a fi accesibilă , notată, se extinde la clasele de echivalență: pentru două clase și , avem
←,{\ displaystyle \ leftarrow,}VS{\ displaystyle C}VS′{\ displaystyle C ^ {\ prime}}{VS←VS′}⇔{∃(eu,j)∈VS×VS′,eu←j}⇔{∀(eu,j)∈VS×VS′,eu←j}.{\ displaystyle \ {C \ leftarrow C ^ {\ prime} \} \ quad \ Leftrightarrow \ quad \ left \ {\ există (i, j) \ în C \ times C ^ {\ prime}, \ qquad i \ leftarrow j \ right \} \ quad \ Leftrightarrow \ quad \ left \ {\ forall (i, j) \ in C \ times C ^ {\ prime}, \ qquad i \ leftarrow j \ right \}.}
Relația este o relație de ordine între clasele de echivalență.
←{\ displaystyle \ leftarrow}
Se spune că o clasă este finală dacă nu conduce la alta, adică dacă clasa este minimă pentru relație. În caz contrar, se spune că este tranzitorie . Apartenența la o clasă finală sau tranzitorie are consecințe asupra proprietăților probabilistice ale unui stat din lanțul Markov, în special asupra statutului său de stare recurentă sau de stare tranzitorie . Numărul și natura claselor finale dictează structura setului de probabilități staționare , care rezumă cu precizie comportamentul asimptotic al lanțului Markov, așa cum se poate vedea în secțiunea următoare și în cele două exemple detaliate la sfârșitul acestei pagini.
←.{\ displaystyle \ leftarrow.}
Este Meuj={nu≥1 | peu,j(nu)>0}.{\ displaystyle M_ {ij} = \ left \ {n \ geq 1 \ | \ p_ {i, j} ^ {(n)}> 0 \ right \}.}
Perioada unui stat este GCD setului. În
cazul în care două state comunică, ele au aceeași perioadă: prin urmare , putem vorbi de perioada unei clase de stări. Dacă perioada este 1, se spune că clasa este aperiodică . Aperiodicitatea stărilor unui lanț Markov condiționează convergența legii de către probabilitatea staționară, vezi pagina Probabilitatea staționară a unui lanț Markov .
eu{\ displaystyle i}Meueu.{\ displaystyle M_ {ii}.}Xnu{\ displaystyle X_ {n}}
Clasificarea statelor și perioada lor pot fi citite cu ușurință pe graficul lanțului Markov . Cu toate acestea, dacă toate elementele matricei de tranziție sunt strict pozitive, lanțul Markov este ireductibil și aperiodic: desenarea graficului lanțului Markov este atunci inutilă.
Dreptul staționar
Definiție
Pot exista una sau mai multe măsurători pe spațiul de stare, cum ar fi:
π=(πeu)eu∈E,{\ displaystyle \ pi = (\ pi _ {i}) _ {i \ în E},}E,{\ displaystyle E,}π=πP,{\ displaystyle \ pi = \ pi \, P,}
sau chiar
∀j∈E,πj=∑eu∈Eπeupeu,j.{\ displaystyle \ forall j \ in E, \ qquad \ pi _ {j} = \ sum _ {i \ in E} \ pi _ {i} \, p_ {i, j}.}
O astfel de măsurare se numește măsurare staționară . O măsură staționară este o funcție proprie a transpunerii matricei de tranziție, asociată cu valoarea proprie 1. Se numește probabilitate staționară sau lege staționară dacă îndeplinește condițiile suplimentare:
π{\ displaystyle \ pi}
- ∀eu∈E,πeu ≥ 0,{\ displaystyle \ forall i \ în E, \ qquad \ pi _ {i} \ \ geq \ 0,}
- ∑eu∈Eπeu = 1.{\ displaystyle \ sum _ {i \ in E} \ pi _ {i} \ = \ 1.}
Termenul „ staționar ” este justificat de următoarea propoziție:
Propunere - Dacă legea inițială a lanțului Markov (adică legea ) este o probabilitate staționară, atunci pentru toată legea este încăX0{\ displaystyle X_ {0}}π,{\ displaystyle \ pi,}nu≥0,{\ displaystyle n \ geq 0,}Xnu{\ displaystyle X_ {n}}π.{\ displaystyle \ pi.}
Demonstrație
Acest lucru rezultă din proprietățile puterilor matricei de tranziție date mai sus: legea μ n a lui X n este exprimată ca o funcție a legii μ 0 a lui X 0 după cum urmează: sau implicăμnu=μ0Pnu=πPnu,{\ displaystyle \ mu _ {n} = \ mu _ {0} P ^ {n} = \ pi P ^ {n},}πP=π{\ displaystyle \ pi P = \ pi}πPnu=π. {\ displaystyle \ pi P ^ {n} = \ pi. \}
Mai general, lanțul Markov este un proces staționar dacă și numai dacă legea sa inițială este o probabilitate staționară .
Existența și unicitatea
În cazul lanțurilor Markov de spațiu discret, anumite proprietăți ale procesului determină dacă există sau nu o probabilitate staționară și dacă este unică sau nu:
- un lanț Markov este ireductibil dacă orice stat este accesibil din orice alt stat;
- o stare este recurentă pozitivă dacă așteptarea timpului primei reveniri la această stare, pornind de la această stare, este finită.
Dacă un lanț Markov are cel puțin o stare recurentă pozitivă, atunci există o probabilitate staționară. Dacă există o probabilitate staționară astfel încât , atunci starea este recurentă pozitivă și invers.
π{\ displaystyle \ pi}πeu>0{\ displaystyle \ pi _ {i}> 0}eu{\ displaystyle i}
Teorema - Dacă un lanț Markov are o singură clasă finală, atunci există cel mult o probabilitate staționară. Apoi avem echivalență între cele 3 propoziții:
VS,{\ displaystyle C,}
- există o probabilitate staționară unică, remarcată π,{\ displaystyle \ pi,}
- există o stare recurentă pozitivă,
- toate stările clasei finale sunt recurente pozitive.
Avem și echivalența
{πeu>0}⇔{eu∈VS}⇔{eu este recurent pozitiv}.{\ displaystyle \ {\ pi _ {i}> 0 \} \ Leftrightarrow \ {i \ în C \} \ Leftrightarrow \ {i {\ text {este pozitiv recurent}} \}.}
Această teoremă este valabilă în special pentru lanțurile Markov ireductibile, deoarece acestea din urmă au o singură clasă (care este deci în mod necesar o clasă finală); lanțurile ireductibile Markov verifică în special
VS=E.{\ displaystyle C = E.}
Legea puternică a numărului mare și a ergodicității
În cazul unui lanț Markov pozitiv ireductibil și recurent, legea puternică a numărului mare este în vigoare: media unei funcții peste instanțele lanțului Markov este egală cu media sa în funcție de probabilitatea sa staționară. Mai exact, sub ipoteza
f{\ displaystyle f}∑eu∈E|f(eu)|πeu <+∞,{\ displaystyle \ sum _ {i \ in E} | f (i) | \, \ pi _ {i} \ <+ \ infty,}
avem aproape sigur avem :
limnu1nu∑k=0nu-1f(Xk) = ∑eu∈Ef(eu)πeu = πf.{\ displaystyle \ lim _ {n} \; {\ frac {1} {n}} \; \ sum _ {k = 0} ^ {n-1} f (X_ {k}) \ = \ \ sum _ {i \ in E} f (i) \, \ pi _ {i} \ = \ \ pi f.}
Media valorii instanțelor este, prin urmare, pe termen lung, egală cu așteptarea în funcție de probabilitatea staționară. În special, această echivalență asupra mijloacelor se aplică dacă este funcția indicator a unui subset al spațiului de stare:
f{\ displaystyle f}LA{\ displaystyle A}limnu1nu∑k=0nu-1χLA(Xk) = ∑eu∈LA πeu = π(LA).{\ displaystyle \ lim _ {n} \; {\ frac {1} {n}} \; \ sum _ {k = 0} ^ {n-1} \ chi _ {A} (X_ {k}) \ = \ \ sum _ {i \ în A} \ \ pi _ {i} \ = \ \ pi (A).}
Acest lucru face posibilă abordarea probabilității staționare prin distribuția empirică (care este o histogramă construită dintr-o anumită secvență), ca în cazul mersului aleatoriu cu barieră .
În special, dacă procesul este construit luând probabilitatea staționară ca lege inițială, schimbarea definită de
θ{\ displaystyle \ theta}X=(X0,X1,X2,...)∈ENU→θX=(X1,X2,X3,...){\ displaystyle x = (x_ {0}, x_ {1}, x_ {2}, \ dots) \ în E ^ {\ mathbb {N}} \ quad \ rightarrow \ quad \ theta \, x = (x_ { 1}, x_ {2}, x_ {3}, \ dots)}
păstrează măsura, ceea ce face ca lanțul Markov să fie un sistem dinamic măsurat . Legea puternică a numărului mare are ca rezultat că lanțul Markov este un sistem dinamic ergodic . Ergodicitatea este în același timp mai puternică decât legea puternică a numărului mare, deoarece putem deduce, de exemplu, că are o limită aproape sigură, dar este și mai slabă, deoarece necesită în principiu staționaritatea lanțului Markov, ceea ce nu este cazul cu legea puternică a numărului mare.
1nu∑k=0nu-1f(Xk,Xk+1),{\ displaystyle {\ frac {1} {n}} \; \ sum _ {k = 0} ^ {n-1} f (X_ {k}, X_ {k + 1}),}∑eu,j∈Ef(eu,j)πeupeu,j,{\ displaystyle \ sum _ {i, j \ in E} f (i, j) \, \ pi _ {i} p_ {i, j},}
Convergența către legea staționară
Dacă lanțul Markov este ireductibilă , recurent pozitiv și aperiodic, apoi converge la o matrice din care fiecare rând este distribuția staționară unică
în particular, legea lui converge la independent de legea inițială În cazul unui spațiu de stat terminat, acesta este dovedită de teorema Perron-Frobenius . Rețineți că este firesc ca secvența definită prin inducție prin relație să aibă, eventual, pentru limită un punct fix al acestei transformări, adică o soluție a ecuațieiPk{\ displaystyle P ^ {k}}π.{\ displaystyle \ pi.}μnu{\ displaystyle \ mu _ {n}}Xnu{\ displaystyle X_ {n}}π{\ displaystyle \ pi}μ0.{\ displaystyle \ mu _ {0}.}μnu,{\ displaystyle \ mu _ {n},}μnu+1=μnuP,{\ displaystyle \ mu _ {n + 1} = \ mu _ {n} P,}π=πP.{\ displaystyle \ pi = \ pi P.}
Lanțuri Markov de spațiu finit
Dacă un lanț Markov este ireductibil și dacă spațiul său de stare este finit, toate stările sale sunt recurente pozitive. Legea puternică a numărului mare este atunci în vigoare.
Mai general, toate elementele unei clase finale finite sunt recurente pozitive, indiferent dacă spațiul de stare este finit sau infinit numărabil.
Distribuții aproape staționare ale unui lanț Markov absorbit
Fie un lanț Markov peste setul de numere naturale . Să presupunem că starea 0 este absorbantă și că lanțul este absorbit la 0 aproape sigur. Fie timpul de absorbție la 0. Spunem că o probabilitate pe este o distribuție cvasi-staționară dacă pentru toate și pentru toate ,
(Xnu){\ displaystyle (X_ {n})}{0,1,2,...}{\ displaystyle \ {0,1,2, ... \}}T0=inf{nu≥0,Xnu=0}{\ displaystyle T_ {0} = \ inf \ {n \ geq 0, X_ {n} = 0 \}}ν{\ displaystyle \ nu}{1,2,3,...}{\ displaystyle \ {1,2,3, ... \}}j≥1{\ displaystyle j \ geq 1}nu≥1{\ displaystyle n \ geq 1}
∑eu≥1νeuP(Xnu=j|X0=eu,T0>nu)=νj.{\ displaystyle \ sum _ {i \ geq 1} \ nu _ {i} \ mathbb {P} (X_ {n} = j | X_ {0} = i, T_ {0}> n) = \ nu _ { j}.}Noi spunem că o probabilitate pe o Yaglom limită în cazul în care pentru tot și totul ,
μ{\ displaystyle \ mu}{1,2,3,...}{\ displaystyle \ {1,2,3, ... \}}eu≥1{\ displaystyle i \ geq 1}j≥1{\ displaystyle j \ geq 1}
limnu→∞P(Xnu=j|X0=eu,T0>nu)=μj.{\ displaystyle \ lim _ {n \ to \ infty} \ mathbb {P} (X_ {n} = j | X_ {0} = i, T_ {0}> n) = \ mu _ {j}.}O limită Yaglom este o distribuție cvasi-staționară . Dacă există, limita Yaglom este unică. Pe de altă parte, pot exista mai multe distribuții cvasi-staționare.
Dacă există o distribuție cvasi-staționară, atunci există un număr real astfel încât .
ν{\ displaystyle \ nu}ρ(ν)∈]0,1[{\ displaystyle \ rho (\ nu) \ in] 0.1 [}∑euνeuP(T0>nu|X0=eu)=ρ(ν)nu{\ displaystyle \ sum _ {i} \ nu _ {i} \ mathbb {P} (T_ {0}> n | X_ {0} = i) = \ rho (\ nu) ^ {n}}
Evaluare
În formulele de mai sus, elementul ( ) este probabilitatea tranziției de la la . Suma elementelor unui rând este întotdeauna egală cu 1 și distribuția staționară este dată de vectorul propriu stâng al matricei de tranziție.
eu,j{\ displaystyle i, j}eu{\ displaystyle i}j{\ displaystyle j}
Uneori întâlnim matrici de tranziție în care termenul ( ) este probabilitatea tranziției de la la , caz în care matricea de tranziție este pur și simplu transpunerea celei descrise aici. Suma elementelor unei coloane este atunci în valoare de 1. Mai mult, distribuția staționară a sistemului este apoi dată de vectorul propriu drept al matricei de tranziție, în loc de vectorul propriu stâng.
eu,j{\ displaystyle i, j}j{\ displaystyle j}eu{\ displaystyle i}
Exemplu: Doudou hamsterul
Hamsterul Doudou cunoaște doar trei locuri în cușca sa: așchii în care doarme, hrănitorul în care mănâncă și roata în care face exerciții. Zilele sale sunt destul de asemănătoare între ele, iar activitatea sa este ușor reprezentată de un lanț Markov. În fiecare minut, poate fie să-și schimbe activitatea, fie să o continue pe cea pe care o făcea. Procesul de nume fără memorie nu este deloc exagerat pentru a vorbi despre Doudou.
- Când doarme, are șanse de 9 la 10 să nu se trezească în minutul următor.
- Când se trezește, există o șansă de 1 la 2 să meargă să mănânce și o șansă de 1 la 2 să meargă la exerciții.
- Masa durează doar un minut, apoi face altceva.
- După ce a mâncat, există șanse de 3 din 10 să meargă la o fugă în roată, dar mai ales 7 din 10 să se întoarcă la culcare.
- Alergarea este obositoare pentru Doudou; există șanse de 8 din 10 să se întoarcă la somn după un minut. Altfel continuă să uite că este deja puțin obosit.
Diagrame
Graficele pot afișa toate săgețile, fiecare reprezentând o probabilitate de tranziție. Cu toate acestea, este mai ușor de citit dacă:
- nu trasăm săgețile de probabilitate zero (tranziție imposibilă);
- nu desenăm buclele (săgeata unui stat către sine) . Cu toate acestea există; probabilitatea lor este implicată deoarece știm că suma probabilităților săgeților care pleacă din fiecare stare trebuie să fie egală cu 1.
Matricea de tranziție
Matricea de tranziție a acestui sistem este după cum urmează (rândurile și coloanele corespund în ordinea stărilor reprezentate pe cip , alimentator , graficul roții ):
P=[0,90,050,050,700,30,800,2]{\ displaystyle P = {\ begin {bmatrix} 0.9 & 0.05 & 0.05 \\ 0.7 & 0 & 0.3 \\ 0.8 & 0 & 0.2 \\\ end {bmatrix}}}
Prognozele
Să presupunem că Doudou doarme în primul minut al studiului.
X(0)=[100]{\ displaystyle \ mathbf {x} ^ {(0)} = {\ begin {bmatrix} 1 & 0 & 0 \ end {bmatrix}}}
După un minut, putem prezice:
X(1)=X(0)P=[100][0,90,050,050,700,30,800,2]=[0,90,050,05]{\ displaystyle \ mathbf {x} ^ {(1)} = \ mathbf {x} ^ {(0)} P = {\ begin {bmatrix} 1 & 0 & 0 \ end {bmatrix}} {\ begin {bmatrix } 0.9 & 0, 05 & 0.05 \\ 0.7 & 0 & 0.3 \\ 0.8 & 0 & 0.2 \\\ end {bmatrix}} = {\ begin {bmatrix} 0.9 & 0.05 & 0.05 \ end {bmatrix}}}
Astfel, după un minut, există 90% șanse ca Doudou să mai doarmă, 5% să mănânce și 5% să alerge.
X(2)=X(1)P=X(0)P2=[100][0,90,050,050,700,30,800,2]2=[0,8850,0450,07]{\ displaystyle \ mathbf {x} ^ {(2)} = \ mathbf {x} ^ {(1)} P = \ mathbf {x} ^ {(0)} P ^ {2} = {\ begin {bmatrix } 1 & 0 & 0 \ end {bmatrix}} {\ begin {bmatrix} 0.9 & 0.05 & 0.05 \\ 0.7 & 0 & 0.3 \\ 0.8 & 0 & 0.2 \\\ end {bmatrix}} ^ {2} = {\ begin {bmatrix} 0.885 & 0.045 & 0.07 \ end {bmatrix}}}
După 2 minute, există șanse de 4,5% ca hamsterul să mănânce.
În general, pentru câteva minute:
nu{\ displaystyle n}X(nu)=X(nu-1)P{\ displaystyle \ mathbf {x} ^ {(n)} = \ mathbf {x} ^ {(n-1)} P} și
X(nu)=X(0)Pnu{\ displaystyle \ mathbf {x} ^ {(n)} = \ mathbf {x} ^ {(0)} P ^ {n}}
Teoria arată că după un anumit timp, legea probabilității este independentă de legea inițială. Să notăm :
q{\ displaystyle q}q=limnu→∞X(nu){\ displaystyle \ mathbf {q} = \ lim _ {n \ to \ infty} \ mathbf {x} ^ {(n)}}
Obținem convergența dacă și numai dacă lanțul este aperiodic și ireductibil . Acesta este cazul în exemplul nostru, astfel încât să putem scrie:
P=[0,90,050,050,700,30,800,2]qP=q(q este legea invariantă cu privire la P.)=qEuq(Eu-P)=0=q([100010001]-[0,90,050,050,700,30,800,2])=q[0,1-0,05-0,05-0,71-0,3-0,800,8]=[q1q2q3][0,1-0,05-0,05-0,71-0,3-0,800,8]=[000]{\ displaystyle {\ begin {align} P & = {\ begin {bmatrix} 0.9 & 0.05 & 0.05 \\ 0.7 & 0 & 0.3 \\ 0.8 & 0 & 0.2 \\\ end {bmatrix}} \\\ mathbf { q} P & = \ mathbf {q} \ qquad {\ mbox {(}} \ mathbf {q} {\ mbox {este legea invariantă în ceea ce privește}} P {\ mbox {.)}} \\ & = \ mathbf {q} I \\\ mathbf {q} (IP) & = \ mathbf {0} \\ & = \ mathbf {q} \ left ({\ begin {bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \ end {bmatrix}} - {\ begin {bmatrix} 0.9 & 0.05 & 0.05 \\ 0.7 & 0 & 0.3 \\ 0.8 & 0 & 0.2 \\\ end {bmatrix }} \ right) \\ & = \ mathbf {q} {\ begin {bmatrix} 0.1 & -0.05 & -0.05 \\ - 0.7 & 1 & -0.3 \\ - 0.8 & 0 & 0.8 \\\ end {bmatrix }} \\ & = {\ begin {bmatrix} q_ {1} & q_ {2} & q_ {3} \ end {bmatrix}} {\ begin {bmatrix} 0.1 & -0.05 & -0.05 \\ - 0.7 & 1 & -0, 3 \\ - 0.8 & 0 & 0.8 \\\ end {bmatrix}} \\ & = {\ begin {bmatrix} 0 & 0 & 0 \ end {bmatrix}} \ end {align}}}
Știind asta , obținem:
q1+q2+q3=1{\ displaystyle q_ {1} + q_ {2} + q_ {3} = 1}[q1q2q3]=[0,8840,04420,0718]{\ displaystyle {\ begin {bmatrix} q_ {1} & q_ {2} & q_ {3} \ end {bmatrix}} = {\ begin {bmatrix} 0.884 & 0.0442 & 0.0718 \ end {bmatrix}}}
Prin urmare, Doudou își petrece 88,4% din timp dormind, 4,42% mâncând și 7,18% alergând.
Ilustrarea impactului modelului
Următorul exemplu își propune să arate importanța modelării sistemului. O bună modelare face posibilă răspunsul la întrebări complexe cu calcule simple.
Studiem o civilizație (fictivă) formată din mai multe clase sociale și în care indivizii se pot deplasa de la o clasă la alta. Fiecare etapă va reprezenta un an. Vom lua în considerare mai degrabă o linie decât un individ, pentru a evita obținerea de cetățeni bicentenari. Există patru stări sociale diferite:
- sclav;
- gratuit;
- cetăţean;
- înalt oficial.
În această companie:
- sclavii pot rămâne sclavi sau pot deveni oameni liberi (prin cumpărarea libertății lor sau prin eliberarea liberală de către stăpânul lor);
- oamenii liberi pot rămâne liberi sau își pot vinde libertatea (de a-și plăti datoriile etc.) sau chiar de a deveni cetățeni (din nou prin merit sau prin cumpărarea titlului de cetățean);
- cetățenii sunt cetățeni pe viață și își transmit cetățenia către descendența lor (se poate crede că numărul cetățenilor tinde să crească și că, după un anumit timp, toți sunt cetățeni, dar istoric, în civilizațiile care au urmat acest model, cetățenii sunt decimați de războaiele și noii sclavi sosesc regulat din străinătate). De asemenea, aceștia pot candida la alegerile anuale pentru a deveni înalți funcționari (magistrați). La sfârșitul mandatului lor, pot fi realesi sau pot deveni din nou cetățeni obișnuiți.
Pentru a complica puțin exemplul și pentru a arăta astfel amploarea aplicațiilor lanțurilor Markov, vom considera că funcționarii publici sunt aleși pentru câțiva ani. Prin urmare, viitorul unui funcționar public individual depinde de perioada de timp în care a fost funcționar public. Prin urmare, suntem în cazul unui lanț Markov neomogen. Din fericire, putem reveni cu ușurință la un lanț omogen. Într-adevăr, este suficient să adăugați o stare artificială pentru fiecare an al mandatului. În loc să avem un stat 4: oficial , vom avea un stat:
- 4: Funcționar public la începutul mandatului său;
- 5: Funcționar public în al doilea an de mandat;
- etc.
Probabilitățile care leagă două stări artificiale consecutive (al treilea și al patrulea an, de exemplu) sunt de valoarea 1, deoarece considerăm că orice mandat început se termină (am putea modela opusul schimbând valoarea acestor probabilități). Să stabilim durata mandatelor la doi ani, contingentul funcționarilor publici fiind reînnoibil la jumătate în fiecare an. Apoi avem următorul grafic:
Pentru a modela alegerile care nu sunt anuale, ar fi, de asemenea, necesar să adăugați state fictive (anul alegerilor, un an de la ultimele alegeri etc.).
Apoi se scrie matricea :
P{\ displaystyle P}P=[97981980002736573673000012131130000010078180]{\ displaystyle \ mathbf {P} = {\ begin {bmatrix} {\ frac {97} {98}} & {\ frac {1} {98}} & 0 & 0 & 0 \\ {\ frac {2} {73}} & {\ frac {65} {73}} & {\ frac {6} {73}} & 0 & 0 \\ 0 & 0 & {\ frac {12} {13}} & {\ frac {1} {13}} & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & {\ frac {7} {8}} & {\ frac {1} {8}} & 0 \ end {bmatrix}}}
După cum sa explicat mai sus, dați probabilitățile de tranziție în etape. La fel și probabilitatea de a fi în stat după ani pentru o descendență care face parte din clasa socială . Pentru a ști ce devine un sclav după ani, este suficient să scrieți:
Pnu{\ displaystyle P ^ {n}}nu{\ displaystyle n}peujnu{\ displaystyle p_ {ij} ^ {n}}j{\ displaystyle j}nu{\ displaystyle n}eu{\ displaystyle i}nu{\ displaystyle n}[10000]×P(nu)=[p1(nu)p2(nu)p3(nu)p4(nu)p5(nu)]{\ displaystyle {\ begin {bmatrix} 1 & 0 & 0 & 0 & 0 \ end {bmatrix}} \ times \ mathbf {P} ^ {(n)} = {\ begin {bmatrix} p_ {1} ^ { (n)} & p_ {2} ^ {(n)} & p_ {3} ^ {(n)} & p_ {4} ^ {(n)} & p_ {5} ^ {(n)} \ end {bmatrix}}}
Unde este probabilitatea de a fi în clasa socială după ce ani de zile știu că linia studiată a părăsit starea de sclav?
peunu{\ displaystyle p_ {i} ^ {n}}eu{\ displaystyle i}nu{\ displaystyle n}
Dacă cunoaștem numărul fiecărei clase sociale din anul 0, este suficient să calculăm:
1leugnue´es×[esvs.llavesleubresvs.eutoyenuse´ltus1e´ltus2]×Pnu=Da{\ displaystyle {\ frac {1} {\ mathrm {lign {\ acute {e}} es}}} \ times {\ begin {bmatrix} {\ rm {slaves}} și {\ rm {free}} & { \ rm {citizens}} și {\ rm {{\ acute {e}} lus_ {1}}} și {\ rm {{\ acute {e}} lus_ {2}}} \ end {bmatrix}} \ times \ mathbf {P} ^ {n} = Y}
Obținem astfel distribuția populației în diferitele clase sociale (după ani). Înmulțind acest vector cu numărul total al populației, obținem numerele fiecărei clase la sfârșitul anilor.
nu{\ displaystyle n}Da{\ displaystyle Y}nu{\ displaystyle n}
Să ne punem acum următoarea întrebare: "La sfârșitul anilor, câte linii vor avea deja un înalt funcționar care și-a încheiat mandatul?" "
nu{\ displaystyle n}
Răspunsul este diferit de numărul de mandate îndeplinite în ani, deoarece există posibilitatea de a fi reales. Răspunsul la această întrebare pare dificil (ar trebui să fie posibil). De fapt, este suficient să se schimbe modelarea problemei. Deci, să trecem la un nou model pentru a răspunde la această întrebare. (Pe de altă parte, nu ne permite să răspundem la întrebările anterioare, de unde prezentarea celor două modele.)
nu{\ displaystyle n}
Este suficient să modificați graficul după cum urmează:
Adăugăm un top absorbant, deoarece odată ce o linie a încheiat un mandat, acesta nu mai este luat în considerare.
Dacă unii cititori sunt critici, ei pot spune că modelul este greșit, deoarece liniile cu un ales nu mai participă la alegeri. Nu este asa. Într-adevăr, numărul de aleși este proporțional cu numărul de cetățeni. Nerinjectarea foștilor înalți funcționari printre candidați nu modifică, prin urmare, probabilitatea ca un cetățean să fie ales, deoarece populația cetățenilor fiind mai mică, numărul de posturi oferite este, de asemenea. Acest model vă permite să răspundeți cu exactitate la întrebarea pusă.
Prin urmare, avem o nouă matrice de tranziție:
Î=[97981980000273657367300000121311300000010000001000001]{\ displaystyle \ mathbf {Q} = {\ begin {bmatrix} {\ frac {97} {98}} & {\ frac {1} {98}} & 0 & 0 & 0 & 0 \\ {\ frac { 2} {73}} & {\ frac {65} {73}} & {\ frac {6} {73}} & 0 & 0 & 0 \\ 0 & 0 & {\ frac {12} {13}} & {\ frac {1} {13}} & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \ end {bmatrix}}}
Făcând aceleași calcule ca la întrebările anterioare, obținem în ultima linie a vectorului soluție procentul de linii care au finalizat cel puțin un mandat sau numărul (dacă înmulțim cu numărul total al populației). Cu alte cuvinte, pentru a modela din nou problema face posibilă răspunsul la întrebarea care părea atât de complicată printr-un calcul simplu al puterilor unei matrice.
Aplicații
- Un proces Bernoulli este un exemplu simplu de lanț Markov.
- Sistemele markoviene sunt foarte prezente în fizică, în special în fizica statistică . Mai general, ipoteza markoviană este adesea invocată atunci când probabilitățile sunt folosite pentru a modela starea unui sistem, presupunând totuși că starea viitoare a sistemului poate fi dedusă din trecut cu o istorie destul de scăzută.
- Celebrul articol din 1948 al lui Claude Shannon , O teorie matematică a comunicării , care fundamentează teoria informației , începe prin introducerea conceptului de entropie dintr-o modelare Markov a limbii engleze . Arată astfel gradul de predictibilitate al limbii engleze, prevăzut cu un model simplu de ordine 1. Deși simple, astfel de modele permit reprezentarea bine a proprietăților statistice ale sistemelor și realizarea unor predicții eficiente fără a descrie structura completă.
- În compresie , modelarea Markoviană permite realizarea unor tehnici de codificare a entropiei foarte eficiente, cum ar fi codarea aritmetică . Mulți algoritmi în recunoașterea tiparelor sau în inteligența artificială, cum ar fi algoritmul Viterbi , utilizat în marea majoritate a sistemelor de telefonie mobilă pentru corectarea erorilor, presupun un proces Markovian de bază.
- Indicele de popularitate al unei pagini web ( PageRank ) așa cum este utilizat de Google este definit de un lanț Markov. Este definit de probabilitatea de a fi în această pagină din orice stare a lanțului Markov care reprezintă Web-ul. Dacă este numărul de pagini web cunoscute și o pagină are legături, atunci probabilitatea sa de a trece la o pagină legată (spre care indică) este și pentru toate celelalte (pagini fără legătură). Rețineți că avem . Parametrul este de aproximativ 0,15.NU{\ displaystyle N}eu{\ displaystyle i}keu{\ displaystyle k_ {i}}peul=1-qkeu+qNU{\ displaystyle p_ {i} ^ {l} = {\ tfrac {1-q} {k_ {i}}} + {\ tfrac {q} {N}}}peunul=qNU{\ displaystyle p_ {i} ^ {nl} = {\ tfrac {q} {N}}}keupeul+(NU-keu)peunul=1{\ displaystyle k_ {i} p_ {i} ^ {l} + (N-k_ {i}) p_ {i} ^ {nl} = 1}q{\ displaystyle q}
- Lanțurile Markov sunt un instrument fundamental pentru modelarea proceselor în teoria cozii și statistici .
- Lanturi Markov sunt frecvent utilizate în fiabilitate pentru calculele de fiabilitate și disponibilitate a sistemelor tehnice , în special pentru modelarea tip de defect de secvențe de evenimente, reparații, modificări de configurație.
- Lanțurile Markov stau la baza sistemelor Bonus / Malus dezvoltate de actuarii companiilor de asigurări auto (probabilitatea de a avea n accidente în anul t fiind condiționată de numărul de accidente din t-1)
- Lanțurile Markov sunt folosite și în bioinformatică pentru a modela relațiile dintre simbolurile succesive ale aceleiași secvențe (de exemplu, a nucleotidelor ), depășind modelul polinomial. Modelele ascunse Markov au, de asemenea, diverse utilizări, cum ar fi segmentarea (definirea limitelor regionale în cadrul secvențelor de gene sau proteine cu proprietăți chimice variate), alinierea multiplă , predicția funcției sau descoperirea genelor (modelele ascunse Markov sunt mai „flexibile” decât definiții stricte ale codonului de tip start + codoni multipli + codoni stop și sunt, prin urmare, mai potrivite pentru eucariote (datorită prezenței intronilor în genomul acestora) sau pentru descoperirea pseudo-genelor).
Note și referințe
Vezi și tu
Articole similare
Bibliografie
- Bruno Sericola: Lanțuri Markov - Teorie, algoritmi și aplicații . Hermes / Lavoisier, 2013.
- Sylvie Méléard: Modele aleatorii în ecologie și evoluție . Springer, 2016.
- Lanțurile Paolo Baldi, Laurent Mazliak, Pierre Priouret, Martingales și Markov. Teoria elementară și exercițiile corectate , ( ISBN 2-7056-6425-4 ) , Hermann (ediții) , 2001
linkuri externe