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

• Název práce v češtině: Míchání karet a konvergence Markovských řetězců
• Název v anglickém jazyce: Mixing cards and convergence of Markov chains
• Klíčová slova: Míchání karet, permutace, Markovské řetěezce, vzdálenost od rovnoměrného rozdělení
• Klíčová slova anglicky: Shuing cards, Permutations, Markov chains, Distance from uniform distribution
• Akademický rok vypsání: 2011/2012
• 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í: 27.10.2011
• Datum zadání: 31.10.2011
• Datum potvrzení stud. oddělením: 20.12.2011
• Datum a čas obhajoby: 04.09.2012 00:00
• Datum odevzdání elektronické podoby: 03.08.2012
• Datum odevzdání tištěné podoby: 03.08.2012
• Datum proběhlé obhajoby: 04.09.2012
• Oponenti: prof. RNDr. Viktor Beneš, DrSc.

Zásady pro vypracování

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.

Seznam odborné literatury

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.

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í. 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.