Кельберт М.Я., Сухов Ю.М. Вероятность и статистика в примерах и задачах. Том 2. Марковские цепи как отправная точка теории случайных процессов и их приложения
Подождите немного. Документ загружается.
20 Глава 1. Цепи Маркова с дискретным временем
Тогда
P
n
=
D
1 0 0
0
1
+
i
√
3
6
n
0
0 0
1
−
i
√
3
6
n
D
−
1
,
и любой элемент матрицы P
n
имеет вид суммы
A
+
B
1
+
i
√
3
6
n
+
C
1
−
i
√
3
6
n
.
Коэффициенты A, B и C могут быть комплексными; они меняются от
элемента к элементу, а найти их можно, подставляя n
=
0, 1, 2. Если
n
=
0, то P
0
=
I
—
единичная матрица (точно так же, как для скаляров
p
0
=
1 для всех p (включая p
=
0)); для n
=
1 берем матрицу P и при
n
=
2 возводим ее в квадрат, чтобы получить P
2
. Например, предположим,
что состояния системы
—
это 1, 2 и 3; в этом случае элементы имеют вид
p
(n)
ij
, i, j
=
1, 2, 3. Тогда для p
(n)
12
пишем:
p
(0)
12
=
A
+
B
+
C
=
0, p
(1)
12
=
A
+
B
1
+
i
√
3
6
+
C
1
−
i
√
3
6
=
1
и
p
(2)
12
=
A
+
B
1
+
i
√
3
6
2
+
C
1
−
i
√
3
6
2
=
2
3
.
Вычисления можно упростить, если избавиться от мнимых частей (по
-
скольку элементы p
(n)
ij
матрицы P
n
действительны и неотрицательны).
С этой целью сперва заметим, что
±
—
комплексные сопряженные корни,
и запишем
1
±
i
√
3
6
=
1
3
1
±
i
√
3
2
=
1
3
e
±
i
/
3
=
1
3
cos
3
±
i sin
3
.
Затем получаем
1
±
i
√
3
6
n
=
1
3
n
e
±
in
/
3
=
1
3
n
cos
n
3
±
i sin
n
3
и
p
(n)
ij
= +
1
3
n
cos
n
3
+
sin
n
3
,
где
=
A,
=
B
+
C и
=
i(B
−
C) должны быть действительными. Снова
получаем уравнения для n
=
0, 1, 2; для p
(n)
12
они имеют вид
+ =
0,
+
1
3
1
2
+
√
3
2
=
1,
+
1
9
−
1
2
+
√
3
2
=
2
3
,
§ 1.1. Марковское свойство и немедленные следствия из него 21
откуда следует, что
=
3
7
,
=
−
3
7
,
=
9
7
√
3.
В частности, lim
n
→∞
p
(n)
12
=
3
/
7.
Пример 1.1.9. Рассмотрим другой пример матрицы, соответствующей
системе с тремя состояниями:
P
=
1
/
3 0 2
/
3
1
/
3 2
/
3 0
1
/
3 1
/
3 1
/
3
!
.
Теперь характеристическое уравнение имеет вид
−
3
+
4
3
2
−
1
3
= −
(
−
1)
−
1
3
=
0
и собственные числа равны
0
=
1,
1
=
1
3
,
2
=
0.
Значит, элементы p
(n)
ij
имеют простой вид
p
(n)
ij
=
A
+
B
1
3
n
+
C
·
0
n
.
Вновь используем три начальные условия, т. е. матрицы P
0
, P и P
2
(как
обычно, считаем, что 0
0
=
1). Например, p
(n)
11
ищется из соотношений
A
+
B
+
C
=
1, A
+
1
3
B
=
1
3
, A
+
1
3
2
B
=
1
3
,
откуда получаем A
=
1
/
3, B
=
0, C
=
2
/
3 и p
(n)
11
≡
1
/
3, n
>
1. Аналогично
p
(n)
12
=
1
/
3
−
(1
/
3)
n
и p
(n)
13
=
1
/
3
+
(1
/
3)
n
. При n
→ ∞
все элементы первой
строки матрицы P
n
стремятся к 1
/
3 (что на самом деле верно для всех
девяти элементов матрицы P
n
).
Пример 1.1.10. Сделаем ряд предварительных замечаний. Во
-
первых,
1
—
собственное число любой стохастической матрицы P. Действительно,
пусть I
—
единичная матрица, т. е. элементы матрицы I равны
ij
, i, j
∈
I.
Тогда а) det(
I
−
P)
=
det( I
−
P)
T
=
det( I
−
P
T
), т. е. собственные числа
матрицы P и транспонированной матрицы P
T
совпадают; и б) 1
—
всегда
является собственным числом матрицы P
T
: соответствующий собственный
22 Глава 1. Цепи Маркова с дискретным временем
вектор
—
это строка 1
=
(1, . . . , 1) из единиц. Формально 1P
T
=
1, или,
что эквивалентно, P1
T
=
1
T
для столбца 1
T
. Чтобы проверить последнее
равенство, заметим, что каждый элемент столбца P1
T
равен 1:
(P1
T
)
i
=
X
j
∈
I
p
ij
=
1,
поскольку матрица P стохастическая.
Следовательно, характеристический многочлен стохастической матри
-
цы делится на
−
1; в случае размера 3
×
3 частное является квадратным
трехчленом, значит, все собственные числа можно найти явно.
Во
-
вторых, если
+
—
комплексное собственное число матрицы P, то
сопряженное комплексное число
−
=
+
также является собственным
значением, поскольку только это дает возможность получить действитель
-
ный характеристический многочлен как произведение линейных одночле
-
нов (имеется в виду произведение (
−
+
) (
−
−
)
=
2
−
(
+
+
−
)
+
+ −
с действительными коэффициентами
+
+
−
и
+ −
= |
±
|
2
). Используя
запись
±
= |
±
|
e
±
i
ϕ
= |
±
|
(cos
ϕ ±
i sin
ϕ
),
можно работать только с действительными слагаемыми вида
cos(n
ϕ
)
и sin(n
ϕ
).
В
-
третьих, коэффициент A перед единицей в уравнении для p
(n)
ij
, как
правило, определяет предел lim
n
→∞
p
(n)
ij
. Это следует из того, что
| | 6
1 для
всех собственных чисел
матрицы P и,
«
как правило
»
(хотя и не всегда),
любое собственное число
6=
1 по модулю меньше 1,
| | <
1. Это более
тонкий факт, к нему мы еще вернемся в последующих параграфах. Поэтому
в разложении
p
(n)
ij
=
A
+
X
собственные
числа
s
6=
1
B
s
n
s
все члены, кроме A, исчезают при n
→ ∞
. (В случае P
=
0 1
1 0
это
неверно: собственные числа равны 1, и
−
1 и предел lim
n
→∞
p
(n)
ij
не существует,
так как P
n
осциллирует между I для четных n и P для нечетных n.)
Необходимо отметить, что многие (даже очень простые) примеры могут
привести к достаточно громоздким формулам для p
(n)
ij
. Например, матрице
P
=
1
/
3 1
/
3 1
/
3
0 1
/
2 1
/
2
1
/
3 2
/
3 0
!
§ 1.1. Марковское свойство и немедленные следствия из него 23
соответствует характеристическое уравнение
−
3
+
5
6
2
+
5
18
−
1
9
= −
(
−
1)
2
+
1
6
−
1
9
=
0
с собственными числами
0
=
1,
±
=
−
1
±
√
17
12
.
Отсюда получаем уравнение
p
(n)
ij
=
A
+
B
−
1
+
√
17
12
n
+
C
−
1
−
√
17
12
n
,
где
A
+
B
+
C
=
ij
, A
+
B
−
1
+
√
17
12
+
−
1
+
√
17
12
=
p
ij
и
A
+
B
−
1
+
√
17
12
2
+
C
−
1
−
√
17
12
2
=
p
(2)
ij
.
Например, окончательное выражение для p
(n)
21
имеет вид
4
19
+
2
19
6
√
17
−
1
−
1
+
√
17
12
n
−
2
19
6
√
17
+
1
−
1
−
√
17
12
n
.
Рис. 1.3
Пример 1.1.11. Полезным свойством является наличие симметрии
в матрице P: оно может сократить число состояний исходной цепи Мар
-
кова. Например, матрица N
×
N вида
P
=
1
−
/
(N
−
1) . . .
/
(N
−
1)
/
(N
−
1) 1
−
. . .
/
(N
−
1)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
/
(N
−
1)
/
(N
−
1) . . . 1
−
описывает модель мутации вируса, в которой вирус либо сохраняет свой
тип, либо меняет его на любой другой тип с одинаковыми в этом случае
вероятностями (типы
—
это 1, . . . N).
24 Глава 1. Цепи Маркова с дискретным временем
Чтобы вычислить p
(n)
11
, сведем число состояний к двум (к примеру 1 и 0),
рассматривая переходы из состояния 1 в него же или в другое состояние
и обратно, без дальнейшей детализации (поскольку для полной постановки
задачи все остальные состояния неразличимы). Приведенная цепь с двумя
состояниями имеет матрицу перехода 2
×
2
1
−
/
(N
−
1) 1
−
/
(N
−
1)
.
Теперь можно применить формулы из примера 1.1.7 (с
=
/
(N
−
1)):
p
(n)
11
=
/
(N
−
1)
+
/
(N
−
1)
+
+
/
(N
−
1)
1
− −
N
−
1
n
=
=
1
N
+
N
−
1
N
1
−
N
N
−
1
n
.
Кроме того, в силу симметрии
p
(n)
ij
=
1
−
p
(n)
11
N
−
1
∀
i
6=
j.
Теперь пора установить знаменитое марковское свойство для ц.м.д.в.
Оно состоит в том, что цепь Маркова стартует заново после любого за
-
данного момента времени n.
Теорема 1.1.12. Пусть (X
n
)
—
цепь Маркова с параметрами ( , P).
Тогда,
∀
m
>
1 и i
∈
I при условии, что X
m
=
i, процесс (X
m
+
n
, n
>
0)
—
цепь Маркова с параметрами (
i
, P). В частности, при условии, что
X
m
=
i, случайные величины X
m
+
1
, X
m
+
2
, . . . не зависят от величин
X
0
, . . . , X
m
−
1
.
Иными словами, в ц.м.д.в. прошлое (X
0
, . . . , X
m
−
1
) и будущее
(X
m
+
1
, X
m
+
2
, . . .) условно независимы при фиксированном настоящем
(X
m
=
i).
Д о к а з а т е л ь с т в о. Напомним, что стохастический вектор
i
состо
-
ит из элементов
ij
, j
∈
I. Нужно проверить, что для любого события
A, определяемого величинами X
0
, . . . , X
m
−
1
, и события B, определяемого
величинами X
m
+
1
, . . . , X
m
+
1
+
n
, для некоторого n, имеют место следующие
утверждения: а) условная вероятность P (A
∩
B
|
X
m
=
i) представляется
в виде произведения
P (A
∩
B
|
X
m
=
i)
=
P (A
|
X
m
=
i) P (B
|
X
m
=
i), (1.1.10)
и б) условная вероятность P (B
|
X
m
=
i) вычисляется, как в (
i
, P)
-
ц.м.д.в.:
P (B
|
X
m
=
i)
=
X
(j
1
,...,j
n
)
∈
B
p
ij
1
. . . p
j
n
−
1
j
n
. (1.1.11)
§ 1.1. Марковское свойство и немедленные следствия из него 25
Пусть вначале A и B имеют вид
A
= {
X
0
=
i
0
, . . . , X
m
−
1
=
i
m
−
1
}
, B
= {
X
m
+
1
=
j
1
, . . . , X
m
+
n
+
1
=
j
n
}
для некоторой последовательности состояний i
0
, . . . , i
m
−
1
, j
1
, . . . , j
n
∈
I.
Произвольные события A и B являются объединениями таких непересе
-
кающихся
«
элементарных
»
событий.
Для событий A и B указанного вида выполняются соотношения
P (A
∩
B
∩ {
X
m
=
i
}
)
=
=
P (X
0
=
i
0
, . . . , X
m
−
1
=
i
m
−
1
, X
m
=
i, X
m
+
1
=
j
1
, . . . , X
m
+
n
+
1
=
j
n
)
=
=
i
0
p
i
0
i
1
. . . p
i
m
−
1
i
p
ij
1
. . . p
j
n
−
1
j
n
.
Для произвольного B нужно взять сумму по всем (j
1
, . . . , j
n
)
∈
B:
i
0
p
i
0
i
1
. . . p
i
m
−
1
i
X
(j
1
,...,j
n
)
∈
B
p
ij
1
. . . p
j
n
−
1
j
n
.
Сумма
P
(j
1
,...,j
n
)
∈
B
дает условную вероятность P (B
|
X
m
=
i), значит, эта
вероятность действительно вычисляется так же, как в (
i
, P)
-
ц.м.д.в.
Далее, для произвольного события A просуммируем по (i
0
, . . . , i
m
−
1
)
∈
A:
P (A
∩
B
∩ {
X
m
=
i
}
)
=
X
(i
0
,...,i
m
−
1
)
∈
A
i
0
p
i
0
i
1
. . . p
i
m
−
1
i
P (B
|
X
m
=
i)
=
=
P (A
∩ {
X
m
=
i
}
) P (B
|
X
m
=
i).
Наконец, для вычисления условной вероятности P (A
∩
B
|
X
m
=
i) разделим
на P (X
m
=
i):
P (A
∩
B
|
X
m
=
i)
=
P (A
∩
B
∩ {
X
m
=
i
}
)
P (X
m
=
i)
=
=
P (A
∩ {
X
m
=
i
}
)
P (X
m
=
i)
P (B
|
X
m
=
i)
=
P (A
|
X
m
=
i) P (B
|
X
m
=
i),
что и требовалось доказать.
В дальнейшем будем обозначать через P
i
условные вероятности
P (
· |
X
0
=
i), взятые при условии, что состояние системы в момент времени
0 есть i.
Пример 1.1.13. Три девочки A, B и C играют в настольный теннис.
В каждой игре две девочки играют друг против друга, а третья отдыхает.
Победитель любой фиксированной n
-
й игры снова играет в (n
+
1)
-
й игре.
26 Глава 1. Цепи Маркова с дискретным временем
Вероятность того, что девочка x победит девочку y в любой игре, в которой
они играют друг против друга, равна s
x
/
(s
x
+
s
y
) для x, y
∈ {
A, B, C
}
, x
6=
6=
y, где s
A
, s
B
, s
C
соответствуют игровым навыкам этих трех девочек.
a) Представьте этот процесс в виде ц.м.д.в., определив пространство
возможных состояний и переходные вероятности.
б) Найдите вероятность того, что те же две девочки, которые играли
друг против друга в первой игре, будут опять играть друг против друга
в четвертой игре. Покажите, что эта вероятность не зависит от того, какие
именно две девочки участвовали в первой игре.
Решение. a) Промаркируем состояния буквами A, B, C, определя
-
ющими, какая из девочек не участвует в заданной игре. Тогда матрица
переходных вероятностей для
{
A, B, C
} × {
A, B, C
}
имеет вид
0
s
C
s
B
+
s
C
s
B
s
B
+
s
C
s
C
s
A
+
s
C
0
s
A
s
A
+
s
C
s
B
s
A
+
s
B
s
A
s
A
+
s
B
0
.
Этот процесс является цепью Маркова, потому что результаты последо
-
вательных игр независимы.
б) Сейчас мы ищем вероятность того, что за три шага цепь вернется
в заданное начальное состояние. См. рис. 1.4.
Рис. 1.4
В силу симметрии эта вероятность одинакова для любого начального
состояния и равна
p
(3)
AA
=
p
AB
p
BC
p
CA
+
p
AC
p
CB
p
BA
=
2s
A
s
B
s
C
(s
A
+
s
B
) (s
B
+
s
C
) (s
C
+
s
A
)
.
Пример 1.1.14. Рок
-
концерт, проводящийся в холле с N нумерован
-
ными местами, привлёк огромную толпу зрителей. Свет потушен, N
−
1
место уже занято и последний зритель заходит в зал. Первым N
−
1 зри
-
телям распорядитель довольно легкомысленно посоветовал занять места
случайным образом, но последний зритель настаивает на том, чтобы занять
§ 1.1. Марковское свойство и немедленные следствия из него 27
место, указанное в его билете. Если это место свободно, он занимает его,
и концерт начинается. Однако если это место занято, зритель настаивает,
чтобы место было освобождено. В этом случае зритель, освободивший
место, решает поступать точно также: если свободное место соответствует
его билету, он его занимает; в противном случае он настаивает, чтобы его
место освободили. Ту же политику применяет и следующий неудачливый
зритель и т. д. Каждое перемещение занимает 45 секунд. Какова ожидаемая
задержка начала концерта, вызванная этими перемещениями.
Решение (набросок). Здесь важно иметь в виду, что первоначаль
-
но N
−
1 зритель распределен так, что а) вероятность того, что место j
свободно, равна 1
/
N, j
=
1, . . . , N; б) при условии, что место j свободно,
вероятность того, что первый зритель, вошедший в зал, займет место i
1
,
второй займет место i
2
, . . ., (N
−
1)
-
й займет место i
N
−
1
, равна 1
/
(N
−
1)!,
для любой последовательности i
1
, . . ., i
N
−
1
из множества
{
1, . . . , N
}\{
j
}
.
Рассмотрим ц.м.д.в. с состояниями N, N
−
1, . . ., 0. Здесь состояние 0
обозначает, что зритель, пришедший последним, увидит свое место сво
-
бодным, состояние n, 1
6
n
6
N
−
1, означает, что (N
−
n)
-
е передвижение
было
«
неудачным
»
, и N
—
начальное состояние системы. Тогда вероят
-
ность перехода из состояния n в 0 равна 1
/
n и вероятность перехода из n
в n
−
1 равна (n
−
1)
/
n; вероятность перехода из 0 в 0 равна 1. Пусть E(n)
обозначает ожидаемое число переходов (перемещений) до того момента,
как ц.м.д.в. попадет в состояние 0 из состояния n; нас интересует E(N).
Полезное замечание: E(n) равно ожидаемому числу перемещений в зале
с n местами.
Ключевым в решении задачи является рекуррентное соотношение:
E(n)
=
n
−
1
n
·
[1
+
E(n
−
1)]
+
1
n
·
0
=
n
−
1
n
[1
+
E(n
−
1)], n
=
1, 2, . . . ,
где
E(1)
=
0.
Отсюда следует, что
E(n)
=
1
n
(n
−
1
+
n
−
2
+
. . .
+
1)
=
n
−
1
2
.
Если N
=
121 (размер небольшого зала), то ожидаемое время задержки
45
·
120
2
=
45 мин.
Пример 1.1.15. Мораль следующей задачи составляет то, что часто
полезно ввести вероятности даже там, где изначально их не было. Пред
-
положим, что окружность единичной длины
C
1
=
n
z:
|
z
| =
1
2
o
разбита
на два непересекающихся измеримых множества, одно из них, называемое
28 Глава 1. Цепи Маркова с дискретным временем
красным, имеет общую длину 2
/
3, а другое, голубое, длину 1
/
3. Докажите,
что всегда можно вписать в окружность квадрат так, что по меньшей мере
три из его четырех вершин будут красными.
Решение. При заданном разбиении рассмотрим квадрат, вписанный
случайным образом, причем одна из вершин распределена на
C
1
равномер
-
но; это единственным образом определяет квадрат. Пронумеруем вершины
1, 2, 3, 4, например, по часовой стрелке, начиная с той первой, которая
распределена равномерно. Положим
X
i
=
1(вершина i попала в красное множество), i
=
1, 2, 3, 4.
Тогда
E (числа красных вершин)
=
EX
1
+
EX
2
+
EX
3
+
EX
4
=
4 EX
1
=
8
/
3
>
2.
Таким образом, сумма X
1
+
X
2
+
X
3
+
X
4
принимает значения 3 или 4
с положительной вероятностью, значит, всегда можно вписать квадрат так,
как указано в задаче.
На самом деле можно оценить вероятность P того, что по меньшей
мере три из четырех вершин будут красными. Действительно, имеет место
оценка: P
>
P
0
, где P
0
=
1
3
есть корень уравнения
(1
−
P
0
)2
+
4P
0
=
8
3
,
которое соответствует ситуации, когда с вероятностью P
0
имеется четыре
красные вершины, а с дополнительной вероятностью 1
−
P
0
в точности
две.
Завершая данный параграф, мы хотели бы отметить, что в определении
1.1.3 мы ввели класс так называемых однородных, или однородных
во времени, цепей Маркова. Мы будем опускать термин
«
однородный
»
,
кроме нескольких случаев, когда мы рассматриваем
«
неоднородные
»
цепи
(что имеет место для цепей Маркова с непрерывным временем, см. § 2.4).
Отметим только, что в неоднородной цепи Маркова переходная вероят
-
ность из состояния i в j зависит от времени перехода. Следовательно,
вместо одной переходной матрицы P мы будем рассматривать семейство
матриц P
n
, n
=
0, 1, 2, . . ., которое описывает вероятности переходов из
состояния i, в котором цепь находится в момент времени n, в состояние j
в момент времени n
+
1.
§ 1.2. Разбиение состояний на классы 29
§ 1.2. Разбиение состояний на классы
Борьба сообщающихся классов
(Из серии
«
Кое
-
что из политики
»
.)
Разбиение на классы
—
это естественное разбиение пространства со
-
стояний I, порожденное матрицей перехода P. Если не оговорено заранее,
мы имеем в виду, что пространство состояний и соответствующая матрица
конечны.
Определение 1.2.1. Говорят, что состояния i и j принадлежат к одному
сообщающемуся классу, если p
(n
1
)
ij
>
0 и p
(n
2
)
ji
>
0 для некоторых n
1
, n
2
>
>
0 (Напомним, что если n
=
0, то P
0
—
единичная матрица I.) Этот
факт обозначается i
↔
j. Если выполняется одно из этих условий, то
пишем i
→
j или j
→
i, а если мы хотим подчеркнуть, что одно из них не
выполняется, то мы будем обозначать это как i
6→
j или j
6→
i.
Чтобы проверить, что это разбиение корректно определено, заметим,
что а) каждое состояние сообщается с самим собой (i
↔
i, так как p
(0)
ii
=
1),
б) соотношение i
↔
j симметрично, т. е. выполняется или не выполняется
независимо от порядка внутри пары i, j (что очевидно из определения);
в) если i
↔
j и j
↔
k, то i
↔
k (так как p
(n
1
+
n
2
)
ik
=
P
l
∈
I
p
(n
1
)
il
p
(n
2
)
lk
>
p
(n
1
)
ij
p
(n
2
)
jk
и аналогичные оценки верны для p
(n
1
+
n
2
)
ki
). Тогда в силу а) каждое состояние
попадает в некоторый класс, в силу б) каждый класс корректно определен
как (неупорядоченное) подмножество I, а в силу в) каждое состояние
попадает не более чем в один класс. Состояния из разных классов, конечно,
не сообщаются.
Полезно иметь в виду, что i
→
j тогда и только тогда, когда существует
последовательность таких состояний
i
0
=
i, i
1
, . . . , i
n
−
1
, i
n
=
j,
что p
i
l
i
l
+
1
>
0 для любой пары (i
l
, i
l
+
1
), 0
6
l
<
n. Действительно, p
(n)
ij
=
=
P
i
1
,...i
n
−
1
p
ii
1
. . . p
i
n
−
1
j
и вся сумма положительна тогда и только тогда, когда
по крайней мере одно слагаемое положительно.
Определение 1.2.2. Класс сообщающихся состояний (класс экви
-
валентности, сообщающийся класс) C называют замкнутым, если для
любых таких i
∈
C и j
∈
I, что i
→
j, состояние j принадлежит C. Иначе
говоря, невозможно выйти из замкнутого класса. Если состояние (или все
состояния, что то же самое) выводит из класса, то такой класс называется
незамкнутым. Состояния, образующие незамкнутые классы эквивалентно
-
30 Глава 1. Цепи Маркова с дискретным временем
сти; часто называют несущественными, они и в самом деле несущественны
с точки зрения асимптотического поведения цепи. Состояние i называется
поглощающим, если p
ii
=
1. Это эквивалентно тому, что сообщающий
-
ся класс поглощающего состояния i состоит только из этого состояния
и является замкнутым.
Цепь Маркова называется неприводимой, если все ее состояния обра
-
зуют один класс сообщающихся состояний (который в этом случае должен
быть замкнутым). Изучение цепи, имеющей более одного класса сообщаю
-
щихся состояний, по сути сводится к изучению ее
«
сужений
»
на различные
классы.
Новый факт, доказанный мною, ... состоит
в том, что классовая борьба неизбежно
ведет к диктатуре пролетариата.
К. Маркс (1818
–
1883), немецкий философ
Пример 1.2.3. Пусть частица переходит из состояния i
=
1, . . . , N
−
1
в состояние i
+
1 с вероятностью p, а в состояние i
−
1 с вероятностью 1
−
p,
где 0
<
p
<
1. Из состояний 0 и N невозможны переходы ни в одно другое
состояние, т. е. достигнув однажды состояния 0 или N, частица останется
там навсегда. Этот пример описывает матч двух игроков, когда в каждой
игре проигравший выплачивает победителю одну единицу (
«
очко
»
) и матч
продолжается до тех пор, пока один из игроков не проиграет все свои очки.
Другой интерпретацией является блуждание пьяного, который, выходя из
пивной (паба), делает шаги либо в сторону дома (дом
—
это состояние 0),
либо в сторону озера (озеро
—
это состояние N). В первом случае значение
N
—
это общее число очков у обоих игроков перед началом поединка;
вполне очевидно, что оно сохраняется неизменным в ходе игры. Во втором
случае N
—
это расстояние (число шагов) между домом и озером (паб нахо
-
дится где
-
то между домом и озером). Каждое состояние i
=
0, 1, . . . , N
—
это число очков у первого игрока или расстояние от дома; p и 1
−
p
—
вероятности выигрыша и проигрыша первого игрока в каждой игре или
вероятности сделать шаг в сторону дома или озера соответственно. Ре
-
зультаты игр являются независимыми, так же как и направления движения
на каждом шаге.
§ 1.2. Разбиение состояний на классы 31
Здесь матрица перехода является (N
+
1)
×
(N
+
1)
-
матрицей вида
P
=
1 0 0 0 . . . 0 0 0
1
−
p 0 p 0 . . . 0 0 0
0 1
−
p 0 p . . . 0 0 0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
0 0 0 0 . . . 0 p 0
0 0 0 0 . . . 1
−
p 0 p
0 0 0 0 . . . 0 0 1
,
см. рис. 1.5. Сообщающимися классами являются классы
{
0
}
,
{
1, . . .
. . . , N
−
1
}
и
{
N
}
, классы
{
0
}
и
{
N
}
замкнуты (т. е. состояния 0 и N явля
-
ются поглощающими). Таким образом, состояния 1, . . . , N
−
1 являются
несущественными, и игра обязательно закончится в одном из граничных
состояний.
Рис. 1.5
Пример 1.2.4. Рассмотрим (6
×
6)
-
матрицу перехода на множестве
состояний
{
1, 2, 3, 4, 5, 6
}
следующего вида:
P
=
∗
0 0 0
∗
0
0 0
∗
0 0 0
0 0
∗
0 0
∗
0
∗
0 0
∗
0
∗
0 0 0 0
∗
0
∗
0 0 0 0
,
где символ
∗
обозначает ненулевой элемент, см. рис. 1.6. Сообщающимися
классами являются классы C
1
= {
1, 5
}
, C
2
= {
2, 3, 6
}
и C
3
= {
4
}
, из
которых лишь класс C
2
замкнут. Стрелки между классами показывают
динамику цепи. Если мы стартуем из класса C
2
, то остаемся в C
2
навсегда.
Если мы стартуем из C
3
(т. е. из состояния 4), то попадаем либо в C
2
(и тогда остаемся в C
2
навсегда), либо в C
1
. Интуиция подсказывает,
что, проведя некоторое время в C
1
, мы должны покинуть этот класс,
т. е. перейти в C
2
. В действительности так и происходит, как мы вскоре
увидим.
Приведем простой, но полезный факт.
Теорема 1.2.5. Цепь Маркова с конечным пространством состоя-
ний всегда имеет хотя бы один замкнутый сообщающийся класс.
32 Глава 1. Цепи Маркова с дискретным временем
Рис. 1.6
Чтобы доказать это, рассмотрим любой класс, скажем C
1
. Если этот
класс незамкнут, возьмем следующий класс, достижимый из C
1
. Если
и этот класс незамкнут, будем продолжать этот процесс. В конце концов
мы достигнем замкнутого класса.
Замечание 1.2.6. Случай счетной цепи Маркова со счетным про
-
странством состояний I более сложен. Здесь может не существовать ни
одного замкнутого класса. Вдобавок в бесконечном замкнутом классе
могут также быть
«
несущественные
»
состояния, в том смысле, что цепь
может побывать в каждом из таких состояний только конечное число раз,
а затем уйти в
«
бесконечность
»
(хотя все еще может оставаться в этом же
замкнутом классе).
Рис. 1.7
Самыми простыми являются примеры, когда пространство состояний
I представляет собой множество неотрицательных целых чисел
Z
+
=
= {
0, 1, 2, . . .
}
. Три примера показаны на рис. 1.7; соответствующие
§ 1.2. Разбиение состояний на классы 33
матрицы перехода таковы:
a)
0 1 0 0 . . . 0 . . .
0 0 1 0 . . . 0 . . .
0 0 0 1 . . . 0 . . .
. . . . . . . . . . . . . . . . . . .
, б)
0 1 0 0 . . . 0 . . .
1
−
p 0 p 0 . . . 0 . . .
0 1
−
p 0 p . . . 0 . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
и
в)
0 1 0 0 . . . 0 . . .
1
−
p
1
0 p
1
0 . . . 0 . . .
0 1
−
p
2
0 p
2
. . . 0 . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
Эти примеры описывают так называемые процессы рождения и ги-
бели, когда состояние i представляет собой размер популяции, а при
переходе к следующему состоянию может умереть одна особь или может
появиться одна особь. В случае а) допускаются только переходы в сторону
увеличения популяции и цепь является детерминированной. Здесь каж
-
дое состояние i образует незамкнутый класс и является несущественным.
В модели б)
«
смерть
»
особи происходит с одной и той же вероятностью
1
−
p, а рождение
—
с вероятностью p, независимо от размера популяции
i в данный момент времени (если только, конечно, i не равно 0). Приме
-
ром такого процесса может служить очередь
«
заданий
»
, обслуживаемых
некоторой системой (например, клиенты, ожидающие своей очереди в па
-
рикмахерской, в которой имеется лишь одно кресло для обслуживания,
либо компьютерные программы, последовательно выполняемые процессо
-
ром). Тогда i
—
это число заданий в очереди. Если до того момента, когда
парикмахер закончит обслуживание текущего клиента, приходит новый
клиент, то имеем скачок i
→
i
+
1; в противном случае имеем скачок
i
→
i
−
1; из состояния 0 возможен лишь скачок в состояние 1 (хотя
в действительности парикмахер может ожидать некоторое время, пока
появится первый клиент). Возможны два случая: p
>
1
/
2 и 0
<
p
<
1
/
2.
Интуитивно ясно, что если p
>
1
/
2, то задания поступают по крайней мере
с такой же частотой, с какой происходит их обслуживание, и очередь может
превратиться в бесконечную (что, конечно, доставит удовольствие нашему
парикмахеру). В этом случае, как мы далее увидим, каждое состояние i
будет посещаться цепью лишь конечное число раз и X
n
(размер очереди
в момент времени n) будет бесконечно расти с ростом n. Если 0
<
p
<
<
1
/
2, то задания будут поступать не так часто и система сможет достичь
«
равновесия
»
с некоторым стационарным распределением длины очереди.
Часто используется модификация примера б), когда состояние 0 пола
-
гают поглощающим с вероятностью p
00
=
1.
В более общем случае в) правила динамики популяции таковы, что для
каждой особи существует шанс погибнуть (но только для одного в каждый
34 Глава 1. Цепи Маркова с дискретным временем
момент времени); например p
n
=
/
(
+
n ), 1
−
p
n
=
n
/
(
+
n ), где
>
0 и
>
0
—
«
интенсивности
» «
миграции
»
и смерти; общая картина
становится более сложной. В дальнейшем мы обстоятельно проанализи
-
руем некоторые из этих моделей в § 1.5
–
1.7.
Рис. 1.8
Вернемся к цепям Маркова с конечным числом состояний. В общем
случае если перенумеровать состояния, то матрица перехода P с конечным
числом элементов приобретает некоторую структуру, см. рис. 1.8. Обыч
-
но в левом верхнем углу размещают квадратный блок O
0
, состоящий из
вероятностей возможных переходов между несущественными состояниями
(т. е. между и внутри незамкнутых сообщающихся классов). Этот блок мо
-
жет быть нулевым, если таковых переходов нет. Далее, квадратные блоки
C
1
, . . . , C
m
размещены на главной диагонали. Эти блоки представляют
замкнутые сообщающиеся классы различных размеров; они образуют сто
-
хастические подматрицы. Последнее означает, что для любых i
=
1, . . . , m
и любых состояний j
∈
C
i
сумма
P
k
∈
C
i
p
jk
элементов матрицы внутри класса
C
i
вдоль строки j равна 1. Цепи Маркова, соответствующие блокам C
1
,
. . . , C
m
, могут изучаться по отдельности (что проще сделать ввиду их
меньшего размера). Блоки O
1
, . . . , O
m
с правой стороны от O
0
—
это
неотрицательные прямоугольные матрицы; некоторые из них (но не все)
могут быть нулевыми. (Конечно, суммы элементов каждой строки матрицы
P всегда равны 1.) Если матрица не имеет несущественных состояний, то
блоки O
0
, O
1
, . . . , O
m
могут просто отсутствовать.
Пространство между блоками O
0
, O
1
, . . . , O
m
и C
1
, . . . , C
m
заполнено
нулями. (Внутри матриц также может быть много нулей, см. ниже.)
§ 1.2. Разбиение состояний на классы 35
Рис. 1.9
Мы будем называть конечную ц.м.д.в. (X
n
) (или, что то же самое, ее
переходную матрицу P) неприводимой, если она состоит из единственного
сообщающегося класса C (который автоматически является замкнутым).
Иными словами, конечная переходная матрица неприводима, если каждая
пара состояний i, j
∈
I сообщается, а все множество состояний образует
один замкнутый класс I
=
C. Графически в этом случае матрица P сводится
к блоку C, см. рис. 1.9 а). Отличительной особенностью здесь является то,
что для любой пары состояний i, j
∈
I элементы p
(n)
ij
матрицы P
n
(т. е.
переходные вероятности из состояния i в состояние j за n шагов) строго
больше 0 для некоторого n
>
1 (которое, как правило, зависит от i и j).
Некоторые авторы рассматривают более сложную ситуацию и гово
-
рят, что ц.м.д.в. неприводима, если она обладает единственным замкнутым
сообщающимся классом и несколькими незамкнутыми классами. В этом
случае конечная цепь имеет единственное инвариантное, или стационар
-
ное, распределение, см. ниже. Соответствующая матрица приведена на
рис. 1.9 б): имеется один квадратный блок C, который составляет стоха
-
стическую подматрицу, плюс квадратный блок O
0
в верхнем левом углу,
и отдельный прямоугольный блок O
1
, или просто O. При итерации такой
матрицы P, т. е. при возведении ее во все более высокую степень n, блок
O
0
будет стремиться к 0 при n
→ ∞
. Поведение блока O более сложно:
мы проанализируем его позднее. Что же касается блока C, то он просто
будет возводиться в степень n (что удобно).
Приведенные выше рассуждения наталкивают на мысль, что будет
происходить при итерации конечной переходной матрицы P с несколькими
замкнутыми сообщающимися классами. Как и ранее, блок O
0
матрицы
P
n
будет стремиться к 0 при n
→ ∞
. Как и ранее, блоки C
1
, . . . , C
m
36 Глава 1. Цепи Маркова с дискретным временем
матрицы P
n
будут просто возводиться в степень n. Последнее замечание
иллюстрирует тот факт, что приводимую цепь, содержащую более чем
один класс, можно изучать, рассматривая отдельно каждый из классов.
Для простоты предположим, что конечная матрица P неприводима.
Нетрудно догадаться, что внутри блока C у нас может быть периодиче
-
ская структура, содержащая v клеток меньшей (одинаковой) размерности,
циклически перемещаемых матрицей P: клетка 1
«
переходит
»
в клетку 2,
и т. д., клетка v переходит в клетку 1, см. рис. 1.10. Пространство вне
клеток снова заполнено нулями.
Рис. 1.10
Эта картина соответствует разбиению пространства I (которое, по
нашему предположению, составляет отдельный (и замкнутый) сообщаю
-
щийся класс) на такие периодические подклассы W
1
, . . . , W
v
, что переход
за один шаг возможен только из состояния j
∈
W
i
в состояние k
∈
W
i
+
1
,
i
=
1, . . . , v. (Здесь сумму i
+
1 следует понимать как сумму по модулю v,
так что W
v
+
1
=
W
1
). Число v называется периодом класса C.
В большинстве наших примеров период замкнутого сообщающегося
класса равен единице, т. е. класс состоит из одной клетки. Такие классы
(или, что то же самое, их переходные матрицы) называются апериодиче-
скими.
Вообще говоря, если возвести переходную матрицу P, соответствую
-
щую замкнутому сообщающемуся классу C с периодом v, в степень v,
то матрицу P
v
можно разбить на квадратные стохастические подматрицы,
расположенные на главной диагонали. Образно говоря, периодические
подклассы W
1
, . . . , W
v
играют роль замкнутых сообщающихся классов для
матрицы P
v
. (Нужно, правда, отметить, что формально такое утверждение
неверно: некоторые из подклассов W
i
могут состоять из нескольких непе
-
ресекающихся замкнутых сообщающихся классов матрицы P
v
.)
Мы увидим, что полная структура конечной переходной матрицы P
§ 1.2. Разбиение состояний на классы 37
может быть достаточно сложной. К счастью, большинство приложений
и интересных примеров не требуют большой степени общности, и нам
удастся сделать упрощающие предположения.
Пример 1.2.7. Рассмотрим стохастическую 7
×
7 матрицу
P
=
0 1
/
2 0 0 0 0 1
/
2
1
/
3 0 0 0 0 1
/
3 1
/
3
0 1
/
2 0 1
/
2 0 0 0
0 0 0 0 1 0 0
0 0 0 1 0 0 0
0 1
/
2 0 0 0 0 1
/
2
1
/
3 1
/
3 0 0 0 1
/
3 0
.
Найдите все сообщающиеся классы соответствующей ц.м.д.в.
Рис. 1.11
Решение. См. рис. 1.11. Сообщающимися классами являются
{
1, 2, 6, 7
}
,
{
3
}
и
{
4, 5
}
. Замкнутые классы
—
{
1, 2, 6, 7
}
и
{
4, 5
}
;
состояние 3 является несущественным. Класс
{
4, 5
}
имеет периодическую
структуру. Следовательно, предел величины p
(n)
ij
не существует (она
осциллирует) при i
=
3, 4, 5 и j
=
4, 5. Для класса
{
1, 2, 6, 7
}
подматрица
перехода имеет вид
0 1
/
2 0 1
/
2
1
/
3 0 1
/
3 1
/
3
0 1
/
2 0 1
/
2
1
/
3 1
/
3 1
/
3 0
и обладает симметрией 1
↔
6 и 2
↔
7. Таким образом, если объединить
состояния 1 и 6 в (новое) состояние I, а состояния 2 и 7 объединить
в состояние II, то получим цепь с двумя состояниями и матрицей перехода
Π =
0 1
2
/
3 1
/
3
.
38 Глава 1. Цепи Маркова с дискретным временем
Характеристическое уравнение для последней матрицы имеет вид
2
−
1
3
−
2
3
=
0,
корни этого уравнения равны
0
=
1,
1
= −
2
/
3. Следовательно, элементы
Π
n
имеют вид A
+
B(
−
2
/
3)
n
. Подобрав должным образом постоянные,
получаем
Π
n
=
2
/
5
+
3
/
5(
−
2
/
3)
n
3
/
5
−
3
/
5(
−
2
/
3)
n
2
/
5
−
2
/
5(
−
2
/
3)
n
3
/
5
+
2
/
5(
−
2
/
3)
n
.
Таким образом,
Π
n
→
2
/
5 3
/
5
2
/
5 3
/
5
.
Тогда в силу симметрии для первоначального блока
{
1, 2, 6, 7
}
предельной
будет матрица
1
/
5 3
/
10 1
/
5 3
/
10
1
/
5 3
/
10 1
/
5 3
/
10
1
/
5 3
/
10 1
/
5 3
/
10
1
/
5 3
/
10 1
/
5 3
/
10
,
т. е. p
(n)
i1
, p
(n)
i6
→
1
/
5 и p
(n)
i2
, p
(n)
i7
→
3
/
10, i
=
1, 2, 6, 7. Вероятности p
(n)
3j
стремятся к
1
2
lim
n
→∞
p
(n)
2j
, j
=
1, 2, 6, 7.
Следует подчеркнуть, что такой способ вычисления пределов
lim
n
→∞
p
(n)
ij
не является оптимальным. В дальнейшем мы познакомимся
с намного более эффективными способами.
§ 1.3. Времена и вероятности достижения
A hit, a very palpable hit. (Гамлет)
В. Шекспир (1546
–
1616), английский драматург и поэт
Напомним, что через P
i
обозначается распределение ц.м.д.в. (X
n
), ко
-
торая выходит из состояния i
∈
I. Аналогично будем обозначать через
E
i
математическое ожидание по мере P
i
. Пусть A
⊂
I
—
это некоторое
подмножество множества состояний. Момент (первого) достижения
H
A
—
это момент времени, когда цепь Маркова впервые попадает в A,
т. е.
H
A
=
inf
{
n
>
0: X
n
∈
A
}
. (1.3.1)
§ 1.3. Времена и вероятности достижения 39
Вероятность достижения h
A
i
—
это вероятность того, что цепь, стартующая
из состояния i, когда
-
нибудь попадет в A:
h
A
i
=
P
i
(H
A
< ∞
); (1.3.2)
если A
—
это замкнутый класс, то h
A
i
называют вероятностью поглощения.
Математическое ожидание величины H
A
обозначают k
A
i
:
k
A
i
=
E
i
(H
A
)
=
X
0
<
n
<∞
n P
i
(H
A
=
n)
+ ∞ ·
P
i
(H
A
= ∞
). (1.3.3)
Следовательно, если P
i
(H
A
= ∞
)
>
0, то k
A
i
= ∞
. (По соглашению,
∞ ·
0
=
0.)
Вычисление вероятностей достижения основывается на следующей
теореме.
Теорема 1.3.1. При заданном множестве A
⊂
I величины h
A
i
представляют собой минимальные неотрицательные решения сле-
дующей линейной системы:
(
h
A
i
≡
1, i
∈
A,
h
A
i
=
P
j
∈
I
p
ij
h
A
j
, i
6∈
A,
(1.3.4)
т. е. для любого решения g
i
>
0 системы (1.3.4) выполняется нера-
венство g
i
>
h
A
i
, i
∈
I.
Д о к а з а т е л ь с т в о. Напомним, что h
A
i
вычисляется при условии, что
X
0
=
i. Если i
∈
A, то H
A
=
0, следовательно, h
A
i
=
1. Если i
6∈
A, то
H
A
>
1, и тогда
h
A
i
=
X
j
∈
I
P
i
(H
A
< ∞
, X
1
=
j)
=
X
j
∈
I
P
i
(X
1
=
j) P
i
(H
A
< ∞|
X
1
=
j)
=
=
(в силу марковского свойства)
X
j
p
ij
P
j
(H
A
< ∞
)
=
X
j
p
ij
h
A
j
.
Возьмем любое неотрицательное решение g
i
. Если i
∈
A, то g
i
=
h
A
i
=
=
1. Если i
6∈
A, то
g
i
=
X
j
p
ij
g
j
=
X
j
∈
A
p
ij
+
X
j
6∈
A
p
ij
g
j
=
X
j
∈
A
p
ij
+
X
j
6∈
A
p
ij
X
k
∈
A
p
jk
+
X
k
6∈
A
p
jk
g
k
=
=
P
i
(X
1
∈
A)
+
P
i
(X
1
6∈
A, X
2
∈
A)
+
X
j
6∈
A,k
6∈
A
p
ij
p
jk
g
k
.