Original title: Rychlost konvergence Markovových řetězců - dolní meze pro mixing
Translated title: Mixing of Markov chains - lower bounds for mixing
Authors: Ditrich, Jakub ; Prokešová, Michaela (advisor) ; Swart, Jan (referee)
Document type: Bachelor's theses
Year: 2022
Language: cze
Abstract: [cze] [eng]
V práci se zabýváme rychlostí konvergence ireducibilních a aperiodických homogenních markovských řetězců s konečnou diskrétní množinou stavů. Přesněji dolními odhady času potřebného k dostatečnému přiblížení marginálního rozdělení řetězce ke stacionárnímu rozdělení, takzvaným časem mixingu. Ukážeme různé metody odvození odhadů, patřičně je namotivujeme, zformulujeme a dokážeme. Nakonec ukážeme jejich použití na vhodných příkladech. Výsledkem je přehledný soupis tří metod, které se za účelem získání dolní meze dají použít. 1 The focus of the thesis is the convergence of irreducible aperiodic homoge- neous Markov chains with a finite and discrete set of states. Specifically, lower bounds on the time needed for the chain's marginal probability distribution to be sufficiently close to the stationary distribution, so called mixing time. Multiple methods are introdu- ced, properly motivated and proven. Finally, each method is demonstrated on a suitable example. The result is an overview of three methods that can be used to derive lower bounds for mixing time. 1
Keywords: lower bound for mixing time; Markov chain; speed of convergence; dolní mez pro čas mixingu; Markovův řetězec; rychlost konvergence

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

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


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