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

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

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

Решение. Переходная 5

матрица имеет вид:







1 0 0 0 0

9 1

6 1

4 1

0 0 0 1

2 1

0 0 0 1

2 1







Из рис. 1.47 и вида матрицы P заключаем, что

состояние 1 поглощающее;

состояния 2 и 3 невозвратны и апериодичны;

состояния 4 и 5 положительно возвратны, апериодичны.

Средние времена возвращения равны

1, m

= ∞

, m

Наконец, для h

(попасть в 1) имеем соотношения

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

13, h

13.

Счетное количество и одна ночь

(Из серии

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

Задача 1.16.21. 1. Блоха совершает случайное блуждание на целых

числах

{

. . . ,

−

1, 0, 1, . . .

}

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

шаг вправо с вероятностью p или на два шага влево. Пусть n

0 и T

—

время первого достижения положения n, если блоха выходит из нуля. По

кажите, что производящая функция

(s)

P (T

k) удовлетворяет

уравнению

(s)

= {ϕ

(s)

}

, где

(s)

= ϕ

(s) и

−

2. Покажите, что блоха (с вероятностью 1) допрыгает до состояния 1,

если p

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

блохе, чтобы оказаться в состоянии 1.

Решение. 1. Можно записать

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

где

—

интервал времени между первым попаданием в состояние k

−

и первым попаданием в состояние k. Благодаря строго марковскому свой

ству

∼

, где T

—

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

состояния 0. Используя пространственную однородность переходов, по

лучим, что

E (e

...

))

= ϕ

(s) E

−

(

(s))

∀

−

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

= ∞

) нулю или положительна. Единственное отличие заключается

в том, что во втором случае

= ϕ

(s)

| |

→

−

< ∞

)

2. Для

(s)

= ϕ

(s), взяв условные вероятности по первому скачку,

получим

(s)

−

p)s

(s)

−

p)s(

(s))

Значит, величина

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

−

− Φ +

(

Φ −

1) ((1

−

Φ −

Корни этого уравнения имеют вид

Φ =

−

4p(1

−

2(1

−

При p

3 два последних корня по модулю больше 1, поэтому

Φ =

и T

< ∞

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

Наконец, положим

M :

= ϕ

(s)



→

−

Тогда

−

3(1

−

При p

3 подстановка

Φ =

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

−

В частности, это доказывает, что M

= ∞

при p

Задача 1.16.22. Из лаборатории поступили 2 независимые последова

тельности наблюдений Y

, Y

, . . . и Z

, Z

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

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

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

значения 1 или 0 с неизвестными вероятностями успеха

P (Y

−

P (Y

0) и q

P (Z

−

P (Z

0), i

где 0

1, 0

1. Для того чтобы решить, какая из вероятностей p

и q больше, мы применяем следующий тест: выбираем натуральное число

M и прекращаем наблюдения в первый такой момент времени n, что или

. . .

−

. . .

)

или

. . .

−

. . .

)

= −

в первом случае мы принимаем решение, что p

q, а во втором

—

что

q. Покажите, что если p

q, то вероятность ошибки (т. е. вероятность

решить, что p

q) равна (1

)

−

, где

p(1

−

q)q

−

Решение. Определим ц.м.д.в. X

−

)

. . .

−

) на

{−

M, . . . , M

}

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

p(1

−

q), p

−

q(1

−

p), p

−

p) (1

−

q),

= −

1, . . . , M

−

где

−

M и M

—

поглощающие состояния. Мы хотим вычислить h

, где h

(попасть в

−

M до попадания в M). Получим уравнения

−

q(1

−

p)h

−

(pq

−

p) (1

−

q))h

p(1

−

q)h

−

При u

−

получим

−

. . .





−

где

p(1

−



q(1

−

p). Тогда

−

При i

−

1 получаем

−

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

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

−

= −

−

Тогда

−

Задача 1.16.23. В вершинах приведенного ниже графа (см. рис. 1.48)

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

ко одна лампочка.

Рис. 1.48

Пусть X

обозначает номер лампочки, которая горит в момент времени

0. Процесс эволюционирует следующим образом. Если X

i, то

лампочку, которая загорится в момент времени n

1, выбирают (с равной

вероятностью) среди вершин, которые соединены ребром с i. Например,

если лампочка C горела в момент времени n, то одна из лампочек R

, R

, L

загорится с вероятностью 1

4 в момент времени n

1. Покажите,

что P (X

) сходится к пределу при n

→ ∞

, и найдите этот предел.

При X

C найдите среднее количество раз, когда лампочка R

заго

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

Предположим теперь, что длина интервала времени, в течение которого

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

чайной величиной со средним 2

7 и последовательные моменты включения

лампочек независимы. Пусть в момент t

0 включается лампочка C.

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

от C, прежде, чем снова загорится лампочка C.

Решение. Рассматриваемая ц.м.д.в.

—

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

конечном графе. Она обратима по отношению к стационарному распре

делению

(

), где

и v

—

кратность вершины i. В данном примере

, 1

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

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

циклы длиной 2 и 3 (взаимно простые), она апериодична. Тогда при n

→ ∞

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

(n)

сходится к

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

P (X

j) также сходится к

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

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

. Таким образом, P (X

)

→

32.

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

4. Это следует из теоремы 1.7.7, утверждающей, что для

неприводимой положительно возвратной цепи Маркова со стацио-

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

справедливы равенства

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

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

горит лампочка, равно 2

7, мы сразу получаем ответ

(

)

Или, среднее время возвращения m

в состояние C в неприводимой

положительно возвратной цепи равно 1

8 (теорема 1.7.8). Тогда

(время, проведенное вне C до возвращения в C)

Рисунок симметричен, поэтому

(время, проведенное справа от C до возвращения в C)

что дает тот же ответ 1 для цепи с непрерывным временем.

Задача 1.16.24. Рассмотрим ц.м.д.в. на множестве I

= {

0, 1, 2, . . .

}

с переходными вероятностями p

i,i

, p

i,0

−

, i

0, где (a

)

—

последовательность таких неслучайных чисел, что 0

1 для всех i.

Пусть b

1, b

. . . a

−

, i

1. Покажите, что цепь

а) возвратна тогда и только тогда, когда b

→

0 при i

→ ∞

;

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

< ∞

; если

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

Решение. Так как цепь неприводима, можно рассмотреть фиксиро

ванное состояние, скажем 0. Пусть T

—

первый момент попадания в 0:

inf

{

1: X

}

. Рассмотрим P

< ∞

). Мы имеем

