Rychlost konvergence Markovových řetězců - dolní meze pro mixing

• Název práce v češtině: Rychlost konvergence Markovových řetězců - dolní meze pro mixing
• Název v anglickém jazyce: Mixing of Markov chains - lower bounds for mixing
• Klíčová slova: Markovův řetězec, rychlost konvergence, dolní mez pro čas mixingu
• Klíčová slova anglicky: Markov chain, speed of convergence, lower bound for mixing time
• 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.11.2020
• Datum zadání: 13.11.2020
• Datum potvrzení stud. oddělením: 27.11.2020
• Datum a čas obhajoby: 31.01.2022 08:00
• Datum odevzdání elektronické podoby: 05.01.2022
• Datum odevzdání tištěné podoby: 10.01.2022
• Datum proběhlé obhajoby: 31.01.2022
• Oponenti: Dr. Jan Swart

Zásady pro vypracování

Práce se bude zabývat odhadem rychlosti mixingu diskrétních Markovových řetězců, speciálně odvození dolních mezí pro čas mixingu.
Úkolem studentky/ta je nastudovat, popsat a ilustrovat na příkladech různé metody odvození dolních mezí pro čas mixingu.
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 některými metodami pro odvození dolní meze pro čas mixingu.