Униформа (теория вероятности)

В вероятности теории метод униформизации (также известный как метод Дженсена ^{[ 1 ]} или метод рандомизации ^{[ 2 ]})-это метод вычисления переходных решений цепочек марковских цепочек конечного состояния путем аппроксимирования процесса с помощью цепочки марковского дискретного времени . ^{[ 2 ]} Оригинальная цепь масштабируется по самой быстрой скорости перехода γ , так что переходы происходят с одинаковой скоростью в каждом состоянии, отсюда и название. Метод прост в программировании и эффективно вычисляет приближение к переходному распределению в один момент времени (около нуля). ^{[ 1 ]} Метод был впервые введен Уинфридом Грассманном в 1977 году. ^{[ 3 ]}^{[ 4 ]}^{[ 5 ]}

Метод Описание

периода Для цепочки марковского марковского с матрицей скорости перехода Q цепочка с единообразным временем Маркова имеет матрицу вероятности перехода $P:=(p_{ij})_{i,j}$ , который определяется ^{[ 1 ]}^{[ 6 ]}^{[ 7 ]}

p_{ij}={\begin{cases}q_{ij}/\gamma &{\text{ if }}i\neq j\\1-\sum _{k\neq i}q_{ik}/\gamma &{\text{ if }}i=j\end{cases}}

с γ , параметром равномерной скорости, выбранным таким, что

\gamma \geq \max _{i}|q_{ii}|.

В матричной нотации:

P=I+{\frac {1}{\gamma }}Q.

Для начального распределения $π$ (0) распределение в момент времени t , $π$ ( t ) вычисляется ^{[ 1 ]}

\pi (t)=\sum _{n=0}^{\infty }\pi (0)P^{n}{\frac {(\gamma t)^{n}}{n!}}e^{-\gamma t}.

Это представление показывает, что цепь марковского непрерывного времени может быть описана дискретной цепью Маркова с переходной матрицей P, как определено выше, где прыжки происходят в соответствии с процессом Пуассона с интенсивностью γT .

На практике эта серия прекращается после конечных условий.

Выполнение

Псевдокод для алгоритма включен в Приложение A из статьи Рейбмана и Триведи 1988 года. ^{[ 8 ]} Используя параллельную версию алгоритма, цепочки с государственными пространствами более 10 ⁷ были проанализированы. ^{[ 9 ]}

Ограничения

Рейбман и Триведи утверждают, что «униформизация - это метод выбора для типичных проблем», хотя они отмечают, что для жестких проблем некоторые индивидуальные алгоритмы, вероятно, будут работать лучше. ^{[ 8 ]}

Внешние ссылки

Реализация MATLAB

Примечания

^ Jump up to: ^а ^{беременный} ^в ^{дюймовый} Стюарт, Уильям Дж. (2009). Вероятность, цепочки Марков, очереди и моделирование: математическая основа моделирования производительности . ПРИЗНАЯ УНИВЕРСИТЕТА ПРИСЕТА . п. 361 . ISBN 0-691-14062-6 .
^ Jump up to: ^а ^{беременный} Ибе, Оливер С. (2009). Марковские процессы для стохастического моделирования . Академическая пресса . п. 98 ISBN 0-12-374451-2 .
^ Gross, D.; Миллер, DR (1984). «Метод рандомизации как инструмент моделирования и процедура решения для переходных процессов Маркова». Операционные исследования . 32 (2): 343–361. doi : 10.1287/opre.32.2.343 .
^ Grassmann, WK (1977). «Переходные решения в системах очереди Маркова» ». Компьютеры и операционные исследования . 4 : 47–00. doi : 10.1016/0305-0548 (77) 90007-7 .
^ Grassmann, WK (1977). «Переходные решения в марковских очередях». Европейский журнал оперативных исследований . 1 (6): 396–402. doi : 10.1016/0377-2217 (77) 90049-2 .
^ Cassandras, Christos G.; LaFortune, Stéphane (2008). Введение в дискретные системы событий . Спрингер. ISBN 0-387-33332-0 .
^ Росс, Шелдон М. (2007). Введение в модели вероятности . Академическая пресса. ISBN 0-12-598062-0 .
^ Jump up to: ^а ^{беременный} Рейбман, А.; Триведи К. (1988). «Численный переходный анализ моделей Маркова» (PDF) . Компьютеры и операционные исследования . 15 : 19. doi : 10.1016/0305-0548 (88) 90026-3 .
^ Дингл, Н.; Харрисон, стр ; Nottenbelt, WJ (2004). «Работа и распределение гиперграфа для распределенного расчета плотностей времени отклика в очень больших моделях Маркова» . Журнал параллельных и распределенных вычислений . 64 (8): 908–920. doi : 10.1016/j.jpdc.2004.03.017 . HDL : 10044/1/5771 .

[stewart-1] Jump up to: ^а ^{беременный} ^в ^{дюймовый} Стюарт, Уильям Дж. (2009). Вероятность, цепочки Марков, очереди и моделирование: математическая основа моделирования производительности . ПРИЗНАЯ УНИВЕРСИТЕТА ПРИСЕТА . п. 361 . ISBN 0-691-14062-6 .

[ibe-2] Jump up to: ^а ^{беременный} Ибе, Оливер С. (2009). Марковские процессы для стохастического моделирования . Академическая пресса . п. 98 ISBN 0-12-374451-2 .

[3] Gross, D.; Миллер, DR (1984). «Метод рандомизации как инструмент моделирования и процедура решения для переходных процессов Маркова». Операционные исследования . 32 (2): 343–361. doi : 10.1287/opre.32.2.343 .

[4] Grassmann, WK (1977). «Переходные решения в системах очереди Маркова» ». Компьютеры и операционные исследования . 4 : 47–00. doi : 10.1016/0305-0548 (77) 90007-7 .

[5] Grassmann, WK (1977). «Переходные решения в марковских очередях». Европейский журнал оперативных исследований . 1 (6): 396–402. doi : 10.1016/0377-2217 (77) 90049-2 .

[cass-6] Cassandras, Christos G.; LaFortune, Stéphane (2008). Введение в дискретные системы событий . Спрингер. ISBN 0-387-33332-0 .

[ross-7] Росс, Шелдон М. (2007). Введение в модели вероятности . Академическая пресса. ISBN 0-12-598062-0 .

[reibman-8] Jump up to: ^а ^{беременный} Рейбман, А.; Триведи К. (1988). «Численный переходный анализ моделей Маркова» (PDF) . Компьютеры и операционные исследования . 15 : 19. doi : 10.1016/0305-0548 (88) 90026-3 .

[9] Дингл, Н.; Харрисон, стр ; Nottenbelt, WJ (2004). «Работа и распределение гиперграфа для распределенного расчета плотностей времени отклика в очень больших моделях Маркова» . Журнал параллельных и распределенных вычислений . 64 (8): 908–920. doi : 10.1016/j.jpdc.2004.03.017 . HDL : 10044/1/5771 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]