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

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

Примером Марковского процесса: система S – счётчик в такси. Состояние системы в момент t характеризуется числом километров (десятых долей километров), пройденных автомобилем до данного момента. Пусть в момент t₀ счётчик показывает S₀/ Вероятность того, что в момент t>t₀ счётчик покажет то или иное число километров (точнее, соответствующее число рублей) S₁ зависит от S₀, но не зависит от того, в какие моменты времени изменились показания счётчика до момента t₀.

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

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

Марковским случайным процессом с дискретными состояниями и дискретным временем (или цепью Маркова) называется Марковский процесс, в котором его возможные состояния S₁, S₂, S_3, … можно заранее перечислить, а переход из состояния в состояние происходит мгновенно (скачком), но только в определённые моменты времени t_0, t_1, t_2, ..., называемые шагами процесса.

Обозначим p_ij – вероятность перехода случайного процесса (системы S) из состояния I в состояние j. Если эти вероятности не зависят от номера шага процесса, то такая цепь Маркова называется однородной.

Пусть число состояний системы конечно и равно m. Тогда её можно характеризовать матрицей перехода P₁, которая содержит все вероятности перехода:

p₁₁ p₁₂ … p_1m

p₂₁ p₂₂ … p_2m

… … … …

P_m1 p_m2 … p_mm

Естественно, по каждой строке ∑ p_ij = 1, I = 1, 2, …, m.

Обозначим p_ij(n) – вероятностью того, что в результате n шагов система перейдёт из состояния I в состояние j. При этом при I = 1 имеем вероятности перехода, образующие матрицу P₁, т.е. p_ij(1) = p_ij

Необходимо, зная вероятности перехода p_ij, найти p_ij(n) – вероятности перехода системы из состояния I в состояние j за n шагов. С этой целью будем рассматривать промежуточное (между I и j) состояние r, т.е. будем считать, что из первоначального состояния I за k шагов система перейдёт в промежуточное состояние r с вероятностью p_ir(k), после чего за оставшиеся n-k шагов из промежуточного состояния r она перейдёт в конечное состояние j с вероятностью p_rj(n-k). Тогда по формуле полной вероятности

P_ij(n) = ∑ p_ir (k) p_rj (n-k) – равенство Маркова.

Убедимся в том, что, зная все вероятности перехода p_ij = p_ij(1), т.е. матрицу P₁ перехода из состояния в состояние за один шаг, можно найти вероятность p_ij(2), т.е. матрицу P₂ перехода из состояния в состояние за два шага. А зная матрицу P₂, - найти матрицу P₃ перехода из состояния в состояние за три шага, и т.д.

Действительно, полагая n = 2 в формуле P_ij(n) = ∑ p_ir (k) p_rj (n-k), т.е. k=1 (промежуточное между шагами состояние), получим

P_ij(2) = ∑ p_ir(1)p_rj (2-1) = ∑ p_ir p_rj

Полученное равенство означает, что P₂ =P₁P₁ = P²₁

Полагая n = 3, k = 2, аналогично получим P₃ = P₁P₂ = P₁P₁² = P₁³, а в общем случае P_n = P₁ⁿ

Пример

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

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

2. семьи, не имеющие автомобиля, но намеревающиеся его приобрести;

3. семьи, имеющие автомобиль.

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

0,8 0,1 0,1

0 0,7 0,3

0 0 1

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

Найти вероятность того, что:

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

2. семья, не имевшая автомобиля, но намеревающаяся его приобрести, будет иметь автомобиль через два года.

РЕШЕНИЕ: найдём матрицу перехода Р₂ через два года:

0,8 0,1 0,1 0,8 0,1 0,1 0,64 0,15 0,21

0 0,7 0,3 0 0,7 0,3 0 0,49 0,51

0 0 1 0 0 1 0 0 1

То есть искомые в примере 1) и 2) вероятности равны соответственно

р₁₁ =0,64, р₂₃ =0,51

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

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

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

РЕШЕНИЕ. Возможные состояния системы: S_{0 –} оба узла исправны; S₁ – первый узел ремонтируется, второй исправен; S₂ – второй узел ремонтируется, первый исправен; S₃ – оба узла ремонтируются.

Стрелка, направления, например, из S₀ в S₁, означает переход системы в момент отказ первого узла, из S₁ в S₀ – переход в момент окончания ремонта этого узла.

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