A matematikában a Markov-lánc egy olyan diszkrét sztochasztikus folyamatot jelent, amely Markov-tulajdonságú. Nevét egy orosz matematikusról, Andrej Markovról kapta, aki hírnevét a tudomány ezen ágában végzett kutatásaival szerezte. Markov-tulajdonságúnak lenni röviden annyit jelent, hogy adott jelenbeli állapot mellett, a rendszer jövőbeni állapota nem függ a múltbeliektől. Másképpen megfogalmazva ez azt is jelenti, hogy a jelen leírása teljesen magába foglalja az összes olyan információt, ami befolyásolhatja a folyamat jövőbeli helyzetét. Vegyünk például egy olyan fizikai rendszert, amelynek lehetséges állapotai . Az S rendszer az idő múlásával állapotait véletlenszerűen változtatja; vizsgáljuk a rendszer állapotait a diszkrét időpontokban, és legyen egyenlő k-val, ha S az n időpontban az állapotban van. Ezzel a terminológiával a Markov-tulajdonság így is megfogalmazható: A rendszer korábbi állapotai a későbbi állapotokra csak a jelen állapoton keresztül gyakorolhatnak befolyást.

Adott jelen mellett tehát a jövő feltételesen független a múlttól. Semmi, ami a múltban történt, nem hat, nem ad előrejelzést a jövőre nézve, a jövőben minden lehetséges. Alapvető példa erre az érmedobás – ha fejet dobunk elsőre, másodikra ugyanúgy 50/50%-kal dobhatunk írást vagy fejet egyaránt. Ha pedig 100-szor dobunk fejet egymás után, akkor is ugyanannyi a valószínűsége, hogy fejet kapunk 101.-re, mint annak, hogy írást, az előzőekhez hasonlóan-a múlt tehát nem jelzi előre a jövőbeli eredményt. A jelen állapot az, hogy van egy érménk (nem cinkelt), fejjel és írással a két oldalán. Szabályos kereteket feltételezve semmi más nem befolyásolhatja a jövőbeni dobás alakulását.

Minden egyes pillanatban a rendszer az adott valószínűségi változó eloszlása alapján vagy megváltoztatja az állapotát a jelenbeli állapotától, vagy ugyanúgy marad. Az állapotváltozásokat átmenetnek nevezzük, és azokat a valószínűségeket, melyek a különböző állapotváltozásokra vonatkoznak, átmenet-valószínűségeknek nevezzük. Ez a fogalom megtalálható a véletlen analízisben is.

Formális definíció

szerkesztés

A nem független valószínűségi változók egy jelentős osztálya a Markov-láncok. Egy X1, X2, X3, … valószínűségi változó sorozatot Markov-láncnak nevezzük, ha az alábbi feltétel teljesül rá minden n természetes számra és minden x, x1, x2,…, xn valós számrendszerre 1 valószínűséggel:

 

Ezt a feltételt szokás Markov-tulajdonságnak is nevezni. Jelen esetben az Xi lehetséges értékei egy megszámlálható S halmazból valóak. Ezt az S halmazt állapothalmaznak nevezzük. A Markov-láncokat ábrázolhatjuk irányított gráfokkal is, ahol a csúcsok az egyes állapotok, a két csúcsot összekötő élre írt érték (felfogható súlyokként is) pedig az egyik állapotból a másikba kerülés valószínűsége (iránynak megfelelően).

Stacionárius átmenetvalószínűségű (homogén) Markov-láncról beszélünk, ha az átmenet-valószínűségek nem függnek az időtől, azaz:

 

n-től függetlenül.

m-edrendű Markov-láncok az olyan Markov-láncok, melyekre (véges m esetén):

 
 

minden n-re, vagyis a rendszer csak m időszakra emlékszik vissza, a korábbiak állapotok nem befolyásolják a jövőt.