. . . a

−

< ∞

)

lim

→∞

−

lim

→∞

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

тогда и только тогда, когда b

→

0. Таким образом, состояние 0 возвратно

тогда и только тогда, когда b

→

0. Далее,

∞

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

< ∞

Уравнения инвариантности таковы:

∞

−

, i

следовательно,





−

Задача 1.16.25. Приведите примеры обратимых цепей Маркова.

Решение. Не каждая цепь обратима: пример

—

матрица P конечного

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

столбцам и строкам равны 1), и

—

равномерное распределение, но P

. Например,

4 1

0 1

2 1

4 1

4 0

С другой стороны, существуют целые классы обратимых цепей Мар

кова:

а) все (2

цепи;

б) конечные цепи, у которых P

P: в этом случае матрица P является

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

является инвари

антным, более того,

и P находятся в состоянии детального баланса;

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

которых

1(i и j сообщаются)

где v

—

кратность вершины i (число инцидентных ребер);

г) процессы рождения и гибели с вероятностями перехода p

−

и суммой

. . .

< ∞

;

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

здесь

−

. . .

, i

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

Задача 1.16.26. Частица совершает случайное блуждание на множе

стве

{

0, 1, 2, . . .

}

. Если в момент времени n частица находится в состоянии

1, то в момент времени n

1 она перемещается на один шаг влево

с вероятностью p, на один шаг вправо с вероятностью r или остается на

прежнем месте с вероятностью q

−

r. Если частица находится

в состоянии 0, то она совершает шаг вправо с вероятностью r или оста

ется в состоянии 0. Покажите, что при p

r такая цепь положительно

возвратна и найдите для этого случая инвариантное распределение. Опре

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

невозвратной.

Решение. Мы хотим показать, что цепь невозвратна, когда 0

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

0, и положительно возвратна,

когда p

0 (цепь, очевидно, положительно возвратна, когда r

и невозвратна, когда p

0, r

0 ). В случае положительной возвратности

уравнения детального баланса

определяют инвариантную меру

, которую можно нормировать

тогда и только тогда, когда r

p; при этом







−



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

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

P (попасть в 0

i). Получим уравнения

1, (p

r)h

−

