Original title: Coupling a rychlost konvergence Markovských řetězců
Translated title: Coupling and the speed of convergence of Markov chains
Authors: Macháček, Adam ; Prokešová, Michaela (advisor) ; Honzl, Ondřej (referee)
Document type: Bachelor's theses
Year: 2011
Language: cze
Abstract: [cze] [eng]
V předložené práci studujeme dvě metody pro odvození od- hadu rychlosti konvergence marginálního rozdělení diskrétního, aperio- dického a nerozložitélného Markovského řetězce s konečným stavovým prostorem k jeho stacionárnímu rozdělení. Nejprve se zabýváme odhado- váním rychlosti konvergence pomocí couplingové metody. K této metodě potřebujeme vzdálenost v totální variaci, kterou definujeme a vysvětlíme úlohu, kterou má tato vzdálenost v teorii odhadování rychlosti konver- gence. V druhé části studujeme odhad rychlosti konvergence metodou silně rovnoměrných časů. Obě metody popíšeme a dokážeme o nich ně- která základní tvrzení. Poté ukážeme použití obou postupů na několika příkladech, především na příkladu procházky po hyperkrychli a na mo- delu míchání karet. 1 In the present work we study two methods for estimating the rate of convergence of marginal distribution of a discrete-time irre- ducible and aperiodic Markov chain to its stationary distribution (i.e. the speed of mixing). Firstly, we concentrate on deriving an upper bound for the rate of convergence by using the coupling technique. Moreover, we will also define the total variation distance and explain its role in the es- timation of the speed of mixing. In the second part we will study the me- thod of strong uniform times. Both methods are described in detail and several basic theorems are proved. Finally we demonstrate the use of both approaches on a number of models, particularly on the random walk on a hypercube and on shuffling a deck of cards. 1
Keywords: coupling; Markov chain; speed of convergence of Markov chains; strong uniform times; coupling; Markovský řetězec; rychlost konvergence Markovských řetězců; silně rovnoměrné časy

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/38351

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


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