m=1 esetén egyszerű Markov-láncnak nevezzük.

  • Legyen egy dolog két állapota A és E, azaz az S állapothalmaz kételemű, S = {A, E}.
 
  • Ha a dolog egy t időpontban A állapotban van, akkor annak a valószínűsége, hogy (t+1)-ben E állapotba kerül, legyen 0,4. Annak a valószínűsége, hogy továbbra is A-ban marad, 0,6 lesz (mivel a két feltételes valószínűség összege szükségszerűen 1 kell legyen).
  • Ha a dolog ugyanebben a t időpontban E állapotban van, akkor annak a valószínűsége, hogy (t+1)-ben A állapotba kerül, legyen 0,7. Annak a valószínűsége, hogy továbbra is E-ben marad, 0,3 lesz.

Ezt ábrázolja a bal oldali irányított gráf, ahol A és E állapotokat egy-egy kör szemlélteti, az egyes körökből kimenő nyilak mellé írt számok pedig az átmenet-valószínűségek.

Gyakran csak az állapotváltozások nyilait rajzolják fel az ilyen ábrákon, mivel annak az valószínűsége, hogy egy állapot változatlan marad, kiszámolható úgy, hogy 1-ből levonjuk az állapotot szemléltető körből kimenő nyilak fölé írt valószínűségek összegét.

Ez egy stacionárius, egyszerű (elsőrendű) Markov-lánc.
  • Valamely véges állapotú gép jól reprezentálhatja a Markov-láncokat. Feltételezzük, hogy a masinánk lehetséges inputjai egymástól függetlenek és egyenletes eloszlásúak. Ekkor, ha a gépezet egy tetszőleges y állapotban van az n-edik időpillanatban, akkor annak valószínűsége, hogy az n + 1-edik pillanatban az x állapotban lesz, csak a jelenlegi állapottól függ.

Markov-láncok tulajdonságai

szerkesztés

Először szükséges bevezetnünk az egy-lépéses átmenet-valószínűség:

 

és az n-lépéses átmenet-valószínűség fogalmát:

 

Előbbi az i állapotból egy lépéssel a j állapotba kerülés, utóbbi az n. lépés után a j állapot valószínűségét fejezi ki, feltéve, hogy  .

Az n-lépéses átmenet-valószínűségekre teljesül a Chapman–Kolmogorov-egyenlőség, amely 0 < k< n esetén minden k-ra az alábbi:

 

Egy Markov-lánc kezdeti eloszlása egy (sor)vektor, mely az alábbi módon értelmezett

 

Míg az abszolút eloszlása az n-edik időpillanatban

 

ahol

  j=1, 2, ..., s. s féle állapot van.

Azonban egy Markov-lánc lehet az időtől független, ilyenkor   eloszlása, azaz   nem függ n-től, azaz   minden n-re. Ekkor szokás az eloszlást egyszerűen  -vel jelölni.

Reducibilitás

szerkesztés

Egy tetszőleges i, j állapotpárról azt mondjuk, hogy i-ből elérhető a j állapot (jelölése: ij), ha feltéve, hogy az i állapotban vagyunk, annak a valószínűsége, hogy valamikor a jövőben a j-be kerülünk, nem nulla. Formálisan, j elérhető i-ből, ha létezik olyan n>0, melyre

 

Egy i állapot egy j állapottal kapcsolatos (más néven közlekedik) (jelölve: ij), ha i-ből j és j-ből i is egyaránt elérhető. Egy C halmaz kapcsolatos osztályt alkot, ha benne minden elempár kapcsolatos egymással, és nem létezik olyan C-n kívüli állapot, amely valamely C-beli állapottal kapcsolatos lenne. (Azt is mondhatjuk, hogy a kapcsolatosság ekvivalenciareláció, tehát osztályokra bontja az állapotteret). Egy ilyen osztályt zártnak hívunk, ha az osztály elhagyásának valószínűsége nulla, azaz ha i C-beli, de j nem, akkor j nem elérhető i-ből. Végezetül, egy Markov-láncot irreducibilisnek nevezünk, ha állapotainak halmaza egy kapcsolatos osztályt alkot: vagy mind tranziensek, vagy rekurrens zérus állapotok, vagy rekurrens nem zérus állapotok. Mindegyik esetben az összes állapot periódusa megegyezik. Egy véges sok állapotú láncnak nem lehet zérus állapota, és nem lehet az összes állapota tranziens. Egy irreducibilis Markov-láncban bármely állapotból bármely állapotba eljuthatunk valahány (véges) lépésben.

