hidden - assigned and confirmed by the Study Dept.
Date of registration:
06.11.2020
Date of assignment:
13.11.2020
Confirmed by Study dept. on:
27.11.2020
Date and time of defence:
31.01.2022 08:00
Date of electronic submission:
05.01.2022
Date of submission of printed version:
10.01.2022
Date of proceeded defence:
31.01.2022
Opponents:
Dr. Jan Swart
Guidelines
Práce se bude zabývat odhadem rychlosti mixingu diskrétních Markovových řetězců, speciálně odvození dolních mezí pro čas mixingu.
Úkolem studentky/ta je nastudovat, popsat a ilustrovat na příkladech různé metody odvození dolních mezí pro čas mixingu.
Práce je kompilační, vlastní příspěvek studenta/ky bude spočívat v přehledném zpracování a vysvětlení studované problematiky (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
Levin, D.A., Peres, Y. (2017). Markov Chains and Mixing Times, AMS, Providence, Rhode Island.
Preliminary scope of work
Jednou za základních vlastností Markovových řetězců, velmi důležitou zvláště v moderních algoritmických aplikacích Markovový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). Tato rychlost se dá dobře kvantifikovat pomocí veličiny nazývané čas mixingu. Metod používaných pro odvození mezí (horních i dolních) pro čas mixingu je mnoho. Práce se bude zabývat některými metodami pro odvození dolní meze pro čas mixingu.