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

Итак, модель марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i -го состояния в j -е состояние), см. рис. 33.1.

Рис. 33.1. Пример графа переходов

Каждый переход характеризуется вероятностью перехода P_ij. Вероятность P_ij показывает, как часто после попадания в i -е состояние осуществляется затем переход в j -е состояние. Конечно, такие переходы происходят случайно, но если измерить частоту переходов за достаточно большое время, то окажется, что эта частота будет совпадать с заданной вероятностью перехода.

Ясно, что у каждого состояния сумма вероятностей всех переходов (исходящих стрелок) из него в другие состояния должна быть всегда равна 1 (см. рис. 33.2).

Рис. 33.2. Фрагмент графа переходов (переходы из i-го состояния являются полной группой случайных событий)

Например, полностью граф может выглядеть так, как показано на рис. 33.3.

Рис. 33.3. Пример марковского графа переходов

Реализация марковского процесса (процесс его моделирования) представляет собой вычисление последовательности (цепи) переходов из состояния в состояние (см. рис. 33.4). Цепь на рис. 33.4 является случайной последовательностью и может иметь также и другие варианты реализации.

Рис. 33.4. Пример марковской цепи, смоделированной по марковскому графу, изображенному на рис. 33.3

Чтобы определить, в какое новое состояние перейдет процесс из текущего i -го состояния, достаточно разбить интервал [0; 1] на подынтервалы величиной P_{i 1}, P_{i 2}, P_{i 3}, … (P_{i 1} + P_{i 2} + P_{i 3} + … = 1), см. рис. 33.5. Далее с помощью ГСЧ надо получить очередное равномерно распределенное в интервале [0; 1] случайное число r _рр и определить, в какой из интервалов оно попадает (см. лекцию 23).

Рис. 33.5. Процесс моделирования перехода из i-го состояния марковской цепи в j-е с использованием генератора случайных чисел

После этого осуществляется переход в состояние, определенное ГСЧ, и повтор описанной процедуры для нового состояния. Результатом работы модели является марковская цепь (см.рис. 33.4).

Пример. Имитация стрельбы из пушки по цели. Для того, чтобы проимитировать стрельбу из пушки по цели, построим модель марковского случайного процесса.

Определим следующие три состояния: S ₀ — цель не повреждена; S ₁ — цель повреждена; S ₂ — цель разрушена. Зададим вектор начальных вероятностей:

Значение P ₀ для каждого из состояний показывает, какова вероятность каждого из состояний объекта до начала стрельбы.

Зададим матрицу перехода состояний (см. табл. 33.1).

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

Наглядно модель марковского процесса можно представить себе в виде следующего графа (см. рис. 33.6).

Рис. 33.6. Граф марковского процесса, моделирующий стрельбу из пушки по цели

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

Проимитируем, используя таблицу случайных чисел, процесс стрельбы. Пусть начальное состояние будет S ₀. Возьмем последовательность из таблицы случайных чисел: 0.31, 0.53, 0.23, 0.42, 0.63, 0.21, … (случайные числа можно взять, например, из этой таблицы).

0.31: цель находится в состоянии S ₀ и остается в состоянии S ₀, так как 0 < 0.31 < 0.45;
0.53: цель находится в состоянии S ₀ и переходит в состояние S ₁, так как 0.45 < 0.53 < 0.45 + 0.40;
0.23: цель находится в состоянии S ₁ и остается в состоянии S ₁, так как 0 < 0.23 < 0.45;
0.42: цель находится в состоянии S ₁ и остается в состоянии S ₁, так как 0 < 0.42 < 0.45;
0.63: цель находится в состоянии S ₁ и переходит в состояние S ₂, так как 0.45 < 0.63 < 0.45 + 0.55.

Так как достигнуто состояние S ₂ (далее цель переходит из S ₂ в состояние S ₂ с вероятностью 1), то цель поражена. Для этого в данном эксперименте потребовалось 5 снарядов.

На рис. 33.7 приведена временная диаграмма, которая получается во время описанного процесса моделирования. Диаграмма показывает, как во времени происходит процесс изменения состояний. Такт моделирования для данного случая имеет фиксированную величину. Нам важен сам факт перехода (в какое состояние переходит система) и не важно, когда это происходит.

Рис. 33.7. Временная диаграмма переходов в марковском графе (пример имитации)

Процедура уничтожения цели совершена за 5 тактов, то есть марковская цепь этой реализации выглядит следующим образом: S ₀— S ₀— S ₁— S ₁— S ₁— S ₂. Конечно, ответом задачи это число быть не может, так как в разных реализациях получатся разные ответы. А ответ у задачи может быть только один.

Повторяя данную имитацию, можно получить, например, еще такие реализации (это зависит от того, какие конкретно случайные числа выпадут): 4 (S ₀— S ₀— S ₁— S ₁— S ₂); 11 (S ₀— S ₀— S ₀— S ₀— S ₀— S ₁— S ₁— S ₁— S ₁— S ₁— S ₁— S ₂); 5 (S ₁— S ₁— S ₁— S ₁— S ₁— S ₂); 6 (S ₀— S ₀— S ₁— S ₁— S ₁— S ₁— S ₂); 4 (S ₁— S ₁— S ₁— S ₁— S ₂); 6 (S ₀— S ₀— S ₁— S ₁— S ₁— S ₁— S ₂); 5 (S ₀— S ₀— S ₁— S ₁— S ₁— S ₂). Всего уничтожено 8 целей. Среднее число циклов в процедуре стрельбы составило: (5 + 4 + 11 + 5 + 6 + 4 + 6 + 5)/8 = 5.75 или, округляя, 6. Именно столько снарядов, в среднем, рекомендуется иметь в боевом запасе пушки для уничтожения цели при таких вероятностях попаданий.

Теперь следует определить точность. Именно точность может нам показать, насколько следует доверять данному ответу. Для этого проследим, как сходится последовательность случайных (приближенных) ответов к правильному (точному) результату. Напомним, что, согласно центральной предельной теореме (см. лекцию 25, лекцию 21), сумма случайных величин есть величина неслучайная, поэтому для получения статистически достоверного ответа необходимо следить за средним числом снарядов, получаемых в ряде случайных реализаций.

На первом этапе вычислений средний ответ составил 5 снарядов, на втором этапе средний ответ составил (5 + 4)/2 = 4.5 снаряда, на третьем — (5 + 4 + 11)/3 = 6.7. Далее ряд средних величин, по мере накопления статистики, выглядит следующим образом: 6.3, 6.2, 5.8, 5.9, 5.8. Если изобразить этот ряд в виде графика средней величины выпущенных снарядов, необходимых для поражения цели, в зависимости от номера эксперимента, то обнаружится, что данный ряд сходится к некоторой величине, которая и является ответом (см. рис. 33.8).

Рис. 33.8. Изменение средней величины в зависимости от номера эксперимента

Визуально мы можем наблюдать, что график «успокаивается», разброс между вычисляемой текущей величиной и ее теоретическим значением со временем уменьшается, стремясь к статистически точному результату. То есть в некоторый момент график входит в некоторую «трубку», размер которой и определяет точность ответа.

Алгоритм имитации будет иметь следующий вид (см. рис. 33.9).

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