Markovův řetězec
From Wikipedia, the free encyclopedia
Markovův řetězec popisuje obvykle diskrétní náhodný (stochastický či pravděpodobnostní) proces, pro který platí, že pravděpodobnosti přechodu do následujícího stavu závisejí pouze na současném stavu, ne na předchozích stavech. Tato tzv. Markovova vlastnost dovoluje proces znázornit stavovým diagramem, kde z každého stavu (uzlu grafu) vycházejí hrany možných přechodů do dalšího stavu s připsanou pravděpodobností.
Obrázek říká, že je-li systém ve stavu E, přejde s pravděpodobností 0,7 do stavu A, kdežto s pravděpodobností 0,3 zůstane ve stavu E. Podobně po stavu A bude s pravděpodobností 0,4 následovat stav E, kdežto s pravděpodobností 0,6 systém zůstane ve stavu A. Chování takového systému je tedy „bezpaměťové“: není potřeba si pamatovat historii, stačí pouze aktuální stav. Reprezentací takového systému tedy může být konečný automat. Markovovy řetězce dostaly jméno po matematiku Andreji Markovovi.
Příklad: Pokud je známo, s jakou pravděpodobností následují např. v angličtině po určitém znaku abecedy jiné znaky, lze automaticky generovat náhodné řetězce znaků, které sice zpravidla nedávají smysl, ale na pohled se anglickým větám velmi podobají.
Markovovy řetězce mají mnoho praktických použití, zejména v informatice, v chemii, v ekonomii i v dalších společenských vědách.