Náhodné procházky na sítích, časy dosažení a časy pokrytí
| Thesis title in Czech: | Náhodné procházky na sítích, časy dosažení a časy pokrytí |
|---|---|
| Thesis title in English: | Random walks on networks, hitting times and cover times |
| Key words: | náhodná procházka na grafu|čas dosažení|čas pokrytí |
| English key words: | random walk on network|hitting time|cover time |
| Academic year of topic announcement: | 2019/2020 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Department of Probability and Mathematical Statistics (32-KPMS) |
| Supervisor: | RNDr. Michaela Prokešová, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 23.11.2019 |
| Date of assignment: | 25.11.2019 |
| Confirmed by Study dept. on: | 11.12.2019 |
| Date and time of defence: | 02.09.2021 08:00 |
| Date of electronic submission: | 22.07.2021 |
| Date of submission of printed version: | 22.07.2021 |
| Date of proceeded defence: | 02.09.2021 |
| Opponents: | doc. RNDr. Jan Večeř, Ph.D. |
| Guidelines |
| 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. |
| References |
| Levin, D.A., Peres, Y., Wilmer, E.L. (2009). Markov Chains and Mixing Times, AMS, Providence, Rhode Island. |