Эргодические и поглощающие марковские цепи

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

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

Из поглощающего состояния нельзя перейти ни в какое другое. В матрице переходных вероятностей поглощающему состоянию соответствует строка, в которой все переходные вероятности p_ij=0, кроме одной (диагональной) p_ii=1.

Для эргодических цепей характерно то, что при достаточно большом шаге k наступает стационарный (установившийся) режим, при котором вероятности состояний p_i(k) практически не изменяются с течением времени, т.е. . Вектор P_С = [p_ci] = [p_c1, p_c2, …, p_cN] называется вектором стационарных вероятностей. До наступления стационарного режима система находится в переходном режиме. Переходный режим заканчивается, когда ||P_C ‑ P(k)||<e, где e - сколь угодно малая ­положительная величина. Каждая компонента p_ci вектора стационарных вероятностей характеризует среднюю долю времени, в течение которого система находится в состоянии S_i. Если все состояния цепи являются сообщающимися, то вся цепь является эргодической. В такой системе из любого состояния можно попасть в любое за конечное число шагов, в матрице переходных вероятностей нет нулевых элементов, а граф системы является сильно связанным.

Для определения стационарных вероятностей p_ci нахождения системы в состоянии S_i нужно составить систему N линейных алгебраических уравнений с N неизвестными:

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

Для системы на рисунке 2.6 выполняется:

p_С1=p_С2p₂₁+p_С3p₃₁

p_С2=p_С1p₁₂+p_С4p₄₂

p_С3=p_С1p₁₃+p_С4p₄₃

p_С4=p_С2p₂₄+p_С3p₃₄

Условие нормировки: p_С1+p_С2 +p_С3+p_С4=1

Эта система уравнений переопределена, есть линейно-зависимые уравнения.

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

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

В установившемся режиме, независимо от начального состояния, вероятность нахождения поглощающей марковской цепи в поглощающем состоянии близка к единице, а вероятности остальных состояний близки к нулю. Для примера на рисунке p_С1= p_С2 = p_С3= 0, p_С4=1.В связи с этим для исследования интересен только переходный режим.

Пример[1].Требуется построить математическую модель и определить основные характеристики системы обработки информации, содержащей канал передачи информации К, буфер Б, специализированное вычисли­тель­ное устройство В. На вход системы поступает информация, гене­рируемая источником входной информации И.

Рис.2.8. Пример системы обработки информации.

Схема работы вычислительной системы следующая. Источник И выдает один пакет сразу, как только освобождается канал К. Канал К передает пакет в течение двух тактов. В канале может находиться только один пакет. Если буфер занят, канал хранит пакет, но блокируется по входу. Буфер Б может хранить от 0 до N пакетов. Если буфер занят полностью, он не принимает новый пакет. Буфер выдает пакет вычислителю В сразу, как только вычислитель освобождается и тут же может принять новый пакет. Вычислитель В обрабатывает пакет в течение одного такта и выводит его из системы. С вероятностью p происходит сбой, и обработка пакета повторяется.

Введем множество состояний.

Канал К может находиться в одном из трех состояний:

k=1 – пакет принят и находится в начале передачи (передастся через 2 такта);

k=2 – пакет находится в середине передачи (передастся через 1 такт);

k=0 – передача пакета завершена, но буфер занят и канал заблокирован.

Буфер Б может находиться в одном из N+1 состоянии:

n=0 – буфер свободен;

n=1, 2,…, N – в буфере находятся 1, 2,…, N пакетов.

Вычислитель В может находиться в одном из двух состояний:

i=0 – вычислитель свободен; i=1 – вычислитель занят.

Состояние системы S на каждом такте описывается вектором трех компонентов (k, n, i).||S|| = 3∙(N+1)∙2, хотя некоторые состояния являются невозможными.

Построим граф марковской цепи и определим переходные вероятности (рис.2.9).

Начнем с состояния (0,N,1) – вычислитель занят, буфер занят, канал заблокирован и содержит один пакет, готовый к передаче в буфер. Из этого состояния возможны два перехода:

Рис.2.9. Граф марковской цепи, описывающей работу вычислительной системы

Состояние (0,N,1) –

с вероятностью p произойдет сбой и произойдет возврат в то же состояние (на рис. 2.9 этому случаю соответствует дуга)

с вероятностью 1-p пакет будет обработан, В освободится и тут же будет занят пакетом из буфера (i=1), Б уменьшится и тут же будет вновь заполнен пакетом из К (n=N), канал освободится и тут же получит новый пакет, который будет находиться в начале передачи (k=1). То есть произойдет переход в новое состояние (1,N,1).

Состояние(1,N,1) –

с вероятностью p произойдет сбой, В по-прежнему будет занят (i=1), Б по-прежнему будет заполнен (n=N), пакет по каналу перейдет на следующую стадию (k=2). Новое состояние (2,N,1).

