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

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

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

Текст из файла (страница 11)

а) См. рис. 1.22. Если ki = E i T и hi = P i (XT YT = 0),то с учетом первого шага в силу марковского свойства и симметрии мыполучаемk (0,0) = 1 + k (−1,0) ,h (0,0) = h (−1,0) ,k (0,0)k (−1,−1)+,42h (0,0)h (−1,−1)1= ++,442k (−1,0) = 1 +h (−1,0)k (−1,1) = 1 +h (−1,−1)k (−1,0),2h (−1,0)=.2§ 1.6. Возвратность и невозвратность: случайные блуждания на кубических решеткахТогдаE i (Vi) =∞XP (Vi > k) =k>1С другой стороны,E i Vi = E i∞X∞Xfik .k=01(Xn = i) =n=0∞X(n)pii .n=0Следовательно, fi = 1 тогда и только тогда, когда∞Pn=0(n)pii = ∞.Пусть теперь (Xn) — это простое симметричное случайное блуждание в Z2 .

Оно неприводимо, следовательно, достаточно проверить, что∞P(n)pii = ∞ для одного состояния i ∈ Z2 , скажем начала координат (0, 0).n=0Обозначим символом (Xn±) проекцию (Xn) на диагональ {x = ±y} в Z2 .Тогда (Xn±) — это независимые простые симметричные случайные блуж12дания на √ Z, и возвращение в (0, 0) цепи (Xn) означает одновременноевозвращение в 0 для каждой из цепей (Xn±).

Далее,±P 0 (X2k= 0) = Ck2kи1,22k(2k)+−p00= P 0 (X2k= 0) P 0 (X2k= 0).(2k)Формула Стирлинга задает для p00 приближение √2 (2k) 2k 1 21≈ √= , при k → ∞.2k2k2 k k92ET = k (0,0) = ,Следовательно,12h (0,0) = .В силу симметрии,∞Xn=01418P (XT = 2 и YT = 0) = h (0,0) = .б) Состояние i возвратно, если fi = P (Ti < ∞) = 1, где Ti = inf{n > 1 :Xn = i}. Если Vi — это суммарное (общее) время, проведенное в состоянии i, то P i (Vi > k + 1) равноP i (Vi > k) P i (Vi > k + 1|Vk > k) = P i (Vi > k)fi = . . .

= fik+1 .2(n)p00=Рис. 1.22Следовательно,67∞Xk=0k(2k)p00= ∞.Pi(n)i pij= ( Pn) j , вектор= ( i) являетсяинвариантным вектором матрицы P (т. е. собственным вектором, соответствующим собственному значению 1): P = .Обозначим стационарное распределение= ( i) и будем подразумевать выполнение равенства P = без дополнительных напоминаний.Конечно, вектор удовлетворяет еще двум дополнительным условиям: а)он лежит в Pнеотрицательном ортанте ( i > 0 ∀ i ∈ I) и б) он лежит в гиперплоскостиi = 1. Если условие б) не выполняется, будем использоватьiб) если =антным.1 0+,=> 0, то матрица имеет единственное инвариантное+Тогда: а) еслираспределение1−обозначение вместо и назовем инвариантной мерой: = ( i), P = ,i > 0 для любого состояния i.Следует различать два уравнения: P = (уравнение инвариантности)и Ph = h (уравнение времени достижения).Пример 1.7.2. Рассмотрим (2 × 2)-матрицу перехода1−.P=+,= 0, то P = 0 1 и любой вектор (x, y) является инвари-= n(b − (N − n)).Cin Cb(N−i),CNa+bi = 0, 1, .

