Úkolem studenta/tky je nastudovat, popsat a ilustrovat na příkladech, jak lze v případě, že máme markovský řetězec, jehož množinu stavů lze ztotožnit s vrcholy nějakého grafu, využít metriku na hranách tohoto grafu ke konstrukci couplingu, který nám umožní přesně omezit rychost konvergence takového řetězce k jeho stacionárnímu rozdělení.
Práce je kompilační, vlastní příspěvek studenta bude spočívat v přehledném zpracování a vysvětlení studovaných metod (v češtině nebo slovenštině), doplnění podrobností v některých důkazech a vypracování vybraných cvičení z knihy Markov Chains and Mixing Times.
Seznam odborné literatury
D A Levin, Y Peres (2017): Markov Chains and Mixing Times, AMS, Providence
Předběžná náplň práce
Jednou za základních vlastností markovských řetězců, velmi důležitou zvláště v moderních algoritmických aplikacích markovských řetězců s diskrétním časem a konečným stavovým prostorem, je rychlost konvergence marginálního rozdělení řetězce k jeho stacionárnímu rozdělení (neboli rychlost mixingu). A coupling pravděpodobnostních rozdělení je metoda, která ke zjištění (odhadu) vzdálenosti mezi dvěma pravděpodobnostními rozděleními používá konstrukci dvourozměrného náhodného elementu, který má daná pravděpodobnostní rozdělení jako marginální. Když zkonstruujeme coupling dvou markovských řetězců se stejnou maticí pravděpodobností přechodu, které startují jeden ze stacionárního rozdělení a druhý z pevného stavu, můžeme ho využít k odhadu rychlosti mixingu. Otázka je, jak vhodný coupling zkonstruovat. Metoda využívající transportní metriky je jednou z možností a má hodně aplikací například v oblasti přibližného počítání prvků velkých kombinatorických množin (např. všechna přípustná q-obarvení velkého grafu, počet hard-core konfigurací na velkém grafu), které využívá znáhodněné algoritmy (neboli simulované, vhodně zvolené markovské řetězce).
- zadáno a potvrzeno stud. odd.