Цепь Маркова с непрерывным временем

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

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

Пример CTMC с тремя состояниями следующий: процесс выполняет переход по истечении времени, заданного временем удержания - экспоненциальной случайной величины , где i - его текущее состояние. Каждая случайная величина независима и такая, что , и . При переходе должно быть сделано, процесс переходит по прыжкам цепи , в дискретном времени цепь Маркова с стохастической матрицы:${\ 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 изменяет состояние из состояния i в соответствии с минимумом двух случайных величин, которые являются независимыми и такими, что для тех случаев, когда параметры задаются Q-матрицей${\ displaystyle E_ {i, j} \ sim {\ text {Exp}} (q_ {i, j})}$${\ displaystyle i \ neq j}$ ${\displaystyle Q=(q_{i,j})}$

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

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

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

Определение [ править ]

Марковская цепь с непрерывным временем ( X _t ) _{t  ≥ 0} определяется следующим образом: ^[1]

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

Для i  ≠  j элементы q _ij неотрицательны и описывают скорость переходов процесса из состояния i в состояние j . Элементы q _ii могут быть выбраны равными нулю, но для математического удобства общее соглашение состоит в том, чтобы выбирать их так, чтобы каждая строка сумм равнялась нулю, то есть:${\displaystyle Q}$

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

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

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

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

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

• ${\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})}$^{[ сомнительно - обсудить ]}

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

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

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

Бесконечно малое определение [ править ]

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

Пусть будет случайной величиной, описывающей состояние процесса в момент времени t , и предположим, что процесс находится в состоянии i в момент времени t . По определению марковской цепи с непрерывным временем, не зависит от значений до момента ; то есть не зависит от . Имея это в виду, для всех , для всех и для небольших значений справедливо следующее:${\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 _n с дискретным временем для описания n- го скачка процесса и переменные S ₁ , S ₂ , S ₃ , ... для описания времени удержания в каждом из состояний, где S _i следует экспоненциальному распределению со скоростью параметр - q _{Y i Y i} .

Свойства [ править ]

Общение в классах [ править ]

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

Временное поведение [ править ]

Напишите P ( t ) для матрицы с элементами p _ij = P ( X _t  =  j  |  X ₀  =  i ). Тогда матрица P ( t ) удовлетворяет прямому уравнению - дифференциальному уравнению первого порядка

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

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

${\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 - это распределение вероятностей, к которому процесс сходится при больших значениях t . Заметим, что для рассмотренного ранее процесса с двумя состояниями с P ( t ), заданным формулой

${\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}}}$

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

${\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}}.}$

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

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

Пример 2 [ править ]

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

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

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

Обратное время [ править ]

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

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

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

Один из методов нахождения стационарного распределения вероятностей , л , с концентрацией эргодической непрерывного времени марковской цепи, Q , являются первым нахождением его вложенного марковской цепью (ЭМС) . Строго говоря, EMC - это обычная цепь Маркова с дискретным временем, которую иногда называют скачкообразным процессом . Каждый элемент матрицы вероятности одношагового перехода EMC, S , обозначается s _ij и представляет условную вероятность перехода из состояния i в состояние 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}$

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

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

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

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

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

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

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]