, i

минимальное неотрицательное решение которых имеет вид





, i

0, при p

≡

1, i

0, при p

Но

< ∞

)

−

r) P

< ∞

)

, т. e. P

< ∞

)

что и дает искомый ответ.

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

Задача 1.16.27. Жили

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

Неразлучные друзья, делили они и кров, и пищу. И все бы хорошо, да

одна беда

—

от блох не могли избавиться. Блохи, общей численности N,

тоже были у них общими

—

перепрыгивали с одной собаки на другую...

В каждый момент времени ровно одна блоха перепрыгивает с одной собаки

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

из N возможных, каждый такой выбор не зависит от всех предыдущих.

Пусть X

—

это число блох на черной собаке в момент времени n.

Покажите, что последовательность X

= {

: n

}

образует ц.м.д.в. и

выпишите ее вероятности перехода. Покажите, что инвариантное распре

деление задается как





, k

0, 1, 2, . . . , N.

Решение. Находим p

i,i

−

, p

i,i

−

. Это цепь Маркова,

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

дущих событий. Уравнения детального баланса

i,i

1,i

имеют

решение

−

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

× ··· ×

−

× ··· ×

Следовательно, для некоторого 0

N имеем

−

1))

−

2))

× ··· ×

−

× ··· ×

−

M)!M!

Из условия

1 следует, что

−

, и

−

, i

0, 1, . . . , N.

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

Bin(N, 1

2).

A Delicate Detailed Balance

Деликатный детальный баланс

(Из серии

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

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

Задача 1.16.28. Конечный связный граф G состоит из множества вер

шин V, множества ребер E и не содержит петель или кратных ребер.

Частица совершает случайное блуждание на V, двигаясь на каждом шаге

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

выбрана с одинаковой вероятностью, независимо от предыдущих шагов.

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

), где d

—

кратность вершины v.

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

; в каж

дый момент времени она с одинаковой вероятностью может делать любые

(дозволенные для ладьи) шаги. Каково среднее время возвращения ладьи

в угол доски?

Решение. Так как граф G связный, цепь конечна и неприводима, т. е.

положительно возвратна. Следовательно, существует единственное инва

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

)

удовлетворяет уравнениям детального баланса, так как d

v,v

∀

v, v

∈

V. Значит, оно инвариантно, и данная цепь

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

есть единственное инвариантное распреде

ление.

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

определяет m

, т. е. среднее время возвращения в k (см. теорему ??).

Если ладья находится в углу доски или на любом из 64 квадратов, то d

14, v

∈

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

| =

угловое

, m

угловое

64.

Шахматная доска состоит из 8

8 клеток. Допустимыми шагами являются шаги любой

длины, параллельные сторонам доски.

Глава 2

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

временем

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

матрицы

Специалисты по марковским процессам любят

делать это, используя цепи

(Из серии

Как они делают это

Определение 2.1.1. Назовем Q

матрицей на конечном или счет

ном пространстве состояний I матрицу с действительными элементами

, i, j

∈

I), обладающую следующими свойствами:

—

диагональные элементы неположительны, q

0, i

∈

—

внедиагональные элементы неотрицательны, q

0, i

j, i, j

∈

—

имеет место условие баланса:

−

∈

I : j

, т. е.

∀

∈

Для i

j значение q

—

это скорость перехода из состояния i в j.

Величину

−

j:j

обозначим q

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

скорость перехода из состояния i). Будем обозначать Q

матрицу просто

Q (общеупотребительное сокращение). Как и в гл. 1, I будет обозначать

единичную матрицу.

Записывая в общей теории марковских цепей с непрерывным временем

условие баланса

∈

I:j

= −

, предполагаем, что

j:j

< ∞

. Однако

существенную часть теории можно развить, если равенство в условии

баланса ослаблено до верхней оценки

0, т. е. q

j : j

∀

∈

Тогда Q

матрица, удовлетворяющая условию баланса, называется кон-

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

неконсервативные Q

матрицы рассматриваться не будут; см. рис. 2.1 а).

Как и ранее, Q

матрица порождает диаграмму, на которой стрелка i

→

присутствует тогда и только тогда, когда q

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

Рис. 2.1

Пример 2.1.2. Нулевая матрица







0 . . . 0

. . .

0 . . . 0







Соответствующая диаграмма не имеет стрелок (т. е. состоит из изолиро

ванных точек).

