Markovljev lanac

Izvor: Wikipedija
Skoči na: orijentacija, traži

U matematici Markovljev lanac nazvan po Andreyu Markovu predstavljaju niz stanja sustava. U svakome trenutku sustav može preći u neko novo stanje ili može ostati u istome stanju. Promjene stanja nazivaju se tranzicije. Ako slijed stanja ima Markovljevo svojstvo to znači da je svako buduće stanje vremenski neovisno o svakome prijašnjem stanju.

Formalna definicija[uredi VE | uredi]

Markovljev lanac je slijed slučajnih varijabla X1, X2, X3, ... s Markovljevim svojstvom i to zato što su trenutno, buduće i prošlo stanje nezavisni

\Pr(X_{n+1}=x|X_n=x_n, \ldots, X_1=x_1) = \Pr(X_{n+1}=x|X_n=x_n).\,


Moguće vrijednosti Xi formiraju prebrojivi skup S nazvan 'stanje prostora lanca.

Markovljevi lanci se često opisuju direktnim grafom gdje su bridovi označeni vjerojatnošću koja predstavlja prelazak iz jednog stanja u drugo.

Primjer 1[uredi VE | uredi]

Na željezničkoj pruzi nalazi se semafor na kojem gori ili crveno (C) ili zeleno (Z) svjetlo. U ovom primjeru željeznička pruga i semafor predstavljaju jedan sustav. Pretpostavimo da smo u nekom vremenskom intervalu promatrali u kojem se stanju nalazi naš sustav i da smo registrirali slijedeći niz:

   C, C, Z, Z, Z, C, Z, Z, C, C, C, Z, Z, Z, C, Z. (*)

U mnogim problemima se želi na osnovu sadašnjega stanja sustava predvidjeti u kom stanju će biti sustav prilikom slijedećeg ili nekoga kasnijega promatranja. Na osnovu nekoga promatranoga stanja ne možemo sa sigurnošću predvidjeti neko stanje već odrediti s kojom vjerojatnošću će se sustav nalaziti u nekom određenom stanju. Za ovaj primjer zanimljiva su slijedeća pitanja:

  1. Ako je sustav sada u stanju C, kolika je vjerojatnost da će pri slijedećem promatranju biti u stanju C?
  2. Ako je sustav sad u stanju C, kolika je vjerojatnost da će pri slijedećem promatranju biti u stanju Z?
  3. Ako je sustav sad u stanju Z, kolika je vjerojatnost da će pri slijedećem promatranju biti u stanju C?
  4. Ako je sustav sad u stanju Z, kolika je vjerojatnost da će pri slijedećem promatranju biti u stanju Z?

Pokušajmo odgovoriti na ova pitanja. Iz niza (*) vidimo da je sustav u stanju C bio 7 puta. U 3 slučaja sustav je ostao u stanju C, a u 4 iz stanja C prešao u stanje Z. Zaključujemo da je:

p („sustav je bio u stanju C i ostao u stanju C“ ) = \frac{3}{7},a
p („sustav je bio u stanju C i prešao u stanje Z“) = \frac{4}{7}

Iz niza (*) zaključujemo da je

p („sustav je bio u stanju Z i ostao u stanju Z“) = \frac{5}{8}
p („sustav je bio u stanju Z i prešao u stanje C“) =\frac{3}{8}


Informacije o vjerojatnostima prijelaza sustava iz jednoga u drugo stanje možemo zapisati koristeći matrični račun:

Naznačena matrica zove se matrica prijelaznih vrijednosti i obično se označava sa P, a njezini elementi, gdje su indeksi p_{ij}, iz skupa svih stanja. Matricu P možemo zapisati i pomoću stabla.

Uočimo da je suma svih grana koje izlaze iz bilo kojeg čvora jednaka 1.
Dakle možemo reći :
Markovljev lanac je niz diskretnih slučajnih varijabli \text{x}_{0},\text{x}_{\text{1}},\text{x}_{\text{2}}\text{ }...\text{x}_{\text{n}} koji zadovoljavaju uvjete:

  • varijable opisuju stanje nekog fizičkog sustava u vremenima t0, t1, t2, ...
  • prijelaz iz jednog stanja u drugo u trenutku tn opisan je matricom prijelaznih vjerojatnosti (To je matrica s elementima pij(n) , a naziva se jos i matrica prijelaznih vrijednosti)
  • lanac je markovljev ukoliko stanje sustava u trenutku tn ovisi samo o stanju u prethodnom trenutku, tj.

\text{ }P\text{     }\left\{ \text{ }\mathbf{X}_{\mathbf{n}}\text{ }=\text{ }\mathbf{s}_{\mathbf{in}}\text{ }|\text{ }\mathbf{X}_{\mathbf{n}-\mathbf{1}}\text{ }=\mathbf{s}_{\mathbf{in}-\mathbf{1}\text{ }},\text{     }...\text{ },\text{ }\mathbf{X}_{\mathbf{1}}\text{ }=\text{ }\mathbf{s}_{\mathbf{i1}}\text{ } \right\}\text{ }=\text{ }P\text{ }\{\text{ }\mathbf{X}_{\mathbf{n}}\text{ }=\text{ }\mathbf{s}_{\mathbf{in}}\text{     }|\text{ }\mathbf{X}_{\mathbf{n}-\mathbf{1}}\text{ }=\mathbf{s}_{\mathbf{in}-\mathbf{1}}\text{ }\}


Markovljevi lanci danas imaju široki spektar upotrebe, tako da se upotrebljavaju u statistici, biologiji, pa čak i u književnosti. Neka od područja primjene su: modeliranje različitih procesa u teoriji redova i statistici, aritmetičko kodiranje , populacijski procesi, upotreba u bioinformatici za genetsko kodiranje, prepoznavanje osobe na temelju slike, predviđanje vremenske prognoze, skladanje glazbe, generiranje teksta, itd.

