Rychlost konvergence Markovových řetězců - spektrální metody

• Název práce v češtině: Rychlost konvergence Markovových řetězců - spektrální metody
• Název v anglickém jazyce: Mixing of Markov chains - spectral methods
• Klíčová slova: Markovovy řetězce|čas mixingu|spektrální metody
• Klíčová slova anglicky: Markov chains|mixing time|spectral methods
• Akademický rok vypsání: 2020/2021
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra pravděpodobnosti a matematické statistiky (32-KPMS)
• Vedoucí / školitel: RNDr. Michaela Prokešová, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 06.01.2021
• Datum zadání: 06.01.2021
• Datum potvrzení stud. oddělením: 19.01.2021
• Datum a čas obhajoby: 21.06.2022 08:00
• Datum odevzdání elektronické podoby: 12.05.2022
• Datum odevzdání tištěné podoby: 16.05.2022
• Datum proběhlé obhajoby: 21.06.2022
• Oponenti: doc. RNDr. Zbyněk Pawlas, Ph.D.

Zásady pro vypracování

Práce se bude zabývat odhadem rychlosti mixingu diskrétních Markovových řetězců, speciálně použitím spektrálních metod pro reverzibilní řetězce.
Úkolem studenta je nastudovat, popsat a ilustrovat na příkladech odvození horní meze pro čas mixingu pomocí spektrálních metod.
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.

Seznam odborné literatury

Levin, D.A., Peres, Y. (2017). Markov Chains and Mixing Times, AMS, Providence, Rhode Island.

Předběžná náplň práce

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 spektrálními metodami.