Кельберт М.Я., Сухов Ю.М. Вероятность и статистика в примерах и задачах. Том 2. Марковские цепи как отправная точка теории случайных процессов и их приложения

Подождите немного. Документ загружается.

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

ВЕРОЯТНОСТЬ И СТАТИСТИКА

В ПРИМЕРАХ И ЗАДАЧАХ

Том II

Марковские цепи как отправная точка

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

приложения

Москва

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

2009

УДК 519.21???

ББК 22.171???

К34???

Издание осуществлено при поддержке РФФИ

(издательский проект № ??

?????).

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

К34??? Вероятность и статистика в примерах и задачах. Т. II: Марков

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

приложения. М.: МЦНМО, 2009.

—

??? с.: ил.

ISBN ???

Для освоения теории вероятностей и математической статистики тренировка в

решении задач и выработка интуиции важны не меньше, чем изучение доказательств

теорем; большое разнообразие задач по этому предмету затрудняет студентам пере

ход от лекций к экзаменационным задачам, а от них

—

к практике.

Специфический предмет этого тома, цепи Маркова и их применения, переживает

последнее время большой подъем. Многие замечательные теоретические результаты

были получены в этой области, которая долгое время рассматривалась многими

специалистами как

мертвая

зона. Активную роль в развитии этой области играют

именно прикладные исследования. Предмет этой книги критически важен как для

современных приложений (финансовая математика, менеджмент, телекоммуникации,

обработка сигналов, биоинформатика), так и для приложений классических (актуар

ная математика, социология, инженерия).

Авторы собрали большое количество упражнений, снабженных полными реше

ниями. Эти решения адаптированы к нуждам и умениям учащихся. Необходимые

теоретические сведения приводятся по ходу изложения; кроме того, текст снабжен

историческими отступлениями.

ББК 22.171???

Перевод с английского Л. Сахно под ред. Ю. Мишуры

На обложке изображены... (г. Кембридж, Великобритания).

ISBN ??? (Том II)

ISBN 978

94057

252

Оглавление

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

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

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

§ 1.2. Разбиение состояний на классы . . . . . . . . . . . . . . . . 29

§ 1.3. Времена и вероятности достижения . . . . . . . . . . . . . . 38

§ 1.4. Строго марковское свойство . . . . . . . . . . . . . . . . . . 47

§ 1.5. Возвратность и невозвратность: определения и основные

факты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

§ 1.6. Возвратность и невозвратность: случайные блуждания на

кубических решетках . . . . . . . . . . . . . . . . . . . . . . 59

§ 1.7. Инвариантные распределения: определения и основные

факты. Положительная и нулевая возвратность. I . . . . . . 68

§ 1.8. Положительная и нулевая возвратность. II . . . . . . . . . . 76

§ 1.9. Сходимость к положению равновесия. Предельные про

порции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

§ 1.10. Детальный баланс и обратимость . . . . . . . . . . . . . . . 98

§ 1.11. Управляемые и частично наблюдаемые цепи Маркова . . . 108

§ 1.12. Геометрическая алгебра цепей Маркова, I. Собственные

значения и спектральные щели . . . . . . . . . . . . . . . . . 115

§ 1.13. Геометрическая алгебра цепей Маркова, II. Случайные

блуждания на графах . . . . . . . . . . . . . . . . . . . . . . 134

§ 1.14. Геометрическая алгебра цепей Маркова, III. Границы Пу

анкаре и Чигера . . . . . . . . . . . . . . . . . . . . . . . . . 150

§ 1.15. Большие уклонения для цепей Маркова с дискретным вре

менем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

4 Оглавление

§ 1.16. Вопросы по теории цепей Маркова с дискретным временем

на экзаменах

Математические треножники

в Кембридж

ском университете . . . . . . . . . . . . . . . . . . . . . . . . 177

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

§ 2.1. Матрицы перехода и Q

матрицы . . . . . . . . . . . . . . . 209

§ 2.2. Марковские цепи с непрерывным временем: определения

и основные конструкции. Марковское и строго марковское

свойства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

§ 2.3. Процесс Пуассона . . . . . . . . . . . . . . . . . . . . . . . . 235

§ 2.4. Неоднородный процесс Пуассона . . . . . . . . . . . . . . . 256

§ 2.5. Процессы рождения и гибели. Взрыв . . . . . . . . . . . . . 263

§ 2.6. Инвариантные распределения счетных цепей Маркова.

Цепь скачков . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

§ 2.7. Времена и вероятности достижения. Возвратность и невоз

вратность. Положительная и нулевая возвратность . . . . . 300

§ 2.8. Сходимость к инвариантному распределению. Обратимость 320

§ 2.9. Применения к теории очередей. Марковские очереди . . . . 327

§ 2.10. Ветвящиеся процессы с непрерывным временем. Марков

ские процессы миграции и сети с очередями Джексона . . . 342

§ 2.11. Большие уклонения для цепей Маркова с непрерывным

временем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

§ 2.12. Вопросы к теории цепей Маркова с непрерывным време

нем, заданные на экзаменах

Математические треножни

ки

в Кембриджском университете . . . . . . . . . . . . . . 385

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

§ 3.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427

§ 3.2. Функции правдоподобия, I. Оценки максимального прав

доподобия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435

§ 3.3. Состоятельность оценок. Различные виды сходимости . . . 446

§ 3.4. Функции правдоподобия, II. Формула Уиттла . . . . . . . . 472

§ 3.5. Байесовский анализ цепей Маркова: априорные и апосте

риорные распределения . . . . . . . . . . . . . . . . . . . . . 484

§ 3.6. Элементы теории управления и теории информации . . . . . 499

§ 3.7. Скрытые марковские модели, I. Оценивание состояний

марковских цепей . . . . . . . . . . . . . . . . . . . . . . . . 518

Оглавление 5

§ 3.8. Скрытые марковские модели, II. Обучающий алгоритм Ба

ума

—

Уэлча . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539

§ 3.9. Обобщения алгоритма Баума

—

Уэлча. Глобальная сходи

мость итераций . . . . . . . . . . . . . . . . . . . . . . . . . . 549

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

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

ские лауреаты: уроки, которые следует усвоить . . . . . . . . . . . . . 575

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

Предисловие

Этот том, как и предшествующий ему том I, был задуман с намерением

дать студентам Кембриджа возможность проверить их уровень подготов

ки к экзаменам

Математические треножники

. Однако, как и в первом

томе, в процессе подготовки появилась и другая цель: показать широкой

публике, как вероятность, статистика и другие подобные курсы изучаются

в Кембриджском университете и какой уровень подготовки достигается

к концу такого обучения. Вдобавок специфический предмет этого тома,

цепи Маркова и их применения, переживает последнее время большой

подъем. Многие замечательные теоретические результаты были получены

в этой области, которая только двадцать лет назад или около того рас

сматривалась многими вероятностниками как

мертвая

зона. Еще более

удивительно то, что активную роль в развитии этой области играли именно

прикладные исследования. Мотивируемые все увеличивающимся количе

ством проблем, возникающих в таких, казалось бы, различных областях,

как информатика, биология и финансы,

прикладные

математики вторг

лись на территорию, которую традиционно занимали те немногие

чистые

математики, которые все еще продолжали улучшать старые результаты,

убирая или добавляя то или иное условие в теоремах, читать которые ста

новилось все труднее, не говоря уже о том, чтобы их применять. Поэтому

мы не могли не почувствовать себя обязанными включить некоторые из

этих относительно новых идей в нашу книгу, несмотря на то, что соответ

ствующие параграфы имеют мало общего с нынешними кембриджскими

курсами. Тем не менее, мы старались по возможности придерживаться

кембриджского подхода (в нашем понимании) на протяжении всего тома.

В целом складывается ощущение, что современную теорию цепей Мар

кова можно сравнить с огромным и сложным живым организмом, который

внезапно проснулся из зимней спячки и в настоящее время находится

в стадии активного потребления и усвоения свежей пищи, поставляемой

плодородными полями, процветающими благодаря замечательным клима

тическим условиям. И, как часто бывает в природе, некоторые части такого

организма претерпевают серьезные изменения: они либо становятся более

важными, либо теряют свое значение по сравнению с предыдущей стадией

развития. Кроме того, некоторые части, например старая кожа, могут быть

сброшены, или заменены на новые, лучше приспособленные к внешнему

миру. В этом смысле нашу книгу можно сравнить с фотографическим

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

снимком этого гиганта с определенного расстояния и в некотором ракурсе.

Мы не можем показать все существо целиком (для этого оно слишком

велико и слишком быстро двигается), и многие детали в рамках нашей

фотографии получаются смазанными. Но тем не менее, мы надеемся, что

в целом картинка получится новой и свежей.

В то же время наша цель заключалась в том, чтобы не упустить те

темы, которые особенно важны в курсе, посвященном основным поня

тиям цепей Маркова. Эти те главы, которые особенно стимулируют к

размышлениям новичков, и, что неудивительно, обычно предоставляют

плодотворную почву для постановки подходящих для экзаменов задач. В

общем, весь материал теории цепей Маркова, который оказался полезным

на кембриджских экзаменах в 1991

–

2001 гг., включен в эту книгу.

Конечно, экзаменационные задачи сами по себе, наряду с их решения

ми, составляют важную часть этой книги, так же как и предыдущего тома.

Мы осознаем, что этот шаг не прибавил счастья некоторым кембридж

ским коллегам, предпочитавшим сохранить этот материал

для служебного

пользования

. Тем не менее, с нашей точки зрения, теория цепей Маркова

представляет интерес для представителей многих дисциплин. Многие люди,

имеющие отношение к различным сферам академической жизни, желали

бы изучить как можно скорее и в той степени, в какой это возможно для

них, основы этой теории и ее применения, и использовать эти знания в

своей работе. Большинство из них не имеет математической базы, которую

принято считать стандартной для кембриджских студентов

математиков.

Совершенно естественный путь для них

—

пройти через большое число

задач, снабженных комментариями и решениями. Подборка задач кем

бриджских

Математических треножников

с решениями исключительно

полезна с этой точки зрения, и желание спрятать эти задачи под за

мок и использовать исключительно для кембриджских студентов кажется

несколько эгоистичным, хотя и вполне понятным.

В связи с этим хотелось бы рассказать следующую историю о Чарльзе

Бэббидже (1791

–

1871), английском математике, который провел боль

шую часть своей жизни, конструируя счетные машины (механические

устройства, которые можно считать прототипами современных компьюте

ров). В 1828

–

39 гг. Бэббидж занимал престижное кресло Лукасианского

профессора математики в Кембриджском университете (в данное время

это место занимает Стефан Хокинг); с 1840 г. он жил и работал в ос

новном в Лондоне. В то время улицы Лондона были полны бродячих

шарманщиков (часто итальянских подростков с прекрасными голосами).

Их музицирование пришлось не по вкусу некоторым жителям Лондона, и

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

только в назначенное время и в определенных местах. В 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

∈

неотрицательных чисел, сумма которых равна единице:

∈

1. (1.1.1)

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

Мы можем рассматривать (1.1.1) как распределение единичной

массы

по

множеству I, причем точка i имеет массу

. По этой причине иногда удобно

говорить о вероятностной функции массы i

∈

7→

. Тогда вероятность

множества J

⊆

I равна (J)

∈

Если

1 для некоторого i

∈

I и

0 при j

i, то распределение

сосредоточено

в точке i. Тогда состояние нашей системы становится

детерминированным

. Такое распределение обозначим

Иногда условие

∈

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

—

мера на I. Если общая масса

∈

< ∞

, то мера называется конеч

ной и может быть преобразована в вероятностное распределение путем

нормировки:

∈

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

∈

1. Но даже если

∈

= ∞

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

бесконечна), можно приписать конечные значения

(J)

∈

конечным

подмножествам J

⊂

Случайный механизм, вызывающий изменение состояния, описывается

матрицей перехода P с элементами p

, i, j

∈

I. Элемент p

равен

вероятности, с которой система перейдет из состояния i в состояние j за

единицу времени. Таким образом, p

это условная вероятность того, что

система будет находиться в состоянии j в следующий момент, при условии,

что в данный момент она находится в состоянии i. Значит, все элементы P

неотрицательны, но не превышают 1, и сумма элементов в любой строке

равна 1:

∀

i, j

∈

I и

∈

∀

∈

I. (1.1.2)

Матрица P, обладающая такими свойствами, называется стохастиче-

ской. По аналогии, вероятностное распределение (

) на I часто называют

стохастическим вектором. Тогда стохастическая матрица

—

это матрица,

в которой каждая строка является стохастическим вектором.

Пример 1.1.1. Простейший случай имеет вид 2

2 (пространство из

двух состояний). Не ограничивая общности, можно считать, что состоя

ниями являются 0 и 1; тогда элементы матрицы имеют вид p

, i, j

0, 1,

а стохастическую матрицу можно представить в виде



−



где 0

1. В частности, при

= =

0 получаем единичную матрицу,

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

а при

= =

—

антидиагональную матрицу:



1 0

0 1





0 1

1 0



Система с единичной матрицей остается в начальном состоянии навсегда;

в антидиагональном случае она меняет состояние в каждый момент вре

мени, переходя из 0 в 1 и обратно.

С другой стороны, при

= =

2 мы получаем матрицу



2 1



В этом случае система может либо остаться в том же состоянии, либо

поменять его с вероятностью 1

Удобно представить матрицу перехода в виде диаграммы, на которой

стрелками показаны возможные переходы, помеченные соответствующими

Рис. 1.1

вероятностями перехода (

замкнутые

стрелки, ведущие обратно к своему

началу, часто не рисуют, равно как и не обозначают детерминированные

переходы). См. рис. 1.1.

La Dolce Beta

(Из серии

Фильмы, которые не вышли на большой экран

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







0 1

3 1

4 1

2 1

2 0 0

0 0 0 1







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

Ср. с названием фильма Ф. Феллини

La Dolce Vita

(

Сладкая жизнь

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

Время принимает значения n

0, 1, 2, . . . Чтобы дополнить общую

картину, нужно указать, в каком состоянии наша система находится в на

чальный момент n

0. Как правило, мы будем предполагать, что система

Рис. 1.2

в момент n

0 находится в состоянии i с вероятностью

, где

—

заданное

начальное

распределение на I.

Обозначим через X

состояние нашей системы в момент n. Правила,

задающие марковскую цепь с начальным распределением

и матрицей

перехода P, таковы:

а) X

имеет распределение :

P (X

∀

∈

б) более общим образом,

∀

n и i

, . . . , i

∈

I вероятность P (X

, . . . , X

) того, что система находится в состояниях i

, i

, . . .

. . . , i

в моменты времени 0, 1, . . . , n записывается как произведение

P (X

, X

, . . . , X

)

. . . p

−

. (1.1.3)

Конечно, а)

—

частный случай б) при n

Важным следствием соотношения (1.1.3) являются равенства для

условной вероятности P (X

, . . . , X

−

, X

i) того,

что состояние в момент n

1 есть j, при условии, что заданы состояния

,. . . , i

−

и i

i в моменты времени 0, . . . , n

−

1, n:

