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

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

Пример 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_ {я, j} \ sim {\ text {Exp}} (q_ {я, j})}$${\ displaystyle i \ neq j}$ ${\ Displaystyle Q = (q_ {я, j})}$

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

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

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

Определение

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

• конечное или счетное пространство состояний 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}.}$

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

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

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

Другой распространенный способ определения цепей Маркова с непрерывным временем состоит в том, чтобы вместо матрицы скорости перехода использовать следующее: ${\ 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 {для всех}} i,}$

${\ displaystyle m_ {ij} = {\ frac {q_ {ij}} {\ sum _ {k \ neq i} q_ {ik}}}, {\ text {для всех}} i \ neq j.}$

Рассмотрим упорядоченную последовательность моментов времени и состояний, записанных в эти моменты времени , тогда она утверждает, что: ${\ Displaystyle т_ {0} <т_ {1} <\ точки <т_ {п}}$${\ 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 (Икс (т + час) = j \ середина X (т) = я) = \ дельта _ {ij} + q_ {ij} час + о (час)}$ ,

где - дельта Кронекера, и были использованы краткие обозначения . ${\ 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 Р (т) = е ^ {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}}}$

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

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

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

${\ displaystyle \ sum _ {я \ 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

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

Изображение справа описывает цепь Маркова в дискретном времени, моделирующую Pac-Man с пространством состояний {1,2,3,4,5,6,7,8,9}. Игрок управляет Пакманом через лабиринт, поедая пак-точки. Тем временем за ним охотятся призраки. Для удобства лабиринт представляет собой небольшую сетку 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_ {Tt}}$

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

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

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

${\ displaystyle s_ {ij} = {\ begin {case} {\ frac {q_ {ij}} {\ sum _ {k \ neq i} q_ {ik}}} & {\ text {if}} i \ neq j \\ 0 & {\ text {иначе}}. \ end {case}}}$

Отсюда 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}$${\ 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δ), ... задают последовательность состояний, которые посещает δ-скелет.

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

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

Ноты

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