Original title: Coupling, transportní metrika a aplikace pro přibližné počítání
Translated title: Coupling, transportation metrics and applications to approximate counting
Authors: Kluvancová, Rozálie ; Prokešová, Michaela (advisor) ; Swart, Jan (referee)
Document type: Bachelor's theses
Year: 2023
Language: cze
Abstract: [cze] [eng]
Důležitou vlastností markovských řetězců s diskrétním časem a konečnou množinou stavů je rychlost konvergence marginálního rozdělení řetězce ke stacionárnímu rozdě- lení (neboli rychlost mixingu). Pokud zkonstruujeme coupling dvou markovských řetězců se stejnou maticí pravděpodobností přechodu, kdy jeden startuje ze stacionárního rozdě- lení a druhý z pevného stavu, můžeme ho použít k odhadu rychlosti mixingu. Cílem práce je popsat, jak můžeme takový coupling sestrojit pomocí transportní metriky, a aplikovat tuto metodu při přibližném počítání prvků množiny všech přípustných obarvení grafu. 1 An important property of discrete-time Markov chains with finite state space is the rate of convergence of the marginal distribution of the chain to the stationary distribution (i.e. mixing rate). If we construct a coupling of two Markov chains with the same transition matrix, where one starts from a stationary distribution and the other from a fixed state, we can use it to estimate the mixing rate. The main goal of this thesis is to describe how we can construct such a coupling using the transportation metric, and to apply this method to approximate counting of all proper colorings of the graph. 1
Keywords: coupling of probability distributions|transportation metric|approximate counting; coupling pravděpodobnostních rozdělení|transportní metrika|přibližné počítání

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

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


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