Název:
Coupling a rychlost konvergence Markovských řetězců
Překlad názvu:
Coupling and the speed of convergence of Markov chains
Autoři:
Macháček, Adam ; Prokešová, Michaela (vedoucí práce) ; Honzl, Ondřej (oponent) Typ dokumentu: Bakalářské práce
Rok:
2011
Jazyk:
cze
Abstrakt: [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. 1In 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
Klíčová slova:
coupling; Markovský řetězec; rychlost konvergence Markovských řetězců; silně rovnoměrné časy; coupling; Markov chain; speed of convergence of Markov chains; strong uniform times