Марковские случайные процессы
Исследование операций случайных процессов с использованием цепей Маркова и уравнений Колмогорова
[Марков Андрей Андреевич (1856 - 1922) – выдающийся русский математик, внёсший большой вклад в теорию вероятностей, математический анализ и теорию чисел.]
Задачи, решаемые с помощью цепей маркова, относятся к задачам исследования операций в условиях неопределенности, в которых неопределенные факторы, входящие в задачу, являются случайными величинами с известными вероятностными характеристиками.
Пусть имеется некоторая физическая система S, которая с течением времени меняет свое состояние (переходит из одного состояния в другое), причем заранее неизвестным, случайным образом. Тогда мы будем говорить, что в системе S протекает случайный процесс. Случайный процесс называется марковским, если для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t0 и не зависят от того, когда и как система пришла в это состояние. Другими словами, в марковском случайном процессе будущее развитие его зависит только от настоящего состояния и не зависит от предыстории процесса.
Например, пусть система S представляет собой техническое устройство, которое уже проработало некоторое время, соответственным образом износилось и перешло в некоторое состояние, характеризующимся определенной степенью изношенности. Нас интересует, как будет работать система в будущем (частота отказов, потребность в ремонте и т.д.). Очевидно, что характеристики работы системы в будущем зависят от его настоящего состояния и не зависят от того, когда и как устройство достигло своего настоящего состояния.
Марковские случайные процессы делятся на классы в зависимости от того, как и в какие моменты времени система S может менять свои состояния. Последовательность состояний системы и сам процесс переходов из состояния в состояние называется цепью. Виды марковских процессов:
1. С дискретными состояниями и дискретным временем.
Возможные состояния S1, S2, S3, ... можно перечислить (перенумеровать), а переход системы из состояния в состояние происходит только в строго определенные, заранее фиксированные моменты времени. Такие процессы называется дискретными цепями Маркова и описываются с помощью матриц переходных вероятностей.
2. С дискретными состояниями и непрерывным временем.
Возможные состояния S1, S2, S3, ... можно перечислить (перенумеровать), а переход системы из состояния в состояние возможен в любой, заранее неизвестный, случайный момент времени. Такие процессы называются непрерывными цепями Маркова и описываются с помощью дифференциальных уравнений Колмогорова.
Возможные переходы системы из состояния в состояние удобно изображать с помощью графа состояний. Рассмотрим примеры.
Пример 1. Техническое устройство S состоит из двух узлов: 1 и 2, каждый из которых может в ходе работы устройства выйти из строя. Возможны следующие состояния системы:
S1 – оба узла работают;
S2 – первый узел отказал, второй работает;
S3 – второй узел отказал, первый работает;
S4 – оба узла отказали.
Граф состояний, отражающий возможные переходы системы из одного состояния в другое, будет формироваться следующим образом (рис. 1):
| S1 |
| S2 |
| S3 |
| S4 |
Рис. 1.
(В данном графе мы пренебрегаем возможностью строго одновременного отказа обоих узлов.)
Пример 2. Система S – автомашина, которая может находиться в одном из 5 состояний:
S1 – исправно работает;
S2 – неисправна, ожидает осмотра;
S3 – осматривается;
S4 – ремонтируется;
S5 – списывается.
Граф состояний (рис. 2):
| S1 |
| S2 |
| S3 |
| S4 |
| S5 |
Рис. 2.
Пример 3. Изменим пример 1. Пусть каждый узел после отказа сразу же начинает восстанавливаться. Возможные состояния системы:
S1 – оба узла работают;
S2 – первый узел восстанавливается, второй работает;
S3 – второй узел восстанавливается, первый работает;
S4 – оба узла восстанавливаются.
Граф состояний:
| S1 |
| S2 |
| S3 |
| S4 |
Рис. 3.
Пример 4. В условиях примера 3 каждый узел перед тем, как начать восстанавливаться, подвергается осмотру с целью локализации неисправности. Состояния системы будем нумеровать двумя индексами. Первый индекс будет означать состояния первого узла:
1 – работает;
2 – осматривается;
3 – восстанавливается.
Второй индекс – те же состояния для второго узла. Возможные состояния системы будут:
S11 – оба узла работают;
S12 – первый узел работает, второй осматривается;
…
S33 – оба узла восстанавливаются.
Граф состояний:
| S11 |
| S12 |
| S13 |
| S21 |
| S22 |
| S23 |
| S31 |
| S32 |
| S33 |
Рис. 4.