Periodicitás

szerkesztés

Tetszőleges i állapot periódusa k, ha ahhoz, hogy i állapotból i állapotba visszatérjünk, k-nak valamely többszörös darabszámú lépésre van szükség. Például, ha egy i állapotba való visszatérés csak páros darab lépésben történhet meg, akkor i periódusa 2 lesz. Egy i állapot periódusának formális definíciója:

 

(ahol „lnko” a legnagyobb közös osztó). Meg kell jegyezni, hogy attól függetlenül, hogy egy állapot periódusa k, nem jelenti azt, hogy belőle kiindulva k lépésben újra el tudjuk érni azt. Például, ha egy állapotba vissza tudunk térni {6,8,10,12,…} lépésben, akkor annak periódusa 2 lesz, annak ellenére, hogy a 2-es szám nincs a listában. Ha k = 1, akkor az állapotot aperiodikusnak nevezzük. Egyébként (ha k>1) az állapotot k-periodikusnak mondjuk.

Bebizonyítható az is, hogy egy kapcsolatos osztályban minden állapot periódusa ugyanaz, azaz a periódus osztálytulajdonság.

Egy véges állapotú irreducibilis Markov-láncot ergodikusnak nevezünk, ha minden állapota aperiodikus.

Rekurrencia

szerkesztés

Egy tetszőleges i állapot tranziens , átmeneti, ha (feltéve, hogy i állapotból indulunk) annak a valószínűsége, hogy soha nem térünk vissza i-be nem nulla, azaz annak valószínűsége, a rendszer valamikor visszatér az i állapotba, nem egy. Legyen Ti valószínűségi változó az az első a lépésszám, ami után először visszatérünk i-be:

 

Ekkor i állapot tranziens, ha:

 

Egy i állapot lényeges: ha i → j esetén j → i is teljesül. A lényegesség osztálytulajdonság, azaz beszélhetünk lényeges és lényegtelen osztályokról, egy osztálynak vagy minden eleme lényeges, vagy egy sem. A lényeges osztályokból nem lehet kijutni (mert akkor vissza is tudnánk jönni, azaz osztályon belül maradnánk), a lényegtelenekből viszont kijuthatunk és ekkor többé már nem térhetünk vissza. A nem lényeges állapotok tranziensek (fordítva azonban nem igaz).

Legyen Mi a visszatérésig megtett lépésszám várható értéke (átlagos visszatérési idő)

 

Ekkor ha Mi véges, az i állapotot pozitívnak, egyébként nullállapotnak nevezzük. Meg lehet mutatni azt is, hogy egy állapot akkor és csak akkor lényeges, ha:

 

Egy i állapotot nyelőnek nevezünk, ha lehetetlen belőle kikerülni, azaz, ha

  , azaz   minden  -re.

Ergodicitás

szerkesztés

Egy i állapotra azt mondjuk, hogy ergodikus, ha aperiodikus és pozitív. Ha pedig egy Markov-láncban minden állapot ergodikus, akkor magát a láncot is ergodikusnak nevezzük.

Szilárd-állapot analízis és határeloszlások

szerkesztés

Ha egy Markov-lánc homogén, azaz a folyamat egy időfüggetlen pij mátrixszal leírható, ekkor a π vektor a stacionárius eloszlás, ha   -re teljesül, hogy:

 

 

 

Egy irreducibilis láncnak akkor és csakis akkor van stacionárius eloszlása, ha az összes állapota pozitív. Ebben az esetben π egyértelmű, és kifejezhető a kapcsolata a várt visszatérési idővel:

 

