Original title: Silně stacionární časy a konvergence Markovských řetězců
Translated title: Strong stationary times and convergence of Markov chains
Authors: Suk, Luboš ; Prokešová, Michaela (advisor) ; Kříž, Pavel (referee)
Document type: Bachelor's theses
Year: 2012
Language: cze
Abstract: [cze] [eng]
V této práci si ukážeme, jak se dá odhadovat rychlost konvergence markovských řetězců k jejich stacionárnímu rozdělení. Budeme k tomu používat metodu využívající silně stacionárních časů. Zaměříme se pouze na nerozložitelné a aperiodické řetězce, u kterých máme zaručenou existenci právě jednoho sta- cionárního rozdělení. Zavedeme si čas mixingu markovského řetězce neboli čas potřebný k tomu, aby marginální rozdělení řetězce bylo dostatečně blízko stacionárnímu. K měření vzdálenosti mezi rozděleními budeme v této práci používat vzdálenost v totální variaci. Hlavním cílem práce bude pro vybrané řetězce zkonstruovat vhodný silně stacionární čas a ten pak použít k nalezení horního odhadu času mixingu. In this thesis we study the estimation of speed of convergence of Markov chains to their stacionary distributions. For that purpose we will use the method of strong stationary times. We focus on irreducible and aperiodic chains only since in that case the existence of exactly one stationary distribution is guaranteed. We introduce the mixing time for a Markov chain as the time needed for the marginal distribution of the chain to be sufficiently close to the stationary dis- tribution. The distance between two distributions is measured by the total variation distance. The main goal of this thesis is to construct an appropriate strong stationary time for selected chains and then use it for obtaining an upper bound for the mixing time.
Keywords: markov chain; mixing time; strong stationary time; total variation distance; markovský řetězec; silně stacionární čas; vzdálenost v totální variaci; č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/46005

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


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