Поглощающая цепь Маркова

(Конечная) прогулка пьяницы - пример поглощающей цепи Маркова. ^[1]

В математической теории вероятности , поглощая цепь Маркова является цепью Маркова , в которой каждое государство может достигать поглощающее состояние. Поглощающее состояние - это состояние, в которое, однажды войдя, нельзя выйти.

Как и общие цепи Маркова, могут существовать поглощающие цепи Маркова в непрерывном времени с бесконечным пространством состояний. Однако в этой статье основное внимание уделяется случаю дискретного времени в пространстве состояний.

Формальное определение [ править ]

Цепь Маркова является поглощающей цепью, если ^[1]^[2]

есть хотя бы одно поглощающее состояние и
можно перейти из любого состояния по крайней мере в одно поглощающее состояние за конечное число шагов.

В поглощающей цепи Маркова состояние, которое не поглощает, называется переходным.

Каноническая форма [ править ]

Пусть поглощающая цепь Маркова с переходной матрицей P имеет t переходных состояний и r поглощающих состояний. потом

{\ displaystyle P = \ left ({\ begin {array} {cc} Q&R \\\ mathbf {0} & I_ {r} \ end {array}} \ right),}

где Q является т матрицы с размерностью т матрица R является ненулевым т матрицы с размерностью г матрицей, 0 является г матрицы с размерностью т нулевой матрицы, а я _т представляет собой R матрицу с размерностью г единичной матрицей. Таким образом, Q описывает вероятность перехода из одного переходного состояния в другое, в то время как R описывает вероятность перехода из некоторого переходного состояния в некоторое поглощающее состояние.

Фундаментальная матрица [ править ]

Основное свойство поглощающей цепи Маркова - это ожидаемое количество посещений переходного состояния j, начиная с переходного состояния i (до того, как оно будет поглощено). Вероятность перехода от i к j ровно за k шагов - это ( i , j ) -запись Q ^k . Суммируя это для всех к (от 0 до ∞) дает фундаментальную матрицу, обозначаемый N . Можно доказать, что

N=\sum _{k=0}^{\infty }Q^{k}=(I_{t}-Q)^{-1},

где я _т является т матрицу с размерностью т единичная матрица. Элемент ( i , j ) матрицы N - это ожидаемое количество раз, когда цепочка находится в состоянии j , при условии, что цепочка началась в состоянии i . Имея под рукой матрицу N , легко получить другие свойства цепи Маркова. ^[2]

Разница в количестве посещений [ править ]

Дисперсия количества посещений переходного состояния j с запуском в переходном состоянии i (до поглощения) является ( i , j ) -записью матрицы

N_{2}=N(2N_{\operatorname {dg} }-I_{t})-N_{\operatorname {sq} },

где N _дг является диагональная матрица с той же диагональю , как N и N _кв является произведение Адамара из N с самим собой (то есть каждый элемент N в квадрате).

Ожидаемое количество шагов [ править ]

Ожидаемое количество шагов до поглощения при запуске в переходном состоянии i - это i- я запись вектора

\mathbf {t} =N\mathbf {1} ,

где 1 - вектор-столбец длины t , все элементы которого равны 1.

Разница в количестве шагов [ править ]

Разница в количестве шагов до поглощения при запуске в переходном состоянии i является i- й записью вектора

(2N-I_{t})\mathbf {t} -\mathbf {t} _{\operatorname {sq} },

где т _кв является произведение Адамара о т с самим собой (то есть каждый элемент т в квадрате).

Переходные вероятности [ править ]

Вероятность посещения переходного состояния j при запуске в переходном состоянии i - это ( i , j ) -запись матрицы

H=(N-I_{t})(N_{\operatorname {dg} })^{-1},

где N _дг является диагональной матрицей с той же диагональю , как N .

Поглощающие вероятности [ править ]

Другое свойство - это вероятность быть поглощенным в поглощающем состоянии j при запуске из переходного состояния i , которое является ( i , j ) -заходом матрицы

B=NR.

