Markova ķēde

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:
+Saskaitāms
stāvokļu skaitsNepārtraukts
stāvokļu skaitsDiskrēts
laiksGalda spēle cirks, 
teksta ģenerēšanaŠautriņas metiensNepārtraukts
laiksĶīmiskais līdzsvars,
radioaktīvā sabrukšana,
veikalā esošu cilvēku skaitsBrauna kustība
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ērojamsSistēmas stāvoklis
ir daļēji novērojamsSistēma ir
autonomaMarkova ķēdeLaikapstākļu minēšanas
modelisSistēmā ir
izvēles elementsKvantu krustiņi un nullītesFinanš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ā , ka priekš jebkura  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 , kur   ir matricjas i-tā rinda, j-tā kolonna.

Piemēram, pirmā attēla Markova ķēdi var pierakstīt šādi: .

 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: . Sākot kādā vienā stāvoklī, pietiekami daudz reižu reizinot ar Markova matricu, tiek sasniegts stacionārais sadalījums: . Matricas formā stacionārā sadalījuma īpašību pieraksta kā . Atrisiont šo matricu veidoto lineāru vienādojumu sistēmu un normalizējot ar (varbūtību summa ir 1), iegūst stacionārā sadalījuma vektoru: . Š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. 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: . 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 , kur šī matrica tiecas uz nulles matricu: . Lai iegūtu sagaidāmo vērtību atrasties uz katra lauciņa jāsaskaita bezgalīgi daudz matricu: . Pareizinot no kreisās puses ar , kur  ir vienības matrica iegūst: , kur pēc iekavu atvēršanas labajā pusē iegūst: , bet , tādēļ , bet, izmantojot inversās matricu īpašībau , iegūst . Šoreiz šai matricai ir vērtības: , 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 

Kategorija:Varbūtību teorija
Kategorija:Statistika