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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

е. определяются вероятностями p 0,j , где j — точка,соседняя по отношению к началу координат 0 = (0, . . . , 0)). При d = 1решетка Zd — это просто множество целых чисел; случайное блужданиев этом случае определяется вероятностями p и q = 1 − p скачков вправои влево.Рис. 1.15Такие блуждания на интуитивном уровне можно представлять себе какобобщенную версию модели блужданий пьяницы (или процесса рожденияи гибели), см. также пример 1.2.3. Пространство состояний здесь — это I == Z (= Z1), а матрица вероятностей перехода является бесконечной и имеетотчетливо выраженную «диагональную» структуру.............. .

. . . . . .. . . q 0 p 0 . . . . . .P = . . . 0 q 0 p 0 . . . ,. . . . . . 0 q 0 p . . .....................(1.6.1).где элементы p и q расположены соответственно над и под главной диа-60Глава 1. Цепи Маркова с дискретным временемгональю, а остальные элементы матрицы — нули.Если d = 2, то Z2 — это квадратная решетка на плоскости; здесь мыбудем рассматривать симметричное случайное блуждание «по ближайшимсоседям», когда вероятности скачков в каждом из направлений одинаковыи равны 1/4.§ 1.6.

Возвратность и невозвратность: случайные блуждания на кубических решетках61ного d. При этом вероятность скачков равна 1/ (2d).Теорема 1.6.1. При d = 1 случайное блуждание «по ближайшимсоседям» на Z невозвратно, за исключением случая p = q = 1/2, прикотором случайное блуждание возвратно.Д о к а з а т е л ь с т в о. Очевидно, что рассматриваемая ц.м.д.в. неприводима, следовательно, достаточно проверить, является ли возвратнымP (n)состоянием начало координат 0. Оценимp00 . Заметим, чтоn(n)p00=(0,n нечетно,(2k)! k kp q ,k!k!(1.6.2)n = 2k четно,поскольку необходимо совершать одинаковое число шагов вправо и влево.Воспользовавшись формулой Стирлинга√n! ≈ 2 nn+1/2 e−n при n → ∞,находимМожно также представить и многомерные модели для любого задан-(1.6.3)14pq = p(1 − p) 6 , 0 6 p 6 1,причем единственная точка, при которой достигается равенство — p = q == 1/2.

Другими словами, := 4pq < 1 при p 6= 1/2 и = 1 при p = 1/2.X(n)p00(< ∞,= ∞,1(2k)Следовательно, учитывая, что p00 ≈ √nРис. 1.17Далее,Такие блуждания интуитивно ассоциируются с бесконечным двумернымобобщением модели блужданий пьяницы.Если d = 3, то Z3 — это трехмерная кубическая решетка; интуитивно ее можно представить себе как бесконечный (во всех направлениях)кристалл.

Тогда блуждание нашей частицы можно моделировать как перемещение одиночного электрона между тяжелыми ионами и атомами,расположенными в узлах решетки. Вероятность перемещения в один изшести соседних узлов равна 1/6.(2k) 2k+1/2 k k1p q = √ 22k (pq) k .k2 k2k+1(2k)p00 ≈ √Рис. 1.16kk, получаемp 6= 1/2,p = 1/2.(1.6.4)Теорема 1.6.2. Симметричное случайное блуждание «по ближайшим соседям» на Zd возвратно при d = 2 и невозвратно при d = 3(а также при d > 3).Д о к а з а т е л ь с т в о.

Пусть d = 2; опять рассмотрим некоторое фиксированное состояние, скажем 0 = (0, 0). Каждый замкнутый путь на Z 2должен состоять из одинакового числа скачков влево и вправо и одинакового числа скачков вверх и вниз, см. рис. 1.18.(n)Тогда вновь p00 = 0, если n нечетно.Полезной оказывается идея спроектировать случайное блуждание наортогональные оси, повернув эти оси на угол /4.62Глава 1. Цепи Маркова с дискретным временем§ 1.6. Возвратность и невозвратность: случайные блуждания на кубических решетках63для каждого из этих двух блужданий. Следовательно, при n = 2k выполняется соотношениеТаким образом,Pkk!k! 22kМежду движениями, рассматриваемыми в старых и новых координатах,существует взаимно однозначное соответствие:1.k(1.6.5)p00 = ∞, и случайное блуждание возвратно.(n)(2k)p00 =Xi,j,l>0:i+j+l=k(2k)!(i!) 2 (j!) 2 (l!) 2 1 2k6= k! 2 1 2k(2k)! X62(k!)i!j!l!6↔ новые координаты: цепь (Xn0 )121перемещение на вектор ± (0; 1) ↔ перемещение на вектор ± √ (−1; 1).2перемещение на вектор ± (1; 0) ↔ перемещение на вектор ± √ (1; 1)Это означает, что в новых координатах цепь (Xn0 ) образована паройнезависимых симметричных случайных блужданий «по ближайшим соседям» на Z (в горизонтальном и вертикальном направлениях).

Возвращениев состояние 0 = (0, 0) означает одновременное возвращение в состояние 0 1 1 X k! 1(2k)!k!max.2(k!)i!j!l! 3k 22ki!j!l! 3ki,j,l>0:i+j+l=kДалее,Xi,j,l>0:i+j+l=kk!= 3k ,i!j!l!(1.6.6)поскольку эта сумма представляет собой число способов разместить kшаров в трех ящиках. При k = 3m можно также записать(3m)!(3m)!>,m!m!m!i!j!l!Рис. 1.20i,j,l>0:i+j+l=k61В новых координатах, с точностью до множителя √ , скачки происходят2вдоль диагоналей единичного квадрата.Рис. 1.19≈При d = 3 по-прежнему имеет место равенство p00 = 0, когда n нечетно. Если n четно, траектория возвращается в 0 = (0, 0, 0) тогда и толькотогда, когда совершено равное количество скачков для каждой пары противоположных направлений (вверх/вниз, восток/запад, север/юг).

Такимобразом,Рис. 1.18старые координаты: цепь (Xn)(2k) (2k)! 1 2(2k)p00 =если i + j + l = 3m.(1.6.7)Действительно, предположим, что i < m < l. Тогда, переходя от (m!) 3к i!j!l!, мы либо а) заменяем «хвосты» (i + 1) . . . m и (j + 1) . . . l в выражении для m! на произведение (m + 1) .

. . (m + 2m − i − j), которое равно(m + 1) . . . l при j < m, либо б) заменяем хвост (i + 1) . . . m произведением(m + 1) . . . j(m + 1) . . . (3m − i − j), которое равно (m + 1) . . . j(m + 1) . . . lпри j > m. В любом случае мы увеличиваем знаменатель, следовательно,уменьшаем дробь.Тогда при n = 2k = 6m имеем(6m)p006 6m (3m)! 1 3m(6m)! 1((3m)!) 2 2(m!) 33,(1.6.8)64Глава 1. Цепи Маркова с дискретным временемчто в силу формулы Стирлинга эквивалентно величине2Следовательно,(6m)p00>P(6m)p00m(6m−2)(1/6) 2 p00и(6m)Таким образом,X(1.6.9)m< ∞. Но при m > 1 выполняются неравенстваp00(6m−2)p00√ 1 3 12 √.3 /2(6m−4)> (1/6) 4 p00, т.