Пример 2.1.3. Матрица размера 2

2 в общем случае имеет вид



−



, ,

В некоторых важных примерах из этой главы Q

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

бесконечна. Однако мы на время сосредоточимся на конечных матрицах.

Интересная матричная функция

—

это матричная экспонента e

exp(tQ):

∞

(tQ)

∞

(tQ)

, т. е. (e

)

∞

)

. (2.1.1)

Для конечной матрицы Q параметром t в соотношении (2.1.1) может

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

с непрерывным временем (ц.м.н.в.) будем предполагать, что t

0. Этот

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

|| =



∞

(tQ)



∞

(tQ)

∞

exp(

|||

)

< ∞

Основные свойства матричной экспоненты немедленно вытекают из

определения:

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

матрицы 211

а) e

s)Q

, s, t

∈ R

(в частности, e

−

)

−

); это

свойство обобщает стандартное мультипликативное свойство экспоненци

альной функции x

7→

: e

y)a

;

б) функция e

непрерывна (на самом деле и дифференцируема) по

∈ R

, причем полагаем e

I; точнее,

Q, t

∈ R

, т. е.

)

(Qe

)

. Более того,

, t

∈ R ∀

0, 1, . . . ;

это снова обобщение стандартного скалярного уравнения для скалярной

экспоненты

a, x

∈ R

;

в) det e

t(tr Q)

, t

∈ R

(это свойство доказывается сложнее, см.

далее).

Следующее утверждение уточняет свойства а) и б) для t, s

Теорема 2.1.4. Пусть Q

—

конечная Q-матрица. Семейство мат-

риц

P(t)

, t

0, (2.1.2)

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

г) полугрупповое свойство

P(t

P(s)P(t), s, t

0; (2.1.3)

д) P(t)

—

единственное решение уравнений

P(t)

P(t)Q, t

0, прямое уравнение,

P(t)

QP(t), t

0, обратное уравнение,

(2.1.4)

где P(0)

е)

∀

0, 1, 2, . . .

P(t)

P(t)Q

P(t), в частности

P(t)



. (2.1.5)

Д о к а з а т е л ь с т в о. Свойство г) прямо следует из определения мат

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

((t

s)Q)

−

(tQ)

(sQ)

−

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

Свойство е) можно доказать, итерируя уравнение (2.1.4):

P(t)

−



P(t)





−

P(t)



. . .

P(t)Q

P(t).

Поэтому докажем только свойство д), для чего запишем

P(t)

∞

−

1)!

∞

(tQ)

−

1)!

QP(t)

P(t)Q. (2.1.6)

Заметим, что равенство (2.1.6) имеет место и для e

−

= −

−

= −

−

Начальное условие P(0)

I также проверяется непосредственно: для

0 все члены в соотношении (2.1.1) обращаются в нуль, кроме k

Доказывая единственность, предположим, что M(t)

—

некоторое реше

ние уравнения

M(t)

M(t)Q, причем M(0)

I. Тогда

(M(t)e

−

)



M(t)



−

M(t)

−

M(t)Qe

−

M(t) (

−

)

M(t)Qe

−

M(t)Qe

−

0. (2.1.7)

Поэтому матрица M(t)e

−

не изменяется по t, а в момент t

0 она

равна I. Значит, M(t)e

−

≡

I, и

M(t)

Те же аргументы применимы к уравнению

M(t)

QM(t).

Замечание 2.1.5. Для конечной Q

матрицы уравнение (2.1.3) верно

для любых t, s

∈ R

(и на самом деле является групповым свойством).

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

и обратного уравнений мы использовали экспоненту e

−

, т. е. обратили

знак tQ; см. соотношение (2.1.7). Однако нам нужно неотрицательное t

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

Теорема 2.1.6. Если Q

—

конечная матрица, то P(t)

—

стохастическая матрица для любого t

0 тогда и только тогда,

когда Q является Q-матрицей, т. е. P(t) имеет все неотрицательные

элементы, сумма которых по строкам равна 1:

0, и

(t)

1. (2.1.8)

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

матрицы 213

Д о к а з а т е л ь с т в о. Начнем с доказательства достаточности, т. е.

предположим, что Q является Q

матрицей. Пусть вначале t мало и по

ложительно. Для малых t

0 имеем

P(t)

o(t), т. е. p

(t)

o(t).

Значит, для малых t

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

(t)

0 и p