Továbbá, ha egy lánc irreducibilis és aperiodikus is, akkor bármely i és j állapotra,

 

Meg kell jegyeznünk, hogy ez nem szab feltételeket a kezdeti eloszlásra nézve, a lánc konvergál a stacionárius eloszláshoz függetlenül attól, hol kezdődött.

Ha egy Markov-lánc nem irreducibilis, akkor stacionárius eloszlása nem lesz egyértelmű (beleértve minden zárt kapcsolatos osztályt, ami a láncban van, mindegyiknek külön-külön saját stacionárius eloszlása lesz. Ezek közül egyik sem lesz kiterjeszthető az egész láncra). Azonban, ha egy j állapot aperiodikus, akkor

 

és az összes többi i állapotra legyen fij annak a valószínűsége, hogy eljutunk j-be valahány lépésben, ha i-ből indultunk,

 

Véges állapotú Markov-láncok

szerkesztés

Ha az állapothalmaz véges, az átmenet-valószínűségek mátrixba rendezhetőek, ezt átmenetmátrixnak (jele: P) nevezzük. Ezen mátrix i-edik sorának j-edik elemét pij-vel jelöljük, és az alábbi módon kaphatjuk meg:

 

A P egy sztochasztikus mátrix, azaz minden eleme nemnegatív, és minden sorban az elemek összege 1 (ez a valószínűség tulajdonságaiból következik). Továbbiakban, ha egy Markov-lánc homogén, azaz átmenet mátrixának, P-nek elemei nem függnek az időtől (azaz n-től), ekkor a k-lépéses átmenet-valószínűség mátrixa megkapható az átmenet mátrix k-adik hatványként, azaz Pk alakban (ez a Chapman–Kolmogorov-tétel következménye).

A stacionárius eloszlás π, egy (sor)vektor, amelyre teljesül az alábbi egyenlet:

 

Más szóval a π stacionárius eloszlás az átmenetmátrix az 1 sajátértékéhez tartozó bal oldali (lenormált) sajátvektora.

A stacionárius eloszlás mindig létezik, de az nem garantált, hogy egyértelmű is lesz. Azonban ha egy Markov-lánc irreducibilis, aperiodikus és véges állapotterű, akkor létezik egy és csakis egy stacionárius eloszlás, π. Ráadásul Pk konvergál egy egy-rangú mátrixhoz, melynek minden sora a stacionárius eloszlás π, azaz

 

ahol 1 egy oszlopvektor, aminek minden eleme 1. Ez itt nem más, mint a Perron–Frobenius-tétel. Az állítás tehát nem jelent mást, hogy ahogy telik az idő, a Markov-lánc elfelejti, honnan indult (azaz a kezdeti eloszlását), és konvergál a stacionárius eloszláshoz.

 
Vegyük ismét csak a fenti példabeli Markov-láncot, és írjuk fel a   átmenetmátrixot:

 

Jelöljük  -vel a dolog t-beli állapotának valószínűségeit:

 

ahol   annak a valószínűsége, hogy a dolog t-ben E állapotban van, és   annak a valószínűsége, hogy a dolog t-ben A állapotban van. (Természetesen   minden t-re.)

Ha t=0-ban az   valószínűségi vektor jellemzi a dolog lehetséges állapotát, akkor t=1-ben  , ahol

 .

Hasonlóan t=k-ban

 

Hasonlóan tovább számolva azt kapjuk, hogy

 

Tegyük fel, hogy t=0-ban a dolog az E állapotban volt, azaz   Ha most arra vagyunk kíváncsiak, hogy három időegység múlva milyen valószínűséggel lesz a dolog az E állapotban, akkor k=3 mellett ki kell számolnunk  -at, és   első komponense adja meg a keresett valószínűséget:

 

vagyis 0,363 valószínűséggel lesz a dolog 3 időszak múlva az E állapotban.

