Markovi ahel

**Markovi ahelaks** (vene matemaatiku Andrei Markov seeniori nime järgi) nimetatakse matemaatikas lõpliku või loenduva olekute hulgaga diskreetse ajaga juhuslikku protsessi, millel on Markovi omadus.

Markovi omadus tähendab, et fikseeritud oleviku korral tulevik ei sõltu minevikust. Teiste sõnadega, olevikuseisundi kirjeldus sisaldab kogu informatsiooni, mis võib protsessi tulevast arengut mõjutada.

## Definitsioon
Markovi ahel on juhuslike muutujate jada *X*1, *X*2, *X*3, ..., millel on Markovi omadus:

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

Muutujate *X**i* võimalikud väärtused moodustavad lõpliku või loenduva hulga *S*, mida nimetatakse ahela **olekute ruumiks**.

Markovi ahelat kujutatakse tihti suunatud graafina, mille servade juurde on kirjutatud ühest olekust teistesse ülemineku tõenäosused.

### Modifikatsioonid
Pideva ajaga Markovi ahelatel on pidevalt muutuv indeks.

Ajaliselt homogeenne Markovi ahel (ajaliselt homogeensete üleminekutõenäosustega Markovi ahel) on Markovi ahel, kus *n* kõigi väärtuste korral

:\Pr(X_{n+1}=x|X_n=y) = \Pr(X_{n}=x|X_{n-1}=y)\, .

*m*-ndat järku Markovi ahel ehk Markovi ahel mäluga *m* (*m* on lõplik) on Markovi ahel, milles iga *n* korral

:\Pr(X_n=x_n|X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2}, \dots , X_{1}=x_{1})
:  = \Pr(X_n=x_n|X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2}, \dots, X_{n-m}=x_{n-m}) ,

st tulevik sõltub ainult olekutest viimasel *m* hetkel. Ahelast (*X<sub>n</sub>*) saab konstrueerida ahela (*Y<sub>n</sub>*), millel on "klassikaline" Markovi omadus. Nimelt, olgu   
*Y<sub>n</sub>* = (*X<sub>n</sub>*; *X**n*&minus;1; ...; *X**n*&minus;*m*+1) *X* väärtuste ''m''-korteež. Sel juhul on *Y<sub>n</sub>* klassikalise Markovi omadusega Markovi ahel.

Markovi ahelad võib esitada lõplike automaatidena. Kui automaat on hetkel *n* olekus *y*, siis tõenäosus, et ta hetkel *n*&nbsp;+&nbsp;1 läheb üle olekusse *x*, sõltub ainult olekust hetkel *n*.

## Markovi ahelate omadused

Olgu *n* ajasammuga olekust *i* olekusse *j* jõudmise tõenäosus defineeritud kui

:p_{ij}^{(n)} = \Pr(X_n=j\mid X_0=i) \,

ja ühe ajasammuga olekust *i* olekusse *j* ülemineku tõenäosus kui

:p_{ij} = \Pr(X_1=j\mid X_0=i). \,

