Методы и алгоритмы построения элементов систем статистического моделирования

В свою очередь, эргодические цепи могут быть регулярными или

циклическими. Циклические цепи отличаются от регулярных тем, что в процессе

переходов через определенное количество шагов (циклов) происходит возврат в

какое-либо состояние. Регулярные цепи этим свойством не обладают. Если

просуммировать все вышесказанные определения, то можно дать следующую

классификацию марковских процессов (рис. 9):

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

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

В дальнейшем рассматриваются простые однородные марковские цепи с

дискретным временем. Основным математическим соотношением для ДМЦ является

уравнение, с помощью которого определяется состояние системы на любом ее k-

м шаге. Это уравнение имеет вид:

[pic] (4)

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

Уравнение Колмогорова-Чепмена относится к классу рекуррентных

соотношений, позволяющих вычислить вероятность состояний марковского

случайного процесса на любом шаге (этапе) при наличии информации о

предшествующих состояниях.

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

марковской цепи.

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

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

из одного или нескольких поглощающих состояний.

Для примера рассмотрим переходную матрицу, описывающую переходы в

системе, имеющей 4 возможных состояния, два из которых являются

поглощающими. Матрица перехода такой цепи будет иметь вид:

[pic] (5)

Практически важным является вопрос о том, сколько шагов сможет пройти

система до остановки процесса, то есть поглощения в том или ином состоянии.

Для получения дальнейших соотношений путем переименования состояний матрицу

(8.5) переводят к блочной форме:

[pic] (6)

[pic]

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

[pic] (6а)

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

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

[pic] - матрица, описывающая переходы в системе из невозвратного

множества состояний в поглощающее множество;

[pic] - матрица, описывающая внутренние переходы в системе в

невозвратном множестве состояний.

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

фундаментальной:

[pic] (7)

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

[pic] (8)

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

[pic] (7а)

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

системы в то или иное состояние до остановки процесса (поглощения).

Если необходимо получить общее среднее количество раз попадания

системы в то или иное состояние до поглощения, то фундаментальную матрицу

М необходимо умножить справа на вектор-столбец, элементами которого будут

единицы, то есть

[pic] (8а)

где [pic].

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

значения переходных вероятностей матрицы [pic] с одним поглощающим

состоянием: [pic]; [pic]; [pic]; [pic]; [pic]; [pic]; [pic]; [pic].

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

[pic]

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

[pic]; [pic]; [pic] ; [pic]

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

[pic];

[pic] .

В данном случае компоненты вектора [pic] означают, что если процесс

начинается с состояния [pic], то общее среднее число шагов процесса до

поглощения будет равно 3,34 и, соответственно, если процесс начинается с

состояния [pic], то - 2,26.

В конкретных задачах, конечно, более информативным результатом будет

не количество шагов, а какие-либо временные или экономические показатели.

Этот результат легко получить, если связать пребывание в каждом состоянии с

соответствующими характеристиками. Очевидно, набор этих характеристик

составит вектор, на который нужно умножить [pic] слева.

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

[pic] [pic], а в состоянии [pic]- [pic], то общее время до поглощения будет

равно:

[pic]

В случаях, когда марковская цепь включает несколько поглощающих

состояний, возникают такие вопросы: в какое из поглощающих состояний цепь

попадет раньше (или позже); в каких из них процесс будет останавливаться

чаще, а в каких - реже? Оказывается, ответ на эти вопросы легко

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

Обозначим через [pic] вероятность того, что процесс завершится в

некотором поглощающем состоянии [pic] при условии, что начальным было

состояние [pic]. Множество состояний [pic] снова образует матрицу, строки

которой соответствуют невозвратным состояниям, а столбцы - всем поглощающим

состояниям. В теории ДМЦ доказывается, что матрица В определяется следующим

образом:

[pic] (8.9)

где

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

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

Рассмотрим конкретный пример системы с четырьмя состояниями [pic],

два из которых- [pic]- поглощающие, а два - [pic]- невозвратные (рис.10):

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

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

следующим образом:

[pic]; [pic]; [pic]

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

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

[pic]

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

[pic]

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

вычисляется так:

[pic].

Поясним вероятностный смысл полученной матрицы с помощью конкретных

чисел. Пусть[pic], а[pic]. Тогда после подстановки полученных значений в

матрицу [pic]получим:

[pic]

Таким образом, если процесс начался в [pic], то вероятность попадания

его в [pic] равна [pic], а в [pic] - [pic]. Отметим одно интересное

обстоятельство: несмотря на то, что, казалось бы, левое поглощающее

состояние (“левая яма”) находится рядом с [pic], но вероятность попадания

в нее почти в два раза меньше, чем в “удаленную яму” - [pic]. Этот

интересный факт подмечен в теории ДМЦ, и объясняется он тем, что [pic], то