(t)

для i

j, если q

Далее, если q

0, то

(t)

(2)

o(t

где q

(2)

—

это элемент с индексами i и j матрицы Q

. Заметим, что

(2)

так как в сумме

нет отрицательных слагаемых (они могли бы

появиться при k

i или k

j, но при этом q

0, что уничтожает их).

Рис. 2.2

Таким образом, видим, что если q

0, то для малых

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

(t)

0 при условии, что

(2)

0. Продолжая в том же духе, без труда выводим,

что для малых t

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

(t)

если для некоторого n элемент q

(n)

матрицы Q

положи

телен. Условие положительности q

(n)

0 для заданного n

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

→

. . .

→

−

→

j из i в j длины n. Иными словами,

состояние i сообщается с j.

Рис. 2.3

А что, если q

(n)

≡

0? Тогда i не сообщается с j и p

0. В любом случае

для малых t

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

(t)

0 для всех состояний

i, j.

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

Наконец, сумма элементов в каждой строке матрицы Q нулевая, а тогда

то же верно и для Q

для всех n

(n)

j,l

−





0. (2.1.9)

Значит, сумма элементов в каждой строке матрицы P(t) равна 1:

P(t)

∞

сумма по строкам равна 1 сумма по строкам равна 0,

(это рассуждение верно для всех t

∈ R

). Таким образом, установлено, что

для малых t

0 матрица P(t)

—

стохастическая. Но тогда это верно для

всех t

0, так как в силу полугруппового свойства

P(t)





. . . P





| {z }

n раз



i

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

Этим заканчивается доказательство достаточности в теореме 2.1.6.

Обратно, если P(t) имеет единичную сумму по строкам для любого

0, то

(t)

(QP(t))

Так как P(0)

I, из полученного равенства следует, что

Аналогично если для некоторых i

j элемент p

(t) неотрицателен для

любого t

0, то q

0. Это означает, что Q является Q

матрицей. Этим

заканчивается доказательство необходимости и завершается доказатель

ство теоремы 2.1.6.

Пример 2.1.7 (продолжение). Очевидно, что для нулевой Q

матрицы

P(t)

≡

Пример 2.1.8 (продолжение). Рассмотрим общую Q

матрицу размера



−



, ,

0. (2.1.10)

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

матрицы 215

Собственные значения

1,2

этой матрицы являются корнями уравнения

det



−



(

κ +

) (

κ +

)

− = κ

(

+ + κ

)

т. е.

= −

(

Матрицу можно привести к диагональному виду, а именно Q

UDU

−

где



0 0

− −



. (2.1.11)

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

P(t)

∞

−

∞

−



1 0

0 e

−

)



−

Если

= =

0, то P(t)

≡

I, в противном случае все элементы матрицы

имеют вид

(t)

−

)

причем

(0)

(t)

= −

