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 rendelkezik a Markov-tulajdonsággal. 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. Rendelkezni a Markov-tulajdonsággal 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 jövőbeli helyzetét a folyamatnak. 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.

[szerkesztés] Formális definíció

A nem független valószínűségi változók egy jelentős osztálya, a Markov-láncok. Egy X₁, X₂, X₃, ... 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, x₁, x₂,..., x_n 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 X_i lehetséges értékei egy megszámlálható S halmazból valóak. Ezt az S halmazt állapot halmaznak 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).

[szerkesztés] Típusai

Homogén Markov-láncok 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}=x|X_n=y) = \Pr(X_{n}=x|X_{n-1}=y)\,$

minden n-re.

m-rendű Markov-láncok Az m-rendű Markov-láncok, olyan 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.

[szerkesztés] Példa

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 az n-edik időpillanatban, akkor az a valószínűségi érték, hogy az n + 1-edik pillanatban az x állapotba jutunk, csak a jelenlegi állapottól függ.

[szerkesztés] Markov-láncok tulajdonságai

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) \,$

Ez előbbi az i állapotból a j állapotba kerülés egy lépésen keresztüli az utóbbi az n lépésen keresztüli jutás valószínűségét fejezi ki.

Az n-lépéses átmenet-valószínűségekre teljesül a Chapman–Kolmogorov-egyenlőség, amely minden k-ra 0 < k< n esetén 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_n)).$

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

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

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.

[szerkesztés] Reducibilitás

Egy tetszőleges j állapotról azt mondjuk, hogy elérhető egy tőle különböző i állapotból (jelölve: i → j), 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 minden állapotra feltételezzük, hogy önmagából elérhető.

Egy i állapotról azt mondjuk, hogy kapcsolatos egy másik j állapottal (jelölve: i ↔ j), 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 ebben az értelemben a kapcsolatosság ekvivalencia reláció). 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 kapcsolatos osztályt alkot. Ez azt jelenti, hogy egy irreducibilis Markov-láncban bármely állapotból bármely állapotba eljuthatunk valahány (véges) lépésben.

[szerkesztés] Periodicitá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:

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

[szerkesztés] Rekurrencia

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. Például, vegyünk egy olyan T_i valószínűségi változó, amely egyenlő azzal az első időpillanattal, amikor 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}) > 0.$

Ha egy i állapot nem tranziens, akkor lényegesnek mondjuk. Bár a visszatérési idő véges, nem kell, hogy végeset várjunk. Legyen M_i az elvárt 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 csakis 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. Következésképpen i állapot akkor és csakis akkor nyelő, ha:

p i i = 1

and

p i j = 0

for $i \not= j.$

[szerkesztés] Ergodicitá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.

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

Ha egy Markov-lánc homogén, azaz a folyamat egy időfüggetlen p_ij mátrixszal leírható, ekkor a π vektor a stacionárius eloszlás, ha kezdeti étékeire π_j sum to 1 teljesül, hogy:

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

Egy irreducibilis lánc akkor és csakis akkor rendelkezik stacionárius eloszlással, 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 f_ij 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}.$

[szerkesztés] Véges állapotú Markov-láncok

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 p_ij-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 P^k 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 és aperiodikus, akkor létezik egy és csakis egy stacionárius eloszlás, π. Ráadásul P^k 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.

[szerkesztés] Megfordítható Markov-láncok

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.

[szerkesztés] Bernoulli-modell

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.

[szerkesztés] Markov-láncok általános állapothalmazzal

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

Ha $\tau_A = \inf\{n\geq 0: X_n \in A\}$ , akkor $P_z(\tau_A<\infty)>0$ minden $z$ -re.
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.

[szerkesztés] Alkalmazások

[szerkesztés] Fizika

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.

[szerkesztés] Statisztikai folyamatok

A Markov-láncokat használhatjuk a statisztika egyes folyamatainak modellezésére is. Claude Shamon 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 Carlot (MCMC). Az utóbbi években ez forradalmasította a Bayes-i következtetés egyes metódusait is.

[szerkesztés] Internetes alkalmazások

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

[szerkesztés] Gazdaság

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

[szerkesztés] Matematikai biológia

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]

[szerkesztés] A tanulás folyamatának statisztikai elmélete

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.

[szerkesztés] Játék, szerencsejáték

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.

[szerkesztés] Zene

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.

[szerkesztés] Baseball

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.

[szerkesztés] Markov paródiagenerátor

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

[szerkesztés] Történet

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

[szerkesztés] Bibliográfia

^
Kenner, Hugh & O'Rourke, Joseph (November 1984), "A Travesty Generator for Micros", BYTE 9 (12): 129-131, 449-469
^ Hartman, Charles (1996), The Virtual Muse: Experiments in Computer Poetry, Hanover, NH: Wesleyan University Press, 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.

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-13: 9780521884419. Appendix contains abridged Meyn & Tweedie. online: http://decision.csl.uiuc.edu/~meyn/pages/CTCN/CTCN.html

Booth, Taylor L. (1967). Sequential Machines and Automata Theory, 1st, New York: John Wiley and Sons, Inc.. Library of Congress Card Catalog Number 67-25924. 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 (1959). Finite Mathematical Structures, 1st, Englewood Cliffs, N.J.: Prentice-Hall, Inc.. Library of Congress Card Catalog Number 59-12841. 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

[szerkesztés] Hivatkozások

(pdf) Markov Chains chapter in American Mathematical Society's introductory probability book
Generates random parodies in the style of another body of text using a Markov chain algorithm
A generator that uses Markov Chains to create random words
Markov Chains
Class structure a PlanetMath oldalain
Chapter 5: Markov Chain Models
Generating Text (About generating random text using a Markov chain.)
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^th 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
[2]

Kategóriák: Valószínűségszámítás | Sztochasztikus folyamatok | Statisztikai modellek

See also ebooksgratis.com: no banners, no cookies, totally FREE.