Original title:
Konvergence metody Markov chain Monte Carlo
Translated title:
Convergence of the Markov chain Monte Carlo method
Authors:
Dzurilla, Matúš ; Beneš, Viktor (advisor) ; Dostál, Petr (referee) Document type: Bachelor's theses
Year:
2015
Language:
slo Abstract:
[eng][cze] This thesis deals with the problem of random q-coloring from graph theory, in which goal is to color all vertices of graph by q colors so that no adjacent vertices have the same color. The aim is to generate random q-coloring from uniform distribution on the set of relevant solutions. The problem was expres- sed through Markov chain and approach was done through Markov Chain Monte Carlo method, namely the Gibbs sampler. The aim was to modify theorem of fast convergence of Gibbs sampler from systematic sweep to random sweep. It was ne- cessary to prove several auxiliary theorems, and in the proof of main theorem the "coupling" method was used. We managed to estimate the number of iterations needed to make the distance, in terms of total variation,from the distribution on the chain to the target distribution sufficiently small. The meaning og the the- orem was demonstrated in numerical examples and example od simulation was also added. 24Tato práce se zabývá problémem náhodného q-obarvení z teorie grafů, ve kte- rém je úkolem obarvit vrcholy grafu q barvami, tak aby žádné sousední vrcholy neměly stejnou barvu. Cílem je generovat náhodné q-obarvení z rovnoměrného rozdělení na množině přípustných řešení. Problém byl formulovaný pomocí Mar- kovských řetězců a bylo k němu přistupováno přes Markov Chain Monte Carlo metodu, konkrétně Gibbsův výběrový plán. Cílem byla modifikace věty o rych- losti konvergence Gibbsova výběrového plánu z systematického na náhodný výběr vrcholů. Bylo třeba dokázat několik pomocných tvrzení a při důkazu hlavní věty byla použita metoda "coupling". Podařilo se odhadnout počet iteraci potřebných k tomu aby vzdálenost, ve smyslu totální variace, rozdělení řetězce od cílového rozdělení byla dostatečně malá. Význam věty byl demonstrovaný na numerických příkladech a je přidána také ukázka simulace. 23
Keywords:
Gibbs sampler; random q-coloring; total variation distance; Gibbsův výběrový plán; náhodné q-obarvení; vzdálenost totální variace
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/81265