*n* sammuga üleminek rahuldab Chapmani-Kolmogorovi võrrandit, mille järgi iga *k* (0 p_{ij}^{(n)} = \sum_{r \in S} p_{ir}^{(k)} p_{rj}^{(n-k)}.

Marginaaljaotus Pr (*X**n* = *x*) on olekutevaheline jaotus hetkel *n*. Algjaotus on Pr (*X*0 = *x*).  Protsessi kulgu sammude kaupa kirjeldab valem

:  \Pr(X_{n}=j) = \sum_{r \in S} p_{rj} \Pr(X_{n-1}=r) = \sum_{r \in S} p_{rj}^{(n)} \Pr(X_0=r).

Ülaindeks (n) on mõeldud lihtsalt täisarvulise indeksina. Ent kui Markovi ahel on homogeenne, siis võib seda ülaindeksit tõlgendada ka astmenäitajana.

### Taanduvus

Olekut *j* nimetatakse teisest olekust *i* **kättesaadavaks** (*accessible*; tähistus *i* → *j*), kui eeldusel, et ollakse olekus *i*, on nullist erinev tõenäosus, et millalgi tulevikus ollakse olekus *j* . Teiste sõnadega, olek *j* on olekust *i* kättesaadav, kui leidub niisugune täisarv *n* &ge; 0, et

:  \Pr(X_{n}=j | X_0=i) > 0.\, 

Selles definitsioonis lubatakse ka *n* väärtust 0, mistõttu iga olek on selle definitsiooni järgi kättesaadav ka iseendast.

Öeldakse, et olek *i* **lävib** seisundiga *j* (*i* ↔ *j*), kui olek *i* on kättesaadav olekust *j* ning olek *j* on kättesaadav olekust *i*. Olekute hulk *C* on **läviv klass**, kui mis tahes kaks olekut hulgast *C* lävivad teineteisega ja ükski olek hulgast *C* ei lävi ühegi olekuga, mis ei kuulu hulka *C*. (Saab näidata, et lävimine on ekvivalentsusseos.) Läviv klass on **kinnine**, kui klassist lahkumise tõenäosus (*probability of leaving the class*) on null: kui olek *i* asub lävivas klassis *C*, kuid olek *j* mitte, siis olek *j* ei ole kättesaadav olekust *i*.

Markovi ahel on **taandumatu**, kui tema olekute ruum on läviv klass. Teiste sõnadega, taandumatus Markovi ahelas on mis tahes olek kättesaadav mis tahes olekust.

### Perioodilisus
Olekul *i* on **periood** *k*, kui mis tahes naasmine (*return*) olekusse *i* peab toimuma *k* kordse arvu ajasammude möödudes. Näiteks kui olekusse *i* on võimalik naasta ainult paarisarvu sammude möödudes, siis *i* on perioodiline perioodiga 2. Oleku periood on

:  k = \operatorname{SYT}\{ n: \Pr(X_n = i | X_0 = i) > 0\}
(kus "SYT" on suurim ühistegur). Pandagu tähele, et kui mingil olekul on periood *k*, ei pruugi sellesse olekusse olla võimalik *k* sammuga naasta. Näiteks kui olekusse on võimalik naasta {6, 8, 10, 12, ...} ajasammuga, siis *k* on 2, kuigi 2 selles loetelus ei esine.

Kui *k* = 1, siis nimetatakse olekut **aperioodiliseks**. Kui *k*>1, siis nimetatakse olekut **perioodiliseks perioodiga ''k***.

Saab näidata, et lävivas klassis on kõigil olekutel üks ja seesama periood.

Lõpliku olekute arvuga taandumatut Markovi ahelat nimetatakse *'ergoodiliseks**, kui tema olekud on aperioodilised.

===Naasmine===
Olekut ''i'' nimetatakse **siirdeolekuks** (''transient''), kui on nullist erinev tõenäosus, et alustades olekust ''i'' ei naasta kunagi olekusse ''i''. Olgu [[juhuslik muutuja]] ''T<sub>i</sub>'' esimene naasmisaeg olekusse ''i'' ("tabamisaeg" (''"hitting time"'')):

: <math> T_i = \inf \{ n: X_n = i | X_0 = i\}</math>

Siis olek ''i'' on siirdeolek [[siis ja ainult siis, kui]]

: <math> \Pr(T_i = {\infty}) > 0. </math>

Kui olek ''i'' on ei ole siirdeolek (tal on tõenäosusega 1 lõplik tabamisaeg), siis teda nimetatakse **naasvaks**. Kuigi tabamisaeg on lõplik, ei pruugi tal olla  lõplikku [[matemaatiline ootus|matemaatilist ootust]].

Olgu ''M<sub>i</sub>'' naasmisaja matemaatiline ootus

: <math> M_i = E[T_i].\, </math>

Siis olek ''i'' on **püsiv**, kui ''M<sub>i</sub>'' on lõplik. Vastasel juhul on olek ''i'' **nullsiirdeolek** (''null recurrent'').

Saab näidata, et olek on naasev (''recurrent'') siis ja ainult siis, kui

: <math>\sum_{n=0}^{\infty} p_{ii}^{(n)} = \infty</math>

Olekut ''i'' nimetatakse **neelavaks**, kui sellest olekut on võimatu lahkuda. Seega on olek ''i'' on neelav siis ja ainult siis, kui

: <math> p_{ii} = 1</math> ning <math> p_{ij} = 0</math>, kui <math>i \not= j.</math>

===Ergoodilisus===
Olekut ''i'' nimetatakse **ergoodiliseks**, kui ta on aperioodiline ja püsiv. Kui Markovi ahela kõik olekud on ergoodilised, siis ahelat nimetatakse ergoodiliseks.

===Püsivate seisundite analüüs ja piiravad jaotused===
(''Steady-state analysis and limiting distributions'')

Kui Markovi ahel on homogeenne, nii et protsess on kirjeldatav üheainsa ajast sõltumatu maatriksiga ''p''<sub>''ij''</sub>, siis vektor ''π'' on **statsionaarne jaotus** (''stationary distribution'') (ka **tasakaalus jaotus**, **invariantne mõõt**), kui selle koordinaatide (''entries'') ''π<sub>j</sub>'' summa on 1 ning nad rahuldavad võrrandit

: <math>\pi_j = \sum_{i \in S} \pi_i p_{ij}.</math>

Taandumatul ahelal on statsionaarne jaotus siis ja ainult siis, kui kõik selle olekud on püsivad. Sel juhul leidub ainult üks statsionaarne jaotus ''π'' ning ta on seotud naasmisaja matemaatilise ootusega:

: <math>\pi_j = \frac{1}{M_j}.\,</math>

Kui ahel on taandumatu ja ühtlasi aperioodiline, siis mis tahes ''i'' ja ''j'' korral

: <math>\lim_{n \rarr \infty} p_{ij}^{(n)} = \frac{1}{M_j}.</math>

Algsele jaotusele ei ole siin mingit piirangut. Ahel koondub statsionaarse jaotusega ahelaks sõltumata algsest olekust.

Kui ahel ei ole taandumatu, siis ei ole tal ühtset statsionaarset jaotust. (Igal kinnisel lävival klassil on oma ainus statsionaarne jaotus. Igaüks neist laieneb kogu ahela statsionaarseks jaotuseks, kus tõenäosus väljaspool klassi on nullile lähenev hulk (''set to zero'').) Samas, kui olek ''j'' on aperioodiline, siis

: <math>\lim_{n \rarr \infty} p_{jj}^{(n)} = \frac{1}{M_j}</math>

ja iga teise oleku ''i'' puhul olgu ''f<sub>ij</sub>'' tõenäosus, et startides olekust ''i'', läbib (''visits'') ahel kunagi olekut ''j''

: <math>\lim_{n \rarr \infty} p_{ij}^{(n)} = \frac{f_{ij}}{M_j}.</math>

==Lõpliku seisundite ruumiga Markovi ahelad==

Kui olekute ruum on lõplik, transitsiooni tõenäolist jaotust (''transition probability distribution'') võib kujutada transitsioonimaatriksina, milles element **p** järjekorranumbriga (''i'', ''j'') võrdub

:<math>p_{ij} = \Pr(X_{n+1}=j\mid X_n=i). \,</math>

**P** on [[stohhastiline maatriks]]. Kui Markovi ahel on ajaliselt homogeenne (''time-homogeneous'') Markovi ahel, siis transitsioonimaatriks **P** on sõltumatu tähisest ''n'' ning ''k''-astmelise transitsioonitõenäosuse võib arvutada transitsioonimaatriksi astmel ''k'', **P**<sup>''k''</sup>.

Olekujaotus (''stationary distribution'') ''π'' on (jada) [[vektor]], mis rahuldab võrrandit

:<math> \pi = \pi\mathbf{P}.\,</math>

Teisisõnu, olekujaotus ''π'' on normaliseerimisel saadud transitsioonimaatriksi omadusvektor (''normalized left eigenvector''), mis on seotud omadusväärtusega (''eigenvalue'') 1.

Väärtust ''π'' võib vaadelda lineaarse (järelikult pideva) maatriksiga **P** seotud ühiksimpleksi (''unit simplex'') transformatsiooni fikseeritud punktina.

Iga pideva transformatsiooni (''continuous transformation'') puhul on ühiksimpleksil kindel punkt, milles alati eksisteerib olekujaotus, kuid üldiselt ei ole garanteeritud, et see on ainukordne. Ometi, kui Markovi ahel on redutseerimatu ja aperioodiline, eksisteerib ainukordne olekujaotus **π**. Lisaks läheneb (''converges'') **P**<sup>''k''</sup> üheveeruline maatriks (''rank-one matrix''), milles iga rida on olekujaotus **π**

:<math>\lim_{k\rightarrow\infty}\mathbf{P}^k=\mathbf{1}\pi</math>

kus **1** on veeru vektor (''column vector'') kõigi väärtuste jaoks, mis võrduvad 1. Seda väidab [[Perron-Frobeniuse teoreem]]. See tähendab, et aja möödudes "unustab" Markovi ahel oma algjaotuse ning läheneb oma olekujaotusele.

==Pöörduv Markovi ahel==

Pöörduva (''reversible'') Markovi ahela idee tuleneb võimest "inverteerida" (''"invert"'') tõenäosuse tingimuslikkust kasutavat [[Bayes' seadus]]t:

:<math>\Pr(X_{n}=i\mid X_{n+1}=j) = \frac{\Pr(X_n = i, X_{n+1} = j)}{\Pr(X_{n+1} = j)}</math>
::::::<math> = \frac{\Pr(X_{n} = i)\Pr(X_{n+1} = j\mid X_n=i)}{\Pr(X_{n+1} = j)}. \,</math>

Ilmneb, et aeg on pöörduv. Järelikult võib Markovi ahel olla **pöörduv*' (*reversible*), kui see on *π*, nagu näiteks

:<math>\pi_i p_{i,j} = \pi_j p_{j,i}.\,</math>

Seda tingimust tuntakse ka detailse tasakaalu tingimusena (*detailed balance*).

Summeerides (*summing over*) <math>i</math> annab

:<math>\sum_i \pi_i p_{i,j} = \pi_j\,</math>

pöörduvate Markovi ahelate puhul, et *π* on alati olekujaotus.

==Bernoulli skeem==
(*A Bernoulli scheme*)

[[Bernoulli skeem]] on Markovi ahela erijuhtumiks, kus transitsioonide tõenäosusmaatriksil (*transition probability matrix*) on identsed read, mis tähendab, et ka järgmine olek on sõltumatu käesolevast (lisaks sellele, et ta on sõltumatu mineviku olekutest). Ainult kahe võimaliku olekuga Bernoulli skeem on tuntud kui [[Bernoulli protsess]].

==Üldise olekuruumiga Markovi ahelad==
(*Markov chains with general state space*)



==Rakendused==
===Füüsika===


===Katsetamine===
(*Testing*)


===Järjestusteooria===
(*Queueing theory*)



===Internetirakendused===



===Statistika===


===Majandusteadus===


===Matemaatiline bioloogia===



===Mänguteooria===
(*Gambling*)



===Muusika===
Markovi ahelaid on kasutatud [[algoritmiline komponeerimine|algoritmilisel komponeerimisel]], kasutades selleks näiteks [[muusikatarkvara]] [[Open Music]], [[CSound]] või [[Max]].

Esimese tasandi järjestusega ahelate (*first-order chain*) puhul saavad olekutest heli [[väärtus (matemaatika)|väärtused]] ning igale helile konstrueeritakse tõenäosusvektor, saades nii üleminekute tõenäolise [[maatriks]]i (*transition probability matrix*). [[Algoritm]]i konstrueerimise eesmärgiks on toota üleminekute maatriksi väärtustel põhinevaid [[muusikaline parameeter|muusikaliste parameetrite]] väärtusi: näiteks [[MIDI]] väärtusi, [[helisagedus]]i hertsides, [[helivältus]]te suurusi või muude muusikaliste parameetrite väärtusi.




Teise tasandi Markovi ahelaid (*second-order Markov chain*) võib kasutada, arvestades käesolevat *ja* ka eelmist olekut.




Kõrgematel tasanditel, *n*-tasandi järjestusega ahelate (* *n*th-order chains*) puhul rühmituvad algsed helid helide rühmadeks, 'purunedes' samal ajal juhuslikeks kujunditeks ja järgnevusteks. Sellised kõrgema tasandi ahelad genereerivad muusikalise fraasi tasemel struktuure, sel ajal kui esimese tasandi järjestusega süsteem toodab 'sihitut ekslemist'.

===Pesapall===


===Kirjandus: Markovi paroodiageneraatorid===
(*Markov parody generators*)

Markovi protsesse võib kasutada ka antud tekstikatkest pealiskaudsel vaatlusel reaalsena näivate uute tekstide genereerimiseks. Meetodit on kasutatud erinevate taasloovate "paroodiageneraatorite" tarkvara puhul (vt [[dissociated press]], [[Jeff Harrison]], [[Mark V Shaney]],
          
).

==Teooria ajalugu==
[[Andrei Markov]] vanem sai aastal 1906 nende protsesside esimesi tulemusi alguses puhtalt teoreetiliselt. Arvutuslikult lõpetatud seisundiruumide (*countably infinite state spaces*) üldistuse esitas [[Andrei Nikolajevitš Kolmogorov]] aastal 1936. Markovi ahelaid on seostatud [[Browni liikumine|Browni liikumisega]] ja ergoodilise hüpoteesiga, mis on ühtedeks tähtsamateks teemadeks 20.sajandi alguse füüsikas.



==Vaata ka==

==Viited==


==Kirjandus==
*  A.A. Markov. "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". *Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete*, 2-ya seriya, tom 15, pp 135–156, 1906.
* A.A. Markov. "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: R. Howard. *Dynamic Probabilistic Systems, volume 1: Markov Chains*. John Wiley and Sons, 1971.
* Classical Text in Translation: A. A. Markov, An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains, trans. David Link. Science in Context 19.4 (2006): 591-600. Online: http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=637500
* Leo Breiman. *Probability*. Original edition published by Addison-Wesley, 1968; reprinted by Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-296-3. *(See Chapter 7.)*
* J.L. Doob. *Stochastic Processes*. New York: John Wiley and Sons, 1953.  ISBN 0-471-52369-0.
* S. P. Meyn and R. L. Tweedie. *Markov Chains and Stochastic Stability*. London: Springer-Verlag, 1993.  ISBN 0-387-19832-6. online: http://decision.csl.uiuc.edu/~meyn/pages/book.html .  Second edition to appear, Cambridge University Press, 2008.
* S. P. Meyn. *Control Techniques for Complex Networks*. Cambridge University Press, 2007. ISBN 9780521884419.  Appendix contains abridged Meyn & Tweedie.  online:    http://decision.csl.uiuc.edu/~meyn/pages/CTCN/CTCN.html
* Extensive, wide-ranging book meant for specialists, written for both theoretical computer scientists as well as electrical engineers. With detailed explanations of state minimization techniques, FSMs, Turing machines, Markov processes, and undecidability. Excellent treatment of Markov processes pp.&nbsp;449ff. Discusses Z-transforms, D transforms in their context.
* Classical text. cf Chapter 6 *Finite Markov Chains* pp.&nbsp;384ff.

==Välislingid==
*[http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter11.pdf (pdf) Markov Chains chapter in American Mathematical Society's introductory probability book]
*[http://www.utilitymill.com/utility/Markov_Chain_Parody_Text_Generator Generates random parodies in the style of another body of text using a Markov chain algorithm]
*[http://www.fourteenminutes.com/fun/words/ A generator that uses Markov Chains to create random words]
*[http://crypto.mat.sbg.ac.at/~ste/diss/node6.html Markov Chains]
*[http://www.math.rutgers.edu/courses/338/coursenotes/chapter5.pdf Chapter 5: Markov Chain Models]
*[http://www.cs.bell-labs.com/cm/cs/pearls/sec153.html Generating Text] *(About generating random text using a Markov chain.)*
*[http://www.mathworks.com/company/newsletters/news_notes/clevescorner/oct02_cleve.html The World's Largest Matrix Computation] *(Google's PageRank as the stationary distribution of a random walk through the Web.)''
*Dissociated Press in Emacs approximates a Markov process
*Markov Chain Example
*Markov Chains for Search Engines
*Steganography proof-of-concept using Markov Chains.
*n<sup>th</sup> order Markov Chain implementation in Ruby
*Baseball Run Modeler using Markov Chains
*Theory of Markov chains in baseball
* Sequential analysis software for generating visual representations of probability models