Пример: Транспортная логистика
Я ищу:
На главную  |  Добавить в избранное  

Экономико-математическое моделирование /

Дискретный марковский процесс

←предыдущая следующая→
1 2 3 4 



Скачать реферат


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

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

Основными вероятностными прогнозными характеристиками Марков-ской цепи являются вероятности состояний на любом шаге .[1]

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

Разложимые Марковские цепи содержат невозвратные состояния, назы-ваемые поглощающими. Из поглощающего состояния нельзя перейти ни в какое другое. На графе поглощающему состоянию соответствует вершина, из которой не выходит ни одна дуга. В установившемся режиме поглощающему состоянию соответствует вероятность, равная 1.

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

Для эргодических цепей при достаточно большом времени функциони-рования (t стремится к бесконечности) наступает стационарный режим, при котором вероятности состояний системы не зависят от времени и не зави-сят от распределения вероятностей в начальный момент времени, т.е. .[4]

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

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

Для примера рассмотрим переходную матрицу, описывающую переходы в системе, имеющей 4 возможных состояния, два из которых являются по-глощающими. Матрица перехода такой цепи будет иметь вид: Практически важным является вопрос о том, сколько шагов сможет пройти система до остановки процесса, то есть по-глощения в том или ином состоянии. Для получения дальнейших соотноше-ний путем переименования состояний матрицу (1) переводят к блочной фор-ме: Такая форма позволяет представить матрицу (2) в каноническом виде: ,

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

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

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

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

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

Для иллюстрации приведем конкретный числовой пример: пусть извест-ны значения переходных вероятностей матрицы с одним поглощающим состоянием: P11 = 1; P12 = P13 = 0; P21 = 0,25; P22 = 0,5; P23 = 0,25; P31 = 0,5; P32 = 0,5; P33 = 0.

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

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

;

;

.

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

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

Так, если задать в нашем примере время пребывания в состоянии S2 - t2 = 20 час, а в состоянии S3 - t3 = 30 час, то общее время до поглощения будет равно: час.

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

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

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

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

Рассмотрим конкретный пример системы с четырьмя состояниями S1- S4, две из которых - S1 , S2 - поглощающие, а две - невозвратные: S3 и S4. Для на-глядности и простоты вычислений обозначим переходные вероятности сле-дующим образом:

P11 = P22 = 1; P31 = P43 = q; P34 = P42 = P.

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

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

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

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

Таким образом, если процесс начался в S3, то вероятность попадания его в S1 равна 0,38 , а в S2 - 0,62. Отметим одно интересное обстоятельство: не-смотря на то, что, казалось бы, левое поглощающее состояние ("левая яма") находится рядом с S3, но вероятность попадания в нее почти в два раза меньше, чем в "удаленную яму" - S2 . Этот интересный факт подмечен в тео-рии дискретных Марковских процессов и объясняется он тем, что p q , то есть процесс имеет как бы "правый уклон". Рассмотренная выше модель на-зывается в теории дискретных Марковских процессов моделью случайного блуждания. Такими моделями часто объясняются многие физические и тех-нические явления и даже поведение игроков во время различных игр.

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

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

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

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

Марковская неоднородная цепь.

Допустим, что в системе S протекает Марковский дискретный процесс с дискретным временем. Пусть - возможные состояния системы S и - шаги, в которые система может перескакивать из состояния в состояние, то есть иметь Марковскую цепь.

Марковская цепь называется неоднородной, если переходные вероятно-сти (хотя бы одна) зависят от номера шага k.

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

Для неоднородной Марковской цепи вектор-строка вероятностей со-стояний (1)

Для неоднородной Марковской цепи имеет место следующая формула: (2)

У неоднородной Марковской цепи переходные вероятности (хотя бы одна из них) и, следовательно, матрица переходных вероятностей за-висят от номера k.

Вероятности состояний неоднородной Марковской цепи на каждом шаге k вычисляется либо по реккурентной формуле (1), либо по формуле (2) , где - вектор начального распределения вероятно-стей состояний системы. [1]

Дискретный Марковский случайный процесс с непрерывным временем.

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

Пусть - всевозможные состояния системы S. Вероятность события , состоящего в том, что система S в момент времени t находится в состоянии Si, называется вероятностью i-ого состояния системы в момент времени. Вероятность состояния является, таким образом, вероятностной функцией времени .

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

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

←предыдущая следующая→
1 2 3 4 



Copyright © 2005—2007 «Mark5»