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

Текст из файла (страница 11)

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

а
) существенное состояние (рис.7): возможны переходы из в и обратно.

Рис. 7. Существенное состояние

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

Р
ис. 8. Несущественное состояние

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

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

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

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

Рис. 9. Классификация марковских процессов

Математический аппарат дискретных марковских цепей

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

(4)

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

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

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

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

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

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

(5)

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

(6)

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

(6а)

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

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

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

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

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

(7)

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

(8)

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

(7а)

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

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

(8а)

где .

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

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

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

; ; ;

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

;

;

.

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

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

Так, если задать в нашем примере время пребывания в состоянии , а в состоянии - , то общее время до поглощения будет равно:

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

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

(8.9)

где

М - фундаментальная матрица с размерностью S;

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

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

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

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

; ;

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

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

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

.

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

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

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

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

(10)

где

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

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

Характеристики

Список файлов ответов (шпаргалок)