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

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

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

Пример 1.8.6. Однородный процесс рождения и гибели. Этот про

цесс является случайным блужданием на

, таким что

p, p

−

p, i

1, p

q, p

−

где 0

p, q

1. Рассмотрим случай 0

1 и 0

1, когда цепь

неприводима. Тогда классификация такова:

2 : положительная возвратность,

2 : нулевая возвратность,

2 : невозвратность

независимо от значения q.

Действительно, уравнения инвариантности

−

, i

−

как и выше, имеют решение

B(p

−

p))

, i

При p

2 имеет смысл свести число параметров к одному, т. е.

положить A

0. Для i

0, 1 мы получаем одно и то же уравнение

pB.

Чтобы нормировать, запишем



−

. . .





−



p(1

−

q(1

−

2p)

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

q(1

−

2p)

p(1

−

2p)

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

−



−



, i

и цепь является положительно возвратной, что и утверждалось.

Далее, при p

2 выполняются соотношения

(числа посещений состояния i, прежде чем цепь вернется в k)













−



−

, 0

i, k

< ∞

, i



−



, 0

< ∞



−



, 0

< ∞

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

(время возвращения в k)

, k

∈ Z

При p

2 мы должны рассмотреть f

< ∞

). Записав

< ∞

)

−

q P

(достичь 0),

мы видим, что если P

(попасть в 0)

1, то цепь невозвратна. Однако

(достичь состояния i

−

, i

см. § 1.5. Следовательно, при p

2 цепь невозвратна.

Остается рассмотреть случай p

2. В этом случае f

1 и цепь

возвратна. Уравнения инвариантности

−

, i

имеют общее решение

Bi, i

1. При i

1, 0 эти уравнения имеют

вид

−

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

0 и

≡

A, i

и неотрицательные инвариантные меры соответствуют значениям A

Мы видим, что

< ∞

только при A

0. Таким образом, цепь

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

возвратность.

Значит, при p

2 справедливо следующее: а) все неотрицательные

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

(

) взаимно пропорциональны, и каждая такая

мера, не равная 0 тождественно, имеет компоненты

0 при i

(2q)

0. Кроме того, б) все векторы

, k

0, должны быть

инвариантными и, следовательно, взаимно пропорциональными. При такой

нормировке, что

1, единственно возможными являются случаи а)

≡

1 и

(2q)

∀

k, i

1 и б)

∀

