Марковские процессы

В содержании описан текст к презентации с нумерацией слайдов!

Понятие о марковском процессе
В стохастических задачах исследования операций часто затруднительно даже построение математической модели, уже не говоря об оптимизации. В большинстве случаев не удается построить простую математическую модель, позволяющую в явном (аналитическом) виде найти интересующие нас величины (показатели эффективности) в зависимости от условий операции а и элементов решения х. Однако в некоторых особых случаях такую математическую модель удается построить. Это — когда исследуемая операция представляет собой (точно или приближенно) так называемый марковский случайный процесс.
А что такое «марковский случайный процесс»? Определение этого понятия мы дадим не сразу, сначала поговорим о том, что такое вообще «случайный процесс».
Слайд. 2. Пусть имеется некоторая физическая система S, которая с течением времени меняет свое состояние (переходит из одного состояния в другое), причем заранее неизвестным, случайным образом.
Тогда мы будем говорить, что в системе S протекает случайный процесс.
Под «физической системой» можно понимать что угодно: техническое устройство, группу таких устройств, предприятие, отрасль промышленности, живой организм, популяцию и т. д. Большинству процессов, протекающих в реальных системах, свойственны, в той или иной мере, черты случайности, неопределенности.
Пусть, например, система S — космический корабль, выводимый на заданную орбиту. Процесс вывода неизбежно сопровождается случайными ошибками, отклонениями от заданного режима, на которые приходится вводить коррекцию (если бы не случайные ошибки, коррекция была бы не нужна). Значит, процесс вывода на орбиту — случайный процесс.
Теперь спустимся из космоса в околоземную зону. Физическая система S — обыкновенный самолет, совершающий рейс на заданной высоте, по определенному маршруту. Является ли этот процесс случайным? Безусловно, да, так как он неизбежно (в силу турбулентности атмосферы и других факторов) сопровождается случайными возмущениями, колебаниями (в этом не усомнится никто, испытавший на себе так называемую «болтанку» или нарушение графика полетов).
Еще пример: система S — техническое устройство, состоящее из ряда узлов, которые время от времени выходят из строя, заменяются или восстанавливаются. Процесс, протекающий в этой системе, безусловно, случаен. А столовая самообслуживания? В ней время от времени могут образовываться и рассасываться очереди, возникать задержки, нехватка подносов и т. д.
Вообще, если подумать, труднее привести пример «неслучайного» процесса, чем случайного. Даже процесс хода часов — классический пример точной, строго выверенной работы («работает, как часы») подвержен случайным изменениям (уход вперед, отставание, остановка).
Случайные возмущения присущи любому процессу. Но до тех пор, пока эти возмущения несущественны, мало влияют на интересующие нас параметры, мы можем ими пренебречь и рассматривать процесс как детерминированный, неслучайный.
Необходимость учета случайностей возникает тогда, когда они прямо касаются нашей заинтересованности. Например, составляя расписание самолетов, можно пренебречь случайными колебаниями самолета вокруг центра массы, а проектируя автопилот — безусловно, нет.
Слайд. 3. Теперь, когда нам ясно, что такое «случайный процесс», дадим определение «марковского случайного процесса». Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t0 и не зависят от того, когда и как система пришла в это состояние.
Это очень важное определение стоит того, чтобы его растолковать подробнее. Пусть в настоящий момент t0 (см. рис. 15.1) система находится в определенном состоянии S0. Мы наблюдаем процесс со стороны и в момент t0 знаем состояние системы S0 и всю предысторию процесса, все, что было при tt0). Можем ли мы его предугадать (предсказать)? В точности — нет, наш процесс случайный, значит — непредсказуемый. Но какие-то вероятностные характеристики процесса в будущем мы найти можем. Например, вероятность того, что через некоторое время t система S окажется в состоянии S1 или сохранит состояние S0 и т. п.
Так вот, для марковского случайного процесса такое «вероятностное предсказание» оказывается гораздо проще, чем для немарковского. Если процесс — марковский, то предсказывать можно, только учитывая настоящее состояние системы S0 и забыв о его «предыстории» (поведении системы при tt0 счетчик покажет то или другое число частиц S1 (или не менее S1), разумеется, зависит от S0, но не зависит от того, в какие именно моменты приходили частицы до момента t0.
На практике часто встречаются процессы, которые если не в точности марковские, то могут быть в каком-то приближении рассмотрены как марковские. Пример: система S — группа самолетов, участвующих в воздушном бою. Состояние системы характеризуется числом самолетов «красных» — x и «синих» — y, сохранившихся (не сбитых) к какому-то моменту. В момент t0 нам известны численности сторон — x0 и y0. Нас интересует вероятность того, что в какой-то момент t0 + µ численный перевес будет на стороне «красных». От чего зависит эта вероятность? В. первую очередь от того, в каком состоянии находится система в данный момент t0 а не от того, когда и в какой последовательности погибали сбитые до момента t0 самолеты.
Итак, в сущности, любой процесс можно рассматривать как марковский, если все параметры из «прошлого», от которых зависит «будущее», включить в «настоящее». Например, пусть речь идет о работе какого-то технического устройства; в какой-то момент t0 оно еще исправно, и нас интересует вероятность того, что оно проработает еще время µ. Если за настоящее состояние системы считать просто «система исправна», то процесс безусловно не марковский, потому что вероятность того, что она не откажет за время µ, зависит, в общем случае, от того, сколько времени она уже проработала и когда был последний ремонт.
Если оба эти параметра (общее время работы и время после последнего ремонта) включить в настоящее состояние системы, то процесс уже можно будет, пожалуй, считать марковским. Однако такое «обогащение настоящего за счет предыстории» далеко не всегда бывает полезно, так как (если число параметров прошлого велико) оно зачастую приводит к «проклятию многомерности», о котором мы уже говорили. Поэтому в дальнейшем, говоря о марковском процессе, мы будем подразумевать его простым, «бесхитростным», с небольшим числом параметров, определяющих «настоящее».
На практике марковские процессы в чистом виде обычно не встречаются, но нередко приходится иметь дело с процессами, для которых влиянием «предыстории» можно пренебречь. При изучении таких процессов можно с успехом применять марковские модели.
Слайд. 4. В исследовании операций большое значение имеют так называемые марковские случайные процессы с дискретными состояниями и непрерывным временем. Процесс называется процессом с дискретными состояниями, если его возможные состояния S1, S2, S3,… можно заранее перечислить (перенумеровать), и переход системы из состояния в состояние происходит «скачком», практически мгновенно. Процесс называется процессом с непрерывным времен ем, если моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны, если переход может осуществиться, в принципе, в любой момент. Мы здесь будем рассматривать только процессы с дискретными состояниями и непрерывным временем.
Слайд. 5. Пример такого процесса: техническое устройство S состоит из двух узлов, каждый из которых в случайный момент времени может выйти из строя (отказать), после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время. Возможные состояния системы можно перечислить:
S0— оба узла исправны,
S1— первый узел ремонтируется, второй исправен,
S2— второй узел ремонтируется, первый исправен,
S3— оба узла ремонтируются.
Переходы системы S из состояния в состояние происходят практически мгновенно, в случайные моменты выхода из строя того или другого узла пли окончания ремонта.
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой — так называемым графом состояний. Состояния системы изображаются прямоугольниками (или кругами, или даже точками), а возможные переходы из состояния в состояние — стрелками, соединяющими состояния. Мы будем изображать состояния прямоугольниками, в которых записаны обозначения состояний: S1, S2,…Sn.
Построим граф состояний для рассмотренного выше примера (см. рис. 15.2). Стрелка, направленная из S0 в S1 означает переход в момент отказа первого узла; стрелка, направленная обратно, из S1 в S0 переход в момент окончания ремонта этого узла. Остальные стрелки объясняются аналогично.
Может возникнуть вопрос: почему нет стрелки, ведущей непосредственно из S0 в S3? Разве не может быть, что оба узла откажут одновременно, например, вследствие короткого замыкания? Вопрос законный. Ответим, что мы предполагаем узлы выходящими из строя независимо друг от друга, а вероятностью строго одновременного выхода их из строя пренебрегаем/
Слайд. 6. Понятие о марковских процессах с непрерывным временем переходов
Марковские процессы
Слайд. 7. Марковские процессы с непрерывным временем переходов можно рассматривать как марковские цепи, если разбить время на малые интервалы ∆t и определить вероятности pij за ∆t. При равных интервалах эти вероятности, для того, чтобы процесс был марковским, должны быть постоянными. В противном случае поведение будет зависеть от предыстории, в данном случае от того, как долго система находится в i-ом состоянии.
Вероятность pij при малых ∆t равна (формула), где (обозначение)- постоянный коэффициент, называемый интенсивностью перехода из i-го состояния в j-е состояние.
В соответствии с марковским свойством вся предыстория процесса сказывается на его поведении в будущем только через текущее состояние, которое и определяет дальнейший ход процесса.
Таким образом, нет необходимости знать, как долго процесс находится в текущем состоянии. Отсюда следует, что распределение остающегося времени пребывания процесса в состоянии sj должно зависеть только от самого состояния, а не от времени пребывания в нем. Этим свойством обладает только одно распределение – экспоненциальное.
Таким образом, непременное свойство непрерывного марковского процесса – экспоненциальность распределения времени пребывания процесса в каждом из состояний.
Слайд. 8. Марковский процесс с непрерывным временем переходов можно задать в виде графа (рис. 1.8.1) или описать системой дифференциальных уравнений.
Для определения финальных вероятностей состояний дифференциальные уравнения преобразуются в систему линейных уравнений.
Рис. 1.8.1 Граф марковского процесса
Иногда марковский процесс с дискретными состояниями, переходы между которыми разрешаются в любой момент времени, называется непрерывной марковской цепью.

Рассмотрим, как можно получить дифференциальное уравнение, описывающее марковский процесс. Для этого используем уравнение Колмогорова-Чепмена (1.7.1.) в следующем виде: (формула) Проведем следующие преобразования: где Е – единичная матрица.
Слайд. 9. Тогда искомое дифференциальное уравнение в матричной форме примет следующий вид (формула).
Систему дифференциальных уравнений можно получить непосредственно из графа состояний. Например, имеем граф марковского процесса (рис. 1.8.2).


Слайд. 10. Матрица вероятностей переходов для данного случая: (на слайде)
В свою очередь матрица интенсивностей переходов имеет вид(на слайде).
Слайд. 11. На основе матричной записи дифференциального уравнения (1.8.1.) запишем систему уравнений: (на слайде)
Анализ полученной системы дает возможность сформулировать правило составления таких систем: для произвольного момента времени производная от вероятности i го состояния равна сумме произведений всех других вероятностей на интенсивности перехода из них в i-ое состояние "минус" произведение вероятности i го состояния на суммарную интенсивность выхода из i го состояния.
Полученное правило можно записать в виде формулы (на слайде).
Для установившегося режима и система дифференциальных уравнений преобразуется к системе линейных алгебраических уравнений, решением которой являются финальные вероятности состояний системы. Определение финальных вероятностей рассмотрим на примере.
Слайд. 12. Пример. Система может находиться в двух состояниях. Для описания модели системы составим граф марковского процесса (рис.1.8.3).
Требуется определить финальные значения вероятностей состояний Решение.
Для определения вероятностей составим систему дифференциальных уравнений: (на слайде).
Слайд. 13. Чтобы получить финальные значения вероятностей необходимо перейти к алгебраическим уравнениям: (на слайде).
После замены любого уравнения на нормирующую сумму решение системы становится очевидным: (на слайде)
Слайд. 14. Модель "гибели и размножения"
Схема "гибели и размножения" часто встречается в разнообразных практических задачах. Своим названием эти процессы обязаны биологической задаче об изменении численности популяции и распространением эпидемий.
В технических системах данной моделью описывают процессы возникновения отказа и восстановления.
Процесс "гибели и размножения" может быть представлен марковским случайным процессом с непрерывным временем, причем число состояний может быть бесконечным или конечным. В этом случае интервалы времени между двумя моментами рождения и гибели распределены по экспоненциальному закону.
Таким образом, марковский процесс называется процессом "гибели и размножения", если его граф состояний (рис. 1.8.4) имеет вид цепочки состояний, в которой каждое состояние (кроме крайних) связано с двумя соседними состояниями, а крайние состояния только с соседним состоянием.
Слайд. 15. Для такого графа достаточно просто определяются финальные вероятности состояний. (на слайде). В итоге получилась система уравнений.
Добавим к ней нормировочное уравнение.
Слайд. 16. Вероятность всех состояний выразим через вероятность нулевого состояния: (на слайде)
Слайд. 17. После подстановки вероятностей в нормировочное уравнение выражение для определения вероятности нулевого состояния примет следующий вид: (на слайде).
Значения остальных вероятностей рассчитываются по полученным ранее соотношениям.
Слайд. 18. Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t0 и не зависят от того, когда и как система пришла в это состояние.
Если процесс — марковский, то предсказывать можно, только учитывая настоящее состояние системы S0 и забыв о его «предыстории» (поведении системы при t

Презентация в рамках дисциплины "Экономико-математические методы" на тему: "Марковские процессы"

Интернет-ресурсы. Экономическая литература