Ú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.
Seznam odborné literatury
D A Levin, Y Peres, E L Wilmer (2009): 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). 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ů.
Předběžná náplň práce v anglickém jazyce
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.
- zadáno a potvrzeno stud. odd.