Альтернативный вид уравнений Колмогорова

Марковской цепи

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

Вернемся еще раз к формуле (1.2.1). Имеем

,

и тогда

.

Если теперь при Δt→0 объявить предел отношения интенсивностью перехода i → i, то получим систему уравнений

или для однородной цепи Маркова –

.

В матричном виде это будет , где

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

или

и так далее. При таком определении λ_ij интенсивности переходов будут удовлетворять условию

(i =0, 1,2, … n ),

то есть в этом случае значения λ_jj(t) нужно искать по формуле

в согласии с системой уравнений Колмогорова (1.2.2).

Простейший поток событий

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

С точки зрения математики поток событий может быть описан как случайный процесс X(t), принимающий только целочисленные неубывающие значения 0, 1, 2, … Применительно к системам массового обслуживания процесс X(t) есть просто число заявок или требований, поступивших в СМО за промежуток времени от 0до t.

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

Отсутствие последствия (lack of memory). Отсутствие последствия в потоке означает, что для любого момента времени t будущие моменты наступления событий не зависят от того, в какие моменты наступали аналогичные события в прошлом, то есть будущее зависит от прошлого только через настоящее (на языке математики – обычное марковское свойство).

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

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

Говоря другими словами, простейший поток событий представляет собой однородную цепь Маркова с непрерывным временем, обладающую дополнительно еще и свойством ординарности. Граф такой марковской цепи изображен на рис. 3. На этом рисунке λ – это некоторая пока еще не определенная интенсивность соответствующего марковского процесса. Найдем закон распределения вероятностей событий в этом потоке.

Рис. 3

Очевидно, что для графа состояний, изображенного на этом рисунке (точнее говоря, для случайного марковского процесса, соответствующего этому графу состояний), уравнения Колмогорова (1.2.2) примут следующий вид:

, k = 1, 2, … . (1.4.1)

Здесь p_k(λ) – вероятность того, что за время от 0 до t в систему поступит ровно k заявок (или, что то же самое, произойдет ровно k событий).

Начальные условия к этим уравнениям:

; , k=1, 2, …, (1.4.2)

то есть или , где – символ Кронекера:

=

Условия (1.4.2), очевидно, означают, что на начальный момент времени заявки в системе отсутствуют.

Для решения системы уравнений (1.4.1) произведем замену, введя новую функцию U_k(t) по правилу . Тогда уравнения (1.4.1) примут вид

, k =1, 2, … . (1.4.3)

Начальные условия к этим уравнениям, очевидно, задаются равенствами

; , k = 1, 2, …

Теперь из системы (1.4.3) имеем

; ;

;

и так далее. В итоге для всех k =1, 2, … получим формулу

,

так что

. (1.4.4)

Это и есть знаменитое распределение Пуассона, или, точнее говоря, стационарное распределение Пуассона, поскольку в общем случае для этого распределения const. Итак, простейший поток событий описывается вероятностным распределением Пуассона, вследствие чего его часто так и называют – поток Пуассона.

Заметим, что если в начальный момент времени в системе имеются i > 0 требований, а под p_k(t) по-прежнему понимается вероятность того, что за время от 0 до t поступит ровно k заявок, то, как можно показать, в этом случае решение уравнений (1.4.1) даст нам распределение

, k = i +1, i +2, …

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

Далее обозначим через k(t) общее число заявок (требований), поступивших в систему в промежутке времени от 0до t. В этом случае

Таким образом, мы получили, что среднее число требований (заявок), поступивших в систему за промежуток времени от 0 до t, есть просто . Отсюда в свою очередь следует, что интенсивность λ марковского процесса, описываемого соответствующим графом состояний, определяется формулой .

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

.

