Почти полностью разложимая цепь Маркова

В теории вероятностей — почти полностью разложимая (NCD) цепь Маркова это цепь Маркова , в которой пространство состояний может быть разделено таким образом, что движение внутри раздела происходит гораздо чаще, чем движение между разделами. ^[1] Существуют особенно эффективные алгоритмы для вычисления стационарного распределения цепей Маркова с этим свойством. ^[2]

Определение

Андо и Фишер определяют полностью разложимую матрицу как матрицу, в которой «идентичная перестановка строк и столбцов оставляет набор квадратных подматриц на главной диагонали и нули повсюду». Почти полностью разложимая матрица — это матрица, в которой идентичная перестановка строк и столбцов оставляет набор квадратных подматриц на главной диагонали и небольшие ненулевые значения во всех остальных местах. ^[3]^[4]

Пример

Цепь Маркова с матрицей перехода

P={\begin{pmatrix}{\frac {1}{2}}&{\frac {1}{2}}&0&0\\{\frac {1}{2}}&{\frac {1}{2}}&0&0\\0&0&{\frac {1}{2}}&{\frac {1}{2}}\\0&0&{\frac {1}{2}}&{\frac {1}{2}}\\\end{pmatrix}}+\epsilon {\begin{pmatrix}-{\frac {1}{2}}&0&{\frac {1}{2}}&0\\0&-{\frac {1}{2}}&0&{\frac {1}{2}}\\{\frac {1}{2}}&0&-{\frac {1}{2}}&0\\0&{\frac {1}{2}}&0&-{\frac {1}{2}}\\\end{pmatrix}}

почти полностью разложимо, если ε мало (скажем, 0,1). ^[5]

Алгоритмы стационарного распределения

Разработаны специальные итерационные алгоритмы для цепей Маркова НИЗ. ^[2] хотя многоуровневый алгоритм, алгоритм общего назначения, ^[6] Экспериментально было показано, что он конкурентоспособен, а в некоторых случаях значительно быстрее. ^[7]

См. также

комковатость

Ссылки

^ Контовасилис, КП; Митроу, Нью-Мексико (1995). «Марково-модулированный трафик с почти полными характеристиками разложимости и связанными с ним гибкими моделями массового обслуживания». Достижения в области прикладной теории вероятности . 27 (4): 1144–1185. дои : 10.2307/1427937 . JSTOR 1427937 . S2CID 123810850 .
^ Jump up to: ^а ^б Кури, младший; Макаллистер, DF; Стюарт, WJ (1984). «Итерационные методы вычисления стационарных распределений почти полностью разложимых цепей Маркова». SIAM Journal по алгебраическим и дискретным методам . 5 (2): 164–186. дои : 10.1137/0605019 .
^ Андо, А .; Фишер, FM (1963). «Почти разложимость, разделение и агрегирование, а также актуальность дискуссий о стабильности». Международное экономическое обозрение . 4 (1): 53–67. дои : 10.2307/2525455 . JSTOR 2525455 .
^ Куртуа, П.Дж. (1975). «Анализ ошибок в почти полностью разложимых стохастических системах». Эконометрика . 43 (4): 691–709. дои : 10.2307/1913078 . JSTOR 1913078 .
^ Пример 1.1 из Инь, Джордж; Чжан, Цин (2005). Цепи Маркова с дискретным временем: двухвременные методы и приложения . Спрингер. п. 8 . ISBN 978-0-387-21948-6 .
^ Хортон, Г.; Лейтенеггер, ST (1994). «Многоуровневый алгоритм решения установившихся цепей Маркова». Обзор оценки производительности ACM SIGMETRICS . 22 : 191–200. CiteSeerX 10.1.1.44.4560 . дои : 10.1145/183019.183040 . S2CID 1110664 .
^ Лейтенеггер, Скотт Т.; Хортон, Грэм (июнь 1994 г.). О полезности многоуровневого алгоритма для решения почти полностью разложимых цепей Маркова (Отчет ICASE № 94-44) (PDF) (Технический отчет). НАСА. Отчет подрядчика 194929. Архивировано из оригинала 8 апреля 2013 г. Мы представляем экспериментальные результаты, показывающие, что многоуровневый алгоритм общего назначения конкурентоспособен и может быть значительно быстрее, чем алгоритм KMS специального назначения при использовании алгоритма Гаусса-Зейделя и исключения Гаусса. используются для решения отдельных блоков. Цепи Маркова, Многоуровневые, Численное решение.

[1] Контовасилис, КП; Митроу, Нью-Мексико (1995). «Марково-модулированный трафик с почти полными характеристиками разложимости и связанными с ним гибкими моделями массового обслуживания». Достижения в области прикладной теории вероятности . 27 (4): 1144–1185. дои : 10.2307/1427937 . JSTOR 1427937 . S2CID 123810850 .

[kms-2] Jump up to: ^а ^б Кури, младший; Макаллистер, DF; Стюарт, WJ (1984). «Итерационные методы вычисления стационарных распределений почти полностью разложимых цепей Маркова». SIAM Journal по алгебраическим и дискретным методам . 5 (2): 164–186. дои : 10.1137/0605019 .

[3] Андо, А .; Фишер, FM (1963). «Почти разложимость, разделение и агрегирование, а также актуальность дискуссий о стабильности». Международное экономическое обозрение . 4 (1): 53–67. дои : 10.2307/2525455 . JSTOR 2525455 .

[4] Куртуа, П.Дж. (1975). «Анализ ошибок в почти полностью разложимых стохастических системах». Эконометрика . 43 (4): 691–709. дои : 10.2307/1913078 . JSTOR 1913078 .

[5] Пример 1.1 из Инь, Джордж; Чжан, Цин (2005). Цепи Маркова с дискретным временем: двухвременные методы и приложения . Спрингер. п. 8 . ISBN 978-0-387-21948-6 .

[6] Хортон, Г.; Лейтенеггер, ST (1994). «Многоуровневый алгоритм решения установившихся цепей Маркова». Обзор оценки производительности ACM SIGMETRICS . 22 : 191–200. CiteSeerX 10.1.1.44.4560 . дои : 10.1145/183019.183040 . S2CID 1110664 .

[7] Лейтенеггер, Скотт Т.; Хортон, Грэм (июнь 1994 г.). О полезности многоуровневого алгоритма для решения почти полностью разложимых цепей Маркова (Отчет ICASE № 94-44) (PDF) (Технический отчет). НАСА. Отчет подрядчика 194929. Архивировано из оригинала 8 апреля 2013 г. Мы представляем экспериментальные результаты, показывающие, что многоуровневый алгоритм общего назначения конкурентоспособен и может быть значительно быстрее, чем алгоритм KMS специального назначения при использовании алгоритма Гаусса-Зейделя и исключения Гаусса. используются для решения отдельных блоков. Цепи Маркова, Многоуровневые, Численное решение.

[1]

[2]

[3]

[4]

[5]

[6]

[7]