есть процесс имеет как бы “правый уклон”. Рассмотренная выше модель

называется в теории ДМЦ моделью случайного блуждания. Такими моделями часто

объясняются многие физические и технические явления и даже поведение

игроков во время различных игр.

В частности, в рассмотренном примере объясняется тот факт, что более

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

противнику и все равно его шансы на выигрыш будут более предпочтительными.

Кроме указанных выше средних характеристик вероятностного процесса с

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

порядков. В частности, дисперсия числа пребывания в том или ином состоянии

- D определяется с помощью следующей матрицы:

[pic] (10)

где

[pic] - диагональная матрица, т.е. матрица, полученная из М путем

оставления в ней лишь диагональных элементов и замены остальных элементов

нулями. Например, приведенная выше матрица (7а) будет иметь вид:

[pic]

В свою очередь, матрица М представляет собой матрицу, полученную из М

путем возведения в квадрат каждого ее элемента, то есть для (7а) будем

иметь:

[pic]

Аналогичным образом определяема и дисперсия для общего количества раз

пребывания в том или ином состоянии [pic]. Обозначим ее [pic]:

[pic] (11)

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

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

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

между состояниями. Напомним, что эргодические цепи могут быть регулярными и

циклическими. Ранее определение таких цепей было дано.

Поскольку согласно данному выше определению в эргодической ДМЦ на

любом шаге должны быть возможными любые переходы, то очевидно при этом, что

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

условия вытекают некоторые замечательные свойства регулярных ДМЦ:

1. Степени [pic] при [pic] стремятся к стохастической матрице [pic].

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

вектор

[pic] (12)

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

Вектор (12) в теории ДМЦ занимает особое место из-за наличия многих

приложений и называется вектором предельных или финальных вероятностей

(иногда - стационарным вектором). Финальные вероятности определяют с

помощью векторно-матричного уравнения

[pic] (13)

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

[pic] (13а)

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

[pic] (14)

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

Так же, как и в случае поглощения ДМЦ многие характеристики

эргодических цепей определяются с помощью фундаментальной матрицы, которая

в этом случае будет иметь вид:

[pic] (15)

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

значение, является продолжительность времени, за которое процесс из

состояния [pic] впервые попадает в [pic], так называемое время первого

достижения. Матрица средних времен достижения определяется по формуле:

[pic] (16)

где

[pic] - фундаментальная матрица (15);

[pic] - диагональная матрица, образованная из фундаментальной заменой

всех элементов, кроме диагональных, нулями;

D - диагональная матрица с диагональными элементами, [pic];

Е - матрица, все элементы которой равны единице.

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

сложный вид:

[pic] (17)

где кроме уже упомянутых обозначений встречается новое - ([pic],

обозначающее диагональную матрицу, полученную из матричного произведения

матриц [pic].

2.3. Управляемые марковские цепи

Как указывалось выше, под управляемыми марковскими процессами понимают

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

значениями переходных вероятностей. В качестве примеров таких процессов

можно привести любые торговые операции, у которых вероятность сбыта и

получения эффекта может зависеть от рекламы, мероприятий по улучшению

качества, выбора покупателя или рынка сбыта и т.д.

Очевидно, что при создании математических моделей в данном случае

должны фигурировать следующие компоненты:

- конечное множество решений (альтернатив) [pic], где [pic] - номер

состояния системы;

- матрицы переходов [pic]соответствующие тому или иному принятому k-му

решению;

- матрицы доходов (расходов) [pic], также отражающие эффективность

данного решения.

Управляемой цепью Маркова (УЦМ) называется случайный процесс,

обладающий марковским свойством и включающий в качестве элемента

математической модели конструкцию (кортеж) [pic]. Решение, принимаемое в

каждый конкретный момент (шаг процесса), назовем частным управлением.

Таким образом, процесс функционирования системы, описываемой УЦМ,

выглядит следующим образом:

- если система находится в состоянии [pic] и принимается решение [pic],

то она получает доход [pic];

- состояние системы в последующий момент времени (шаг) определяется

вероятностью [pic], то есть существует вероятность того, что система

из состояния [pic] перейдет в состояние [pic], если выбрано решение

[pic].

Очевидно, общий доход за n шагов является случайной величиной,

зависящей от начального состояния и качества принимаемых в течение хода

процесса решений, причем это качество оценивается величиной среднего

суммарного дохода (при конечном времени) или среднего дохода за единицу

времени (при бесконечном времени).

Стратегией ( называется последовательность решений:

[pic] (18)

где

[pic]- вектор управления.

Задание стратегии означает полное описание конкретных решений,

принимаемых на всех шагах процесса в зависимости от состояния, в котором

находится в этот момент процесс.

Если в последовательности (векторе) ( все [pic] одинаковы, то такая

стратегия называется стационарной, т.е. не зависящей от номера шага.

Стратегия [pic] называется марковской, если решение [pic], принимаемое в

каждом конкретном состоянии, зависит только от момента времени n, но не

зависит от предшествующих состояний.

Оптимальной будет такая стратегия, которая максимизирует полный

ожидаемый доход для всех i и n. В теории УМЦ разработаны два метода

определения оптимальных стратегий: рекуррентный и итерационный.

Первый, рекуррентный, метод применяется чаще всего при сравнительно

небольшом числе шагов n. Его идея основана на применении принципа

Беллмана и заключается в последовательной оптимизации дохода на каждом шаге

с использованием рекуррентного уравнения следующего вида:

[pic] (19)

где

[pic] - полный ожидаемый доход;

[pic] шагов, если система находится в состоянии i;

[pic] - непосредственно ожидаемый доход, т.е. доход на одном

шаге, если процесс начался с i-го состояния;

[pic] - величина полного ожидаемого дохода за n прошедших шагов,

если процесс начинался с j-го состояния (i(j).

Таким образом, данный метод, по существу, аналогичен методу

динамического программирования, отличием является лишь то, что на каждом

шаге учитывается вероятность попадания системы в то или иное состояние.

Поэтому этот метод называют стохастическим динамическим программированием.

Конкретное применение метода будет рассмотрено далее на примере.

Второй - итерационный метод оптимизации применяется при неограниченном

числе этапов (шагов) процесса. Этот метод использует свойство эргодичности

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

повторных расчетов (итераций). При этих уточнениях находят решение,

обеспечивающее в среднем минимум дохода при большом числе шагов. Оно уже не

будет зависеть от того, на каком шаге производится оценка оптимальной

стратегии, то есть является справедливым для всего процесса, независимо от

номера шага. Важным достоинством метода является, кроме того, и то, что он

дает возможность определить момент прекращения дальнейших уточнений.

Главное отличие итерационного метода от рассмотренного ранее,

рекуррентного, заключается в том, что в данном случае используется матрица

предельных (финальных) вероятностей, где вследствие свойства эргодичности

переходные вероятности постоянны на всех шагах процесса. Поскольку матрица

доходов состоит также из постоянных, не зависимых от n величин, то можно

предположить, что с ростом n общая величина доходов будет возрастать

линейно.

Представим графически линейную зависимость суммарного дохода от числа

шагов [pic] (рис. 11).

Для наглядности график (см. рис. 11) изображен для УМЦ с двумя

состояниями [pic] и [pic]. На графике прямая [pic] показывает зависимость

суммарного дохода, если система “стартовала” из состояния [pic].

Соответственно, прямая [pic] изображает ту же зависимость для состояния

[pic]. Обе прямые могут быть описаны линейными уравнениями [pic]:

[pic] (20)

где

g - угловой коэффициент прямой [pic];

[pic] - доход в i-том состоянии в конце процесса.

Легко заметить, что при таком представлении зависимости [pic] величина

непосредственно ожидаемого дохода q (см. формулу (19)) заменяется g.

Отличие здесь лишь в том, что g является величиной постоянной для всего

процесса, в то время как q меняется на каждом шаге. Величина [pic]

показывает, на сколько в среднем отличается доход, когда процесс

заканчивается в том или ином состоянии. В теории марковских цепей [pic]

называют весом, так как разница [pic] при двух состояниях показывает

средний выигрыш от того, в каком состоянии мы находимся в конце процесса

(независимо от выбранной стратегии).

Рис. 11. Зависимость суммарного дохода от числа шагов

Таким образом, подводя итоги общих рассуждений, можно сказать, что

свойство эргодичности позволяет нам считать справедливым приближенное

равенство:

[pic] (21)

На этом предположении и основан итерационный метод. Суть его сводится

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

определяются значения сумм

[pic] (22)

Таким образом, если ранее (при рекуррентном методе) искалась

стратегия, обеспечивающая на каждом шаге максимум суммы непосредственно

ожидаемого дохода и дохода на предшествующих шагах, то здесь находится

стратегия, обеспечивающая максимум средней прибыли и относительного веса

сразу для всего процесса. При этом производятся последовательные расчеты -

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

и весов, обеспечивающие максимум доходов.

-----------------------

СО

ДПр

ГПЗ

ГРРСЧ

ПИД

СО

ИС

ГСП

ГРРСЧ

ПИД

f(x)

F(x)

1/(a-b)

Si+1

[pic]

Марковские

процессы

[pic]

с дискретным временем

с непрерывным временем

однородные

неоднородные

управляемые

неуправляемые

марковские цепи

полумарковские цепи

простые

сложные

поглощающие

эргодические

регулярные

циклические

Страницы: 1, 2

МЕНЮ

Методы и алгоритмы построения элементов систем статистического моделирования

ИНТЕРЕСНОЕ