Таким образом, среднее значение и дисперсия общего числа заявок в простейшем потоке событий одинаковы и равны . Отсюда следует, что коэффициент вариации , равный отношению дисперсии к математическому ожиданию и характеризующий степень нерегулярности потока заявок, в данном случае равен единице. Заметим, что для регулярного или детерминированного потока, то есть потока, в котором промежутки времени между двумя последовательными заявками являются постоянными величинами, коэффициент вариации v равен нулю, для большинства же других законов распределения 0 < v < 1.

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

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

– это вероятность того, что интервал времени между двумя последовательными событиями не превзойдет t или, говоря другими словами, F(t) – вероятность того, что хотя бы одно событие произойдет в некотором интервале времени от 0 до t, если оно произошло в начальный момент времени при t = 0.

Применим эту формулу к потоку Пуассона. Ясно, что в этом случае

,

где – вероятность того, что промежуток времени между двумя последовательными событиями в потоке, напротив, превзойдет t, то есть вероятность того, что на интервале длины t (от 0 до t) не произошло ни одного события. В силу же формулы (1.4.4) вероятность отсутствия событий за время t есть просто и, значит,

, (1.4.5)

а соответствующая плотность вероятности

(1.4.6)

(напомним в этой связи, что по определению

).

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

Покажем, что верно и обратное утверждение, то есть из формулы (1.4.6) можно в свою очередь вывести обратным ходом и закон распределения (1.4.4). В самом деле, очевидно, что

.

Далее, пусть p₁(t) – вероятность того, что за время t в систему придет только одна заявка или, что то же самое, в системе произойдет только одно случайное событие. Пусть это событие произошло в некоторый момент времени τ < t. Это, в свою очередь, означает, что за время t–τ, оставшееся до конца рассматриваемого интервала, в системе не произойдет ни одного случайного события. Вероятность этого для каждого отдельного момента времени (в интервале от τ до t) есть, очевидно, .

В этом случае средняя вероятность отсутствия случайных событий за время от τ до t для всех τ ( ) согласно определению средней величины есть просто

.

Точно так же очевидно, что

и так далее. В результате мы снова получим распределение чисел появления случайных событий в простейшем потоке (1.4.4).

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

Так, например, если время обслуживания какой-либо системы массового обслуживания имеет экспоненциальное распределение, то число обслуженных за время t заявок также подчиняется закону Пуассона со своей средней интенсивностью обслуживания μ:

,

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

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

.

Проинтегрировав это выражение по частям, получим

.

Дисперсия показательно распределенной величины

.

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

.

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

Для полноты картины, а также для проверки и подтверждения истинности полученных результатов необходимо еще продемонстрировать марковское свойство (на языке теории массового обслуживания – свойство отсутствия последствия) полученного нами распределения интервалов между событиями в простейшем потоке (1.4.5). Проще всего это сделать следующим образом. Найдем еще раз F(t) – функцию распределения интервалов времени между событиями в потоке (1.4.4). Для этого повторим вывод формулы для F(t), но уже не для рассмотренного выше отрезка между начальным моментом времени t = 0 и некоторым t, а рассматривая произвольный, в том числе и достаточно удаленный от начальной точки, отрезок времени от t₀ до

t₀ + t, где t₀ – любое фиксированное число. В данном случае событие (приход заявки в систему) происходит внутри отрезка времени от t₀ до t₀ + t (то есть за время, меньшее, чем t₀ + t), но лишь при условии, что это случится не раньше момента времени t₀ (все события, которые имели место до этого времени, нас не интересуют). Очевидно, что тогда функция распределения F(t) будет описываться условной вероятностью

.

Отсюда по формуле для условной вероятности имеем

– уже известный нам закон распределения (1.4.5). Или, говоря другими словами, будущее показательно распределенной случайной величины (после момента времени t₀) не зависит от прошлой истории этой величины (до момента времени t₀), и это распределение остается неизменным во времени. Подчеркнем при этом, что показательное распределение является единственным непрерывным распределением, обладающим этим свойством. В случае же дискретных случайных величин единственным распределением с таким же свойством является геометрическое распределение случайной величины.