Кельберт М.Я., Сухов Ю.М. Вероятность и статистика в примерах и задачах. Том 2. Марковские цепи как отправная точка теории случайных процессов и их приложения
Подождите немного. Документ загружается.
220 Глава 2. Цепи Маркова с непрерывным временем
§ 2.2. Марковские цепи с непрерывным временем:
определения и основные конструкции.
Марковское и строго марковское свойства
The Markov Chain Saw Massacre
1
(Из серии
«
Фильмы, которые не вышли на большой экран
»
.)
Определение 2.2.1. Цепь Маркова с непрерывным временем, (конеч
-
ной) Q
-
матрицей Q и начальным распределением
—
это семейство таких
случайных величин (X
t
, t
>
0) со значениями в I, что
a) P (X
0
=
i)
=
i
,
б) для любых 0
<
t
1
<
t
2
<
. . .
<
t
n
и любых состояний i
0
, , . . . , i
n
∈
I
выполняется равенство
P (X
0
=
i
0
, X
t
1
=
i
1
, . . . , X
t
n
=
i
n
)
=
=
i
0
p
i
0
i
1
(t
1
)p
i
1
i
2
(t
2
−
t
1
) . . . p
i
n
−
1
i
n
(t
n
−
t
n
−
1
), (2.2.1)
где p
ij
(t)
—
элемент матрицы P(t)
=
e
tQ
.
Типичная траектория (путь) ц.м.н.в. (X
t
) показана на рис. 2.5.
Рис. 2.5
Далее мы увидим, что произвольная траектория а) проводит случайное
время, распределенное как
∼
Exp(q
i
), в состоянии i, а затем б) прыгает
в состояние j
6=
i с вероятностью q
ij
/
q
i
; см. (2.2.10).
Стандартное соглашение состоит в том, что траектории непрерывны
справа. Это означает, что с вероятностью 1 при всех t
>
0
lim
h
&
0
X
t
+
h
=
X
t
.
В случаях, когда это соглашение не слишком существенно, будем изоб
-
ражать траектории в виде непрерывных линий.
Важно понять, что событие
{
X
0
=
i
0
, X
t
1
=
i
1
, . . . , X
t
n
=
i
n
}
в соот
-
ношении (2.2.1) включает все траектории, проходящие через состояния
1
Ср. c названием фильма
«
Texas Chainsaw Massacre
»
(
«
Техасская резня бензопилой
»
).
§ 2.2. Марковские цепи с непрерывным временем... 221
Рис. 2.6
i
0
, i
1
, . . . , i
n
в моменты времени t
0
=
0, t
1
, . . ., t
n
; их поведение между
этими моментами времени произвольно.
Матрицу Q часто называют генератором цепи Маркова (X
t
) с непре
-
рывным временем. Саму цепь называют (
, Q)
-
цепью Маркова с непре
-
рывным временем (ц.м.н.в.) и генератором Q. Как и в случае цепей Мар
-
кова с дискретным временем (ц.м.д.в.), мы часто будем работать с цепями,
выходящими из фиксированного состояния i, т. е.
=
i
. Такая цепь
называется (
i
, Q)
-
ц.м.н.в.
Из определения 2.2.1 вытекают следующие свойства.
I. Матрица P(t)
=
(p
ij
(t)) называется матрицей перехода в момент
времени t. Она задает условные вероятности
p
ij
(t)
=
P (X
t
=
j
|
X
0
=
i)
=
P (X
t
+
s
=
j
|
X
s
=
i). (2.2.2)
В терминах траекторий p
ij
(t) задает полную вероятность всех путей из i
в j за время t.
Рис. 2.7
II. Отсутствие памяти у условных вероятностей. Оно состоит в том, что
P (X
t
n
=
j
|
X
t
n
−
1
=
i, X
t
n
−
2
=
i
n
−
2
, . . . , X
0
=
i
0
)
=
=
P (X
t
n
=
j
|
X
t
n
−
1
=
i)
=
p
ij
(t
n
−
t
n
−
1
), (2.2.3)
т. е. условная вероятность P (X
t
n
=
j
|
X
t
n
−
1
=
i, X
t
n
−
2
=
i
n
−
2
, . . . , X
0
=
i
0
)
не зависит от t
1
, . . . , t
n
−
1
и i
0
, i
1
, . . . , i
n
−
2
.
222 Глава 2. Цепи Маркова с непрерывным временем
Чтобы доказать равенство (2.2.3), нужно использовать определение
условной вероятности
P (X
t
n
=
j
|
X
t
n
−
1
=
i, X
t
n
−
2
=
i
n
−
2
, . . . , X
0
=
i
0
)
=
=
P (X
0
=
i
0
, . . . , X
t
n
−
1
=
i, X
t
n
=
j)
P (X
0
=
i
0
, . . . , X
t
n
−
1
=
i)
и подставить выражение из формулы (2.2.1).
III. Безусловная вероятность
P (X
t
=
j)
=
X
i
i
p
ij
(t)
= (
P(t)
)
j
(2.2.4)
задает полную вероятность множества траекторий, находящихся в состо
-
янии j в момент времени t.
Рис. 2.8
IV. Как и в случае дискретного времени, имеет место марковское свой-
ство, которое обеспечивает условную независимость прошлого и будущего
при фиксированном настоящем.
Теорема 2.2.2. Пусть (X
t
)
—
это ( , Q)-ц.м.н.в. Тогда для любого
заданного t
>
0 и любого состояния i при условии, что
{
X
t
=
i
}
,
прошлое (X
s
, 0
6
s
<
t) и будущее (X
t
+
s
, t
>
0) независимы и (X
t
+
s
)
является (
i
, Q)-ц.м.н.в.
V. Говорят, что
=
является стационарным распределением, если
и только если P (X
t
=
j)
=
j
для любых t, j, т. е. P(t)
≡
. При этом
вектор
-
строка
обращается в нуль под действием матрицы Q:
0
=
d
dt
P(t)
=
d
dt
P(t)
=
P(t)Q,
0
=
P(t)Q
|
t
=
0
=
Q.
(2.2.5)
Иными словами,
—
собственный вектор
-
строка матрицы Q с нулевым
собственным числом.
§ 2.2. Марковские цепи с непрерывным временем... 223
Рис. 2.9
VI. На самом деле любая (конечная) Q
-
матрица имеет стационар
-
ное распределение, т. е. собственная вектор
-
строка
=
(
i
) с нулевым
собственным значением и неотрицательными компонентами, для которых
P
i
i
=
1. В частности, 0 является собственным значением любой Q
-
мат
-
рицы.
VII. Как и в случае дискретного времени, если
P(t)
→ Π =
(1)
(2)
. . .
(m)
- - -
- - -
- - -
- - -
,
то каждая строка
(i)
является стационарным распределением:
(i)
P(t)
=
(
Π
P(t))
(i)
=
lim
→∞
P( )P(t)
(i)
=
lim
→∞
P(
+
t)
(i)
=
(i)
.
(2.2.6)
См. теорему 2.8.1 из § 2.8.
Например, если в примере 2.1.8 выполняется условие
+ >
0, то
=
+
,
+
(2.2.7)
является (единственным) стационарным распределением. Но при
= =
=
0 мы имеем P(t)
≡
I и любой вектор будет инвариантным.
VIII. Как и в случае дискретного времени, можно определить строго
марковское свойство. Назовем случайную величину T со значениями
в [0,
∞
] моментом остановки, если для любого t
>
0 событие
{
T
<
<
t
}
определяется набором (X : 0
6 <
t). Иными словами, индикатор
1(T
<
t) является функцией только от (X : 0
6 <
t).
224 Глава 2. Цепи Маркова с непрерывным временем
Рис. 2.10
Рис. 2.11
Once Upon a Stopping Time
2
(Из серии
«
Фильмы, которые не вышли на большой экран
»
.)
Примером момента остановки вновь является момент достижения под
-
множества состояний A
⊂
I:
H
A
=
inf[s
>
0: X
s
∈
A], (2.2.8)
поскольку
1(H
A
6
t)
=
1(
∃
s
∈
[0, t] : X
s
∈
A)
зависит только от (X , 0
6 6
t).
Мы будем особо интересоваться моментами достижения заданного со
-
стояния i (также называемыми моментами перехода в i, как и для
ц.м.д.в.).
H
i
=
inf [s
>
0: X
s
=
i]. (2.2.9)
Теорема 2.2.3. Пусть (X
t
)
—
( , Q)-ц.м.н.в. и T
—
момент оста-
новки. Тогда для любого состояния i при условии, что произошло
2
Ср. с названием фильма
«
Once Upon a Time
»
.
§ 2.2. Марковские цепи с непрерывным временем... 225
событие
{
T
< ∞
, X
T
=
i
}
, прошлое (X
t
, 0
6
t
6
T) и будущее
(X
t
+
T
, t
>
0) независимы и (X
t
+
T
, t
>
0)
—
это (
i
, Q)-ц.м.н.в.
Рис. 2.12 иллюстрирует случай, когда T
=
H
i
, где H
i
—
время перехода
в состояние i.
Рис. 2.12
A Passage Time to India
3
(Из серии
«
Фильмы, которые не вышли на большой экран
»
.)
IX. Ц.м.н.в. (X
t
) с генератором Q обладает следующими свойствами:
при условии, что X
t
=
i, q
i
= −
q
ii
>
0, остаточное время пребывания
R
i
в состоянии i имеет экспоненциальное распределение с парамет-
ром q
i
= −
q
ii
:
P (R
i
> |
X
t
=
i)
=
P (X
t
+
s
=
i
∀
0
6
s
< |
X
t
=
i)
=
e
−
q
i
.
Далее, в момент t
+
R
i
цепь совершает прыжок в состояние j с ве-
роятностью
b
p
ij
=
q
ij
/
q
i
:
P (X
t
+
R
i
=
j
|
X
t
=
i)
=
q
ij
q
i
. (2.2.10)
Это свойство будет проверено позже.
Если для состояния i выполняется условие q
i
=
0, то q
ij
=
0
∀
j;
такое состояние называется поглощающим. Соответствующая диаграмма
из стрелок не содержит стрелок, выходящих из состояния i.
Замечание 2.2.4. Определение 2.2.1 выделяет так называемую од-
нородную цепь Маркова. Здесь вероятности p
ij
(t) зависят только от
времени t, за которое совершается переход из состояния i в j. В более
общем случае неоднородных цепей нужно рассматривать вероятность
p
ij
(s, t
+
s), t, s
>
0, того, что состояние в момент t
+
s есть j, при условии,
что состояние в момент s есть i. Примеры таких цепей появятся в § 2.4.
3
Ср. с названием фильма
«
A Passage to India
»
226 Глава 2. Цепи Маркова с непрерывным временем
Рис. 2.13
Пример 2.2.5. Некий вирус может находиться в N
+
1 штамме 0, . . . , N.
Он сидит в своем штамме случайное время, распределенное как
∼
Exp ( ),
а затем с равными вероятностями мутирует в один из остальных штаммов.
Найдите вероятность того, что в момент времени t он будет сидеть в том
же штамме, что и в начальный момент,
P (в момент t штамм тот же, что и в момент 0).
Рис. 2.14
Решение. Стрелочная диаграмма ц.м.н.в. из условия задачи полностью
симметрична. На рис. 2.14 показаны только стрелки, выходящие из состо
-
яния 0. В силу симметрии
q
i
:
= −
q
ii
=
; q
ij
=
N
, 1
6
i, j
6
N
+
1, i
6=
j,
и
Q
=
−
/
N . . .
/
N
/
N
−
. . .
/
N
. . . . . .
/
N
/
N . . .
−
.
§ 2.2. Марковские цепи с непрерывным временем... 227
Нам нужно вычислить p
ii
(t)
=
(e
tQ
)
ii
. Очевидно, p
ii
(t)
=
p
11
(t)
∀
i, t, опять
же в силу симметрии.
Рассмотрим приведенную Q
-
матрицу размера 2
×
2 с состояниями 0
и 1:
e
Q
=
−
/
N
−
/
N
с собственными числами 0 и
= −
(N
+
1)
N
. Эту матрицу можно приве
-
сти к диагональному виду. Собственные вектор
-
строки имеют вид (1, 1)
и (N,
−
1). Поэтому
p
11
(t)
=
(e
t
˜
Q
)
11
=
A
+
Be
−
(N
+
1)
N
t
.
Как и в примере 2.1.8, если искать решение в виде A
+
Be
t
, то получим
такие значения:
A
=
1
N
+
1
, B
=
N
N
+
1
и
p
11
(t)
=
1
N
+
1
+
N
N
+
1
e
−
(N
+
1)
N
t
=
p
ii
(t).
В силу симметрии
p
ij
(t)
=
1
N
(1
−
p
ii
(t))
=
1
N
+
1
−
1
N
+
1
e
−
(N
+
1)
N
t
, i
6=
j.
Остается заключить, что
p
ij
(t)
−→
1
N
+
1
при t
→ ∞
(это равномерное дискретное распределение).
Пример 2.2.6. Блоха скачет по часовой стрелке от вершины к вершине
треугольника ABC; времена пребывания
—
независимые показательно рас
-
пределенные с параметром единица случайные величины. Найдите соб
-
ственные значения соответствующей Q
-
матрицы и выразите вероятности
перехода p
xy
(t), t
>
0, x, y
=
A, B, C, через эти корни характеристического
уравнения. Выразите суммы
S
0
(t)
=
∞
X
n
=
0
t
3n
(3n)!
, S
1
(t)
=
∞
X
n
=
0
t
3n
+
1
(3n
+
1)!
, S
2
(t)
=
∞
X
n
=
0
t
3n
+
2
(3n
+
2)!
,
через функции e
t
, e
−
t
/
2
, cos(
√
3t
/
2) и sin(
√
3t
/
2).
Найдите пределы
lim
t
→∞
e
−
t
S
j
(t), j
=
0, 1, 2.
228 Глава 2. Цепи Маркова с непрерывным временем
Какова связь между разложениями e
t
=
S
0
(t)
+
S
1
(t)
+
S
2
(t) и e
t
=
=
ch t
+
sh t?
Решение. Выпишем характеристический полином Q
-
матрицы
det
−
1
−
κ 1 0
0
−
1
−
κ 1
1 0
−
1
−
κ
!
=
(
−κ −
1)
3
+
1
= −κ
(
κ
2
+
3
κ +
3).
Корни (собственные числа) равны
κ =
0,
−
3
2
±
i
√
3
2
.
Поэтому диагональные переходные вероятности равны
p
xx
(t)
=
a
+
e
−
3t
/
2
b cos
√
3
2
t
+
c sin
√
3
2
t
, x
=
A, B, C,
где
a
=
p
xx
(
∞
)
=
1
3
(так как
=
(1
/
3, 1
/
3, 1
/
3)),
a
+
b
=
p
xx
(0)
=
1, следовательно, b
=
2
/
3,
−
3
2
b
+
√
3
2
c
=
˙
p
xx
(0)
=
q
xx
= −
1, следовательно, c
=
0.
Заметим, что Q
-
матрица имеет вид Q
=
A
−
I, где все элементы матрицы
A за исключением a
12
, a
23
и a
21
, являются нулевыми. Следовательно,
e
tQ
=
e
−
tI
e
tA
. Далее, заметим, что Q
3
=
I и все диагональные элементы
матрицы Q
k
равны 0, если k не делится на 3. Отсюда следует, что
p
xx
(t)
=
∞
X
n
=
0
e
−
t
t
3n
(3n)!
, x
=
A, B, C.
Таким образом,
S
0
(t)
=
∞
X
n
=
0
t
3n
(3n)!
=
1
3
e
t
+
2
3
e
−
t
/
2
cos
√
3
2
t
.
Аналогично вероятности p
AB
(t)
=
p
BC
(t)
=
p
CA
(t) равны
1
3
−
1
3
e
−
3t
/
2
cos
√
3
2
t
+
1
√
3
e
−
3t
/
2
sin
√
3
2
t
,
следовательно, S
1
(t)
=
∞
P
n
=
0
t
3n
+
1
(3n
+
1)!
равно
1
3
e
t
−
1
3
e
−
t
/
2
cos
√
3
2
t
+
1
√
3
e
−
t
/
2
sin
√
3
2
t
.
§ 2.2. Марковские цепи с непрерывным временем... 229
Наконец, вероятности p
AC
(t)
=
p
BA
(t)
=
p
CB
(t) равны
∞
X
n
=
0
e
−
t
t
3n
+
2
(3n
+
2)!
=
1
3
−
1
3
e
−
3t
/
2
cos
√
3
2
t
−
1
√
3
e
−
3t
/
2
sin
√
3
2
t
,
и S
2
(t)
=
∞
P
n
=
0
t
3n
+
2
(3n
+
2)!
равно
1
3
e
t
−
1
3
e
−
t
/
2
cos
√
3
2
t
−
1
√
3
e
−
t
/
2
sin
√
3
2
t
.
Пределы
lim
t
→∞
e
−
t
S
j
(t)
=
1
3
, j
=
0, 1, 2,
задают стационарное распределение
=
(1
/
3, 1
/
3, 1
/
3).
Разложение e
t
=
ch t
+
sh t появляется, если рассмотреть ц.м.н.в.
с Q
-
матрицей
−
1 1
1
−
1
,
т. е.
«
приведенный
»
вариант предыдущей цепи.
Пример 2.2.7. Рассмотрим Q
-
матрицу размера N
×
N вида
−
0 . . . 0 0
0
−
. . . 0 0
0 0
−
. . . 0 0
. . . . . . . . . . . . . . . . . . . . . .
0 0 0 . . .
−
0 0 0 . . . 0 0
=
−
1 1 0 . . . 0 0
0
−
1 1 . . . 0 0
0 0
−
1 . . . 0 0
. . . . . . . . . . . . . . . . . . . . . .
0 0 0 . . .
−
1 1
0 0 0 . . . 0 0
. (2.2.11)
См. рис. 2.15. Здесь состояние N является поглощающим: q
Ni
≡
0, или,
Рис. 2.15
что то же самое, q
NN
= −
q
N
=
0. При этом все матрицы Q
k
являются
верхними треугольными (так как отсутствует стрелка j
−
1
←
j). Значит,
таковой будет и матрица e
tQ
. Прямое уравнение имеет вид
˙
P(t)
=
P(t)Q,
начальное условие P(0)
=
I, поэтому
˙
p
ii
= −
p
ii
, p
ii
(0)
=
1, 1
6
i
<
N,
˙
p
ij
= −
p
ij
+
p
ij
−
1
, p
ij
(0)
=
0, 1
6
i
<
j
<
N,
˙
p
iN
=
p
iN
−
1
, p
iN
(0)
=
0, 1
6
i
<
N,
˙
p
NN
=
0, p
NN
(0)
=
1,
230 Глава 2. Цепи Маркова с непрерывным временем
и, поскольку, очевидно, p
ij
(t)
=
0 для всех i
>
j, это уравнение допускает
рекуррентное решение вида
из уравнения
˙
p
ii
= −
p
ii
следует, что p
ii
(t)
=
e
−
t
, для 1
6
i
<
N,
из уравнения
˙
p
ii
+
1
= −
p
ii
+
1
+
e
−
t
следует, что p
ii
+
1
(t)
=
te
−
t
, для
1
6
i
<
N,
а из уравнения
˙
p
ii
+
2
= −
p
ii
+
2
+
2
te
−
t
получаем p
ii
+
2
(t)
=
( t)
2
2
e
−
t
,
для 0
6
i
<
N
−
1 и т. д.
Общая формула
p
ij
(t)
=
( t)
j
−
i
(j
−
i)!
e
−
t
, 1
6
i
<
j
<
N
−
1,
и
p
iN
(t)
=
1
−
N
−
i
X
l
=
0
( t)
l
l!
e
−
t
, 0
6
i
<
N;
наконец,
p
NN
≡
1.
В матричной форме
P(t)
=
e
tQ
=
e
−
t
t
1
e
−
t
( t)
2
2!
e
−
t
. . .
P
l>N
( t)
l
l!
e
−
t
0 e
−
t
t
1
e
−
t
. . .
P
l>N
−
1
( t)
l
l!
e
−
t
. . . . . . . . . . . . . . .
0 0 0 0 1
. (2.2.12)
Видим, что при t
→ ∞
выполняется условие
p
ij
(t)
→
0
∀
0
6
i
<
j
<
N и p
iN
(t)
→
1
∀
0
6
i
<
N.
Таким образом,
lim
t
→∞
p
ij
(t)
=
jN
т. е. P(t)
→
0 0 0 . . . 1
0 0 0 . . . 1
. . . . . . . . . . . . . . .
0 0 0 . . . 1
∼
N
∼
N
.
.
.
∼
N
.
Здесь
N
—
вероятностное распределение, сосредоточенное в состоянии
N (цепь с течением времени заканчивает движение в состоянии N).
§ 2.2. Марковские цепи с непрерывным временем... 231
Полезное наблюдение состоит в том, что если q
i
=
0, то состояние
i поглощающее, т. е. p
ii
(t)
≡
1
∀
t
>
0 (и обратное утверждение также
верно).
Типичные траектории (
(0)
, Q) ц.м.н.в. представлены на рис. 2.16. Они
все прыгают вверх на одну единицу и согласно выше приведенному опи
-
санию со временем достигают состояния N, где и остаются навсегда.
Рис. 2.16
Пример 2.2.8. Если взять Q
-
матрицу вида
−
0 . . . 0 0
0
−
. . . 0 0
0 0
−
. . . 0 0
. . . . . . . . . . . . . . . . . .
0 0 0 . . .
−
0 0 . . . 0
−
=
−
1 1 0 . . . 0 0
0
−
1 1 . . . 0 0
0 0
−
1 . . . 0 0
. . . . . . . . . . . . . . . . . .
0 0 0 . . .
−
1 1
1 0 0 . . . 0
−
1
, (2.2.13)
то она образует цикл, см. рис. 2.17.
Рис. 2.17
Матрица P(t)
=
e
tQ
здесь будет иметь периодическую структуру:
p
ij
(t)
=
p
i
+
l,j
+
l
(сложение по mod N)
∀
i, j, l,
232 Глава 2. Цепи Маркова с непрерывным временем
Действительно, суммируя переходные вероятности по всем состояниям,
которые
«
проектируются
»
в состояние j, когда при движении вдоль дей
-
ствительной временной оси образуется цикл, получим ответ
p
ij
(t)
=
p
1,j
+
1
−
i
(t)
=
∞
X
l
=
0
( t)
j
−
i
+
lN
(j
−
i
+
lN)!
e
−
t
, 1
6
i
6
j
6
N,
и
p
ij
(t)
=
p
1,N
+
j
−
i
+
1
(t), 1
6
j
<
i
6
N.
При t
→ ∞
распределение p
ij
(t) стремится к равномерному дискретному
распределению
i
=
1
/
N
∀
i. Это единственное решение уравнения Q
=
=
0, удовлетворяющее условиям
i
>
0,
N
P
i
=
1
i
=
1.
Пример 2.2.9. Многие свойства, которые обсуждались ранее, можно
без большого труда перенести на бесконечные матрицы. Например, рас
-
смотрим бесконечную Q
-
матрицу вида
Q
=
−
0 0 . . .
0
−
0
.
.
.
0 0
−
.
.
.
. . .
.
.
.
.
.
.
.
.
.
.
.
.
=
−
1 1 0 0 . . .
0
−
1 1 0
.
.
.
0 0
−
1 1
.
.
.
. . .
.
.
.
.
.
.
.
.
.
.
.
.
, (2.2.14)
(см. рис. 2.18).
Рис. 2.18
В этом примере матрица Q
k
вновь является верхней треугольной при
всех k
=
0, 1, . . ., значит, таковой является и матричная экспонента
P(t)
=
e
tQ
=
∞
X
k
=
0
t
k
Q
k
k!
, t
>
0. (2.2.15)
Элементы p
ii
+
l
(t) при l
>
0 требуется вычислить, но элементы p
ii
−
l
(t) уж
точно тождественно равны нулю
P(t)
=
p
00
(t) p
01
(t) p
02
(t) . . .
0 p
11
(t) p
12
(t) . . .
0 0 p
22
(t) . . .
0
.
.
.
.
§ 2.2. Марковские цепи с непрерывным временем... 233
Чтобы найти элементы p
ii
+
l
(t), можно использовать прямое или обратное
уравнения
˙
P(t)
=
P(t)Q или
˙
P(t)
=
QP(t) (2.2.16)
с начальным условием P(0)
=
I. Для l
=
0 (т. е. для диагональных элемен
-
тов) уравнения принимают вид
˙
p
ii
= −
p
ii
(t), p
ii
(0)
=
1,
откуда следует, что
p
ii
(t)
=
e
−
t
∀
i
=
0, 1, . . . и t
>
0. (2.2.17)
Для l
=
1 (один шаг вправо от главной диагонали) получим
˙
p
ii
+
1
= −
p
ii
+
1
(t)
+
p
ii
(t) (прямое уравнение),
˙
p
ii
+
1
= −
p
ii
+
1
(t)
+
p
i
+
1i
+
1
(t) (обратное уравнение),
откуда следует, что
p
ii
+
1
(t)
=
te
−
t
∀
i
=
0, 1, . . . , и t
>
0. (2.2.18)
В общем случае, для любых l
=
0, 1, . . . имеем
˙
p
ii
+
l
= −
p
ii
+
l
(t)
+
p
ii
+
l
−
1
(t) (прямое уравнение),
˙
p
ii
+
l
= −
p
ii
+
l
(t)
+
p
i
+
1i
+
l
(t) (обратное уравнение),
что приводит к формулам
p
ii
+
l
(t)
=
( t)
l
l!
e
−
t
∀
i
=
0, 1, . . . , и t
>
0. (2.2.19)
Наконец, поскольку переходы i
→
j для j
<
i невозможны,
p
ii
−
l
(t)
=
0
∀
i
=
0, 1, . . . , l
=
1, 2, . . . и t
>
0. (2.2.20)
В матричной форме
P(t)
=
e
−
t
t
1
e
−
t
( t)
2
2!
e
−
t
. . .
0 e
−
t
t
1
e
−
t
.
.
.
0 0 e
−
t
.
.
.
. . .
.
.
.
.
.
.
.
.
.
=
закон Пуассона с t
0
закон Пуассона с t
0 0
закон Пуассона с t
. . . . . . . . . . . . . . . . . . . . . . . .
.
(2.2.21)
234 Глава 2. Цепи Маркова с непрерывным временем
Эквивалентным образом, можно получить тот же результат, перейдя
к пределу
P(t)
=
e
tQ
=
lim
N
→∞
e
tQ
(N)
, t
>
0, (2.2.22)
где Q
(N)
и p
(N)
(t)
=
e
tQ
(N)
—
это матрицы вида (2.2.11) и (2.2.12) соответ
-
ственно.
Матрицы P(t), t
>
0, определенные формулой (2.2.21), имеют свой
-
ства, перечисленные в теореме 2.1.4. Очевидно, каждая матрица P(t)
стохастическая, задающая набор переходных вероятностей на
Z
+
. Можно
повторить определение 2.2.1 для I
= Z
+
= {
0, 1, . . .
}
и (бесконечной)
матрицы переходных вероятностей P(t), определенных формулой (2.2.21).
Типичные траектории (
(0)
, Qt)
-
ц.м.н.в. (выходящей из 0) изображены на
рис. 2.16. Все скачки ц.м.н.в. равны 1.
Суммируем вышесказанное.
Теорема 2.2.10. Пусть матрица Q имеет вид (2.2.14). Семейство
матриц P(t) из соотношения (2.2.21) удовлетворяет равенствам
(2.2.15) и (2.2.22) и имеет следующие свойства:
а) полугрупповое свойство
P(t
+
s)
=
P(s)P(t), s, t
>
0; (2.2.23)
б) P(t)
—
единственное решение уравнений
d
dt
P(t)
=
P(t)Q, t
>
0, прямое уравнение,
d
dt
P(t)
=
QP(t), t
>
0, обратное уравнение,
(2.2.24)
причем P(0)
=
I;
в)
d
k
dt
k
P(t)
t
=
0
=
Q
k
∀
k
=
1, 2, . . ..
Прямые и обратные уравнения часто называют уравнениями Колмогорова, по имени
Андрея Николаевича Колмогорова (1903
–
1987), великого русского математика, внесшего
важный вклад во многие области теоретической и прикладной математики. Колмогоров из
-
вестен как создатель строгого обоснования всей теории вероятностей, и более 50 лет он
был признанным лидером советского математического сообщества. В отличие от некоторых
других советских математиков и физиков того периода, он никогда не занимал особо высо
-
ких административных постов и не участвовал непосредственно в ядерной или космической
программах. Однако он имел непререкаемый авторитет как в математике, так и в вопросах,
выходящих за ее пределы, и служил образцом для подражания в российском и международ
-
ном интеллектуальном сообществе.
Другое имя, связанное с этими уравнениями,
—
Уильям Феллер (1906
–
1970), известный
американский математик, родившийся в Загребе (Хорватия). Он существенно прояснил роль
прямых и обратных уравнений в теории вероятностей и ее многочисленных приложениях. Он
§ 2.3. Процесс Пуассона 235
также написал классический учебник в двух томах [F], по
-
видимому никем не превзойденный
до настоящего времени.
§ 2.3. Процесс Пуассона
Приключение Пуассона
4
(Из серии
«
Фильмы, которые не вышли на большой экран
»
.)
Процесс Пуассона был введен в примере 2.2.9 в предыдущем парагра
-
фе. Ввиду его важности введем специальные обозначения.
Определение 2.3.1. Пусть
>
0 фиксировано. Семейство случайных
величин (N
t
, t
>
0) со значениями в
Z
+
= {
0, 1, . . .
}
называется процес
-
сом Пуассона с интенсивностью
, если
а) N
0
=
0,
б) для любых 0
<
t
1
<
t
2
<
. . .
<
t
n
и любых неотрицательных целых
чисел i
1
, . . . , i
n
∈
I выполняется соотношение
P (N
t
1
=
i
1
, . . . , N
t
n
=
i
n
)
=
p
0i
1
(t
1
)p
i
1
i
2
(t
2
−
t
1
) . . . p
i
n
−
1
i
n
(t
n
−
t
n
−
1
), (2.3.1)
где p
ij
(t)
—
элементы матрицы P(t)
=
e
tQ
, определенной в формуле (2.2.21).
Мы будем кратко обозначать процесс Пуассона с интенсивностью
через ПП ( ), а его распределение
—
просто через P
=
P . Процесс ПП ( )
имеет кусочнопостоянные, неубывающие (непрерывные справа) траекто
-
рии, выходящие из 0.
Из равенства (2.3.1) следует, что ПП (
) имеет независимые прираще-
ния N
t
j
+
1
−
N
t
j
на непересекающихся интервалах (t
j
, t
j
+
1
) и эти приращения
распределены по закону Po(
(t
j
+
1
−
t
j
)). В самом деле, полагая t
0
=
0
и i
0
=
0, получим, что вероятность P (N
t
1
=
i
1
, . . . , N
t
n
=
i
n
) совпадает
с P (N
t
1
−
N
t
0
=
i
1
−
i
0
, . . . , N
t
n
−
N
t
n
−
1
=
i
n
−
i
n
−
1
), т. е. с вероятностью того,
что приращения примут заданную последовательность значений. Затем,
повторяя определение 2.3.1, получим, что для любых 0
=
t
0
<
t
1
<
. . .
<
t
n
и любых чисел 0
=
i
0
, i
1
, . . . , i
n
∈ Z
+
выполняется соотношение
P (N
t
1
−
N
t
0
=
i
1
−
i
0
, . . . , N
t
n
−
N
t
n
−
1
=
i
n
−
i
n
−
1
)
=
=
n
−
1
Q
k
=
0
( (t
k
+
1
−
t
k
))
i
k
+
1
−
i
k
(i
k
+
1
−
i
k
)!
e
−
(t
k
+
1
−
t
k
)
, если 0
6
i
1
6
. . .
6
i
n
,
0 в остальных случаях.
(2.3.2)
4
Игра слов, ср.
«
Приключения Посейдона
»
.
236 Глава 2. Цепи Маркова с непрерывным временем
Рис. 2.19
Обратно, из свойства (2.3.2) следует свойство (2.3.1). Этот факт важен
для нашего понимания пуассоновских процессов.
Прежде чем двигаться дальше, напомним основные свойства показа
-
тельного распределения Exp( ):
а) плотность распределения равна f(x)
=
e
−
x
1(x
>
0),
б) функция распределения равна
F(x) :
=
P (X
<
x)
=
x
Z
−∞
f(y) dy
=
(1
−
e
−
x
)1(x
>
0),
в)
«
хвост
»
функции распределения равен
1
−
F(x)
=
P (X
>
x)
=
(
e
−
x
, x
>
0,
1, x
6
0,
г) среднее значение равно EX
=
∞
R
0
xf(x) dx
=
1
,
д) дисперсия равна E (X
−
EX)
2
=
∞
R
0
x
−
1
2
f(x) dx
=
1
2
,
е) если X
1
∼
Exp(
1
), . . . , X
n
∼
Exp(
n
) и эти с.в. независимы в сово
-
купности, то W
=
min[X
1
, . . . , X
n
]
∼
Exp
n
P
i
=
1
i
; действительно,
P (W
>
x)
=
P (X
i
>
x, 1
6
i
6
n)
=
n
Y
i
=
1
P (X
i
>
x)
=
n
Y
i
=
1
e
−
i
x
,
§ 2.3. Процесс Пуассона 237
ж) свойство отсутствия памяти:
P (X
>
t
+
s
|
X
>
s)
=
e
−
(t
+
s)
e
−
s
=
e
−
t
=
P (X
>
t)
∀
t, s
>
0;
это свойство часто интерпретируют так: если время жизни (или время пре
-
бывания) превысило заданный уровень s, то при этом условии остаточное
время жизни X
−
s по
-
прежнему имеет распределение Exp( ).
Рис. 2.20
Далее мы обозначаем ПП ( ) либо N
t
, либо N(t) в зависимости от того,
какое обозначение более подходит для конкретного случая. Следующая
теорема
—
это основной результат данного параграфа.
Теорема 2.3.2. Процесс ПП (
) (N(t)) можно охарактеризовать
тремя эквивалентными способами: это процесс со значениями
в
Z
+
= {
0, 1, . . .
}
с N
0
=
0 и
а) процесс, удовлетворяющий соотношениям (2.3.1), где P(t)
=
=
(p
ij
(t)), t
>
0,
—
стохастическая матрица, заданная в формуле
(2.2.21); или, что эквивалентно, процесс с независимыми пуассонов-
скими приращениями:
N(t
k
)
−
N(t
k
−
1
)
∼
Po( (t
k
−
t
k
−
1
)),
∀
0
<
t
1
<
. . .
<
t
n
, (2.3.3)
или
б) процесс с независимыми приращениями и такими инфините-
зимальными вероятностями: для любого t
>
0
P (N(t
+
h)
−
N(t)
=
0)
=
1
−
h
+
o(h),
P (N(t
+
h)
−
N(t)
=
1)
=
h
+
o(h),
P (N(t
+
h)
−
N(t)
>
2)
=
o(h)
(2.3.4)
при h
&
0, где слагаемые o(h) не зависят от t,
или
в) процесс, проводящий случайное время S
i
∼
Exp( ) в каждом
состоянии i независимо друг от друга, а затем попадающий в со-
стояние i
+
1, i
=
0, 1, . . .
238 Глава 2. Цепи Маркова с непрерывным временем
Говорят, что а)
—
это определение (или характеризация) в терминах
независимых пуассоновских приращений, б)
—
определение в терминах
инфинитезимальных вероятностей, в)
—
в терминах показательных времен
пребывания.
Замечание 2.3.3. Характеризацию б) можно сформулировать в экви
-
валентном виде:
б
0
) процесс ПП ( ) (N
t
)
—
это процесс со значениями в
Z
+
с N
0
=
=
0 и следующими инфинитезимальными условными вероятностями:
для любых t
>
0 и i
=
0, 1, . . .
P (N(t
+
h)
−
N(t)
=
0
|
N(t)
=
i)
=
1
−
h
+
o(h),
P (N(t
+
h)
−
N(t)
=
1
|
N(t)
=
i)
=
h
+
o(h),
P (N(t
+
h)
−
N(t)
>
2
|
N(t)
=
i)
=
o(h)
(2.3.5)
при h
&
0, где слагаемые o(h) не зависят ни от t, ни от i.
Д о к а з а т е л ь с т в о теоремы 2.3.2. Импликация а)
⇒
б) очевидна.
Из п. а) следует, что
P (N
t
+
h
−
N
t
=
l)
=
( h)
l
l!
e
−
h
=
(
e
−
h
=
1
−
h
+
O(h
2
), l
=
0,
(
h)e
−
h
=
h(1
+
o(h)), l
=
1,
и
P (N
t
+
h
−
N
t
>
2)
=
1
−
P (N
t
+
h
−
N
t
=
0 или 1)
=
=
1
−
(1
−
h
+
h
+
o(h))
=
o(h).
Отсюда получаем п. б).
Импликация б)
⇒
в) посложнее. Сначала проверим, что нет двойных
скачков, т. е.
P (нет скачков размером 2 и выше на полуинтервале (0, t])
=
=
P
таких скачков нет на полуинтервалах
k
−
1
m
t,
k
m
t
i
∀
k
=
1, . . . , m
=
=
m
Y
k
=
1
P
таких скачков нет на полуинтервалах
h
k
−
1
m
t,
k
m
t
i
=
=
Y
k
P
скачков нет вообще или есть единственный скачок размера 1
на полуинтервале
k
−
1
m
t,
k
m
t
i
=
=
1
−
t
m
+
t
m
+
o
t
m
m
=
1
+
o
t
m
m
→
1 при m
→ ∞
в силу б).
§ 2.3. Процесс Пуассона 239
Все это верно для любого t
>
0, поэтому
P (скачков размера 2 и выше нет вообще)
=
1.
Далее, проверим, что для любых t, s
>
0 выполняется условие:
P (N
t
+
s
−
N
s
=
0)
=
e
−
s
.
Запишем аналогично предыдущему
P (N
t
+
s
−
N
s
=
0)
=
P (нет скачков на полуинтервалах (s, t
+
s])
=
=
P
нет скачков на полуинтервалах
s
+
k
−
1
m
t, s
+
k
m
t
i
∀
k
=
1, . . . , m
=
=
m
Y
1
P
нет скачков на полуинтервалах
s
+
k
−
1
m
t, s
+
k
m
t
i
=
=
1
−
t
m
+
o
t
m
m
→
e
−
t
при m
→ ∞
в силу б).
Введем теперь времена пребывания:
S
0
=
sup[t
>
0: N(t)
=
0],
S
1
=
sup[t
>
0: N(S
1
+
t)
=
1]
и т. д. Тогда моменты времени, в которые процесс совершает скачки, равны
S
0
(
=
H
1
, время достижения состояния 1),
S
0
+
S
1
(
=
H
2
, время достижения состояния 2),
.
.
.
S
0
+
. . .
+
S
k
−
1
(
=
H
k
, время достижения состояния k),
.
.
.
Рис. 2.21