Lanțuri Markov

Sisteme de tip Markov

Noțiunea matematica de lanț Markov a apărut in urma studierii unor probleme practice e tipul următor.

Sa examinam un sistem (fizic, tehnic, economic, biologic, social) la momente discrete de timp 0,1,2,..,k,… Presupuneam ca la fiecare moment k sistemul se poate afla in una din stările s_1,s_2,s_3,…s_(n ); punem S = {s_1,s_2,s_3,…s_(n )}, uneori S = {1,2,3,…n}. Notam cu X_k sau X(k) variabila aleatoare care descrie starea sistemului la momentul k si admitem ca evoluția sistemului este probabilistica sau stochastica, ceea ce înseamnă ca, deși se cunosc stările X_1,X_2,X_3,…X_(n )ale sistemului pana in momentul k inclusiv, evoluția sa viitoare, in particular starea X_(k+1) este cunoscuta doar in termeni probabilistici (adică se poate determina probabilitatea cu care X(k+1) ia o anumita valoare din S). In principiu, admitem ca se cunosc probabilitățile

P (X_0= s_0,X_1=s_1,…,X_k=s_k), ∀ k ∈ ℕ , ∀ s_0,s_1,s_2,…s_(k )∈ S

si se pune problema calculării probabilităților condiționate de tipul

P (X_(k+1)=s_(k+1) / X_0 = s_0 ,X_1=s_1 ,…,X_k=s_k).

Daca P (X_(k+1)=s_(k+1) / X_0 = s_0 ,X_1=s_1 ,…,X_k=s_k) = P (X_(k+1)=s_(k+1)), atunci sistemul considerat este un sistem fără memorie.

Daca P (X_(k+1)=s_(k+1) / X_0 = s_0 ,X_1=s_1 ,…,X_k=s_k) = P (X_(k+1)=s_(k+1) / X_k=s_k), ceea ce inseamna ca pentru a cunoaste „trecutul” sistemului este suficient sa cunoaștem starea sa din momentul efectuării ultimei observații, iar modul in care sistemul a ajuns in aceasta stare nu are importanta, atunci sistemul considerat se numește sistem de tip Markov (sau sistem markovian).

Mersul aleator (Mersul la întâmplare)

Se considera o particula care la un moment dat se afla intr-un punct i ∈ {0,1,2,3,…,n} al segmentului [0,n]; fie S ={0,1,2,3,…,n}. Presupunem ca la momentul k = 0, particula se afla in poziția s_0 ∈ S. Daca la momentul k ∈ ℕ, particula se afla in poziția s_k, atunci la momentul (k+1) particula se afla intr-o pozitie descrisa astfel:

in poziția s_k, cu probabilitatea r_(s_k ), 0 ≤ s_k ≤ n

in poziția s_k+1, cu probabilitatea p_(s_k ), 0 ≤ s_k ≤ n - 1

in poziția s_k-1, cu probabilitatea q_(s_k ), 1 ≤ s_k ≤ n

Au loc relațiile r_(s_k )+p_(s_k )+q_(s_k ) = 1, 1 ≤ s_k ≤ n-1; r_0+ p_0=1; q_n+p_n=1.

Putem sa fixam datele descrise mai sus prin următoarea matrice pătratică de ordin (n+1)

(■(■(r_0&p_0&0@q_1&r_1&p_1@0&q_2&r_2 ) ■(0@0@p_2 )&⋯&■(0 &0 &0@0 &0 &0@0 &0 &0)@⋮&⋱&⋮@■(0 &0@0 &0) ■(0 &0@0 &0)&⋯&■(q_(n-1)&r_(n-1)&p_(n-1)@0&q_n&r_n )))

Notând cu X_k v.a. care reprezintă poziția particulei la momentul k, rezulta

P (X_(k+1)=s_(k+1) / X_k = s_k ,X_(k-1)=s_(k-1) ,…,X_0=s_0) = P (X_(k+1)=s_(k+1) / X_k=s_k), deci modelul (sistemul) fizic descris este de tip markovian.

Asemenea modele descriu mișcarea browniana intr-un mediu fluid, descompusa după diferite direcții.

Deseori, modelul mersului aleatoriu este asociat cu așa-numitul „mers al bețivului” (luând, eventual, r_0 = 0, 0 ≤ k ≤ n).

Exista doua modele celebre ale unor fenomene fizice care reprezintă mersuri aleatoare si care au fost concepute fără nici o legătura cu sistemele de tip Markov: modelul lui Daniel Bernoulli (1769) care descrie difuzia a doua lichide incompresibile intre doua containere si modelul Ehrenfest (1907), propus de soții Tatiana si Paul Ehrenfest.

Matrice stochastica. Vector de probabilitate

Un vector p = (p_1,p_2,..,p_n) ∈ R^n se numeste vector de probabilitate daca p_i≥0, ∀ i ∈ {1,2,3,..,n} si ∑_(i=1)^n▒p_i =1

O matrice ∏▒=(p_ij) ∈ M_n (R) se numește matrice stochastica daca fiecare linie a sa este un vector e probabilitate, i.e.

∑_(j=1)^n▒p_ij =1,∀ i∈{1,2,3,…,n} si p_ij≥ 0,∀ i,j∈{1,2,3,…,n}

O matrice ∏▒∈ M_n (R) se numeste matrice dublu stochastica daca toate liniile si coloanele sale sunt vectori de probabilitate, i.e. ∏ si ∏^T sunt matrici stochastice.

De asemenea matricea unitate I_n∈ M_n (R), i.e. matricea care are 1 pe diagonala principala si 0 in rest, este o matrice dublu stochastica.