Общие сведения
В теории массового обслуживания к наиболее изученным и исследованным относятся модели, у которых случайный процесс функционирования относится к классу Марковских процессов, т.е. Марковские модели.
Случайный процесс, протекающий в системе, называется Марковским, если для любого момента времени вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент и не зависят от того, когда и как система пришла в это состояние.
При исследовании ВС аналитическим моделированием наибольшее значение имеют Марковские случайные процессы с дискретными состояниями и непрерывным временем. Процесс называется процессом с дискретными состояниями, если его возможные состояния
можно заранее перечислить, т.е. состояния системы принадлежат конечному множеству, и переход системы из одного состояния в другое происходит мгновенно. Процесс называется процессом с непрерывным временем, если смена состояний может произойти в любой случайный момент.
Описание Марковской модели
Для описания поведения системы в виде Марковской модели следует определить понятие состояния системы; выявить все состояния, в которых может находиться система; указать, в каком состоянии находится система в начальный момент; построить граф состояний, т.е. изобразить все состояния, например, кружками и возможные переходы из состояния в состояние – стрелками, соединяющими состояния (на рис. 3.1. выделено пять состояний); разметить граф, т.е. для каждого перехода указать интенсивность
потока событий, переводящих систему из состояния
в состояние
:
Рис. 3.1. Пример графа состояний
(3.7)
где
- вероятность перехода из состояния
в состояние
за время от
до
.
Для стационарных Марковских процессов интенсивности переходов не зависят от времени:
, тогда
.
Понятие состояния зависит от целей моделирования. В одном случае, например, оно может быть определено по состояниям элементов, каждый из которых может быть «свободен» или «занят»; в другом случае состояние системы определяется числом заявок, находящихся на обслуживании и в очередях.
В классе марковских процессов выделяют процессы с дискретными состояниями, называемые марковскими цепями. Когда множество состояний процесса
конечно, марковскую цепь называют конечной. Конечная марковская цепь может быть определена в непрерывном или дискретном времени. В первом случае переходы процесса из одного состояния в другое связываются с произвольными моментами времени
и цепь называют непрерывной; во втором – только в фиксированные моменты времени, обозначаемые порядковыми номерами
и цепь называется дискретной.
Дискретная марковская цепь определяется:
- множеством состояний
;
- матрицей вероятностей переходов
,
,
, элементы которой характеризуют вероятности перехода процесса из состояния
в состояние
;
- вектором начальных вероятностей
, определяющим вероятности
того, что в начальный момент времени
процесс находится в состоянии
.
Марковская цепь может быть представлена графом, вершины которого соответствуют состояниям цепи, а дуги ненулевым вероятностям переходов. На рис. 3.2 (а) представлен граф марковской цепи, имеющей 5 состояний и вектор начальных вероятностей
. Вероятности переходов показаны на дугах графа.
Рис. 3.2. Графы марковских цепей: а – дискретная, б – непрерывная
Марковская цепь порождает множество реализаций случайного процесса
, который представляется последовательностью состояний
соответствующих моментам времени
. В зависимости от возможности перехода из одних состояний в другие марковские цепи делятся на поглощающие и эргодические цепи.
Поглощающая марковская цепь содержит поглощающее состояние, достигнув которого, процесс прекращается. Признаком поглощающей цепи является наличие в матрице
диагонального элемента
. Так, марковская цепь, представленная на рис. 3.2, является поглощающей, так как содержит поглощающее состояние
. Для поглощающей цепи любой процесс в результате
шагов при
с вероятностью 1 попадает в поглощающее состояние.
Поглощающие марковские цепи широко используются в качестве временных моделей программ и вычислительных процессов. При моделировании программы состояния цепи отождествляются с модулями (операторами) программ, а матрица переходных вероятностей определяет порядок переходов между модулями, зависящий от структуры программы и исходных данных, значения которых определяют развитие вычислительного процесса. На такой модели можно вычислить число обращений к модулям программы и время выполнения программы, оцениваемой средними значениями, дисперсиями и при необходимости – распределениями. Аналогично вычислительный процесс, сводящийся к последовательности обращений к ресурсам системы в порядке, определяемом программой, можно представить поглощающей марковской цепью, состояния которой соответствуют использованию ресурсов системы – процессора и периферийных устройств, а переходные вероятности отображают порядок обращения к различным ресурсам.
Эргодическая марковская цепь представляет собой множество состояний, связанных матрицей переходных вероятностей таким образом, что из какого бы состояния процесс ни исходил, после некоторого числа шагов он может оказаться в любом состоянии. По этой причине состояния эргодической цепи называются эргодическими (возвратными). Процесс, порождаемый эргодической цепью, начавшись в некотором состоянии, никогда не завершается, а последовательно переходит из одного состояния в другое, попадая в различные состояния в разной частотой, зависящей от переходных вероятностей. Поэтому основная характеристика эргодической цепи – вероятности пребывания процесса в состояниях
, или относительные частоты попадания процесса в состояния
и доля времени, которую процесс проводит в каждом из состояний. В качестве дополнительных характеристик эргодических цепей используются математическое ожидание и дисперсия времени (числа шагов) первого попадания в состояние
из состояния
и предельная корреляция числа попаданий в состояния
и
.Эти характеристики определяются методами алгебраической теории марковских цепей.
Эргодические цепи широко используются в качестве моделей надежности систем. В этом случае состояния цепи соответствуют состояниям системы различающихся составом исправного и отказавшего оборудования. Переходы между состояниями связаны с отказами и восстановлением устройств и реконфигурацией связей между ними, выполняемой для сохранения работоспособности системы. Оценки характеристик эргодической цепи дают представление о надежности поведения системы в целом. Кроме того, эргодические цепи широко используются в качестве базовых моделей взаимодействия устройств с задачами, поступающими на обработку.
Непрерывная марковская цепь, поведение которой в любой момент времени подчиняется одному и тому же закону, называется однородной. Такая цепь задается матрицей интенсивностей переходов
,
. Интенсивность переходов определяется следующим образом:
,
,
где
- вероятность перехода из состояния
в состояние
за время
.
Это означает, что если процесс находится в состоянии
, то вероятность перехода в течение промежутка времени
в состояние
, отличное от
равно
. Аналогично вероятность перехода процесса из состояния
в состояние
равно
.
Интенсивность переходов должна удовлетворять условию
,
(1)
На рис. 3.2 (б) представлен граф непрерывной Марковской цепи с тремя состояниями и дугами, нагруженными интенсивностями переходов. Матрица
для данного графа, составленная с учетом условия (1) имеет вид:

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

|

|

|

|

|

|

|

|

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