Original title: Náhodné procházky na grupě permutací - aneb kdy jsou karty dobře zamíchané
Translated title: Random walks on the symmetric group - how many times should you shuffle a deck of cards
Authors: Hruška, Martin ; Prokešová, Michaela (advisor) ; Hlubinka, Daniel (referee)
Document type: Bachelor's theses
Year: 2022
Language: cze
Abstract: [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
Keywords: Markov chain|shuffling cards|riffle shuffle|mixing time; Markovský řetězec|míchání karet|systém Farao|čas mixingu

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

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


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