В качестве альтернативы, эта вероятность также может быть непосредственно получена из ( i , j ) -записи для достаточно большого значения n . $P^{n}$

Примеры [ править ]

Генерация строки [ править ]

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

P={\begin{bmatrix}1/2&1/2&0&0\\0&1/2&1/2&0\\1/2&0&0&1/2\\0&0&0&1\end{bmatrix}}.

Первое состояние представляет собой пустую строку , второе состояние - строку «H», третье состояние - строку «HT», а четвертое состояние - строку «HTH». Хотя в действительности подбрасывание монеты прекращается после того, как генерируется цепочка «HTH», перспектива поглощающей цепи Маркова заключается в том, что процесс перешел в поглощающее состояние, представляющее цепочку «HTH», и, следовательно, не может выйти.

Для этой поглощающей цепи Маркова фундаментальная матрица имеет вид

{\begin{aligned}N&=(I-Q)^{-1}=\left({\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}}-{\begin{bmatrix}1/2&1/2&0\\0&1/2&1/2\\1/2&0&0\end{bmatrix}}\right)^{-1}\\[4pt]&={\begin{bmatrix}1/2&-1/2&0\\0&1/2&-1/2\\-1/2&0&1\end{bmatrix}}^{-1}={\begin{bmatrix}4&4&2\\2&4&2\\2&2&2\end{bmatrix}}.\end{aligned}}

Ожидаемое количество шагов, начиная с каждого из переходных состояний, равно

\mathbf {t} =N\mathbf {1} ={\begin{bmatrix}4&4&2\\2&4&2\\2&2&2\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}={\begin{bmatrix}10\\8\\6\end{bmatrix}}.

Следовательно, ожидаемое количество подбрасываний монеты перед наблюдением за последовательностью (орел, решка, орел) составляет 10, запись для состояния представляет собой пустую строку.

Суммарная вероятность завершения игры в Змеи и Лестницы к N ходу.

Азартные игры [ править ]

Игры, полностью основанные на шансе, можно смоделировать с помощью увлекательной цепи Маркова. Классическим примером этого является древнеиндийская настольная игра « Змеи и лестницы» . График справа ^[3] отображает массу вероятности в одиночном поглощающем состоянии, который представляет собой последний квадрат, когда матрица перехода возводится в большую и большую степень. Чтобы определить ожидаемое количество ходов для завершения игры, вычислите вектор t, как описано выше, и исследуйте t _start , который составляет приблизительно 39,2.

Клиника инфекционных болезней [ править ]

Пример тестирования на инфекционные заболевания в продуктах крови или в медицинских клиниках часто преподается как пример поглощающей цепи Маркова. ^[4] Общественная модель Центров США по контролю и профилактике заболеваний (CDC), например, для ВИЧ и гепатита B, ^[5] иллюстрирует свойство, согласно которому поглощение цепей Маркова может приводить к обнаружению болезни, а не к потере обнаружения через другие средства.

В стандартной модели CDC цепь Маркова имеет пять состояний: состояние, в котором человек не инфицирован, затем состояние с инфицированным, но не обнаруживаемым вирусом, состояние с обнаруживаемым вирусом и поглощающие состояния выхода / потери из клиники, или быть обнаруженным (цель). Типичные скорости перехода между марковскими состояниями - это вероятность p за единицу времени заражения вирусом, w для скорости удаления периода окна (время до обнаружения вируса), q для количества выходов / потерь из системы и d для обнаружения, принимая типичную скорость, с которой система здравоохранения проводит тесты данного продукта крови или пациентов. $\lambda$

Классический пример модели скрининга на ВИЧ или вирус гепатита

Отсюда следует, что мы можем «пройтись по модели Маркова», чтобы определить общую вероятность обнаружения для человека, начинающего как необнаруженный, путем умножения вероятностей перехода к каждому следующему состоянию модели как:

${\frac {p}{(p+q)}}{\frac {w}{(w+q)}}{\frac {d}{(d+q)}}$ .

