Униформизация (теория вероятностей) - Uniformization (probability theory)

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

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

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

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

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

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

В матричной записи:

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

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

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

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

На практике это серии завершается после конечного числа условий.

Выполнение

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

Ограничения

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

внешняя ссылка

• Реализация Matlab

Примечания

1. Стюарт, Уильям Дж. (2009). Вероятность, цепи Маркова, очереди и моделирование: математические основы моделирования производительности. Princeton University Press. п.361. ISBN  0-691-14062-6.
2. Ибе, Оливер С. (2009). Марковские процессы для стохастического моделирования. Академическая пресса. п.98. ISBN  0-12-374451-2.
3. Gross, D .; Миллер, Д. Р. (1984). «Метод рандомизации как инструмент моделирования и процедура решения переходных марковских процессов». Исследование операций. 32 (2): 343–361. Дои:10.1287 / opre.32.2.343.
4. Грассманн, В. К. (1977). «Переходные решения в марковских системах массового обслуживания». Компьютеры и исследования операций. 4: 47–00. Дои:10.1016/0305-0548(77)90007-7.
5. Грассманн, В. К. (1977). «Переходные решения в марковских очередях». Европейский журнал операционных исследований. 1 (6): 396–402. Дои:10.1016/0377-2217(77)90049-2.
6. Cassandras, Christos G .; Лафортюн, Стефан (2008). Введение в дискретные системы событий. Springer. ISBN  0-387-33332-0.
7. Росс, Шелдон М. (2007). Введение в вероятностные модели. Академическая пресса. ISBN  0-12-598062-0.
8. Reibman, A .; Триведи, К. (1988). «Численный переходный анализ марковских моделей» (PDF). Компьютеры и исследования операций. 15: 19. Дои:10.1016/0305-0548(88)90026-3.
9. Dingle, N .; Харрисон, П.Г.; Knottenbelt, W. J. (2004). «Униформизация и разбиение гиперграфа для распределенного вычисления плотностей времени отклика в очень больших марковских моделях». Журнал параллельных и распределенных вычислений. 64 (8): 908–920. Дои:10.1016 / j.jpdc.2004.03.017. HDL:10044/1/5771.