Цепи Маркова с непрерывным временем (CTMC) и дифференциальные уравнения Колмогорова

Фундаментальным отличием CTMC от дискретных цепей является наличие так называемого времени пребывания (Sojourn Time). Если система попала в определенное состояние, она находится в нем случайное время, которое строго подчиняется экспоненциальному закону распределения (в силу требования отсутствия памяти, или марковского свойства). Интенсивность (параметр экспоненциального распределения), с которой система стремится покинуть текущее состояние, определяет скорость процесса. Если из текущего состояния есть несколько путей выхода, время пребывания определяется суммой интенсивностей всех исходящих маршрутов, а вероятности выбора конкретного пути прямо пропорциональны их относительным интенсивностям.

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

Для нахождения вероятностей состояний системы в любой произвольный момент времени t применяются дифференциальные уравнения Колмогорова (Прямая и Обратная системы уравнений). В матричной форме прямая система записывается как dP(t)/dt = P(t) * Q. Это фундаментальное дифференциальное уравнение первого порядка с матричными коэффициентами. Его формальным аналитическим решением является матричная экспонента: P(t) = exp(Q * t). Вычисление матричной экспоненты является тяжелейшей вычислительной задачей линейной алгебры, требующей применения спектрального разложения (поиска собственных векторов и значений матрицы Q) или аппроксимаций в виде рядов Тейлора, что позволяет процессорам рассчитывать вероятности для тысяч состояний одновременно.

Огромное практическое значение имеет анализ эргодических свойств CTMC при времени t, стремящемся к бесконечности. Если процесс является неразложимым, дифференциальные производные затухают до нуля, и система выходит на стационарный режим. Уравнение Колмогорова превращается в простую систему линейных алгебраических уравнений: pi * Q = 0, где pi — искомый вектор стационарных вероятностей (при условии, что сумма всех его элементов равна единице). Именно этот алгебраический аппарат лежит в основе абсолютно всех аналитических моделей теории массового обслуживания (формулы Эрланга), расчета надежности резервированных электронных систем и моделирования кинетики химических реакторов в химической промышленности.