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

 

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

ГОУ СПО  «ХАКАССКИЙ ПОЛИТЕХНИЧЕСКИЙ КОЛЛЕДЖ»

Специальность 230105

«ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ»

 

 

 

 

 

курсовая работа

по дисциплине   «МАТЕМАТИЧЕСКИЕ  МЕТОДЫ»

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Руководитель:

___________ О.Н. Горбачева

       (подпись)

_______________________

    (оценка, дата)

Выполнила: 

Студентка группы ПРО– 31

__________М. В. Слученкова

        (подпись)

________________________

          (дата)

 

 

 

 

Абакан 2011 год

Содержание

Введение 3

1. Теоретическая часть 5
1. Случайные процессы с дискретным временем 5
2. Марковский процесс с дискретным состоянием и не прерывным  
   временем. Уравнение Колмогорова 7
1. Непрерывные цепи Маркова 7
2. Уравнение Колмогорова 9
3. Потоки событий 11
4. Предельные вероятности состояний 12
5. Процессы гибели и размножения 13
2. Практическая часть 15
1. Постановка задачи 15
2. Составление математической модели 15
3. Решение задачи с помощью уравнения Колмогорова с помощью прикладных программ 15
4. Выбор программной среды 17
5. Основные блоки программы 18
6. Алгоритм программы 19
7. Тестирование и отладка программы 21

Заключение 22

Список  используемых источников 23

Приложение ……25

 

Введение

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

Для исследования изменения во времени  теория вероятностей конца XIX - начала XX века не имела ни разработанных  частных схем, ни тем более общих  приемов. А необходимость их создания буквально стучала в окна и  двери математической науки. Изучение броуновского движения в физике подвело  математику к порогу создания теории случайных процессов.

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

Во-первых, эта работы А.А. Маркова (1856-1922) по изучению цепных зависимостей. Во-вторых, работы Е.Е. Слуцкого (1880-1948) по теории случайных функций.

Оба этих направления играли очень  существенную роль в формировании общей  теории случайных процессов.

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

Оставалось осуществить глубокий анализ имеющихся работ, высказанных  в них идей и результатов и  на его базе осуществить необходимый  синтез.

Цель курсовой работы - на практическом примере продемонстрировать использование Марковского случайного процесса

Задачи:

1. Изучить теоретический материал по Марковским случайным процессам с дискретными состояниями.
2. Отобрать материал для курсовой работы.
3. Составить математическую модель задачи.
4. Рассмотреть методы решения задачи и выбрать оптимальный.
5. Решить задачу с помощью прикладных программ.
6. Составить алгоритм решения задачи для оптимального метода.
7. Выбрать оптимальную среду программирования и написать программу для решения задачи.
8. Отладить и протестировать программу.
9. Проанализировать результаты работы и сделать вывод.

 

1. Теоретическая часть

1. Случайные процессы с дискретным временем

Случайный процесс, протекающий в  некоторой системе S с возможными состояниями S₁, S₂, S₃, …, называется Марковским, или случайным процессом без последствия, если для любого момента времени t₀ вероятные характеристики процесса в будущем (при t>t₀) зависит только от его состояния в данный момент t₀ и не зависят от того, когда и как система пришла в это состояние; т.е. не зависят от её поведения в прошлом (при t<t₀).

Примером Марковского процесса: система S - счётчик в такси. Состояние  системы в момент t характеризуется  числом километров (десятых долей  километров), пройденных автомобилем  до данного момента. Пусть в момент t₀ счётчик показывает S₀/ Вероятность того, что в момент t>t₀ счётчик покажет то или иное число километров (точнее, соответствующее число рублей) S₁ зависит от S₀, но не зависит от того, в какие моменты времени изменились показания счётчика до момента t₀.

Многие процессы можно приближенно  считать Марковскими. Например, процесс  игры в шахматы; система S - группа шахматных  фигур. Состояние системы характеризуется  числом фигур противника, сохранившихся  на доске в момент t₀. Вероятность того, что в момент t>t₀ материальный перевес будет на стороне одного из противников, зависит в первую очередь от того, в каком состоянии находится система в данный момент t_0, а не от того, когда и в какой последовательности исчезли фигуры с доски до момента t₀.

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

Марковским случайным процессом  с дискретными состояниями и  дискретным временем (или цепью Маркова) называется Марковский процесс, в котором его возможные состояния S₁, S₂, S_3, … можно заранее перечислить, а переход из состояния в состояние происходит мгновенно (скачком), но только в определённые моменты времени t_0, t_1, t_2, ..., называемые шагами процесса.

Обозначим p_ij - вероятность перехода случайного процесса (системы S) из состояния I в состояние j. Если эти вероятности не зависят от номера шага процесса, то такая цепь Маркова называется однородной.

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

p₁₁ p₁₂ … p_1m

