Вероятность и статистика в примерах и задачах. Том 2: Марковские цепи как отправная точка теории случайных процессов

МАРКОВСКИЕ ЦЕПИ КАК 
ОТПРАВНАЯ ТОЧКА ТЕОРИИ 
СЛУЧАЙНЫХ ПРОЦЕССОВ 
И ИХ ПРИЛОЖЕНИЯ

2

kelbert-tom-2-new-black-2-bordo.Page 1   29.01.2010   17:07:20
kelbert-tom-2-new-black-2-bordo.Page 1   29.01.2010   17:07:20

М. Я. Кельберт, Ю. М. Сухов

Вероятность и статистика
в примерах и задачах

Том 2

Марковские цепи как отправная точка теории
случайных процессов и их приложения

Электронное издание

Москва
Издательство МЦНМО
2017

УДК 519.21
ББК 22.171
К34

Кельберт М. Я., Сухов Ю. М.
Вероятность и статистика в примерах и задачах
Т. 2: Марковские цепи как отправная точка теории случайных
процессов и их приложения
Электронное издание
М.: МЦНМО, 2017
560 с.
ISBN 978-5-4439-2327-7

Для освоения теории вероятностей и математической статистики тренировка в решении задач и выработка интуиции важны не меньше, чем изучение
доказательств теорем; большое разнообразие задач по этому предмету затрудняет студентам переход от лекций к экзаменационным задачам, а от
них — к практике.
Специфический предмет этого тома, цепи Маркова и их применения,
переживает последнее время большой подъем. Многие замечательные теоретические результаты были получены в этой области, которая долгое время
рассматривалась многими специалистами как «мертвая»зона. Активную роль
в развитии этой области играют именно прикладные исследования. Предмет
этой книги критически важен как для современных приложений (финансовая математика, менеджмент, телекоммуникации, обработка сигналов, биоинформатика), так и для приложений классических (актуарная математика,
социология, инженерия).
Авторы собрали большое количество упражнений, снабженных полными решениями. Эти решения адаптированы к нуждам и умениям учащихся.
Необходимые теоретические сведения приводятся по ходу изложения; кроме
того, текст снабжен историческими отступлениями.

Подготовлено на основе книги:
Кельберт М. Я., Сухов Ю. М. Вероятность и статистика в примерах
и задачах. Т. 2: Марковские цепи как отправная точка теории случайных
процессов и их приложения. — М.: МЦНМО, 2010. —
ISBN 978-5-94057-557-3.

Издательство Московского центра
непрерывного математического образования
119002, Москва, Большой Власьевский пер., 11,
тел. (499)-241-08-04
http://www.mccme.ru

ISBN 978-5-4439-2327-7
© Кельберт М. Я., Сухов Ю. М., 2010
© МЦНМО, 2017

Оглавление

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5

Гл а в а 1. Цепи Маркова с дискретным временем . . . . . . . . . . . . .
9

§ 1.1.
Марковское свойство и немедленные следствия из него . . . . . .
9
§ 1.2.
Разбиение состояний на классы . . . . . . . . . . . . . . . . . . .
26
§ 1.3.
Времена и вероятности достижения . . . . . . . . . . . . . . . . .
35
§ 1.4.
Строго марковское свойство . . . . . . . . . . . . . . . . . . . . .
44
§ 1.5.
Возвратность и невозвратность: определения и основные факты .
48
§ 1.6.
Возвратность и невозвратность: случайные блуждания на кубических решетках . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
§ 1.7.
Инвариантные распределения: определения и основные факты.
Положительная и нулевая возвратность. I . . . . . . . . . . . . .
64
§ 1.8.
Положительная и нулевая возвратность. II . . . . . . . . . . . . .
71
§ 1.9.
Сходимость к положению равновесия. Предельные пропорции . .
82
§ 1.10. Детальный баланс и обратимость . . . . . . . . . . . . . . . . . .
93
§ 1.11. Управляемые и частично наблюдаемые цепи Маркова
. . . . . .
102
§ 1.12. Геометрическая алгебра цепей Маркова, I. Собственные значения
и спектральные щели . . . . . . . . . . . . . . . . . . . . . . . . .
109
§ 1.13. Геометрическая алгебра цепей Маркова, II. Случайные блуждания
на графах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
128
§ 1.14. Геометрическая алгебра цепей Маркова, III. Границы Пуанкаре
и Чигера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
143
§ 1.15. Большие уклонения для цепей Маркова с дискретным временем .
151
§ 1.16. Вопросы по теории цепей Маркова с дискретным временем на
экзаменах «Математические треножники» в Кембриджском университете . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
169

