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

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

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

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

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

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

(3.7)

где - вероятность перехода из состояния в состояние за время от до .

Для стационарных Марковских процессов интенсивности переходов не зависят от времени: , тогда .

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

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

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

- множеством состояний ;

- матрицей вероятностей переходов , , , элементы которой характеризуют вероятности перехода процесса из состояния в состояние ;

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

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

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

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

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

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

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

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

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

, ,

где - вероятность перехода из состояния в состояние за время .

Это означает, что если процесс находится в состоянии , то вероятность перехода в течение промежутка времени в состояние , отличное от равно . Аналогично вероятность перехода процесса из состояния в состояние равно .

Интенсивность переходов должна удовлетворять условию

, (1)

На рис. 3.2 (б) представлен граф непрерывной Марковской цепи с тремя состояниями и дугами, нагруженными интенсивностями переходов. Матрица для данного графа, составленная с учетом условия (1) имеет вид:

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

,

(2)

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

Например, для цепи на рис. 3.2 (б) имеем:

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

Система уравнений равновесия получается из условия равенства интенсивности входящего и исходящего потока

;

;

.

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

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

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

В первом случае надо вероятность умножить на вероятность того, что за время система не перейдет в состояние , или . Суммарный поток событий, выводящий систему из состояния , имеет интенсивность . Значит, вероятность того, что за время система выйдет из состояния , равна . Отсюда вероятность первого варианта

.

Найдем вероятность перехода в состояние . Если в момент система находилась в состоянии с вероятностью , то вероятность перехода в состояние за время равна

.

Аналогично для состояния

.

Складывая вероятности , и , получим

.

Раскроем квадратные скобки, перенесем в левую часть и разделим обе части на :

.

Если устремить к нулю, то слева получим производную функции :

.

Аналогичные уравнения можно вывести для всех остальных состояний. Получается система дифференциальных уравнений:

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

Представим уравнения Колмогорова в общем виде:

, (3.8)

Здесь учтено, что для состояний, не имеющих непосредственных переходов, можно считать .

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

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

Для вычисления предельных вероятностей нужно все левые части в уравнениях Колмогорова (3.8) положить равными нулю и решить полученную систему линейных алгебраических уравнений:

, (3.10)

В связи с тем, что эти уравнения однородные, т.е. не имеют свободного члена и, значит, позволяют определить неизвестные только с точностью до произвольного множителя, следует воспользоваться нормировочным условием

(3.11)

и с его помощью решить систему уравнений.

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

Рис. 3.2. Граф состояний модели размножения и гибели

В этой модели формулы для определения вероятностей состояний, полученные в результате решения уравнений Колмогорова, имеют вид:

(3.12)

(3.13)

Эти формулы часто используют при решении задач теории массового обслуживания.