Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,749

Денисенко Т.И.

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

Цепь Маркова, используется и в качестве математической модели при изучении поведения определенных стохастических систем. Для коротких отрезков времени можно использовать вычисления абсолютных вероятностей f. Когда же число переходов неограниченно возрастает (больше k), необходимы иные методы анализа поведения системы.

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

Рассмотрим Марковскую цепь с матрицей переходных состояний:

f

Рассматривая эту матрицу как матрицу сложности вершин некоторого графа (рисунок 1), структурный граф.

Дуги графа намечены вероятностями Pij, т. е. вероятностями перехода f. Из определения замкнутого множества С состояний следует, что состояние не образуют неприводимой Марковской цепи, ибо состояний 0, 1 и 2 достигнуть из состояния 3 не представляется возможным. Ясно, что состояние 3 образует замкнутое множество состояний, и оно является поглощающим, т.е. состояние 3 можно считать неприводимой цепью.

p

Рис. 1.

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

Введем в рассмотрение величину f - вероятность первого возвращения в состояние Sj на m-ом шаге. Построим формулу для вычисления этой характеристики Марковского процесса. Допустим, что задана матрица переходов f. В этом случае очевидны следующие соотношения:

f,

f.

Действительно, перейдя из Sj в Sj за два шага можно двумя альтернативными способами, а именно,

а) через некоторое промежуточное состояние f,

б) перейти из Sj в Sj на первом шаге, а на втором шаге это состояние сохранить.

В первом случае вероятность перехода f по определению есть f, во втором случае переход системы в Sj будет повторным и его вероятность, естественно, есть произведение f.

Таким образом,

f.

Рассуждая аналогично, найдем, что

f,                            (1)

где f - вероятность перехода f за три шага,

f - вероятность первого возвращения в Sj на третьем шаге,

f - вероятность появления Sj на третьем шаге,

f - вероятность события.

Рассуждая для шага m, получим

f                      (2)

Из (2) определяем вероятность первого появления состояния Sj на m-ом шаге

f.                      (3)

Вероятность возвращения в состояние Sj по крайней мере хотя бы раз можно оценить по формуле

f.                               (4)

Если можно гарантировать, что система, раз побывав в состоянии Sj, обязательно в него вернется без каких-либо ограничений на число шагов, то

f.

Среднее время возвращения в состояние Sj сложно оценить средним числом шагов, требуемым для этого возврата в данной системе, т. е. величиной

f                     (5)

Если f, то не известно, вернется ли вообще система в состояние Sj и, следовательно, можно полагать, что f.

Исходя из понятия «время первого возвращения в данное состояние» множество всех состояний Марковской цепи можно описать следующим образом:

1) Состояние Sj является невозвратным, если f, т. е. f.

2) Состояние Sj возвратное, если f.

3) Возвратное состояние нулевое, если f, и не нулевым, если f, т. е. конечно.

4) Состояние периодическим с периодом Т, если возвращение в него возможно только через число шагов, пропорциональных Т, 2Т, 3Т, ..., а это означает, что если m не делится на Т без остатка, то f.

5) Возвратное состояние является эргодическим, если оно ненулевое и апериодическим.

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

СПИСОК ЛИТЕРАТУРЫ:

1. Ларичев О.И. Наука и искусство принятия решений. М., 1979