Цепи Маркова (1121219), страница 21
Текст из файла (страница 21)
е. лежат в замкнутомединичном круге комплексной плоскости C.2. Если матрица P является апериодической, то все собственныезначения p 6= 0 таковы, что | p | < 1, т. е. лежат внутри открытого единичного круга в C. И наоборот, если все собственныезначения p 6= 0 таковы, что | p | < 1, то цепь является апериодической.Это утверждение является частным случаем так называемой теоремы Перрона—Фробениуса, которую можно сформулировать и доказатьдля матрицы с неотрицательными элементами общего вида.
Ср. с § 1.14.Нас особенно интересует свойство 2. Поэтому приведем его краткоедоказательство. Предположим, что матрица P является неприводимойи апериодической. Тогда, согласно теореме 1.9.2 вектор P n стремитсяк стационарному распределению для любого начального распределения, в частности и для = i , i = 1, . . .
, l, где i — это мера, сосредоточенная в точке i. Набор векторов i образует ортонормированный базисв пространствах l-мерных вектор-строк Rl и Cl :lPi=1|x i |21/211 Играслов: EVAT = the eigen-value added tax и EVAT = education via advanced technology.Следовательно, сходимость имеет место для любых l-мерных вектор-строкxT = (x1 , . . .
, xl), действительных или комплексных:— обычная евклидова норма век-тора, порожденная обычным скалярным произведением в R l или Cl .В примере 1.12.1 мы видели, что спектр матрицы перехода (1.12.1)лежит в отрезке [−1, 1] , между точками 0 = 1 и −1. Оказывается, этоявляется общим свойством матрицы вероятностей перехода. Точнее, собственные значения P могут быть и комплексными, но они должны лежать(1 на i-м месте, остальные элементы — нули).T nlim x P = limn→∞n→∞lXnxi i P =i=1lXi=1xi = hx, 1i .(1.12.24)Предположим теперь, что существует собственная вектор-строка T ,6=соответствующий такому собственному значению , что | | > 1 и6= 0 = 1.
ТогдаPn = n 6→ h , 1i ,== (0, . . . , 0, 1, 0 . . . , 0)Здесь ||x|| = (hx, xi)1/ 2||x||i||P|| = sup [||xT P|| : вектор-строка xT ∈ Rl , ||x|| = 1] =h ||xT P||i= sup: вектор-строка xT ∈ Rl , x 6= 0 .Отметим также, что если многочлен det( I − P) имеет попарно различные корни, то он имеет l линейно независимых собственных векторов.Начиная с этого момента будем предполагать, что матрица P неприводима; в противном случае существует инвариантное подпространстводля каждого сообщающегося класса и можно рассматривать действиематрицы P на каждом подпространстве.
Полезно также отметить, чтовектор-строка, представляющая собой индикатор каждого сообщающегосякласса (с компонентами 1 для элементов класса и 0 вне класса), будет инвариантной для PT . Норма матрицы ||P||, используемая ниже, определяетсяобычным образом:(Из серии «Кое-что из политики».)Мы будем делать то же, что и всегда: повышатьналог на добавленные собственные значения11 .We will do what we always do: raise EVAT,the eigen-value added tax.Глава 1. Цепи Маркова с дискретным временем128130Глава 1.
Цепи Маркова с дискретным временемΠ=(1.12.25)j=1.(j)утверждению 1, приведенному выше, спектральный радиус (P) матрицывероятностей перехода P равен единице и совпадает с нормой ||P|| (в общемслучае можно только утверждать, что ||M|| > (M)). Далее, спектральнаящель матрицы M определяется как минимальное значение (M) разности(M) − | |, где собственное значения таковы, что | | < (M):κ −jРис. 1.36k−1Xчто противоречит равенству (1.12.24). Следовательно, такого собственноговектора не существует, и для всех собственных значений 6= 0 должновыполняться неравенство | | < 1.Теперь, напротив, предположим, что все собственные значения 6= 0по модулю меньше 1, но матрица P является периодической, т.
е. имеетпериодические подклассы C1 , . . . , Ck с периодом k. Тогда при действииматрицы Pk при всех j = 1, . . . , k состояния из Cj не сообщаются с состояниями, не принадлежащими классу Cj . Таким образом, при действииматрицы перехода за k шагов Pk , каждый подкласс Cj содержит некоторый замкнутый сообщающийся класс Sj для матрицы Pk (а, возможно,совпадает с ним). Разумеется, при всех j = 1, . . .
, k матрица P k имеетстационарное распределение, т. е. инвариантный стохастический вектор,(1)сосредоточенный на Sj . Рассмотрим j = 1 и предположим, что (1) = ( i )является стационарным распределением для P k , сосредоточенным на S1 .(1)Т. е. (1) Pk = (1) и i = 0 ∀ i 6∈ C1 .Далее, вектор-строка (1) циклически перемещается под действием исходной матрицы P и ее степеней P 2 , . . . , Pk−1 : вектор (j) = (1) Pj−1сосредоточен на Cj , и опять является стационарным распределением дляPk , j = 1, .
. . , k − 1. Возьмем тогда корень k-й степени из единицы,обозначаемый κ ( κ k = 1, но κ 6= 1), и образуем вектор-строку§ 1.12. Геометрическая алгебра ц.м.д.в., I. Собственные значения и спектральные щели 131Поскольку+(1)κ −k+1 = κj=1(1)+κκj(j)= κΠ,j=2получаем собственный вектор матрицы P, соответствующий собственномузначению κ , где κ 6= 1, но |κ| = 1. (Эту же процедуру можно повторить длявсех нетривиальных корней k-й степени из единицы.) Но это противоречитсделанному выше предположению о том, что все собственные значенияматрицы P, отличные от 0 = 1, по модулю меньше 1. Этим завершаетсядоказательство свойства 2.Минимальный круг на комплексной плоскости C с центром в началекоординат и содержащий все собственные значения матрицы, называетсяспектральным кругом, а его радиус называют спектральным радиусом.Иными словами, спектральный радиус (M) матрицы M равен максимальному модулю собственных значений матрицы M.
Таким образом, согласно(j+1)— такое собственное значение, что | | < (M)] .(1.12.26)В соответствии с вышеприведенным утверждением 2 значение спектрального радиуса неприводимой апериодической матрицы перехода P достигается на единственном собственном значении 0 = 1, которое имеетгеометрическую кратность 1: мы исключили возможность собственногозначения 6= 1, модуль которого равен 1.Для неприводимой апериодической матрицы P спектральная щель даетскорость сходимости вектор-строки Pn к инвариантному распределениюи скорость сходимости вектор-столбца Pn x к вектору hx, T i1T . ЗдесьlPкоэффициент hx, T i =i xi играет ту же роль, что и hx, 1i в соотноше(M) = min [1 − | | :κjk−1XΠP =k−2Xi=1нии (1.12.24).
Это становится особенно очевидным, когда матрица P имеетl линейно независимых собственных вектор-строк T0 = , T1 , . . . , Tl−1 .Тогда каждая l-мерная вектор-строка xT (действительная или комплекс-132Глава 1. Цепи Маркова с дискретным временемlP−1ная) записывается в виде линейной комбинацииupupn Tp p= u0 +p=0l−1XupxT P n =l−1Xp=0Tp.Следовательно,§ 1.12. Геометрическая алгебра ц.м.д.в., I.
Собственные значения и спектральные щели 133l-мерных векторов (действительных или комплексных). ТогдаhPT x, yi = h (xT P) T , yi =n Tp p,(1.12.27)p=1=lXlXxi pji yjj=i,j=1xi pij yji(в силу обратимости) =i,j=1X l−1upp=1и норма остающейся в правой части соотношения (1.12.27) суммы равнаn Tp p6 (1 − ) nl−1Xp=1|up | ||p ||= O((1 − (P)) n).(1.12.28)p=0vp np ϕp ,p=1X l−1vpp=1= v0 1 +l−1XP x=vp np ϕpxiiXjpij yj = hx, (yT P) T i = hx, PT yi .np ϕp 6 O((1 − ) n),= (PT) = (P).С этой точки зрения, удобный класс образуют обратимые стохастические матрицы.
Дело в том, что если неприводимая матрица переходаP обратима относительно своего стационарного распределения , то еедействие (правостороннее или левостороннее) является эрмитовым относительно «взвешенного» скалярного произведения h · , · i :иhx, yi =lXx i yi i .(1.12.29)i=1Более того, транспонированная матрица P T обладает тем же свойством:ее действие (правостороннее или левостороннее) является эрмитовым от x1y1xlylносительно h · , · i . Действительно, пусть x = ...
, y = ... — пара(1.12.30)Аналогично можно показать, чтоhPx, yi = h (xT PT) T , yi = hx, (yT PT) T i = hx, Pyi .p=0l−1XXiАналогично если PT имеет l линейно независимых собственных векторlP−1vp ϕp , находимстрок ϕT0 = 1T , ϕT1 , . . .
, ϕTl−1 , то, представив x в виде x =n=(1.12.31)Но это означает, что для правостороннего и левостороннего действийматрицы P сопряженная матрица P ∗ относительно h · , · i совпадает с P,т. е. P является эрмитовой (самосопряженной) относительно h · , · i . Этовыполнено также и для PT , что и утверждалось.Взвешенное скалярное произведение является невырожденным (в томсмысле, что hx, xi = 0 тогда и только тогда, когда x = 0, посколькувсе компоненты i положительны). Здесь применима стандартная теоремао том, что каждая эрмитова матрица имеет ортонормированный базис изсобственных векторов и ее спектр — действительный (т.
е. все собственныезначения действительны). В нашем случае это влечет за собой возможность выбрать собственные векторы 0 , 1 , . . . , l−1 действительными(так как 0 ∝ T , вектор 0 можно сделать положительным). И хотяортогональность подразумевается относительно скалярного произведенияh · , · i и будет потеряна, если вернуться к стандартному скалярномуlPпроизведению hx, yi =xi yi , но линейная независимость сохранится,i=1и соотношения (1.12.27) и (1.12.28) остаются справедливыми (при u p == hx, p i ).Подведем итог.Теорема 1.12.4.
Пусть P — неприводимая стохастическая(l × l)-матрица, обратимая относительно своего стационарногораспределения . Тогда обе матрицы P и PT являются эрмитовымиотносительно скалярного произведения h · , · i . Таким образом,каждая из них имеет l действительных собственных значений, и ихспектры совпадают. Кроме того, собственные значения матрицP и PT , если считать их, учитывая их кратность, совпадают.Глава 1. Цепи Маркова с дискретным временем012pв порядке убывания, получим> ...
>>=1>Упорядочив собственные значения134l−1> −1.(1.12.32)1−|1,l−1 |] .(1.12.33)В этом случае из соотношений (1.12.27), (1.12.28) следует, чтоPn =+ O((1 − ) n),(1.12.34)pij = pji = vij /vi .+ (−1) n (Λ (1) − Λ (2) ) Π + O((1 − ) n)P(2)=i, Λi.Pn =и Λ (1) =Pi∈C (1)(1.12.36)i∈C (2)Специалисты по марковским процессам открытоделают это в сообщающихся классах= vi.Xvj .(1.13.2)j∈Gзадает стационарные вероятности (иными словами, вектор T являетсясобственным вектором матрицы P в R|G| или C|G| , соответствующим собственному значению 0 = 1). Здесь |G| обозначает общее число вершинграфа.