Hlavní obsah
Informatika
Kurz: Informatika > Kapitola 2
Lekce 2: Moderní teorie informacePůvod Markovovských řetězců
Úvod do Markovovských řetězců Tvůrce: Brit Cruise.
Chceš se zapojit do diskuze?
Zatím žádné příspěvky.
Transkript
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.