Состояния и интенсивность потока событий

Будем считать, что СМО имеет конечное число дискретных состояний S₁, S₂, S₃,…, S_n , при этом процесс перехода из одного состояния в другое происходит мгновенно в любой случайный момент времени (время непрерывно). Случайный процесс перехода системы из одного состояния S_i в другое состояние S_j называется Марковским, если переходная вероятность p_ij зависит только от текущего состояния системы и не зависит от прошлых состояний.

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

Граф, представленный на этом рисунке, содержит 5 состояний и 8 переходов. Для каждого перехода указана интенсивность потока событий λ_ij, (измеряется в 1/сек), определяющая переход системы из состояния S_i в состояние S_j.

где p_ij (t, t + Δt) - вероятность перехода из состояния i в состояние j за время (t, t + Δt).

λ24 λ35

λ12 λ23 λ45

S1 S2 S3 S4 S5

λ21 λ43

λ52

Рис. 2. Граф состояний марковской модели

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

Уравнения Колмогорова

Переход марковской модели из одного состояния в другое определяется системой дифференциальных уравнений Колмогорова. Вывод этой системы уравнений приведен в Главе 2. Запишем эту систему на конкретном примере Марковского процесса с графом, представленным на рис. 3.2.

В каждый момент времени t система находится в одном из состояний S_i с вероятностью p_i(t). Придадим времени малое приращение Δt. За это время система может остаться в прежнем состоянии или перейти в новое состояние. Проведем расчет вероятностей перехода для этой ситуации.

Система находится в состоянии S₁. Система останется в этом состоянии с вероятностью p₁(t).

Вероятность того, что система уйдет из этого состояния в состояние S₂, равна p₁(t) λ₁₂ Δt.

Вероятность того, что система перейдет из состояния S₂ в состояние S₁, равна p₂(t) λ₂₁ Δt.

Объединяя эти соотношения, получим вероятность того, что система будет находиться в состоянии S₁ в момент времени (t + Δt)

p₁(t + Δt) = p₁(t) - p₁(t) λ₁₂ Δt + p₂(t) λ₂₁ Δt;

Вероятность того, что система останется в состоянии S₁ увеличивается за счет вероятности перехода из состояния S₂ (знак + ) и уменьшается за счет ухода в состояние S₁ (знак - ).

Перепишем это уравнение в следующем виде

В результате предельного перехода при Δt → 0 в левой части этого уравнения получим производную. Тогда

Это первое уравнение системы, определяющее изменение вероятности p₁(t) нахождения системы в состоянии S₁ во времени.

Система находится в состоянии S₂. Вероятность того, что система останется в этом состоянии, равна p₂(t).

Вероятность того, что система уйдет из этого состояния в состояния S₁, S₃ и S₄ равна p₂(t)λ₂₁Δt + p₂(t)λ₂₃Δt + p₂(t)λ₂₄Δt .

Вероятность того, что система перейдет из состояний S₁ и S₅ в состояние S₂ равна p₁(t) λ₁₂ Δt + p₅(t) λ₅₂ Δt.

Объединяя эти соотношения, получим, вероятность того, что система будет находиться в состоянии S₂ в момент времени (t + Δt)

P₂(t + Δt) = p₂(t) + p₁(t) λ₁₂ Δt + p₅(t) λ₅₂ Δt - p₂(t) λ₂₁ Δt -

- p₂(t)λ₂₃Δt - p₂(t) λ₂₄ Δt .

В результате получим второе уравнение системы уравнений Колмогорова

Аналогично получим остальные уравнения Колмогорова.

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

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

с условием

Для марковской модели с графом состояний, приведенным на рис 3.2, система уравнений Колмогорова для стационарного режима имеет следующий вид

с дополнительным условием

Замечание. Эта система из 6 алгебраических уравнений с 5 неизвестными является линейно зависимой. Поэтому одно любое уравнение можно отбросить. В результате решения системы уравнений Колмогорова находится функция распределения вероятностей дискретной случайной величины.