Цепи Маркова и времена смешивания
«Цепи Маркова и время смешивания» — книга о времени смешивания цепей Маркова . Второе издание было написано Дэвидом А. Левином и Ювалем Пересом . Элизабет Уилмер была соавтором первого издания и считается соавтором второго издания. Первое издание было опубликовано в 2009 году Американским математическим обществом . [1] [2] с расширенным вторым изданием в 2017 году. [3] [4] [5] [6]
Фон
[ редактировать ]Цепь Маркова — это случайный процесс, определяемый набором состояний и для каждого состояния распределением вероятностей состояний. Начиная с начального состояния, он следует за последовательностью состояний, где каждое состояние в последовательности выбирается случайным образом из распределения, связанного с предыдущим состоянием.В этом смысле он «без памяти»: каждый случайный выбор зависит только от текущего состояния, а не от прошлой истории состояний. При мягких ограничениях цепь Маркова с конечным набором состояний будет иметь стационарное распределение , к которому она сходится, а это означает, что после достаточно большого числа шагов вероятность пребывания в каждом состоянии будет близка к вероятности нахождения в каждом состоянии, близкой к вероятности стационарного распределения: независимо от начального состояния или точного количества шагов. Время смешивания цепи Маркова — это количество шагов, необходимых для того, чтобы произошла эта сходимость с подходящей степенью точности. Говорят, что семейство цепей Маркова быстро перемешивается , если время смешивания является полиномиальной функцией некоторого размерного параметра цепи Маркова, и в противном случае медленно перемешивайте . Эта книга посвящена конечным цепям Маркова, их стационарным распределениям и временам перемешивания, а также методам определения того, быстро или медленно перемешиваются цепи Маркова. [1] [4]
Классический и знакомый пример этого явления — перетасовка колод карт: сколько перетасовок требуется, начиная с неслучайной исходной колоды карт, чтобы получить почти случайную перестановку ? Это можно смоделировать как цепь Маркова, состояния которой представляют собой упорядочение колоды карт, а вероятности перехода из одного состояния в другое задаются некоторой математической моделью случайного перетасовки, такой как модель Гилберта-Шеннона-Ридса . В этой ситуации быстрое перемешивание цепи Маркова означает, что не нужно выполнять огромное количество перетасовок, чтобы достичь достаточно рандомизированного состояния. Помимо карточных игр, аналогичные соображения возникают в поведении физических систем, изучаемых статистической механикой , и некоторых рандомизированных алгоритмов . [1] [4]
Темы
[ редактировать ]Книга разделена на две части: первая более вводная, а вторая более продвинутая. [2] [6] После трех глав вводного материала о цепях Маркова, в четвертой главе определяются способы измерения расстояния цепи Маркова до ее стационарного распределения и времени, необходимого для достижения этого расстояния. В пятой главе описывается связь , один из стандартных методов ограничения времени смешивания. В этом методе создаются две цепи Маркова, одна начинается с заданного начального состояния, а другая — со стационарного распределения, с переходами, которые имеют правильные вероятности внутри каждой цепи, но не являются независимыми от цепочки к цепочке, в таком Таким образом, две цепи, скорее всего, перейдут в те же состояния, что и друг друга. Таким образом, время смешивания может быть ограничено временем синхронизации двух связанных цепей. В шестой главе обсуждается метод, называемый «сильными стационарными временами», с помощью которого для некоторых цепей Маркова можно доказать, что случайный выбор времени остановки из определенного распределения приведет к состоянию, полученному из стационарного распределения. [6]
После главы о нижних границах времени смешивания, основанных на « коэффициенте узкого места » и изопериметрическом числе , [5] Следующие две главы первой части посвящены двум важным примерам: перетасовке карт и случайным блужданиям по графам . В главах 10 и 11 рассматриваются еще два параметра, тесно связанных со временем смешивания: время попадания , при котором цепь Маркова впервые достигает заданного состояния, и время покрытия, при котором она впервые достигает всех состояний. [6] Они также обсуждают обратимые во времени цепи Маркова и их подключение к электрическим сетям. [5] В последней главе этой части обсуждается связь между спектральной щелью цепи Маркова и временем ее смешивания. [6]
Вторая часть книги включает в себя еще много примеров применения этой теории, в том числе динамику Глаубера в модели Изинга , марковские модели хромосомной перестройки , асимметричный процесс простого исключения , в котором частицы случайным образом перепрыгивают в незанятые соседние пространства, и случайные ходит в группе фонарщиков . [6] Темы, затронутые во второй части книги, включают дополнительные сведения о спектральных графах и графах-расширителях . [5] соединение путей (при котором последовательность из более чем двух цепей Маркова соединена попарно), [6] связи между сцепкой и расстоянием землеройной машины , мартингалы , [5] критические температуры , [2] «эффект обрезания», при котором распределение вероятностей цепи быстро меняется между несмешанным и смешанным, [1] [2] [6] процесс развивающегося множества (производная цепь Маркова на множествах состояний данной цепи), [2] Цепи Маркова с бесконечным числом состояний и цепи Маркова, действующие в непрерывном времени, а не в виде дискретной последовательности шагов. В гостевой главе Джима Проппа и Дэвида Б. Уилсона описывается связь из прошлого , метод получения выборок, взятых точно из стационарного распределения, а не (как получается из методов Монте-Карло с марковскими цепями ) приближений к этому распределению. [1] [2] В последней главе собраны открытые проблемы в этой области. [5]
Аудитория и прием
[ редактировать ]Эта книга может быть использована либо в качестве справочника исследователями в областях, использующих эти методы, либо в качестве основы для курса для аспирантов. [1] особенно тот, который ограничен вводным материалом в первой части книги. [6] на уровне бакалавра . только знания теории вероятностей и линейной алгебры где требуются [1] [2] Однако рецензент Рик Дарретт предполагает, что содержание книги будет слишком сложным для курсов бакалавриата, даже в университетах исследовательского уровня. [6] и рецензент Такис Константопулос предполагает, что содержание книги будет лучше оценено читателем, который уже имел некоторое представление о материале, который она охватывает. [5]
Рецензент Олле Хэггстрем называет книгу «авторитетной и легко читаемой». [1] Рецензент HM Mai пишет, что его объяснения осторожны и «хорошо мотивированы», а текст «ясный и ясный». [2] Рецензент Ласло Лакатос называет его «блестящим руководством по современной теории цепей Маркова». А рецензент Дэвид Олдос предсказывает, что эта книга «долго будет оставаться наиболее необходимой литературой» в этой области.
Ссылки
[ редактировать ]- ^ Jump up to: а б с д и ж г час Хэггстрем, Олле (2010), «Обзор цепей Маркова и времени смешивания (1-е изд.)», Mathematical Reviews , MR 2466937
- ^ Jump up to: а б с д и ж г час Май, Х.М., «Обзор цепей Маркова и времени смешивания (1-е изд.)», zbMATH , Zbl 1160.60001
- ^ Лакатош, Ласло, «Обзор цепей Маркова и времени смешивания (2-е изд.)», zbMATH , Zbl 1390.60001
- ^ Jump up to: а б с Олдос, Дэвид (март 2019 г.), «Обзор цепей Маркова и времени смешивания (2-е изд.)», The Mathematical Intelligencer , 41 (1): 90–91, doi : 10.1007/s00283-018-9839-x , MR 3918079
- ^ Jump up to: а б с д и ж г Константопулос, Такис (2019), «Обзор цепей Маркова и времени смешивания (2-е изд.)», SIAM Review , 61 (3): 631–634, doi : 10.1137/19N974865 , MR 3989422
- ^ Jump up to: а б с д и ж г час я дж Дарретт, Рик (сентябрь 2019 г.), «Обзор цепей Маркова и времени смешивания (2-е изд.)» , MAA Reviews , Математическая ассоциация Америки