1. (Это выглядит еще

более удивительным, так как можно было ожидать, что при k

1 должно

выполняться неравенство

. . .

−

. . . ,

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

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

жить, что возможно равенство

−

Наконец, нетрудно проверить, что

(числа посещений состояния i, прежде чем цепь вернется в k, равно n)



2(i

−





−

2(i

−



−

∀

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

Cherchez la Gamme: a Musical On Vectorial Return Times

Ищите Гамму: мюзикл о векторных временах возвращения

(Из серии

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

Пример 1.8.7. Пусть X

: n

—

случайное блуждание на

множестве целых чисел, причем шаги влево либо вправо совершаются

с вероятностью 1

2 в любой момент времени. Покажите, что

P (X





и докажите, что м.ц.д.в. X возвратна.

Пусть X

0, m

—

натуральное число, а N

—

случайное число попада

ний в точку m, прежде чем цепь вернется в 0.

Найдите P (N

1) и докажите, что

P (N







−



−

, n

Решение. Изучим вероятность P (X

(2n)

того, что

траектория длины 2n, которая начинается в точке 0, возвращается в точку

0 через 2n шагов. Каждая такая траектория должна состоять из n шагов

вправо и n влево. Общее число таких траекторий равно C

, и вероятность

каждой из них равна (1

. Эти рассуждения и приводят к формуле для

P (X

0).

Сумма

∞

P (X

0) совпадает с

∞

P (X

(возвращение за нечетное число шагов невозможно), и ее можно оценить

при помощи формулы Стирлинга: n!

≈

√

2 n

−

. Это приводит к ряду

√

n, который расходится. Таким образом, в силу теоремы о том,

Игра слов, ср.

Cherchez La Femme

(

Ищите женщину

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

что состояние возвратно тогда и только тогда, когда

(n)

= ∞

заключаем, что состояние 0 возвратно. Эти же аргументы можно исполь

зовать и для любого состояния i. Следовательно, цепь возвратна. (Это же

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

является свойством класса.)

Символ P будет означать здесь P

, т. е. распределение цепи (

, P).

Тогда P (N

(побывать в m перед возвращением в 0). Взяв услов

ную вероятность по первому шагу, запишем

P (N

(побывать в m перед возвращением в 0),

где P

обозначает распределение цепи (

, P). Положим

(побывать в m перед возвращением в 0),

тогда

−

, 1

Общее решение имеет вид h

Bi. Из условий h

0, h

1 находим,

что A

0, B

m. Следовательно, h

m и P (N

(2m).

Очевидно,

−

P (N

(вновь попасть в 0, прежде чем попасть в m).

В силу симметрии

(вновь попасть в m, прежде чем попасть в 0)

−

Для того чтобы траектория, начинающаяся в точке 0, попала в событие

{

}

при n

1, она должна пройти через m, прежде чем вернуться в 0,

−

1 раз вернуться в m, не попадая ни разу в 0, и лишь затем устремиться

в 0, уже не возвращаясь в m. В силу строго марковского свойства

P (N



−



−

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

(попасть в 0, прежде чем вернуться в m)

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

тат.

Пример 1.8.8. Рассмотрим цепь Маркова с пространством состояний

= {

0, 1, 2, . . .

}∪{

, 2

, 3

, . . .

}

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

на рис. 1.24, где 0

1 и p

−

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

Рис. 1.24

Для каждого значения q определите, является ли цепь невозвратной,

положительно возвратной или имеет нулевую возвратность.

В случае, когда цепь положительно возвратна, вычислите инвариантное

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

Решение. При i

1 положим

(достичь i

−

1), b

(достичь i)

(эти вероятности не зависят от значения i в силу однородности рассмат

риваемой цепи). Вычисляя условные вероятности относительно первого

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

pba

, b

pba,

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

−

, и a

pqa

−

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

p(1

q)a

−

(pq

1)a

и решениями являются

1 и a

−

Нас интересует минимальное решение

−

1, что достигается тогда и только тогда, когда q

√

−

Следовательно, цепь возвратна тогда и только тогда, когда q

(

√

−



и невозвратна тогда и только тогда, когда q

(

√

−



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

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

вратность, рассмотрим уравнение инвариантности

P, эквивалентное

системе уравнений

q, i

−

p, i

Эти уравнения допускают рекуррентное решение:



−



−





−

и аналогично



−





−



По индукции находим общие формулы



−



−



−



−

и стационарное распределение существует тогда и только тогда, когда оба

ряда, составленные из

, сходятся, что выполняется при (1

−

)

1, т. е. q

(

√

−



2. Следовательно, цепь имеет нулевую возвратность,

когда q

(

√

−



2, и положительно возвратна, когда q

(

√

−



В последнем случае



∞





−



−



−

В счетном пространстве состояний много точек. Больше, чем звезд

на небе, и намного больше, чем песчинок в песках Сахары.

(Из серии

Так говорил суперлектор

Пример 1.8.9. Пусть (W

)

—

это процесс рождения и гибели на

= {

0, 1, 2, . . .

}

со следующими вероятностями перехода:

i,i

−

, i

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

Сопоставляя (W

) с симметричным простым случайным блужданием (Y

)

на

или иным способом, докажите, что (W

)

—

это возвратная ц.м.д.в.

Докажите, что (W

) имеет нулевую возвратность.

Вычислите векторы

(

, i

∈ Z

) для цепи (W

), k

∈ Z

Наконец, пусть W

0, а N

—

число посещений состояния 1, прежде

чем цепь вернется в 0. Покажите, что P

, n

Решение. Заметим, что (W

) является неприводимой ц.м.д.в. Кроме

того, W

= |

, где (Y

)

—

симметричное случайное блуждание

по бли

жайшим соседям

на

. Следовательно,

((W

) возвращается в i)

((Y

) возвращается в i)

∀

∈ Z

но правая часть равна 1, так как цепь (Y

) возвратна. Следовательно,

вероятность в левой части также равна 1, и цепь (W

) также возвратна.

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

) не имеет стационарного распределения. Рассмотрим уравнения инва

риантности

−

, i

Уравнение во второй строке имеет общее решение вида

Bi, i

Из первой строки находим B

0 и

2. Следовательно, любая

инвариантная мера имеет вид

A, i

где A

0. Для этой меры

= ∞

, за исключением случая, когда A

Таким образом, стационарное распределение не существует и цепь (W

)

имеет нулевую возвратность.

Следовательно, для ц.м.д.в. (W

) выполняется равенство











1, i, k

1 или i

2, i

0, k

2, i

1, k

Далее, в силу строго марковского свойства

(возвращение в 1 без прохождения цепи через 0))

−

(достичь 0 без возвращений в 1)

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

Действительно,

1 (так как p

1),

(возвращение в 1 без прохождения цепи через 0)

−

(так как цепь достигает 0 из 1 с вероятностью 1

2 и возвратна),

(достичь 0 без возвращений в 1)

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

Предельные пропорции

Время есть образ вечности.

Лаэрт Диоген (II в. н. э.), греческий писатель

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

ц.м.д.в.

забывает

свое начальное распределение

. В частности, если

(i)

, мера Дирака, сосредоточенная в состоянии i, ц.м.д.в.

забывает

о начальном состоянии i. Очевидно, такое поведение цепи связано со

свойствами n

кратной матрицы перехода P

при n

→ ∞

. Рассмотрим

сначала случай конечной цепи.

Теорема 1.9.1. Предположим, что (m

m)-матрица перехода P

поэлементно сходится к предельной матрице

Π =

(

)

lim

→∞

(n)

∀

i, j

∈

I. (1.9.1)

Тогда а) каждая строка

(i)

матрицы

задает инвариантное рас-

пределение

(i)

или

б) Если матрица P неприводима, то все ее строки

(i)

совпадают:

(1)

. . .

(m)

. В этом случае

lim

→∞

P (X

для любого j

∈

I и любого начального распределения .

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

Д о к а з а т е л ь с т в о. а) Для любого состояния j можно записать

(

(i)

∈

lim

→∞

(n)

lim

→∞

(n)

lim

→∞

(

(i)

)

. (1.9.2)

б) Если матрица P неприводима, то все строки

(i)

матрицы

совпада

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

деление. А также,

lim

→∞

P (X

lim

→∞

(n)

lim

→∞

(n)

. (1.9.3)

Для счетной цепи в уравнении (1.9.2) следует обосновать возможность

менять порядок перехода к пределу и суммирования. Однако формула

(1.9.3) остается верной и в общем случае, при условии, что нам известно,

что матрица P

сходится к матрице

, у которой строки равны между собой

и представляют собой инвариантное распределение

Итак, когда же эта сходимость P

→ Π

имеет место? Простой контр

пример, когда такая сходимость невозможна: P



0 1

1 0



. Здесь









1 0

0 1



, n четно,



0 1

1 0



, n нечетно.

(1.9.4)

В общем случае рассмотрим (m

матрицу







0 1 0 . . . 0

0 0 1 . . . 0

. . . . . . . . . . . .

1 0 0 . . . 0







которая соответствует рис. 1.25.

Тогда P

отвечает рис. 1.26 и так далее, m

я степень P

I соответ

ствует рис. 1.27.

Рисунок затем повторяется по модулю m. Опять стационарное распре

деление единственно:

m . . . , 1

m).

Мы знаем, что в этих примерах матрица P периодическая. Напомним,

что матрица P

—

апериодическая тогда и только тогда, когда

(n)

0 для всех достаточно больших n

∀

∈

I. (1.9.5)

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

Рис. 1.25 Рис. 1.26 Рис. 1.27

Более того, если матрица P неприводима, то

(n)

0 для всех достаточно больших n

∀

i, j

∈

I. (1.9.6)

Теорема 1.9.2. Предположим, что матрица P неприводима, апе-

риодична и положительно возвратна. Тогда

→ Π

при n

→ ∞

Элементы в столбцах матрицы

постоянны. Иными словами,

столбцы матрицы

состоят из повторений одного и того же

вектора

, где

—

(единственное) стационарное распределение

для P. Следовательно, неприводимая, апериодическая и положи-

тельно возвратная цепь Маркова забывает свое начальное распре-

деление:

lim

→∞

P (X

∀

и j

∈

Д о к а з а т е л ь с т в о. Рассмотрим две цепи Маркова: (X

(i)

), заданную

парой (

(i)

, P), и цепь (X

( )

), заданную парой ( , P). Тогда

(n)

(i)

j),

P (X

( )

j).

Чтобы оценить разность между этими вероятностями, мы определим их

общую часть

, склеив эти две цепи Маркова, т. е. рассматривая их сов

местно. Одна из возможностей

—

рассмотреть их как одну цепь Маркова,

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

сматриваем цепь Маркова (Y

) на I

I, состояниями являются (k, l) где

k, l

∈

I, переходные вероятности имеют вид

(k,l) (u,v)

, k, l, u, v

∈

I, (1.9.7)

а начальное распределение

P (Y

(k, l))

1(k

, k, l

∈

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

Однако, лучший способ

—

рассмотреть цепь (W

), вероятности перехода

которой равны

(k,l) (u,v)

(

, если k

1(u

v), если k

k, l, u, v

∈

I, (1.9.8)

а начальное распределение такое же, как и выше

P (W

(k, l))

1(k

, k, l

∈

I. (1.9.9)

В самом деле, уравнение (1.9.8) определяет матрицу вероятностей пе

рехода на I

I: все ее элементы p

(k,l) (u,v)

0 и суммы элементов по строкам

равны 1. Проверим это:

u,v

∈

(k,l) (u,v)







, если k







Далее, частичное (

маргинальное

) суммирование приводит к исходным

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

∈

(k,l) (u,v)

∈

(k,l) (u,v)

Образно говоря, две компоненты цепи (W

) по отдельности ведут себя

как (X

(i)

) и (X

); рассматриваемые совместно, они эволюционируют как

независимые компоненты (т. е. как в (Y

)) до того (случайного) момента

времени T, когда они совпадают

inf[n

1: X

(i)

после которого они движутся синхронно. Следовательно,

(n)

−

(i)

−

j).

Записав

(i)

P (X

(i)

j, T

P (X

(i)

j, T

n) (1.9.10)

j, T

n), (1.9.11)

замечаем, что первое слагаемое в каждой сумме одно и то же:

(i)

j, T

n),

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

так как события

{

(i)

j, T

}

{

j, T

}

совпадают. Следова

тельно,

(n)

−

P (X

(i)

j, T

−

P (X

j, T

(n)

−

| 6

n). (1.9.12)

Эта оценка называется неравенством спаривания (склейки).

Таким образом, достаточно проверить, что P

→

0, т. е. P (T

< ∞

)

1. Но (Y

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

цепью Маркова. (Неприводимость следует из того факта, что исходная

матрица P является неприводимой и апериодичной (см. уравнение (1.9.6)),

а положительная возвратность следует из того факта, что (Y

) имеет инва

риантное распределение (

)

(k,l)

k l

.) Следовательно, в силу теоремы

1.5.9

∀

состояний l

∈

(l,l)

< ∞

)

где

(l,l)

inf[n

0: X

(i)

l].

Так как T

(l,l)

, отсюда следует требуемое утверждение.

В случае конечной неприводимой апериодической цепи можно доказать,

что скорость сходимости p

(n)

—

геометрическая: см. теорему 1.9.3.

В действительности, если конечная ц.м.д.в. неприводима и апериодична,

то существуют такие m

1 и

∈

(0, 1), что

(m)

для любых состояний i, j. (1.9.13)

Теорема 1.9.3. Если P

—

конечная, неприводимая и апериодиче-

ская матрица, то для любых состояний i, j выполняется неравен-

ство



(n)

−



−

)

−

, (1.9.14)

где m и

такие, как в неравенстве (1.9.13).

Д о к а з а т е л ь с т в о. Повторяем ту же схему доказательства, что и в

теореме 1.4.2 мы должны оценить P

n). Но для конечного случая

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

(k,l)

∈

(m)

∈

(m)

т. е.

(k,l)

−

)

∀

k, l

∈

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

Тогда в силу строго марковского свойства





откуда и следует утверждение теоремы.

Поучительным является следующий пример.

Пример 1.9.4. Рассмотрим колоду карт, пронумерованных 1, 2, . . . , 52.

Процесс тасования карт происходит следующим образом: мы снимаем

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

52 возможных позиций, т. е. либо вновь на верхнюю позицию, либо под

колоду, либо на одну из 50 позиций между другими картами. Как долго

в среднем будет продолжаться этот процесс тасования до того момента,

пока самая нижняя карта не окажется сверху?

Пусть p

обозначает вероятность того, что после n итераций кар

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

независимо от начального порядка карт, p

имеет предел при n

→ ∞

и вычислить этот предел p. Сформулируйте точно все общие результаты,

на которые вы будете ссылаться.

Покажите, что, по крайней мере до того момента, пока нижняя карта

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

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

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

−

| 6

52(1

log 52)

Решение. Занумеруем позиции, на которых могут находится карты,

числами 1,2, . . . , 52, где 1 обозначает нижнюю позицию. Предположим, что

нижняя карта достигла позиции m. Тогда верхняя карта может находиться

где

то ниже с вероятностью m

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

события удовлетворяет уравнению



−



откуда находим k

m. Тогда общее среднее время достижения верх

ней позиции равно

. . .



. . .



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

становок

(группе перестановок). Эта цепь апериодическая, поскольку,

сняв верхнюю карту, мы вновь можем положить ее на прежнее место. Эта

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

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

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

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

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

вторую позицию и т. д. В силу симметрии равномерное распределение на

является инвариантным.

Следовательно, в силу теоремы о том, что для неприводимой апе-

риодической цепи Маркова (X

) со стационарным распределением

(

) выполняется соотношение lim

→∞

P (X

∀

j, получаем

lim

→∞

(52)!

Наконец, предположим, что в процессе тасования под нижнюю карту

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

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

дывать следующую карту (под ту, что была первоначально нижней), то она

равновероятно может оказаться на одной из k

й позиций, т. е. k

карта по прежнему будут упорядочены случайным образом. По индукции

это рассуждение применимо до момента, когда k

51.

Предположим далее, что T

—

это время, когда нижняя карта достигнет

вершины. Колода карт в момент времени T

1 упорядочена случайным

образом. В силу строго марковского свойства она таковой останется и в

момент времени (T

∨

max [T

1, n]. Следовательно,

−

| = |

P (карты расположены в порядке возрастания в момент n)

−

P (карты расположены в порядке возрастания в момент (T

∨

| 6

P (T



. . .



log 52).

То, что я говорю,

—

это пасьянс.

Перетасовка карт. (Дон Кихот)

М. де Сервантес (1547

–

1616), испанский писатель

Оставшаяся часть этого параграфа посвящена предельным пропор-

циям. Это предмет так называемых эргодических теорем, в которых

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

(в нашем случае ц.м.д.в.). Одним из удивительных феноменов являет

ся то, что при предположении типа неприводимости предельные средние

времена совпадают со средними значениями относительно стационарных

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

распределений. Эти последние средние можно рассматривать как усред-

нение по пространству (т. e. усреднение по пространству состояний I).

Таким образом, приведенный выше факт можно трактовать следующим

образом:

усреднение по времени на большом временн

ом интервале сов

падает с усреднением по пространству

; так формально можно пояснить

свойство перемешивания

для случайных процессов (на самом деле су

ществует целая иерархия таких свойств). Свойства перемешивания лежат

в основе многих феноменов, наблюдаемых в природе, и во многих областях

человеческой деятельности. Исторически, эти свойства связаны с именами

двух знаменитых физиков XIX в.

—

американца Дж. В. Гиббса (1839

–

1903)

и австрийца Л. Больцмана (1844

–

1906). Эргодические теоремы образуют

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

включает в себя широкий спектр концепций и методов.

В предельной пропорции мы все будем мертвы.

Дж. Майнард Кейнс (1883

–

1946), британский экономист

Приведем естественный пример.

Пример 1.9.5. Рассмотрим число посещений цепью состояния i до

момента времени n:

(n)

−

1(X

i). (1.9.15)

Если существует предел

lim

→∞

(n)

, (1.9.16)

то его называют предельной пропорцией времени, проведенного в состо

янии i.

Вообще, если f: I

→ R

—

это функция на пространстве состояний I, то

можно рассматривать сумму

V (f, n)

−

f(X

) (1.9.17)

и предел

lim

→∞

V (f, n)

. (1.9.18)

Теорема 1.9.6. Для любого состояния i выполняется равенство



lim

→∞

(n)



1, (1.9.19)

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

где

(

, если состояние i положительно возвратно,

0, если состояние i нулевой возвратности или невозвратно.

(1.9.20)

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

вратно. Тогда, как мы знаем, суммарное число V

посещений состояния i

конечно с вероятностью 1; см. формулы (1.5.8), (1.5.18). Значит, V

→

при n

→ ∞

с вероятностью 1. Так как 0

(n)

, мы получаем, что

(n)

→

0 при n

→ ∞

с вероятностью 1.

Пусть теперь состояние i возвратно. Тогда моменты времени T

(1)

(2)

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

с P

вероятностью 1. В силу теоремы 1.8.3 они являются н.о.р.с.в. со

средним m

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

средними в случае нулевой возвратности. Очевидно,

(1)

. . .

(n))

но

(1)

. . .

(n)

−

см. рис. 1.28. Таким образом, мы можем записать

(n)

(1)

. . .

(n)

−

)

(n)

(1)

. . .

(n))

). (1.9.21)

По теореме 1.8.4 с P

вероятностью 1 существует предел lim

→∞

(l)



(l)

→

при n

→ ∞



1. (1.9.22)

Далее, так как состояние i возвратно, последовательность (V

(n)) бес

конечно возрастает, и с P

вероятностью 1 выполняется соотношение

(n)

% ∞

, при n

→ ∞

)

1. (1.9.23)

Тогда мы можем в формуле (1.9.22) суммировать до V

(n) вместо n и со

ответственно разделить на V

(n):

lim

→∞

(n)

(l)

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

Рис. 1.28

Это соотношение выполняется и на пересечении двух ранее упомянутых

событий вероятности 1, которое, очевидно, имеет и P

вероятность 1. На

этом же событии выполняется равенство

lim

→∞

(n)

−

(l)

Иными словами, из формул (1.9.22) и (1.9.23) следует, что



(n)

−

(l)

→

(n)

(l)

→

при n

→ ∞



(1.9.24)

Но тогда в силу соотношения (1.9.21) все на том же пересечении этих двух

событий P

вероятности 1 отношение n

(n) стремится к m

, т. e. обратное

отношение V

(n)

n стремится к r

. Отсюда следуют соотношения

(1.9.19) и (1.9.20), что и завершает доказательство теоремы 1.9.6.

Замечание 1.9.7. Аккуратный анализ доказательства теоремы 1.9.6

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

можно утверждать, что в формуле (1.9.19) вероятностное распределение P

может быть заменено на P

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

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

. Это возможно благодаря тому, что суммы T

(1)

. . .

(n)

все еще асимптотически ведут себя, как если бы с.в. T

(l)

были бы н.о.р..

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

(На самом деле распределение первой с.в. T

(1)

другое и зависит

от начального состояния.)

Теорема 1.9.8. Пусть P

—

конечная неприводимая переходная

матрица. Тогда для любого начального распределения

и любой

ограниченной на I функции f справедливо равенство



lim

→∞

V (f, n)

(f)



1, (1.9.25)

где

(f)

∈

f(i). (1.9.26)

Д о к а з а т е л ь с т в о является уточнением доказательства теоремы

1.9.6. А именно, соотношение (1.9.25) эквивалентно равенству



lim

→∞



V (f, n)

−

(f)





Иными словами, мы хотим проверить, что с P

вероятностью 1 выполняется

условие



V (f, n)

−

(f)



→

0 при n

→ ∞

. (1.9.27)

Записывая V (f, n)

∈

(n)f(i) и (f)

∈

f(i), мы можем пре

образовать и ограничить левую часть соотношения (1.9.27) следующим

образом:



V (f, n)

−

(f)



∈



(n)

−



f(i)



∈



(n)

−



f(i)

Мы знаем, что V

(n)

→

с P

вероятностью 1 для любого i

∈

Замечание 1.9.7 позволяет утверждать, что V

(n)

→

с P

вероятно

стью 1 (т. е. независимо от выбора начального состояния) или, более того,

с P

вероятностью 1, где P

—

распределение (

, P) ц.м.д.в. с произвольным

начальным распределением

. Получаем соотношение (1.9.25), что и за

вершает доказательство теоремы 1.9.8.

Пример 1.9.9. Опишите предельное поведение ц.м.д.в. на конечном

пространстве состояний. Описание должно содержать обсуждение схо

димости вероятностей, а также поведение почти наверное. Объясните, что

происходит с невозвратными цепями.

Решение. Пространство состояний распадается на открытые классы

, . . . , O

и замкнутые классы C

, . . . , C

. Если l

1 (случай един

ственного замкнутого класса), то цепь неприводима. Выходя из открытого

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

класса, скажем O

, цепь попадет в замкнутый класс C

с вероятностью h

Эти вероятности удовлетворяют уравнению

Здесь

—

это вероятность перехода из класса O

в класс O

или C

, и для

1, . . . , j

l выполняются равенства h

Цепь имеет единственное стационарное распределение

(r)

, сосредото

ченное на C

, при каждом r

1, . . . , j

l (следовательно, единственное

стационарное распределение при l

1). Любое стационарное распределе

ние представляет собой смесь стационарных распределений

(r)

Если цепь выходит из C

, то для любой функции f на C

выполняются

условия

f(X

)

→

∈

(r)

f(i) почти наверное.

Более того, в апериодическом случае (когда НОД

{

n: p

(n)

} =

1 для

некоторого a

∈

) для любого i

∈

имеем

P (X

)

→

и скорость сходимости геометрическая.

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

Поворот времени, поворот судьбы

Из серии

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

Пусть (X

, X

, . . .)

—

ц.м.д.в. и зафиксировано N

1. Что можно

сказать об обращенной во времени цепи (X

), т. е. о семействе (X

−

, n

0, 1, . . . , N)

, X

−

, . . . , X

Теорема 1.10.1. Пусть (X

)

—

это ц.м.д.в. ( , P), где

(

)

—

стационарное распределение для P и

∀

∈

I. Тогда 1) для лю-

бого N

1 обращенная во времени цепь (X

, X

−

, . . . , X

) является

ц.м.д.в. (

P), где

(

) задается равенством

; (1.10.1)

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

Reversal of Fortune

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

2) если матрица P неприводима, то таковой является и

Д о к а з а т е л ь с т в о. 1) Во

первых, заметим, что

P является стоха

стической матрицей, т. е.

0 и

Далее, вектор

является

инвариантным:

Протащим

теперь множитель

•

сквозь произведение:

P (X

, . . . , X

)

P (X

, . . . , X

)

. . . p

−

. . . p

−

. . .

−

. . .

Мы видим, что (X

−

) является ( ,

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

2) Если P неприводима, то любые два состояния i, j сообщаются, т. е.

существует такой путь i

, i

, . . . , i

j, что

. . . p

−

. . . p

−

. . . p

−

. . .

−

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

. . .

−

0, и состояния j, i являются сообщающи

мися и для

Случай, когда цепь (X

−

) имеет то же распределение, что и цепь (X

представляет особый интерес.

Теорема 1.10.2. Пусть (X

)

—

ц.м.д.в. Следующие два свойства

эквивалентны:

1) для любого n

1 и любых состояний i

, . . . , i

P (X

, . . . , X

)

P (X

, . . . X

); (1.10.2)

2) ц.м.д.в. (X

) находится в состоянии равновесия, т. е. (X

)

∼

( , P) где

—

инвариантное распределение для P и

для любых состояний i, j

∈

I. (1.10.3)