Теория марковских процессов и уравнения Колмогорова

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

состояния,
уравнения Колмогорова, финальные
вероятности состояний.

2. Случайный процесс

• Работа любой системы массового
обслуживания (например, очереди в кафе,
работы колл-центра или загрузки сервера) —
это процесс, который развивается во времени,
и в нём есть элемент случайности. Мы не
можем точно предсказать, когда придёт
следующий клиент или сколько времени займёт
обслуживание.
• Поэтому такой процесс
называют случайным (или вероятностным).
Это значит, что поведение системы меняется во
времени под влиянием случайных событий, и
эти изменения подчиняются законам теории
вероятностей.

3. Случайный процесс

• Процесс с дискретными состояниями — это когда у системы
есть заранее известный список возможных состояний (например:
«очередь пуста», «в очереди 1 человек», «в очереди 2 человека»
и т.д.). Переход из одного состояния в другое происходит
мгновенно, скачком — как переключение тумблера.
• Процесс с непрерывным временем — это когда моменты
переходов случайны. Мы не знаем точно, когда произойдёт
событие (например, когда придёт следующий клиент или когда
закончится обслуживание), но знаем, что это может случиться в
любой момент времени.
• Процесс работы системы массового обслуживания (СМО) —
это как раз пример такого процесса: у него есть дискретные
состояния (например, длина очереди меняется целыми
числами), и переходы между ними происходят в случайные
моменты времени. Например, отключение участка электрической
сети при аварии — состояние меняется скачком, и момент
аварии случаен.

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

• Когда мы изучаем работу системы массового
обслуживания (СМО) математически, всё становится
намного проще, если процесс её работы —
марковский. Но что это значит?
• Марковский процесс — это такой случайный процесс,
у которого нет памяти. Есть у него одно важное
свойство, которое называется отсутствие
последействия. Звучит сложно, но на деле всё
просто:
• Если мы знаем, в каком состоянии система
находится прямо сейчас, то для предсказания её
будущего нам совершенно не нужно знать, как она
оказалась в этом состоянии. Была ли она в прошлом
перегружена или простаивала, пришёл ли клиент
минуту назад или час назад — всё это неважно.
Будущее зависит только от текущего момента.
Система живёт сегодняшним днём. Что было вчера —
забыто. Всё, что случится завтра, определяется только

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

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

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

• Чтобы стало ещё яснее, давайте разберём конкретный пример из
жизни — счётчик электроэнергии.
• Представьте себе обычный счётчик в квартире, который считает,
сколько киловатт-часов вы уже потратили. У этого счётчика есть
одно важное свойство: он показывает только текущее значение —
сколько энергии вы потребили на данный момент.
• Допустим, сейчас полдень, и счётчик показывает 10 кВт·ч. Мы
хотим предсказать, что он покажет вечером. Очевидно, что это
будет зависеть от того, сколько сейчас на счётчике (10 кВт·ч) и
сколько энергии вы потратите днём. Но вот что интересно: нам
совершенно неважно, в какие именно моменты времени вы
включали чайник или стиральную машину до полудня. Было ли
это утром равномерно или всё сразу — счётчик это не волнует.
Важно только итоговое значение на текущий момент.
• Почему это марковский процесс?
Потому что будущее состояние счётчика (показания вечером)
зависит только от его настоящего состояния (показания сейчас)
и того, сколько энергии добавится в будущем. Прошлое (как
именно вы пришли к текущим показаниям) не играет роли.

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

• Представьте себе некую систему S, которая может находиться в разных состояниях
(например, "работает", "простаивает", "в ремонте"). С течением времени эти состояния
меняются, и происходят эти изменения случайным образом — то есть мы не можем точно
предсказать, когда именно система переключится. В таком случае говорят, что в системе
протекает случайный процесс.
• Когда математики и инженеры изучают такие процессы, они выделяют два особо важных
типа. Оба типа — марковские (то есть без памяти, о которых мы говорили раньше), и оба
имеют дело с дискретными состояниями (состояния можно перечислить по порядку:
состояние №1, №2, №3...). Различаются они тем, когда именно система может прыгать из
одного состояния в другое.
• Тип 1: Процесс с дискретным временем.
Здесь переходы разрешены только в строго определённые, заранее известные моменты
времени. Например:
• Каждую минуту ровно в 0 секунд.
• Каждый час в начале часа.
• Раз в сутки в полночь.
В промежутках между этими моментами система «застывает» и не меняется. Это как кадры в
мультфильме: между кадрами ничего не движется.
• Тип 2: Процесс с непрерывным временем.
Здесь переходы могут случиться в любой случайный момент времени. Никто не знает, когда
именно произойдёт событие — сейчас, через секунду или через год. Система как бы «живёт»
непрерывно, и переключение может произойти в любой миг. Например, поломка
оборудования может случиться в любой момент, а не только в начале часа.