. . , N.Инвариантное распределение может оказаться не единственным, еслицепь имеет более чем один замкнутый сообщающийся класс. Она можетиметь стационарные распределения, заданные на разных замкнутых классах; см. рис. 1.8.Стационарное распределение не может быть задано на открытом сообщающемся классе, поскольку i всегда равно нулю для состояний i,принадлежащих открытым классам.Неединственность инвариантного распределения возникает тольков случае, когда число замкнутых сообщающихся классов превышает 1,так как неприводимая матрица имеет не более одного стационарногораспределения (т. е.

либо одно, либо ни одного). Конечная неприводимаяматрица P всегда имеет единственное стационарное распределение.Если матрица P является (счетной) неприводимой и невозвратной, тодля нее не существует инвариантного распределения.Если матрица P неприводима и возвратна, то возможны два случая:1. Матрица P имеет (единственное) стационарное распределение . Тогда все вероятности i положительны. В этом случае говорят, что матрицаP положительно возвратна (имеет положительную возвратность).2.

Для P не существует стационарного распределения. В этом случаеговорят, что P имеет нулевую возвратность.Более точно, каждая неприводимая возвратная матрица P имеет инвариантную меру , для которой P = и все компоненты i положительны.Однако сумма компонент может быть как конечной, так и бесконечной,и в определении 1.7.6 мы будем разделять эти случаи:XiXiПоскольку P (Xn = j) =(1.7.1)∀ j ∈ I.n= P (X0 = j) = P (X1 = j) = .

. . = P (Xn = j) = . . .=jiПусть (Xn) — это ц.м.д.в. с матрицей вероятностей перехода P.Определение 1.7.1. Начальное распределение вероятностей называется инвариантным (или стационарным), если оно сохраняется во времени.Это означает, что= (N − n) (a − n),Проверьте, что инвариантное распределение является гипергеометрическим.i< ∞ : P имеет положительную возвратность,i= ∞ : P имеет нулевую возвратность.Марк Аврелий Антоний (121–180), римский императорnВремя — это река событий, и сильно ее течение;чуть что-то показалось на горизонте, оно уже унесено течением,и ему на место приходит что-то другое, которое тоже пройдет.69Пример 1.7.3.

Пусть a, b > N, a, b, N ∈ Z. Рассмотрим м.ц.д.в.с состояниями n = 0, 1, . . . , N и переходами в соседние состояния (т. е.рождением и гибелью) с вероятностями pn и qn = 1 − pn переходов в n + 1и n−1 из n, заданными соотношениями pn = n / ( n + n), qn = n / ( n + n),где§ 1.7. Инвариантные распределения:определения и основные факты. Положительнаяи нулевая возвратность. I§ 1.7. Инвариантные распределения. Положительная и нулевая возвратность. IГлава 1.

Цепи Маркова с дискретным временем68инвариантным, т. е. k = k P, тогда и только тогда, когда состояние k возвратно.3. Если матрица P неприводима и возвратна, то710<ki< ∞ ∀ i, k ∈ I.Отметим одну из особенностей. Решения уравнения P = при сложении и умножении на постоянную вновь являются решениями: ( 1 + 2)P == 1 P +. 2 P и (c )P = c( P). Следовательно, можно выполнить нормиPPровку ij = i , чтобы получить равенствоj = 1 (при условии,jjPчтоj < ∞). Мы видим, что для неприводимой цепи все инвариантные§ 1.7.

Инвариантные распределения. Положительная и нулевая возвратность. IГлава 1. Цепи Маркова с дискретным временем70иP k (Tk > m − 1, Xm−1 = i)pik = P k (Tk = m, Xm−1 = i).1(Xn = i) =E k (ожидаемое число попаданий в i до возвращения в k),=если i 6= k (для 1 6 n < Tk),если i = k (начиная с n = 0).1,Тогда при j 6= k имеем(1.7.2)kjX= Ek1(Xn = j) =06n6Tk −1== 1 + E k (Tk − 1) = E k Tk .( P) k :=Xki pik61=kиXkk(субинвариантность).(1.7.6)X26n<∞ i : i6=kkk pkj+2. Соотношение ( k P) k = 1 выполняется тогда и только тогда,когда состояние k возвратно. Следовательно, вектор k являетсяXXE k 1(Tk > n, Xn = i)pij = ( k P) j .i : i6=k 16n<∞Далее, при i = k имеем( k P) k =Xki pik=kk pkki∈I= pkk ++XXi : i6=ki : i6=ki∈IP k (Tk > n − 1, Xn−1 = i, Xn = j),P k (Tk > n − 1, Xn−1 = i)pij ==i∈IXXа это выражение в силу соотношения (1.7.7) равно(1.7.4)Теорема 1.7.4.

