Кельберт М.Я., Сухов Ю.М. Вероятность и статистика в примерах и задачах. Том 2. Марковские цепи как отправная точка теории случайных процессов и их приложения
Подождите немного. Документ загружается.
180 Глава 1. Цепи Маркова с дискретным временем
Пусть A
+
и A
−
—
пересечения события A с событиями
{
X
n
>
0
}
и
{
X
n
<
<
0
}
:
A
+ = {
Y
n
=
i, Y
n
−
1
=
y
n
−
1
, . . . , Y
0
=
y
0
=
0, X
n
>
0
}
,
A
− = {
Y
n
=
i, Y
n
−
1
=
y
n
−
1
, . . . , Y
0
=
y
0
=
0, X
n
<
0
}
.
Тогда P (Y
n
+
1
=
i
+
1
|
A) можно представить в виде
P (X
n
+
1
=
i
+
1
|
A
+
) P (X
n
>
0
|
A)
+
P (X
n
+
1
= −
i
−
1
|
A
−
) P (X
n
<
0
|
A)
=
=
p P (X
n
>
0
|
A)
+
q P (X
n
<
0
|
A).
Далее, каждая траектория из X
0
=
0 в X
n
=
i имеет зеркальное
отражение
—
траекторию из X
0
=
0 в X
n
= −
i с теми же Y
0
, . . ., Y
n
. Для
каждой такой пары траекторий можно записать
P
X
0
(траектория)
=
p
i
q
i
P
X
0
(отражение),
поскольку вероятность
«
петель
»
, появляющихся вдоль траектории (меж
-
ду первым и последним моментами, когда цепь X попадает в заданное
состояние), одинакова для обеих траекторий и единственное отличие меж
-
ду вероятностями возникает при переходе цепи из некоторого состояния
в соседнее состояние (в соответствующем направлении) между петлями.
Поэтому
P (A)
=
P (траектория)
+
P (отражение)
=
P (траектория)
1
+
q
i
p
i
и
P (X
n
>
0
|
A)
=
P (траектория)
P (траектория)
+
P (отражение)
=
p
i
q
i
+
p
i
,
P (X
n
<
0
|
A)
=
q
i
q
i
+
p
i
.
Тогда вероятности
P (Y
n
+
1
=
i
+
1
|
A)
=
p
i
+
1
+
q
i
+
1
p
i
+
q
i
и P (Y
n
+
1
=
i
−
1
|
A)
=
1
−
p
i
+
1
+
q
i
+
1
p
i
+
q
i
не зависят от y
1
, . . . , y
n
−
1
. Итак, последовательность (Y
n
, n
=
0, 1, . . .)
образует ц.м.д.в. с указанными выше вероятностями перехода.
§ 1.16. Вопросы по теории цепей Маркова с дискретным временем 181
Задача 1.16.4. Лягушку посадили в подвал, пол которого разделен на
N квадратов, занумерованных от 1 до N. Пусть X
n
—
это номер квадрата,
в котором лягушка находится в момент n; последовательность (X
n
)
n
>
0
можно рассматривать как неприводимую цепь Маркова с вероятностями
перехода p
ij
(1
6
i, j
6
N). Восприимчивая к движениям фотокамера
делает мгновенный снимок подвала всякий раз после того, как лягуш
-
ка перепрыгивает с одного квадрата на другой, и снимки производятся
только в такие моменты. Пусть Y
n
обозначает номер квадрата, в кото
-
ром находится лягушка на n
-
й фотографии. Покажите, что (Y
n
) также
является неприводимой ц.м.д.в., и найдите ее вероятности перехода. Пусть
(
1
, . . . ,
N
)
—
инвариантная вероятностная мера для цепи (X
n
). Найдите
инвариантную меру для цепи (Y
n
), а также среднее число фотографий,
произведенных в единицу времени.
Предположим теперь, что N
=
9, квадраты расположены в виде таб
-
лицы 3
×
3
1 2 3
4 5 6
7 8 9
и в каждую единицу времени лягушка с равными вероятностями может
остаться на прежнем месте или перепрыгнуть на один из смежных квад
-
ратов (как в перпендикулярном направлении, так и по диагонали; так что,
например, p
2j
=
1
/
6 для всех j
6
6). Найдите инвариантную вероятностную
меру для цепи (X
n
) и среднее число фотографий, произведенных в единицу
времени.
Решение. Заметим, что каждое значение p
ii
меньше 1; в противном
случае цепь была бы приводимой. Предположим, что Y
n
=
X
m
, т. е. n
-
я
фотография производится в момент m. Тогда для любого j
6=
i условная
вероятность P (Y
n
+
1
=
j
|
Y
n
=
i, Y
n
−
1
=
i
n
−
1
, . . . , Y
0
=
i
0
) записывается в
виде
P (X
m
+
1
=
j
|
X
m
=
i)
+
P (X
m
+
1
=
i, X
m
+
2
=
j
|
X
m
=
i)
+
. . .
=
=
p
ij
+
p
ii
p
ij
+
p
2
ii
p
ij
+
. . .
=
p
ij
(1
−
p
ii
)
−
1
:
=
q
ij
и q
ii
:
=
P (Y
n
+
1
=
i
|
Y
n
=
i)
=
0. Поскольку эти вероятности не зависят от
n и от значений Y
l
при l
<
n, (Y
n
) является ц.м.д.в. с матрицей перехода
0 p
12
/
(1
−
p
11
) p
13
/
(1
−
p
11
) . . . p
1N
/
(1
−
p
11
)
p
21
/
(1
−
p
22
) 0 p
23
/
(1
−
p
22
) . . . p
2N
/
(1
−
p
22
)
. . . . . . . . . . . . . . .
p
N1
/
(1
−
p
NN
) p
N2
/
(1
−
p
NN
) p
N3
/
(1
−
p
NN
) . . . 0
.
182 Глава 1. Цепи Маркова с дискретным временем
Более того, цепь (Y
n
) неприводима: при j
6=
i можно перейти из состояния
i в j посредством той же последовательности прыжков, что и в цепи (X
n
) (а
из i в i можно перейти, совершив прыжок или серию прыжков из i, а затем
обратно).
Далее,
P (в момент n
+
1 сделана фотография
|
X
n
=
i)
=
1
−
p
ii
.
Следовательно, в инвариантном состоянии среднее число фотографий
в единицу времени равно
P (фотография произведена в единичном интервале времени)
=
=
N
X
i
=
1
i
(1
−
p
ii
)
=
1
−
X
i
i
p
ii
.
Инвариантная мера для Y
n
имеет вероятности
i
=
i
(1
−
p
ii
)
1
−
N
P
k
=
1
k
p
kk
, 1
6
i
6
N.
В самом деле,
X
i
i
q
ij
=
X
i : i
6=
j
i
(1
−
p
ii
)
1
−
N
P
k
=
1
k
p
kk
p
ij
1
−
p
ii
=
X
i
6=
j
i
p
ij
1
−
N
P
k
=
1
k
p
kk
=
j
(1
−
p
jj
)
1
−
N
P
k
=
1
k
p
kk
=
j
.
В заданном примере
1
=
3
=
7
=
9
и
2
=
4
=
6
=
8
в силу
симметрии. Тогда уравнения инвариантности принимают вид
1
=
1
4
1
+
2
×
1
6
2
+
1
9
5
,
2
=
2
×
1
4
1
+
3
×
1
6
2
+
1
9
5
,
5
=
4
×
1
4
1
+
4
×
1
6
2
+
1
9
5
.
Учитывая равенство 4
1
+
4
2
+
5
=
1, находим
1
=
4
49
,
2
=
6
49
,
5
=
9
49
.
Среднее число фотографий в единицу времени равно
1
−
9
X
i
=
1
i
p
ii
=
1
−
9
1
49
=
40
49
.
§ 1.16. Вопросы по теории цепей Маркова с дискретным временем 183
Задача 1.16.5. Улитка ползет по бесконечной ограде, которую можно
рассматривать как решетку с вершинами в точках
Z × {
0, 1, 2
}
. Из вер
-
шины вида (n, 2) улитка перемещается влево или вправо (т. е. в (n
−
1, 2)
или в (n
+
1, 2)) с равной вероятностью. Из вершины вида (n, 1) она пере
-
мещается вверх в вершину (n, 2) с вероятностью 1
/
2 и в любую другую из
трех оставшихся вершин
—
с вероятностью 1
/
6. Из вершины (n, 0) улитка
обязательно перемещается влево, если n четно, и вправо, если n нечетно.
Классифицируйте состояния ц.м.д.в. соответствующей последовательности
вершин, по которым осуществляется движение улитки. Если улитка выхо
-
дит из вершины (0, 1), то какова вероятность того, что она когда
-
либо
попадет в положительно возвратное состояние? Какова вероятность того,
что она когда
-
нибудь попадет в вершину (0, 0)?
Решение. Состояния (n, 2), n
∈ Z
, образуют замкнутый сообщаю
-
щийся класс и все имеют нулевую возвратность. Для каждого n пара
состояний (2n
−
1, 0) и (2n, 0) образует замкнутый сообщающийся класс,
следовательно, все такие состояния
—
положительно возвратны. Наконец,
каждое состояние (n, 1) невозвратно: p
(n,1) (n,2)
>
0, но невозможен переход
с уровня 2 на уровень 1.
Предположим, что улитка выходит с уровня 1, и рассмотрим вероят
-
ность P
(i,1)
(когда
-
нибудь достичь уровень 0). Эта вероятность равна
∞
X
n
=
0
P
(i,1)
(оставаться на уровне 1 на n шагах, затем перейти на уровень 0)
=
=
∞
X
n
=
0
1
3
n
1
6
=
1
6
1
−
1
3
−
1
=
1
4
.
Улитка может когда
-
нибудь попасть в вершину (0, 0), если и только
если она когда
-
нибудь приползет туда из (0, 1) или из (
−
1, 1). Пусть
h
i
=
P (когда
-
нибудь попасть в (0,0)
|
текущее состояние (i, 1)).
Тогда h
−
1
=
h
0
(в общем случае в силу симметрии h
−
i
=
h
i
−
1
) и
h
0
=
1
6
+
1
6
h
0
+
1
6
h
1
,
h
n
=
1
6
h
n
−
1
+
1
6
h
n
+
1
, n
>
1.
Подставив h
n
=
At
n
во второе уравнение, находим t
2
−
6t
+
1
=
0, т. е.
t
=
3
±
2
√
2. Так как h
n
6
1, получаем, что h
n
=
A(3
−
2
√
2)
n
. Из первого
уравнения находим A
=
h
0
=
1
/
2(1
+
√
2)
=
(
√
2
−
1)
/
2.
184 Глава 1. Цепи Маркова с дискретным временем
Hold infinity in the palm of your hand...
Попробуйте удержать бесконечность в своей ладони...
У. Блейк (1757
–
1827), английский поэт
Задача 1.16.6. Две частицы A и B перемещаются случайно в моменты
времени t
=
1, 2, . . . на множестве M
= {
1, . . . , m
}
, m
>
3, отражаясь
от границ, при этом их позиции X
A
(t) и X
B
(t) подчиняются некоторому
порядку (так что X
A
(t)
6
X
B
(t)) согласно следующей схеме.
1. Если расстояние между ними больше единицы, то в следующий
момент они осуществляют движение независимо друг от друга согласно
следующим правилам:
а) если частица не находится на границе, т. е. в точках 1 или m, то она
совершает скачок в одну из ближайших соседних точек с вероятностью
1
/
2;
б) если частица находится на границе, то она либо совершает скачок
в одну из ближайших соседних точек в M, либо остается в той же точке,
опять с вероятностью 1
/
2.
2. Если частицы встречаются (попадают в одну и ту же точку) или же
расстояние между ними равно единице, то они меняют свое поведение.
Если предполагаемые скачки могут привести к перестановке порядка ча
-
стиц, т. е. к неравенству X
A
>
X
B
, то обе частицы сохраняют свое прежнее
положение. (Вероятности предполагаемых скачков те же, что и ранее,
и эти предполагаемые скачки независимы.) В противном случае частицы
совершают эти предполагаемые скачки.
Определите пространство состояний ц.м.д.в., которая образована парой
(X
A
(t), X
B
(t)), и найдите ее инвариантное распределение. Обратима ли эта
цепь?
Решение. Приведенное выше описание определяет конечную непри
-
водимую цепь Маркова (с единственным сообщающимся классом) на
пространстве состояний
S = {
(n
A
, n
B
) : 1
6
n
A
6
n
B
6
m
}
,
с общим числом состояний m(m
+
1)
/
2. В самом деле, p
(m)
(n
A
,n
B
),(n
0
A
,n
0
B
)
>
0
для всех (n
A
, n
B
), (n
0
A
, n
0
B
)
∈ S
. Таким образом, цепь имеет единственное
стационарное распределение.
Кроме того, для всех (n
A
, n
B
), (n
0
A
, n
0
B
)
∈ S
матрица перехода сим
-
метрична: p
(n
A
,n
B
),(n
0
A
,n
0
B
)
=
p
(n
0
A
,n
0
B
),(n
A
,n
B
)
. Действительно, каждая из этих
вероятностей равна либо 0, либо 1
/
4, либо 1
/
2 (если (n
A
, n
B
)
=
(n
0
A
, n
0
B
)
=
=
(1, 1) или (n
A
, n
B
)
=
(n
0
A
, n
0
B
)
=
(m, m)). Следовательно, стационарное
распределение является равномерным на
S
, и цепь обратима.
§ 1.16. Вопросы по теории цепей Маркова с дискретным временем 185
Задача 1.16.7. Рассмотрим стохастическую матрицу на множестве
{
1, . . . , 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
.
Найдите все возвратные состояния соответствующей цепи Маркова с дис
-
кретным временем.
Пусть p
n
ij
обозначает элемент матрицы P
n
с индексом ‘ij’. Определите
пары (i, j), для которых существует предел lim
n
→∞
p
n
ij
, и найдите эти предель
-
ные значения.
Решение. См. пример 1.2.7. Более простой способ решения
—
восполь
-
зоваться следующей теоремой. Если матрица P неприводимая, аперио-
дическая и имеет инвариантное распределение
, то p
(n)
ij
→
j
∀
i, j.
Действительно, замкнутый класс
—
это класс
{
1, 2, 6, 7
}
, а инвариант
-
ное распределение
=
1
5
,
3
10
,
1
5
,
3
10
. Отсюда получаем предел lim
n
→∞
p
(n)
ij
для i, j
∈ {
1, 2, 6, 7
}
; а для i
=
3 этот предел нужно разделить на 2.
Задача 1.16.8. В модели, описанной в примере 1.3.2, предположим, что
частица начинает движение из угла A (см. рис. 1.12). Найдите
а) вероятность того, что частица вернется в A, так и не побывав в цен
-
тральной вершине C;
б) среднее время возвращения в A;
в) математическое ожидание числа посещений вершины C до возвра
-
щения в A.
Решение. Часть a) уже рассматривалась в примере 1.3.2 (см. также
рис. 1.12).
б) применим следующую теорему: Для неприводимой ц.м.д.в. с инва-
риантным распределением
, среднее время возвращения в состоя-
ние i равно 1
/
i
.
Здесь
A
=
3
/
(18
+
6)
=
1
/
8, и, следовательно, ответ 8.
в) применим следующую теорему: Для неприводимой ц.м.д.в. с инва-
риантным распределением
среднее число посещений состояния j
до возвращения в состояние i равно
j
/
i
.
Здесь
C
=
1
/
4, и ответ 2.
(В гл. 2 мы дадим строгое определение процесса Пуассона. Однако,
если это определение уже известно, то следующую задачу можно легко
решить сейчас.)
186 Глава 1. Цепи Маркова с дискретным временем
Задача 1.16.9. Предположим, что (X
t
)
t
>
0
и (Y
t
)
t
>
0
—
независимые
пуассоновские процессы, оба с интенсивностью
. Рассмотрим разность
W
t
=
X
t
−
Y
t
. Пусть J
1
обозначает момент первого скачка процесса W
t
.
Найдите совместное распределение J
1
и W
J
1
.
Пусть M и N
—
натуральные числа. Найдите вероятность того, что
(W
t
)
t
>
0
достигнет уровня N раньше, чем уровня
−
M.
Покажите, что среднее время достижения процессом (W
t
)
t
>
0
множе
-
ства
{−
M, N
}
равно
MN
2
.
Указание. (j
+
1)
2
−
2j
2
+
(j
−
1)
2
=
2.
Решение. Из построения следует, что J
1
—
показательная с.в., W
J
1
принимает значения
±
1 с вероятностью 1
/
2 и с.в. J
1
и W
J
1
независимы.
Кроме того, (W
t
) является цепью Маркова с непрерывным временем на
целочисленной решетке
Z
с интенсивностью 2 , а соответствующая цепь
скачков является простым симметричным случайным блужданием.
Следовательно, если h
i
=
P
i
(достичь N прежде, чем
−
M), то
h
i
=
1
2
h
i
−
1
+
1
2
h
i
+
1
, h
−
M
=
0, h
N
=
1.
В общем виде h
i
=
A
+
Bi, откуда следует, что h
0
=
M
M
+
N
.
Аналогично если k
i
=
E
i
(достичь N или
−
M), то
k
i
=
1
2
+
1
2
k
i
−
1
+
1
2
k
i
+
1
, k
−
M
=
k
N
=
0.
В общем виде k
i
=
A
+
Bi
+
Ci
2
, откуда следует, что k
i
=
NM
/
(2 )
+
+
(N
−
M)i
/
(2 )
−
i
2
/
(2 ) и k
0
=
MN
2
.
Задача 1.16.10. Пусть (X
n
)
n
>
0
и (Y
n
)
n
>
0
—
независимые простые слу
-
чайные блуждания на
Z
, выходящие из x и y соответственно. На каждом
шаге (X
n
)
n
>
0
совершает скачок вправо с вероятностью p и влево
—
с веро
-
ятностью 1
−
p. Для (Y
n
)
n
>
0
соответствующие вероятности равны q и 1
−
q.
Для всех целых чисел x, y и p, q из (0, 1) найдите вероятность
(x, y, p, q)
того, что X
n
=
Y
n
при некотором n
>
0.
Решение. Поскольку X
n
=
Y
n
тогда и только тогда, когда X
n
−
Y
n
=
0,
удобно рассмотреть разность W
n
=
X
n
−
Y
n
, которая является случайным
блужданием на
Z
с вероятностями перехода
p
ij
=
p(1
−
q) при j
−
i
=
2,
pq
+
(1
−
p) (1
−
q) при j
−
i
=
0,
(1
−
p)q при j
−
i
= −
2.
§ 1.16. Вопросы по теории цепей Маркова с дискретным временем 187
Следовательно, P
x,y
(X
n
=
Y
n
)
=
P
x
−
y
(W
n
попадает в 0)
=
0 при нечетном
|
x
−
y
|
. При x
−
y
=
2k обозначим эту вероятность символом h
k
. Имеют
место уравнения:
h
k
=
(1
−
p)qh
k
−
1
+
(pq
+
(1
−
p) (1
−
q))h
k
+
p(1
−
q)h
k
+
1
,
или
h
k
=
(1
−
p)q
p
+
q
−
2pq
h
k
−
1
+
p(1
−
q)
p
+
q
−
2pq
h
k
+
1
, k
∈ Z
,
и h
0
=
1. Конечно, нас интересует минимальное неотрицательное решение.
Рассмотрим сначала k
>
0. Рекурсия
(h
k
, h
k
+
1
)
=
(h
k
−
1
, h
k
)
0
−
(1
−
p)q
/
(p(1
−
q))
1 (p
+
q
−
2pq)
/
(p(1
−
q))
имеет собственные значения 1 и q(1
−
p)
/
(p(1
−
q)), и, следовательно,
допускает общее решение
h
k
=
A
+
B
q(1
−
p)
p(1
−
q)
k
, если p
6=
q
и
h
k
=
A
+
Bk, если p
=
q.
Если p
6
q, то q(1
−
p)
/
(p(1
−
q))
>
1. Тогда минимальное неотрица
-
тельное решение получается при A
=
1, B
=
0: h
k
≡
1. Если p
>
q,
то q(1
−
p)
/
(p(1
−
q))
<
1. Тогда минимальное неотрицательное решение
получается при A
=
0, B
=
1:
h
k
=
q(1
−
p)
p(1
−
q)
k
.
Для k
6
0 ответ симметричен: если q
6
p, то h
k
≡
1, а если q
>
p, то
h
k
=
p(1
−
q)
q(1
−
p)
k
.
Ответ для
(x, y, p, q) получается с помощью соответствующей под
-
становки значений x, y, p и q.
Задача 1.16.11. Пусть (X
n
)
n
>
0
, (Y
n
)
n
>
0
и (Z
n
)
n
>
0
—
простые симмет
-
ричные случайные блуждания на
Z
. Тогда V
n
=
(X
n
, Y
n
, Z
n
) является
ц.м.д.в. Чему равны вероятности перехода для этой цепи?
Покажите, что с вероятностью 1 цепь (V
n
)
n
>
0
попадает в состояние
(0, 0, 0) только конечное число раз.
188 Глава 1. Цепи Маркова с дискретным временем
Решение. Вероятности перехода для (V
n
) равны
p
(i,j,k) (l,m,n)
=
(
1
/
8, если
|
i
−
l
| = |
j
−
m
| = |
l
−
n
| =
1,
0 в противном случае.
Наша цель
—
показать, что
∞
X
n
=
0
p
(n)
(0,0,0) (0,0,0)
< ∞
.
Как и ранее, p
(n)
(0,0,0) (0,0,0)
=
0, когда n нечетно. Кроме того, p
(2n)
(0,0,0) (0,0,0)
=
=
p
(2n)
00
3
, где p
(2n)
00
=
C
n
2n
. Следовательно,
p
(2n)
00
3
≈
1
( n)
3
/
2
, и ряд схо
-
дится. Таким образом, цепь (V
n
) невозвратна, откуда и следует утвержде
-
ние.
Задача 1.16.12. Рассмотрим ц.м.д.в. с пространством состояний
{
0, 1, 2, 3
}
и матрицей вероятностей перехода
1
/
3 2
/
3 0 0
7
/
16 1
/
4 5
/
16 0
1
/
6 1
/
6 1
/
6 1
/
2
1
/
2 1
/
6 1
/
6 1
/
6
.
Предположим, что цепь выходит из состояния 0. Найдите среднее число
переходов до того момента, когда цепь впервые попадет в состояние 3.
Найдите вероятность того, что цепь в первый раз попадает в состояние
2 на n
-
м шаге.
Решение. Положим
k
i
=
E
i
(число шагов, необходимое чтобы попасть в 3).
Соответствующие уравнения имеют вид
k
0
=
1
+
1
3
k
0
+
2
3
k
1
,
k
1
=
1
+
7
16
k
0
+
1
4
k
1
+
5
16
k
2
,
k
2
=
1
+
1
6
(k
0
+
k
1
+
k
2
),
откуда получаем
k
0
=
77
6
, k
1
=
34
3
, k
2
=
181
30
.
§ 1.16. Вопросы по теории цепей Маркова с дискретным временем 189
Далее, из 0 цепь может попасть в состояние 2, только пройдя через
состояние 1. Значит, можно рассмотреть приведенную цепь с матрицей
перехода
P
=
1
/
3 2
/
3 0
7
/
16 1
/
4 5
/
16
0 0 1
!
.
Собственные значения равны 1, 5
/
6 и
−
1
/
4. Следовательно,
p
(n)
02
=
P
0
(T
2
6
n)
=
A
+
B
5
6
n
+
C
−
1
4
n
,
и
P
0
(T
2
=
n)
=
p
(n)
02
−
p
(n
−
1)
02
=
5
6
n
+
−
1
4
n
, n
>
1.
Из граничных условий
n
=
1 :
5
6
−
1
4
=
0
и
n
=
2 :
25
36
+
1
16
=
5
24
находим
=
3
/
13,
=
10
/
13. Таким образом, ответ имеет вид
3
13
5
6
n
+
10
13
−
1
4
n
, n
>
1.
Задача 1.16.13. Последовательность случайных выпуклых много
-
угольников строится по следующей схеме. На каждом шаге имеющийся
многоугольник разбивают на два новых так: случайным образом выби
-
рают два разных ребра и соединяют средние точки этих ребер; затем
случайным образом выбирают один из образовавшихся многоугольников
и рассматривают его на следующем шаге. Каждый раз, когда делают слу
-
чайный выбор, все возможные исходы считаются равновероятными, и все
результаты такого случайного выбора независимы. Для n
=
0, 1, 2, . . .
пусть X
n
+
3 обозначает число ребер многоугольника на n
-
м шаге; таким
образом, X
n
принимает неотрицательные целые значения. Найдите матрицу
вероятностей перехода для ц.м.д.в.
{
X
n
, n
>
0
}
.
Объясните, почему предел lim
n
→∞
P (X
n
=
i) существует и не зависит
от числа ребер исходного многоугольника; найдите, чему равен этот предел
для каждого i
=
0, 1, 2, . . .
Решение. Если рассматриваемый многоугольник
—
треугольник, то на
следующем шаге может быть получен треугольник или четырехугольник
190 Глава 1. Цепи Маркова с дискретным временем
с вероятностью 1
/
2. Если же на данном шаге имеется четырехугольник, то
на следующем шаге могут появиться треугольник, или четырехугольник,
или пятиугольник, каждый с вероятностью 1
/
3. Аналогично из пятиуголь
-
ника можно получить треугольник, четырехугольник, пятиугольник или
шестиугольник, каждый с вероятностью 1
/
4. Эти рассуждения наводят на
мысль, что матрица вероятностей перехода для
X
n
=
число ребер
−
3
=
0
1
2
.
.
.
, n
=
1, 2, . . . ,
имеет вид
1
/
2 1
/
2 0 0 0 . . .
1
/
3 1
/
3 1
/
3 0
.
.
.
. . .
1
/
4 1
/
4 1
/
4 1
/
4 0 . . .
. . . . . . . . . . . . . . . . . . . . . . . .
.
Действительно, если X
n
=
m, т. е. n
-
й многоугольник имеет m
+
3 ребра,
то число способов выбрать два ребра равно C
2
m
+
3
=
(m
+
3) (m
+
2)
2
. Если
мы соединим соседние ребра i и i
+
1 mod m (m
+
3 возможностей), то сле
-
дующим может быть треугольник (при этом X
n
+
1
=
0) или (m
+
4)
-
угольник
(при этом X
n
+
1
=
m
+
1). Тогда
P (X
n
+
1
=
0
|
X
n
=
m)
=
P (X
n
+
1
=
m
+
1
|
X
n
=
m)
=
=
1
2
(m
+
3)
2
(m
+
3) (m
+
2)
=
1
m
+
2
.
В общем случае, если мы выбираем ребра i и i
+
s mod m и при этом между
ними находится s
−
1 ребро (таких возможностей по
-
прежнему m
+
3), то
следующим многоугольником может быть (s
+
2)
-
угольник (и X
n
+
1
=
s
−
1)
или (m
+
5
−
s)
-
угольник (и X
n
+
1
=
m
+
2
−
s), 1
6
s
6
(m
+
3)
/
2. Тогда
P (X
n
+
1
=
s
−
1
|
X
n
=
m)
=
P (X
n
+
1
=
m
+
2
−
s
|
X
n
=
m)
=
=
1
2
(m
+
3)
2
(m
+
3) (m
+
2)
=
1
m
+
2
.
(Для нечетного m значение s
=
(m
+
3)
/
2 приводит к такому же значению
1
/
(m
+
2) для вероятности P (X
n
+
1
=
s
−
1
|
X
n
=
m).) Отсюда следует наше
утверждение о матрице перехода.
Рассмотренная выше матрица неприводима, так как p
ij
=
1
i
+
2
>
0
при j
6
i
+
1 и p
(j
−
i
−
1)
ij
>
p
ii
+
1
p
i
+
1i
+
2
. . . p
j
−
1j
>
0 при j
>
i
+
1. Она
§ 1.16. Вопросы по теории цепей Маркова с дискретным временем 191
является апериодической, поскольку p
ii
>
0. Следовательно, она имеет не
более одного такого стационарного распределения
= {
i
}
, что P
=
и
j
=
lim
n
→∞
p
(n)
ij
∀
j
∈
I. Чтобы решить уравнение P
=
, запишем
0
=
1
2
0
+
1
3
1
+
1
4
2
+
. . .
=
1
и
i
=
1
i
+
1
i
−
1
+
1
i
+
2
i
+
. . .
=
1
i
+
1
i
−
1
+
i
+
1
, i
>
1,
т. е.
i
+
1
=
i
−
1
i
+
1
i
−
1
. Отсюда находим
2
=
1
−
1
2
0
=
1
2
0
и
3
=
2
−
1
3
1
=
1
3!
0
.
Введем предположение индукции
i
=
1
i!
0
. Тогда
i
+
1
=
0
1
i!
−
1
i
+
1
1
(i
−
1)!
=
0
(i
+
1)!
(i
+
1
−
i)
=
0
(i
+
1)!
.
Следовательно,
0
=
e
−
1
и
i
=
1
i!
e
−
1
, т. е. является распределением
Пуассона со средним 1.
Лев Толстой в повести
«
Дьявол
»
пишет:
«
Обыкновенно думают, что самые обычные
консерваторы
—
это старики, а новаторы
—
это молодые люди. Это не совсем справедливо.
Самые обычные консерваторы
—
это молодые люди. Молодые люди, которым хочется жить,
но которые не думают и не имеют времени подумать о том, как надо жить, и которые поэтому
избирают себе за образец ту жизнь, которая была.
»
Задача 1.16.14. Предположим, что экзаменатор должен оценить очень
большое число ответов. Каждый ответ, независимо от остальных, является
правильным с вероятностью p и неправильным с вероятностью 1
−
p.
У экзаменатора есть две стратегии оценивания. Первая стратегия (которую
он применяет вначале) состоит в проверке каждого ответа, правильный
ответ получает полный балл, а неправильный ответ получает нулевой балл.
Вторая стратегия менее точная; каждый ответ с вероятностью q и неза
-
висимо от предыдущих он оценивает по прежней схеме (т. е. выставляет
полный балл для правильного ответа и нулевой балл для неправильного);
либо с вероятностью 1
−
q он просто выставляет полный балл, не проверяя,
верен ответ или нет. Экзаменатор переходит от первой стратегии ко второй,
когда наблюдает n последовательных правильных ответов, и переходит
192 Глава 1. Цепи Маркова с дискретным временем
от второй стратегии к первой, когда обнаруживает неправильный ответ.
Представьте этот процесс в виде ц.м.д.в. Найдите предельные пропорции
ответов, которые экзаменатор проверил адекватно, и предельные пропор
-
ции неправильных ответов, которые получили полный балл.
Решение. Состояниями являются 0, 1, . . . , n. В состоянии i
<
n эк
-
заменатор заметил, что имеются i последовательных правильных ответов,
и он использует стратегию 1. В состоянии n он замечает, что имеются
n правильных ответов, и переходит на стратегию 2, и ни одного непра
-
вильного ответа при этом еще не появилось. Эти рассуждения приводят
к матрице
P
=
1
−
p p 0 0 0 . . . 0 0
1
−
p 0 p
.
.
.
.
.
.
. . . 0 0
1
−
p 0 0 p
.
.
.
. . . 0 0
. . . . . . . . . . . . . . . .
.
.
.
.
.
.
. . . . . . . . . . . . . .
1
−
p 0 0 0 0 . . . 0 p
q(1
−
p) 0 0 0 0 . . . 0 1
−
q(1
−
p)
.
Уравнения инвариантности
P
=
имеют вид
0
=
(1
−
p)
X
0
6
j
6
n
−
1
j
+
q(1
−
p)
n
,
i
=
p
i
−
1
,
n
=
p
n
−
1
+
(1
−
q(1
−
p))
n
, 1
6
i
6
n
−
1,
откуда получаем
=
q(1
−
p)
q(1
−
p
n
)
+
p
n
1, p, . . . , p
n
−
1
,
p
n
q(1
−
p)
.
Следовательно, предельная пропорция адекватно оцененных ответов равна
n
−
1
X
i
=
0
i
+
n
q
=
q
p
n
(1
−
q)
+
q
,
а предельная пропорция неправильно оцененных ответов равна
n
(1
−
q) (1
−
p)
=
p
n
(1
−
q) (1
−
p)
p
n
(1
−
q)
+
q
.
Naturam expellas... tamen usque recurret.
Гоните природу в дверь, она войдет в окно.
Гораций (65 г. до н. э.
–
8 г. н. э.), римский поэт
§ 1.16. Вопросы по теории цепей Маркова с дискретным временем 193
Задача 1.16.15. Неприводимая цепь Маркова имеет состояния 0, 1,
. . . , n и матрицу перехода P
=
(p(i, j)). Стартуя из a, эта цепь не может
попасть в состояние c, не пройдя вначале через b. Кроме того, известно,
что
p(b, c)
=
p,
p(b, a)
=
1
−
p,
p(b, j)
=
0 для j
6=
a, c.
Пусть
j
i
обозначает среднее число шагов до первого попадания в со
-
стояние j при условии, что ц.м.д.в. выходит из состояния i. Выразите
a
c
в терминах величин
b
a
.
Последовательно подбрасывают монету, для которой вероятность вы
-
падения герба равна p. Вычислите:
а) среднее число бросков до появления серии из k последовательных
гербов;
б) Определим блок порядка k как часть последовательности гербов
и решек между последовательными появлениями не менее, чем k идущих
друг за другом гербов. По соглашению, блок заканчивается этой серией
гербов, за которой следует решка, а после решки начинается начинается
новый блок порядка k. Серию по меньшей мере k последовательных гербов
внутри блока будем называть вспышкой. Найдите отношение
средняя длина вспышки
средняя длина блока
.
(При k
=
1 это отношение равно p.)
Решение. В силу строго марковского свойства имеем
c
a
=
p
b
a
+
(1
−
p) (
b
a
+
c
a
)
+
1
=
b
a
+
(1
−
p)
c
a
+
1,
откуда следует, что
c
a
=
1
p
(
b
a
+
1).
Далее, рассмотрим а). Пусть состояние цепи Маркова
—
это число
бросков монеты после последнего появления решки. Тогда
k
0
=
1
p
(
k
−
1
0
+
1)
=
1
p
+
1
p
2
(
k
−
2
0
+
1)
=
=
1
p
+
1
p
2
+
. . .
+
1
0
p
=
1
p
+
1
p
2
+
. . .
+
1
p
k
=
1
−
p
k
p
k
(1
−
p)
.
Теперь для б) рассмотрим последовательные независимые
«
блоки
»
ис
-
пытаний, в результате которых после k или более гербов подряд следует
194 Глава 1. Цепи Маркова с дискретным временем
решка. Для каждого блока среднее число гербов равно
k
+
(pq)
+
2p
2
q
+
3p
3
q
+
. . .
=
k
+
p
1
−
p
.
Ожидаемая длина блока равна
k
0
+
1
+
p
1
−
p
=
1
+
1
−
p
k
p
k
(1
−
p)
+
p
1
−
p
.
Действительно, величина
k
0
—
это среднее число бросков до появления
k последовательных гербов, p
/
(1
−
p)
—
это среднее число гербов, в до
-
полнение к k имеющимся гербам, до появления первой решки, а 1
—
это
вклад, внесенный этой первой решкой. Тогда благодаря усиленному з.б.ч.
предельная пропорция гербов, появляющихся внутри блока, равна
k
+
p
/
(1
−
p)
1
+
(1
−
p
k
)
/
(p
k
(1
−
p))
+
p
/
(1
−
p)
=
(k(1
−
p)
+
p)p
k
.
Задача 1.16.16. Рассмотрим ц.м.д.в. (X
n
)
n
>
0
с начальным состоянием
X
0
=
0 и вероятностями переходов
P(i, i
+
1)
=
p, P(i, i
−
1)
=
q (i
∈ Z
),
где p
+
q
=
1. Пусть
M
n
=
max
0
6
r
6
n
{
X
n
}
и Y
n
=
M
n
−
X
n
.
Для каждого из следующих случаев определите, является ли (Z
n
)
n
>
0
ц.м.д.в., и в случае положительного ответа найдите ее вероятности пе
-
рехода:
а) Z
n
=
M
n
; б) Z
n
=
Y
n
.
Решение. Пусть Z
n
принимает значения из множества I. Формальное
определение таково:
P (X
0
=
i
0
, X
1
=
i
1
, .. . , X
n
=
i
n
)
=
i
0
p
i
0
i
1
. . .p
i
n
−
1
i
n
∀
n
>
1 и i
0
, i
1
, .. . , i
n
∈
I.
Здесь (
i
, i
∈
I)
—
это вероятностное распределение, а (p
ij
, i, j
∈
I)
—
стохастическая матрица (матрица перехода) на I. Отсюда следует, что
условные вероятности
P (X
n
+
1
=
j
|
X
n
=
i, X
n
−
1
=
i
n
−
1
, . . . , X
0
=
i
0
)
=
p
ij
не зависят от того, какие значения i
n
−
1
, . . . , i
0
принимают величины X
n
−
1
,
. . . , X
0
.
§ 1.16. Вопросы по теории цепей Маркова с дискретным временем 195
Далее, в случае а) последовательность Z
n
=
M
n
не является цепью
Маркова, так как, например
P (M
4
=
2
|
M
3
=
1, M
2
=
0, M
1
=
0, M
0
=
0)
=
p
>
>
P (M
4
=
2
|
M
3
=
1, M
2
=
2, M
1
=
1, M
0
=
0)
=
p
2
.
А в случае б) последовательность Z
n
=
Y
n
является цепью Маркова,
поскольку
P (Y
n
=
y
n
|
Y
n
−
1
=
y
n
−
1
, . . . , Y
1
=
y
1
, Y
0
=
0)
=
=
q, если y
n
=
y
n
−
1
+
1,
p, если y
n
=
y
n
−
1
−
1 и y
n
−
1
>
0,
p, если y
n
=
y
n
−
1
=
0,
т. е. эта вероятность не зависит от y
1
, . . . , y
n
−
2
.
Задача 1.16.17. 1. Случайная последовательность неотрицательных
целых чисел (F
n
)
n
>
0
образована следующим образом: F
0
=
0, F
1
=
1,
а далее если известны F
0
, . . . , F
n
, то F
n
+
1
полагают равным либо сумме,
либо разности величин F
n
и F
n
−
1
с вероятностью 1
/
2. Является ли (F
n
)
n
>
0
ц.м.д.в.?
Рассмотрев ц.м.д.в. X
n
=
(F
n
−
1
, F
n
), найдите вероятность того, что
(F
n
)
n
>
0
достигнет значения 3, прежде чем вновь попадет в 0.
2. Постройте диаграмму для (X
n
)
n
>
0
, достаточную, чтобы установить
общую закономерность поведения цепи. На основании этого, используя
строго марковское свойство, покажите, что вероятность достижения со
-
стояния (1, 1), если ц.м.д.в. выходит из (1, 2), равна (3
−
√
5)
/
2.
Not wrung from speculation and subtleties,
but from common sense and observation.
Не исходи из изворотливых рассуждений,
а полагайся на наблюдения и здравый смысл.
Т. Браун (1605
–
1682), английский врач и литератор
Решение. См. рис. 1.46.
Последовательность (F
n
) не является цепью Маркова, так как F
n
+
1
зависит от F
n
и F
n
−
1
, однако пара (F
n
−
1
, F
n
) является ц.м.д.в. Первая часть
рис. 1.48 a показывает, что уровня F
n
=
3 можно достичь из состояния
(F
0
, F
1
)
=
(0, 1), попадая либо в точку (2, 3), либо в (1, 3). Попасть на
этот уровень, прежде чем на уровень F
n
=
0 (т. е. в состояние (1, 0)),
можно по двум прямым траекториям, дополненным нескольким смежными
196 Глава 1. Цепи Маркова с дискретным временем
Рис. 1.46
треугольными циклами. Первая из этих возможностей имеет вероятность
1
·
1
2
·
1
2
1
+
1
8
+
1
8
2
+
. . .
=
2
7
,
а вторая
—
вероятность
1
·
1
2
·
1
2
·
1
2
1
+
1
8
+
1
8
2
+
. . .
=
1
7
,
что в сумме равно 3
/
7.
Рассмотрим треугольный участок на рис. 1.48, обладающий очевидной
симметрией. В частности,
P
(1,2)
(попасть в (1, 1))
=
P
(2,3)
(попасть в (1, 2))
=
P
(1,3)
(попасть в (2, 1)) :
=
p
и
P
(2,1)
(попасть в (1, 1))
=
P
(3,2)
(попасть в (2, 1)) :
=
p
0
.
Очевидно, 0
<
p, p
0
<
1. Взяв условную вероятность по первому скачку,
мы можем записать (благодаря строго марковскому свойству)
p
=
1
2
p
0
+
1
2
P
(2,3)
(попасть в (1, 1))
=
1
2
p
0
+
1
2
p
2
и
p
0
=
1
2
+
1
2
P
(1,3)
(попасть в (1, 1))
=
1
2
+
1
2
pp
0
, следовательно, p
0
=
1
2
−
p
.
Получим
p
=
1
2(2
−
p)
+
1
2
p
2
, т. e. p
3
−
4p
2
+
4p
−
1
=
(p
−
1) (p
2
−
3p
+
1)
=
0.
§ 1.16. Вопросы по теории цепей Маркова с дискретным временем 197
Корни этого уравнения равны p
=
1 и
3
±
√
5
2
. Нас интересует ми
-
нимальный неотрицательный корень, т. e. p
=
3
−
√
5
2
. Следовательно,
p
0
=
2
1
+
√
5
.
Задача 1.16.18. Блоха прыгает случайным образом по вершинам тре
-
угольника; каждый прыжок она совершает из занятой вершины на одну
из двух других с вероятностью 1
/
2. Найдите вероятность того, что блоха
вернется на место старта через n прыжков.
Вторая блоха также прыгает по вершинам треугольника, но для нее
вероятность прыгнуть по часовой стрелке в 2 раза больше, чем вероятность
прыгнуть против часовой стрелки. Чему равна вероятность того, что вторая
блоха возвратится на место старта через n прыжков?
Решение. Для первой блохи матрица переходных вероятностей такова:
P
=
0 1
/
2 1
/
2
1
/
2 0 1
/
2
1
/
2 1
/
2 0
!
.
Благодаря симметрии все элементы на диагонали p
(n)
ii
одинаковы, равно
как и все элементы p
(n)
ij
вне диагонали. Поэтому рассмотрим приведенную
цепь с двумя состояниями 1 и 0 (не одинаковыми) и переходной матрицей
e
P
=
0 1
1
/
2 1
/
2
.
Тогда p
(n)
11
=
e
p
(n)
11
. Собственные числа матрицы
e
P равны 1 и
−
1
/
2, и
p
(n)
11
=
A
+
B
−
1
2
n
,
причем A
+
B
=
1, A
−
B
/
2
=
0. Отсюда получаем A
=
1
/
3, B
=
2
/
3 и
p
(n)
ii
=
1
3
+
2
3
−
1
2
n
.
Для второй блохи
P
=
0 1
/
3 2
/
3
2
/
3 0 1
/
3
1
/
3 2
/
3 0
!
,
а собственные числа равны
1,
−
1
2
±
i
√
3
6
=
−
1
√
3
e
±
i
/
6
.
198 Глава 1. Цепи Маркова с дискретным временем
Тогда
p
(n)
11
= +
−
1
√
3
n
cos
n
6
+
sin
n
6
.
При этом
=
1
/
3, так как p
(n)
11
→
1
, и
=
(1
/
3, 1
/
3, 1
/
3) является (един
-
ственным) стационарным распределением. Постоянные
и вычисляются
из уравнений для n
=
0 и n
=
1:
+ + =
1,
−
1
√
3
√
3
2
+
1
2
=
0.
Получим
=
1
/
3,
=
2
/
3,
=
0 и
p
(n)
11
=
1
3
+
2
3
−
1
√
3
n
cos
n
6
.
Задача 1.16.19. В упрощенной компьютерной игре фигурка движется
случайно по решетке размера N
×
N (N
>
2) по следующим правилам.
Пусть (X
n
, Y
n
)
—
положение фигурки после n шагов, где X
n
и Y
n
могут
принимать значения 0, 1, . . . N
−
1. На (n
+
1)
-
м шаге вероятность каждой
из следующих четырех возможностей равна 1
/
4:
а) X
n
+
1
=
X
n
+
1 (mod) N, Y
n
+
1
=
Y
n
;
б) X
n
+
1
=
X
n
−
1 (mod) N, Y
n
+
1
=
Y
n
;
в) X
n
+
1
=
X
n
, Y
n
+
1
=
Y
n
+
1, (mod) N;
г) X
n
+
1
=
X
n
, Y
n
+
1
=
Y
n
−
1, (mod) N.
Вычислите
1) среднее число шагов до возвращения в состояние (1, 1), если ц.м.д.в.
выходит из состояния (1, 1),
2) среднее число шагов для достижения (1, 1), если ц.м.д.в. выходит из
состояния (0, 1).
Решение. В данном случае ц.м.д.в. является случайным блужданием
на плоском графе с N
2
вершинами, которые расположены в узлах це
-
лочисленной решетки (i, j), i, j
=
0, 1, 2, . . . , N
−
1, и ребрами, которые
соединяют каждую такую точку с четырьмя соседними (при условии, что
точка (i, 0) соединяется с точкой (i, N
−
1), а точка (0, j)
—
с (N
−
1, j);
периодические граничные условия). В силу уравнений детального баланса
равномерное распределение
вида
(i,j)
=
1
N
2
инвариантно. Так как граф связный, ц.м.д.в. неприводима. Поэтому она
положительно возвратна и является единственным стационарным рас
-
пределением. Тогда
§ 1.16. Вопросы по теории цепей Маркова с дискретным временем 199
1) среднее число шагов m
(i,j)
, необходимых для возвращения в (i, j),
при условии, что ц.м.д.в. выходит из (i, j), равно 1
/
(i,j)
=
N
2
(см. теорему
1.7.8);
2) благодаря симметрии и строго марковскому свойству,
m
(i,j)
=
1
+
E
(i
−
1,j)
(время до попадания в (i, j)).
Тогда
E
(0,1)
(время до попадания в (1, 1))
=
N
2
−
1.
Задача 1.16.20. В лабиринте, приведенном на рис. 1.47, пять пронуме
-
рованных клеток для крыс соединены туннелями. Линии означают туннели,
по которым крыса может двигаться в любом направлении, а стрелки обо
-
значают туннели, в которых есть
«
турникеты
»
, препятствующие движению
в противоположном направлении.
Рис. 1.47
Крыса бегает по лабиринту следующим образом: в каждой клетке она
случайным образом выбирает выход, и на каждом перекрестке, обозначен
-
ном
•
, она случайным образом выбирает направление (включая туннель,
из которого она только что вышла, если только обратный путь не перекрыт
турникетом). Пусть X
n
—
число посещений n
-
й клетки. Найдите матрицу
переходных вероятностей для цепи X
=
(X
n
).
Классифицируйте каждое состояние цепи в а), используя, где следует,
термины
«
поглощающее
»
,
«
невозвратное
»
,
«
возвратное
»
,
«
апериодиче
-
ское
»
,
«
нулевой возвратности
»
,
«
положительно возвратное
»
.
Вычислите среднее время возвращения в каждое состояние.
Найдите вероятность того, что крыса попадет в клетку 1, при условии,
что она вышла из клетки 3.