Цепь Маркова с непрерывным временем - Continuous-time Markov chain

Эта статья посвящена математическим свойствам цепей Маркова с непрерывным временем. Для общей области исследования см. Цепь Маркова.

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

Пример CTMC с тремя состояниями ${\displaystyle \{0,1,2\}}$ выглядит следующим образом: процесс выполняет переход по истечении времени, заданного параметром Время выдержки- экспоненциальная случайная величина ${\displaystyle E_{i}}$, куда я его текущее состояние. Каждая случайная величина независима и такая, что ${\displaystyle E_{0}\sim {\text{Exp}}(6)}$, ${\displaystyle E_{1}\sim {\text{Exp}}(12)}$ и ${\displaystyle E_{2}\sim {\text{Exp}}(18)}$. Когда необходимо произвести переход, процесс движется в соответствии с прыжковая цепь, а цепь Маркова с дискретным временем со стохастической матрицей:

${\displaystyle {\begin{bmatrix}0&{\frac {1}{2}}&{\frac {1}{2}}\\{\frac {1}{3}}&0&{\frac {2}{3}}\\{\frac {5}{6}}&{\frac {1}{6}}&0\end{bmatrix}}.}$

Эквивалентно теорией конкурирующие экспоненты, этот CTMC меняет состояние из состояния я согласно минимуму двух независимых случайных величин, таких что ${\displaystyle E_{i,j}\sim {\text{Exp}}(q_{i,j})}$ за ${\displaystyle i\neq j}$ где параметры задаются Q-матрица ${\displaystyle Q=(q_{i,j})}$

${\displaystyle {\begin{bmatrix}-6&3&3\\4&-12&8\\15&3&-18\end{bmatrix}}.}$

Каждое недиагональное значение может быть вычислено как произведение времени удержания исходного состояния на вероятность перехода в данное состояние из цепочки скачков. Значения диагонали выбираются так, чтобы сумма каждой строки равнялась 0.

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

Определение

Цепь Маркова с непрерывным временем (Икс_т)_т ≥ 0 определяется:^[1]

• конечное или счетное пространство состояний S;
• а матрица скорости перехода Q с размерами, равными S; и
• начальное состояние ${\displaystyle k}$ такой, что ${\displaystyle X_{0}=k}$, или распределение вероятностей для этого первого состояния.

За я ≠ j, элементы q_ij неотрицательны и описывают скорость перехода процесса из состояния я заявить j. Элементы q_ii могут быть выбраны равными нулю, но для математического удобства принято выбирать их так, чтобы каждая строка ${\displaystyle Q}$ суммы к нулю, то есть:

${\displaystyle q_{ii}=-\sum _{k\neq i}q_{ik}.}$

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

Есть три других определения процесса, эквивалентных приведенному выше.^[2]

Определение вероятности перехода

Другой распространенный способ определения цепей Маркова с непрерывным временем состоит в том, чтобы вместо матрицы скорости перехода ${\displaystyle Q}$, используйте следующее:^[1]

• ${\displaystyle v_{i}}$, за ${\displaystyle i\in S}$, представляющий скорость распада (экспоненциального распределения), при котором система остается в состоянии ${\displaystyle i}$ как только он входит в него; и
• ${\displaystyle m_{ij}}$, за ${\displaystyle i,j\in S}$, представляющая вероятность того, что система перейдет в состояние ${\displaystyle j}$, учитывая, что в настоящее время он покидает состояние ${\displaystyle i}$.

Естественно, ${\displaystyle m_{ii}}$ должен быть нулевым для всех ${\displaystyle i}$.

Ценности ${\displaystyle v_{i}}$ и ${\displaystyle m_{ij}}$ тесно связаны с матрицей скорости перехода ${\displaystyle Q}$, по формулам:

${\displaystyle v_{i}=\sum _{k\neq i}q_{ik}=-q_{ii},{\text{ for all }}i,}$

${\displaystyle m_{ij}={\frac {q_{ij}}{\sum _{k\neq i}q_{ik}}},{\text{ for all }}i\neq j.}$

Рассмотрим упорядоченную последовательность моментов времени ${\displaystyle t_{0}<t_{1}<\dots <t_{n}}$ и состояния, записанные в это время ${\displaystyle i_{0},i_{1},\dots ,i_{n}}$, то считается, что:

${\displaystyle \Pr(X_{t_{n+1}}=i_{n+1}\mid X_{t_{0}}=i_{0},X_{t_{1}}=i_{1},\ldots ,X_{t_{n}}=i_{n})=\Pr(X_{t_{n+1}}=i_{n+1}\mid X_{t_{n}}=i_{n})=p_{i_{n}i_{n+1}}(t_{n+1}-t_{n})}$^{[сомнительный ]}

