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 studentky/ta 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 rychlosti 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.
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í.
- zadáno a potvrzeno stud. odd.