Original title:
Rychlost konvergence Markovových řetězců - spektrální metody
Translated title:
Mixing of Markov chains - spectral methods
Authors:
Hotmar, Vojtěch ; Prokešová, Michaela (advisor) ; Pawlas, Zbyněk (referee) Document type: Bachelor's theses
Year:
2022
Language:
cze Abstract:
[cze][eng] V této práci se zabýváme horními a dolními odhady času mixingu reverzibilních ho- mogenních Markovových řetězců s konečným stavovým prostorem a diskrétním časem. Odhady jsou založeny na spektrálních vlastnostech matic přechodu, které těmto řetěz- cům náleží. Primárně se zajímáme o vlastní čísla těchto matic, a o to, jaký mají vztah k rychlosti konvergence. Dále si ukážeme, co jsou součinové řetězce a projekce Markovových řetězců, a také, že jejich spektrální vlastnosti lze jednoduše odvodit z vlastností řetězců, ze kterých jsou tyto řetězce vybudovány. Tyto vlastnosti a odhady budou ukázány na několika názorných příkladech. 1In this thesis, we deal with the upper and lower bounds for the mixing time of reversi- ble homogeneous Markov chains with finite state space and discrete time. The estimates are based on the spectral properties of the transition matrices belonging to these chains. Primarily, we are interested in the eigenvalues of these matrices and how they relate to the rate of convergence. Next we will describe what the product chains and the projecti- ons of Markov chains are. And also that their spectral properties can be easily derived from the properties of the chains on which these chains are built. These properties and estimates are shown on several illustrative examples. 1
Keywords:
Markov chains|mixing time|spectral methods; Markovovy řetězce|čas mixingu|spektrální metody
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/174340