Název: Náhodné procházky na sítích a rychlost konvergence Markovových řetězců
Překlad názvu: Random walks on networks and mixing of Markov chains
Autoři: Gemrotová, Kateřina ; Prokešová, Michaela (vedoucí práce) ; Pawlas, Zbyněk (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2020
Jazyk: cze
Abstrakt: [cze] [eng]
Práce se zabývá odhadováním rychlosti konvergence marginálních rozdělení reverzi- bilních Markovových řetězců s diskrétním časem a konečnou diskrétní množinou stavů ke svým stacionárním rozdělením. Odhad vyjádříme pomocí několika veličin a využi- jeme teorii elektrických sítí, které nám pomohou při reprezentaci náhodných procházek na grafu. Výsledkem práce bude jednoduše zjistitelný horní odhad času mixingu pro ná- hodné procházky na souvislých grafech s libovolným počtem vrcholů a hran. Jednotlivé dílčí výsledky demonstrujeme na jednoduchých příkladech či protipříkladech. 1 The thesis presents the study of deriving upper bounds of the speed of convergence of reversible Markov chains with discrete time and discrete finite space state to their stationary distributions. We express the derived upper bound in terms of several variables and we make use of the theory of electrical networks, which will help us to represent random walks on a graph. The result of this thesis will be simply obtainable upper bound of mixing time of random walks on connected graphs with an arbitrary number of vertices and edges. Partial results will be demonstrated on simple examples and counterexamples. 1
Klíčová slova: náhodná procházka na grafu; reverzibilní Markovův řetězec; rychlost konvergence; čas mixingu; mixing time; random walk on a graph; reversible Markov chain; speed of convergence

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/121269

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-435203


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce