Поглощающая цепь Маркова - Absorbing Markov chain
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/10/Drunkard%E2%80%99s_walk.svg/500px-Drunkard%E2%80%99s_walk.svg.png)
В математической теории вероятность, поглощающая цепь Маркова это Цепь Маркова в котором каждое состояние может достичь состояния поглощения. Поглощающее состояние - это состояние, в которое однажды нельзя выйти.
Как и общие цепи Маркова, могут существовать поглощающие цепи Маркова в непрерывном времени с бесконечным пространством состояний. Однако в этой статье основное внимание уделяется случаю дискретного времени в пространстве состояний.
Формальное определение
Цепь Маркова является поглощающей, если[1][2]
- есть хотя бы один поглощающее состояние и
- можно перейти из любого состояния по крайней мере в одно поглощающее состояние за конечное число шагов.
В поглощающей цепи Маркова состояние, которое не поглощает, называется переходным.
Каноническая форма
Пусть поглощающая цепь Маркова с матрицей перехода п имеют т переходные состояния и р поглощающие состояния. потом
куда Q это т-к-т матрица р ненулевой т-к-р матрица 0 является р-к-т нулевая матрица, и яр это р-к-р единичная матрица. Таким образом, Q описывает вероятность перехода из одного переходного состояния в другое, пока р описывает вероятность перехода из некоторого переходного состояния в некоторое поглощающее состояние.
Фундаментальная матрица
Основным свойством поглощающей цепи Маркова является ожидаемое количество посещений переходного состояния. j начиная с переходного состояния я (до впитывания). Вероятность перехода с я к j точно k шаги - это (я,j) -вход Qk. Подводя итог для всех k (от 0 до ∞) дает фундаментальную матрицу, обозначенную N. Можно доказать, что
куда ят это т-к-т единичная матрица. (я, j) запись матрицы N ожидаемое количество раз, когда цепь находится в состоянии j, учитывая, что цепочка запущена в состоянии я. С матрицей N в свою очередь, легко получить другие свойства цепи Маркова.[2]
Разница в количестве посещений
Разница в количестве посещений переходного состояния j с запуском в переходном состоянии я (до впитывания) - это (я,j) -вход матрицы
куда Ndg это диагональная матрица с той же диагональю, что и N и Nкв это Произведение Адамара из N с собой (т.е. каждая запись N возведен в квадрат).
Ожидаемое количество шагов
Ожидаемое количество шагов до поглощения при запуске в переходном состоянии я это яй элемент вектора
куда 1 это длина-т вектор-столбец, все элементы которого равны 1.
Разница в количестве шагов
Разница в количестве шагов до поглощения при запуске в переходном состоянии я это яй элемент вектора
куда ткв это Произведение Адамара из т с собой (т.е. каждая запись т возведен в квадрат).
Переходные вероятности
Вероятность посещения переходного состояния j при запуске в переходном состоянии я это (я,j) -вход матрицы
куда Ndg это диагональная матрица с той же диагональю, что и N.
Поглощающие вероятности
Еще одно свойство - это вероятность быть поглощенным в поглощающем состоянии j при запуске из переходного состояния. я, какой (я,j) -вход матрицы
Примеры
Генерация строки
Рассмотрим процесс многократного переворачивания честная монета пока не появится последовательность (орел, решка, решка). Этот процесс моделируется поглощающей цепью Маркова с матрицей перехода
Первое состояние представляет собой пустой строкой, второй - строку «H», третий - строку «HT», а четвертый - строку «HTH». Хотя в действительности подбрасывание монеты прекращается после того, как генерируется цепочка «HTH», перспектива поглощающей цепи Маркова заключается в том, что процесс перешел в поглощающее состояние, представляющее цепочку «HTH», и, следовательно, не может выйти.
Для этой поглощающей цепи Маркова фундаментальная матрица имеет вид
Ожидаемое количество шагов, начиная с каждого из переходных состояний, равно
Следовательно, ожидаемое количество подбрасываний монеты перед наблюдением за последовательностью (орел, решка, орел) равно 10, запись для состояния представляет собой пустую строку.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Probability_of_winning_Snakes_and_Ladders_by_turns.svg/220px-Probability_of_winning_Snakes_and_Ladders_by_turns.svg.png)
Азартные игры
Игры, полностью основанные на шансе, можно смоделировать с помощью увлекательной цепи Маркова. Классический пример - древнеиндийская настольная игра. Змеи и лестницы. График справа[3] отображает массу вероятности в одиночном поглощающем состоянии, которое представляет собой конечный квадрат, когда матрица перехода возводится в большую и большую степень. Чтобы определить ожидаемое количество ходов для завершения игры, вычислите вектор т как описано выше и изучить тНачните, что составляет примерно 39,2.
Клиника инфекционных болезней
Пример тестирования на инфекционные заболевания в продуктах крови или в медицинских клиниках часто преподается как пример поглощающей цепи Маркова.[4] Например, общественная модель Центров США по контролю и профилактике заболеваний (CDC) для ВИЧ и гепатита B:[5] иллюстрирует свойство, заключающееся в том, что поглощение цепей Маркова может приводить к обнаружению болезни по сравнению с потерей обнаружения другими способами.
В стандартной модели CDC цепь Маркова имеет пять состояний: состояние, в котором человек не инфицирован, затем состояние с зараженным, но не обнаруживаемым вирусом, состояние с обнаруживаемым вирусом и состояния поглощения, когда человек бросил / пропал из клиники, или быть обнаруженным (цель). Типичные скорости перехода между марковскими состояниями - это вероятность п за единицу времени заражения вирусом, ш для скорости удаления периода окна (время до обнаружения вируса), q для показателя выхода / потери из системы, и d для обнаружения, предполагая типичную скорость на котором система здравоохранения проводит анализы рассматриваемого продукта крови или пациентов.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8c/Hivmodelmarkov.png/220px-Hivmodelmarkov.png)
Отсюда следует, что мы можем «пройтись по модели Маркова», чтобы определить общую вероятность обнаружения человека, начавшего как необнаруженный, путем умножения вероятностей перехода в каждое следующее состояние модели как:
.
Последующее общее абсолютное количество ложноотрицательных тестов - основная проблема CDC - тогда будет представлять собой частоту тестов, умноженную на вероятность достижения зараженного, но неопределяемого состояния, умноженную на продолжительность пребывания в зараженном неопределяемом состоянии:
.
Смотрите также
Рекомендации
- ^ а б Гринстед, Чарльз М .; Снелл, Дж. Лори (Июль 1997 г.). "Глава 11: Цепи Маркова" (PDF). Введение в вероятность. Американское математическое общество. ISBN 978-0-8218-0749-1.
- ^ а б Кемени, Джон Г.; Снелл, Дж. Лори (Июль 1976 г.) [1960]. "Глава 3: Поглощающие цепи Маркова". In Gehring, F. W .; Халмос, П. Р. (ред.). Конечные цепи Маркова (Второе изд.). Нью-Йорк Берлин Гейдельберг Токио: Springer-Verlag. стр.224. ISBN 978-0-387-90192-3.
- ^ На основании определения, приведенного в С.К. Альтоен; Л. Кинг; К. Шиллинг (март 1993 г.). «Как долго длится игра в змей и лестниц?». Математический вестник. The Mathematical Gazette, Vol. 77, № 478. 78 (478): 71–76. Дои:10.2307/3619261. JSTOR 3619261.
- ^ результаты, поиск (1998-07-28). Цепи Маркова. Кембридж: Издательство Кембриджского университета. ISBN 9780521633963.
- ^ Сандерс, Джиллиан Д .; Анайя, Генри Д .; Аш, Стивен; Хоанг, Туен; Golden, Joya F .; Баюми, Ахмед М .; Оуэнс, Дуглас К. (июнь 2010 г.). «Экономическая эффективность стратегий улучшения тестирования на ВИЧ и получения результатов: экономический анализ рандомизированного контролируемого исследования». Журнал общей внутренней медицины. 25 (6): 556–563. Дои:10.1007 / s11606-010-1265-5. ISSN 0884-8734. ЧВК 2869414. PMID 20204538.