Original title: Coupling a rychlost konvergence diskrétních MCMC algoritmů.
Translated title: Coupling and speed of convergence of discrete MCMC algorithms.
Authors: Kalaš, Martin ; Prokešová, Michaela (advisor) ; Dvořák, Jiří (referee)
Document type: Bachelor's theses
Year: 2011
Language: cze
Abstract: [cze] [eng]
Konvergence marginálního rozdělení Markovova řetězce ke stacionárnímu rozdělení je důležitá vlastnost, která má v moderní matematice mnoho aplikací. Jednou z nich jsou např. Markov Chain Monte Carlo algoritmy, které slouží ke generování realizací ze složitých pravděpodobnostních rozdělení. Pro takové aplikace je klíčové správně odhadnout tzv. mixing time Markovova řetězce, tj. počet kroků nutný k tomu, aby se marginální rozdělení řetězce lišilo od stacionárního rozdělení jen s povolenou nepřesností. Cílem této práce je popsat metodu odhadu mixing time, která využívá obecnou pravděpodobnostní techniku zvanou coupling. V první části textu bude vybudován teoretický aparát, na jehož základě tuto metodu odvodíme. Ve druhé části předvedeme její použití na klasických příkladech Markovových řetězců, kterým je například náhodná procházka po grafu. V závěru ukážeme odhad rychlosti konvergence Metropolisova řetězce pro přípustná obarvení grafu, jakožto typického příkladu MCMC algoritmu. Convergence of the marginal distribution of a Markov chain to its stationary distribution is an essential property of this model with many applications in different fields of modern mathematics. Such typical applications are for example the Markov Chain Monte Carlo algorithms, which are useful for sampling from complicated probability distributions. A crucial point for usefulness of such algorithms is the so called mixing time of corresponding Markov chain, i.e. the number of steps the chain has to make for the difference between its current marginal distribution and stationary distribution to be sufficiently small. The main goal of this thesis is to describe a method for estimation of the mixing time based on a probability technique called coupling. In the first part we collect some definitions and propositions to show how the method works. Later the method is demonstrated on several traditional examples of Markov chains including e.g. random walk on a graph. In the end we study Metropolis chain on the set of proper colorings of a graph as a specific example of MCMC algorithm and show how to estimate its mixing time.
Keywords: convergence; coupling; Markov chain; MCMC algorithm; stationary distribution; coupling; konvergence; Markovův řetězec; MCMC algoritmus; stacionární rozdělení

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

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


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