Markova ķēde

Markova procesa diagramma- no katra stāvokļa izejošās bultiņas ar skaitļiem norāda varbūtību. No stāvokļa izejošo varbūtību summai jābūt 1 (visa varbūtība)

Markova ķēde, arī Markova process ir gadījuma rakstura process, kas raksturo virkni iespējamiem notikumiem. Katra virknes nākamā locekļa iespējamās varbūtības ir atkarīgas tikai no pašreizējā stāvokļa un ir neatkarīgas no iepriekšējo stāvokļu vēstures.

Markova ķēdes pielieto, lai veidotu statistiskus modeļus pasaules procesiem. Tie ir pamats Monte Karlo metodēm, lai iegūtu vērtības no varbūtību sadalījuma funkcijām, kas ir atradis pielietojumu Beiesa statistikā, bioloģijā, ķīmijā, ekonomikā, finansē, informācijas teorijā, fizikā, signālu apstrādē un valodas apstrādē.

Markova ķēžu veidi

Markova ķēde iedala pēc to iespējamo stāvokļu veida (galīgs skaits vai bezgalīgs skaits iznākumu) un laika solis starp stāvokļu maiņu (diskrēts vai nepārtraukts). Tabulā var redzēt piemērus dažādiem Markova processiem:


	Saskaitāms stāvokļu skaits	Nepārtraukts stāvokļu skaits
Diskrēts laiks	Galda spēle cirks, teksta ģenerēšana	Šautriņas metiens
Nepārtraukts laiks	Ķīmiskais līdzsvars, radioaktīvā sabrukšana, veikalā esošu cilvēku skaits	Brauna kustība

Piemērs daļēji novērotam Markova gadījuma lielumam- Alise sazinās ar Bobu katru dienu, Bobs pastāsta, ko todien darīja, taču šī darbība ir atkarīga no tās dienas laikapstākļiem. Boba darbība līdz ar to liecina par tās dienas laikapstākļiem

Markova ķēžu modeļus izmanto mainīgās sistēmās. Markova ķēdes var vispārināt atkarībā no tā vai tiek novērtots katrs stāvoklis vai nē un vai sistēma iekļauj vai neiekļauj izvēles elementu. Tabulā var redzēt piemērus šādiem Markova processiem:

	Sistēmas stāvoklis ir novērojams	Sistēmas stāvoklis ir daļēji novērojams
Sistēma ir autonoma	Markova ķēde	Laikapstākļu minēšanas modelis
Sistēmā ir izvēles elements	Kvantu krustiņi un nullītes	Finanšu tirgus modelis

Markova ķēžu matemātika

Markova īpašība

Markova īpašība apgalvo, ka nākamais procesa stāvoklis ir atkarīgs tikai no esošā stāvokļa. Matemātiski tas pierakstās kā $P(X_{m+1}=i_{m+1}|X_{m}=i_{m})$ , ka priekš jebkura $m$ nākamais gadījuma notikums ir atkarīgs tikai no šī grīža gadījuma notikuma.^[1]

Markova ķēdes matrica

Markova ķēdes varbūtību sadalījumu var pierakstīt ar matricas palīdzību. Katru matricas ierakstu var aprēķināt pēc formulas $p_{ij}=P(X_{m+1}=j|X_{m}=i)$ , kur $p_{ij}$ ir matricjas i-tā rinda, j-tā kolonna.

Piemēram, pirmā attēla Markova ķēdi var pierakstīt šādi: ${\boldsymbol {P}}={\begin{pmatrix}0&0.2&0.8\\0.5&0&0.5\\0.1&0.9&0\end{pmatrix}}$ .

Markova matricas stacionārais sadalījums