Последующее общее абсолютное количество ложноотрицательных тестов - основная проблема CDC - тогда будет представлять собой частоту тестов, умноженную на вероятность достижения зараженного, но неопределяемого состояния, умноженную на продолжительность пребывания в неопределяемом зараженном состоянии:

${\frac {p}{(p+q)}}{\frac {1}{(w+q)}}\lambda$ .

См. Также [ править ]

Дискретно-фазовое распределение
Поглощающий набор (случайные динамические системы)

Ссылки [ править ]

^ a b Гринстед, Чарльз М .; Снелл, Дж. Лори (июль 1997 г.). "Глава 11: Цепи Маркова" (PDF) . Введение в вероятность . Американское математическое общество. ISBN 978-0-8218-0749-1.
^ a b Кемени, Джон Г .; Снелл, Дж. Лори (июль 1976 г.) [1960]. "Глава 3: Поглощающие цепи Маркова". В Геринге, FW; Халмос, PR (ред.). Конечные цепи Маркова (2-е изд.). Нью-Йорк Берлин Гейдельберг Токио: Springer-Verlag. С. 224 . ISBN 978-0-387-90192-3.
^ На основе определения, найденного в SC Althoen; Л. Кинг; К. Шиллинг (март 1993 г.). «Как долго длится игра в змей и лестниц?». Математический вестник . The Mathematical Gazette, Vol. 77, № 478. 78 (478): 71–76. DOI : 10.2307 / 3619261 . JSTOR 3619261 .
^ результаты, поиск (1998-07-28). Цепи Маркова . Кембридж: Издательство Кембриджского университета. ISBN 9780521633963.
^ Сандерс, Джиллиан Д .; Анайя, Генри Д .; Аш, Стивен; Хоанг, Туен; Golden, Joya F .; Баюми, Ахмед М .; Оуэнс, Дуглас К. (июнь 2010 г.). «Экономическая эффективность стратегий улучшения тестирования на ВИЧ и получения результатов: экономический анализ рандомизированного контролируемого исследования» . Журнал общей внутренней медицины . 25 (6): 556–563. DOI : 10.1007 / s11606-010-1265-5 . ISSN 0884-8734 . PMC 2869414 . PMID 20204538 .

Внешние ссылки [ править ]

Демонстрационный проект Wolfram: поглощение цепей Маркова
Монополия как цепь Маркова

[Grin-1] Гринстед, Чарльз М .; Снелл, Дж. Лори (июль 1997 г.). "Глава 11: Цепи Маркова" (PDF) . Введение в вероятность . Американское математическое общество. ISBN 978-0-8218-0749-1.

[Kem-2] Кемени, Джон Г .; Снелл, Дж. Лори (июль 1976 г.) [1960]. "Глава 3: Поглощающие цепи Маркова". В Геринге, FW; Халмос, PR (ред.). Конечные цепи Маркова (2-е изд.). Нью-Йорк Берлин Гейдельберг Токио: Springer-Verlag. С. 224 . ISBN 978-0-387-90192-3.

[3] На основе определения, найденного в SC Althoen; Л. Кинг; К. Шиллинг (март 1993 г.). «Как долго длится игра в змей и лестниц?». Математический вестник . The Mathematical Gazette, Vol. 77, № 478. 78 (478): 71–76. DOI : 10.2307 / 3619261 . JSTOR 3619261 .

[4] результаты, поиск (1998-07-28). Цепи Маркова . Кембридж: Издательство Кембриджского университета. ISBN 9780521633963.

[5] Сандерс, Джиллиан Д .; Анайя, Генри Д .; Аш, Стивен; Хоанг, Туен; Golden, Joya F .; Баюми, Ахмед М .; Оуэнс, Дуглас К. (июнь 2010 г.). «Экономическая эффективность стратегий улучшения тестирования на ВИЧ и получения результатов: экономический анализ рандомизированного контролируемого исследования» . Журнал общей внутренней медицины . 25 (6): 556–563. DOI : 10.1007 / s11606-010-1265-5 . ISSN 0884-8734 . PMC 2869414 . PMID 20204538 .

[1]