Методы и алгоритмы построения элементов систем статистического моделирования
Рис. 9. Классификация марковских процессов
4. Математический аппарат дискретных марковских цепей
В дальнейшем рассматриваются простые однородные марковские цепи с дискретным временем. Основным математическим соотношением для ДМЦ является уравнение, с помощью которого определяется состояние системы на любом ее k-м шаге. Это уравнение имеет вид:
(4)
и называется уравнением Колмогорова-Чепмена.
Уравнение Колмогорова-Чепмена относится к классу рекуррентных соотношений, позволяющих вычислить вероятность состояний марковского случайного процесса на любом шаге (этапе) при наличии информации о предшествующих состояниях.
Дальнейшие математические соотношения зависят от конкретного вида марковской цепи.
4.1. Поглощающие марковские цепи
Как указывалось выше, у поглощающих ДМЦ имеется множество, состоящее из одного или нескольких поглощающих состояний.
Для примера рассмотрим переходную матрицу, описывающую переходы в системе, имеющей 4 возможных состояния, два из которых являются поглощающими. Матрица перехода такой цепи будет иметь вид:
(5)
Практически важным является вопрос о том, сколько шагов сможет пройти система до остановки процесса, то есть поглощения в том или ином состоянии. Для получения дальнейших соотношений путем переименования состояний матрицу (8.5) переводят к блочной форме:
(6)
Такая форма позволяет представить матрицу (6) в каноническом виде:
(6а)
где - единичная матрица;
- нулевая матрица;
— матрица, описывающая переходы в системе из невозвратного множества состояний в поглощающее множество;
— матрица, описывающая внутренние переходы в системе в невозвратном множестве состояний.
На основании канонической формы (6а) получена матрица, называемая фундаментальной:
(7)
В матрице (7) символ (-1) означает операцию обращения, то есть
(8)
После соответствующих преобразований матрица (7) примет вид:
(7а)
Каждый элемент матрицы (7а) соответствует среднему числу раз попадания системы в то или иное состояние до остановки процесса (поглощения).
Если необходимо получить общее среднее количество раз попадания системы в то или иное состояние до поглощения, то фундаментальную матрицу М необходимо умножить справа на вектор-столбец, элементами которого будут единицы, то есть
(8а)
где .
Для иллюстрации приведем конкретный числовой пример: пусть известны значения переходных вероятностей матрицы с одним поглощающим состоянием: ; ; ; ; ; ; ; .
Переходная матрица в блочной системе будет выглядеть так: