Thomas Fernique

Как долго нужно тасовать карты?

T. Fernique планирует провести 4 занятия.

Если раз за разом подбрасывать монетку, то результат очередного подбрасывания никак не зависит от предыдущих. А что получится, если мы будем бродить по (достаточно сложному) графу, каждый раз кидая монетку или кубик, чтобы решить, по какому ребру переходить в следующую вершину? Получится один из модельных примеров для очень широкого и полезного класса процессов — цепей Маркова.

Эти простые случайные процессы имеют множество применений как статистические модели процессов реального мира. Впрочем, постоянно растущий размер изучаемых моделей делает вопрос их поведения (в частности, скорость перемешивания) в зависимости от размера систем живой и центральной частью современной теории вероятности.

Программа курса

• введение в цепи Маркова;
• алгоритм Метрополиса–Гастингса;
• каплинг;
• тасование карт.

Литература:

Markov chains and mixing times, David A. Levin, Yuval Peres, and Elizabeth L. Wilmer,
with an Appendix written by James G. Propp and David B. Wilson, American Mathematical Society, 2009.

Organization Committee e-mail:
dubna@mccme.ru