Теория марковских случайных процессов

 

y1	0	0	1	1
y2	0	1	0	1

 

Предположим, что известны вероятности  переходов, представленные в виде матрицы

 

и начальные вероятности P₀(0)=0,7, P₁(0)=P₂(0)=P₃(0)=0,1. Граф переходов для этого процесса имеет вид, показанный на рис. 2.

 

 

 

 

 

 

 

Рис. 2. Граф переходов.

 

Определим вероятности состояний  на различные моменты времени. Согласно формуле (8) вероятности состояний на момент времени t₁:

P₀ (t₁) =P₀ (0) p₀₀ + P₁ (0) p₁₀ +P₂  (0) p₂₀ + P₃  (0) p₃₀ =0.1;

P₁ (t₁) =P₀ (0) p₀₁ + P₁ (0) p₁₁ +P₂  (0) p₂₁ + P₃  (0) p₃₁ =0.18;

P₂ (t₁) =P₀ (0) p₀₂ + P₁ (0) p₁₂ +P₂  (0) p₂₂ + P₃ (0) p₃₂ =0.62;

P₃ (t₁) =P₀ (0) p₀₃+ P₁ (0) p₁₃ +P₂ (0) p₂₃ + P₃ (0) p₃₃ =0.1;

на момент времени t₂:

P₀ (t₂) = P₀ (t₁) p₀₀ + P₁  (t₁) p₁₀ + P₂ (t₁) p₂₀ + P₃ (t₁) p₃₀ =0.4;

P₁ (t₂) = P₀ (t₁) p₀₁ + P₁ (t₁) p₁₁ + P₂ (t₁) p₂₁ + P₃ (t₁) p₃₁ =0.06;

P₂ (t₂) = P₀ (t₁) p₀₂ + P₁ (t₁) p₁₂  + P₂ (t₁) p₂₂ + P₃ (t₁) p₃₂ =0.14;

P₃ (t₂) = P₀ (t₁) p₀₃ + P₁ (t₁) p₁₃ + P₂ (t₁) p₂₃ + P₃ (t₁) p₃₃ =0.4;

и т.д.

Предполагая, что рассматриваемый  случайный процесс обладает эргодическим свойством, что соответствует действительности, определим вероятности состояний для стационарного режима. Искомые вероятности P₀, P₁, P₂, P₃ могут быть найдены, согласно равенствам (10) и (11), из системы уравнений:

P₀ = 0.5P₁ +0.5P₂

P₁ = 0.2P₀ +0.4P₃

P₂ = 0.8P₀ +0.6P₃

P₃ = 0.5P₁ +0.5P₂

P₀ +P₁+P₂ +P₃ =1.

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

Решив систему уравнений, получим: P₀ =0.25; P₁ =0.15; P₂ =0.35; P₃ =0.25.

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

Предположим, что процесс только что перешел в состояние E_i. Он останется в этом состоянии на следующем шаге с вероятностью p_ii и с вероятностью 1-p_ii уйдет из этого состояния. Если процесс действительно останется в этом состоянии, то вероятность того, что на следующем, втором, шаге он останется в данном состоянии, по-прежнему равна p_ii, а вероятность того, что процесс перейдет в другое состояние, останется равной 1-p_ii. И так далее. Более того, благодаря марковскому свойству тот факт, что процесс пребывал в данном состоянии известное число шагов, никак не сказывается на вероятности остаться на следующем шаге в этом же состоянии или перейти в некоторое другое состояние. Так как эти события независимы, то вероятность того, что процесс находился в состоянии E_i точно m шагов и затем сразу перешел в другое состояние, равна (1-p_ii) , что и задает геометрическое распределение.

4. Марковские процессы с непрерывным  временем.

 

Для марковских процессов  с непрерывным временем, когда  переходы из одного состояния в другое возможны в любой момент времени, вероятность перехода из состояния E_i в состояние E_j точно в момент времени t не может быть задана, поскольку такая вероятность равна нулю. Вместо этого можно определить вероятность соответствующего перехода на интервале времени (t, t+Dt), определяемая как

p_ij (t, t +Dt)=Pr {g (t+Dt)=E_j | g (t)=E_i}, i, j=0,n.

При этом , i, j=0,n.

