Markova ķēde

thumb|300x300px|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 kumulatīvā 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:

thumb|300x300px|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:

## 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.

### 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}. 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
thumb|300x300px|Absorbējošās Markova ķēdes piemērs ar monētu- tā absorbējas, kad uzmet secīgi ģerboni, valūtu un ģerboni (HTH).
Absorbējošām Markova matricām ir tāds stāvoklis, no kura nevar izkļūt. 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{A A^{-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.

Vēl kā absorbējošo Markova matricu var interpretēt galda spēli cirks, kur uzvaras stāvoklis ir absorbējošais stāvoklis.

## Atsauces