Под случайным (вероятностным или стохастическим) процессом понимается процесс изменения во времени состояния какой-либо системы в соответствии с вероятностными закономерностями.
Процесс работы СМО представляет собой случайный процесс с дискретными состояниями и непрерывным временем. Это означает, что состояние СМО меняется скачком в случайные моменты появления каких-то событий (например, прихода новой заявки, окончания обслуживания и т.п.).
Случайный процесс, протекающий в системе называется марковским случайным процессом (или «процессом без последействия»), если он обладает следующим свойством: для каждого момента времени: вероятность любого состояния системы в будущем (при > .0) зависит только от ее состояния в настоящем (при t= ) и не зависит от того, когда и каким образом система пришла в это состояние.
Пример марковского процесса: система S — счетчик в такси. Состояние системы в момент t характеризуется числом километров (десятых долей километров), пройденных автомобилем до данного момента. Пусть в момент t0 счетчик показывает S0. Вероятность того, что в момент t > . t0 счетчик покажет то или иное число километров (точнее, соответствующее число рублей) S1, зависит от S0, но не зависит от того, в какие моменты времени изменялись показания счетчика до момента t0.
|
|
Многие процессы можно приближенно считать марковскими. Например, процесс игры в шахматы . система S — группа шахматных фигур. Состояние системы характеризуется числом фигур противника, сохранившихся на доске в момент t0. Вероятность того, что в момент t> . t0 материальный перевес будет на стороне одного из противников, зависит в первую очередь от того, в каком состоянии находится система в данный момент t0, а не от того, когда и в какой последовательности исчезли фигуры с доски до момента t0.
Случайный процесс называется процессом с дискретными состояниями, если возможные состояния системы можно перечислить (перенумеровать), а система переходит из одного состояния в другое мгновенно (скачком).
Случайный процесс называется процессом, с дискретным временем, если переходы системы из состояния в состояние возможны только в строго определенные, фиксированные моменты времени. Эти моменты принято называть «шагами» или «этапами» процесса.
Случайный процесс называется процессом с непрерывным временем, если переход системы из состояния в состояние возможен в любой, наперед неизвестный, случайный момент времени.
Условимся обозначать как событие, состоящее в том, что после k шагов система находится в состоянии .
При любом k события образуют полную группу и несовместны.
|
|
Процесс происходящий в системе, можно представить как последовательность (цепочку) событий. Если для каждого шага вероятность перехода из любого состояния в любое состояние не зависит от того, когда и как система пришла в состояние , то такая последовательность событий называется марковской цепью.
Вероятности переходов (переходные вероятности) можно записать как условные вероятности
.
Легко видеть, что вероятности состояний системы после k-гo шага
если вероятности переходов от шага к шагу не меняются (цепь Маркова однородна).
Рассмотрим теперь непрерывную цепь Маркова.
Назовем плотностью вероятности перехода предел отношения вероятности перехода системы за время из состояния в состояние к длине промежутка . Тогда при малом вероятность перехода с точностью до бесконечно малых высших порядков равна
Предположим, что нам известны плотности вероятностей переходов для всех пар состояний системы, граф переходов которой показан на рис. 10.
Рис. 10
Поставим задачу: найти одну из вероятностей состояний, например . Придадим t малое приращение и найдем вероятность того, что в момент t+ система будет находиться в состоянии .
Могут представиться две возможности:
1) в момент t система уже была в состоянии , а за время не вышла из этого состояния . это происходит с вероятностью .
2) в момент t система была в состоянии , а за время перешла из него в состояние . Вероятность совмещений этих событий
Применяя правило сложения вероятностей, получим
)= +
Раскроем скобки в правой части, перенесем в левую и разделим обе части неравенства на . получим
Устремляя к нулю и переходя к пределу, видим, что левая часть есть ни что иное как производная функции ,
,
т.е. получи дифференциальное уравнение первого порядка (уравнение, содержащее как саму неизвестную функцию, так и ее производную). Рассуждая аналогично, получим систему дифференциальных уравнений, называемых уравнениями Колмогорова. Интегрирование этих уравнений даст искомые вероятности состояний как функции времени. Начальные условия должны быть заданы: если в момент t = 0 система находилась в состоянии , то надо принять .
Оказывается, что все уравнения построены по определенному правилу (правило составления дифференциальных уравнений Колмогорова): в левой части каждого уравнения стоит производная вероятности состояния, а правая часть содержит столько членов, сколько стрелок связано с данным состоянием. Если стрелка направлена из состояния, соответствующий член имеет знак «минус» . если в состояние — знак «плюс». Каждый член равен произведению плотности вероятности перехода, соответствующей данной стрелке, умноженной на вероятность того состояния, из которого исходит стрелка.
Это правило составления дифференциальных уравнений для вероятностей переходов является общим и справедливо для любой непрерывной марковской цепи.
Рассмотрим еще один пример марковского случайного процесса.
Построить граф состояний и составить систему дифференциальных уравнений Колмогорова следующего случайного процесса: устройство S состоит из двух узлов, каждый из которых в случайный момент времени может выйти из строя, после чего мгновенно начинается ремонт узла, продолжающийся заранее неизвестное случайное время.
Решение. Возможные состояния системы: S0 — оба узла исправны . S1 — первый узел ремонтируется, второй исправен . S2 — второй узел ремонтируется, первый исправен . S3 — оба узла ремонтируются. Граф системы приведен на рисунке 5.2.
Рисунок 5.2. – Граф системы для примера 5.1.
Стрелка, направленная, например, из S0 в S1, означает переход системы в момент отказа первого узла, из S1 в S0 — переход в момент окончания ремонта этого узла.
|
|
На графе отсутствуют стрелки из S0 в S3 и из S1 в S2. Это объясняется тем, что выходы узлов из строя предполагаются независимыми друг от друга и, например, вероятностью одновременного выхода из строя двух узлов (переход из S0 в S3) или одновременного окончания ремонтов двух узлов (переход из S3 в S0) можно пренебречь.
Согласно правилу составления дифференциальных уравнений Колмогорова получим следующую систему:
В данной системе независимых уравнений на единицу меньше общего числа уравнений. Поэтому для решения системы необходимо добавить уравнение .
Уравнения Колмогорова дают возможность найти все вероятности состояний как функции времени. Особый интерес представляют вероятности системы pi (t) в предельном стационарном режиме, т.е. при , которые называются предельными (или финальными) вероятностями состояний.
В теории случайных процессов доказывается, что если число состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое состояние, то предельные вероятности существуют.
Предельная вероятность состояния Si имеет четкий смысл: она показывает среднее относительное время пребывания системы в этом состоянии. Например, если предельная вероятность состояния S0, т.е. р0=0,5, то это означает, что в среднем половину времени система находится в состоянии S0.
Так как предельные вероятности постоянны, то, заменяя в уравнениях Колмогорова их производные нулевыми значениями, получим систему линейных алгебраических уравнений, описывающих стационарный режим. Для системы S с графом состояний, изображенном на рис. 5.2), такая система уравнений имеет вид:
Систему (15.10) можно составить непосредственно по размеченному графу состояний, если руководствоваться правилом, согласно которому слева в уравнениях стоит предельная вероятность данного состояния pit умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа — сумма произведений интенсивностей всех потоков, входящих в i-e состояние, на вероятности тех состояний, из которых эти потоки исходят.
|
|
Для математического описания марковского случайного процесса с дискретными состояниями и непрерывным временем, протекающего в СМО, познакомимся с одним из важных понятий теории вероятностей — понятием потока событий.
Потоки событий.
Под потоком событий понимается последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени (например, поток вызовов на телефонной станции, поток отказов ЭВМ, поток покупателей и т.п.).
Поток характеризуется интенсивностью l — частотой появления событий или средним числом событий, поступающих в СМО в единицу времени.
Поток событий называется регулярным, если события следуют одно за другим через определенные равные промежутки времени. Например, поток изделий на конвейере сборочного цеха (с постоянной скоростью движения) является регулярным.
Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. В частности, интенсивность стационарного потока есть величина постоянная: l(t)=l. Например, поток автомобилей на городском проспекте не является стационарным в течение суток, но этот поток можно считать стационарным в течение суток, скажем, в часы пик. Обращаем внимание на то, что в последнем случае фактическое число проходящих автомобилей в единицу времени (например, в каждую минуту) может заметно отличаться друг от друга, но среднее их число будет постоянно и не будет зависеть от времени.
Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени t1 и t2 — число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие (когда каждое последующее событие зависит только от непосредственно предшествующего, но не от более ранних). Например, поток пассажиров, входящих в метро, практически не имеет последействия. А, скажем, поток покупателей, отходящих с покупками от прилавка, уже имеет последействие (хотя бы потому, что интервал времени между отдельными покупателями не может быть меньше, чем минимальное время обслуживания каждого из них).
Поток событий называется ординарным, если вероятность попадания на малый (элементарный) участок времени At двух и более событий пренебрежимо мала по сравнению с вероятностью попадания одного события. Другими словами, поток событий ординарен, если события появляются в нем поодиночке, а не группами. Например, поток поездов, подходящих к станции, ординарен, а поток вагонов не ординарен.
Поток событий называется простейшим (или стационарным пуассоновским), если он одновременно стационарен, ординарен и не имеет последействия. Название простейший объясняется тем, что СМО с простейшими потоками имеет наиболее простое математическое описание. Заметим, что регулярный поток не является простейшим, так как он обладает последействием: моменты появления событий в таком потоке жестко зафиксированы.
В теории массового обслуживания наибольшее число аналитических результатов получено для простейшего потока. Он обладает следующими свойствами: стационарностью, отсутствием последействия (длина интервала времени до момента поступления следующей заявки не зависит от того, поступила в начальный момент заявка или нет) . ординарностью (в каждый момент времени в систему может поступить не более одной заявки). Для простейшего потока интервалы времени между двумя последовательными заявками — независимые случайные величины с показательной функцией распределения
.
Математическое ожидание и дисперсия длины интервала времени между последовательными моментами поступления заявок
Простейший поток обладает устойчивостью: при суммировании независимых простейших потоков получается снова простейший поток с суммарной интенсивностью.
Для простейшего потока число заявок, поступающих в систему за промежуток времени , распределено по закону Пуассона:
,
где — вероятность того, что за время в систему поступит ровно k заявок. Математическое ожидание и дисперсия распределения Пуассона .
Распределение Пуассона дискретно. Заметим, что распределение Пуассона может описываться и нестационарный поток, у которого . Такой поток также является пуассоновским, но не является простейшим.
Если закон распределения промежутков времени между соседними заявками отличается от экспоненциального, то имеет место поток с ограниченным последействием (поток Пальма), или рекурсивный поток. Пример такого потока— поток Эрланга. Поток k-го порядка — это поток, у которого интервалы времени между моментами поступления двух последовательных заявок представляют собой сумму k независимых случайных величин, распределенных по показательному закону с параметром . Такой поток получить из простейшего потока выбрасыванием подряд (k-1) заявок с сохранением каждой k-й заявки.
Плотность распределения интервала времени между двумя соседними заявками в потоке Эрланга k -ro порядка
При k =1 поток будет простейшим.