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

В вероятностей теории укрупняемость — это метод уменьшения размера пространства состояний некоторых цепей Маркова с непрерывным временем , впервые опубликованный Кемени и Снеллом. ^[1]

Определение

Предположим, что полное пространство состояний цепи Маркова разделено на непересекающиеся подмножества состояний, где эти подмножества обозначаются t _i . Это образует раздел $\scriptstyle {T=\{t_{1},t_{2},\ldots \}}$ штатов. И пространство состояний, и набор подмножеств могут быть либо конечными, либо счетно бесконечными.Цепь Маркова с непрерывным временем $\{X_{i}\}$ является суммируемым относительно разбиения T тогда и только тогда, когда для любых подмножеств t _i и t _j в разбиении и для любых состояний n,n' в подмножестве t _i ,

\sum _{m\in t_{j}}q(n,m)=\sum _{m\in t_{j}}q(n',m),

где q ( i,j ) — скорость перехода из состояния i в состояние j . ^[2]

Аналогично, для стохастической матрицы P P n является округляемой матрицей на разбиении T тогда и только тогда, когда для любых подмножеств t _i и t _j в разбиении и для любых состояний ,n' в подмножестве t _i ,

\sum _{m\in t_{j}}p(n,m)=\sum _{m\in t_{j}}p(n',m),

где p ( i,j ) — вероятность перехода из состояния i в состояние j . ^[3]

Пример

Рассмотрим матрицу

P={\begin{pmatrix}{\frac {1}{2}}&{\frac {3}{8}}&{\frac {1}{16}}&{\frac {1}{16}}\\{\frac {7}{16}}&{\frac {7}{16}}&0&{\frac {1}{8}}\\{\frac {1}{16}}&0&{\frac {1}{2}}&{\frac {7}{16}}\\0&{\frac {1}{16}}&{\frac {3}{8}}&{\frac {9}{16}}\end{pmatrix}}

и заметьте, что на разбиении t = {(1,2),(3,4)} оно является комкуемым, поэтому мы пишем

P_{t}={\begin{pmatrix}{\frac {7}{8}}&{\frac {1}{8}}\\{\frac {1}{16}}&{\frac {15}{16}}\end{pmatrix}}

и назовем P _t сосредоточенной матрицей P на t .

Последовательно кусковые процессы

В 2012 году Катехакис и Смит открыли процессы последовательного объединения, для которых стационарные вероятности могут быть получены путем последовательного вычисления стационарных вероятностей удачно построенной последовательности цепей Маркова. Каждая из последних цепочек имеет (обычно намного) меньшее пространство состояний, и это приводит к значительным улучшениям в вычислениях. Эти результаты связаны с надежностью многих приложений, моделями и проблемами массового обслуживания. ^[4]

Квази-комкаемость

Франческинис и Мунц ввели квазикомкуемость - свойство, при котором небольшое изменение в матрице скоростей делает цепь комкующейся. ^[5]

См. также

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

Ссылки

^ Кемени, Джон Г .; Снелл, Дж. Лори (июль 1976 г.) [1960]. Геринг, ФРВ; Халмош, PR (ред.). Конечные цепи Маркова (второе изд.). Нью-Йорк Берлин Гейдельберг Токио: Springer-Verlag. п. 124. ИСБН 978-0-387-90192-3 .
^ Джейн Хиллстон , Композиционное марковское моделирование с использованием алгебры процессов в материалах второго международного семинара по численному решению цепей Маркова: вычисления с цепями Маркова, Роли, Северная Каролина, январь 1995. Kluwer Academic Press
^ Питер Г. Харрисон и Нареш М. Патель, Моделирование производительности сетей связи и компьютерных архитектур, Аддисон-Уэсли, 1992 г.
^ Катехакис, Миннесота ; Смит, Л.К. (2012). «Процедура последовательного объединения для класса цепей Маркова». Вероятность в инженерных и информационных науках . 26 (4): 483. doi : 10.1017/S0269964812000150 .
^ Франческинис, Г.; Мунц, Ричард Р. (1993). «Оценки для квазисъедающихся цепей Маркова». Оценка производительности . 20 (1–3). Эльзевир Б.В.: 223–243. дои : 10.1016/0166-5316(94)90015-9 .

[1] Кемени, Джон Г .; Снелл, Дж. Лори (июль 1976 г.) [1960]. Геринг, ФРВ; Халмош, PR (ред.). Конечные цепи Маркова (второе изд.). Нью-Йорк Берлин Гейдельберг Токио: Springer-Verlag. п. 124. ИСБН 978-0-387-90192-3 .

[2] Джейн Хиллстон , Композиционное марковское моделирование с использованием алгебры процессов в материалах второго международного семинара по численному решению цепей Маркова: вычисления с цепями Маркова, Роли, Северная Каролина, январь 1995. Kluwer Academic Press

[3] Питер Г. Харрисон и Нареш М. Патель, Моделирование производительности сетей связи и компьютерных архитектур, Аддисон-Уэсли, 1992 г.

[mnksmit-4] Катехакис, Миннесота ; Смит, Л.К. (2012). «Процедура последовательного объединения для класса цепей Маркова». Вероятность в инженерных и информационных науках . 26 (4): 483. doi : 10.1017/S0269964812000150 .

[fra-5] Франческинис, Г.; Мунц, Ричард Р. (1993). «Оценки для квазисъедающихся цепей Маркова». Оценка производительности . 20 (1–3). Эльзевир Б.В.: 223–243. дои : 10.1016/0166-5316(94)90015-9 .

[1]

[2]

[3]

[4]

[5]