Цепи Маркова

Рассмотрим состояния цепи Маркова более конкретно. Их можно классифицировать следующим образом:

- Возвратное состояние;

- Достижимое состояние;

- Неразложимая цепь Маркова;

- Периодическое состояние;

- Периодическая цепь Маркова;

- Поглощающее состояние;

- Эргодическое состояние.

Рассмотрим некоторые из них.

Возвратное состояние – это состояние Марковской цепи, посещаемое ею бесконечное число раз.

Определение.

Пусть дана однородная цепь Маркова с дискретным временем . Пусть - вероятность, выйдя из состояния i, вернуться в него ровно за n шагов. Тогда - вероятность, выйдя из состояния i, вернуться в него за конечное время.

Состояние i называется возвратным (рекуррентным), если fii = 1. В противном случае состояние называется невозвратным (транзиентным).

Достижимое состояние

Определение

Пусть - однородная цепь Маркова с дискретным временем. Состояние j называется достижимым из состояния i, если существует           n = n(i,j) такое, что  .

Пишут .

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

Период состояния

Пусть дана однородная цепь Маркова с дискретным временем с матрицей переходных вероятностей P. В частности, для любого , матрица является матрицей переходных вероятностей за n шагов. Рассмотрим последовательность . Число , где gcd обозначает наибольший общий делитель, называется периодом состояния j.

Замечание: таким образом, период состояния j равен d(j), если из того что следует, что n делится на d(j).

Периодические состояния и цепи

- Если d(j) > 1, то состояние j называется периодическим.

- Если d(j) = 1, то состояние j называется апериодическим.

- Периоды сообщающихся состояний совпадают:

.

Таким образом период любого неразложимого класса цепи Маркова определён и равен периоду любого своего представителя. Соответственно, классы делятся на периодические и апериодические.

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

Примеры использования

Области применения цепей Маркова.

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

Система обслуживания с отказами

Сервер, состоит из нескольких блоков, например модемов или сетевых карт, к которым поступают запросы от пользователей на обслуживание. Если все блоки заняты, то запрос теряется. Если один из блоков принимает запрос, то он становится занятым до конца его обработки. В качестве состояний возьмем количество незанятых блоков. Время будет дискретно. Обозначим за α вероятность поступления запроса. Также мы считаем, что время обслуживания также является случайным и состоящим из независимых продолжений, т.е. запрос с вероятностью β обслуживается за один шаг, а с вероятностью (1 - β) обслуживается после этого шага как новый запрос. Это дает вероятность (1 - β) β для обслуживания за два шага, (1 - β)2 β для обслуживания за три шага и т.д. Рассмотрим пример с 4 устройствами, работающими параллельно. Составим матрицу переходных вероятностей для выбранных состояний:

Можно заметить, что она имеет единственный эргодический класс, и, следовательно, система p × P = p в классе вероятностных векторов имеет единственное решение. Выпишем уравнения системы, позволяющей находить это решение:

p0 (1 - α) + p1 β = p0,

p0 α + p1 (1 - α - β) + p2 2β = p1,

p1 α + p2 (1 - α - 2β) + p3 3β = p2,

p2 α + p3 (1 - α - 3β) + p4 4β = p3,

p3 α + p4 (1 - 4β) = p4.

Отсюда получаем (при γ = α / β):

p1 = γ p0,

p2 = γ2 p0 / 2,

p3 = γ3 p0 / 3,

p4 = γ4 p0 / 4,

из условия нормировки следует:

p0 = С = (1 + γ + γ2/2 + γ3/3 + γ4/4)-1.

Теперь известен набор вероятностей πi того, что в стационарном режиме в системе будет занято i блоков. Тогда долю времени p4 = С γ4/4 в системе заняты все блоки, система не отвечает на запросы. Полученные результаты распространяются на любое число блоков. Теперь можно воспользоваться ими: можно сопоставить затраты на дополнительные устройства и уменьшение времени полной занятости системы.

Процессы принятия решений с конечным и бесконечным числом этапов

Рассмотрим процесс, в котором есть несколько матриц переходных вероятностей. Для каждого момента времени выбор той или иной матрицы зависит от принятого нами решения. Понять вышесказанное можно на следующем примере. Садовник в результате анализа почвы оценивает ее состояние одним из трех чисел: (1) - хорошее, (2) - удовлетворительное или (3) - плохое. При этом садовник заметил, что продуктивность почвы в текущем году зависит только от ее состояния в предыдущем году. Поэтому вероятности перехода почвы без внешних воздействий из одного состояния в другое можно представить следующей цепью Маркова с матрицей P1:

Логично, что продуктивность почвы со временем ухудшается. Например, если в прошлом году состояние почвы было удовлетворительное, то в этом году оно может только остаться таким же или стать плохим, а хорошим никак не станет. Однако садовник может повлиять на состояние почвы и изменить переходные вероятности в матрице P1 на соответствующие им из матрицы P2:

Теперь можно сопоставить каждому переходу из одного состояния в другое некоторую функцию дохода, которая определяется как прибыль или убыток за одногодичный период. Садовник может выбирать использовать или не использовать удобрения, именно от этого будет зависеть его конечный доход или убыток. Введем матрицы R1 и R2, определяющие функции дохода в зависимости от затрат на удобрения и качества почвы: