Марковские модели

Общие сведения

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

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

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

Описание Марковской модели

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

Рис. 3.1. Пример графа состояний

(3.7)
где - вероятность перехода из состояния в состояние за время от до .
Для стационарных Марковских процессов интенсивности переходов не зависят от времени: , тогда .
Понятие состояния зависит от целей моделирования. В одном случае, например, оно может быть определено по состояниям элементов, каждый из которых может быть «свободен» или «занят»; в другом случае состояние системы определяется числом заявок, находящихся на обслуживании и в очередях.

В классе марковских процессов выделяют процессы с дискретными состояниями, называемые марковскими цепями. Когда множество состояний процесса конечно, марковскую цепь называют конечной. Конечная марковская цепь может быть определена в непрерывном или дискретном времени. В первом случае переходы процесса из одного состояния в другое связываются с произвольными моментами времени и цепь называют непрерывной; во втором – только в фиксированные моменты времени, обозначаемые порядковыми номерами и цепь называется дискретной.

Дискретная марковская цепь определяется:

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

Марковская цепь может быть представлена графом, вершины которого соответствуют состояниям цепи, а дуги ненулевым вероятностям переходов. На рис. 3.2 (а) представлен граф марковской цепи, имеющей 5 состояний и вектор начальных вероятностей . Вероятности переходов показаны на дугах графа.

Рис. 3.2. Графы марковских цепей: а – дискретная, б – непрерывная

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

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

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

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

Непрерывная марковская цепь, поведение которой в любой момент времени подчиняется одному и тому же закону, называется однородной. Такая цепь задается матрицей интенсивностей переходов , . Интенсивность переходов определяется следующим образом:
,         ,
где - вероятность перехода из состояния в состояние за время .
Это означает, что если процесс находится в состоянии , то вероятность перехода в течение промежутка времени в состояние , отличное от равно . Аналогично вероятность перехода процесса из состояния в состояние равно .
Интенсивность переходов должна удовлетворять условию
,                                                                        (1)
На рис. 3.2 (б) представлен граф непрерывной Марковской цепи с тремя состояниями и дугами, нагруженными интенсивностями переходов. Матрица для данного графа, составленная с учетом условия (1) имеет вид:

Основной характеристикой непрерывной Марковской цепи является стационарное (финальное) распределение вероятностей состояний , где - вероятности пребывания процесса в состояниях соответственно. Значение вероятностей определяется решением системы уравнений:
,
                                                                                 (2)
Систему уравнений (2) называют уравнениями равновесия. Они составляются по графу Марковской цепи с учетом того, что в каждом состоянии входящий поток должен равняться исходящему потоку.
Например, для цепи на рис. 3.2 (б) имеем:

Состояние	Интенсивность входящего потока	Интенсивность исходящего потока

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

См. также:

Уравнения Колмогорова для вероятностей состояний