Stohastička matrica i vektor stanja Markovljevog lanca[uredi VE | uredi]

Ako Markovljev lanac ima k mogućih stanja koje označavamo 1,2,3,...k onda se vjerojatnost da je sustav u stanju j u trenutku t+1 nakon što je bio u stanju i u trenutku t označava pij i zove se vjerojatnost prijelaza iz stanja i u stanje j. Matrica P=[ pij] se zove matrica prijelaza Markovljevoga lanca. Zbroj elemenata u svakom stupcu matrice prijelaznih vrijednosti \left( \text{p}_{\text{1j}}+\text{p}_{\text{2j}}+...+\text{p}_{\text{kj}}=\text{1} \right) naziva se stohastička matrica, matrica vjerojatnosti ili Markovljeva matrica. (u primjeru 1 uočili smo da je zbroj vjerojatnosti grana koje izlaze iz jednoga čvora 1 )

~\sum\limits_{i=1}^{n}{p_{ij}=1}


Za svako stanje i\in \left\{ 1,2,...,\left. n \right\} \right. Prijelazna vjerojatnost p_{ij} predstavlja uvjetnu vjerojatnost da će se sustav naći u j-tom stanju ako se prethodno nalazio u i-tom stanju.

Ako se vratimo na naš primjer onda možemo sa p_{1}^{1} označiti vjerojatnost da će sustav naći u stanju 1, a sa p_{2}^{1} da će sustav na početku biti u stanju 2. u našem primjeru je


p_{1}^{1}=\frac{7}{16},\text{  }p_{2}^{1}=\frac{9}{16}


Izračunajmo vjerojatnost p_{i}^{2},i\in \left\{ 1,2 \right\} da će se prilikom sljedećeg promatranja sustav nalaziti u stanju 1, odnosno 2. primjenom formule za totalnu vjerojatnost dobivamo slijedeći sustav linearnih jednadžbi :


\begin{align}
  & p_{1}^{1}p_{11}+p_{2}^{1}p_{21}=p_{1}^{2} \\ 
 & p_{1}^{1}p_{12}+p_{2}^{1}p_{22}=p_{2}^{2} \\ 
 &  \\ 
 & \text{ili u matri }\!\!\check{\mathrm{c}}\!\!\text{ nom obliku   }\left[ \text{p}_{\text{1}}^{\text{2}}\text{   p}_{\text{2}}^{\text{2}} \right]=\left[ \text{p}_{1}^{1}\text{  p}_{\text{2}}^{\text{1}} \right]\left[ \begin{matrix}
   \text{p}_{\text{11}} & \text{p}_{\text{12}}  \\
   \text{p}_{\text{21}} & \text{p}_{\text{22}}  \\
\end{matrix} \right] \\ 
\end{align}


Označimo li sa p^{1} vektor-redak početnih vrijednosti,a sa p^{2} vektor-redak vjerojatnosti u sljedećem promatranju, onda sustav možemo pisati i u skraćenom obliku :


p^{2}=p^{1}P


Ako je P matrica prijelaznih vrijednosti za Markovljev proces, a p1 vektor-redak početnih vjerojatnosti, onda je


p^{2}=p^{1}P

vektor-redak za iduće promatranje .


U našem primjeru je


p^{1}=\left[ \frac{7}{16}\text{   }\frac{\text{9}}{\text{16}} \right]\text{  pa je   p}^{\text{2}}=\left[ \frac{7}{16}\text{   }\frac{\text{9}}{\text{16}} \right]\left[ \begin{matrix}
   \frac{3}{7} & \frac{4}{7}  \\
   \frac{3}{8} & \frac{5}{8}  \\
\end{matrix} \right]=\left[ \frac{51}{128}\text{  }\frac{\text{77}}{\text{128}} \right]


Dakle, ako se sustav s vjerojatnošću p_{1}^{1}=\frac{7}{16} nalazi na početku ( to jest pri prvom promatranju) u stanju 1, a s vjerojatnošću p_{2}^{1}=\frac{9}{16} u stanju 2 onda će se s vjerojatnošću p_{1}^{2}=\frac{51}{128} nalaziti u stanju 1 pri slijedećem promatranju.

Regularni Markovljevi Lanci[uredi VE | uredi]

Markovljev lanac koji je određen regularnom matricom prijelaza se zove regularni markovljev lanac. Matrica prijelaza je regularna ako neke njezine cijelobrojne potencije imaju sve pozitivne unose. Markovljev lanac ima stalan vektor stanja q takav da P^{n}x^{(0)} ide prema 'q' kako se 'n' proizvoljno povećava za x^{(0)}. Zaključujemo da će vektor stanja u sustav nakon n promatranja postati stalan i tada će za svaki ishod biti jednaka prethodnoj.


Pouzdani vektor stanja[uredi VE | uredi]

Zamislimo da je Q takva prijelazna matrica čiji su svi stupci jednaki vektoru vjerojatnosti q. Takva matrica će svaki vektor stanja transformirati u stalni vektor stanja. Teorem koji govori (a ovdje nije naveden) da je zbroj stupaca u bilo kojem promatranju za P^{n} jednak 1 implicira P^{n}\to Q tako da n\to \infty . Ovo dalje implicira P^{n}x\to Qx=q tako da n\to \infty . Stoga, za regularni Markovljev lanac, sustav se približava fiksnome vektoru stanja q. Vektor q se zove pouzdani vektor stanja. Za sustave s mnogo stanja, obično najučinkovitiji način za računanje pouzdanoga vektora stanja jest da se izračuna P^{n}x za neki veliki n.