Megfordítható Markov-láncok

szerkesztés

A Markov-láncok megfordításáról szóló ötlet, a Bayes-tétel alkalmazásával történő feltételes valószínűség „invertálás” képességéből származtatható:

 
 

Ez most úgy képzelhetjük el, mintha az idő megfordult volna. Ekképpen egy Markov-láncról azt mondjuk, hogy megfordítható, ha létezik egy olyan π, melyre

 

Ezt a feltételt szokás leíró egyensúly feltételnek is nevezni.

Ezeket összegezve  -re

 

egyenletet kapjuk a megfordítható Markov-láncokra. A π mindig stacionárius eloszlást jelöli.

Bernoulli-modell

szerkesztés

A Bernoulli-féle modell egy olyan speciális esete a Markov-láncoknak, ahol az átmenet mátrix sorai egységek. Ez azt jelenti, hogy a következő állapot még az eredeti, jelenbeli állapottól is teljesen független (természetesen azon túl, hogy a múltbeliektől független). A két-állapotú Bernoulli-modellt szokás Bernoulli-folyamatnak is nevezni.

Markov-láncok általános állapothalmazzal

szerkesztés

Sok eredmény, ami a véges állapotú Markov-láncokra vonatkozik, általánosítható olyan láncokra, melyek állapothalmaza megszámlálhatatlan méretű, a Harris-láncok segítségével. Az alapötlet az, hogy megnézzük, van-e olyan pont az állapothalmazban, amit a lánc 1 valószínűséggel elér. Általánosságban ez persze nem igaz a végtelen számosságú állapothalmazokra, azonban definiálhatunk egy A és egy B halmazt együtt ε számmal, és egy ρ valószínűségi mértékkel, melyekre

  1. Ha  , akkor   minden  -re.
  2. Ha   és  , akkor  .

Ekkor összehúzhatjuk a két halmazt egy kiegészítő ponttá, legyen ez α. Ekkor a rekurrens Harris-lánc úgy alakítható, hogy tartalmazza α-t is. A Harris-láncok gyűjteménye már egy kényelmes foka az általánosságnak. Elég tág, ahhoz, hogy számtalan izgalmas példát magába foglaljon, de eléggé korlátozott ahhoz, hogy számos jelentős tétel legyen megfogalmazható rájuk.

Alkalmazások

szerkesztés

A Markovi rendszerek jelentős részei a fizikának, különösképp a statisztikus mechanikának. Minden egyes alkalommal, amikor a valószínűséget használjuk egy rendszer ismeretlen, vagy modellezetlen részletének jellemzésére, és feltehető, hogy a mozgások időre nézve invariánsak, illetve nincs szükség a múltbéli események ismerésére a jövőbeli állapot meghatározására, Markov-láncokról beszélünk.

Statisztikai folyamatok

szerkesztés

A Markov-láncokat használhatjuk a statisztika egyes folyamatainak modellezésére is. Claude Shannon egyik híres 1948-as lapja „A kommunikáció matematikai elmélete”, mely egy csapás alatt megteremtette az információelmélet mezejét, kezdődik rögtön azzal, hogy az angol nyelv Markov modellezésének segítségével bemutatja az entrópia fogalmát. Az ilyen idealizált modellek segíthetnek a rendszerek statisztikai szabályszerűségeit megragadni. Annak ellenére, hogy nem tudjuk teljes pontossággal leírni a rendszer struktúráját, az ilyen modellek kellően hatékony adattömörítést biztosíthatnak egyes entrópikus kódolási technikákkal, például az aritmetikai kódolással. Hatékonyak lehetnek az állapot értékelés, és a minta felismerésben is. A világ mobil telefon rendszereinek hibaelhárítása a Viberth-algoritmustól függ, míg rejtett Markov modellek állnak a beszédfelismerés és a bioinformatika (például, a gének előrejelzésében) illetve a tanulás egyes folyamatainak hátterében is.

