Цепи Маркова (1121219), страница 34
Текст из файла (страница 34)
Рассмотрим ц.м.д.в. на множестве I = {0, 1, 2, . . .}с переходными вероятностями pi,i+1 = ai , pi,0 = 1 − ai , i > 0, где (ai) —последовательность таких неслучайных чисел, что 0 < a i < 1 для всех i.Пусть b0 = 1, bi = a0 a1 . . . ai−1 , i > 1. Покажите, что цепьа) возвратна тогда и только тогда, когда bi → 0 при i →P∞;bi < ∞; еслиб) положительно возвратна тогда и только тогда, когдаP 0 (T > n) = a0 a1 . . . an−1 = bnиP 0 (T < ∞) = lim P 0 (T 6 n) = 1 − lim P 0 (T > n) = 1b n < ∞.i > 1,.1 /4 1 /4 1 /20 1 /2 1 /23 /4 1 /4 0.С другой стороны, существуют целые классы обратимых цепей Маркова:а) все (2 × 2)-цепи;б) конечные цепи, у которых P T = P: в этом случае матрица P являетсядважды стохастической, равномерное распределение является инвариантным, более того, и P находятся в состоянии детального баланса;в) Случайные блуждания на (конечных) неориентированных графах, длякоторыхiэто условие выполняется, найдите инвариантное распределение.Решение.
Так как цепь неприводима, можно рассмотреть фиксированное состояние, скажем 0. Пусть T — первый момент попадания в 0:T = inf{n > 1 : Xn = 0}. Рассмотрим P 0 (T < ∞). Мы имеем −1PЗадача 1.16.25. Приведите примеры обратимых цепей Маркова.Решение. Не каждая цепь обратима: пример — матрица P конечногоразмера не меньше трех, дважды стохастическая (т. е. суммы по всемстолбцам и строкам равны 1), и — равномерное распределение, но P 6=6= PT .
Например,!P=7E C (время, проведенное справа от C до возвращения в C) = ,2bn ,n=0i> 0Рисунок симметричен, поэтомуn→∞P 0 (T > n) =и цепь положительно возвратна тогда и только тогда, когдаУравнения инвариантности таковы:nE C (время, проведенное вне C до возвращения в C) = 7.n→∞Xn>02= 1.7Или, среднее время возвращения mC в состояние C в неприводимойположительно возвратной цепи равно 1/ C = 8 (теорема 1.7.8).
Тогда205тогда и только тогда, когда bn → 0. Таким образом, состояние 0 возвратнотогда и только тогда, когда bn → 0. Далее,Поскольку граф связный, цепь неприводима, и, так как она содержитциклы длиной 2 и 3 (взаимно простые), она апериодична. Тогда при n → ∞переходная вероятность за n шагов pij(n) сходится к j , и вероятностьP (Xn = j) также сходится к j для любых состояний i, j и начальногораспределения . Таким образом, P (Xn = L1) → 3/32.Далее, данная цепь положительно возвратна. Искомое среднее равноCR1 = R1 / C = 3/4.
Это следует из теоремы 1.7.7, утверждающей, что длянеприводимой положительно возвратной цепи Маркова со стационарным распределением справедливы равенства kj = j / k .Последняя часть задачи содержит ссылку на модель с непрерывнымвременем. Но поскольку среднее значение всех интервалов времени, когдагорит лампочка, равно 2/7, мы сразу получаем ответ§ 1.16. Вопросы по теории цепей Маркова с дискретным временемpij =и11(i и j сообщаются)vij= vj.Xvi ,iгде vi — кратность вершины i (число инцидентных ребер);г) процессы рождения и гибели с вероятностями перехода p ii+1 = pi ,pii−1 = qi = 1 − pi и суммойB=1+p0p pp p p+ 0 1 + 0 1 2 + .
. . < ∞;q1q1 q2q1 q2 q3206Глава 1. Цепи Маркова с дискретным временемздесь0= B −1 ,i=B−1 p 0pi...,q1qi+1i > 1,находится в состоянии детального баланса с матрицей перехода.Задача 1.16.26. Частица совершает случайное блуждание на множестве {0, 1, 2, . . .}. Если в момент времени n частица находится в состоянииm > 1, то в момент времени n + 1 она перемещается на один шаг влевос вероятностью p, на один шаг вправо с вероятностью r или остается напрежнем месте с вероятностью q = 1 − p − r. Если частица находитсяв состоянии 0, то она совершает шаг вправо с вероятностью r или остается в состоянии 0.
Покажите, что при p > r такая цепь положительновозвратна и найдите для этого случая инвариантное распределение. Определите, для каких p, q, r цепь имеет нулевую возвратность или являетсяневозвратной.Решение. Мы хотим показать, что цепь невозвратна, когда 0 < p < r,имеет нулевую возвратность, когда p = r > 0, и положительно возвратна,когда p > r > 0 (цепь, очевидно, положительно возвратна, когда r = 0,и невозвратна, когда p = 0, r > 0 ). В случае положительной возвратностиуравнения детального балансаиir =h0 = 1,(p + r)hi = rhi+1 + phi−1 , i > 1,минимальное неотрицательное решение которых имеет вид p i, i > 0, при p < r,hi =rиНоhi ≡ 1,i > 0,при p = r > 0.P 0 (T0 < ∞) = (1 − r) P 0 (T0 < ∞) + rh1 ,что и дает искомый ответ.т.
e. P 0 (T0 < ∞) = h1 ,= CkNk 1 N2, k = 0, 1, 2, . . . , N.N−ii, pi,i−1 = . Это цепь Маркова,Решение. Находим pi,i+1 =NNпоскольку выбор блохи, которая совершает скачок, не зависит от предыдущих событий. Уравнения детального баланса i pi,i+1 = i+1 pi+1,i имеютрешение=i+1N−ii+1N=i,откуда следует, что1 × 2 × · · · × (N − 1) × NN × (N − 1) × · · · × 2 × 10=N!N!0=0.Следовательно, для некоторого 0 < M < N имеемpЧтобы определить нулевую возвратность и невозвратность, рассмотримвероятности попадания hi = P (попасть в 0|X0 = i). Получим уравнения207Задача 1.16.27.
Жили-были две собаки, одна белая, другая черная.Неразлучные друзья, делили они и кров, и пищу. И все бы хорошо, даодна беда — от блох не могли избавиться. Блохи, общей численности N,тоже были у них общими — перепрыгивали с одной собаки на другую...В каждый момент времени ровно одна блоха перепрыгивает с одной собакина другую, блоха выбирается случайным образом и с равной вероятностьюиз N возможных, каждый такой выбор не зависит от всех предыдущих.Пусть Xn — это число блох на черной собаке в момент времени n.Покажите, что последовательность X = {Xn : n > 0} образует ц.м.д.в.
ивыпишите ее вероятности перехода. Покажите, что инвариантное распределение задается какi+1 pопределяют инвариантную меру i = (r/p) i , которую можно нормироватьтогда и только тогда, когда r < p; при этом r i r1−.i =p§ 1.16. Вопросы по теории цепей Маркова с дискретным временемM=N − (M − 1)MИз условияPiiM− 1=0=hPii(N − (M − 1)) × (N − (M − 2)) × · · · × NM × (M − 1) × · · · × (M − 1)N!=(N − M)!M!iCiN = 1 следует, что00=0= CMN 0.= 2 −N , и= 2−N CiN , i = 0, 1, . . . , N.Таким образом, инвариантное распределение является биномиальным:Bin(N, 1/2).A Delicate Detailed BalanceДеликатный детальный баланс(Из серии «Фильмы, которые не вышли на большой экран».)208Глава 1.
Цепи Маркова с дискретным временемЗадача 1.16.28. Конечный связный граф G состоит из множества вершин V, множества ребер E и не содержит петель или кратных ребер.Частица совершает случайное блуждание на V, двигаясь на каждом шагек случайно выбранной соседней вершине, причем каждая такая вершинавыбрана с одинаковой вероятностью, независимо от предыдущих шагов.Покажите, что единственное инвариантное распределение равно v == dv / (2|E|), где dv — кратность вершины v.Ладья совершает случайное блуждание по шахматной доске 15 ; в каждый момент времени она с одинаковой вероятностью может делать любые(дозволенные для ладьи) шаги. Каково среднее время возвращения ладьив угол доски?Решение.
Так как граф G связный, цепь конечна и неприводима, т. е.положительно возвратна. Следовательно, существует единственное инвариантное (стационарное) распределение. Распределение v = dv / (2|E|)удовлетворяет уравнениям детального баланса, так как d v dv,v0 /dv == dv0 dv0 v /dv0 ∀ v, v0 ∈ V. Значит, оно инвариантно, и данная цепьобратима. Таким образом, v есть единственное инвариантное распределение.В положительно возвратной цепи с инвариантным распределением ,1/ k определяет mk , т. е.
среднее время возвращения в k (см. теорему ??).Если ладья находится в углу доски или на любом из 64 квадратов, то d v == 2 × 7 = 14, v ∈ V. Следовательно, |E| = 64 × 14/2,угловое=141= ,64 · 1464mугловое = 64.Глава 2Цепи Маркова с непрерывнымвременем§ 2.1. Матрицы перехода и Q-матрицыСпециалисты по марковским процессам любятделать это, используя цепи(Из серии «Как они делают это».)Определение 2.1.1.
Назовем Q-матрицей на конечном или счетном пространстве состояний I матрицу с действительными элементами(qij , i, j ∈ I), обладающую следующими свойствами:— диагональные элементы неположительны, qii 6 0, i ∈ I;q ij > 0,— внедиагональные элементы неотрицательны,Pi 6= j, i, j ∈ I;Pqij , т. е. qij = 0 ∀ i ∈ I.— имеет место условие баланса: −qii =j∈I : j6=ijqij — это скорость перехода из состояния i в j.Для i 6= j значениеPqij обозначим qi (далее будет видно, что это суммарнаяВеличину −qii =j:j6=iскорость перехода из состояния i).
Будем обозначать Q-матрицу простоQ (общеупотребительное сокращение). Как и в гл. 1, I будет обозначатьединичную матрицу.Записывая в общейвременемP теории марковских цепей с непрерывнымPусловие балансаqij = −qii , предполагаем, чтоqij < ∞. Однакоj:j6=ij∈I:j6=iсущественную часть теории можно развить,если равенствоPP в условиибаланса ослаблено до верхней оценкиqij 6 0, т. е. qi >qij ∀ i ∈ I.j15 Шахматная доска состоит из 8 × 8 клеток. Допустимыми шагами являются шаги любойдлины, параллельные сторонам доски.j : j6=iТогда Q-матрица, удовлетворяющая условию баланса, называется консервативной; этот термин не будет встречаться в данном томе, так какнеконсервативные Q-матрицы рассматриваться не будут; см.
рис. 2.1 а).Как и ранее, Q-матрица порождает диаграмму, на которой стрелка i → jприсутствует тогда и только тогда, когда qij > 0.210Глава 2. Цепи Маркова с непрерывным временем§ 2.1. Матрицы перехода и Q-матрицы211а) etQ esQ = esQ etQ = e (t+s)Q , s, t ∈ R (в частности, e−tQ = (etQ) −1); этосвойство обобщает стандартное мультипликативное свойство экспоненциальной функции x 7→ exa : e (x+y)a = exa eya = eya exa ;б) функция etQ непрерывна (на самом деле и дифференцируема) поd tQe = QetQ = etQ Q, t ∈ R, т. е.dtt ∈ R, причем полагаем e0·Q = I; точнее,d tQ(e ) ij = (QetQ) ij = (etQ Q) ij .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