8. Граф состояний

• Есть особый вид марковских процессов, который называется марковская
цепь. Это процесс, у которого:
• Состояния — дискретные (можно перечислить).
• Время — дискретное (переходы происходят не когда попало, а в
определённые моменты: шаг 1, шаг 2, шаг 3...).
• Представьте, что мы наблюдаем за системой не непрерывно, а делаем
«снимки» в некоторые моменты: первый снимок, второй, третий... Время
между снимками может быть любым (секунда, день, год), но важно, что
мы рассматриваем процесс именно по шагам.
• Как это обозначают:
• S0​ — состояние системы в самом начале (до первого шага).
• S1​ — состояние после первого шага.
• S2​ — состояние после второго шага.
• ...
• Sk — состояние после k-го шага.
• Таким образом, вместо непрерывного времени t мы используем номер
шага k. Это сильно упрощает математику.

9. Пример

• Представьте себе небольшую
электростанцию, на которой работают два
генератора. Каждый из них может в любой
случайный момент сломаться. Когда
генератор ломается, его начинают
ремонтировать, и время ремонта тоже
случайное — никто точно не знает,
сколько он займёт.
• Нам нужно описать эту систему с
помощью графа состояний. Для этого
сначала перечислим все возможные
ситуации, в которых может оказаться
система.
• Состояния системы:
• s₀ — оба генератора работают исправно.
Всё хорошо.
• s₁ — первый генератор сломался и
ремонтируется, а второй пока работает.
• s₂ — второй генератор ремонтируется,
первый работает.
• s₃ — оба генератора сломались и оба
ремонтируются.
• Других вариантов нет. Эти четыре
состояния полностью описывают
положение дел на станции.

10. Пример

• В нашем графе состояний для двух генераторов есть важная
особенность: из состояния s₀ (оба работают) нет прямой стрелки в
состояние s₃ (оба сломались). И наоборот, из s₃ нет прямой стрелки
обратно в s₀. Почему?
• Потому что мы считаем, что поломки генераторов
происходят независимо друг от друга и в случайные моменты времени.
Представьте: чтобы оба генератора сломались одновременно, нужно,
чтобы две независимые случайные поломки случились в одно и то же
мгновение. Теоретически это возможно, но вероятность этого настолько
мала, что в практических расчётах ей пренебрегают. Мы считаем, что за
очень маленький промежуток времени может произойти
только одно событие — либо ломается первый, либо ломается второй,
но не оба сразу.
• То же самое с ремонтом: одновременное окончание ремонта двух
генераторов тоже событие крайне маловероятное. Поэтому мы не рисуем
стрелку из s₃ сразу в s₀. Вместо этого система сначала перейдёт
в s₁ или s₂ (когда один из генераторов починится), и только потом, если
починится второй — в s₀.
• Если система в состоянии s₀, то за время Δt она может перейти в s₁, если
за этот промежуток случится поломка первого генератора. Вероятность
такого события примерно равна интенсивности поломок, умноженной на
Δt. Для других переходов — аналогично.

11. Поток событий

• Поток событий — это просто
последовательность похожих событий,
которые происходят одно за другим, но в
случайные моменты времени. Мы не
знаем точно, когда случится следующее
событие, но можем изучать закономерности
этого потока.
• Главное: события
считаются однородными — то есть мы не
различаем их между собой, нам важно
только то, что они происходят. Например,
нам всё равно, кто именно звонит, важен
сам факт звонка.

12. Поток событий

• Регулярный поток событий —
это когда события происходят
через строго одинаковые
промежутки времени, как по
расписанию. Например, поезда
метро каждые 5 минут ровно.
• Но в реальной жизни такие потоки
встречаются крайне редко,
потому что почти всегда есть
случайности (опоздания, сбои,
неравномерность). Поэтому
регулярный поток — это скорее
идеальная модель.
• Как изображают:
Любой поток событий можно
нарисовать на временной́ оси Ot в
виде точек. Каждая точка — это
момент, когда случилось событие.
Для регулярного потока точки
будут располагаться на равном
расстоянии друг от друга.

13. Поток событий