(

Например, для верхнего левого элемента

−

(

= −

, B

Поэтому матрица P(t) равна

P(t)







−

(

−

(

−

(

−

(







; (2.1.12)

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

при t

→ ∞

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







+ +







Пример 2.1.9. Рассмотрим Q

матрицу размера 3

3 вида

−

1 1

2 1

−

2 1

0 1

−

для которой Q

−

3 11

−

3 2

Рис. 2.4

Характеристическое уравнение имеет вид

det

−

κ 1

2 1

−

κ 1

0 1

−

= −

(

κ +

(

κ +

+ κ

)

+ κ =

(

κ +



−

(

κ +

1) (

κ +



(

κ +



−κ

−

κ −



= κ



−κ

−

κ −



следовательно собственные значения равны

= −

√

Тогда

(t)

−

t(2

−

√

−

t(2

√

, i, j

1, 2, 3, t

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

матрицы 217

где постоянные A, B, C зависят от i, j и удовлетворяют уравнению

, так как P(0)

−



−

√



−



√



, так как

P(0)



−

√





√



(2)

, так как

P(0)

(2)

Например, для p

(t) мы имеем

, B

√

, C

−

√

и p

(t)

→

7 при t

→ ∞

Пример 2.1.10. Нетрудно привести пример Q

матрицы с кратными

корнями характеристического уравнения det(Q

−

0, а именно,







−

2 1 1 0

−

2 1 0

0 1

−

2 1

1 0 1

−







Корни здесь равны 0,

−

3; корень

−

3 имеет алгебраическую кратность

2, но геометрическая кратность каждого собственного значения равна 1.

Следовательно, элементы p

(t) матрицы перехода P

задаются фор

мулой

(t)

−

t)e

−

, i, j

1, 2, 3, 4,

где A

, B

, C

и D

—

постоянные. Чтобы найти их, нужно использовать

уравнение (2.1.5) при n

0, 1, 2, 3. В результате получаем матрицу P(t):







6te

−

14e

−

14e

−

6te

−

6 6e

−

6te

−

6te

−

3 6e

−

12te

−

12te

−

12e

−

12e

−

6te

−

6te

−







Замечание 2.1.11. Квадрат Q

матрицы не обязательно Q

матрица (то

же относится и к другим степеням Q

). Например, в случае (2

матрицы

(см. пример 2.1.8 выше) мы получаем:



−





+ −

−

− −



Эта матрица является Q

матрицей тогда и только тогда, когда

= =

0, т. е. Q

0. Однако сумма элементов по строкам матрицы Q

всегда

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

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

2.1.6 (см. соотношение (2.1.9)). Вообще

то, структуру матрицы Q

можно

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

мат

рицу Q. Скажем, чтобы вычислить элементы q

(2)

, рассмотрим все пути

→

j длины 2, перемножим q

и q

вдоль каждого из этих путей

и просуммируем полученные произведения. Далее, для Q

возьмем все пути

длины 3 и т. д.

С другой стороны, для любого a

0, произведение Q

матрицы и чис

ла a является Q

матрицей. Аналогично сумма Q

матриц Q

является

матрицей (значит, и любая линейная комбинация a

или, более

общим образом,

с неотрицательными коэффициентами a

является

матрицей).

Замечание 2.1.12. При заданной Q

матрице и любом t

0 матрица

P(t)

стохастическая по теореме 2.1.6. Поэтому существует ц.м.д.в.,

для которой P(t)

—

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

Однако неверно, что любую матрицу вероятностей перехода P можно

записать в виде e

для некоторой Q

матрицы и t

0. Здесь может

помочь упомянутое ранее свойство в) det e

t(tr Q)

. Например, матрицы

перехода



0 1

2 1



1 0 0

0 1 0

нельзя записать в виде e

, так как их определители нулевые или отрица

тельные, в то время как e

t(tr Q)

Теперь, используя полугрупповое свойство, докажем, что det e

t(tr Q)

. В самом деле,

det e

s)Q

det(e

)

(det e

) (det e

Далее, определитель det e

непрерывен (и даже дифференцируем) по t,

причем det e

det I

1. Значит, det e

для некоторого (действи

тельного) q. Наконец, чтобы найти q, заметим, что

det e



det(I

tQ)



Это означает, что q

—

коэффициент при t в многочлене det(I

tQ), а он

в точности равен tr Q. Заметим, что det e

→

0 при t

→ ∞

за исключением

случая, когда Q

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

матрицы 219

В других случаях необходим более глубокий анализ. Например, рас

смотрим матрицу перехода

0 1 0

0 0 1

1 0 0

Предположим, что ее можно записать в виде e

. В таком случае рас

смотрим матрицу перехода P

; очевидно, (P

)

P. Нетрудно

проверить, что для матрицы перехода

0 0 1

1 0 0

0 1 0

ее квадрат равен (P

)

P. Но для m

3 это невозможно (в матрице P

слишком много нулей). Действительно, матрица P описывает детермини

рованные передвижения. Отсюда следует, что и матрица P

должна быть

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

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

Итак, матрицу P нельзя представить в виде e

Замечание 2.1.13. Общее мультипликативное свойство матричной

экспоненты имеет вид

, (2.1.13)

если и только если матрицы Q

и Q

коммутируют, т. е. если Q

Отсюда следует полугрупповое свойство e

t)Q

, по

скольку матрицы (sQ) и (tQ) коммутируют.

Проверить равенство (2.1.13) можно прямыми вычислениями. Если

, то

)

k!(n

−

k)!

−

k!(n

−

k)!

−

. (2.1.14)

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

∞

(tQ

)

∞

(tQ

)

можно удачно переупорядочить и получить ряд

∞

(t(Q

))

, равный

t(Q

)

. Однако без предположении о коммутации Q

в разло

жении (2.1.14) возникнут перемежающиеся произведения матриц Q

и Q

и мы не получим формулы (2.1.14).