8.3.1. Марковские случайные процессы. Уравнения Колмогорова для вероятностей состояний

 

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

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

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

Рассмотрим понятие марковского случайного процесса.

Пусть имеется некоторая физическая система S, состояние которой меняется с течением времени (под системой S может пониматься что угодно: техническое устройство, ремонтная мастерская, вычислительная машина, железнодорожный узел и т.д.). Если состояние системы S меняется во времени случайным, заранее непредсказуемым образом, мы говорим, что в системе S протекает случайный процесс.

Случайный процесс, протекающий в системе S, называется марковским процессом (или «процессом без последействия»), если он обладает следующим свойством:

Для каждого момента времени t₀ вероятность любого состояния системы в будущем (при t>t₀) зависит только от её состояния в настоящем (при t=t₀) и не зависит от того, когда и каким образом система пришла в это состояние (т.е. как развивался процесс в прошлом).

Другими словами, в марковском случайном процессе будущее развитие его зависит только от настоящего состояния и не зависит от «предыстории» процесса.

Рассмотрим пример. Пусть система S представляет собой техническое устройство, которое уже проработало некоторое время, соответственным образом «износилось» и пришло в некоторое состояние, характеризующееся определенной степенью изношенности S. Нас интересует, как будет работать система в будущем. Ясно, что, по крайней мере в первом приближении, характеристики работы системы в будущем (частота отказов, потребность в ремонте) зависят от состояния устройства в настоящий момент и не зависят от того, когда и как устройство достигло своего настоящего состояния.

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

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

Случайный процесс называется процессом с дискретными состояниями, если возможные состояния системы:          

S₁, S₂, S₃, …

можно перечислить (перенумеровать) одно за другим, а сам процесс состоит в том, что время от времени система S скачком (мгновенно) перескакивает из одного состояния в другое.

Пример. Техническое устройство S состоит из двух узлов: I и II, каждый из которых может в ходе работы устройства отказать (выйти из строя). Возможны следующие состояния системы:

S₁ – оба узла работают;        S₂ – первый узел отказал, второй работает;

S₃ – второй узел отказал, первый работает;     S₄ – оба узла отказали.

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

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

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

Пусть имеется система S с дискретными состояниями:

                                           S₁, S₂, …, S_n.

Мы будем изображать каждое состояние прямоугольником, а возможные переходы («перескоки») из состояния в состояние – стрелками, соединяющими эти прямоугольники (рис.8.3.1.1).

 Заметим, что стрелками отмечаются только непосредственные переходы из состояния в состояние; если система может перейти из состояния S₁ в S₃ только через S₂, то стрелками отмечаются только переходы S₁S₂ и S₂S₃, но не S₁S₃.

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

Случайный процесс называется процессом с дискретным временем, если переходы системы из состояния в состояние возможны только в строго определенные, заранее фиксированные моменты времени: t₁, t₂, …. В промежутки времени между этими моментами система S сохраняет свое состояние.

Случайный процесс называется процессом с непрерывным временем, если переход системы из состояния в состояние возможен в любой, наперед неизвестный, случайный момент t.

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

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

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

Пусть имеется ряд дискретных состояний:

                                           S₁, S₂, …, S_n;

переход (перескок) системы S из состояния в состояние может осуществляться в любой момент времени. Граф состояний системы представлен на рис. 8.3.1.2.

Обозначим p_i(t) – вероятность того, что в момент t система S будет находиться в состоянии S_i (i=1,…,n). Очевидно, для любого момента t сумма вероятностей состояний равна единице:

           ,                                

так как события, состоящие в том, что в момент t система находится в состояниях S₁, S₂, …, S_n, несовместны и образуют полную группу.

Поставим задачу – определить для любого t вероятности состояний:           p₁(t), p₂(t), …, p_n(t).

Для того, чтобы найти эти вероятности, необходимо знать характеристики процесса, аналогичные переходным вероятностям для марковской цепи. В случае процесса с непрерывным временем нам не придется задавать определенные, отличные от нуля, переходные вероятности P_ij; вероятность перехода (перескока) системы из состояния в состояние точно в момент t будет равна нулю (так же как вероятность любого отдельного значения непрерывной случайной величины). Вместо переходных вероятностей P_ij мы введем в рассмотрение плотности вероятностей перехода _ij.

Пусть система S в момент t находится в состоянии S_i. Рассмотрим элементарный промежуток времени t, примыкающий к моменту t (рис. 8.3.1.3).

Назовем плотностью вероятности перехода _ij предел отношения вероятности перехода системы за время t из состояния S_i в состояние S_j к длине промежутка t:

,                                                           (8.3.1.1)

где P_ij(t) – вероятность того, что система, находившаяся в момент t в состоянии S_i, за время t перейдет из него в состояние S_j (плотность вероятностей перехода определяется только для ji).

Из формулы (8.3.1.1) следует, что при малом t вероятность перехода P_ij(t) (с точностью до бесконечно малых высших порядков) равна _ijt:

                                           P_ij(t) _ijt.

Если все плотности вероятностей перехода _ij не зависят от t (т.е. от того, в какой момент начинается элементарный участок t), марковский процесс называется однородным; если эти плотности представляют собой какие-то функции времени _ij(t), процесс называется неоднородным. При пользовании сокращенным названием «непрерывная марковская цепь» мы также будем различать однородные и неоднородные цепи.

Предположим, что нам известны плотности вероятностей перехода _ij для всех пар состояний S_i, S_j.

Построим граф состояний системы S и против каждой стрелки проставим соответствующую плотность вероятности перехода (рис.8.3.1.4).

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

Оказывается, зная размеченный граф состояний, можно определить вероятности состояний:

                   p₁(t), p₂(t), …, p_n(t)                                                      (8.3.1.2)

как функции времени. А именно, эти вероятности удовлетворяют определенного вида дифференциальным уравнениям, так называемым уравнениям Колмогорова. Решая эти уравнения, мы получим вероятности (8.3.1.2).

Продемонстрируем методику вывода уравнений Колмогорова для вероятностей состояний на конкретном примере.

Пусть система S имеет четыре возможных состояния:     S₁, S₂, S₃, S₄; размеченный граф состояний системы показан на рис.8.3.1.4.

Поставим себе задачу: найти одну из вероятностей состояний, например, p₁(t). Это есть вероятность того, что в момент t система будет находиться в состоянии S₁.

Как это событие может произойти? Очевидно, двумя способами:

1) в момент t система уже была в состоянии S₁, а за время t не вышла из этого состояния;

2) в момент t система была в состоянии S₃, а за время t перешла из него в S₁.

Вероятность первого варианта найдем как произведение вероятности p₁(t) того, что в момент t система была в состоянии S₁, на условную вероятность того, что будучи в состоянии S₁, система за время t не перейдет из него в S₂. Эта условная вероятность (с точностью до бесконечно малых высших порядков) равна 1-₁₂t.

Аналогично, вероятность второго варианта равна вероятности того, что в момент t система была в состоянии S₃, умноженной на условную вероятность перехода за время t в состояние S₁:

                                           p₃(t)₃₁t.

Применяя правило сложения вероятностей, получим:

                                           p₁(t+t)=p₁(t)(1-₁₂t)+p₃(t)₃₁t.

Раскроем скобки в правой части, перенесем p₁(t) в левую и разделим обе части равенства на t; получим:

.

Теперь устремим t к нулю и перейдем к пределу:

.

Левая часть есть не что иное, как производная функции p₁(t):

.                                    (8.3.1.3)

Таким образом, выведено дифференциальное уравнение, которому должна удовлетворять функция p₁(t). Аналогичные дифференциальные уравнения могут быть выведены и для остальных вероятностей состояния: p₂(t), p₃(t), p₄(t).

Рассмотрим второе состояние S₂ и найдем p₂(t+t), - вероятность того, что в момент (t+t) система S будет находиться в состоянии S₂. Это событие может произойти следующими способами:

       в момент t система уже была в состоянии S₂, а за время t не перешла ни в S₃, ни в S₄;

       в момент t система была в состоянии S₁, а за время t перешла из него в S₂;

       в момент t система была в состоянии S₄, а за время t перешла из него в S₂.

Вероятность первого варианта вычисляется так: p₂(t) умножается на условную вероятность того, что система за t не перейдет ни в S₃, ни в S₄. Так как события, состоящие в переходе за время t из S₂ в S₃ и из S₂ в S₄, несовместны, то вероятность того, что осуществится один из этих переходов, равна сумме их вероятностей, т.е. ₂₃t+₂₄t (с точностью до бесконечно малых высших порядков). Вероятность того, что не осуществится ни один из этих переходов, равна 1-₂₃t-₂₄t. Отсюда вероятность первого варианта:

p₂(t)(1-₂₃t-₂₄t).

Прибавляя сюда вероятности второго и третьего вариантов, получим:

p₂(t+t)= p₂(t)(1-₂₃t-₂₄t)+ p₁(t)₁₂t+ p₄(t)₄₂t.

Перенося p₂(t) в левую часть, деля на t и переходя к пределу, получим дифференциальное уравнение для p₂(t):

.    (8.3.1.4)

Рассуждая аналогично для состояний S₃, S₄, получим в результате систему дифференциальных уравнений, составленных по типу (8.3.1.3) и (8.3.1.4). Отбросим в них для краткости аргумент t у функций р₁, р₂, р₃, р₄ и перепишем эту систему в виде:

             (8.3.1.5)

Эти  уравнения для вероятностей состояний и называются уравнениями Колмогорова.

Интегрирование этой системы уравнений даст нам искомые вероятности состояний как функции времени. Начальные условия берутся в зависимости от того, каково было начальное состояние системы S. Например, если в начальный момент времени (при t=0) система S находилась в состоянии S₁, то надо принять начальные условия:

                               при t=0 p₁=1, p₂=p₃=p₄=0.

Заметим, что всех четырех уравнений для p₁, p₂, p₃, p₄ можно было бы и не писать; действительно, p₁+p₂+p₃+p₄=1 для всех t, и любую из вероятностей p₁, p₂, p₃, p₄ можно выразить через три остальные. Например, p₄ можно выразить через p₁, p₂, p₃ в виде

p₄=1-( p₁+p₂+p₃)

и подставить в остальные уравнения. Тогда специального уравнения для вероятности р₄ можно и не писать. Однако иногда в дальнейшем нам может быть удобнее пользоваться полной системой уравнений типа (8.3.1.5).

Обратим внимание на структуру уравнений (8.3.1.5). Все они построены по вполне определенному правилу, которое можно сформулировать следующим образом.

В левой части каждого уравнения стоит производная вероятности состояния, а правая часть содержит столько членов, сколько стрелок связано с данным состоянием. Если стрелка направлена из состояния, соответствующий член имеет знак «минус»; если в состояние – знак «плюс». Каждый член равен произведению плотности вероятности перехода, соответствующей данной стрелке, умноженной на вероятность того состояния, из которого исходит стрелка.

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