Původ Markovovských řetězců

Když se podíváte na přírodu, mnoho z nás si všimne krásné dichotomie. Žádné dvě věci nejsou úplně stejné, ale všechny zřejmě mají podobnou formu. Platón věřil, že pravé formy vesmíru jsou nám skryty. Pozorováním přírody můžeme získat pouze přibližnou znalost těchto forem. Jsou skryty ve schématech. Čisté formy jsou dosažitelné jednině pomocí abstraktního uvažování filozofie a matematiky. Například kruh. Je popsán tak, že vzdálenost od středu k okraji je všude stejná. Zatím jsme však nikde nenašli vyrobený dokonalý kruh, či dokonalou úsečku. Přesto Platona napadlo, že po nespočetně mnoha letech vesmír dosáhne ideálního stavu, navrácením se ke své dokonalé formě. Platonské zaměření se na abstrakní čistou formu zůstávalo populární po celá staletí. A až do 16. stolení nebylo překonáno když se lidé snažili uchopit různorodost reálného světa a použít matematiku k popisu skrytých vzorů. Bernoulli upravil myšlenku očekávání. Zajímal se o způsob, jak přesně odhadnout neznámou pravděpodobnost nějaké události na základě toho jak často danná událost nastane při nezávislých pokusech. A použil jednoduchý příklad. Předpokládejte, že je skryto v urně 3000 světlých a 2000 tmavých kamenů bez vašeho vědomí. A potom provedeme experiment, abychom určili poměr mezi nimi. Taháte jeden kámen za druhým, opět je vracíte, a přitom si zaznamenáváte, jak často který vytáhnete. Bernoulli takto dokázal, že střední hodnota našeho pozorování se vzrůstajícím počtem pokusů konverguje ke skutečnému poměru. Říkáme tomu Zákon velkých čísel. Z toho vyvodil: "Pokud pozorování všech událostí bude pokračovat do nekonečna bude spozorováno, že vše na světě je řízeno přesnými poměry a konstantním Zákonem změny." Tato myšlenka byal rychle rozšířena o pozorování, že ne všechny věci konvergují ke střední hodnotě, ale pravděpodobnost odchyky od průměrů také sleduje známý tvar distribuce. Skvělým příkladem toho je fazolový stroj Francise Galtona. Představme si, že každou kolizi jako nezávislou událost podobnou hodu mincí. Po deseti kolizích, fazole spadne do kbelíku představujícího poměr mezi levými a pravými vychýleními nebo také pany či orla. A tato křivka je známá jako binomické rozdělení. Zdá se být ideální formou, neboť se objevuje všude. Vždy když se podíváte na rozptyl mnoha náhodných pokusů. Zdá se, že průměrný osud těchto událostí je nějak předem určený. Dnes se tomu říká Centrální limitní věta. Ale pro někho to byla nebezpečná filozofická myšlenka. Pavel Nekrasov původem teolog, který se později začal věnovat matematice a byl velkým podporovatelem náboženské doktríny svobodné vůle. Neměl rád myšlenku, že bychom měli statistikou předurčený osud. A tak vytvořil slavné tvrzení: "Nezávislost je nezbytnou podmínkou pro Zákon velkých čísel." A jelikož nezávislost máme pouze pro tyto příklady her s fazolemi či kostkami, kde výsledek předcházejících událostí nemění pravděpodobnost současné či budoucí události, tak se můžeme spolehnout, že většina věcí v reálném světě je jistě závislá na předchozích výsledcích. Například možnost požáru, sluníčka, či dokonce střední délka života. A když pravděpodobnost nějaké události je závislá na předchozí události, říkáme, že události jsou závislé. Ale toto tvrzení rozčílilo jiného ruského matematika. Andreje Markova, který byl veřejným nepřítelem Nekrasova. A tak napsal dopis: "Tyto okolnosti mě donutili vysvětlit v sérii článků, že Zákon velkých čísel může být aplikován i na závislé proměnné." Použil konstrukci, o které se Nekrasovi ani nesnilo. A tak Markov rozšířil Bernoulliho výsledek na závislé proměné použitím geniální konstrukce. Představte si hod mincí, který je nezávislý, ale je závislý na předchozím výsledku. Takže má krátkodobou paměť na poslední událost. To lze zobrazit pomocí hypotetického stroje, který obsahuje dva hrníčky, kterým říkáme stavy. V jednom stavu máme 50 černých a 50 bílých korálků, zatímco v druhém stavu máme více černých než bílých. Jeden hrníček tedy bude stav 0. Ten reprezentuje, že jsme vytáhli černý korálek. Ten duhý označme stav 1 a znamená to, že jsme předtím vytáhli bílý korálek. Nyní pusťme náš přístroj. Začneme v libovolném stavu a vytáhneme korálek. A poté se rozhodneme pokračovat ve stavu 0, či 1, podle toho jakou barvu jsme vytáhli. A v závislosti na tom vypíšeme 0, pokud jsme vytáhli černou nebo jedničkou pokud byla bílá. Můžeme najít 4 možné přechody. Byli jsme ve stavu 0 a vytáhli jsme černou, tak se vrátíme zpátky do stejného stavu a vybíráme z něj znovu. Pokud jsme vytáhli bílou, tak přeskočíme do stavu 1, který může také cyklit nebo se vrátit zpět do stavu 0, pokud byla vybrána černá. Pravděpodobnost vytažení bílé vs. černé není určitě nezávislá, protože závisý na předchozím výsledku. Markov dokázal, že pokud jsou všechny stavy stroje dostupné, pokud pustíte stroj v sekvenci, tak dosáhne ekvilibria. A to nezávisle na tom, kde jste začali. Od té doby počet navštívení jednotlivých stavů, konverguje k nějakému danému poměru, pravděpodobnosti. Tento jednoduchý příklad vyvrátil Nekrasovo tvrzení, že pouze nezávislé události mohou konvergovat k předpověditelné distribuci. Ale koncept modelování náhodných sekvencí s použítím stavů a přechodů mezi stavy se stal známý jako Markovův řetězec. A jedna z prvních a nejznámějších aplikací Markovových řetězců byla publikována Claudem Shannonem.