Náhodné procházky na grupě permutací - aneb kdy jsou karty dobře zamíchané

• Název práce v češtině: Náhodné procházky na grupě permutací - aneb kdy jsou karty dobře zamíchané
• Název v anglickém jazyce: Random walks on the symmetric group - how many times should you shuffle a deck of cards
• Klíčová slova: Markovský řetězec|míchání karet|systém Farao|čas mixingu
• Klíčová slova anglicky: Markov chain|shuffling cards|riffle shuffle|mixing time
• Akademický rok vypsání: 2021/2022
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra pravděpodobnosti a matematické statistiky (32-KPMS)
• Vedoucí / školitel: RNDr. Michaela Prokešová, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 22.10.2021
• Datum zadání: 22.10.2021
• Datum potvrzení stud. oddělením: 18.11.2021
• Datum a čas obhajoby: 07.09.2022 08:15
• Datum odevzdání elektronické podoby: 21.07.2022
• Datum odevzdání tištěné podoby: 25.07.2022
• Datum proběhlé obhajoby: 07.09.2022
• Oponenti: doc. RNDr. Daniel Hlubinka, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

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.

Předběžná náplň práce

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.