В случае марковской цепи с непрерывным  временем для описания переходов используются не вероятности переходов, а интенсивности переходов. Интенсивность перехода из состояния E_i в состояние E_j в момент времени t, обозначаемая через q_ij(t), определяется следующим образом:

q_ij(t)= , i¹j;   (12)

q_ii(t)= .   (13)

Эти пределы имеют следующую  интерпретацию. Если в момент времени t процесс находится в состоянии E_i, то вероятность перехода в течение промежутка времени (t,t+Dt) в произвольное (отличное от E_i) состояние задается величиной -q_ii(t) Dt+o(Dt)¹. Таким образом, величину -q_ii(t) можно интерпретировать как интенсивность, с которой процесс уходит из состояния E_i. Аналогично, вероятность перехода процесса в течение времени (t, t+Dt) из состояния E_i в состояние E_j задается величиной +q_ij(t)Dt+o(Dt) и величину q_ij(t) можно интерпретировать как интенсивность, с которой процесс переходит из состояния E_i в состояние E_j, при условии, что E_i - текущее состояние процесса. Так как всегда (t,t+Dt)=1, то из равенств (12) и (13) следует, что

(t)=0, i=0,n.

Если вероятности переходов p_ij(t,t+Dt), а, значит, и интенсивности переходов q_ij(t), не зависят от времени t (p_ij(t,t+Dt)ºp_ij(Dt) и q_ij(t) ºq_ij), т.е. от того, в какой момент начинается промежуток Dt, то марковский процесс называется однородным, в противном случае - неоднородным.

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

Интенсивности переходов q_ij, i,j=0,n, можно задать в виде квадратной матрицы Q размерности (n+1)´(n+1):

называемая матрицей интенсивностей переходов. Элементы матрицы переходов Q удовлетворяют условию (14) (сумма элементов строки равна нулю), и такая матрица называется дифференциальной.

Рассмотрим теперь задачу определения вероятностей (2) марковского случайного процесса с непрерывным временем.

Вероятность того, что марковский процесс в момент времени t+Dt окажется в состоянии E_i, определяется как

P_i(t+Dt) = (t)p_ji(Dt), i=0,n.

Действительно, марковский процесс  в момент времени t+Dt окажется в состоянии E_i, если он в момент времени t находится в состоянии E_j (с вероятностью P_j(t)) и за промежуток времени Dt перейдет с вероятностью p_ji(Dt) из состояния E_j в состояние E_i. Суммируя произведения вероятностей этих двух независимых событий по всем возможным состояниям процесса в момент времени t, получим равенство (15).

Если вычесть P_i(t) от обоих сторон равенства (15), а затем разделить на Dt и определить соответствующие пределы при Dt®0, то получим:

, i=0,n

или в векторном виде:        (16)

Решая данную систему дифференциальных уравнений при заданном распределении P(0)={P₀(0), P₁(0), ..., P_n(0)} начальных вероятностей с учетом нормировочного условия (3), можно определить вероятности P_i(t), i=0,n, состояний марковского случайного процесса в любой момент времени.

В случае эргодичности марковского  случайного процесса существуют предельные (при t®¥) вероятности состояний P_i, i=0,n, и они не зависят от начальных условий и временного параметра. Тогда производные dP_i(t)/dt=0, i=0,n, и система дифференциальных уравнений (16) для стационарного режима превращается в систему линейных алгебраических уравнений:

, i=0,n

или в векторном виде         (17)

PQ=0.

Система (17) совместно с нормировочным условием дает единственное решение для стационарных вероятностей P_i, i=0,n.

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

Пример. Определим вероятности состояний равновесия марковского случайного процесса с четырьмя возможными состояниями E₀, E₁, E₂, E₃ и матрицей интенсивностей переходов

Граф переходов для этого процесса приведен на рис. 3. В диаграмму переходов не включены петли, ведущие из состояния E_i, i=0,3, обратно в это же состояние, так как, согласно (14), члены на главной диагонали матрицы Q не содержат никакой новой информации: они равны сумме элементов соответствующей строки, взятой со знаком минус.

    

 

Рис. 3. Граф переходов примера.

Система (17) вместе с нормировочным условием для этого примера имеет вид:

-lP₀+mP₁=0

lP₀-(l+m)P₁+mP₂=0

-(l+m)P₂+mP₃=0

lP₁+lP₂-mP₃=0

