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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ НАУКИ РФ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ ЭЛЕКТРОНИКИ И АВТОМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

КАФЕДРА ТЕХНИЧЕСКИХ И ИНФОРМАЦИОННЫХ СРЕДСТВ СИСТЕМ УПРАВЛЕНИЯ

КУРСОВОЙ ПРОЕКТ ПО ДИСЦИПЛИНЕ

«МОДЕЛИРОВАНИЕ СИСТЕМ»

на тему:

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

Выполнил студент группы                         ИТБС-1-08

          А.А. Ивченко

(Инициалы, Фамилия)

Руководитель      И.О. Дементьев

(Инициалы, Фамилия)

МОСКВА 2011

Содержание:

Введение.             

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

Дискретный Марковский процесс с дискретным временем. Марковская однородная цепь.             

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

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

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

Пуассоновский стационарный (простейший) поток событий.             

Экономическое применение.             

Литература:             

Приложение.             

Введение.

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

Условие статической устойчивости позволяет использовать в процессе принятия решений эффективные математические методы теории случайных процессов и, в частности, одного из ее разделов - теории Марковских процессов.[1]

Функционирование широкого класса систем можно представить как процесс перехода из одного состояния в другое под воздействием каких-либо причин. Например, процесс функционирования ЭВМ характеризуется тем, что в каждый момент времени обработкой информации заняты те или иные блоки. Процесс прохождения обрабатываемой информации по блокам ЭВМ можно рассматривать как процесс перехода системы из одного состояния в другое. В полной мере это относится и к процессу функционирования ЭВМ с точки зрения надежности. В каждый момент времени некоторые узлы работоспособны, а некоторые отказали и восстанавливаются. Если каждому возможному множеству работоспособных (или отказывающих) элементов поставить в соответствие множество состояний системы, то отказы и восстановления элементов будут отражаться переходом объекта из одного состояния в другое. [4]

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

Управление инвестиционным портфелем является типичной задачей исследования операций. В ней присутствуют все атрибуты канонической постановки:

      динамика цен на обращаемые бумаги рассматривается как случайный Марковский процесс с дискретным временем;

      цель операции носит многокритериальный характер (ожидаемый выигрыш, риск, ликвидность и т.п.);

      процесс развивается в динамике.

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

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

Рассматриваемые процессы, обладают определенным свойством и представляют собой базу вероятностных моделей специального вида. Они названы Марковскими по имени впервые их исследовавшего математика А.А. Маркова.

Напомним для начала некоторые понятия. Случайным процессом или синонимически случайной функцией S(t) , где t – время, называется функция, которая каждому моменту времени t из временного промежутка проводимого опыта ставит в соответствие единственную случайную величину S(t).

Значит аргументом случайной функции является время, а ее значением – случайная величина. Таким образом, случайная величина характеризует изменение случайной величины в процессе опыта.

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

Связи между элементами системы в одну или обе стороны могут быть как непосредственными, так и опосредованными. Элементы системы и связи между ними изменяются, вообще говоря, во времени и характеризуют в каждый момент времени t состояние S(t) системы S.

Если система S с течением времени t изменяет свои состояния S(t) случайным образом, то говорят, что в системе S протекает случайный процесс. В любой момент времени система пребывает только в одном из состояний, то есть для любого момента времени t найдется единственное состояние Si такое, что S(t) = Si. Если множество состояний не более чем счетно, то оно дискретно. Если множество состояний более чем счетно, то оно непрерывно. [3]

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

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

Случайный процесс, протекающий в системе S, называется Марковским, если он обладает свойством отсутствия последствия, состоящим в том, что для каждого момента времени t0 вероятность любого состояния S(t) системы S в будущем (при t>t0) зависит только от ее состояния S(t0) в настоящем (при t=t0) и не зависит от того, как и сколько времени развивался этот процесс в прошлом (при t>t0).

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

При исследовании непрерывных и дискретных случайных цепей обычно пользуются графическим представлением функционирования системы. Граф состояний системы представляет собой совокупность вершин, изображающих возможные состояния системы Si, и совокупность ветвей, изображающих возможные переходы системы из одного состояния в другое. [4]

Дискретный Марковский процесс с дискретным временем. Марковская однородная цепь.

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

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

Случайный процесс с дискретным временем можно представить случайной последовательностью (по индексу k) этих событий которую называют также цепью.

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

Так как система в любой момент t может пребывать только в одном из состояний , то при каждом k=1,2,… события несовместны и образуют полную группу.

Основными характеристиками Марковских цепей являются вероятности событий .

Вероятности называются вероятностями состояний.

Таким образом, вероятность i состояния на k шаге есть вероятность того, что система S от k до (k+1) шага будет пребывать в состоянии . Сумма вероятностей этих событий для каждого равна 1: . Если переходные вероятности не зависят от шагов k, то Марковская цепь называется однородной. Если же хотя бы одна вероятность изменяется с изменением шага k, то цепь называется неоднородной. Запишем переходные вероятности в виде квадратной матрицы n порядка, сумма элементов каждой строки равна 1.

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

Для однородной Марковской цепи вектор-строка вероятностей состояний от k до (k+1) шага, равна произведению вектора-строки вероятностей состояний от (k-1) до k шага на матрицу переходных вероятностей: .

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

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

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

Основными вероятностными прогнозными характеристиками Марковской цепи являются вероятности состояний на любом шаге .[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 час, то общее время до поглощения будет равно: час.

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