Název: Náhodné procházky na grupě permutací - aneb kdy jsou karty dobře zamíchané
Překlad názvu: Random walks on the symmetric group - how many times should you shuffle a deck of cards
Autoři: Hruška, Martin ; Prokešová, Michaela (vedoucí práce) ; Hlubinka, Daniel (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2022
Jazyk: cze
Abstrakt: [cze] [eng]
Tato práce se zabývá náhodnými procházkami na symetrické grupě a to modely, které se používají pro popis míchání balíčku karet. V práci se zaměříme na otázku rychlosti mixingu (rychlosti konvergence marginálního rozdělení náhodné procházky k jejímu stacionárnímu rozdělení). Položíme si základní otázku při míchání karet: kolikrát je potřeba karty zamíchat, aby už byly dostatečně náhodně rozdělené. Model náhodné procházky, což je Markovův řetězec, je matematickou formalizací procesu míchání karet. Problém míchání karet převedeme na problém odhadu vzdálenosti mezi marginálním rozdělením tohoto Markovského řetězce a jeho stacionárním rozdělením. Potom využijeme standardních metod pro odhad rychlosti konvergence Markovského řetězce k jeho stacionárnímu rozdělení, jako je například silně stacionární čas. 1 This thesis deals with random walks on a symmetric group, namely the models that are used to describe the shuffling of a deck of cards. In this work we focus on the question of mixing speed (the speed of convergence of the marginal distribution of a random walk to its stationary distribution). We ask ourselves a basic question when shuffling cards: how many times do the cards need to be shuffled so that they are already sufficiently randomly distributed. The random walk model, which is a Markov chain, is the mathematical formalization of the card shuffling process. We transfer the card shuffling problem to the problem of estimating the distance between the marginal distribution of this Markov chain and its stationary distribution. We then use standard methods to estimate the convergence rate of the Markov chain to its stationary distribution, such as strong stationary times. 1
Klíčová slova: Markovský řetězec|míchání karet|systém Farao|čas mixingu; Markov chain|shuffling cards|riffle shuffle|mixing time

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

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


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