hidden - assigned and confirmed by the Study Dept.
Date of registration:
20.10.2010
Date of assignment:
20.10.2010
Date and time of defence:
27.06.2011 00:00
Date of electronic submission:
24.05.2011
Date of submission of printed version:
26.05.2011
Date of proceeded defence:
27.06.2011
Opponents:
doc. RNDr. Jiří Dvořák, Ph.D.
Guidelines
Úkolem studenta/tky je nastudovat, popsat a ilustrovat na příkladech metody odhadu rychlosti mixingu diskrétních Markovských řetězců pomocí couplingu. 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.
Pro úspěšné vypracování práce je vhodné absolvovat předměty NSTP238 a NSTP050.
References
D A Levin, Y Peres, E L Wilmer (2009): 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). Metod používaných pro odvození mezí pro tuto rychlost je mnoho, práce se zaměří na pokročilejší metody z teorie náhodných procesů používající coupling. Tyto metody budou použity pro odhad rychlosti konvergence některých Markov Chain Monte Carlo algoritmů.
Preliminary scope of work in English
One of the essential properties of Markov chains very important particularly in the modern algorithmic applications of Markov chains with discrete time and finite statespace is the speed of convergence of their marginal distribution to the limit distribution.(in of other words the speed of mixing). There are several methods for obtaining the bounds for the mixing speed, the thesis will deal with the more advanced methods which use coupling. These methods will be applied to the estimation of the speed of convergence of several Markov Chain Monte Carlo algorithms.
- assigned and confirmed by the Study Dept.