Míchání karet a konvergence Markovských řetězců

• Thesis title in Czech: Míchání karet a konvergence Markovských řetězců
• Thesis title in English: Mixing cards and convergence of Markov chains
• Key words: Míchání karet, permutace, Markovské řetěezce, vzdálenost od rovnoměrného rozdělení
• English key words: Shuing cards, Permutations, Markov chains, Distance from uniform distribution
• Academic year of topic announcement: 2011/2012
• 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: 27.10.2011
• Date of assignment: 31.10.2011
• Confirmed by Study dept. on: 20.12.2011
• Date and time of defence: 04.09.2012 00:00
• Date of electronic submission: 03.08.2012
• Date of submission of printed version: 03.08.2012
• Date of proceeded defence: 04.09.2012
• Opponents: prof. RNDr. Viktor Beneš, DrSc.

Guidelines

Práce se bude zabývat odhadem rychlosti mixingu diskrétních Markovských řetězců a to speciálně případem, kdy uvažovaný řetězec je náhodná procházka na symetrické grupě. Jednoduchým příkladem praktické aplikace tohoto modelu je míchání karet. Práce je kompilační, vlastní příspěvek studenta bude spočívat v přehledném zpracování a vysvětlení studovaných metod (v češtině nebo slovenštině), doplnění podrobností v některých důkazech a vypracování vybraných cvičení z knihy Markov Chains and Mixing Times.

Úspěšné absolvování předmětu NSTP022 (Pravděpodobnost a matematická statistika) nebo NSTP129 (Pravděpodobnost a statistika) do okamžiku zápisu bakalářské práce nutné. Pro úspěšné vypracování práce je rovněž vhodné absolvovat předměty NSTP238 a NSTP050.

References

D Aldous, P Diaconis (1986): Shuffling cards and stopping times, Amer. Math. Monthly 93, 333-348.

D A Levin, Y Peres, E L Wilmer (2009): 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í. K řešení tohoto problému pak můžeme použít standardních metod pro odhad rychlosti konvergence Markovského řetězce k jeho stacionárnímu rozdělení, jako je coupling nebo silně stacionární časy.