Markovljev lanac
U matematici Markovljev lanac nazvan po Andreju Andrejeviču 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
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
- [math]\displaystyle{ \Pr(X_{n+1}=x|X_n=x_n, \ldots, X_1=x_1) = \Pr(X_{n+1}=x|X_n=x_n).\, }[/math]
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
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 sljedeć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 sljedeć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 sljedeća pitanja:
- Ako je sustav sada u stanju C, kolika je vjerojatnost da će pri sljedećem promatranju biti u stanju C?
- Ako je sustav sad u stanju C, kolika je vjerojatnost da će pri sljedećem promatranju biti u stanju Z?
- Ako je sustav sad u stanju Z, kolika je vjerojatnost da će pri sljedećem promatranju biti u stanju C?
- Ako je sustav sad u stanju Z, kolika je vjerojatnost da će pri sljedeć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“ ) = [math]\displaystyle{ \frac{3}{7} }[/math],a
p („sustav je bio u stanju C i prešao u stanje Z“) = [math]\displaystyle{ \frac{4}{7} }[/math]
Iz niza (*) zaključujemo da je
p („sustav je bio u stanju Z i ostao u stanju Z“) = [math]\displaystyle{ \frac{5}{8} }[/math]
p („sustav je bio u stanju Z i prešao u stanje C“) =[math]\displaystyle{ \frac{3}{8} }[/math]
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 [math]\displaystyle{ p_{ij} }[/math], 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
[math]\displaystyle{ \text{x}_{0},\text{x}_{\text{1}},\text{x}_{\text{2}}\text{ }...\text{x}_{\text{n}} }[/math] 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.
[math]\displaystyle{ \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{ }\} }[/math]
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
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
[math]\displaystyle{ \left( \text{p}_{\text{1j}}+\text{p}_{\text{2j}}+...+\text{p}_{\text{kj}}=\text{1} \right) }[/math] 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 )
[math]\displaystyle{ ~\sum\limits_{i=1}^{n}{p_{ij}=1} }[/math]
Za svako stanje [math]\displaystyle{ i\in \left\{ 1,2,...,\left. n \right\} \right. }[/math]
Prijelazna vjerojatnost [math]\displaystyle{ p_{ij} }[/math] 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 [math]\displaystyle{ p_{1}^{1} }[/math] označiti vjerojatnost da će sustav naći u stanju 1, a sa [math]\displaystyle{ p_{2}^{1} }[/math] da će sustav na početku biti u stanju 2. u našem primjeru je
[math]\displaystyle{ p_{1}^{1}=\frac{7}{16},\text{ }p_{2}^{1}=\frac{9}{16} }[/math]
Izračunajmo vjerojatnost [math]\displaystyle{ p_{i}^{2},i\in \left\{ 1,2 \right\} }[/math] da će se prilikom sljedećeg promatranja sustav nalaziti u stanju 1, odnosno 2. primjenom formule za totalnu vjerojatnost dobivamo sljedeći sustav linearnih jednadžbi :
[math]\displaystyle{ \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} }[/math]
Označimo li sa [math]\displaystyle{ p^{1} }[/math] vektor-redak početnih vrijednosti,a sa [math]\displaystyle{ p^{2} }[/math] vektor-redak vjerojatnosti u sljedećem promatranju, onda sustav možemo pisati i u skraćenom obliku :
[math]\displaystyle{ p^{2}=p^{1}P }[/math]
Ako je P matrica prijelaznih vrijednosti za Markovljev proces, a p1 vektor-redak početnih vjerojatnosti, onda je
[math]\displaystyle{ p^{2}=p^{1}P }[/math]
vektor-redak za iduće promatranje .
U našem primjeru je
[math]\displaystyle{ 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] }[/math]
Dakle, ako se sustav s vjerojatnošću [math]\displaystyle{ p_{1}^{1}=\frac{7}{16} }[/math] nalazi na početku ( to jest pri prvom promatranju) u stanju 1, a s vjerojatnošću [math]\displaystyle{ p_{2}^{1}=\frac{9}{16} }[/math] u stanju 2 onda će se s vjerojatnošću [math]\displaystyle{ p_{1}^{2}=\frac{51}{128} }[/math] nalaziti u stanju 1 pri sljedećem promatranju.
Regularni Markovljevi Lanci
Markovljev lanac koji je određen regularnom matricom prijelaza se zove regularni markovljev lanac. Matrica prijelaza je regularna ako neke njezine cjelobrojne potencije imaju sve pozitivne unose. Markovljev lanac ima stalan vektor stanja q takav da [math]\displaystyle{ P^{n}x^{(0)} }[/math] ide prema 'q' kako se 'n' proizvoljno povećava za [math]\displaystyle{ x^{(0)} }[/math]. 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
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 [math]\displaystyle{ P^{n} }[/math] jednak 1 implicira [math]\displaystyle{ P^{n}\to Q }[/math] tako da [math]\displaystyle{ n\to \infty }[/math]. Ovo dalje implicira [math]\displaystyle{ P^{n}x\to Qx=q }[/math] tako da [math]\displaystyle{ n\to \infty }[/math]. 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 [math]\displaystyle{ P^{n}x }[/math] za neki veliki n.