A Markov-láncok metódusai fontos szerepet játszanak abban is, hogy véletlen számok sorozatait generáljunk ahhoz, hogy kellően precízen tükrözni tudjunk bonyolult valószínűség-eloszlásokat, mint például egy folyamatot, a Markov lánc Monte Carlót (MCMC). Az utóbbi években ez forradalmasította a Bayes-i következtetés egyes metódusait is.

Internetes alkalmazások

szerkesztés

Egy honlap PageRank mutatója, amelyet a Google is használ, is Markov-lánc által definiált. Annak a valószínűsége, hogy egy tetszőleges   honlapon legyünk a stacionárius eloszlás alapján, a következő Markov-lánc minden (ismert) weboldalra. Legyen   az ismert honlapok száma, és ha az  -edik lap   linkkel rendelkezik, akkor annak az átmenet-valószínűsége, hogy be van linkelve egy másik laphoz  , és   ha nincs egy másik lap linkjei között. A használt   paraméter megközelítőleg 0,15-dal egyenlő.

Markov-láncokat használnak arra is, hogy analizálják a felhasználók navigációs viselkedését a weben. Egy internetező "linkátmenetét" egy adott honlapon modellezhetjük első-, vagy másodrendű Markov-modellek segítségével, és arra is felhasználhatjuk, hogy ezzel előre jelezzük a későbbi navigációkat, és ez által készíthessünk alkalmas weblapot minden egyes felhasználó részére külön-külön.

A dinamikus makroökonómiának is nélkülözhetetlen része a Markov-lánc.

Matematikai biológia

szerkesztés

A Markov-láncok újabb felhasználási területe a biológiai modellezés. Kiváltképp a népesedési folyamatoké, amely hasznos olyan folyamatok modellezésében, amelyek analógok a biológiai népességgel. A Leslie-mátrix is egy alkalmas példa erre, annak ellenére, hogy egyes értékei nem valószínűségek (lehetnek 1-nél is nagyobbak). Másik fontos példa a sejtek osztódása közbeni alakok modellezése. Az alakok eloszlása, hosszú ideig rejtély volt, mind addig, míg azt meg nem határozták egy egyszerű Markov-modell segítségével. Ebben a modellben egy sejt állapota, annak oldalainak számát jelenti. A békákon, legyeken és hidrákon tapasztalati úton szerzett információk azt sugallják, hogy a sejt alakjának stacionárius eloszlása bizonyíthatóan minden többsejtű állatra ugyanaz.[1]

A tanulás folyamatának statisztikai elmélete

szerkesztés

Memóriánk működésére is létezik statisztikailag helyes megközelítés. Az emberi agy működése a tanulási folyamatok során is Markov-láncokkal magyarázható. Képzeljünk el egy tanulót, akinek átnyújtunk egy lista szót. Ő azokat átolvassa, majd leírja azokat, amiket megjegyzett. Ezután ismét átolvassa, a memorizáltakat leírja, és a kísérletsorozat így folytatódik. Valamelyik szót vizsgálatunk tárgyává választva, azt mondjuk, hogy a szó n-edik kísérletnél a k állapotban van, ha az n kísérletből k esetben emlékezett a szóra a kísérleti alany. Ezen P(k,n) valószínűségek meghatározására is Markov-láncok elméletére van szükség.

Játék, szerencsejáték

szerkesztés

Markov-láncokat használunk egyes szerencsejátékok és társasjátékok modellezésére is. Egy ismert gyerekjáték, a „Kígyók és létrák” is egy Markov-láncként fogható fel. Minden egyes körnél a játékos egy meghatározott mezőn áll (adott állapotban van) és megvannak a rögzített valószínűségi értékek a következő, lehetséges mezőre (állapotba) jutáshoz.