е.(6m)(6m−4)(6m)6 62 p00и p006 64 p00.(2k)p006kXm(6m)p00(1 + 62 + 64) < ∞,(1.6.10)гдеprojP (Xn+1 = i ± e Xnproj = i) =1e = (1; 0; 0),1/ (2d)1= ,1 − (d − 3) /d62e = (0; 1; 0),и блуждание невозвратно.Подобный подход можно использовать и при рассмотрении решетокболее высоких размерностей.

Однако существует другой способ установитьневозвратность для всех размерностей d > 3. А именно, спроектируемслучайное блуждание (Xnd) на решетке Zd на трехмерную решетку, игнорируя все координаты, кроме первых трех. Спроектированная цепь (X nproj) наZ3 остается неподвижной с вероятностью (d − 3) /d, когда исходная цепьсовершает скачки в тех направлениях, которые мы игнорируем, а когдановая цепь совершает скачки, она ведет себя как симметричное трехмерноеблуждание «по ближайшим соседям»:= 1, 2, 3,(1.6.11)§ 1.6.

Возвратность и невозвратность: случайные блуждания на кубических решеткахдолжно быть возвратным; см. теорему 1.6.3. Однако эта последняя цепьневозвратна. Следовательно, невозвратна и цепь (X nd).Симметричные случайные блуждания «по ближайшим соседям» частоназывают простыми блужданиями. Перефразировав известное высказывание, можно утверждать, что в двумерном случае все дороги простогослучайного блуждания приведут вас к начальному состоянию (или к любойдругой заданной точке), тогда как в трехмерном случае (и в случае болеевысоких размерностей) это уже неверно.

