Original title: Náhodné procházky na sítích a rychlost konvergence Markovových řetězců
Translated title: Random walks on networks and mixing of Markov chains
Authors: Gemrotová, Kateřina ; Prokešová, Michaela (advisor) ; Pawlas, Zbyněk (referee)
Document type: Bachelor's theses
Year: 2020
Language: cze
Abstract: [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
Keywords: mixing time; random walk on a graph; reversible Markov chain; speed of convergence; náhodná procházka na grafu; reverzibilní Markovův řetězec; rychlost konvergence; čas mixingu

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/121269

Permalink: http://www.nusl.cz/ntk/nusl-435203


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses