Náhodné procházky na sítích, časy dosažení a časy pokrytí

• Název práce v češtině: Náhodné procházky na sítích, časy dosažení a časy pokrytí
• Název v anglickém jazyce: Random walks on networks, hitting times and cover times
• Klíčová slova: náhodná procházka na grafu|čas dosažení|čas pokrytí
• Klíčová slova anglicky: random walk on network|hitting time|cover time
• Akademický rok vypsání: 2019/2020
• 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í: 23.11.2019
• Datum zadání: 25.11.2019
• Datum potvrzení stud. oddělením: 11.12.2019
• Datum a čas obhajoby: 02.09.2021 08:00
• Datum odevzdání elektronické podoby: 22.07.2021
• Datum odevzdání tištěné podoby: 22.07.2021
• Datum proběhlé obhajoby: 02.09.2021
• Oponenti: doc. RNDr. Jan Večeř, Ph.D.

Zásady pro vypracování

Jedním ze základních příkladů Markovových řetězců je náhodná procházka na konečném grafu. Pokud tento graf vybavíme navíc ještě určením průchozí kapacity každé hrany - tzv. vodivostí, je možné odvodit vlastnosti náhodné procházky na něm, které dobře odpovídají fyzikálním vlastnostem elektrických sítí. Ty lze potom využít k odpovědi na zcela praktické otázky o pravděpodobnostním rozdělení časů putování mezi jednotlivými vrcholy, či jejich skupinami a potažmo také o rychlosti konvergence náhodné procházky vystartované v určitém bodě ke stacionárnímu rozdělení.
Úkolem studenta je nastudovat, popsat a ilustrovat na příkladech základní vlastnosti náhodných procházek na sítích. Speciálně se zaměří na metody odhadu časů dosažení nějaké skupiny vrcholů a času pokrytí, které následně umožňují odvodit odhady pro rychlost mixingu (konvergence ke stacionárnímu rozdělení).
Práce je kompilační, vlastní příspěvek studenta 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., Wilmer, E.L. (2009). Markov Chains and Mixing Times, AMS, Providence, Rhode Island.