Název:
Rychlost konvergence Markovových řetězců - dolní meze pro mixing
Překlad názvu:
Mixing of Markov chains - lower bounds for mixing
Autoři:
Ditrich, Jakub ; Prokešová, Michaela (vedoucí práce) ; Swart, Jan (oponent) Typ dokumentu: Bakalářské práce
Rok:
2022
Jazyk:
cze
Abstrakt: [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. 1The 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
Klíčová slova:
dolní mez pro čas mixingu; Markovův řetězec; rychlost konvergence; lower bound for mixing time; Markov chain; speed of convergence