• Стационарность (однородность во времени) Поток называется стационарным, если его поведение
не зависит от времени суток. Вероятность того, что за
какой-то промежуток времени (например, за 10 минут)
случится определённое количество событий, зависит
только от длины этого промежутка, но не от того, в
какое время суток мы его взяли - утром, днём или
ночью.
• Отсутствие последействия (независимость) Поток называется потоком без последействия, если
события происходят независимо друг от друга. То,
сколько событий случилось в прошлом, никак не
влияет на то, сколько их случится в будущем.
Прошлое и будущее не связаны.
• Ординарность (поодиночке) Поток называется ординарным, если события
приходят по одному, а не группами. Вероятность того,
что в один и тот же миг случится сразу два или больше

14. Поток событий

• Простейший (стационарный пуассоновский) поток - это
случайный поток событий, который обладает сразу тремя
важными свойствами: стационарностью, отсутствием
последействия и ординарностью. Такой поток удобнее всего
изучать, потому что его поведение предсказуемо с точки
зрения вероятностей.
• Нестационарный пуассоновский поток - сохраняет два
свойства: отсутствие последействия и ординарность, но его
интенсивность может меняться со временем. Например, днём
звонков может быть больше, чем ночью, но при этом они попрежнему независимы и приходят по одному.
• Почему их называют пуассоновскими?
Потому что количество событий, которое произойдёт на
любом промежутке времени, подчиняется распределению
Пуассона. Это значит, что мы можем точно рассчитать
вероятность того, что за минуту, час или день случится ровно
0, 1, 2, … событий, зная только среднюю интенсивность
потока.

15. Закон Пуассона

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

16. Вероятность событий

• Вероятностью i-го состояния называется
вероятность pi(t) того, что в момент t система будет
находиться в состоянии Si. Очевидно, что для
любого момента t сумма вероятностей всех
состояний равна единице:

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

• Уравнения Колмогорова - уравнения для переходной
функции марковского случайного процесса.
• Исчерпывающей количественной характеристикой
Марковского процесса является совокупность
вероятностей состояний, т.е. вероятностей pi(t) того,
что в момент t процесс будет находиться в
состоянии si(i =1…n).

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

Рассмотрим, как определяются вероятности состояний по приведенному
графу состояний, считая все потоки простейшими. В случайный момент
времени t система может находиться в одном из состояний si с вероятностью
pi(t). Придадим t малое приращение ∆t и найдем, например, p2(t+∆t) вероятность того, что в момент t+∆t система будет в с состоянии s2. Это
может произойти, во-первых, если система в момент была в состоянии s2 и
за время t не вышла из него; во-вторых, если в момент t система была в
состоянии s1 или s5 и за время ∆t перешла в состояние s2.
В первом случае надо вероятность p2(t) умножить на вероятность того, что за
время ∆t система не перейдет в состояние s1, s3 или s4. Суммарный поток
событий, выводящий систему из состояния s2, имеет интенсивность λ21+
λ23+ λ24. Значит, вероятность того, что за время ∆t система выйдет из
состояния s2, равна (λ21+ λ23+ λ24)∆t. Отсюда вероятность первого варианта
p2.1(t+∆t)= p2(t)[1-(λ21+ λ23+ λ24)∆t].
Найдем вероятность перехода в состояние s2. Если в момент t система
находилась в состоянии s1 с вероятностью pi(t), то вероятность перехода в
состояние s1 за время ∆t равна p2.2(t+∆t)= p1(t)λ12∆t.
Аналогично для состояния s5. p2.3(t+∆t)= p1(t)λ52∆t.
Складывая вероятности p2.1(t+∆t) + p2.2(t+∆t) + p2.2(t+∆t), получим.

19. Вывод уравнения Колмагорова

Складывая вероятности p2.1(t+∆t) + p2.2(t+∆t) + p2.2(t+∆t),
получим.
Раскроем квадратные скобки, перенесем p2(t) в левую часть и разделим обе части
на ∆t:
Если устремить ∆t к нулю, то слева получим производную
функции p2(t):
Аналогичные уравнения можно вывести для всех остальных состояний.
Получается система дифференциальных уравнений:

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

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

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

Тоже самое, что
и на
предыдущем
слайде
• правило составления уравнений Колмогорова. В левой
части каждого из них стоит производная
вероятности i-го состояния. В правой части — сумма
произведений вероятностей всех состояний (из
которых идут стрелки в данное состояние) на
интенсивности соответствующих потоков событий,
минус суммарная интенсивность всех потоков,
выводящих систему из данного состояния,
умноженная на вероятность данного (i-го состояния).