ЭЛЕМЕНТЫ ТЕОРИИ МАРКОВСКИХ СЛУЧАЙНЫХ ПРОЦЕССОВ

Понятие случайного процесса

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

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

Пусть имеется некоторая физическая система A, которая в процессе функционирования может принимать различные состояния Ai. Если состояния системы меняются во времени случайным образом, то процесс смены состоя- ний можно рассматривать как случайный процесс, описываемый случайной функцией X(b). Полное множество состояний Aiисследуемой системы может быть либо конечным (i = 1, n), либо бесконечно большим.

Большинство реальных систем имеют дискретное конечное пространство

состояний. Последовательность состояний такой системы Ai

(i = 1, n)

и сам

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

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

Для систем с дискретным временем время пребывания системы в каждом состоянии фиксированное, а моменты переходов t1, t2, ..., tkразмещаются на временной оси через равные промежутки и называются «шагами». Время на- хождения системы в некотором состоянии представляет дискретную случай- ную величину.

Таким образом, случайный процесс с непрерывными состояниями и не- прерывным временем функционирования описывается непрерывной случайной функцией времени. Непрерывные и дискретные цепи описываются дискретны- ми случайными функциями времени.

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

Дискретные цепи Маркова

Случайный процесс, протекающий в системе A, называется марковским или случайным процессом без последствия, если для любого момента времени t0вероятность любого состояния системы при t > t0зависит только от ее со- стояния при t = t0и не зависит от того, как и когда система пришла в это со- стояние. Если число состояний Ai, которые система может принимать, конеч- но, то такие системы описывает марковский случайный процесс с дискретными состояниями, или марковская цепь.

Пример марковского процесса счетчик в такси. Состояние счетчика в момент tхарактеризуется числом километров (десятых долей километров), пройденных автомобилем до данного момента. Пусть в момент t0счетчик пока- зывает S0. Вероятность того, что в момент t1 > t0счетчик покажет то или иное число рублей S1, зависит от S0, но не зависит от того, в какие моменты времени изменялись показания счетчика до момента t0.

Если переходы системы из одного состояния в другое возможны в строго

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

Обычно марковскую цепь изображают в виде графа, вершины которого соответствуют возможным состояниям системы Ai, а дуги - возможным пере- ходам системы из состояния Ai ® Aj. Каждой дуге соответствует переходная

вероятность pij(k)=p[Aj(k)/Ai(k-1)]- это условная вероятность перехода системы

на k-ом шаге в состояние Ajпри условии, что на предыдущем

(k-1)-ом шаге система находилась в состоянии Ai.

Полным описанием марковской цепи служат матрицы переходных веро-

ятностей:

Pij

P 11

P 21

...

=

P i1

...

p n1

P 12

P 22

P i 2

...

P 1n 2

...

...

...

...

...

...

P 1 j

P 2 j

P 1ij

...

P nj

...

...

...

...

...

...

P 1n

P 2n

P in

...

p nn

n

е p ij = 1

j=1

(i = 1, n)

(3.1)

Кроме того, на каждом шаге марковская цепь характеризуется вектором вероятностей состояний:

|S(t)| = [S1(t),S2(t),. . . Sn(t)].(3.2)

Вероятностью i-го состояния называется вероятность Si(t)того, что в мо-

мент tсистема будет находиться в состоянии Ai.Очевидно, что для любого

момента tсумма вероятностей всех состояний равна единице:

n

е S i (t) = 1. (3.3)

i =1

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

Для неоднородной марковской цепи требуется kматриц, где k- число шагов.

Все многообразие марковских цепей подразделяется на эргодические и

разложимые.

Эргодические марковские цепи описываются сильно связанным графом. Это означает, что в такой системе возможен переход из любого состояния Aiв любое состояние Aj(i = 1..n) за конечное число шагов.

Разложимые марковские цепи содержат невозвратные состояния, назы-

ваемые поглощающими. Из поглощающего состояния нельзя перейти ни в ка- кое другое. На графе поглощающему состоянию соответствует вершина, из ко- торой не выходит ни одна дуга.

Пример 3.1

Построить граф состояний и матрицу переходных вероятностей следую-

щего случайного процесса:

Устройство Sсостоит из двух узлов, каждый из которых в случайный момент времени может выйти из строя, после чего мгновенно начинается ре- монт узла, продолжающийся заранее неизвестное случайное время.

Решение:

Возможные состояния системы:

0– оба узла исправны;

1– первый узел ремонтируется, второй исправен;

2– второй узел ремонтируется, первый исправен;

3– оба узла ремонтируются.

Граф системы и матрица переходных вероятностей имеют вид:

p 00

P 20

P 01

P11

P 31

P 02

P 22

P 32

P13 p 23

p 33

Рис 3.1. Граф системы

При рассмотрении марковских цепей наиболее интересно выяснить, как будет изменяться вектор вероятностей состояний |S(t)|,когда система сделает один шаг. Для однородных цепей это можно сделать так.

Вернемся к примеру 3.1. Система может иметь 4 возможных состояния.

Допустим, на (k-1)-м шаге вектор вероятностей состояний системы имел вид:

|S(t)|(k-1) = [S0(k-1) (t),S1(k-1) (t), S2(k-1) (t), S3(k-1) (t)].

Вероятность того, что на k-м шаге система будет находиться, например, в

состоянии 1можно вычислить по формуле полной вероятности:

S1(k) (t) = S0(k-1) (t) p01 + S1(k-1) (t) p11 + S3(k-1) (t) p31 .

Нетрудно заметить, что при вычислениях элементы вектора умножались

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

В общем виде можно записать:

j

(t)

n

i =1

( k -1)

i

(t) Ч

P ij

j = 1, …n.(3.4)

Формула (3.4) позволяет последовательно шаг за шагом определять изме- нение элементов вектора вероятностей состояния, если известны элементы ис- ходного вектора.

Операции по зависимости (3.4) представляют собой умножение вектора (матрицы-строки) состояний на матрицу переходных вероятностей, поэтому (3.4) можно переписать в матричном виде:

|S(t)|(k) = |S(t)|(k-1) Ч||Pij||.(3.5)

В некоторых случаях при исследовании дискретных цепей Маркова воз-

никает задача определения вероятностей состояния через mшагов. Безусловно, можно воспользоваться последовательным применением выражений (3.4) или (3.5), но это не всегда удобно. В ряде случаев для однородных цепей Маркова проще воспользоваться многошаговой матрицей переходных вероятностей

||Pij(m)||. Она позволяет, используя выражения (3.4) или (3.5), определить эле-

менты вектора вероятностей состояний через необходимое число шагов.

Для получения m-шаговой матрицы переходных вероятностей нужно вы-

числить m-ю степень обычной (одношаговой) матрицы:

||Pij(m)|| = ||Pij||m .(3.6)

Выражение (3.6) является следствием известного соотношения, которое

называется уравнение Колмогорова – Чепмена:

||Pij(m)|| = ||Pij(s)|| ||Pij(m-s)||.(3.7)