Гл а в а 2. Цепи Маркова с непрерывным временем . . . . . . . . . . . .
199

§ 2.1.
Матрицы перехода и Q-матрицы
. . . . . . . . . . . . . . . . . .
199
§ 2.2.
Марковские цепи с непрерывным временем: определения и основные конструкции. Марковское и строго марковское свойства
. .
209
§ 2.3.
Процесс Пуассона . . . . . . . . . . . . . . . . . . . . . . . . . . .
224
§ 2.4.
Неоднородный процесс Пуассона . . . . . . . . . . . . . . . . . .
243

Оглавление

§ 2.5.
Процессы рождения и гибели. Взрыв . . . . . . . . . . . . . . . .
251
§ 2.6.
Инвариантные распределения счетных цепей Маркова. Цепь
скачков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
268
§ 2.7.
Времена и вероятности достижения. Возвратность и невозвратность. Положительная и нулевая возвратность . . . . . . . . . . .
284
§ 2.8.
Сходимость к инвариантному распределению. Обратимость
. . .
302
§ 2.9.
Применения к теории очередей. Марковские очереди . . . . . . .
310
§ 2.10. Ветвящиеся процессы с непрерывным временем. Марковские процессы миграции и сети с очередями Джексона . . . . . . . . . . .
324
§ 2.11. Большие уклонения для цепей Маркова с непрерывным временем 353
§ 2.12. Вопросы к теории цепей Маркова с непрерывным временем, заданные на экзаменах «Математические треножники» в Кембриджском университете . . . . . . . . . . . . . . . . . . . . . . . . . . .
365

Гл а в а 3. Статистика цепей Маркова с дискретным временем . . . . .
405

§ 3.1.
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
405
§ 3.2.
Функции правдоподобия, I. Оценки максимального правдоподобия 413
§ 3.3.
Состоятельность оценок. Различные виды сходимости
. . . . . .
423
§ 3.4.
Функции правдоподобия, II. Формула Уиттла
. . . . . . . . . . .
448
§ 3.5.
Байесовский анализ цепей Маркова: априорные и апостериорные
распределения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
459
§ 3.6.
Элементы теории управления и теории информации . . . . . . . .
474
§ 3.7.
Скрытые марковские модели, I. Оценивание состояний марковских цепей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
492
§ 3.8.
Скрытые марковские модели, II. Обучающий алгоритм Баума—Уэлча . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
511
§ 3.9.
Обобщения алгоритма Баума—Уэлча. Глобальная сходимость
итераций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
521

Приложение I. Андрей Андреевич Марков и его время
. . . . . . . . . . . .
539

Приложение II. Пирсон, Максвелл и другие знаменитые Кембриджские
лауреаты: уроки, которые следует усвоить . . . . . . . . . . . . . . . . . . . .
544

Список литературы
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
554

Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
556

Предисловие

