hidden - assigned and confirmed by the Study Dept.
Date of registration:
01.11.2022
Date of assignment:
02.11.2022
Confirmed by Study dept. on:
29.11.2022
Date and time of defence:
07.09.2023 09:00
Date of electronic submission:
19.07.2023
Date of submission of printed version:
24.07.2023
Date of proceeded defence:
07.09.2023
Opponents:
Dr. Jan Swart
Guidelines
Ú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.
References
D A Levin, Y Peres (2017): Markov Chains and Mixing Times, AMS, Providence
Preliminary scope of work
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).
- assigned and confirmed by the Study Dept.