Марковские случайные процессы с дискретными состояниями

Случайный процесс, протекающий в некоторой системе 5 с возможными состояниями 5^ 5₂, 5₃,…, называется марковским, или случайным процессом без последействия, если для любого момента времени ?₀ вероятностные характеристики процесса в будущем (при? > ?₀) зависят только от его состояния в данный момент ?₀ и не зависят от того, когда и как система пришла в это состояние; т. е. не зависят от ее поведения в прошлом (при? < ?₀).

Пример марковского процесса: система 5 — счетчик в такси. Состояние системы в момент? характеризуется числом километров (десятых долей километров), пройденных автомобилем до данного момента. Пусть в момент ?₀ счетчик показывает .9₀. Вероятность того, что в момент? > ?₀ счетчик покажет то или иное число километров (точнее, соответствующее число рублей) 5^, зависит от 5₀, но не зависит от того, в какие моменты времени изменялись показания счетчика до момента ?₀.

Многие процессы можно приближенно считать марковскими. Например, процесс игры в шахматы; система .9 — группа шахматных фигур. Состояние системы характеризуется числом фигур противника, сохранившихся на доске в момент ?₀. Вероятность того, что в момент? > ?₀ материальный перевес будет на стороне одного из противников, зависит в первую очередь от того, в каком состоянии находится система в данный момент ?₀, а не от того, когда и в какой последовательности исчезли фигуры с доски до момента ?₀.

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

Марковским случайным процессом с дискретными состояниями и дискретным временем (или цепью Маркова) называется марковский процесс, в котором его возможные состояния 5_1? 5₂, 5₃, … можно заранее перечислить, а переход из состояния в состояние происходит мгновенно (скачком), но только в определенные моменты времени? о, ?_1? ?₂, называемые шагами процесса.

Обозначим р_Х} — вероятность перехода случайного процесса (системы .9) из состояния /' в состояние у. Если эти вероятности не зависят от номера шага процесса, то такая цепь Маркова называется однородной.

Пусть число состояний системы конечно и равно т. Тогда ее можно характеризовать матрицей перехода Р_1? которая содержит все вероятности перехода:

Естественно, но каждой строке.

Обозначим Ру (п) — вероятность того, что в результате п шагов система перейдет из состояния i в состояние у. При этом при / = 1 имеем вероятности перехода, образующие матрицу Р_1? т. е. р_/;(1) = р_Х).

Необходимо, зная вероятности перехода р_1}, найти р_У)(п) — вероятности перехода системы из состояния % в состояние у за п шагов. С этой целью будем рассматривать промежуточное (между I и ]) состояние г, т. е. будем считать, что из первоначального состояния г за к шагов система перейдет в промежуточное состояние г с вероятностью р^(к)_у после чего за оставшиеся п-кшагов из промежуточного состояния гона перейдет в конечное состояние]с вероятностью р^п-к). Тогда по формуле полной вероятности.

Формула (7.3) называется равенством Маркова.

Убедимся в том, что, зная все вероятности перехода р^ = р^( 1), т. е. матрицу Р_{ перехода из состояния в состояние за один шаг, можно найти вероятности р^(2), т. е. матрицу Р₂ перехода из состояния в состояние за два шага. А зная матрицу Р₂> ^— найти матрицу Р₃ перехода из состояния в состояние за три шага, и г. д.

Действительно, полагая п = 2 в формуле (7.3), т. е. к = 1 (промежуточное между шагами состояние), получим.

Полученное равенство (7.4) означает, что.

Полагая п = 3, & = 2, аналогично получим, а в общем случае

[> Пример 7.1а. Совокупность семей некоторого региона можно разделить на три группы:

• 1) семьи, не имеющие автомобиля и не собирающиеся его покупать;
• 2) семьи, не имеющие автомобиля, но намеревающиеся его приобрести;
• 3) семьи, имеющие автомобиль.

Проведенное статистическое обследование показало, что матрица перехода за интервал в один год имеет вид

(В матрице Р_х элемент/?₃₁ = 1 означает вероятность того, что семья, имеющая автомобиль, также будет его иметь, а, например, элемент р₂₃ = 0,3 — вероятность того, что семья, не имевшая автомобиля, но решившая его приобрести, осуществит свое намерение в следующем году, и т. д.).

Найти вероятность того, что: а) семья, не имевшая автомобиля и не собиравшаяся его приобрести, будет находиться в такой же ситуации через два года; б) семья, не имевшая автомобиля, но намеревающаяся его приобрести, будет иметь автомобиль через два года.

Решение. Найдем матрицу перехода Р₂ через два года:

т.е. искомые в п. а) и б) вероятности равны соответственно р_хх = 0,64, Рп = 0,51. ?

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

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

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

Решение. Возможные состояния системы: 5₀ — оба узла исправны; 5^ - первый узел ремонтируется, второй исправен; 5₂ — второй узел ремонтируется, первый исправен; 5₃ — оба узла ремонтируются. Граф системы приведен на рис. 7.4.

Рис. 7.4.

Стрелка, направленная, например, из 5₀ в 5_1? означает переход системы в момент отказа первого узла, из 5^ в — переход в момент окончания ремонта этого узла.

На графе отсутствуют стрелки из 5₀ в 5₃ и из в .9₂. Это объясняется тем, что выходы узлов из строя предполагаются независимыми друг от друга и, например, вероятностями одновременного выхода из строя двух узлов (переход из 5₀ в 5₃) или одновременного окончания ремонтов двух узлов (переход из 5₃ в 5₀) можно пренебречь. ?