Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






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



 

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

 

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

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

Пусть имеется некоторая физическая система 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 = p10

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 .

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

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

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


 

S
( k )

j


 

(t)


n

S
= е

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)

 

 


Эта страница нарушает авторские права

allrefrs.ru - 2017 год. Все права принадлежат их авторам!