Потоком событий называют последовательность однородных событий, появляющихся одно за другим в случайные моменты времени. Примеры: поток вызовов на телефонной станции; поток сбоев ЭВМ; поток заявок на проведение расчетов в вычислительном центре и т.п.
Поток событий наглядно изображается рядом точек с абсциссами Q 1, Q 2 , ..., Q n , ... (рис. 6.15) с интервалами между ними: Т 1 = Q 2 - Q 1, T 2 = Q 3 -Q 2 , ..., Т п = Q n +1 - Q n . При его вероятностном описании поток событий может быть представлен как последовательность случайных величин:
Q 1 ; Q 2 = Q 1 + T 1 ; Q 3 = Q 1 + T 1 + T 2 ; и т.д.
На рисунке в виде ряда точек изображен не сам поток событий (он случаен), а только одна его конкретная реализация.
Поток событий называется стационарным, если его вероятностные характеристики не зависят от выбора начала отсчета или, более конкретно, если вероятность попадания того или другого числа событий на любой интервал времени зависит только от длины этого интервала и не зависит от того, где именно на оси 0-t он расположен.
Рисунок 6.15 – Реализация потока событий
Поток событий называется ординарным, если вероятность попадания на элементарный интервал времени двух или более событий пренебрежимо мала по сравнению с вероятностью попадания одного события.
Рисунок 6.16 – Поток событий как случайный процесс
Ординарный поток событий можно интерпретировать как случайный процесс Х(t) - число событий, появившихся до момента t(рис. 6.16). Случайный процесс Х(t) скачкообразно возрастает на одну единицу в точках Q ,Q 2 ,...,Q n .
Поток событий называется потоком без последействия, если число событий, попадающих на любой интервал времени , не зависит от того, сколько событий попало на любой другой не пересекающийся с ним интервал. Практически отсутствие последействия в потоке означает, что события, образующие поток, появляются в те или другие моменты времени независимо друг от друга.
Поток событий называется простейшим, если он стационарен, ординарен и не имеет последействия. Интервал времени T между двумя соседними событиями простейшего потока имеет показательное распределение
(при t>0 ); (6.21)
где / М [Т] -величина, обратная среднему значению интервала Т.
Ординарный поток событий без последействия называется пуассоновским. Простейший поток является частным случаем стационарного пуассоновского потока. Интенсивностью потока событий называется среднее число событий, приходящееся на единицу времени. Для стационарного потока ; для нестационарного потока она в общем случае зависит от времени: .
Марковские случайные процессы . Случайный процесс называют марковским , если он обладает следующим свойством: для любого момента времени t 0 вероятность любого состояния системы в будущем (при t >t 0 ) зависит только от ее состояния в настоящем (при t =t 0 ) и не зависит от того, каким образом система пришла в это состояние.
В данной главе будем рассматривать только марковские процессы c дискретными состояниями S 1, S 2 , ...,S n . Такие процессы удобно иллюстрировать с помощью графа состояний (рис. 5.4), где прямоугольниками (или кружками) обозначены состояния S 1 , S 2 , … системы S, а стрелками - возможные переходы из состояния в состояние (на графе отмечаются только непосредственные переходы, а не переходы через другие состояния).
Рисунок 5.4 – Граф состояний случайного процесса
Иногда на графе состояний отмечают не только возможные переходы из состояния в состояние, но и возможные задержки в прежнем состоянии; это изображается стрелкой («петлей»), направленной из данного состояния в него же, но можно обходиться и без этого. Число состояний системы может быть как конечным, так и бесконечным (но счетным).
Марковский случайный процесс с дискретными состояниями и дискретным временем обычно называют марковской цепью. Для такого процесса моменты t 1 , t 2 ..., когда система S может менять свое состояние, удобно рассматривать как последовательные шаги процесса, а в качестве аргумента, от которого зависит процесс, рассматривать не время t, а номер шага: 1, 2, . . ., k;…. Случайный процесс в этом случае характеризуется последовательностью состояний
если S(0) - начальное состояние системы (перед первым шагом); S(1) - состояние системы непосредственно после первого шага; ...; S(k) - состояние системы непосредственно после k-го шага....
Событие S i , (i= 1,2,...) является случайным событием, поэтому последовательность состояний (5.6) можно рассматривать как последовательность случайных событий. Начальное состояние S(0) может быть как заданным заранее, так и случайным. О событиях последовательности (5.6) говорят, что они образуют марковскую цепь.
Рассмотрим процесс с n возможными состояниями S 1, S 2 , ..., S n . Если обозначить через Х(t) номер состояния, в котором находится система S в момент t, то процесс описывается целочисленной случайной функцией Х(t)>0 , возможные значения которой равны 1, 2,...,n . Эта функция совершает скачки от одного целочисленного значения к другому в заданные моменты t 1 , t 2 , ... (рис. 5.5) и является непрерывной слева, что отмечено точками на рис. 5.5.
Рисунок 5.5 – График случайного процесса
Рассмотрим одномерный закон распределения случайной функции Х(t). Обозначим через вероятность того, что после k -го шага [и до (k+1 )-го] система S будет в состоянии S i (i=1,2,...,n) . Вероятности р i (k) называются вероятностями состояний цепи Маркова. Очевидно, для любого k
. (5.7)
Распределение вероятностей состояний в начале процесса
p 1 (0) ,p 2 (0),…,p i (0),…,p n (0) (5.8)
называется начальным распределением вероятностей марковской цепи. В частности, если начальное состояние S(0) системы S в точности известно, например S(0)=S i , то начальная вероятность P i (0) = 1, а все остальные равны нулю.
Вероятностью перехода на k -м шаге из состояния S i в состояние S j называется условная вероятность того, что система после k -го шага окажется в состоянии S j при условии, что непосредственно перед этим (после k - 1 шагов) она находилась в состоянии S i . Вероятности перехода иногда называются также «переходными вероятностями».
Марковская цепь называется однородной, если переходные вероятности не зависят от номера шага, а зависят только от того, из какого состояния и в какое осуществляется переход:
Переходные вероятности однородной марковской цепи Р ij образуют квадратную таблицу (матрицу) размером n * n :
(5.10)
. (5.11)
Матрицу, обладающую таким свойством, называют стохастической. Вероятность Р ij есть не что иное, как вероятность того, что система, пришедшая к данному шагу в состояние S j , в нем же и задержится на очередном шаге.
Если для однородной цепи Маркова заданы начальное распределение вероятностей (5.8) и матрица переходных вероятностей (5.10), то вероятности состояний системы 
могут быть определены по рекуррентной формуле
(5.12)
Для неоднородной цепи Маркова вероятности перехода в матрице (5.10) и формуле (5.12) зависят от номера шага k .
Для однородной цепи Маркова, если все состояния являются существенными, а число состояний конечно, существует предел 
определяемый из системы уравнений и Сумма переходных вероятностей в любой строке матрицы равна единице. 
При фактических вычислениях по формуле (5.12) надо в ней учитывать не все состояния S j , а только те, для которых переходные вероятности отличны от нуля, т.е. те, из которых на графе состояний ведут стрелки в состояние S i .
Марковский случайный процесс с дискретными состояниями и непрерывным временем иногда называют «непрерывной цепью Маркова» . Для такого процесса вероятность перехода из состояния S i в S j для любого момента времени равна нулю. Вместо вероятности перехода p ij рассматривают плотность вероятности перехода которая определяется как предел отношения вероятности перехода из состояния S i в состояние S j за малый промежуток времени , примыкающий к моменту t, к длине этого промежутка, когда она стремится к нулю. Плотность вероятности перехода может быть как постоянной (), так и зависящей от времени . В первом случае марковский случайный процесс с дискретными состояниями и непрерывным временем называется однородным. Типичный пример такого процесса - случайный процесс Х(t), представляющий собой число появившихся до момента t событий в простейшем потоке (рис. 5.2).
При рассмотрении случайных процессов с дискретными состояниями и непрерывным временем удобно представлять переходы системы S из состояния в состояние как происходящие под влиянием некоторых потоков событий. При этом плотности вероятностей перехода получают смысл интенсивностей соответствующих потоков событий (как только происходит первое событие в потоке с интенсивностью , система из состояния S i скачком переходит в Sj) . Если все эти потоки пуассоновские, то процесс, протекающий в системе S, будет марковским.
Рассматривая марковские случайные процессы с дискретными состояниями и непрерывным временем, удобно пользоваться графом состояний, на котором против каждой стрелки, ведущей из состояния S i , в S j проставлена интенсивность потока событий, переводящего систему по данной стрелке (рис.5.6). Такой граф состояний называют размеченным.
Вероятность того, что система S, находящаяся в состоянии S i , за элементарный промежуток времени () перейдет в состояние S j (элемент вероятности перехода из S i в S j ), есть вероятность того, что за это время dt появится хотя бы одно событие потока, переводящего систему S из S i в S j . С точностью до бесконечно малых высших порядков эта вероятность равна .
Потоком вероятности перехода из состояния Si в Sj называется величина (здесь интенсивность может быть как зависящей, так и независящей от времени).
Рассмотрим случай, когда система S имеет конечное число состояний S 1, S 2 ,..., S п. Для описания случайного процесса, протекающего в этой системе, применяются вероятности состояний
(5.13)
где р i (t) - вероятность того, что система S в момент t находится в состоянии S i:
. (5.14)
Очевидно, для любого t
Для нахождения вероятностей (5.13) нужно решить систему дифференциальных уравнений (уравнений Колмогорова), имеющих вид
(i=1,2,…,n),
или, опуская аргумент t у переменных р i ,
(i=1,2,…,n
).
(5.16)
Напомним, что интенсивности потоков ij могут зависеть от времени .
Уравнения (5.16) удобно составлять, пользуясь размеченным графом состояний системы и следующим мнемоническим правилом: производная вероятности каждого состояния равна сумме всех потоков вероятности, переводящих из других состояний в данное, минус сумма всех потоков вероятности, переводящих из данного состояния в другие. Например, для системы S, размеченный граф состояний которой дан на рис. 10.6, система уравнений Колмогорова имеет вид
(5.17)
Так как для любого t выполняется условие (5.15), можно любую из вероятностей (5.13) выразить через остальные и таким образом уменьшить число уравнений на одно.
Чтобы решить систему дифференциальных уравнений (5.16) для вероятностей состояний р 1 (t) p 2 (t ), …, p n (t ), нужно задать начальное распределение вероятностей
p 1 (0),p 2 (0), …,p i (0), …,p n (0 ), (5.18)
сумма которых равна единице.
Если, в частности, в начальный момент t = 0 состояние системы S в точности известно, например, S(0) =S i , и р i (0) = 1, то остальные вероятноcти выражения (5.18) равны нулю.
Во многих случаях, когда процесс, протекающий в системе, длится достаточно долго, возникает вопрос о предельном поведении вероятностей р i (t) при . Если все потоки событий, переводящие систему из состояния в состояние, являются простейшими (т.е. стационарными пуассоновскими с постоянными интенсивностями ), в некоторых случаях существуют финальные (или предельные) вероятности состояний
, (5.19)
независящие от того, в каком состоянии система S находилась в начальный момент. Это означает, что с течением времени в системе S устанавливается предельный стационарный режим, в ходе которого она переходит из состояния в состояние, но вероятности состояний уже не меняются. В этом предельном режиме каждая финальная вероятность может быть истолкована как среднее относительное время пребывания системы в данном состоянии.
Систему, в которой существуют финальные вероятности, называют эргодической. Если система S имеет конечное число состояний S 1 , S 2 , . . . , S n , то для существования финальных вероятностей достаточно, чтобы из любого состояния системы можно было (за какое-то число шагов) перейти в любое другое. Если число состояний S 1 , S 2 , . . . , S n , бесконечно, то это условие перестает быть достаточным, и существование финальных вероятностей зависит не только от графа состояний, но и от интенсивностей .
Финальные вероятности состояний (если они существуют) могут быть получены решением системы линейных алгебраических уравнений,
они получаются из дифференциальных уравнений Колмогорова, если положить в них левые части (производные) равными нулю. Однако удобнее составлять эти уравнения непосредственно по графу состояний, пользуясь мнемоническим правилом: для каждого состояния суммарный выходящий поток вероятности равен суммарному входящему.
Например, для системы S, размеченный граф состояний которой дан на р 
ис. 5.7, уравнения для финальных вероятностей состояний имеют вид
(5.20)
Таким образом, получается (для системы S с п состояниями) система n однородных линейных алгебраических уравнений с n неизвестными р 1, р 2 , ..., р п. Из этой системы можно найти неизвестные р 1 , р 2 , . . . , р п с точностью до произвольного множителя. Чтобы найти точные значения р 1 ,..., р п, к уравнениям добавляют нормировочное условие p 1 + p 2 + … + p п =1, пользуясь которым можно выразить любую из вероятностей p i через другие (и соответственно отбросить одно из уравнений).
Вопросы для повторения
1 Что называют случайной функцией, случайным процессом, сечением случайного процесса, его реализацией?
2 Как различаются случайные процессы по своей структуре и характеру протекания во времени?
3 Какие законы распределения случайной функции применяют для описания случайной функции?
4 Что представляет собой функция математического ожидания случайной функции, в чем ее геометрический смысл?
5 Что представляет собой функция дисперсии случайной функции, в чем ее геометрический смысл?
6 Что представляет собой корреляционная функция случайного процесса, и что она характеризует?
7 Каковы свойства корреляционной функции случайного процесса?
8 Для чего введено понятие нормированной корреляционной функции?
9 Объясните как по опытным данным получить оценки функций характеристик случайного процесса?
10 В чем отличие взаимной корреляционной функции от автокорреляционной функции?
11 Какой случайный процесс относят к стационарным процессам в узком смысле и в широком?
12 В чем заключается свойство эргодичности стационарного случайного процесса?
13 Что понимают под спектральным разложением стационарного случайного процесса и в чем его необходимость?
14 Какова связь между корреляционной функцией и спектральной плотностью стационарной случайной функции?
15 Что называют простейшим потоком событий?
16 Какой случайный процесс называют марковской цепью? В чем заключается методика расчета ее состояний?
17 Что представляет собой марковский случайный процесс с дискретными состояниями и непрерывным временем?
M(U)=10, D(U)=0.2 .
6.5 Найти нормированную взаимную корреляционную функцию случайных функций X(t)=t*U и Y(t)=(t+1)U , где U – случайная величина, причем дисперсия D(U)=10 .
На практике мы почти никогда не имеем дела с марковскими процессами в чистом виде: реальные процессы почти всегда обладают тем или другим последействием. Для марковского процесса время пребывания системы подряд в каком-либо состоянии распределено по показательному закону; на самом деле это далеко не всегда бывает так. Например, если поток событий, переводящий систему из состояния в состояние есть поток отказов какого-то узла, то более естественно предположить, что оставшееся время безотказной работы узла зависит от того, сколько времени узел уже работал. При этом время пребывания узла в рабочем состоянии представляет собой случайную величину, распределенную не по показательному, а по какому-то иному закону. Возникает вопрос о том, можно ли приближенно заменять непуассоновские потоки - пуассоновскими и к каким ошибкам в предельных вероятностях состояний может привести подобная замена. Для этого необходимо уметь хотя бы приближенно исследовать случайные процессы, протекающие в системах с последействием.
Рассмотрим некоторую физическую систему S, в которой протекает случайный процесс, направляемый какими-то непуассоновскими потоками событий. Если мы попробуем для этого процесса написать уравнения, выражающие вероятности состояний как функции времени, мы увидим, что в общем случае это нам не удастся. Действительно, для марковской системы мы вычисляли вероятность того, что в момент система будет в состоянии учитывая только то, в каком состоянии система была в момент t, и не учитывая, сколько времени она была в этом состоянии. Для немарковской системы этот прием уже непригоден: вычисляя вероятность перехода из одного состояния в другое за время мы должны будем учитывать, сколько времени система уже провела в данном состоянии. Это приводит, вместо обыкновенных дифференциальных уравнений, к уравнениям с частными производными, то есть к гораздо более сложному математическому аппарату, с помощью которого только в редких случаях можно получить нужные результаты.
Возникает вопрос: а нельзя ли свести искусственно (хотя бы приближенно) немарковский процесс к марковскому?
Оказывается, в некоторых случаях это возможно: а именно, если число состояний системы не очень велико, а отличающиеся от простейших потоки событий, участвующие в задаче, представляют собой (точно или приближенно) потоки Эрланга. Тогда, вводя в схему возможных состояний системы некоторые фиктивные «псевдосостояния», удается свести немарковский процесс к марковскому и описать его с помощью обыкновенных дифференциальных уравнений, которые при переходят в алгебраические уравнения для предельных вероятностей состояний.
Поясним идею метода «псевдосостояний» на конкретном примере.
Пример 1. Рассматривается система S - Техническое устройство, которое может выходить из строя под влиянием простейшего потока неисправностей с интенсивностью к. Отказавшее устройство немедленно начинает восстанавливаться. Время восстановления (ремонта) Т распределено не по показательному закону (как надо было бы для того, чтобы процесс был марковским), а по закону Эрланга порядка:
Требуется свести данный немарковский процесс к марковскому и найти для него предельные вероятности состояний.
Решение. Случайная величина Т - время восстановления - распределена по закону Эрланга и, значит, представляет собой сумму трех случайных величин распределенных по показательному закону (см. § 5 гл. 4) с параметром
Истинных состояний системы всего два:
Устройство исправно;
Устройство восстанавливается.
Граф этих состояний показан на (он относится к циклической схеме).
Однако в виду того, что переход по стрелке происходит под влиянием не простейшего, а эрланговского потока событий, процесс, происходящий в системе, марковским не является, и для него мы не можем написать ни дифференциальных, ни алгебраических уравнений.
Чтобы искусственно свести это процесс к марковскому, введем в цепочку состояний, вместо одного состояния три последовательных «псевдосостояния».
Ремонт начинается;
Ремонт продолжается;
Ремонт заканчивается, т. е. разделим ремонт на три этапа или «фазы», причем время пребывания системы в каждой из фаз будем считать распределенным по показательному закону (10.2). Граф состояний будет иметь вид, показанный на рис. 4.48, где роль одного состояния будут играть три псевдосостояния Процесс, протекающий в такой системе, уже будет марковским.
Обозначим - предельные вероятности пребывания системы в псевдосостояниях тогда
Обозначая
можем сразу написать (как для обычной циклической схемы) предельные вероятности состояний:
Заметим, что величина представляет собой не что иное, как среднее время восстановления (ремонта) - оно равно сумме средних времен пребывания системы в каждой фазе ремонта.
Переходя в формулах для от средних времен к интенсивностям потоков, по формулам получим:
Таким образом, получен вывод: для нашего элементарного примера вероятность пребывания в каждом из двух состояний, как и для марковского цикла, равна относительному среднему времени пребывания подряд в каждом из состояний.
Следующий пример будет несколько сложнее.
Пример 2. Техническое устройство S состоит из двух одинаковых узлов, каждый из которых может выходить из строя (отказывать) под влиянием простейшего потока неисправностей с интенсивностью 1. Отказавший узел немедленно начинает ремонтироваться. Время ремонта Т распределено по закону Эрланга второго порядка:
Требуется найти предельные вероятности состояний системы.
Решение. Истинных состояний системы три (нумеруем их по числу отказавших узлов).
Оба узла работают;
Один узел работает, другой ремонтируется;
Оба узла ремонтируются.
Разделим условно ремонт на две фазы: ремонт начинается и ремонт заканчивается.
Один узел работает, другой начинает ремонтироваться;
Один узел работает, другой кончает ремонтироваться;
Оба узла начинают рамонтироваться;
Один узел начинает ремонтироваться, а другой кончает;
Оба узла кончают ремонтироваться.
Граф состояний системы с псевдосостояниями показан на рис. 4.49. На стрелках, ведущих из и из написано а не потому что перейти в следующую фазу ремонта (окончание ремонта) может любой из двух узлов.
Уравнения для предельных вероятностей состояний имеют вид:
Из третьего, пятого и шестого уравнений (10.4) имеем:
что дает возможность уменьшить число неизвестных: подставляя (10.5) в оставшиеся три уравнения (10.4), получим:
Из этих трех уравнений с тремя неизвестными можно по произволу отбросить любое, например, последнее, и добавить нормировочное условие:
или, с учетом (10.5),
Учебные вопросы:
Основные понятия Марковских процессов.
Потоки событий.
Пуассоновский поток.
Дискретные Марковские цепи.
Эргодические и поглощающие цепи.
Непрерывные Марковские цепи.
Приложения Марковских процессов.
Теория Марковских случайных процессов.
У теории вероятности очень интересная история. Корни науки уходят далеко в глубь веков, в древнейших государствах – Китае, Индии, Египте, Греции использовались некоторые элементы теории вероятности для переписи населения и даже для определения численности войск неприятеля.
Основоположником теории считают математика, физика и философа Б. Паскаля. Впервые он занялся теорией вероятностей под влиянием вопросов, поставленных перед ним одним из придворных французского двора – шевалье де Мере, блестящим кавалером, философом, искусствоведом и азартным игроком. Но и игра была поводом для глубоких размышлений. Де Мере предложил Б. Паскалю два знаменитых вопроса:
1. Сколько раз надо бросить две игральные кости, чтобы случаев выпадения сразу двух шестерок было больше половины от общего числа бросаний?
2. Как справедливо разделить поставленные на кон двумя игроками деньги, если они по каким-либо причинам прекратили игру преждевременно?
Эти задачи послужили поводом для первоначального введения понятия «математическое ожидание» и формулирования основных теорем сложения и перемножения вероятностей. Вскоре были определены практические приложения: страхование, демография и т.д.
Якоб Бернулли открыл закон больших чисел, который дал возможность установить связь между вероятностью какого-либо случайного события и частотой его появления, наблюдаемой непосредственно из опыта.
Дальнейшие успехи развития теории вероятностей связаны с П. Лапласом, К. Гауссом, С. Пуассоном и др.
В России математик В.Я. Буняковский в начале 19 в. написал первый учебник по теории вероятностей и разработал ее терминологию в современном виде. П.А. Чебышев, А.А. Марков и А.М. Ляпунов ввели понятие «случайной величины», с которой начала развиваться новая ветвь теории вероятности – теория случайных процессов.
Основные понятия Марковских процессов
Функционирование различных систем представляет собой последовательность переходов из одного состояния в другое. Если состояние системы меняется во времени случайным образом, то последовательность состояний может рассматриваться как случайный процесс.
Система называется системой с дискретными состояниями , если множество ее состояний конечно, а переходы из одного состояния в другое осуществляется скачком.
Процесс перехода называется цепью .
Определение цепи Маркова
Имеется некоторая физическая система, имеющая конечное число К
всех возможных фазовых состояний . Пусть в зависимости от вмешательства случая система шаг за шагом (в моменты времени t 0
где - одно из возможных пространств состояний .
Вероятность перехода на m-шаге (условная вероятность):
Таким образом, для вычисления совместных вероятностей Р(Q 0 , ..,Q n) необходимо задать начальное состояние системы и указать физический механизм осуществления смены состояний, позволяющий вычислить вероятности перехода .
1. Частный (вырожденный) случай цепи Маркова. Смена всех состояний происходит независимо, то есть вероятность какого-либо состояния на m-м шаге не зависит от того, в каких состояниях находилась система в предыдущие моменты времени.
– последовательность независимых испытаний.
2. Вероятность фазового состояния параметра Q n в момент времени t n зависит лишь от того, в каком состоянии находилась система в непосредственно предшествующий ему момент времени t n-1 , и не зависит от того, в каких состояниях находилась система в более ранние моменты времени t 0 ,…,t n-2 .
3. Цепь Маркова порядка , если вероятность нового состояния зависит только от m состояний системы, непосредственно ему предшествующих:
Время пребывания системы в некотором состоянии может быть либо дискретным, либо непрерывным. В зависимости от этого различают системы с дискретным или непрерывным временем.
Простейшей вероятностной характеристикой случайного процесса служит набор вероятностей состояний P 1 (t), P 2 (t), ... P n (t), где P i (t) – вероятность перехода системы в состояние S i в момент времени t . Условие нормировки P 1 +P 2 +...+P n =1 .
Если в процессе функционирования система оказывается в состоянии S i , то вероятность перехода ее в состояние S j в общем случае зависит не только от состояния S i , но и от предыдущего состояния.
Случайный процесс, протекающий в системе, называется Марковским (процессом без последействия), если для любого момента времени t 0 вероятность состояния системы в будущем (при t>t 0 ) зависит только от состояния в настоящем (при t=t 0 ) и не зависит от того, как и каким образом, система пришла в данное состояние (т.е. не зависит от предыстории).
Потоки событий
Переход системы в некоторое состояние является событием .
Последовательность переходов системы в состояние S i представляет собой поток событий.
Поток событий называется ординарным , если событие в нем происходит по одиночке.
Интервалы времени t 1 , t 2 , ... t n ординарного потока могут быть одинаковыми или различными, дискретными или непрерывными, случайными или неслучайными.
Если интервалы времени t 1 , t 2 , ... t n – неслучайные величины, то поток называется регулярным или детерминированным, и этот поток описывается путем задания значений T 1 ,T 2 , ... T n .
Если T 1 ,T 2 , ... T n являются случайными, то поток называется случайным и он характеризуется законом распределения величин T 1 ,T 2 ,... T n .
На практике часто встречаются системы, в которых T i – непрерывная случайная величина. В этих случаях система может быть описана плотностью вероятности f(t 1 , t 2 , ... t n) , где t i – конкретное значение случайной величины T i .
Поток называется стационарным , если его вероятностные характеристики не изменяются во времени, т.е. вероятность попадания того или иного числа событий m на участок оси времени t¢+t зависит только от длины участка t и не зависит от того, где на оси времени выбран участок.
Интенсивность (плотность) потока событий (средняя величина событий в единицу времени) является постоянной.
Если интервал времени t i является равномерной случайной величиной, то такой поток называется потоком с последействием и его состояние находится в вероятностной зависимости от предыдущего состояния.
Если случайные величины t i независимые, то такой поток называется потоком с ограниченным последействием и плотность вероятности этого потока равна произведению плотностей вероятности:
f(t 1 ,t 2 , ...t n) = f 1 (t 1) f 2 (t 2) ... f n (t n) (6.5)
Поток с ограниченным последействием может быть стационарным и однородным во времени. В этом случае все интервалы между смежными событиями имеют одинаковый закон распределения:
f i (t i) = f(t i) (6.6)
Потоком без последействия называется случайный поток, если для любых непересекающихся участков времени число событий попадающих на один из них не зависит от того, сколько событий попало на другие участки.
Пуассоновский поток
Потоки случайных событий называются пуассоновскими , если число событий потока m, попадающих на любой участок t, распределен по закону Пуассона
P m = e - a , (6.7)
где а – среднее число событий, находящихся на участке t .
Пуассоновский поток является стационарным, если плотность событий l постоянна, тогда среднее число событий равно lt , иначе поток будет нестационарным.
Случайный поток событий, который обладает свойством стационарности, ординарности и не имеет последействия, называется простейшим и является стационарным пуассоновским потоком .
Просеянные потоки
Процесс переходов системы с дискретным временем функционирования может рассматриваться как воздействие дискретного потока событий, которое характеризуется тем, что в моменты времени t 1 , t 2 , ..., t n события происходят с вероятностью P i . Функция распределения такого потока:
Просеяние потока событий S 1 , S 2 , ... S n , которые наступают в определенные моменты времени с вероятностями p 1 , p 2 , ... p n , означает преобразование этих вероятностей в , , ..., . Если поток является стационарным, то эти вероятности равны: = =...=1-p.
При этом p является константой просеивания, которая определяется либо воздействием какого-либо дестабилизирующего фактора, либо определяется исключением каких-либо событий из множества состояний системы.
Примерами потоков с ограниченным последействием являются потоки Эрланга. Они образуются закономерным просеиванием простейшего потока, при этом под закономерным просеиванием понимается процедура, в результате которой происходит исключение нескольких последующих событий в исходном потоке. Если у простейшего потока исключается каждое нечетное событие, то оставшиеся события образуют поток Эрланга II порядка. Промежуток времени между соседними событиями в таком потоке представляет собой сумму независимых случайных величин и , распределенных по показательному закону ( = + ).
Если в простейшем потоке сохранить только каждое третье событие, то получим поток Эрланга III порядка и т.д. В общем случае, потоком Эрланга k -порядка называется простейший поток, полученный исключением (k- 1) событий и сохранением k -го события.
Дискретные Марковские цепи
Марковский случайный процесс с дискретными состояниями и дискретным временем функционирования описывает систему S с конечным числом состояний. При этом переходы возможны в фиксированные моменты времени t 1 , t 2 , ..., t k . Процесс, происходящий в этой системе, можно представить в виде цепочки случайных событий
S 1 (0) ® S 2 (1) ® ... ® S i (n) ® ... ® S n (k).
Эта последовательность называется дискретной Марковской цепью, если для каждого шага n=1,2, ... k вероятность переходов из любого состояния (S i ®S j) не зависит от того, как система пришла в состояние S i . Каждому переходу системы соответствует условная вероятность
P . (6.9)
Для каждого номера шага n возможные переходы образуют полную группу событий .
однородной , если переходные вероятности не зависят от номера шага. Полным описанием такой цепи может служить квадратная матрица переходных вероятностей
| P 11 | P 12 | ... | P 1n | |
| P ij = | P 21 | P 22 | ... | P 2n |
| ... | ... | ... | ... | |
| P n1 | P n2 | ... | P nn |
и вектор начального распределения вероятностей для всех состояний в момент времени t=0.
= . (6.10)
Переходные вероятности, соответствующие невозможным переходам, равны 0, а вероятности, расположенные по главной диагонали, соответствуют тому факту, что система не изменила своего состояния.
Дискретная Марковская цепь называется неоднородной , если переходные вероятности меняются с изменением номера шага. Для описания таких цепей необходимо задать k матриц переходных вероятностей P ij (k – число рассматриваемых шагов). Главной задачей анализа Марковских процессов является определение вероятность всех состояний системы после любого количества шагов. При этом если известна матрица переходных вероятностей и вектор начального распределения, то вероятности состояний системы после каждого шага определяются по формуле полной вероятности:
P(A) = P(B i)*P(A/B i) (6.11)
После первого шага вероятность P i может быть определена следующим образом:
P i (1) = P j (0)P ji , (6.12)
где P j (0) – вектор начальных состояний,
P ji – строка матрицы условных вероятностей.
P i (2) = P j (1)P ji = P j (0)P ji (1) (6.13)
После k шагов:
P i (k) = P j (k-1)P ji = P j (0)P ji (k), (6.14)
где P ji (k) – вероятности переходов системы из состояния S i в S j за k шагов.
Если возможен переход из состояния S i в состояние S j за k шагов, то величина P ji (k)>0 . Если при этом возможен обратный переход за то же число шагов, то состояние S i называется возвратным . Вероятность того, что система выйдет из состояния S i и за k шагов вернется в него же, равна 1 для возвратных состояний.
Состояние S i - невозвратное , если эта вероятность отлична от 1.
Состояния S i и S j называются сообщающимися , если возможен переход S i ®S j за конечное число шагов.
Цель лекции: освоение понятий поток событий, простейший поток событий, Марковский процесс.
1.Поток событий. Свойства потоков событий. Простейший поток событий. Формула Пуассона.
2. Процесс обслуживания как Марковский процесс.
3. Одноканальная СМО с ожиданием.
Потоком событий называется последовательность однородных событий, следующих одно за другим в случайные моменты времени.
Примерами могут быть:
Поток вызовов на телефонной станции;
Поток сбоев компьютера;
Поток выстрелов, направляемых на цель, и т.д.
Регулярным потоком называется поток, в котором события следуют одно за другим через одинаковые промежутки времени (детерминированная последовательность событий).
Такой поток событий редко встречается на практике. В телекоммуникационных системах чаще встречаются потоки, для которых и моменты наступления событий и промежутки времени между ними являются случайными.
Рассмотрим такие свойства потоков событий, как стационарность, ординарность и отсутствие последействия.
Поток стационарен, если вероятность появления какого-то числа событий на интервале времени τ зависит только от длины этого интервала и не зависит от его расположения на оси времени. Для стационарного потока среднее число событий в единицу времени постоянно.
Ординарным потоком называется поток, для которого вероятность попадания на данный малый отрезок времени двух и более требований пренебрежительно мала по сравнению с вероятностью попадания одного требования.
В системах телекоммуникаций поток принято считать ординарным.
Потокбез последствия характеризуется тем, что для двух непересекающихся интервалов времени
вероятность появления числа событий на втором интервале не зависит от числа появления событий на первом интервале.
Параметром потока называется предел
где - вероятность того, что на интервале появятся заявки.
Интенсивностью потока μ называется среднее число событий в единицу времени.
Для стационарного потока его параметр не зависит от времени .
Для стационарного и ординарного потока λ=μ.
Простейшим или пуассоновским потоком называется стационарный, ординарный поток без последействия.
Простейший поток подчиняется пуассоновскому закону распределения
где - интенсивность потока;
Количество событий, появляющихся за время .
Простейший поток можно задать функцией распределения промежутка между соседними вызовами
F(t)=P(z
P(z>t) равносильна вероятности того, что в промежутке длиной t не поступит не одного вызова.
F(t)=P(z>t)=1- (t)=1-
Данный закон распределения случайной величины называется показательным.
Свойства и характеристики простейшего потока:
а) для простейшего потока математическое ожидание и среднеквадратическое отклонение величины промежутка z равны между собой MZ= σz=1/λ;
б) Математическое ожидание и дисперсия числа вызовов i за промежуток времени t равны между собой Mi=Di= λt.
Совпадение этих величин используют на практике при проверке реального потока для соответствия его простейшему.
В предыдущих лекциях мы научились имитировать наступление случайных событий. То есть мы можем разыграть какое из возможных событий наступит и в каком количестве. Чтобы это определить, надо знать статистические характеристики появления событий, например, такой величиной может быть вероятность появления события, или распределение вероятностей разных событий, если типов этих событий бесконечно много.
Но часто еще важно знать, когда конкретно наступит то или иное событие во времени.
Когда событий много и они следуют друг за другом, то они образуют поток . Заметим, что события при этом должны быть однородными, то есть похожими чем-то друг на друга. Например, появление водителей на АЗС, желающих заправить свой автомобиль. То есть, однородные события образуют некий ряд. При этом считается, что статистическая характеристика этого явления (интенсивность потока событий) задана. Интенсивность потока событий указывает, сколько в среднем происходит таких событий за единицу времени. Но когда именно произойдет каждое конкретное событие надо определить методами моделирования. Важно, что, когда мы сгенерируем, например, за 200 часов 1000 событий, их количество будет равно примерно величине средней интенсивности появления событий 1000/200 = 5 событий в час, что является статистической величиной, характеризующей этот поток в целом.
Интенсивность потока в некотором смысле является математическим ожиданием количества событий в единицу времени. Но реально может так оказаться, что в один час появится 4 события, в другой 6, хотя в среднем получается 5 событий в час, поэтому одной величины для характеристики потока недостаточно. Второй величиной, характеризующей насколько велик разброс событий относительно математического ожидания, является, как и ранее, дисперсия. Собственно именно эта величина определяет случайность появления события, слабую предсказуемость момента его появления. Про эту величину мы расскажем в следующей лекции.
Поток событий это последовательность однородных событий, наступающих одно за другим в случайные промежутки времени. На оси времени эти события выглядят как показано на рис. 28.1 .
Примером потока событий могут служить последовательность моментов касания взлетной полосы самолетами, прилетающими в аэропорт.
Интенсивность потока λ это среднее число событий в единицу времени. Интенсивность потока можно рассчитать экспериментально по формуле: λ = N /T н , где N число событий, произошедших за время наблюдения T н .
Если интервал между событиями τ j равен константе или определен какой-либо формулой в виде: t j = f (t j 1) , то поток называется детерминированным . Иначе поток называется случайным .
Случайные потоки бывают:
- ординарные : вероятность одновременного появления двух и более событий равна нулю;
- стационарные : частота появления событий λ (t ) = const(t ) ;
- без последействия : вероятность появления случайного события не зависит от момента совершения предыдущих событий.
Пуассоновский поток
За эталон потока в моделировании принято брать пуассоновский поток .
Пуассоновский поток это ординарный поток без последействия.
Как ранее было указано, вероятность того, что за интервал времени (t 0 , t 0 + τ ) произойдет m событий, определяется из закона Пуассона:
где a параметр Пуассона.
Если λ (t ) = const(t ) , то это стационарный поток Пуассона (простейший). В этом случае a = λ · t . Если λ = var(t ) , то это нестационарный поток Пуассона .
Для простейшего потока вероятность появления m событий за время τ равна:
Вероятность непоявления (то есть ни одного, m = 0 ) события за время τ равна:
Рис. 28.2 иллюстрирует зависимость P 0 от времени. Очевидно, что чем больше время наблюдения, тем вероятность непоявления ни одного события меньше. Кроме того, чем более значение λ , тем круче идет график, то есть быстрее убывает вероятность. Это соответствует тому, что если интенсивность появления событий велика, то вероятность непоявления события быстро уменьшается со временем наблюдения.
Вероятность появления хотя бы одного события (P ХБ1С ) вычисляется так:
так как P ХБ1С + P 0 = 1 (либо появится хотя бы одно событие, либо не появится ни одного, другого не дано).
Из графика на рис. 28.3 видно, что вероятность появления хотя бы одного события стремится со временем к единице, то есть при соответствующем длительном наблюдении события таковое обязательно рано или поздно произойдет. Чем дольше мы наблюдаем за событием (чем более t ), тем больше вероятность того, что событие произойдет график функции монотонно возрастает.
Чем больше интенсивность появления события (чем больше λ ), тем быстрее наступает это событие, и тем быстрее функция стремится к единице. На графике параметр λ представлен крутизной линии (наклон касательной).
Если увеличивать λ , то при наблюдении за событием в течение одного и того же времени τ , вероятность наступления события возрастает (см. рис. 28.4 ). Очевидно, что график исходит из 0, так как если время наблюдения бесконечно мало, то вероятность того, что событие произойдет за это время, ничтожна. И наоборот, если время наблюдения бесконечно велико, то событие обязательно произойдет хотя бы один раз, значит, график стремится к значению вероятности равной 1.
Изучая закон, можно определить, что: m x = 1/λ , σ = 1/λ , то есть для простейшего потока m x = σ . Равенство математического ожидания среднеквадратичному отклонению означает, что данный поток поток без последействия. Дисперсия (точнее, среднеквадратичное отклонение) такого потока велика. Физически это означает, что время появления события (расстояние между событиями) плохо предсказуемо, случайно, находится в интервале m x σ < τ j < m x + σ . Хотя ясно, что в среднем оно примерно равно: τ j = m x = T н /N . Событие может появиться в любой момент времени, но в пределах разброса этого момента τ j относительно m x на [σ ; +σ ] (величину последействия). На рис. 28.5 показаны возможные положения события 2 относительно оси времени при заданном σ . В данном случае говорят, что первое событие не влияет на второе, второе на третье и так далее, то есть последействие отсутствует.
По смыслу P равно r (см. лекцию 23. Моделирование случайного события. Моделирование полной группы несовместных событий), поэтому, выражая τ из формулы (*) , окончательно для определения интервалов между двумя случайными событиями имеем:
τ = 1/λ · Ln(r ) ,
где r равномерно распределенное от 0 до 1 случайное число, которое берут из ГСЧ, τ интервал между случайными событиями (случайная величина τ j ).
Пример 1 . Рассмотрим поток изделий, приходящих на технологическую операцию. Изделия приходят случайным образом в среднем восемь штук за сутки (интенсивность потока λ = 8/24 [ед/час] ). Необходимо промоделировать этот процесс в течение T н = 100 часов . m = 1/λ = 24/8 = 3 , то есть в среднем одна деталь за три часа. Заметим, что σ = 3 . На рис. 28.6 представлен алгоритм, генерирующий поток случайных событий.
На рис. 28.7 показан результат работы алгоритма моменты времени, когда детали приходили на операцию. Как видно, всего за период T н = 100 производственный узел обработал N = 33 изделия. Если запустить алгоритм снова, то N может оказаться равным, например, 34, 35 или 32. Но в среднем, за K прогонов алгоритма N будет равно 33.33 Если посчитать расстояния между событиями t сi и моментами времени, определяемыми как 3 · i , то в среднем величина будет равна σ = 3 .
Моделирование неординарных потоков событий
Если известно, что поток не является ординарным, то необходимо моделировать кроме момента возникновения события еще и число событий, которое могло появиться в этот момент. Например, вагоны на железнодорожную станцию прибывают в составе поезда в случайные моменты времени (ординарный поток поездов). Но при этом в составе поезда может быть разное (случайное) количество вагонов. В этом случае о потоке вагонов говорят как о потоке неординарных событий.
Допустим, что M k = 10 , σ = 4 (то есть, в среднем в 68 случаях из 100 приходит от 6 до 14 вагонов в составе поезда) и их число распределено по нормальному закону. В место, отмеченное (*) в предыдущем алгоритме (см. рис. 28.6 ), нужно вставить фрагмент, показанный на рис. 28.8 .
Пример 2 . Очень полезным в производстве является решение следующей задачи. Каково среднее время суточного простоя оборудования технологического узла, если узел обрабатывает каждое изделие случайное время, заданное интенсивностью потока случайных событий λ 2 ? При этом экспериментально установлено, что привозят изделия на обработку тоже в случайные моменты времени, заданные потоком λ 1 партиями по 8 штук, причем размер партии колеблется случайно по нормальному закону с m = 8 , σ = 2 (см. лекцию 25). До начала моделирования T = 0 на складе изделий не было. Необходимо промоделировать этот процесс в течение T н = 100 часов.
На рис. 28.9 представлен алгоритм, генерирующий случайным образом поток прихода партий изделий на обработку и поток случайных событий выхода партий изделий с обработки.
На рис. 28.10 показан результат работы алгоритма моменты времени, когда детали приходили на операцию, и моменты времени, когда детали покидали операцию. На третьей линии видно, сколько деталей стояло в очереди на обработку (лежало на складе узла) в разные моменты времени.
Отмечая для обрабатывающего узла времена, когда он простаивал в ожидании очередной детали (см. на рис. 28.10 участки времени, выделенные красной штриховкой), мы можем посчитать суммарное время простоев узла за все время наблюдения, а затем рассчитать среднее время простоя в течение суток. Для данной реализации это время вычисляется так:
T пр. ср. = 24 · (t 1 пр. + t 2 пр. + t 3 пр. + t 4 пр. + + t N пр.)/T н .
Задание 1 . Меняя величину σ , установите зависимость T пр. ср. (σ ) . Задавая стоимость за простой узла 100 евро/час, установите годовые потери предприятия от нерегулярности в работе поставщиков. Предложите формулировку пункта договора предприятия с поставщиками «Величина штрафа за задержку поставки изделий».
Задание 2 . Меняя величину начального заполнения склада, установите, как изменятся годовые потери предприятия от нерегулярности в работе поставщиков в зависимости от принятой на предприятии величины запасов.
Моделирование нестационарных потоков событий
В ряде случаев интенсивность потока может меняться со временем λ (t ) . Такой поток называется нестационарным . Например, среднее количество за час машин скорой помощи, покидающих станцию по вызовам населения большого города, в течение суток может быть различным. Известно, например, что наибольшее количество вызовов падает на интервалы с 23 до 01 часа ночи и с 05 до 07 утра, тогда как в остальные часы оно вдвое меньше (см. рис. 28.11 ).
В этом случае распределение λ (t ) может быть задано либо графиком, либо формулой, либо таблицей. А в алгоритме, показанном на рис. 28.6 , в место, помеченное (**), нужно будет вставить фрагмент, показанный на рис. 28.12 .