Различие между размерностью 2и размерностью 3 возникает в огромном числе самых различных ситуацийфактически во всех областях математики.Завершая этот параграф, проанализируем связь между произвольнойц.м.д.в. (Xn) и цепью (Yn), полученной из цепи (Xn) путем фиксации лишьизменения состояний. Предположим, что P = (pij) — это матрица переходаeij) матрицы перехода для цепи (Yn) имеют видцепи (Xn). Тогда элементы (p(0,i = j,eij =pij(1.6.12)p, i 6= j.1 − piiЦепь (Yn) часто называют цепью скачков цепи (Xn).Теорема 1.6.3.

Если цепь (Yn) невозвратна, то таковой являетсяи исходная цепь (Xn).Д о к а з а т е л ь с т в о. Если цепь (Yn) невозвратна, то для любого состояния i выполняется равенствоefi = P i ((Yn) возвращается в i) < 1.Далее, для (Xn) имеемfi := P i ((Xn) возвращается в i) = pii +3e = (0; 0; 1).См. рис. 1.21.Очевидно, что если первоначальное d-мерное блуждание возвращаетсяв состояние 0 = (0, .

. . 0), то блуждание-проекция возвращается в состояние (0, 0, 0). Следовательно, если исходноеd-мерное блуждание (Xnd) возвратно, то и цепьprojprojпроекция (Xn ) возвратна. Но тогда если в (Xn )проигнорировать все моменты, когда цепь не меняет состояния, а учитывать лишь скачки, тополученное симметричное случайное блуждание(3)Рис. 1.21«по ближайшим соседям» (Xn ) на Z3 также65= pii + (1 − pii)Xj6=iXpij P j ((Xn) достигает i) =j6=ipijP ((Xn) достигает i) 61 − pii j6 pii + (1 − pii)Xj6=ieij P j ((Yn) достигает i),pпоскольку если (Xn) достигает i из j, то это же справедливо и для (Yn).Последнее выражение не превосходитpii + (1 − pii)efi < 1.Следовательно, fi < 1, и цепь (Xn) невозвратна.66Глава 1. Цепи Маркова с дискретным временемМы вернемся к этому утверждению в дальнейшем и приведем альтернативное доказательство.Пример 1.6.4.

а) Пусть (Xn , Yn) — простое симметричное случайноеблуждание в Z2 , стартующее из (0, 0); положимT = inf{n > 0 : max {|Xn |, |Yn |} = 2}.Определите значения ET и P (XT = 2 и YT = 0).б) Пусть (Xn) n>0 — ц.м.д.в. с пространством состояний I и матрицейперехода P. Что подразумевают, когда говорят, что состояние i ∈ I возвратно? Докажите, что состояние i возвратно тогда и только тогда, когда∞Ppii(n) = ∞, где pii(n) обозначает элемент матрицы P n с индексом (i, i).n=0Покажите, что простое симметричное случайное блуждание в Z 2 возвратно.Решение.

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

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