Náhodné procházky na grupě permutací - aneb kdy jsou karty dobře zamíchané
| Thesis title in Czech: | Náhodné procházky na grupě permutací - aneb kdy jsou karty dobře zamíchané |
|---|---|
| Thesis title in English: | Random walks on the symmetric group - how many times should you shuffle a deck of cards |
| Key words: | Markovský řetězec|míchání karet|systém Farao|čas mixingu |
| English key words: | Markov chain|shuffling cards|riffle shuffle|mixing time |
| Academic year of topic announcement: | 2021/2022 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Department of Probability and Mathematical Statistics (32-KPMS) |
| Supervisor: | RNDr. Michaela Prokešová, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 22.10.2021 |
| Date of assignment: | 22.10.2021 |
| Confirmed by Study dept. on: | 18.11.2021 |
| Date and time of defence: | 07.09.2022 08:15 |
| Date of electronic submission: | 21.07.2022 |
| Date of submission of printed version: | 25.07.2022 |
| Date of proceeded defence: | 07.09.2022 |
| Opponents: | doc. RNDr. Daniel Hlubinka, Ph.D. |
| Guidelines |
| Práce se bude zabývat náhodnými procházkami na symetrické grupě (grupě permutací n prvků) a to speciálně modely, které jsou použitelné pro popis míchání balíčku karet, a zaměří se na otázku rychlosti mixingu (rychlosti konvergence marginálního rozdělení náhodné procházky k jejímu stacionárnímu rozdělení). Předpokládaným výstupem je práce přehledového (kompilačního) charakteru. |
| References |
| D Aldous, P Diaconis (1986): Shuffling cards and stopping times, Amer. Math. Monthly 93, 333-348.
D Bayer, P Diaconis (1992): Trailing the dovetail shuffle to its lair, Ann Appl Probab 92, 294-313. D A Levin, Y Peres (2017): Markov Chains and Mixing Times, AMS, Providence. B Mann (1994): How many times should you shuffle a deck of cards? UMAP J. 15, 303-332. |
| Preliminary scope of work |
| Základní otázka při míchání karet je: kolikrát je třeba karty zamíchat, aby už byly dostatečně náhodně rozdělené. Neboli kolikrát je třeba karty zamíchat, aby náhodné rozdělení pořadí karet v balíčku už bylo dostatečně blízko rovnoměrnému rozdělení na množině všech možných pořadí karet. Matematická formalizace procesu míchání karet odpovídá modelu náhodné procházky na symetrické grupě řádu n (grupě všech permutací n prvků) - což je Markovský řetězec. A problém míchání karet se převede na problém odhadu vzdálenosti marginálního rozdělení tohoto Markovského řetězce od jeho stacionárního rozdělení. Potom už je možné použít standardních metod pro odhad rychlosti konvergence Markovského řetězce k jeho stacionárnímu rozdělení, jako je například coupling nebo silně stacionární časy. |