Markov-lánc

A Wikipédiából, a szabad enciklopédiából

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 A_0, A_1, \dots , A_k, \dots. Az S rendszer az idő múlásával állapotait véletlenszerűen változtatja; vizsgáljuk a rendszer állapotait a t=0, 1, \dots diszkrét időpontokban, és X_n legyen egyenlő k-val, ha S az n időpontban az A_k á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 | forrásszöveg szerkesztése]

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:

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

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

Típusai[szerkesztés | forrásszöveg szerkesztése]

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:

\Pr(X_{n+1}=j \mid X_n=i) = p_{ij}\,

n-től függetlenül.

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

\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})

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

Példa[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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

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

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

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

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 Pr(X_0=i)>0.

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:

p_{ij}^{(n)} = \sum_{r \in S} p_{ir}^{(k)} p_{rj}^{(n-k)}.

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

d(0)=(\Pr(X_0=x_0), \Pr(X_0=x_1),\dots, \Pr(X_0=x_s)).

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

d(n)=(\Pr(X_n=x_0), \Pr(X_n=x_1), \dots, \Pr(X_n=x_s)).

ahol

 \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). j=1, 2, ..., s. s féle állapot van.

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

Reducibilitás[szerkesztés | forrásszöveg szerkesztése]

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

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

Az n = 0 megengedése azt jelenti, hogy úgy tekintjük, hogy minden állapot 0 lépésben önmagából elérhető.

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 | forrásszöveg szerkesztése]

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:

 k = \operatorname{lnko}\{ n: \Pr(X_n = i | X_0 = i) > 0\}

(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 | forrásszöveg szerkesztése]

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:

 T_i = \inf \{ n: X_n = i | X_0 = i\}

Ekkor i állapot tranziens, ha:

 \Pr(T_i = {\infty}) < 1.

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õ)

 M_i = E[T_i].\,

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:

\sum_{n=0}^{\infty} p_{ii}^{(n)} = \infty

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

 p_{ii} = 1 , azaz  p_{ij} = 0 minden i \not= j-re.

Ergodicitás[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 kezdeti értékeire πj sum to 1 teljesül, hogy:

\pi_j = \sum_{i \in S} \pi_i p_{ij}.

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:

\pi_j = \frac{1}{M_j}.\,

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

\lim_{n \rarr \infty} p_{ij}^{(n)} = \frac{1}{M_j}.

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

\lim_{n \rarr \infty} p_{jj}^{(n)} = \frac{1}{M_j}

é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,

\lim_{n \rarr \infty} p_{ij}^{(n)} = \frac{f_{ij}}{M_j}.

Véges állapotú Markov-láncok[szerkesztés | forrásszöveg szerkesztése]

Ha az állapothalmaz véges, az átmenet-valószínűségek mátrixba rendezhetőek, ezt átmenet mátrixnak (jel.: 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:

p_{ij} = \Pr(X_{n+1}=j\mid X_n=i). \,

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:

 \pi = \pi\mathbf{P}.\,

Más szóval a π stacionárius eloszlás az átmenet mátrix az 1 sajátértékéhez tartozó bal (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

\lim_{k\rightarrow\infty}\mathbf{P}^k=\mathbf{1}\pi

ahol 1 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.

Megfordítható Markov-láncok[szerkesztés | forrásszöveg szerkesztése]

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ó:

\Pr(X_{n}=i\mid X_{n+1}=j) = \frac{\Pr(X_n = i, X_{n+1} = j)}{\Pr(X_{n+1} = j)}
 = \frac{\Pr(X_{n} = i)\Pr(X_{n+1} = j\mid X_n=i)}{\Pr(X_{n+1} = j)}. \,

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

\pi_i p_{i,j} = \pi_j p_{j,i}.\,

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

Ezeket összegezve i-re

\sum_i \pi_i p_{i,j} = \pi_j\,

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

Bernoulli-modell[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 \tau_A = \inf\{n\geq 0: X_n \in A\}, akkor P_z(\tau_A<\infty)>0 minden z-re.
  2. Ha x \in A és C\subset B, akkor p(x, C)\geq \epsilon \rho(C).

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 | forrásszöveg szerkesztése]

Fizika[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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égi 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 | forrásszöveg szerkesztése]

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 i honlapon legyünk a stacioniárius eloszlás alapján, a következő Markov-lánc minden (ismert) weboldalra. Legyen N az ismert honlapok száma, és ha az i-edik lap k_i linkkel rendelkezik, akkor annak az átmenet-valószínűsége, hogy be van linkelve egy másik laphoz \frac{1-q}{k_i} + \frac{q}{N}, és \frac{q}{N} ha nincs egy másik lap linkjei között. A használt q 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.

Gazdaság[szerkesztés | forrásszöveg szerkesztése]

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

Matematikai biológia[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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.

Zene[szerkesztés | forrásszöveg szerkesztése]

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.

Baseball[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

  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.)
  • J.L. Doob. Stochastic Processes. New York: John Wiley and Sons, 1953. ISBN 0-471-52369-0.
  • 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 | forrásszöveg szerkesztése]