Úkolem studenta/tky je nastudovat, popsat a ilustrovat na příkladech metody odhadu rychlosti mixingu diskrétních Markovských řetězců pomocí couplingu a silně rovnomě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 Behrendsovy knihy.
Pro úspěšné vypracování práce je vhodné absolvovat předměty NSTP238 a NSTP050.
Seznam odborné literatury
E Behrends (2000): Introduction to Markov Chains with Special Emphasis on Rapid Mixing. Friedrick Vieweg & Son. Braunschweig/Wiesbaden
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 a silně rovnomě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 coupling and strong uniform times.
- zadáno a potvrzeno stud. odd.