с вероятностью 1-p пакет будет обработан,В освободится и тут же будет занят пакетом из буфера (i=1), в Б станет на один пакет меньше (n=N-1), пакет по каналу перейдет на следующую стадию (k=2). Новое состояние (2,N-1,1).

Состояние(2,N,1) –

с вероятностью p произойдет сбой, В по-прежнему будет занят (i=1), Б по-прежнему будет заполнен (n=N), пакет по каналу завершит передачу и канал заблокируется (k=0). Новое состояние (0,N,1).

с вероятностью 1-p пакет будет обработан,В освободится и тут же будет занят пакетом из буфера (i=1), Б уменьшится и тут же будет вновь заполнен пакетом из К (n=N), канал освободится и тут же получит новый пакет, который будет находиться в начале передачи (k=1). Новое состояние (1,N,1).

Состояние(2,N-1,1) –

с вероятностью p произойдет сбой, В по-прежнему будет занят (i=1), в Б поступит новый пакет (n=N), канал освободится и тут же получит новый пакет, который будет находиться в начале передачи (k=1). Новое состояние (1,N,1).

с вероятностью 1-p пакет будет обработан,В освободится и тут же будет занят пакетом из буфера (i=1), Б уменьшится и тут же будет вновь заполнен пакетом из К (n=N-1), канал освободится и тут же получит новый пакет, который будет находиться в начале передачи (k=1). Новое состояние (1,N-1,1).

И так далее… Перейдем к рассмотрению завершающих состояний.

Состояние(1,0,1) –

с вероятностью p произойдет сбой, В по-прежнему будет занят (i=1), Б по-прежнему будет свободен (n=0), пакет по каналу перейдет на следующую стадию (k=2). Новое состояние (2,0,1).

с вероятностью 1-p пакет будет обработан,В освободится и поскольку в буфере пакетов нет, останется свободным (i=0), Б по-прежнему будет свободным (n=0), пакет по каналу перейдет на следующую стадию (k=2). Новое состояние (2,0,0).

Состояние(2,0,0) – сбой произойти не может, так как вычислитель не работает, пакет из канала завершит передачу и поступит в Б, а затем сразу в В (i=1, n=0), канал по­лучит новый пакет из источника (k=1). Новое состояние (1,0,1) с вероятностью 1.

Матрица переходных вероятностей содержит 6∙(N+1) строк и столбцов. В матрице есть нулевые строки (для невозможных состояний). В каждой ненулевой строке один элемент равен p, другой 1-p, остальные – нулевые, так как из каждого состояния возможен переход только в два других состояния. В строке, соответствующей состоянию (2,0,0), один элемент равен 1, остальные – 0.

Составим систему уравнений для нахождения стационарных вероятностей.

p(0,N,1) = p∙p(0,N,1)+p∙p(2,N,1),

p(1,N,1) = (1-p)∙p(0,N,1) + (1-p)∙p(2,N,1) + p∙p(2,N-1,1),

p(2,N,1) = p∙p(1,N,1),

………………

для n=N-1, N-2,…, 1:

p(1,n,1) = p∙p(2,n-1,1) + (1-p)∙p(2,n,1),

p(2,n,1) = p∙p(1,n,1) + (1-p)∙p(1,n+1,1),

………………

для n = 0:

p(2,0,1) = p∙p(1,0,1) + (1-p)∙p (1,1,1),

p(1,0,1) = p(2,0,0) + (1-p)∙p(2,0,1),

p(2,0,0) = (1-p)∙p(1,0,1).

Кроме того, выполняется условие нормировки: .

Обозначим p(2,0,0) = p; p/(1-p) = w.

Из последнего уравнения: p(1,0,1) = .

Из предпоследнего: = = .

Из пред-предпоследнего: p(1,1,1)= = = .

и так далее…

p(1,n,1)= ,

p(2,n,1)= .

Из первых трех уравнений вытекает:

из первого

;

из второго (с учетом, что p(2,N,1) = p∙p(1,N,1)):

p(1,N,1) = (1-p) v p p(1,N,1) + (1-p) p p(1,N,1) + p

p(1,N,1) = p(1,N,1)((1-p)vp+(1-p)p) + v^2N p

p(1,N,1) =

p(2,N,1) = v^2N+1 p

p(0,N,1) = v^2N+2 p

из условия нормировки:

=

отсюда p = ( )^-1

Можно определить стационарные вероятностные характеристики системы. Например, вероятность того, что вычислитель простаивает p(2,0,0) = p, вероятность того, что канал простаивает p(0,N,1) = v^2N+2 p.

Самостоятельно определите вероятность того, что в буфере находятся i пакетов; больше, чем i пакетов.