В теории вероятностей , то время смешивания из цепи Маркова время , пока цепь Маркова не «близка» к ее устойчивому состоянию распределению .
Точнее, фундаментальный результат о цепях Маркова состоит в том, что неприводимая апериодическая цепь в конечном состоянии имеет уникальное стационарное распределение π и, независимо от начального состояния, распределение цепи по времени t сходится к π, когда t стремится к бесконечности. Время смешивания относится к любому из нескольких вариантов формализации идеи: насколько большим должно быть t , пока распределение времени t не станет приблизительно π ? Один вариант, время смешивания расстояния вариации , определяется как наименьшее t , так что полное расстояние вариации вероятностных мер мало:
для всех подмножеств состояний и всех начальных состояний. Именно в этом смысле Дэйв Байер и Перси Диаконис ( 1992 ) доказали, что количество перетасовок, необходимых для перемешивания обычной колоды из 52 карт, равно 7. Математическая теория фокусируется на том, как время перемешивания изменяется в зависимости от размера лежащей в основе структуры. цепь. Для колоды с картами количество необходимых тасовок растет по мере . Наиболее развитая теория касается рандомизированных алгоритмов для # P-Complete алгоритмических задач подсчета, таких как количество раскрасок графа заданноговершинный граф. На такие проблемы для достаточно большого количества цветов можно ответить, используя метод цепи Маркова Монте-Карло и показывая, что время смешивания растет только как ( Jerrum 1995 ). Этот пример и пример с перемешиванием обладают свойством быстрого перемешивания , то есть время перемешивания увеличивается, самое большее, полиномиально быстро (количество состояний цепочки). Инструменты для доказательства быстрого перемешивания включают аргументы, основанные на проводимости и методе связи . В более широком использовании метода цепи Маркова Монте-Карло, строгое обоснование результатов моделирования потребует теоретического ограничения времени перемешивания, и многие интересные практические случаи не поддаются такому теоретическому анализу.
См. Также [ править ]
- Смешивание (математика) для формального определения смешивания
Ссылки [ править ]
- Олдос, Дэвид; Заливка, Джим, Обратимые цепи Маркова и случайные блуждания на графах , заархивировано из оригинала 21 сентября 2004 г. CS1 maint: обескураженный параметр ( ссылка ).
- Байер, Дэйв ; Diaconis, Persi (1992), "Скользящий ласточкин хвост перетасовать в его логове" (PDF) , Летопись прикладной вероятности , 2 (2): 294-313, DOI : 10,1214 / aoap / 1177005705 , JSTOR 2959752 , MR 1161056.
- Jerrum, Марк (1995), "Очень простой алгоритм оценки числа K -раскраски низкой степени графа", случайных структур и Алгоритмы , 7 (2): 157-165, DOI : 10.1002 / rsa.3240070205 , Руководство по ремонту 1369061.
- Левин, Дэвид А .; Перес, Юваль ; Уилмер, Элизабет Л. (2009), Марковские цепи и время перемешивания , Провиденс, Род-Айленд: Американское математическое общество, ISBN 978-0-8218-4739-8, MR 2466937.
- Синклер, Алистер (1993), Алгоритмы для случайной генерации и подсчета: подход с цепью Маркова , Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Бостон, Массачусетс, DOI : 10.1007 / 978-1-4612-0323-0 , ISBN 0-8176-3658-7, Руководство по ремонту 1201590.
