Цепи Маркова (1121219), страница 15
Текст из файла (страница 15)
е. либо вновь на верхнюю позицию, либо подколоду, либо на одну из 50 позиций между другими картами. Как долгов среднем будет продолжаться этот процесс тасования до того момента,пока самая нижняя карта не окажется сверху?Пусть pn обозначает вероятность того, что после n итераций карты окажутся расположенными в возрастающем порядке. Покажите, что,независимо от начального порядка карт, pn имеет предел при n → ∞,и вычислить этот предел p. Сформулируйте точно все общие результаты,на которые вы будете ссылаться.Покажите, что, по крайней мере до того момента, пока нижняя картане достигнет верхней позиции, порядок карт, которые будут располагатьсяпод ней, является равномерно случайным.
С помощью этого факта илииными рассуждениями покажите, что для всех n выполняется неравенство|pn − p| 6 52(1 + log 52) /n.Решение. Занумеруем позиции, на которых могут находится карты,числами 1,2, . . . , 52, где 1 обозначает нижнюю позицию. Предположим, чтонижняя карта достигла позиции m. Тогда верхняя карта может находитьсягде-то ниже с вероятностью m/52. Среднее время наступления такогособытия удовлетворяет уравнениюmkm ,km = 1 + 1 −52откуда находим km = 52/m.
Тогда общее среднее время достижения верхней позиции равно11k1 + . . . + k51 = 52 1 + + . . . +.251Тасование карт представляет собой цепь Маркова на множестве перестановок S52 (группе перестановок). Эта цепь апериодическая, поскольку,сняв верхнюю карту, мы вновь можем положить ее на прежнее место. Эта§ 1.9. Сходимость к положению равновесия. Предельные пропорции93цепь является также неприводимой, поскольку можно прийти к состоянию, когда карты расположены в возрастающем порядке: нужно всякийраз, снимая верхнюю карту, класть ее на дно колоды, до тех пор покана дне не окажется карта 1, затем, снимая верхнюю карту, класть ее навторую позицию и т.
д. В силу симметрии равномерное распределение наS52 является инвариантным.Следовательно, в силу теоремы о том, что для неприводимой апериодической цепи Маркова (Xn) со стационарным распределением= ( i) выполняется соотношение lim P (Xn = j) = j ∀ j, получаемn→∞lim pn = p =n→∞1.(52)!Наконец, предположим, что в процессе тасования под нижнюю картуподложено k карт и эти карты упорядочены случайным образом, с равнымивероятностями для каждого возможного порядка.
Когда мы будем перекладывать следующую карту (под ту, что была первоначально нижней), то онаравновероятно может оказаться на одной из k + 1-й позиций, т. е. k + 1карта по прежнему будут упорядочены случайным образом. По индукцииэто рассуждение применимо до момента, когда k = 51.Предположим далее, что T — это время, когда нижняя карта достигнетвершины. Колода карт в момент времени T + 1 упорядочена случайнымобразом.
В силу строго марковского свойства она таковой останется и вмомент времени (T + 1) ∨ n = max [T + 1, n] . Следовательно,|pn − p| = | P (карты расположены в порядке возрастания в момент n) −− P (карты расположены в порядке возрастания в момент (T + 1) ∨ n) | 6 52152116 (1 + log 52).6 P (T > n) 6 ET =1 + + ... +nn251nТо, что я говорю, — это пасьянс.Перетасовка карт. (Дон Кихот)М. де Сервантес (1547–1616), испанский писательОставшаяся часть этого параграфа посвящена предельным пропорциям.
Это предмет так называемых эргодических теорем, в которыхизучаются временные средние вдоль траекторий случайных процессов(в нашем случае ц.м.д.в.). Одним из удивительных феноменов является то, что при предположении типа неприводимости предельные средниевремена совпадают со средними значениями относительно стационарных94Глава 1. Цепи Маркова с дискретным временемраспределений. Эти последние средние можно рассматривать как усреднение по пространству (т. e. усреднение по пространству состояний I).Таким образом, приведенный выше факт можно трактовать следующимобразом: «усреднение по времени на большом временно́м интервале совпадает с усреднением по пространству»; так формально можно пояснить«свойство перемешивания» для случайных процессов (на самом деле существует целая иерархия таких свойств).
Свойства перемешивания лежатв основе многих феноменов, наблюдаемых в природе, и во многих областяхчеловеческой деятельности. Исторически, эти свойства связаны с именамидвух знаменитых физиков XIX в. — американца Дж. В. Гиббса (1839–1903)и австрийца Л. Больцмана (1844–1906). Эргодические теоремы образуютфундамент эргодической теории, развитой области математики, котораявключает в себя широкий спектр концепций и методов.В предельной пропорции мы все будем мертвы.Дж. Майнард Кейнс (1883–1946), британский экономист§ 1.9. Сходимость к положению равновесия. Предельные пропорциигде(i,если состояние i положительно возвратно,если состояние i нулевой возвратности или невозвратно.(1.9.20)Д о к а з а т е л ь с т в о.
Предположим сначала, что состояние i невозвратно. Тогда, как мы знаем, суммарное число Vi посещений состояния iконечно с вероятностью 1; см. формулы (1.5.8), (1.5.18). Значит, V i /n → 0при n → ∞ с вероятностью 1. Так как 0 6 Vi (n) 6 Vi , мы получаем, чтоVi (n) /n → 0 при n → ∞ с вероятностью 1.Пусть теперь состояние i возвратно. Тогда моменты времени T i(1) ,(2)Ti , . . .
между последовательными возвращениями в состояние i конечныс P i -вероятностью 1. В силу теоремы 1.8.3 они являются н.о.р.с.в. сосредним mi = 1/ i в случае положительной возвратности и с бесконечнымисредними в случае нулевой возвратности. Очевидно,ri =0,(1)Приведем естественный пример.Пример 1.9.5. Рассмотрим число посещений цепью состояния i домомента времени n:n−1X1(Xk = i).(1.9.15)Vi (n) =k=0Если существует пределVi (n)lim,n→∞ n(1.9.16)то его называют предельной пропорцией времени, проведенного в состоянии i.Вообще, если f: I → R — это функция на пространстве состояний I, томожно рассматривать суммуV (f, n) =n−1Xf(Xk)(1.9.17)k=0и пределlimn→∞(1.9.18)Теорема 1.9.6.
Для любого состояния i выполняется равенствоPlimn→∞Vi (n)= rin(Vi (n))Ti + . . . + T iно(1)(Vi (n) −1)Ti + . . . + T i> n,6 n − 1,см. рис. 1.28. Таким образом, мы можем записать1n1(1)(V (n) −1)(1)(V (n))(T + . . . + Ti i)66(T + . . . + Ti i ).Vi (n) iVi (n)Vi (n) i= 1,(1.9.19)(1.9.21)n1 X (l)По теореме 1.8.4 с P i -вероятностью 1 существует предел limTi =n→∞ n= mil=1 Xn1(l)PiTi → mi при n → ∞ = 1.(1.9.22)nl=1Далее, так как состояние i возвратно, последовательность (V i (n)) бесконечно возрастает, и с P i -вероятностью 1 выполняется соотношениеP i (Vi (n) % ∞, при n → ∞) = 1.V (f, n).n95(1.9.23)Тогда мы можем в формуле (1.9.22) суммировать до Vi (n) вместо n и соответственно разделить на Vi (n):Vi (n)1 X (l)limTi = m i .n→∞ Vi (n)l=196Глава 1. Цепи Маркова с дискретным временем§ 1.9.
Сходимость к положению равновесия. Предельные пропорции97(1)(На самом деле распределение первой с.в. Ti = Ti = H1 другое и зависитот начального состояния.)Теорема 1.9.8. Пусть P — конечная неприводимая переходнаяматрица. Тогда для любого начального распределенияи любойограниченной на I функции f справедливо равенствоV (f, n)= (f) = 1,(1.9.25)P limnn→∞где(f) =X(1.9.26)i f(i).i∈IРис. 1.28n→∞Это соотношение выполняется и на пересечении двух ранее упомянутыхсобытий вероятности 1, которое, очевидно, имеет и P i -вероятность 1. Наэтом же событии выполняется равенствоVi (n) −1X (l)1Ti = m i .n→∞ Vi (n)l=1Иными словами, из формул (1.9.22) и (1.9.23) следует, чтоPi1Vi (n)Vi (n) −1Xl=1Ti(l)→ miVi (n)1 X (l)иTi → mi при n → ∞Vi (n)l=1(1.9.24)Но тогда в силу соотношения (1.9.21) все на том же пересечении этих двухсобытий P i -вероятности 1 отношение n/Vi (n) стремится к mi , т.
e. обратноеотношение Vi (n) /n стремится к ri = 1/mi . Отсюда следуют соотношения(1.9.19) и (1.9.20), что и завершает доказательство теоремы 1.9.6.Замечание 1.9.7. Аккуратный анализ доказательства теоремы 1.9.6показывает, что если матрица P неприводима и положительно возвратна, томожно утверждать, что в формуле (1.9.19) вероятностное распределение P iможет быть заменено на P j или на распределение P, задаваемое начальным(1)(n)распределением . Это возможно благодаря тому, что суммы T i + .
. . + Ti(l)все еще асимптотически ведут себя, как если бы с.в. T i были бы н.о.р..i∈Iобразовать и ограничить левую часть соотношения (1.9.27) следующимобразом: X X V (n)Vi (n) V (f, n) i− (f) = − i f(i) 6− i |f(i) |.nnni∈I= 1.nИными словами, мы хотим проверить, что с P-вероятностью 1 выполняетсяусловие V (f, n)− (f) → 0 при n → ∞.(1.9.27)nPPЗаписывая V (f, n) =Vi (n)f(i) и (f) =i f(i), мы можем преi∈IlimД о к а з а т е л ь с т в о является уточнением доказательства теоремы1.9.6.
А именно, соотношение (1.9.25) эквивалентно равенству V (f, n)P lim − (f) = 0 = 1.i∈IМы знаем, что Vi (n) /n → i с P i -вероятностью 1 для любого i ∈ I.Замечание 1.9.7 позволяет утверждать, что Vi (n) /n → i с Pj -вероятностью 1 (т. е. независимо от выбора начального состояния) или, более того,с P-вероятностью 1, где P — распределение ( , P) ц.м.д.в. с произвольнымначальным распределением . Получаем соотношение (1.9.25), что и завершает доказательство теоремы 1.9.8.Пример 1.9.9.
Опишите предельное поведение ц.м.д.в. на конечномпространстве состояний. Описание должно содержать обсуждение сходимости вероятностей, а также поведение почти наверное. Объясните, чтопроисходит с невозвратными цепями.Решение. Пространство состояний распадается на открытые классыO1 , . . . , Oj и замкнутые классы Cj+1 , . . . , Cj+l .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