1. Для любого состояния k выполняются соотношенияXkk( k P) j :=(инвариантность),(1.7.5)i pij = j , j 6= kP k (Xn = j, Tk > n) =26n<∞ i : i6=kpkj +E k (число посещений i до возвращения в k) =i∈I : i6=ki∈I= pkj +=1+X= ( ki , i ∈ I), зависящие отX16n<∞kiXkE k 1(Xn = j, Tk > n) =16n<∞Здесь, как и в соотношении (1.5.4), Tk есть время возвращения в состояние k:Tk = inf [n > 1 : Xn = k] .(1.7.3)Тогда 0 6 ki 6 ∞. Рассмотрим векторыпараметра k ∈ I.

Заметим, чтоX(1.7.8)n=0EkTXk −1= EkP k (Tk > m − 1, Xm−1 = i)pij = P k (Tk > m − 1, Xm−1 = i, Xm = j) (1.7.7)kiСледовательно, для неприводимой и возвратной матрицы P вектор k является «истинно» инвариантным вектором со строгоположительными и конечными компонентами.Д о к а з а т е л ь с т в о. 1. В силу марковского свойства для любогоm > 2 и состояний i 6= k и j 6= k выполняются соотношениямерыпропорциональны друг другу:= c . В частности, для всехинвариантных мер все i положительны для любого i ∈ I.Перейдем к доказательствам приведенных выше утверждений. Ключевым утверждением, которое позволяет доказать вышеперечисленныесвойства, является теорема 1.7.4. Положим0jki pikX=1(Xn = i) pik =16n<R (k)= pkk +XXi : i6=k 16n<∞E k 1(Tk > n, Xn = i)pik ,Глава 1.

Цепи Маркова с дискретным временема это выражение в силу (1.7.8) равноX XXP k (Tk = n + 1, Xn = i) = pkk +P k (Tk = n) =pkk +k (m)l plk>k (n)i pik ,т. е.6(n)i6=kpki pij + . . . +pki pij +Xi1 ,...in−1 6=k= pkj +i6=kXX=k,(1.7.9)i, k ∈ I.Заключаем теперь, что для неприводимой возвратной цепи возможныдва случая: а) все ненулевые инвариантные меры таковы, чтоX(1.7.10)i < ∞,i6=k l6=kpki1 . .

. pin−1 j += ... =Xl,i1 ,...,in−1 6=kи б) все ненулевые инвариантные меры таковы, чтоXi = ∞.ll pli piji∈I= 1 сле-(1.7.11)i∈Ii : i6=kXkД о к а з а т е л ь с т в о. 1) Из инвариантности и равенствадует, что для любых j ∈ I и n > 1 выполняется равенствоXXXXj =i pij = 1 · pkj +i pij = pkj +l pli pij =i(i)∀ i ∈ I;kiki2) для неприводимой и возвратной матрицы P выполнено равенствоki = i ∀ i ∈ I.i6=kОтсюда следует, что все ненулевые инвариантные меры связаны отношением пропорциональности 0 = c и все их компоненты конечны и строгоположительны. В частности, все векторы k пропорциональны:>i1)= pkj +.Теорема 1.7.5. Предположим, что = ( i) — инвариантная мера:P = и i > 0 ∀ i ∈ I. Дополнительно предположим, что k = 1 длянекоторого состояния k.

ТогдаX1piklkiX=kk1=С другой стороны,получаем, что e i = 0. Следовательно, e = 0 и = k .Мы видим, что для неприводимой возвратной цепи условие k = 1определяет все ее поведение. Более точно, если — ненулевая инвариантная мера, т. е. P = , i > 0 и k > 0 для некоторого состояния k,то= k k.llОтметим, что в вышеприведенных рассуждениях возвратность не использовалась.2. Из последнего соотношения следует, что ( k P) k = 1 тогда и толькотогда, когда fk = 1, т.

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

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

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

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