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

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

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

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

Для марковского случайного процесса такое «вероятностное предсказание» оказывается гораздо проще, чем для немарковского. Если процесс — марковский, то предсказывать можно, только учитывая настоящее состояние системы S₀ и забыв о его «предыстории» (поведении системы при t < t₀). Само состояние S₀, разумеется, зависит от прошлого, но как только оно достигнуто, о прошлом можно забыть. В марковском процессе «будущее зависит от прошлого только через настоящее».

На практике часто встречаются процессы, которые если не в точности марковские, то могут быть в каком-то приближении рассмотрены как марковские. Пример: система S — группа самолетов, участвующих в воздушном бою. Состояние системы характеризуется числом самолетов «красных» — x и «синих» — y, сохранившихся (не сбитых) к определенному моменту. В момент t₀ нам известны численности сторон — x₀ и y₀. Нас интересует вероятность того, что в момент времени t₀ + t численный перевес будет на стороне «красных». В первую очередь эта вероятность будет зависеть от того, в каком состоянии находится система в момент t₀, а не от того, когда и в какой последовательности погибали сбитые до момента t₀ самолеты.

В сущности, любой процесс можно рассматривать как марковский, если все параметры из «прошлого», от которых зависит «будущее», включить в «настоящее». Например, пусть речь идет о работе некоторого технического устройства; в момент t₀ оно еще исправно, и нас интересует вероятность того, что оно проработает еще время t. Если за настоящее состояние системы считать просто «система исправна», то процесс безусловно немарковский, потому что вероятность того, что она не откажет за время t, зависит, в общем случае, от того, сколько времени она уже проработала и когда был последний ремонт. Если оба эти параметра (общее время работы и время после последнего ремонта) включить в настоящее состояние системы, то процесс можно будет считать марковским. Однако такое «обогащение настоящего за счет предыстории» далеко не всегда бывает полезно, поэтому в дальнейшем, говоря о марковском процессе, будем подразумевать его простым, с небольшим числом параметров, определяющих «настоящее».

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

В исследовании операций большое значение имеют так называемые марковские случайные процессы с дискретными состояниями и непрерывным временем. Процесс называется процессом с дискретными состояниями, если его возможные состояния S₁, S₂, S₃, ... можно заранее перечислить (перенумеровать), и переход системы из состояния в состояние происходит «скачком», практически мгновенно. Процесс называется процессом с непрерывным временем, если моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны, т. е. если переход может осуществиться в любой момент времени. При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой — так называемым графом состояний. Состояния системы изображаются прямоугольниками (или кругами, или точками), а возможные переходы из состояния в состояние — стрелками, соединяющими состояния. Мы будем изображать состояния прямоугольниками, в которых записаны обозначения состояний: S₁, S₂, ..., S_n.

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

Важной характеристикой потока событий является его интенсивность l — среднее число событий, приходящееся на единицу времени. Интенсивность потока может быть как постоянной (l= const), так и переменной, зависящей от времени t. Например, поток автомашин, движущихся по улице, днем интенсивнее, чем ночью, в часы пик — интенсивнее, чем в другие часы.

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

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

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

Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: стационарен, ординарен и не имеет последействия. Название «простейший» связано с тем, что процессы, связанные с простейшими потоками, имеют наиболее простое математическое описание. Самый простой, на первый взгляд, регулярный поток не является «простейшим», так как обладает последействием: моменты появления событий в таком потоке связаны жесткой функциональной зависимостью.

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

Для простейшего потока с интенсивностью l интервал между соседними событиями имеет так называемое экспоненциальное распределение с плотностью

(t > 0) (1)

Величина l в формуле (1) называется параметром показательного закона. Для случайной величины Т, имеющей экспоненциальное распределение, математическое ожидание m_T есть величина, обратная параметру, а среднее квадратическое отклонение s_T равно математическому ожиданию:

(2)

В теории вероятностей в качестве «меры случайности» неотрицательной случайной величины нередко рассматривают так называемый коэффициент вариации:

(3)

Из формул (2), (3) следует, что для показательного распределения n_t = 1, т. е. для простейшего потока событий коэффициент вариации интервалов между событиями равен единице.

Очевидно, что для регулярного потока событий, у которого интервал между событиями вообще не случаен (n_t = 0), коэффициент вариации равен нулю. Элементом вероятности называется вероятность попадания на этот интервал хотя бы одного события потока. Легко доказать, что элемент вероятности (с точностью до малых величин более высокого порядка по сравнению с Dt) равен:

(4)

т. е. для простейшего потока элемент вероятности равен интенсивности потока, умноженной на длину элементарного интервала. Элемент вероятности, в силу отсутствия последействия, совершенно не зависит от того, сколько событий и когда появлялись ранее.

Нормальное распределение занимает центральное место среди непрерывных распределений. Его плотность определяется формулой:

F(t) = (5)

где s > 0, m — параметры распределения. При s = 1 и m = 0 имеет место стандартное нормальное распределение с плотностью:

F(t) = (6)

Пусть рассматривается система S, имеющая n возможных состояний S₁, S₂, ..., S_n. Назовем вероятностью i-го состояния вероятность p_i(t) того, что в момент t система будет находиться в состоянии S_i. Очевидно, что для любого момента сумма всех вероятностей состояний равна единице.

Имея в своем распоряжении размеченный граф состояний, можно найти все вероятности состояний p_i(t) как функции времени. Для этого составляются и решаются так называемые уравнения Колмогорова — дифференциальные уравнения особого вида, в которых неизвестными функциями являются вероятности состояний.

Что будет происходить с вероятностями состояний при t ® ¥ ? Будут ли p₁(t), p₂(t),... стремиться к каким-то пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний. В теории случайных процессов доказывается, что если число n состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое, то финальные вероятности существуют.

Финальную вероятность состояния S_i можно истолковать как среднее относительное время пребывания системы в этом состоянии.

Граф состояний для схемы гибели и размножения имеет вид, показанный на рис. 1. Особенность этого графа в том, что все состояния системы можно вытянуть в цепочку, в которой каждое из средних состояний связано прямой и обратной стрелкой с каждым из соседних состояний — правым и левым, а крайние состояния — только с одним соседним состоянием. Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.

Схема гибели и размножения

l₀₁ l₁₂ l₂₃  l_k-1,k l_k,k+1 l_n-1,n

l₁₀ l₂₁ l₃₂  l_k,k-1  l_k+1,k l_n,n-1

l — интенсивность потока; p₀, p_k — финальные вероятности состояний

Формулы Литтла

L_сист — среднее число заявок в системе;

W_сист — среднее время пребывания заявки в системе;

WочL оч L_оч — среднее число заявок в очереди;

W_оч— среднее время пребывания заявки в очереди

m — интенсивность потока обслуживаний; l — интенсивность потока заявок

l /m = r (приведенная интенсивность потока заявок)

r — среднее число заявок, приходящее за среднее время обслуживания одной заявки

рис. 1