Název: Coupling, transportní metrika a aplikace pro přibližné počítání
Překlad názvu: Coupling, transportation metrics and applications to approximate counting
Autoři: Kluvancová, Rozálie ; Prokešová, Michaela (vedoucí práce) ; Swart, Jan (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2023
Jazyk: cze
Abstrakt: [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
Klíčová slova: coupling pravděpodobnostních rozdělení|transportní metrika|přibližné počítání; coupling of probability distributions|transportation metric|approximate counting

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/184374

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-534269


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce