Теория случайных процессов (1042226), страница 6
Текст из файла (страница 6)
2. Дискретные цепи Маркова196528743Рис. 14i = 1, 2, 3. Блок Ti управляет переходами на множестве состояний i-го КЭ. Блок R управляет переходами из несущественных состояний в существенные, блок Q управляет переходамииз несущественных состояний в несущественные, блок 0 — нулевой.Лекция 6. Долгосрочный прогноз эволюции цепейс одним классом эквивалентностиЭволюция ДЦМ описывается МВП и ВВС за n шагов:P (n) = P n ,π (n) = π (0) P n ;следовательно, долгосрочный прогноз определяется матрицейlim P (n) и вектором lim π (n) .n→∞n→∞В связи с этим возникают вопросы:• при каких условиях эти пределы существуют,• если они существуют, то как их найти,• при каких условиях существуют стационарные режимы?Ответам на эти вопросы предпошлем несколько замечаний,определений и утверждений.Вектор π = (π1 , π2 , ...
, πN ) называется неподвижным дляматрицы P (P -неподвижным), если πP = π . Вектор π являетсяP -неподвижным тогда и только тогда, когда он является P n неподвижным ∀ n > 2: действительно,пусть πP = π , тогда πP 2 = πP = π ⇒ πP 3 = πP = π ⇒ ... ⇒⇒ πP n = πP = π ;пусть πP n = π , тогда πP n−1 = π ⇒ πP = π .Вектор вероятностей состояний π (n) = π (0) P n называетсястационарным, если он не зависит от n. Говорят, что(n)nпоследовательность матриц P = pijпри n → ∞ сильносходится к матрице Π = (πij ), а последовательность векторовЛекция 6. Прогноз эволюции цепей с одним классом эквивалентности 39(n) (n)(n)π (n) = π1 , π2 , ...
, πNсильно сходится к вектору π == (π1 , π2 , ... , πN ), если имеет место поэлементная сходимость(n)(n)pij → πij и πi → πi . Матрица Π и вектор π называютсяфинальной МВП и финальным ВВС соответственно.В основе анализа предельного поведения ДЦМ лежит такназываемаяЭргодическая теорема (теорема 1). Если P — МВП регулярного КЭ, тоπlim P n = Π = ... , π > 0.n→∞πДоказательство см., например, в [1]. Согласно этой теоремедля регулярного КЭ имеет место сильная сходимость P n → Π ,при этом строго стохастический вектор-строка π является одновременно P -неподвижным, финальным и стационарным ВВС.Действительно, при n → ∞π1 π2 ... πN π1 π2 ...
πN π (n) = π (0) P n → π (0) ... ... ... ... =π1 π2 ... πN=π1NXi=1(0)πi , π2NXi=1(0)πi , ..., πNNXi=1(0)πi!== (π1 , π2 , ... , πN ) ∀ π (0) ,т. е. финальный ВВС является единственным и совпадает сострокой финальной МВП. Далее, P n = P n−1 P → π = πP , т. е.π есть P -неподвижный вектор. Наконец, π (n) = hπ (0) = πi == πP n = π , т. е.
если начальный ВВС неподвижен, то вектор πстационарен при любом n; если же начальный ВВС произволен,то вектор π стационарен на ∞.Рассмотрим циклический КЭ, для него последовательность0 1nP не имеет предела при n → ∞: например, P =⇒1 01 00 1⇒ P2 =⇒ P3 =⇒ ... (рис. 15). В этом0 11 040Разд. 2. Дискретные цепи Марковаслучае от матрицы P можно перейти к регуляризованной поЭйлеру матрице1 0 0Pe = αI + (1 − α) P , 0 < α < 1, I = 0 1 0 ,0 0 1которая есть МВП регулярного КЭ (рис.
16), мало отличающаясяот исходной МВП P при малых значениях α. Покажем, что Pe —стохастическая матрица. Действительно,peij = (1 − α) · pij > 0 при i 6= j ,peij = (1 − α) pii + α · 1 > α > 0 при i = j.Более того, peii > 0; следовательно, регуляризованный циклический класс эквивалентности уже является регулярным иe > 0.lim Pe n = Πn→∞e и принимается в качестве финальной матрицы поМатрица Πследовательности P n .1−α112α1Рис. 15α1−αРис. 16Отметим еще одно замечательное свойство матриц P и Pe :вектор π является одновременно неподвижным стохастическимвектором обеих матриц P и Pe, т. е.NXπ = πP , π = π Pe, πi > 0,πi = 1.i=1Действительно, пусть π = π Pe , тогдаπ = π (αI + (1 − α) P ) = απ + (1 − α) πP ⇒⇒ (1 − α) πP = π − απ ⇒ (1 − α) πP = (1 − α) π ⇒ π = πP.В дальнейшем мы будем говорить о так называемой слабойсходимости циклических матриц P n к матрице Π , все строкикоторой совпадают с P -неподвижным вектором π , понимая подe.этим сильную сходимость Pen → ΠЛекция 6.
Прогноз эволюции цепей с одним классом эквивалентности 41Выше при изучении механизма переходов системы из одногосостояния в другое отмечалось, что при старте из любого несущественного состояния система рано или поздно перейдет в одноиз существенных состояний некоторого КЭ и при дальнейшейэволюции никогда не покинет этот класс. Если данное свойствоперевести на теоретико-вероятностный язык, то получим следующую теорему.Теорема 2 (общая теорема о предельном поведении конечной цепи Маркова). При старте из любого несущественного состояния вероятность оказаться в существенном послеn шагов стремится к 1 при n → ∞.Отсюда следует, что если все существенные состояния являются поглощающими, то при n → ∞ система будет поглощенаодним из них.Найдем вероятность bij поглощения системы j -м поглощающим состоянием при ее старте из i-го несущественного.
Уже напервом шаге она будет поглощена с вероятностью pij . Если этогоне произойдет, то система на первом шаге с вероятностью pikокажется в k -м несущественном состоянии и при дальнейшейэволюции с вероятностью bkj будет поглощена j -м поглощающим. По формуле полной вероятности получаемXbij = pij +pik bkj , j ∈ Sc , i, k ∈ Sн .(6.1)k∈SнЕсли вспомнить (см. лекцию 4), что МВП в каноническойформе имеет вид!T 0P =,R Qгде Q = (pij ), i, j ∈ Sн , R = (pij ), i ∈ Sн , j ∈ Sc , и обозначитьB = (bij ), i ∈ Sн , j ∈ Sc , то в матричной записи (6.1) примет видB = R + QB ⇒ B = (I − Q)−1 R,(6.2)(доказательство существования обратной матрицы см. в [1]).Итак, нами доказано следующее утверждение.Теорема 3.
Если все существенные состояния конечной цепи Маркова являются поглощающими, то матрица вероятностей поглощения системы при ее старте из несущественногосостояния равна B = (I − R)−1 R.42Разд. 2. Дискретные цепи МарковаПерейдем к анализу отдельных классов ДЦМ.Неприводимые цепиПусть P — МВП, а π (0) — ВНВ некоторой цепи. Согласноэргодической теореме сильно или слабоπP n → Π = ...
> 0,πтогда∀π (0)⇒π (n) = π (0) P n → π (0) Π = π > 0 при n → ∞,π (0) = π ⇒ π (n) = π ∀ n,т. е. ВВС на n-м шаге сходится к положительному вектору π ,являющемуся строкой финальной МВП, а также единственнымP -неподвижным и единственным стационарным вектором. Такимобразом, построение финальной МВП, финального ВВС, стационарного ВВС сводится к построению P -неподвижного вектораπ , т. е. к решению вырожденной системы уравнений π = πP вклассе стохастических векторов π (в том числе для циклическихцепей).В нижеследующих примерах требуется построить финальныйВВС π и финальную МВП Π .Пример 6.1.
Пусть ГС представленимеет вид0,5 00 0,25 0,5 0,25P = 00 0,50 0,5 0124Рис. 17на рис. 17, а МВП НРЦ0,50 .0,5 0,53Лекция 6. Прогноз эволюции цепей с одним классом эквивалентности 43Решение. Система уравнений для определения неподвижноговектора π имеет видπ1 = 0,5π1 + 0,25π2 , π = πP , π = 0,5π + 0,5π ,4224P⇒⇒πi = 1π3 = 0,25π2 + 0,5π3 ,i=11 = π1 + π2 + π3 + π4⇒ π = (1/6, 2/6, 1/6, 2/6) ;следовательно,1 /6 1 /6Π = 1 /61 /6Пример 6.2. Пусть ГСимеет вид0 0P = 0 1 /32 /32 /62 /62 /62 /61 /61 /61 /61 /62 /62 /6 .2 /6 2 /6представлен на рис. 18, а МВП НЦЦ00 1 /3 2 /30010 0001 .2 /3 000 0 1 /3 0031524Рис.
18Решение. Система уравнений для определения неподвижноговектора π имеет видπ 2 = 2 /3 π 4 ,π=πP, P π 3 = 1 /3 π 5 ,5⇒⇒π 4 = 1 /3 π 1 + π 2 ,πi = 1,i=1π 5 = 2 /3 π 1 + π 3 ,π = (π1 , ..., π5 )π1 + ... + π5 = 144Разд. 2. Дискретные цепи Маркова⇒ π = (1/4, 1/6, 1/12, 1/4, 1/4) ⇒1/4 1/6 1/12 1/4 1/6 1/12⇒ Π = 1/4 1/6 1/12 1/4 1/6 1/121/4 1/6 1/121 /41 /41 /41 /41 /41 /41 /41 /41 /41 /4.Моноэргодические цепиПо определению МЦ имеет несущественные состояния, а существенные образуют единственный КЭ, который может бытькак регулярным, так и циклическим. МВП в канонической формеимеет видi\j12...NcNc + 1Nc + 2...N12...NcNc + 1 Nc + 2...
NT0RQМатрица P разбита на четыре блока T , Q, 0, R размерностями соответственно (Nc × Nc ), (Nн × Nн ), (Nc × Nн ), (Nн × Nc ).По правилам возведения в степень блочных матриц имеем!n0TPn =,R(n) Qnгде R(n) в отличие от T n и Qn не есть n-я степень матрицы R.При n → ∞согласно эргодической теореме и ее следствиπcям T n → Πc = ... > 0, где πñ = (π1 , π2 , ... , πNc ); согласноπcтеореме 2 Qn → 0, а Rn сходится к (Nн × Nc )-матрице с одинаковыми строками, равными πñ , так как с вероятностью 1 системаЛекция 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