Этот том, как и предшествующий ему том 1, был задуман с намерением
дать студентам Кембриджского университета возможность проверить их
уровень подготовки к экзаменам (которые на университетском жаргоне
называются «Математические треножники»: см. Приложение II в конце
тома). Однако, как и в первом томе, в процессе подготовки появилась
и другая цель: показать широкой публике, как вероятность, статистика
и другие подобные курсы изучаются в Кембриджском университете и какой
уровень подготовки достигается к концу такого обучения. Следует заметить, что специфический предмет этого тома, цепи Маркова и их применения, переживает последнее время большой подъем. Многие замечательные
теоретические результаты были получены сравнительно недавно в этой области, которая только двадцать лет назад или около того рассматривалась
многими вероятностниками как «мертвая» зона. Еще более удивительно то,
что активную роль в развитии этой области сыграли в первую очередь прикладные исследования. Мотивируемые все увеличивающимся количеством
проблем, возникающих в таких, казалось бы, различных областях, как информатика, биология и финансы, «прикладные» математики вторглись на
территорию, которую традиционно занимали те немногие «чистые» математики, которые все еще продолжали улучшать старые результаты, убирая
или добавляя то или иное условие в теоремах, читать которые становилось
все труднее, не говоря уже о том, чтобы их применять. Поэтому мы не
могли не почувствовать себя обязанными включить некоторые из этих относительно новых идей в нашу книгу, несмотря на то, что соответствующие
параграфы имеют мало общего с нынешними кембриджскими курсами. Тем
не менее, мы старались по возможности придерживаться кембриджского
подхода (в нашем понимании) на протяжении всего тома.
В целом складывается ощущение, что современную теорию цепей Маркова можно сравнить с огромным и сложным живым организмом, который
внезапно проснулся из зимней спячки и в настоящее время находится
в стадии активного потребления и усвоения свежей пищи, поставляемой
плодородными полями, процветающими благодаря замечательным климатическим условиям. И, как часто бывает в природе, некоторые части такого
организма претерпевают серьезные изменения: они либо становятся более
важными, либо теряют свое значение по сравнению с предыдущей стадией
развития. Кроме того, некоторые части, например старая кожа, могут быть
сброшены, или заменены на новые, лучше приспособленные к внешнему

Предисловие

миру. В этом смысле нашу книгу можно сравнить с фотографическим
снимком этого гиганта с определенного расстояния и в некотором ракурсе.
Мы не можем показать все существо целиком (для этого оно слишком
велико и слишком быстро двигается), и многие детали в рамках нашей
фотографии получаются смазанными. Но тем не менее, мы надеемся, что
в целом картина получится новой и свежей.
В то же время наша цель заключалась в том, чтобы не упустить те темы,
которые в первую очередь важны в курсе, посвященном основным понятиям цепей Маркова. Мы здесь имеем в виду те разделы теории, которые
особенно стимулируют к размышлениям новичков, и, что неудивительно,
обычно предоставляют плодотворную почву для постановки подходящих
для экзаменов задач. В общем, весь материал теории цепей Маркова,
который оказался полезным на кембриджских экзаменах в 1991–2001 гг.,
включен в эту книгу.
Экзаменационные задачи сами по себе, наряду с их решениями, составляют важную часть этой книги, так же как и предыдущего тома. Мы осознаем, что этот шаг не прибавил счастья некоторым кембриджским коллегам, предпочитавшим сохранить этот материал «для служебного пользования». Тем не менее, с нашей точки зрения, теория цепей Маркова представляет интерес для представителей многих дисциплин (да и широкой публики
в целом). Многие люди, имеющие отношение к различным сферам академической жизни, желали бы изучить как можно скорее и в той степени,
в какой это возможно для них, основы этой теории и ее применения, и использовать эти знания в своей работе. Большинство из них не имеет математической базы, которую принято считать стандартной для кембриджских
студентов-математиков (в российский условиях мы могли бы сказать—для
студентов-математиков в Московском, Петербургском и Новосибирском
университетах). Совершенно естественный путь для них — пройти через
большое число задач, снабженных комментариями и решениями. Подборка
задач кембриджских «Математических треножников» с решениями исключительно полезна с этой точки зрения, и желание спрятать эти задачи
под замок и использовать исключительно для кембриджских студентов
кажется несколько эгоистичным, хотя и вполне понятным.
В связи с этим хотелось бы рассказать следующую историю о Чарльзе
Бэббидже (1791–1871), английском математике, который провел большую часть своей жизни, конструируя счетные машины (механические
устройства, которые можно считать прототипами современных компьютеров). В 1828–39 гг. Бэббидж занимал престижное кресло Лукасианского
профессора математики в Кембриджском университете (в данное время
это место занимает Стивен Хокинг); с 1840 г. он жил и работал в основном в Лондоне. В то время улицы Лондона были полны бродячих