P₀+P₁+P₂+P₃=1

Первые четыре уравнения полученной системы являются линейно зависимыми, и любое из них можно исключить из системы, а остальные три уравнения и нормировочное условие определяют единственное решение для вероятностей состояний равновесия. Если l = 2 и m = 1, то P₀=1/19, P₁=2/19, P₂=4/19 и P₃=12/19.

Применение принципа равенства  потоков вероятностей к отдельным  состояниям дает такую же систему уравнений. Так, например, для состояния E₃  lP₁+lP₂=mP₃, что соответствует четвертому уравнению приведенной выше системы.

5. Процессы размножения и гибели.

 

Процессы размножения и гибели являются частным случаем марковских случайных процессов, которые тем  не менее находят весьма широкое  применение при исследовании дискретных систем со стохастическим характером функционирования. Процесс размножения и гибели представляет собой марковский случайный процесс, в котором переходы из состояния E_i допустимы только в соседние состояния E_i-1, E_i и E_i+1. Процесс размножения и гибели является адекватной моделью для описания изменений, происходящих в объеме биологических популяций. Следуя этой модели, говорят, что процесс находится в состоянии E_i, если объем популяции равен i членам. При это переход из состояния E_i в состояние E_i+1 соответствует рождению, а переход из E_i в E_i-1 - гибели, предполагая, что объем популяции может изменяться не более чем на единицу; это означает, что для процессов размножения и гибели не допускаются многократные одновременные рождения и/или гибели.

Дискретные процессы размножения  и гибели менее интересны, чем  непрерывные, поэтому в дальнейшем они подробно не рассматриваются и основное внимание уделяется непрерывным процессам. Однако следует отметить, что для дискретных процессов проходят почти параллельные выкладки. Переход процесса размножения и гибели из состояния E_i обратно в состояние E_i представляет непосредственный интерес только для дискретных цепей Маркова; в непрерывном случае интенсивность, с которой процесс возвращается в текущее состояние, равна бесконечности, и эта бесконечность была исключена согласно определению (13).

В случае процесса размножения и  гибели с дискретным временем вероятности переходов между состояниями

 

 

 

 

Здесь d_i - вероятность того, что на следующем шаге (в терминах биологической популяции) произойдет одна гибель, уменьшающая объем популяции до i-1 при условии, что на данном шаге объем популяции равен i. Аналогично, b_i - вероятность рождения на следующем шаге, приводящего к увеличению объема популяции до i+1; 1-d_i-b_i представляет собой вероятность того, что ни одно из этих событий не произойдет и на следующем шаге объем популяции не изменится. Допускаются только эти три возможности. Ясно, что d₀=0, так как гибель не может наступить, если некому погибать.

Однако в противовес интуиции допускается, что b₀>0, что соответствует возможности рождения, когда в популяции нет ни одного члена. Хотя это можно расценивать как спонтанное рождение или божественное творение, но в теории дискретных систем такая модель представляет собой вполне осмысленное допущение. А именно, модель такова: популяция представляет собой поток требований, находящихся в системе, гибель означает уход требования из системы, а рождение соответствует поступлению в систему нового требования. Ясно, что в такой модели вполне возможно поступление нового требования (рождение) в свободную систему. Матрица вероятностей переходов для общего процесса размножения и гибели имеет следующий вид:

Т=    

 

Если цепь Маркова является конечной, то последняя строка матрицы записывается в виде [0 0… 0d_n1-d_n]; это соответствует тому, что не  допускаются никакие размножения после того, как популяция достигает максимального объема n.

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

Далее будем  рассматривать только непрерывные  процессы размножения и гибели, в  которых переходы из состояния E_i возможны только в соседние состояния E_i-1 (гибель) и E_i+1 (рождение). Обозначим через l_i интенсивность размножения; она описывает скорость, с которой происходит размножение в популяции объема i. Аналогично, через m_i обозначим интенсивность гибели, задающую скорость с которой происходит гибель в популяции объема i. Заметим, что введенные интенсивности размножения и гибели не зависят от времени, а зависят только от состояния E_i, следовательно, получаем непрерывную однородную цепь Маркова типа размножения и гибели. Эти специальные обозначения введены потому, что они непосредственно приводят к обозначениям, принятым в теории дискретных систем. В зависимости от ранее введенных обозначений имеем: