Главная » Просмотр файлов » Цепи Маркова

Цепи Маркова (1121219), страница 21

Файл №1121219 Цепи Маркова (Лекции в различных форматах) 21 страницаЦепи Маркова (1121219) страница 212019-05-09СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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| обозначает общее число вершинграфа.

Характеристики

Тип файла
PDF-файл
Размер
4,15 Mb
Тип материала
Высшее учебное заведение

Список файлов лекций

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6549
Авторов
на СтудИзбе
300
Средний доход
с одного платного файла
Обучение Подробнее