Предисловие
7

шарманщиков (часто итальянских подростков с прекрасными голосами).
Их музицирование пришлось не по вкусу некоторым жителям Лондона,
и было предложено ввести систему лицензий, которые бы разрешали играть только в назначенное время и в определенных местах. В 1860 г.
Бэббидж представил в суд петицию, в которой он требовал, чтобы «никто
не имел права играть на шумных инструментах в местах, где находятся
люди, занимающиеся серьезной работой», по сути запрещавшую любую
уличную музыку. Хотя суд и решил, что такого запрета быть не должно,
и выступил против системы лицензий, он постановил, что Бэббидж (равно
как и любой житель) имеет право попросить любого музыканта удалиться
из района, где он проживает.
Тем не менее, как уже было сказано в первом томе, мы с глубоким
уважением благодарим многочисленных бывших и настоящих сотрудников
факультета математики Кембриджского университета, которые внесли свой
вклад в собрание задач и решений «Треножников», относящихся к цепям
Маркова и их приложениям.
Нужно отметить, что изучение (или сопровождение процесса изучения) большого количества однотипных задач (с решениями или без них)
может быть довольно скрупулезным. Довольно распространенная среди
математической части научного общества точка зрения состоит в том, что
наиболее продуктивный способ изучения математики—это переварить доказательства ряда теорем, достаточно общих, чтобы быть полезными на все
случаи жизни, а потом рассмотреть примеры, которые иллюстрируют эти
теоремы (авторы этой книги обучались именно по такому образцу). Проблема в том, что такой метод идеально подходит для ученых с математическим складом мышления, но, скорее всего, не годится для всех остальных.
С другой стороны, все большее число студентов (в основном, но не
всегда, с не-математической базой подготовки) сильно противится — по
крайней мере психологически — любым попыткам провести «строгие» доказательства основных теорем. Более того, вычисления «вручную», которые часто нужны в задачах с прозрачной идеей решения, также становятся
все менее популярными среди студентов новых поколений, для которых
использование персонального компьютера или ноутбука так же естественно, как использование зубной щетки. Авторы могут привести примеры из
своего лекционного опыта того, что аудитория зачастую доверяет компьютерным вычислениям гораздо больше, чем формальным доказательствам.
Это действительно является проблемой, особенно когда лекция читается
для широкой аудитории. Конечно, такое неприятие в какой-то мере обоснованно, хотя лично мы считаем, что изучение доказательства сходимости
к стационарному распределению марковской цепи более продуктивно, чем
изучение пары дюжин численных примеров, которые подтверждают этот

Предисловие

факт. Однако даже искусственный пример, в котором переходная матрица
размерности 4 на 4 построена таким образом, что все собственные числа
«хорошие» (одно равно 1, одно может быть найдено из соображений симметрии, или иных «реалистических предположений», а остальные два —
корни квадратного уравнения), может дать осечку, а иногда даже и обернуться против составителя, в то время как при помощи пакета программ
эту задачу можно решить элементарно. Тем не менее, наше изложение
в этом томе не принимает такие вещи во внимание; мы полагаем, что это
проявится в стиле написания будущих книг.
Заметим, что на нашу книгу частично оказали влияние книги [N] и
[St1]. Вдобавок многие бывшие и нынешние сотрудники статистической
лаборатории DPMMS Кембриджского университета внесли свой вклад
в создание определенного стиля изложения (мы говорили об этом во
введении к первому тому). Мы с большим удовольствием назовем имена
Дэвида Вильямса, Фрэнка Кэлли, Джеффри Гримметта, Дагласа Кеннеди,
Джеймса Норриса, Гарета Робертса и Колина Спэрроу: мы слушали их
лекции, изучали написанные ими курсы лекций и работали с их примерами. Из сотрудников университета Свонзи большую помощь и поддержку
нам оказали Алан Хоукс, Обри Трумэн и опять-таки Дэвид Вильямс.
Советы и комментарии Роберта Липцера существенно повлияли на содержание гл. 3. Мы выражаем особую благодарность Эли Бассулзу, который
прочитал ранний вариант книги и сделал многочисленные замечания, направленные на улучшение текста. Его помощь вышла за обычный уровень
участия добросовестного читателя в подготовке математического текста
и оказала авторам огромную услугу.
Мы благодарим Сару Шеи-Симондз и Евгению Кельберт за улучшение
стиля книги. Мы также признательны Джону Хейгу, указавшему на ряд
неточностей в английском издании. Мы особенно благодарны Юрию Николаевичу Тюрину, инициатору перевода этой серии книг на русский язык.
Книга содержит три главы, разбитые на параграфы. Главы 1 и 2 включают материал университетских кембриджских курсов, но выходят далеко
за их рамки в различных аспектах теории марковских цепей. В гл. 3 рассматриваются избранные вопросы математической статистики, в которых
структура марковской цепи проясняет как постановку задачи, так и ее
решение. Как правило, эти вопросы очевидны для независимых выборок,
но становятся весьма техничными в общей постановке.
Текст русского издания был значительно переработан и дополнен.
Библиография содержит монографии, иллюстрирующие динамику развития теории случайных процессов, в частности, цепей Маркова, и параллельный прогресс в статистике. Ссылки на необходимые научные статьи
содержатся в самом тексте.

Глава 1

Цепи Маркова с дискретным временем

§ 1.1. Марковское свойство и немедленные
следствия из него

Нельзя выучить математику, только слушая
лекции, точно так же как нельзя выучиться
игре на пианино, только слушая пианиста.

К. Рунге (1856-1927),
немецкий математик-прикладник

Теория марковских цепей — логическое продолжение основного курса
теории вероятностей. Мы изучим класс случайных процессов, который
описывает огромное множество систем, представляющих как теоретический, так и прикладной интерес (а иногда просто занимательных). Тот факт,
что достаточно глубокое погружение в предмет возможно без привлечения
сложного математического аппарата, также объясняет, почему цепи Маркова популярны в самых различных дисциплинах, кажущихся достаточно
далекими от чистой математики.
Базовой моделью первой части курса будет система, которая изменяет
свое состояние в дискретные моменты времени, согласуясь с неким случайным механизмом. Множество всех состояний называется пространством
состояний и на протяжении всего курса будет предполагаться конечным
или счетным; обозначим его I. Каждый элемент i ∈ I называется состоянием; наша система всегда будет находиться в одном из состояний.
Иногда будет известно, в каком состоянии находится система, а иногда
будет лишь известно, что система находится в состоянии i с некоторой
вероятностью. Поэтому имеет смысл ввести вероятностную меру, или
вероятностное распределение (или, для краткости, просто распределение), на I. Вероятностная мера
l на I — это просто совокупность (
li, i ∈ I)
неотрицательных чисел, сумма которых равна единице:

li ⩾ 0,
i∈I

li = 1.
(1.1.1)

Глава 1. Цепи Маркова с дискретным временем

