Úkolem studenta/tky je nastudovat, popsat a ilustrovat na příkladech metody odhadu rychlosti mixingu diskrétních Markovských řetězců pomocí silně stacionárních časů. 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 používající silně stacionární časy.
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 strongly stationary times.
- zadáno a potvrzeno stud. odd.