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

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

Понятие случайного процесса

В системе S протекает случайный процесс, если она с течением времени меняет свое состояние (переходит из одного состояния в другое), причем, заранее неизвестным случайным образом.

Непрерывный случайный процесс x (t) определяется заданием системы случайных величин x (t ₁), x (t ₂),..., x (t_n), соответствующих значениям случайного процесса в фиксированные моменты времени t ₁, t ₂, …, t_n. Эти случайные величины описываются n -мерной плотностью f (x ₁, x ₂, …, x_n, t ₁, t ₂,..., t_n) вероятности.

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

Основное свойство марковского процесса может быть выражено соотношением для условной плотности при любых t ₁ < t ₂ < … < t_k:

f (x (t_k + 1)½ x (t ₁), x (t ₂),..., x (t_k)) = f (x (t_k + 1)½ x (t_k)).

Размерность n вектора x (t) называют порядком марковского процесса. Марковская модель является определенной идеализацией по отношению к реальным процессам. Достоинство этой модели состоит в возможности использования эффективных алгоритмов обработки информации.

В исследовании операций большое значение имеют Марковские случайные процессы с дискретными состояниями и непрерывным временем.

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

Далее рассматриваются только процессы с дискретным состоянием и непрерывным временем.

Поток событий (ПС) – последовательность событий, следующих одно за другим в какие-то случайные моменты времени (например, поток отказов и поток восстановлений, поток вызовов на телефонной станции, поток покупателей в магазине и т.д.). Различают потоки однородных и неоднородных событий.

Однородный ПС характеризуется только моментами поступления этих событий (вызывающими моментами) и задаётся последовательностью { t_n } = {0 £ t ₁ £ t ₂ … £ t_n £…}, где t_n – момент поступления n -ого события. ОПС может быть также задан в виде последовательности промежутков времени между n -ым и (n – 1)-ым событиями {t _n }.

Неоднородным ПС называется последовательность { t_n, f_n }, где t_n – вызывающие моменты; f_n – набор признаков события. Например, может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т.п.

Поток событий можно наглядно изобразить рядом точек на оси времени 0 t – рис. 4.1.

Рис. 4.1. Изображение потока событий на оси времени

Положение каждой точки случайно, и здесь изображена лишь какая-то одна реализация потока.

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

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

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

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

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

Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: 1) стационарен, 2) ординарен, 3) не имеет последствий.

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

Рис. 4.2. Показательное распределение простейшего потока событий

Для случайной величины T, имеющей показательное распределение, математическое ожидание m_T есть величина, обратная параметру, а среднее квадратичное отклонение s _T равно математическому ожиданию m_T = s _T = 1/l.

Поток событий называется рекуррентным (иначе – потоком Пальма), если он стационарен, ординарен, а интервалы времени между событиями T ₁, T ₂, Т ₃,... представляют собой независимые случайные величины с одинаковым произвольным распределением (например, с распределением, показанным на рис. 4.3).

Рис. 4.3. Пример потока Пальма

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