P (X

, . . . , X

−

, X

P (X

, . . . , X

−

, X

i, X

P (X

, . . . , X

−

, X

. . . p

−

. . . p

−

. (1.1.4)

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

Таким образом, при условии, что X

, . . . , X

−

и X

i, X

имеет распределение (p

, j

∈

I). В частности, условное распределение X

не зависит от i

, . . ., i

−

, т. е. зависит только от состояния i в последний

предшествующий момент n.

Формула (1.1.4) иллюстрирует свойство

ограниченной памяти

цепи

Маркова.

Другое следствие (1.1.3)

—

это элегантная формула, содержащая про

изведение матриц, для маргинального вероятностного распределения X

Сейчас мы задаемся вопросом: какова вероятность P (X

j) того, что

в момент n наша система находится в состоянии j. Например, для n

можно записать:

P (X

∈

P (X

i, X

j),

где i

—

все возможные начальные состояния. В самом деле, события

{

состояние i в момент 0, состояние j в момент 1

}

не пересекаются для различных i

∈

I и их объединение равно событию

{

состояние j в момент 1

}

Теперь используем формулу (1.1.3) и напомним правила алгебры матриц:

∈

P (X

i, X

∈

( P)

Путем прямых вычислений эту формулу можно распространить на об

щие значения n:

P (X

,...,i

−

P (X

, . . . , X

−

, X

,...,i

−

. . . p

−

( P

)

, (1.1.5)

где P

—

я степень матрицы P. Таким образом, стохастический вектор,

описывающий распределение величины X

, можно получить, применив

матрицу P

к начальному стохастическому вектору .

Затем аналогично предыдущему

P (X

i, X

,...,i

−

P (X

, . . . , X

−

, X

i, X

,...,i

−

. . . p

−

( P

)

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

откуда следует, что

P (X

i, X

P (X

( P

)

( P

)

. (1.1.6)

Иными словами, элемент p

равен условной вероятности того, что в сле

дующий момент состояние будет j, если в данный момент оно есть i.

Более того,

P (X

i, X

,...,i

−

P (X

i, X

, . . . , X

−

, X

,...,i

−

. . . p

−

)

P (X

i, X

P (X

)

. (1.1.7)

Значит, элемент (P

)

матрицы P

дает вероятность перехода за n шагов

из состояния i в состояние j. Иногда мы будем обозначать эту вероят

ность p

(n)

В общем случае

P (X

i, X

( P

)

P (X

i, X

P (X

( P

)

( P

)

. (1.1.8)

Как следствие, любая степень P

стохастической матрицы вновь сто

хастическая матрица, т. е.

∈

(n)

∀

∈

I. Конечно, этот факт можно

проверить с помощью непосредственных вычислений:

∈

(n)

,...,i

−

. . . p

−

. . .

−

поскольку на каждом шаге (начиная с

) сумма равна единице в силу

соотношений (1.1.2).

Другое следствие состоит в том, что применяя к стохастическому векто

ру стохастическую матрицу (P или в общем случае P

), мы вновь получим

стохастический вектор. Этот факт также подтверждается прямыми вычис

лениями с использованием (1.1.1):

( P

)

i,j

)

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

Окончательно обобщает соотношение (1.1.3) формула

P (X

, X

, . . . , X

)

( P

)

−

)

. . . (P

−

)

−

, (1.1.9)

верная для всех моментов 0

. . .

и состояний i

, . . . , i

∈

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

(

)

—

стохастический вектор и P

)

—

матрица перехода на I.

Случайное состояние X

в момент n рассматривается как случайная вели

чина со значениями I.

Определение 1.1.3. Говорят, что последовательность случайных ве

личин X

со значениями в конечном или счетном множестве I образует

цепь Маркова с дискретным временем (ц.м.д.в.), или, коротко, цепь

Маркова, с начальным распределением

и матрицей перехода P, если

∀

, . . . , i

∈

I совместное распределение P (X

, . . . , X

) задается

формулой (1.1.3). В этом случае мы говорим, что (X

)

—

цепь Маркова

с параметрами (

, P), или ( , P)

—

цепь Маркова.

Теорема 1.1.4. Если (X

)

—

цепь Маркова с параметрами ( , P), то

а) Условная вероятность

P (X

, . . . , X

−

, X

равна условной вероятности P (X

i) и совпадает

с p

. Эквивалентно, условное распределение X

при условии X

, . . . , X

−

, X

i не зависит от i

, . . . , i

−

и совпадает

с (p

, j

∈

I), т. е. с i-й строкой матрицы P.

б) Вероятность P (X

i) того, что состояние в момент n есть i,

равна (

)

в) Элемент p

(n)

матрицы P

совпадает с условной вероятностью

P (X

i), т. е. задает вероятность перехода из i в j за n

шагов.

г) Вероятность общего вида

P (X

, X

, . . . , X

)

задается формулой (1.1.9).

Dial M for Markov

(Из серии

Фильмы, которые не вышли на большой экран

Ср. с названием фильма

Dial M for Murder

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

Пример 1.1.5. Предположим, что все строки матрицы P одинаковы,

т. е. p

не зависит от i. Предположим также, что

, т. е.

совпадает с любой строкой матрицы P. Тогда в силу соотношения (1.1.3)

получаем

P (X

, X

, . . . , X

)

. . . p

Кроме того, в этом примере P

P, так как

(n)

,...,i

−

. . . p

−

. . .

−

благодаря тому что

∈

1. Значит,

P (X

( P

)

∈

(n)

∈

Таким образом,

P (X

, X

, . . . , X

)

P (X

) P (X

) . . . P (X

Следовательно, (X

)

—

последовательность независимых одинаково рас

пределенных (или, коротко, н.о.р.с.в.).

Пример 1.1.6. Если P

—

диагональная матрица, то она должна сов

падать с единичной матрицей, у которой строка с номером i задается

стохастическим вектором







1 0 0 . . . 0

0 1 0 . . . 0

0 0 1 . . . 0

0 0 0 . . . 1







В этом случае любая степень P

вновь равна единичной матрице. Значит,

в силу соотношения (1.1.4) мы получаем, P (X

, т. е. распределе

ние случайной величины (с.в.) X

такое же, как и у X

. Другими словами,

начальное распределение сохраняется во времени.

Пример 1.1.7. Для ц.м.д.в. с двумя состояниями матрица P равна



−



. Элементы P

можно найти с помощью непосредственного

вычисления. Действительно, P

−

P, откуда для элемента p

(n)

полу

чаем равенство

(n)

−

)

−

)

−

)

= +

− −

−

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

Это соотношение рекуррентно по n, с начальными значениями p

(0)

и p

(1)

−

. Значит,

(n)

B(1

− −

)

где

1, A

B(1

− −

)

−

откуда с очевидностью следует, что

(n)







− −

)

, если

+ >

1, если

= =

Элемент p

(n)

можно получить, меняя и местами, а элементы p

(n)

и p

(n)

—

как дополнения до 1.

Пример 1.1.8. В общем случае для вычисления элементов P

мож

но использовать собственные числа и собственные векторы матрицы P.

Рассмотрим пример с матрицей 3

0 1 0

0 2

3 1

3 0 2

Ее собственные числа являются решениями характеристического уравне

ния:

det

−

1 0

0 2

−

3 0 2

−

= −

−

= −

(

−



−



откуда получаем

√

Поскольку все собственные числа различны, матрицу P можно диагона

лизовать: существует такая обратимая матрица D, что

−







1 0 0

√

0 0

−

√







, т. е. P







1 0 0

√

0 0

−

√







−