Цепи Маркова (1121219), страница 2
Текст из файла (страница 2)
В 1860 г. БэббиджПредисловие9представил в суд петицию, в которой он требовал, чтобы «никто не имелправа играть на шумных инструментах в местах, где находятся люди, занимающиеся серьезной работой», по сути запрещавшую любую уличнуюмузыку. Хотя суд и решил, что такого запрета быть не должно, и выступилпротив системы лицензий, он постановил, что Бэббидж (равно как и любойжитель) имеет право попросить любого музыканта удалиться из района, гдеон проживает.Тем не менее, как уже было сказано в первом томе, мы с глубокимуважением благодарим многочисленных бывших и настоящих сотрудниковфакультета математики Кембриджского университета, которые внесли свойвклад в собрание задач и решений «Треножников», относящихся к цепямМаркова и их приложениям.Нужно отметить, что изучение (или сопровождение процесса изучения) большого количества однотипных задач (с решениями или без них)может быть довольно скрупулезным.
Довольно распространенная средиматематической части научного общества точка зрения состоит в том,что наиболее продуктивный способ изучения математики — это переваритьдоказательства ряда теорем, достаточно общих, чтобы быть полезными навсе случаи жизни, а потом рассмотреть примеры, которые иллюстрируютэти теоремы (авторы этой книги обучались именно по такому образцу).Проблема в том, что такой метод идеально подходит для ученых с математическим складом мышления, но, скорее всего, не годится для всехостальных.С другой стороны, все большее число студентов (в основном, ноне всегда, с не-математической базой подготовки) сильно противится —по крайней мере психологически — любым попыткам провести «строгие» доказательства основных теорем. Более того, вычисления «вручную»,которые часто нужны в задачах с прозрачной идеей решения, также становятся все менее популярными среди студентов новых поколений, длякоторых использование персонального компьютера или ноутбука так жеестественно, как использование зубной щетки.
Авторы могут привестипримеры из своего лекционного опыта того, что аудитория зачастую доверяет компьютерным вычислениям, чем формальным доказательствам. Этодействительно является проблемой, особенно когда лекция читается дляширокой аудитории. Конечно, такое неприятие в какой-то мере обоснованно, хотя лично мы считаем, что изучение доказательства сходимости кстационарному распределению марковской цепи более продуктивно, чемизучение пары дюжин численных примеров, которые подтверждают этотфакт. Однако даже искусственный пример, в котором переходная матрицаразмерности 4 на 4 построена таким образом, что все собственные числа«хорошие» (одно равно 1, одно может быть найдено из соображений сим-10Предисловиеметрии, или иных «реалистических предположений», а остальные два —корни квадратного уравнения), может дать осечку, а иногда даже и обернуться против вас, в то время как при помощи пакета программ эту задачуможно решить элементарно.
Тем не менее, наше изложение не принимаеттакие вещи во внимание; мы полагаем, что это проявится в стиле написаниябудущих книг.Заметим, что на нашу книгу частично оказали влияние книги [N] и[St1] . Вдобавок многие бывшие и нынешние сотрудники статистическойлаборатории DPMMS Кембриджского университета внесли свой вклад всоздание определенного стиля изложения (мы говорили об этом во введении к первому тому). Мы с большим удовольствием назовем имена ДэвидаВильямса, Фрэнка Кэлли, Джеффри Гримметта, Дагласа Кеннеди, Джеймса Норриса, Гарета Робертса и Колина Спэрроу: мы слушали их лекции,изучали написанные ими курсы лекций и работали с их примерами.
Изпреподавателей университета Свонзи большую помощь и поддержку намоказали Алан Хоукс, Обри Трумэн и опять-таки Дэвид Вильямс. Советы икомментарии Роберта Липцера существенно повлияли на содержание гл. 3.Мы выражаем особую благодарность Эли Бассулзу, который прочиталранний вариант книги и сделал многочисленные замечания, направленныена улучшение текста. Его помощь вышла за обычный уровень участиядобросовестного читателя в подготовке математического текста и оказалаавторам огромную услугуМы благодарим Сару Шеи-Симондз и Евгению Кельберт за улучшениестиля книги. Мы также признательны Джону Хейгу, указавшему на ряднеточностей в английском издании.Книга содержит три главы, разбитые на параграфы.
Главы 1 и 2 включают материал университетских кембриджских курсов, но выходят далекоза их рамки в различных аспектах теории марковских цепей. В гл. 3 рассматриваются избранные вопросы математической статистики, в которыхструктура марковской цепи проясняет как постановку задачи, так и еерешение. Как правило, эти вопросы очевидны для независимых выборок,но становятся весьма техничными в общей постановке.Библиография содержит монографии, иллюстрирующие динамику развития теории случайных процессов, в частности, цепей Маркова, и параллельный прогресс в статистике.
Ссылки на необходимые научные статьисодержатся в самом тексте.Глава 1Цепи Маркова с дискретным временем§ 1.1. Марковское свойство и немедленныеследствия из негоНельзя выучить математику, только слушаялекции, точно так же как нельзя выучитьсяигре на пианино, только слушая пианиста.К. Рунге (1856-1927), немецкий математик-прикладникТеория марковских цепей — логическое продолжение основного курсатеории вероятностей. Мы изучим класс случайных процессов, которыйописывает огромное множество систем, представляющих как теоретический, так и прикладной интерес (а иногда просто занимательных). Тот факт,что достаточно глубокое погружение в предмет возможно без привлечениясложного математического аппарата, также объясняет, почему цепи Маркова популярны в самых различных дисциплинах, кажущихся достаточнодалекими от чистой математики.Базовой моделью первой части курса будет система, которая изменяетсвое состояние в дискретные моменты времени, согласуясь с неким случайным механизмом.
Множество всех состояний называется пространствомсостояний и на протяжении всего курса будет предполагаться конечнымили счетным; обозначим его I. Каждый элемент i ∈ I называется состоянием; наша система всегда будет находиться в одном из состояний.Иногда будет известно, в каком состоянии находится система, а иногдабудет лишь известно, что система находится в состоянии i с некоторойвероятностью.
Поэтому имеет смысл ввести вероятностную меру, иливероятностное распределение (или, для краткости, просто распределение), на I. Вероятностная мера на I — это просто совокупность ( i , i ∈ I)неотрицательных чисел, сумма которых равна единице:i> 0,Xi∈Ii= 1.(1.1.1)i∈Iной и может быть преобразованав вероятностное распределение путем.Pнормировки: ei = iбудетвероятностноймерой на I, посколькуjj∈IPePP .Pi =ij = 1. Но даже еслиi = ∞ (т. е. если общая массаi∈Ii∈Ij∈Ii∈IPбесконечна), можно приписать конечные значения (J) =i конечным== 1 — антидиагональную матрицу: 1 00 1,.0 11 0Система с единичной матрицей остается в начальном состоянии навсегда;в антидиагональном случае она меняет состояние в каждый момент времени, переходя из 0 в 1 и обратно.С другой стороны, при = = 1/2 мы получаем матрицу1 /2 1 /2.j∈JЕсли i = 1 для некоторого i ∈ I и j = 0 при j 6= i, то распределение«сосредоточено» в точке i.
Тогда состояние нашей системы становится«детерминированным».P Такое распределение обозначим i .Иногда условиеi = 1 не выполняется; тогда просто говорят, чтоi∈IP— мера на I. Если общая массаi < ∞, то мера называется конеч-а при13Мы можем рассматривать (1.1.1) как распределение единичной «массы» помножеству I, причем точка i имеет массу i .
По этой причине иногда удобноговорить о вероятностной функциимассы i ∈ I 7→ i . Тогда вероятностьP.множества J ⊆ I равна (J) =j§ 1.1. Марковское свойство и немедленные следствия из негоГлава 1. Цепи Маркова с дискретным временем121 /2 1 /2В этом случае система может либо остаться в том же состоянии, либопоменять его с вероятностью 1/2.Удобно представить матрицу перехода в виде диаграммы, на которойстрелками показаны возможные переходы, помеченные соответствующимиi∈Jподмножествам J ⊂ I.Случайный механизм, вызывающий изменение состояния, описываетсяматрицей перехода P с элементами pij , i, j ∈ I. Элемент pij равенвероятности, с которой система перейдет из состояния i в состояние j заединицу времени.
Таким образом, pij - это условная вероятность того, чтосистема будет находиться в состоянии j в следующий момент, при условии,что в данный момент она находится в состоянии i. Значит, все элементы Pнеотрицательны, но не превышают 1, и сумма элементов в любой строкеравна 1:Xpij = 1 ∀ i ∈ I.(1.1.2)0 6 pij 6 1 ∀ i, j ∈ I иj∈I6 1. В частности, при«La Dolce Beta»== 0 получаем единичную матрицу,1(Из серии «Фильмы, которые не вышли на большой экран».)Пример 1.1.2.
Матрица 4 × 40 1 /3 1 /3 1 /31 / 4 1 / 4 1 / 4 1 / 4 1 / 2 1 / 2 0 0 00011−где 0 6 ,вероятностями перехода («замкнутые» стрелки, ведущие обратно к своемуначалу, часто не рисуют, равно как и не обозначают детерминированныепереходы). См. рис. 1.1.Матрица P, обладающая такими свойствами, называется стохастической. По аналогии, вероятностное распределение ( i) на I часто называютстохастическим вектором. Тогда стохастическая матрица — это матрица,в которой каждая строка является стохастическим вектором.Пример 1.1.1. Простейший случай имеет вид 2 × 2 (пространство издвух состояний). Не ограничивая общности, можно считать, что состояниями являются 0 и 1; тогда элементы матрицы имеют вид p ij , i, j = 0, 1,а стохастическую матрицу можно представить в виде1−,Рис. 1.1представлена на рис. 1.2. Состояния занумеруем числами 1, 2, 3, 4.1 Ср.с названием фильма Ф.
Феллини «La Dolce Vita» («Сладкая жизнь»).14Глава 1. Цепи Маркова с дискретным временемВремя принимает значения n = 0, 1, 2, . . . Чтобы дополнить общуюкартину, нужно указать, в каком состоянии наша система находится в начальный момент n = 0. Как правило, мы будем предполагать, что система§ 1.1. Марковское свойство и немедленные следствия из него15Таким образом, при условии, что X0 = i0 , .
. . , Xn−1 = in−1 и Xn = i, Xn+1имеет распределение (pij , j ∈ I). В частности, условное распределение Xn+1не зависит от i0 , . . ., in−1 , т. е. зависит только от состояния i в последнийпредшествующий момент n.Формула (1.1.4) иллюстрирует свойство «ограниченной памяти» цепиМаркова.Другое следствие (1.1.3) — это элегантная формула, содержащая произведение матриц, для маргинального вероятностного распределения X n .Сейчас мы задаемся вопросом: какова вероятность P (X n = j) того, чтов момент n наша система находится в состоянии j. Например, для n = 1можно записать:XP (X0 = i, X1 = j),P (X1 = j) =i∈Iгде i — все возможные начальные состояния.
В самом деле, событияРис. 1.2в момент n = 0 находится в состоянии i с вероятностью i , где —заданное «начальное» распределение на I.Обозначим через Xn состояние нашей системы в момент n. Правила,задающие марковскую цепь с начальным распределением и матрицейперехода P, таковы:а) X0 имеет распределение :P (X0 = i) =i,∀ i ∈ I;i 0 pi 0 i 1. . . pin−1 in .(1.1.3)Конечно, а) — частный случай б) при n = 0.Важным следствием соотношения (1.1.3) являются равенства дляусловной вероятности P (Xn+1 = j | X0 = i0 , .