Мы можем рассматривать (1.1.1) как распределение единичной «массы» по
множеству I, причем точка i имеет массу
li. По этой причине иногда удобно
говорить о вероятностной функции массы i ∈ I →
li. Тогда вероятность
множества J ⊆ I равна
l(J) = j∈J

lj.

Если
li = 1 для некоторого i ∈ I и
lj = 0 при j ̸= i, то распределение
«сосредоточено» в точке i. Тогда состояние нашей системы становится
«детерминированным». Такое распределение обозначим
di.
Иногда условие i∈I

li = 1 не выполняется; тогда просто говорят, что

l — мера на I. Если общая масса i∈I

li < ∞, то мера называется конеч
ной и может быть преобразована в вероятностное распределение путем
нормировки: li =
li
j∈I

lj будет вероятностной мерой на I, поскольку
i∈I
li = i∈I

li
j∈I

lj = 1. Но даже если i∈I

li = ∞ (т. е. если общая масса

бесконечна), можно приписать конечные значения
l(J) = i∈J

li конечным
подмножествам J ⊂ I.
Случайный механизм, вызывающий изменение состояния, описывается
матрицей перехода P с элементами pij, i, j ∈ I. Элемент pij равен вероятности, с которой система перейдет из состояния i в состояние j за
единицу времени. Таким образом, pij — это условная вероятность того, что
система будет находиться в состоянии j в следующий момент, при условии,
что в данный момент она находится в состоянии i. Значит, все элементы P
неотрицательны, но не превышают 1, и сумма элементов в любой строке
равна 1:

0 ⩽ pij ⩽ 1 ∀i, j ∈ I
и
j∈I
pij = 1 ∀i ∈ I.
(1.1.2)

Матрица P, обладающая такими свойствами, называется стохастической. По аналогии, вероятностное распределение (
li) на I часто называют
стохастическим вектором. Тогда стохастическая матрица — это матрица,
в которой каждая строка является стохастическим вектором.
Пример 1.1.1. Простейший случай имеет вид 2 × 2 (пространство из
двух состояний). Не ограничивая общности, можно считать, что состояниями являются 0 и 1; тогда элементы матрицы имеют вид pij, i, j = 0, 1,
а стохастическую матрицу можно представить в виде
1 −
a
a

b
1 −
b

,

где 0 ⩽
a,
b ⩽ 1. В частности, при
a =
b = 0 получаем единичную матрицу,

§ 1.1. Марковское свойство и немедленные следствия из него
11

а при
a =
b = 1 — антидиагональную матрицу:
1 0
0 1

,
0 1
1 0

.

Система с единичной матрицей остается в начальном состоянии навсегда;
в антидиагональном случае она меняет состояние в каждый момент времени, переходя из 0 в 1 и обратно.
С другой стороны, при
a =
b = 1/2 мы получаем матрицу
1/2 1/2
1/2 1/2

.

В этом случае система может либо остаться в том же состоянии, либо
поменять его с вероятностью 1/2.

Удобно представить матрицу перехода в виде диаграммы, на которой
стрелками показаны возможные переходы, помеченные соответствующими

Рис. 1.1

вероятностями перехода («замкнутые» стрелки, ведущие обратно к своему
началу, часто не рисуют, равно как и не обозначают детерминированные
переходы). См. рис. 1.1.

«La Dolce Beta» 1

(Из серии «Фильмы, которые не вышли на большой экран».)

Пример 1.1.2. Матрица 4 × 4





0
1/3 1/3 1/3
1/4 1/4 1/4 1/4
1/2 1/2
0
0
0
0
0
1






представлена на рис. 1.2. Состояния занумеруем числами 1, 2, 3, 4.

Время принимает значения n = 0, 1, 2, . . . Чтобы дополнить общую
картину, нужно указать, в каком состоянии наша система находится в начальный момент n = 0. Как правило, мы будем предполагать, что система

1Ср. с названием фильма Ф. Феллини «La Dolce Vita» («Сладкая жизнь»).