Vysvětleno vizuálně
Victor Powell
s textem Lewise Leheho
Markovovy řetězce, pojmenované po Andreji Markovovi, jsou matematické systémy, které přecházejí z jednoho „stavu“ (situace nebo souboru hodnot) do druhého. Pokud byste například vytvořili Markovův řetězový model chování dítěte, mohli byste jako stavy zahrnout „hraní“, „jídlo“, „spánek“ a „pláč“, které by spolu s dalšími chováními mohly tvořit „stavový prostor“: seznam všech možných stavů. Nad stavovým prostorem navíc Markovův řetězec udává pravděpodobnost přeskoku neboli „přechodu“ z jednoho stavu do jakéhokoli jiného stavu – např, pravděpodobnost, že dítě, které si právě hraje, v příštích pěti minutách usne, aniž by předtím plakalo.
Jednoduchý dvoustavový Markovův řetězec je znázorněn níže.
rychlost
Při dvou stavech (A a B) v našem stavovém prostoru existují 4 možné přechody (ne 2, protože stav může přejít zpět sám do sebe). Pokud jsme ve stavu ‚A‘, můžeme přejít do stavu ‚B‘ nebo zůstat ve stavu ‚A‘. Pokud jsme ve stavu „B“, můžeme přejít do stavu „A“ nebo zůstat ve stavu „B“. V tomto dvoustavovém diagramu je pravděpodobnost přechodu z libovolného stavu do libovolného jiného stavu 0,5.
Skuteční modeláři samozřejmě ne vždy kreslí diagramy Markovových řetězců. Místo toho používají „matici přechodů“, aby sečetli pravděpodobnosti přechodů. Každý stav ve stavovém prostoru je zahrnut jednou jako řádek a podruhé jako sloupec a každá buňka matice udává pravděpodobnost přechodu ze stavu svého řádku do stavu svého sloupce. V matici tedy buňky plní stejnou úlohu jako šipky v diagramu.
A B
Pokud stavový prostor přidá jeden stav, přidáme jeden řádek a jeden sloupec a ke každému existujícímu sloupci a řádku přidáme jednu buňku. To znamená, že počet buněk roste kvadraticky, jak přidáváme stavy do našeho Markovova řetězce. Matice přechodů se tedy hodí poměrně rychle, pokud nechcete kreslit diagram Markovova řetězce jako v tělocvičně.
Jedním z využití Markovových řetězců je zahrnutí reálných jevů do počítačových simulací. Můžeme například chtít ověřit, jak často přeteče nová přehrada, což závisí na počtu deštivých dnů v řadě. Při sestavování tohoto modelu vycházíme z následujícího vzorce deštivých (R) a slunečných (S) dnů:
Jedním způsobem, jak simulovat toto počasí, by bylo prostě říci: „Polovina dnů je deštivých. Proto bude mít každý den v naší simulaci padesátiprocentní šanci na déšť.“ To znamená, že každý den bude mít padesátiprocentní šanci na déšť. Toto pravidlo by v simulaci vygenerovalo následující posloupnost:
Všimli jste si, že výše uvedená posloupnost nevypadá úplně jako původní? Druhá posloupnost jako by přeskakovala, zatímco první (skutečná data) jako by se „lepila“. Pokud je v reálných datech jeden den slunečno (S), pak je mnohem pravděpodobnější, že bude slunečno i následující den.
Tuto „lepkavost“ můžeme minout dvoustavovým Markovovým řetězcem. Když je Markovův řetězec ve stavu „R“, má pravděpodobnost 0,9, že zůstane na místě, a 0,1, že odejde do stavu „S“. Stejně tak má stav „S“ pravděpodobnost 0,9, že zůstane na místě, a pravděpodobnost 0,1, že přejde do stavu „R“.
V rukou metereologů, ekologů, informatiků, finančních inženýrů a dalších lidí, kteří potřebují modelovat velké jevy, mohou být Markovovy řetězce docela velké a výkonné. Například algoritmus, který Google používá k určování pořadí výsledků vyhledávání, zvaný PageRank, je typem Markovova řetězce.
Nahoře jsme zařadili „hřiště“ Markovových řetězců, kde si můžete vytvořit vlastní Markovovy řetězce tím, že si pohrajete s maticí přechodů. Zde je několik příkladů, ze kterých můžete vycházet: ex1, ex2, ex3 nebo si je vygenerujte náhodně. Text přechodové matice zčervená, pokud zadaná matice není platnou přechodovou maticí. Řádky matice přechodů musí mít součet 1. Také musí být stejný počet řádků jako sloupců.
Máte také přístup k celoobrazovkové verzi na adrese setosa.io/markov
.