P = s

J1 0

0 0,1

и вектором начальных вероятностей п0 = {1,0,0,0,0} .

Рис. 7.2. Граф марковской цепи

Л/2

Рис. 7.3. Граф непрерывной марковской цепи

Марковская цепь порождает множество реализаций случайного процесса f(t), который представляется последовательностью состоянийf (t ) = f0, f1, f2,..., f (t )eS,

соответствующих моментам времени t=0, 1, 2, ... Начальное состояние f0 = si определяется вектором начальных вероятностей п. Следующее состояние f = s}. определяется i-й строкой матрицы вероятностей переходов Р: процесс f(t) переходит в состояние f = s}. с вероятностью ptj. Затем процесс переходит в состояние f2 = sk, определяемое вероятностями pik , соответствующими состоянию Sj, и т. д. В результате n шагов процесс попадает в

состояния s

1,

sK с вероятностями пп

1

pK

соответственно.

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

Поглощающая марковская цепь содержит поглощающее состояние, достигнув которого, процесс уже никогда его не покидает, т. е. по сути прекращается. Поглощающее состояние будем обозначать s0. Вероятность перехода p00 = 1 и, следовательно, все

остальные вероятности p0}. = 0, j = 1,...,K. Матрица вероятностей переходов поглощающей

цепи имеет следующий вид:

s

s

2

s

4

s

5

1

Из какого бы состояния ни начался процесс, при n --оо с вероятностью 1 он окажется в поглощающем состоянии S0 . Основная характеристика случайного процесса, порождаемого поглощающей марковской цепью, - число пребываний процесса в состояниях s sK до момента поглощения. Число пребываний в каждом из состояний St, i=l,...,K и на

множестве невозвратных состояний {s sK} - случайные величины, характеризуемые

средними значениями, дисперсиями и распределениями. Для определения указанных характеристик используются методы алгебраической теории марковских цепей [14].

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

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

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

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

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

Марковский процесс с дискретными состояниями s1,...,sK, переходы между которыми

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

тому же закону, задается матрицей интенсивностей переходов Q = qij. ~, i, j = 1,K. Интенсивность переходов определяется следующим образом:

qij

lim

At

qij

li miM

At-0 At

где pii (At) - вероятность перехода процесса из состояния si в состояние si, за время At. Это означает, что если процесс находится в состоянии Si, то вероятность перехода в течение

промежутка времени

At

в состояние Sj, отличное от Si, равна

At

qiiAt

Аналогично вероятность

qijAt.

перехода процесса в течение промежутка времени из состояния Si в состояние Sj равна Интенсивность переходов должна удовлетворять условию

i = 1.....K

(7.5)

j=1

На рис. 7.3 представлен граф непрерывной марковской цепи с тремя состояниями S1, S2, S3. Дуги графа нагружены интенсивностями переходов. Графу соответствует следующая матрица интенсивностей переходов:

(7.6)

[J

At -0

s

s

3

При построении матрицы значения qii, i = 1,...,K, в соответствии с (7.5) определяются следующим образом:

к

%»= -Е %

(j *i)

Основная характеристика непрерывной марковской цепи - стационарное (финальное) распределение вероятностей состояний a = [ax,...,aK}, гдеaK - вероятности пребывания

процесса в состояниях s1,... , sK соответственно. Распределение задается вероятностным решением системы линейных уравнений

aQ = 0(7.7)

которая в развернутой форме имеет следующий вид: