Введение

Концепция вероятности
Математические свойства непрерывных марковских цепей

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

Эквивалентно, благодаря свойству конкурирующих экспонент, эта CTMC изменяет состояние из состояния i в соответствии с минимумом двух случайных величин, которые независимы и таковы, что для , где параметры задаются матрицей Q.

Каждый недиагональный элемент может быть вычислен как вероятность того, что цепь скачков переходит из состояния i в состояние j, деленная на ожидаемое время пребывания в состоянии i. Диагональные элементы выбираются таким образом, чтобы сумма элементов в каждой строке была равна 0. CTMC удовлетворяет свойству Маркова, то есть его поведение зависит только от его текущего состояния и не зависит от его предыдущего поведения, благодаря отсутствию памяти у экспоненциального распределения и дискретных марковских цепей.

Свойство "переходная цепочка"/время удержания

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

Общающиеся классы

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

Пример 2

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

Эта цепь Маркова является неприводимой, поскольку привидения могут достичь любого состояния из любого другого за конечное число шагов. Благодаря секретному проходу, цепь Маркова также является апериодической, так как привидения могут переходить из любого состояния в любое другое как за четное, так и за нечетное число переходов. Следовательно, существует единственное стационарное распределение, которое можно найти, решив уравнение , при условии, что сумма элементов должна равняться 1. Решение этого линейного уравнения с учетом ограничения таково: центральное состояние и граничные состояния 2 и 8, прилегающие к секретному проходу, посещаются чаще всего, а угловые состояния – реже всего.

Временная перемена

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