где п_ij это решение прямое уравнение (а дифференциальное уравнение первого порядка ):

${\displaystyle P'(t)=P(t)Q}$

с начальным условием P (0), являющимся единичная матрица.

Бесконечно малое определение

Марковская цепь с непрерывным временем характеризуется скоростями переходов, производными по времени вероятностей переходов между состояниями i и j.

Позволять ${\displaystyle X_{t}}$ случайная величина, описывающая состояние процесса во время т, и предположим, что процесс находится в состоянии я вовремя т.По определению цепи Маркова с непрерывным временем ${\displaystyle X_{t+h}=j}$ не зависит от значений до момента ${\displaystyle t}$; то есть не зависит от ${\displaystyle \left(X_{s}:s<t\right)}$. Имея это в виду, для всех ${\displaystyle i,j}$, для всех ${\displaystyle t}$ и при малых значениях ${\displaystyle h}$, имеет место следующее:

${\displaystyle \Pr(X(t+h)=j\mid X(t)=i)=\delta _{ij}+q_{ij}h+o(h)}$,

куда ${\displaystyle \delta _{ij}}$это Дельта Кронекера и маленькая нотация был нанят.

Приведенное выше уравнение показывает, что ${\displaystyle q_{ij}}$ можно рассматривать как измерение скорости перехода от ${\displaystyle i}$ к ${\displaystyle j}$ происходит для ${\displaystyle i\neq j}$, и как быстро переход от ${\displaystyle i}$ происходит для ${\displaystyle i=j}$.

Прыжковая цепь / определение времени удержания

Определите цепь Маркова с дискретным временем Y_п описать пскачок процесса и переменных S₁, S₂, S₃, ... для описания времени выдержки в каждом из состояний, где S_я следует экспоненциальному распределению с параметром скорости -q_YяYя.

Характеристики

Общение на занятиях

Сообщающиеся классы, быстротечность, повторение, а также положительное и нулевое повторение определяются так же, как и для цепи Маркова с дискретным временем.

Переходное поведение

Напишите P (т) для матрицы с элементами п_ij = P (Икс_т = j | Икс₀ = я). Тогда матрица P (т) удовлетворяет прямому уравнению, a дифференциальное уравнение первого порядка

${\displaystyle P'(t)=P(t)Q}$

где штрих означает дифференцирование по т. Решение этого уравнения дается матрица экспонента

${\displaystyle P(t)=e^{tQ}}$

В простом случае, таком как CTMC в пространстве состояний {1,2}. Генерал Q Матрица для такого процесса представляет собой следующую матрицу 2 × 2 с α,β > 0

${\displaystyle Q={\begin{pmatrix}-\alpha &\alpha \\\beta &-\beta \end{pmatrix}}.}$

Приведенное выше соотношение для прямой матрицы может быть решено явно в этом случае, чтобы дать

${\displaystyle P(t)={\begin{pmatrix}{\frac {\beta }{\alpha +\beta }}+{\frac {\alpha }{\alpha +\beta }}e^{-(\alpha +\beta )t}&{\frac {\alpha }{\alpha +\beta }}-{\frac {\alpha }{\alpha +\beta }}e^{-(\alpha +\beta )t}\\{\frac {\beta }{\alpha +\beta }}-{\frac {\beta }{\alpha +\beta }}e^{-(\alpha +\beta )t}&{\frac {\alpha }{\alpha +\beta }}+{\frac {\beta }{\alpha +\beta }}e^{-(\alpha +\beta )t}\end{pmatrix}}}$

Однако прямые решения для больших матриц сложно вычислить. Дело в том, что Q является генератором для полугруппа матриц

${\displaystyle P(t+s)=e^{(t+s)Q}=e^{tQ}e^{sQ}=P(t)P(s)}$

используется.

Стационарное распределение

Стационарное распределение для неприводимого рекуррентного CTMC - это распределение вероятностей, к которому процесс сходится для больших значений т. Заметим, что для процесса с двумя состояниями, рассмотренного ранее с P (т) предоставлено

${\displaystyle P(t)={\begin{pmatrix}{\frac {\beta }{\alpha +\beta }}+{\frac {\alpha }{\alpha +\beta }}e^{-(\alpha +\beta )t}&{\frac {\alpha }{\alpha +\beta }}-{\frac {\alpha }{\alpha +\beta }}e^{-(\alpha +\beta )t}\\{\frac {\beta }{\alpha +\beta }}-{\frac {\beta }{\alpha +\beta }}e^{-(\alpha +\beta )t}&{\frac {\alpha }{\alpha +\beta }}+{\frac {\beta }{\alpha +\beta }}e^{-(\alpha +\beta )t}\end{pmatrix}}}$

в качестве т → ∞ распределение стремится к

${\displaystyle P_{\pi }={\begin{pmatrix}{\frac {\beta }{\alpha +\beta }}&{\frac {\alpha }{\alpha +\beta }}\\{\frac {\beta }{\alpha +\beta }}&{\frac {\alpha }{\alpha +\beta }}\end{pmatrix}}}$

Обратите внимание, что каждая строка имеет одинаковое распределение, так как это не зависит от начального состояния. Вектор-строка π можно найти, решив^[3]

${\displaystyle \pi Q=0.}$

с дополнительным ограничением, что

${\displaystyle \sum _{i\in S}\pi _{i}=1.}$

Пример 1

Направленное графическое представление цепи Маркова с непрерывным временем, описывающей состояние финансовых рынков (примечание: числа выдуманы).

Изображение справа описывает цепь Маркова в непрерывном времени с пространством состояний {бычий рынок, медвежий рынок, застойный рынок} и матрица скорости перехода

${\displaystyle Q={\begin{pmatrix}-0.025&0.02&0.005\\0.3&-0.5&0.2\\0.02&0.4&-0.42\end{pmatrix}}.}$

Стационарное распределение этой цепочки можно найти, решив ${\displaystyle \pi Q=0}$, при условии, что сумма элементов должна быть равна 1, чтобы получить

${\displaystyle \pi ={\begin{pmatrix}0.885&0.071&0.044\end{pmatrix}}.}$

Пример 2

Граф переходов с вероятностями переходов, примерный для состояний 1, 5, 6 и 8. Между состояниями 2 и 8 существует двунаправленный секретный переход.

Изображение справа описывает моделирование цепи Маркова в дискретном времени. Pac-Man с пространством состояний {1,2,3,4,5,6,7,8,9}. Игрок управляет Пакманом через лабиринт, поедая пак-точки. Тем временем за ним охотятся призраки. Для удобства лабиринт представляет собой небольшую сетку 3x3, а монстры беспорядочно перемещаются в горизонтальном и вертикальном направлениях. Секретный проход между состояниями 2 и 8 можно использовать в обоих направлениях. Записи с нулевой вероятностью удаляются в следующей матрице перехода:

${\displaystyle Q={\begin{pmatrix}&{\frac {1}{2}}&&{\frac {1}{2}}\\{\frac {1}{4}}&&{\frac {1}{4}}&&{\frac {1}{4}}&&&{\frac {1}{4}}\\&{\frac {1}{2}}&&&&{\frac {1}{2}}\\{\frac {1}{3}}&&&&{\frac {1}{3}}&&{\frac {1}{3}}\\&{\frac {1}{4}}&&{\frac {1}{4}}&&{\frac {1}{4}}&&{\frac {1}{4}}\\&&{\frac {1}{3}}&&{\frac {1}{3}}&&&&{\frac {1}{3}}\\&&&{\frac {1}{2}}&&&&{\frac {1}{2}}\\&{\frac {1}{4}}&&&{\frac {1}{4}}&&{\frac {1}{4}}&&{\frac {1}{4}}\\&&&&&{\frac {1}{2}}&&{\frac {1}{2}}\end{pmatrix}}}$

Эта цепь Маркова неприводима, потому что призраки могут перелететь из любого состояния в любое состояние за конечный промежуток времени. Из-за секретного прохода цепь Маркова также апериодична, потому что монстры могут переходить из любого состояния в любое состояние как при четном, так и при нечетном количестве переходов между состояниями. Следовательно, существует уникальное стационарное распределение, которое может быть найдено путем решения ${\displaystyle \pi Q=0}$, при условии, что сумма элементов должна быть равна 1. Решение этого линейного уравнения с учетом ограничения имеет вид ${\displaystyle \pi =(7.7,15.4,7.7,11.5,15.4,11.5,7.7,15.4,7.7)\%.}$Центральное государство и пограничные состояния 2 и 8 соседнего секретного прохода посещаются чаще всего, а угловые состояния посещаются меньше всего.

Обратное время

Для CTMC Икс_т, обратный во времени процесс определяется как ${\displaystyle {\hat {X}}_{t}=X_{T-t}}$. К Лемма Келли этот процесс имеет такое же стационарное распределение, что и прямой процесс.

Цепочка называется обратимой, если обратный процесс такой же, как и прямой. Критерий Колмогорова утверждает, что необходимое и достаточное условие для того, чтобы процесс был обратимым, состоит в том, что произведение скоростей перехода по замкнутому контуру должно быть одинаковым в обоих направлениях.

Встроенная цепь Маркова

Один из способов найти стационарное распределение вероятностей, π, из эргодический цепь Маркова с непрерывным временем, Q, сначала найдя его встроенная цепь Маркова (EMC). Строго говоря, EMC - это обычная цепь Маркова с дискретным временем, которую иногда называют процесс прыжка. Каждый элемент матрицы вероятностей одношагового перехода EMC, S, обозначается s_ij, и представляет условная возможность перехода из состояния я в состояние j. Эти условные вероятности могут быть найдены

${\displaystyle s_{ij}={\begin{cases}{\frac {q_{ij}}{\sum _{k\neq i}q_{ik}}}&{\text{if }}i\neq j\\0&{\text{otherwise}}.\end{cases}}}$

Из этого, S можно записать как

${\displaystyle S=I-\left(\operatorname {diag} (Q)\right)^{-1}Q}$

куда я это единичная матрица и диаг (Q) это диагональная матрица формируется путем выбора главная диагональ из матрицы Q и установка всех остальных элементов на ноль.

Чтобы найти вектор стационарного распределения вероятностей, мы должны найти ${\displaystyle \varphi }$ такой, что

${\displaystyle \varphi S=\varphi ,}$

с ${\displaystyle \varphi }$ вектор-строка, так что все элементы в ${\displaystyle \varphi }$ больше 0 и ${\displaystyle \|\varphi \|_{1}}$ = 1. Отсюда π можно найти как

${\displaystyle \pi ={-\varphi (\operatorname {diag} (Q))^{-1} \over \left\|\varphi (\operatorname {diag} (Q))^{-1}\right\|_{1}}.}$

(S может быть периодическим, даже если Q не является. Один раз π найден, его необходимо нормализовать до единичный вектор.)

Другой процесс с дискретным временем, который может быть получен из цепи Маркова с непрерывным временем, - это δ-скелет - цепь Маркова (с дискретным временем), образованная путем наблюдения Икс(т) с интервалом в δ единиц времени. Случайные величины Икс(0), Икс(δ),Икс(2δ), ... задают последовательность состояний, которые посещает δ-скелет.

Смотрите также

• Уравнения Колмогорова (процесс марковского скачка)

Примечания

1. Росс, С. (2010). Введение в вероятностные модели (10-е изд.). Эльзевир. ISBN  978-0-12-375686-2.
2. Норрис, Дж. Р. (1997). «Цепи Маркова с непрерывным временем I». Цепи Маркова. С. 60–107. Дои:10.1017 / CBO9780511810633.004. ISBN  9780511810633.
3. Норрис, Дж. Р. (1997). «Цепи Маркова с непрерывным временем II». Цепи Маркова. С. 108–127. Дои:10.1017 / CBO9780511810633.005. ISBN  9780511810633.

Рекомендации

• Марков А.А. (1971). «Распространение предельных теорем теории вероятностей на сумму переменных, соединенных в цепочку». перепечатано в Приложении B к: R. Howard. Динамические вероятностные системы, том 1: Марковские цепи. Джон Уайли и сыновья.
• Марков, А.А. (2006). Перевод Линка, Дэвид. "Пример статистического исследования текста Евгения Онегина о соединении образцов в цепочки". Наука в контексте. 19 (4): 591–600. Дои:10.1017 / s0269889706001074.
• Лео Брейман (1992) [1968] Вероятность. Оригинальное издание, опубликованное Эддисон-Уэсли; перепечатано Общество промышленной и прикладной математики ISBN  0-89871-296-3. (См. Главу 7)
• Дж. Л. Дуб (1953) Стохастические процессы. Нью-Йорк: Джон Уайли и сыновья ISBN  0-471-52369-0.
• С. П. Мейн и Р. Л. Твиди (1993) Марковские цепи и стохастическая устойчивость. Лондон: Springer-Verlag ISBN  0-387-19832-6. онлайн: MCSS . Выйдет второе издание, Cambridge University Press, 2009.
• Кемени, Джон Дж .; Хэзлтон Миркил; Дж. Лори Снелл; Джеральд Л. Томпсон (1959). Конечные математические структуры (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Прентис-Холл, Инк. Номер каталога карточек Библиотеки Конгресса 59-12841. Классический текст. cf Глава 6 Конечные цепи Маркова стр. 384ff.
• Джон Г. Кемени & Дж. Лори Снелл (1960) Конечные цепи Маркова, D. van Nostrand Company ISBN  0-442-04328-7
• Э. Нуммелин. «Общие неприводимые цепи Маркова и неотрицательные операторы». Издательство Кембриджского университета, 1984, 2004. ISBN  0-521-60494-X
• Сенета, Э. Неотрицательные матрицы и цепи Маркова. 2-е изд. изд., 1981, XVI, 288 стр., Серия Springer в мягкой обложке по статистике. (Первоначально опубликовано Allen & Unwin Ltd., Лондон, 1973 г.) ISBN  978-0-387-29765-1