p₂₁ p₂₂ … p_2m

… … … …

P_m1 p_m2 … p_mm

Естественно, по каждой строке p_ij = 1, I = 1, 2, …, m.

Обозначим p_ij(n) - вероятностью того, что в результате n шагов система перейдёт из состояния i в состояние j. При этом при i = 1 имеем вероятности перехода, образующие матрицу P₁, т.е. p_ij(1) = p_ij

Необходимо, зная вероятности перехода P_ij, найти P_ij(n) - вероятности перехода системы из состояния I в состояние j за n шагов. С этой целью будем рассматривать промежуточное (между i и j) состояние r, т.е. будем считать, что из первоначального состояния i за k шагов система перейдёт в промежуточное состояние r с вероятностью p_ir(k), после чего за оставшиеся n-k шагов из промежуточного состояния r она перейдёт в конечное состояние j с вероятностью p_rj(n-k). Тогда по формуле полной вероятности

P_ij(n) = p_ir (k) p_rj (n-k) - равенство Маркова.

Убедимся в том, что, зная все  вероятности перехода p_ij = p_ij(1), т.е. матрицу P₁ перехода из состояния в состояние за один шаг, можно найти вероятность p_ij(2), т.е. матрицу P₂ перехода из состояния в состояние за два шага. А зная матрицу P₂, - найти матрицу P₃ перехода из состояния в состояние за три шага, и т.д.

Действительно, полагая n = 2 в формуле P_ij(n) = p_ir (k) p_rj (n-k), т.е. k=1 (промежуточное между шагами состояние), получим

P_ij(2) =  p_ir(1)p_rj (2-1) =p_ir p_rj

Полученное равенство означает, что P₂ =P₁P₁ = P²₁

Полагая n = 3, k = 2, аналогично получим P₃ = P₁P₂ = P₁P₁² = P₁³, а в общем случае P_n = P₁ⁿ

 

 

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

      1.2.1 Непрерывные цепи Маркова

 

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

Рис. 1.1. Пример графа переходов

 

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

 

Ясно, что у каждого  состояния сумма вероятностей всех переходов (исходящих стрелок) из него в другие состояния должна быть всегда равна 1 (см. рис. 1.2).

Рис. 1.2. Фрагмент графа переходов 
(переходы из i-го состояния являются полной группой случайных событий)

 

Например, полностью граф может выглядеть так, как показано на рис. 1.3.

Рис. 1.3. Пример Марковского графа переходов

 

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

 

Рис. 1.4. Пример Марковской цепи, смоделированной 
по Марковскому графу, изображенному на рис. 33.3

Чтобы определить, в какое  новое состояние перейдет процесс  из текущего i-го состояния, достаточно разбить интервал [0; 1] на подынтервалы величиной Pi1, Pi2, Pi3, … (Pi1 + Pi2 + Pi3 + … = 1), см. рис.1.5. Далее с помощью ГСЧ надо получить очередное равномерно распределенное в интервале [0; 1] случайное число грр и определить, в какой из интервалов оно попадает.

Рис. 1.5. Процесс моделирования перехода из i-го 
состояния Марковской цепи в j-е с использованием 
генератора случайных чисел

 

После этого осуществляется переход в состояние, определенное ГСЧ, и повтор описанной процедуры  для нового состояния. Результатом  работы модели является Марковская цепь (см. рис. 1.4).

 

1.2.2 Уравнение Колмогорова

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

Пусть система S имеет четыре возможных состояния S₁, S₂, S₃, S₄. Найдем одну из вероятностей состояний, например P_i(t). Это вероятность того, что в момент t система будет находиться в состоянии S_i.

Придав t малое приращение Δt, найдем вероятность того, что в момент t+Δt система будет находиться в состоянии S₁.

Существуют два варианта этого события:

1 В момент t система уже была в состоянии S_i и за _Δt не вышла из этого состояния.

2  В момент t система была в состоянии S₃, а за _Δt перешла из него в S₁.

Вероятность первого варианта равна произведению вероятности  P₁(t) того, что в момент t система была в состоянии S₁ на условную вероятность того, что, будучи в состоянии S₁ система за время Δt не перейдет в S₂. Эта условная вероятность (с точностью до бесконечно малых высших порядков) равна 1-λ_{12 Δ}t

Аналогично, вероятность  второго варианта равна вероятности  того, что в момент t система была в состоянии S₃, умноженной на условную вероятность перехода за время _Δt в состояние S₁.

Используя правило сложения вероятностей, получаем:

.  

Раскроем скобки в правой части, перенесем P₁(t) в левую часть и, разделив обе части равенства на Δt, получим:

 

Если теперь устремить Δt к нулю и перейти к пределу:

 

то получится дифференциальное уравнение, которому должна удовлетворять  функция p₁(t).