Markov-láncokat alkalmaznak az úgynevezett algoritmikus zenei összeállítások készítésére, olyan szoftverek esetén, mint a CSound vagy a Max. Egy elsőrendű láncban a rendszer állapotai hangjeggyé vagy hangmagassági értékké válnak, és így a minden egyes hanghoz tartozó valószínűségi vektorokból egy átmenetmátrix konstruálható. Egy jól megalkotott algoritmus pedig ezeket a hangjegyeket létrehozza, és kirakja az outputra az átmenetmátrix „súlyai” alapján, legyen az MIDI hangjegy érték, vagy frekvencia (Hz), vagy egyéb kívánatos mérték.

első-rendű mátrix
Note A C# Eb
A 0.1 0.6 0.3
C# 0.25 0.05 0.7
Eb 0.7 0.3 0
másodrendű mátrix
Note A D G
AA 0.18 0.6 0.22
AD 0.5 0.5 0
AG 0.15 0.75 0.1
DD 0 0 1
DA 0.25 0 0.75
DG 0.9 0.1 0
GG 0.4 0.4 0.2
GA 0.5 0.25 0.25
GD 1 0 0


A másodrendű Markov-lánc, figyelembe véve az aktuális és az előző állapotot egyaránt, a második ábrán látható módon írható le.

1960 óta használnak Markov-láncokat, modelleket a magasabb fokú baseball analízisben. Bár az igaz, hogy használata még mindig ritka. Minden egyes helycsere egy baseball meccsen megfelel a Markov-lánc egy állapotának, beleértve a futások és out-ok számát. 24-féle futás-out kombináció tartozik az egyes helycserékhez. Markov-modelleket használhatunk ahhoz, hogy megbecsüljük a futásokat az összes játékosra nézve külön-külön, vagy a csapatra összességében.

Markov paródiagenerátor

szerkesztés

Markov folyamatokat arra is használhatjuk, hogy egy minta dokumentum alapján látszólag értelmesnek tűnő szövegeket generáljunk. Ezeket különböző szórakoztatási célú szoftvereknél, úgynevezett "paródia generátoroknál" használják (lásd dissociated press, Jeff Harrison, Mark V Shaney, [5] [6]).[1][2]).

Történet

szerkesztés

Andrej Markov az első eredményeket (1906) ezen folyamatok tekintetében kizárólag elméleti szinten fektette le. A megszámlálhatóan végtelen állapothalmazra való általánosítással Kolmogorov (1936) állt elő. A Markov-láncok szoros kapcsolatban állnak a Brown-mozgással és az ergodikus hipotézissel, mely két fizikai téma meghatározó részét képezték a 20. század korai éveinek, de Markov ennek ellenére úgy tűnik, ezt inkább kiemelte a matematikai motivációból, nevezetesen azzal, hogy kiterjesztette a független eseményekre vonatkozó nagy számok törvényét. A felfedezéseit először 1913-ban használta fel.


Bibliográfia

szerkesztés
  1. (1984. november 1.) „A Travesty Generator for Micros”. BYTE 9 (12), 129-131, 449-469. o. 
  2. Hartman, Charles. The Virtual Muse: Experiments in Computer Poetry. Wesleyan University Press (1996). ISBN 0819522392 
  • 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.
  • 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.)
  • Booth, Taylor L.. Sequential Machines and Automata Theory, 1st, New York: John Wiley and Sons, Inc.. Library of Congress Card Catalog Number 67-25924 (1967)  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. 449ff. Discusses Z-transforms, D transforms in their context.
  • Kemeny, John G., Hazleton Mirkil, J. Laurie Snell, Gerald L. Thompson. Finite Mathematical Structures, 1st, Englewood Cliffs, N.J.: Prentice Hall, Inc.. Library of Congress Card Catalog Number 59-12841 (1959)  Classical text. cf Chapter 6 Finite Markov Chains pp. 384ff.
  • Levelek a valószínűségről, Typotex, Budapest, 1994 (MEK)
  • Rényi Alfréd, Valószínűségszámítás, Tankönyvkiadó, Budapest, 1968

Hivatkozások

szerkesztés