Оглавление
Время смешивания цепи Маркова
-
Определение времени перемешивания
- Время перемешивания – это время, необходимое для приближения цепи Маркова к стационарному распределению.
- Уникальное стационарное распределение π существует для апериодических неприводимых цепей с конечным числом состояний.
-
Вариации времени перемешивания
- Общее время смешивания – это минимальное значение t, при котором расстояние смешивания между вероятностными измерениями мало.
- Выбор параметра
- ϵ
- влияет на время перемешивания, часто используется
- = 1/4.
-
Примеры времени перемешивания
- Дэйв Байер и Перси Диаконис доказали, что для перемешивания колоды из 52 карт требуется 7 перетасовок.
- Математическая теория показывает, что для
- n
- колоды карт время перемешивания увеличивается как
- 5
- log
- 2
-
- .
-
Быстрое перемешивание
- Время перемешивания увеличивается полиномиально с ростом количества состояний цепи Маркова.
- Инструменты для доказательства быстрого перемешивания включают аргументы, основанные на электропроводности и методе соединения.
-
Практическое применение
- Для строгого обоснования результатов моделирования требуется теоретическое ограничение времени перемешивания.
- Метод Монте-Карло с цепью Маркова широко используется в практических случаях, но не всегда поддается теоретическому анализу.
Полный текст статьи: