Вероятности состояний Марковских моделей

Множество состояний системы марковской цепи определенным образом классифицируются с учетом дальнейшего поведения системы:

1. Невозвратное множество

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

2. Возвратное множество

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

3. Эргодическое множество

В случае эргодического множества возможны любые переходы внутри множества, но исключены переходы из множества и в него.

4. Поглощающее множество

При попадании системы в это множество процесс заканчивается.

Кроме описанной выше классификации множеств различают состояния системы:

а) существенное состояние возможны переходы из S_i в S_j и обратно

б) несущественное состояние возможен переход из S_i в S_j, но невозможен обратный.

В некоторых случаях, несмотря на случайность процесса, имеется возможность до определенной степени управлять законами распределения или параметрами переходных вероятностей. Такие марковские цепи называются управляемыми. Очевидно, что с помощью управляемых цепей Маркова (УЦМ) особенно эффективным становится процесс принятия решений.

Основным признаком детерминированной марковской цепи (ДМЦ) является детерминированность временных интервалов между отдельными шагами (этапами) процесса. Однако, часто в реальных процессах это свойство не соблюдается и интервалы оказываются случайными с каким-либо законом распределения, хотя марковость процесса сохраняется. Такие случайные последовательности называются полумарковскими.

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

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

Далее будут рассмотрены простые однородные марковские цепи с дискретным временем. Основным математическим соотношением для ДМЦ является уравнение, с помощью которого определяется состояние системы на любом k -том ее шаге. Это уравнение имеет вид:

(7.3)

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

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

Дальнейшие математические соотношения зависят от конкретного вида марковской цепи.

Поглощающие марковские цепи

Как указывалось выше, у поглощающих ДМЦ имеется множество, состоящее из одного или нескольких поглощающих состояний.

Для примера рассмотрим переходную матрицу, описывающую переходы в системе, имеющей 4 возможных состояния, два из которых являются поглощающими. Матрица перехода такой цепи будет иметь вид:

(7.4)

Практически важным является вопрос о том, сколько шагов сможет пройти система до остановки процесса, то есть поглощения в том или ином состоянии. Для получения дальнейших соотношений путем переименования состояний матрицу (7.4) переводят к блочной форме:

(7.5)

Такая форма позволяет представить матрицу (7.5) в каноническом виде:

,

(7.5а)

где

- единичная матрица;

- нулевая матрица;

- матрица, описывающая переходы в системе из невозвратного множества состояний в поглощающее множество;

- матрица, описывающая внутренние переходы в системе в невозвратном множестве состояний.

На основании канонической формы (7.5а) получена матрица, называемая фундаментальной.

M [2] = (I [2] - Q [2]) ^-1,

(7.6)

В матрице (7.6) символ (^-1) означает операцию обращения, то есть

М ∙ М ^-1 = 1.

(7.7)

После соответствующих преобразований матрица (4) примет вид:

.

(7.8)

Каждый элемент матрицы (7.8) соответствует среднему числу раз попадания системы в то или иное состояние до остановки процесса (поглощения).

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

М = М ∙ x <2> ,

(7.9)

где .

Для иллюстрации приведем конкретный числовой пример: пусть известны значения переходных вероятностей матрицы П_[3] с одним поглощающим состоянием: P ₁₁ = 1; P ₁₂ = P ₁₃ = 0; P ₂₁ = 0,25; P ₂₂ = 0,5; P ₂₃ = 0,25; P ₃₁ = 0,5; P ₃₂ = 0,5; P ₃₃ = 0.

Рис. 7.1

Переходная матрица в блочной системе будет выглядеть так:

.

В данном случае

Проделаем необходимые вычисления:

.

 

В данном случае компоненты вектора М _S означают, что если процесс начался с состояния S ₂ общее среднее число шагов процесса до поглощения будет равно 3,34 и, соответственно, если процесс начинается с состояния S ₃ , то - 2,26.

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

Так, если задать в нашем примере время пребывания в состоянии S ₂ t ₂ = 20 час, а в состоянии S ₃ - t ₃ = 30 час, то общее время до поглощения будет равно:

В случаях, когда марковская цепь включает несколько поглощающих состояний, возникают такие вопросы: в какое из поглощающих состояний цепь попадет раньше (или позже); в каких из них процесс будет останавливаться чаще, а в каких - реже? Оказывается, ответ на эти вопросы легко получить, если снова воспользоваться фундаментальной матрицей.

Обозначим через b_ij вероятность того, что процесс завершится в некотором поглощающем состоянии S_j при условии, что начальным было состояние S_i. Множество состояний b_ij снова образует матрицу, строки которой соответствуют невозвратным состояниям, а столбцы - всем поглощающим состояниям. В теории ДМЦ доказывается, что матрица В определяется следующим образом:

,

(7.10)

где М - фундаментальная матрица с размерностью S; R - блок фундаментальной матрицы с размерностью r.

Рассмотрим конкретный пример системы с четырьмя состояниями S ₁ - S ₄, две из которых - S ₁, S ₂ - поглощающие, а две - невозвратные: S ₃ и S ₄ (рис.7.2):

S ₁ S ₂ S ₃ S ₄

 

Рис. 7.2. Система с четырьмя состояниями

Для наглядности и простоты вычислений обозначим переходные вероятности следующим образом:

P ₁₁ = P ₂₂ = 1; P ₃₁ = P ₄₃ = q; P ₃₄ = P ₄₂ = P.

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

П[4] =	S 1
S 2
S 3	q			p
S 4		p	q

или

П[4] =	I	O
R	Q

 

Фундаментальная матрица после вычислений примет вид:

.

Тогда, матрица вероятностей поглощения вычисляется так:

.

Поясним вероятностный смысл полученной матрицы с помощью конкретных чисел. Пусть p = 0.7, а q = 0.3. Тогда, после подстановки полученных значений в матрицу В, получим:

		S 1	S 2
B =	S 3	0,38	0,62
S 4	0,11	0,89

 

Таким образом, если процесс начался в S ₃, то вероятность попадания его в S ₁ равна 0,38, а в S ₂ - 0,62. Отметим одно интересное обстоятельство: несмотря на то, что, казалось бы, левое поглощающее состояние («левая яма») находится рядом с S ₃, но вероятность попадания в нее почти в два раза меньше, чем в «удаленную яму» - S ₂. Этот интересный факт подмечен в теории ДМЦ и объясняется он тем, что p > q, то есть процесс имеет как бы «правый уклон». Рассмотренная выше модель называется в теории ДМЦ моделью случайного блуждания. Такими моделями часто объясняются многие физические и технические явления и даже поведение игроков во время различных игр.

В частности, в рассмотренном примере объясняется факт того, что более сильный игрок может дать заранее значительное преимущество («фору») слабому противнику и все равно его шансы на выигрыш будут более предпочтительными.

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

,

(7.11)

где М_dg - диагональная матрица, т.е. матрица, полученная из М путем оставления в ней лишь диагональных элементов и замены остальных элементов нулями. Например, приведенная выше матрица (7.8) будет иметь вид:

.

В свою очередь, матрица М представляет собой матрицу, полученную из М путем возведения в квадрат каждого ее элемента, то есть для (7.8) будем иметь:

.

Аналогичным образом определяема и дисперсия для общего количества раз пребывания в том или ином состоянии М _z, Обозначим ее D _å.

.

(7.12)

 

Эргодические цепи

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

Поскольку согласно данному выше определению в эргодической ДМЦ на любом шаге должны быть возможными любые переходы, то очевидно при этом, что переходные вероятности не должны равняться нулю. Оказывается, из этого условия вытекают некоторые замечательные свойства регулярных ДМЦ:

1. Степени П_{[ n ]} ^k при к (r)0 стремятся к стохастической матрице A _{[ n ]};

2. Каждая строка матрицы А _{[ n ]} представляет один и тот же вероятностный вектор

a = < а 1, а 2,..., аn >,

(7.13)

все компоненты которого положительны.

Вектор (7.13) в теории ДМЦ занимает особое место из-за наличия многих приложений и называется вектором предельных или финальных вероятностей (иногда - стационарным вектором). Финальные вероятности определяют с помощью векторно-матричного уравнения

(7.14)

которое в развернутом виде будет выглядеть так:

(7.14а)

К уравнениям (7.14а) можно дополнительно добавить условие нормировки:

.

(7.15)

Тогда любое из уравнений в (7.15) можно исключить.

Также как и в случае поглощения ДМЦ многие характеристики эргодических цепей определяются с помощью фундаментальной матрицы, которая в этом случае будет иметь вид:

.

(7.16)

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

(13)

где M_z - фундаментальная матрица (12); M_zdg - диагональная матрица, образованная из фундаментальной, заменой всех элементов, кроме диагональных - нулями; D - диагональная матрица с диагональными элементами d_ij = 1/a _i; Е - матрица, все элементы которой равны единице.

Матрица дисперсий времени первого достижения имеет несколько более сложный вид:

(14)

где кроме уже упомянутых обозначений встречается новое - (М_z× М_t) _dg, обозначающее диагональную матрицу, полученную из матричного произведения матриц М_z× М_t.

 

ЛИТЕРАТУРА

1. Макаров И.М. и др. Теория выбора и принятия решений. -М.: Наука, 1982.

2. Медиченко М.П. Методы оптимального планирования и управления,ч.1, МО СССР, 1986.

5. Подиновский В.В. Математическая теория выработки решений в сложных ситуациях. МО СССР, 1981.

6. Ватага А.И., Бережной В.В. Математические методы анализа и синтеза сетей связи. Сборник задач. Часть 1. Ставрополь СВВИУС.

7. Бережной В.В., Ватага А.И. Математические методы анализа и синтеза сетей связи. Часть 2. Ставрополь ФРВИ РВ.

8. Бережной В.В. Математические методы анализа и синтеза сетей связи. Часть 3. Ставрополь ФРВИ РВ.

9. Ватага А.И., Бережной В.В. Малофей О.П. Математические методы анализа и синтеза сетей связи. Сборник задач. Часть 2. Ставрополь ФРВИ РВ, 2000.

10. Соболь И.М. Метод Монте-Карло, -М: Наука, 1985.

12. Моудер Дж. Исследование операций, т.1,2 -М: Мир, 1981.