Pēc pietiekami ilga laika, stāvokļa vektors beidz mainīties, kad to reizina ar Markova matricu. Matemātiski to pieraksta kā matricu reizinājumu: ${\boldsymbol {P\pi }}={\boldsymbol {\pi }}$ . Sākot kādā vienā stāvoklī, pietiekami daudz reižu reizinot ar Markova matricu, tiek sasniegts stacionārais sadalījums: $\lim _{n\to \infty }{\boldsymbol {P^{n}x_{0}}}={\boldsymbol {\pi }}$ .^[2] Matricas formā stacionārā sadalījuma īpašību pieraksta kā ${\begin{pmatrix}0&0.2&0.8\\0.5&0&0.5\\0.1&0.9&0\end{pmatrix}}{\begin{pmatrix}\pi _{1}\\\pi _{2}\\\pi _{3}\end{pmatrix}}={\begin{pmatrix}\pi _{1}\\\pi _{2}\\\pi _{3}\end{pmatrix}}$ . Atrisiont šo matricu veidoto lineāru vienādojumu sistēmu ${\begin{cases}0.2\pi _{2}+0.8\pi _{3}=\pi _{1}\\0.5\pi _{1}+0.5\pi _{3}=\pi _{2}\\0.1\pi _{1}+0.9\pi _{2}=\pi _{3}\end{cases}}$ un normalizējot ar $\pi _{1}+\pi _{2}+\pi _{3}=1$ (varbūtību summa ir 1), iegūst stacionārā sadalījuma vektoru: ${\boldsymbol {\pi }}={\begin{pmatrix}{\frac {55}{237}}\\{\frac {92}{237}}\\{\frac {30}{79}}\end{pmatrix}}$ . Šo var interpretēt tā, ka pēc lielo skaitļu likuma (ar daudziem mērījumiem) ~23% laika tiks pavadīts 1.stāvoklī, ~39% laika tiks pavadīts 2.stāvoklī un ~38 % laika tiks pavadīts 3.stāvoklī.

Absorbējošas Markova matricas

Absorbējošām Markova matricām ir tāds stāvoklis, no kura nevar izkļūt.^[3] Viens no šo matricu raksturlielumiem ir sagaidāmā vērtība atrasties katrā no stāvokļiem pirms absorbējošā stāvokļa sasniegšanas. Attēlā redzamā grafika atbilst absorbējošam procesam un tā Markova matrica ir: ${\boldsymbol {Q}}={\begin{pmatrix}{\frac {1}{2}}&{\frac {1}{2}}&0\\{\frac {1}{2}}&0&{\frac {1}{2}}\\{\frac {1}{2}}&0&0\end{pmatrix}}$ . Katra kolonna atbilst varbūtībai atrasties pirmajā, otrajā vai trešajā stāvoklī savukārt rinda norāda kurā stāvoklī bija sākuma stāvoklis. Lai iegūtu varbūtību atrasties kādā no stāvokļiem pēc n gājieniem ir jāaprēķina kāpinātā matrica ${\boldsymbol {Q}}^{n}$ , kur šī matrica tiecas uz nulles matricu: $\lim _{n\to \infty }{\boldsymbol {Q}}^{n}={\boldsymbol {0}}$ . Lai iegūtu sagaidāmo vērtību atrasties uz katra lauciņa jāsaskaita bezgalīgi daudz matricu: ${\boldsymbol {N}}=\sum _{k=0}^{\infty }{\boldsymbol {Q}}^{k}$ . Pareizinot no kreisās puses ar $({\boldsymbol {I-Q}})$ , kur ${\boldsymbol {I}}$ ir vienības matrica iegūst: ${\boldsymbol {(I-Q)N}}={\boldsymbol {(I-Q)(I+Q+Q^{2}+Q^{3}+...)}}$ , kur pēc iekavu atvēršanas labajā pusē iegūst: ${\boldsymbol {(I-Q)N}}={\boldsymbol {I-Q^{\infty }}}$ , bet $\lim _{n\to \infty }{\boldsymbol {Q}}^{n}={\boldsymbol {0}}$ , tādēļ ${\boldsymbol {(I-Q)N}}={\boldsymbol {I}}$ , bet, izmantojot inversās matricu īpašībau ${\boldsymbol {AA^{-1}}}={\boldsymbol {I}}$ , iegūst ${\boldsymbol {N}}={\boldsymbol {(I-Q)^{-1}}}$ . Šoreiz šai matricai ir vērtības: ${\boldsymbol {N}}={\begin{pmatrix}8&4&2\\6&4&2\\4&2&2\end{pmatrix}}$ , kur pirmā rinda norāda sagaidāmās vērtības atrasties pirmajā, otrajā vai trešajā stāvoklī pirms sasnigegts absorbējošais stāvoklis, pie nosacījuma, ka process sākās pirmajā stāvoklī (šis ir atkarīgs no rindas). Saskaitot visus pirmās rindas locekļus iegūst sagaidāmo gājienu skaitu līdz tiek sasniegts absorbējošais stāvoklis.