Кельберт М.Я., Сухов Ю.М. Вероятность и статистика в примерах и задачах. Том 2. Марковские цепи как отправная точка теории случайных процессов и их приложения
Подождите немного. Документ загружается.
400 Глава 2. Цепи Маркова с непрерывным временем
Замечание 2.12.12. Отметим, что (см., например, Прудников А. П.,
Брычков Ю. А., Маричев О. И. Интегралы и ряды. М.: Физматгиз, 1981,
с. 685)
∞
X
i
=
0
1
i
2
+
1
=
1
2
+
2
cth( ), т. е.
X
i
∈
Z
i
=
cth( ).
Задача 2.12.13. Клиенты становятся в очередь согласно процессу
Пуассона с интенсивностью . Время обслуживания каждого клиента
—
показательная с.в. со средним
−
1
, причем
<
; времена обслуживания
взаимно независимы и не зависят от времен прибытия.
а) Покажите, что вероятность того, что в момент t в очереди находится
n или более клиентов, стремится к (
/
)
n
при t
→ ∞
.
б) В случае, когда начальное распределение является инвариантным,
вычислите среднее время до того момента, когда очередь впервые окажется
пустой.
Решение. Число клиентов в описанной очереди образует такой непри
-
водимый процесс рождения и гибели (X
t
), что q
ii
+
1
=
, q
ii
−
1
=
. Из
уравнений детального баланса заключаем, что инвариантное распределе
-
ние является геометрическим:
i
=
(1
−
/
) (
/
)
i
(так как
<
). Таким
образом, цепь положительно возвратна, и
—
единственное инвариантное
распределение. Теорема 2.8.1 утверждает следующее.
Для неприводимой положительно возвратной ц.м.н.в. p
ij
(t)
→
j
при t
→ ∞
.
а) Следовательно, независимо от начального распределения для любого
n
=
1, 2, . . . выполняется соотношение
P (X
t
6
n
−
1)
→
1
−
X
0
6
i
6
n
−
1
i
=
1
−
n
и
P (X
t
>
n)
→
n
.
б) Положив k
i
=
E
i
(попасть в 0) и записав условные вероятности по
первому скачку, получаем следующие уравнения:
k
i
=
0, k
i
=
1
+
+
+
k
i
+
1
+
+
k
i
−
1
, i
>
1,
причем нас интересует минимальное неотрицательное решение. Это реше
-
ние имеет вид k
i
=
i
/
(
−
), а следовательно,
X
i
>
1
i
k
i
=
1
−
X
i
>
1
i
i
−
=
(
−
)
2
.
§ 2.12. Вопросы к теории цепей Маркова с непрерывным временем 401
Задача 2.12.14. а) Объясните, что понимают под процессом рождения
и гибели X(t) с интенсивностями рождения (
k
) и интенсивностями гибели
(
k
), где
0
=
0.
Выпишите прямые уравнения для вероятностей p
k
(t)
=
P (X(t)
=
k)
и покажите, что вероятностная производящая функция g(s, t)
=
Es
X(t)
удовлетворяет уравнению
∂
g
∂
t
=
(s
−
1)
Λ
(s)
−
1
s
M(s)
,
−
1
<
s
6
1, (2.12.1)
где
Λ
(s)
=
P
k
k
p
k
(t)s
k
и M(s)
=
P
k
k
p
k
(t)s
k
.
(Можно предполагать, что процесс не взрывается.)
б) Некоторое сообщество не располагает запасами пищи, достаточными
для поддержания существования более чем N особей. Если в момент t
сообщество состоит из k особей, то вероятность присоединения к ним
новой особи за промежуток времени (t, t
+
h) равна (N
−
k)h
+
o(h)
независимо от предыстории. В течение этого временн
´
ого интервала каждая
особь может покинуть сообщество с вероятностью
h
+
o(h) независимо
от других особей и независимо от предыстории.
Выпишите генератор соответствующей ц.м.н.в. X(t) и покажите, что
∂
g
∂
t
=
(s
−
1)
Ng
−
( s
+
)
∂
g
∂
s
,
−
1
<
s
6
1. (2.12.2)
Пусть X(0)
=
0. Найдите такую функцию h(t), что функция g(s, t)
=
=
(1
−
h(t)
+
sh(t))
N
является решением уравнения (2.12.2), и найдите
распределение с.в. X(t).
Решение. а) Процесс рождения и гибели (X(t), t
>
0) образует ц.м.н.в.
с пространством состояний
Z
+
= {
0, 1, . . .
}
, скачки возможны только
в ближайшие соседние состояния:
(
интенсивность скачка k
→
k
+
1 (рождение):
k
, k
>
0;
интенсивность скачка k
→
k
−
1 (смерть):
k
, k
>
1.
Таким образом, Q
-
матрица имеет вид:
Q
=
−
0 0
0 0 . . .
1
−
(
1
+
1
)
1
0 . . .
0
2
−
(
2
+
2
)
2
. . .
. . . . . . . . . . . . . . .
.
Прямые уравнения для вероятностей перехода p
k
(t) записываются в виде
d
dt
p
k
= −
(
k
+
k
)p
k
+
k
−
1
p
k
−
1
+
k
+
1
p
k
+
1
, k
>
0,
402 Глава 2. Цепи Маркова с непрерывным временем
где
−
1
=
0.
Для g(s, t)
=
Es
X(t)
=
P
k
s
k
p
k
(t) получаем
X
k
s
k
d
dt
p
k
=
X
k
(
−
(
k
+
k
)p
k
+
k
−
1
p
k
−
1
+
k
+
1
)s
k
,
откуда следует, что
∂
g
∂
t
= −Λ −
M
+
s
Λ +
1
s
M
=
(s
−
1)
Λ −
1
s
M
,
−
1
<
s
6
1,
что и требовалось. Если процесс не взрывается, то эти уравнения спра
-
ведливы при всех t
>
0.
б) В этом случае интенсивности таковы:
k
=
(N
−
k),
k
=
k, k
=
0, 1, . . . , N.
Следовательно,
Λ
(s)
=
N
X
k
=
0
(N
−
k)p
k
s
k
=
Ng
−
s
∂
g
∂
s
,
и
M(s)
=
N
X
k
=
0
kp
k
s
k
=
s
∂
g
∂
s
.
Тогда в силу а) находим
∂
g
∂
t
=
(s
−
1)
Ng
−
(
+
s)
∂
g
∂
s
.
Подставляя g(s, t)
=
(1
−
h(t)
+
sh(t))
N
, получаем
˙
h
=
(1
−
h
+
sh)
−
h(
+
s),
или
˙
h
+
(
+
)h
− =
0, h
=
+
+
ce
−
(
+
)t
.
При условии h(0)
=
0 находим
h
=
+
(1
−
e
−
(
+
)t
).
Мы видим, что X(t)
∼
Bin(N, h(t)), поскольку
Es
X(t)
=
X
0
6
r
6
N
C
r
N
s
r
h
r
(1
−
h)
N
−
r
=
((s
−
1)h(t)
+
1)
N
.
§ 2.12. Вопросы к теории цепей Маркова с непрерывным временем 403
Задача 2.12.15. а) В финале олимпийских соревнований встречаются
хоккейные команды России и Канады. Предположим, что шайбы россиян
попадают в ворота канадцев согласно процессу Пуассона с интенсивно
-
стью r
>
0, а шайбы канадцев подчиняются процессу Пуассона с интен
-
сивностью c
>
0 независимо от шайб россиян. Пусть X
—
число шайб на
счету у россиян до первой шайбы на счету у канадцев. Предположим, что
игра продолжается бесконечно. Найдите P (X
=
k), k
=
0, 1, . . .
Указание. Справедлива формула
∞
R
0
s
k
e
−
s
ds
=
k!.
б) 1. Предположим теперь, что в модели, описанной в п. а), игра
продолжается только до момента времени t
=
1. Чему равна вероятность
P (X
=
1)?
2. Предположим, что к моменту времени t
=
1 на счету у команды
России одна шайба. Найдите среднее время до первой шайбы в этой игре.
Решение. а) Если T
—
момент времени, когда впервые забивают шайбу
канадцы, то T
∼
Exp(c) независимо от пуассоновского процесса ПП (r)
(R(t), t
>
0), которому подчиняются шайбы команды России. Тогда для
k
=
0, 1, . . . имеем
P (X
=
k)
=
P (R(T)
=
k)
=
=
c
∞
Z
0
e
−
ct
P (R(T)
=
k
|
T
=
t) dt
=
c
∞
Z
0
e
−
ct
P (R(t)
=
k) dt
=
=
cr
k
k!
∞
Z
0
e
−
ct
t
k
e
−
rt
dt
=
cr
k
k!(r
+
c)
k
+
1
∞
Z
0
e
−
t
t
k
dt
=
c
(r
+
c)
r
k
(r
+
c)
k
.
404 Глава 2. Цепи Маркова с непрерывным временем
б) 1. Пусть P
(1)
—
искомая вероятность. Тогда
P
(1)
=
P (R(1)
=
1, T
>
1)
+
P (R(1)
=
1, T
6
1)
=
=
P (R(1)
=
1) P (T
>
1)
+
c
1
Z
0
e
−
ct
P (R(t)
=
1
|
T
=
t) dt
=
=
re
−
r
e
−
c
+
rc
1
Z
0
te
−
(r
+
c)t
dt
=
=
re
−
(r
+
c)
+
rc
(r
+
c)
2
r
+
c
Z
0
t
1
e
−
t
1
dt
1
(где t
1
=
(r
+
c)t)
=
=
re
−
(r
+
c)
+
rc
(r
+
c)
2
[1
−
(r
+
c
+
1)e
−
(r
+
c)
].
2. Пусть S
—
момент времени, когда впервые забивают шайбу россияне,
а T, как и ранее, обозначает момент времени, когда впервые забивают
шайбу канадцы. Тогда при условии, что R(1)
=
1, с.в. S
∼
U(0, 1). Отсюда
следует, что
P (min(S, T)
>
t
|
R(1)
=
1)
=
(1
−
t)e
−
ct
, 0
<
t
<
1.
Следовательно, условная плотность f
min(S,T)
|
R(1)
=
1
минимума min(S, T) рав
-
на
e
−
ct
+
c(1
−
t) e
−
ct
=
e
−
ct
(1
+
c(1
−
t)), 0
<
t
<
1,
а условное среднее равно
E [min(S, T)
|
R(1)
=
1]
=
1
Z
0
te
−
ct
(1
+
c(1
−
t)) dt
=
1
c
2
(e
−
c
−
1
+
c).
The KGB’s ’s and the FBI’s κ’s
(Из серии
«
Фильмы, которые не вышли на большой экран
»
.)
Задача 2.12.16. а) Пусть N
—
процесс Пуассона с интенсивностью
ПП ( ). При условии, что
{
N(t)
=
1
}
покажите, что единственный момент
скачка T процесса на интервале (0, t] имеет равномерное распределение
на этом интервале.
§ 2.12. Вопросы к теории цепей Маркова с непрерывным временем 405
б) Один канадский кемпинг пользуется популярностью среди медведей,
которых привлекают мусорные баки с остатками пищи. Мишки наведыва
-
ются в кемпинг согласно процессу Пуассона с интенсивностью . Прибыв
в лагерь, m
-
й мишка бродит некоторое время R
m
в поисках бака, а за
-
тем затрачивает время S
m
, исследуя его содержимое. Векторы (R
m
, S
m
),
m
>
1, являются независимыми случайными векторами с одним и тем же
(совместным) распределением. Пусть U(t) и V (t)
—
число мишек, которые
в момент t скитаются в поисках, и тех, которые уже нашли бак и заняты его
содержимым (будем называть это грабежом). Предположим, что U(0)
=
=
V (0)
=
0.
Пусть
(соответственно )
—
вероятность того, что медведь, прибыв
-
ший в некоторый момент T (случайно выбранный по равномерному закону
из интервала (0, t)), в момент t занят поисками (соответственно грабежом).
Выразите P (U(t)
=
u, V (t)
=
v) в терминах и и, воспользовавшись
этим, покажите, что U(t) и V (t) представляют собой независимые с.в.
с распределением Пуассона каждая.
Покажите, что E (U(t))
→
ER
1
при t
→ ∞
.
Указание. При условии
{
N(t)
=
m
}
первые m моментов прибытия
имеют то же самое распределение, что и порядковые статистики для m
независимых случайных величин, равномерно распределенных на интерва
-
ле (0, t).
Решение. а) Условие N(t)
=
1 означает, что на полуинтервале (0, t]
содержится лишь один момент прибытия. Пусть T
—
момент прибытия.
Тогда
P (T
6
a
|
N(t)
=
1)
=
P (N(a)
=
1
|
N(t)
=
1)
=
=
P (N(a)
=
1, N(t)
−
N(a)
=
0)
P (N(t)
=
1)
=
ae
−
a
e
−
(t
−
a)
te
−
t
=
a
t
∀
0
6
a
6
t.
Следовательно, T
∼
U(0, t).
б) Моменты прибытия медведей на (0, t] при условии
{
N(t)
=
n
}
пред
-
ставляют собой независимые равномерно распределенные точки на (0, t],
соответствующие векторы (R
m
, S
m
), 1
6
m
6
n, независимы и одинаково
распределены. Следовательно, в момент t каждый медведь либо занят
поисками с вероятностью
, либо грабежом с вероятностью , либо уже
ушел с вероятностью 1
− −
независимо от других. Согласно определению
=
P (R
1
>
t
−
T),
=
P (R
1
<
t
−
T
6
R
1
+
S
1
),
1
− − =
P (t
−
T
>
R
1
+
S
1
),
где T
∼
U(0, t), независимо от (R
1
, S
1
). Мы видим, что для любых таких
406 Глава 2. Цепи Маркова с непрерывным временем
неотрицательных целых чисел u, v, что u
+
v
6
n, условная вероятность
вычисляется по формуле
P (U(t)
=
u, V (t)
=
v
|
N(t)
=
n)
=
n!
u v
(1
− −
)
n
−
u
−
v
u!v!(n
−
u
−
v)!
.
Тогда безусловная вероятность P (U(t)
=
u, V (t)
=
v) равна
X
n
>
u
+
v
P (U(t)
=
u, V (t)
=
v
|
N(t)
=
n) P (N(t)
=
n)
=
=
X
n
>
u
+
v
n!
u v
(1
− −
)
n
−
u
−
v
u!v!(n
−
u
−
v)!
( t)
n
e
−
t
n!
=
=
( t)
u
e
−
t
u!
( t)
v
e
−
t
v!
×
X
n
>
u
+
v
((1
− −
) t)
n
−
u
−
v
(n
−
u
−
v)!
e
−
(1
− −
) t
=
=
( t)
u
e
−
t
u!
( t)
v
e
−
t
v!
.
Таким образом, U(t) и V (t) являются независимыми пуассоновскими с.в.
со средними значениями t и t соответственно.
Далее,
=
t
Z
0
P (R
1
>
t
−
r) dr
1
t
=
1
t
t
Z
0
P (R
1
>
r) dr.
Поэтому
lim
t
→∞
t
=
∞
Z
0
P (R
1
>
r) dr
=
ER
1
и
lim
t
→∞
EU(t)
=
ER
1
.
Задача 2.12.17. Пусть
i
(i
>
0) и
i
(i
>
0)
—
положительные кон
-
станты и
Q
=
(q
ij
: i, j
>
0)
—
производящая матрица ц.м.н.в.,
Q
=
−
0 0
0 0 0
·
0
−
(M
0
+
1
)
1
0 0
·
0 1
−
(M
1
+
2
)
2
0
·
0 1 2
−
(M
2
+
3
)
3
·
· · · · · ·
· · · · · ·
§ 2.12. Вопросы к теории цепей Маркова с непрерывным временем 407
где M
i
=
0
+
1
+
. . .
+
i
, i
>
0. Докажите, что минимальный процесс,
ассоциированный с Q, является регулярным (невзрывным) тогда и только
тогда, когда
X
j
>
1
1
j
j
−
1
Y
k
=
0
1
+
M
k
k
= ∞
.
Указание. Ц.м.н.в. (X
t
) (или ее производящая матрица Q) является
невзрывной тогда и только тогда, когда система
Qz
=
z, z
=
(z
i
), z
i
>
0, i
=
0, 1, . . . ,
не имеет ограниченного нетривиального решения. Полезно также восполь
-
зоваться неравенством
(1
+
x
+
y)
6
(1
+
x)e
y
, x
>
0, y
>
0.
Решение. Нетрудно проверить, что ц.м.н.в. X(t) регулярна тогда и толь
-
ко тогда, когда система
Qz
=
z
не имеет ограниченного нетривиального решения. Итак, будем рассматри
-
вать ее решения:
i
=
0:
−
0
z
0
+
0
z
1
=
z
0
,
i
>
1:
0
z
0
+
1
z
1
+
. . .
+
i
−
1
z
i
−
1
−
(M
i
−
1
+
i
)z
i
+
i
z
i
+
1
=
z
i
,
т. е.
i
−
1
P
j
=
0
j
z
j
−
(M
j
−
1
+ +
j
)z
j
+
j
z
j
+
1
=
0.
(2.12.3)
Предположим, что i
>
1. Запишем
i
−
1
X
j
=
0
j
z
j
−
(M
i
−
1
+ +
i
)z
i
+
i
z
i
+
1
=
0
и
i
−
2
X
j
=
0
j
z
j
−
(M
i
−
2
+ +
i
−
1
)z
i
−
1
+
i
−
1
z
i
=
0.
Подстановка приводит к уравнению
(
i
−
1
+
M
i
−
2
+ +
i
−
1
)z
i
−
1
−
(M
i
−
1
+ +
i
)z
i
+
i
z
i
+
1
−
i
−
1
z
i
=
0,
и после перегруппировки членов получаем
(M
i
−
1
+ +
i
−
1
) (z
i
−
1
−
z
i
)
+
i
(z
i
+
1
−
z
i
)
=
0.
408 Глава 2. Цепи Маркова с непрерывным временем
Тогда
z
i
+
1
−
z
i
=
M
i
−
1
+ +
i
−
1
i
(z
i
−
z
i
−
1
)
=
. . .
=
i
Y
k
=
1
M
k
−
1
+ +
k
−
1
k
(z
1
−
z
0
).
Используя соотношение (2.12.3), находим z
1
−
z
0
=
z
0
0
, откуда следует,
что
z
i
+
1
−
z
i
=
z
0
0
i
Y
k
=
1
M
k
−
1
+ +
k
−
1
k
,
z
i
+
1
=
z
0
1
+
0
i
X
j
=
1
j
Y
k
=
1
M
k
−
1
+ +
k
−
1
k
.
Решение является ограниченным и нетривиальным тогда и только тогда,
когда
1
0
X
j
>
1
j
Y
k
=
1
M
k
−
1
+
k
−
1
+
k
< ∞
,
т. е. когда
X
j
>
1
1
j
j
−
1
Y
k
=
0
M
k
+
k
+
k
< ∞
.
Если это неравенство выполняется для некоторого
>
0, тогда очевидно,
что
X
j
1
j
j
−
1
Y
k
=
0
1
+
M
k
k
< ∞
.
И наоборот, если выполняется последнее неравенство, то
P
j
1
j
< ∞
.
Наконец, поскольку 1
+
x
+
y
<
(1
+
x)e
y
, заключаем, что
X
j
1
j
j
−
1
Y
k
=
0
1
+
M
k
+
k
6
X
j
1
j
j
−
1
Y
k
=
0
1
+
M
k
k
e
P
i
1
/
i
< ∞
.
Сформулируем теорему, использованную при решении этой задачи.
Теорема 2.12.18. Пусть (X)
—
ц.м.н.в. с генератором Q и T
=
=
T
explo
—
момент взрыва этой цепи. Зафиксируем
>
0 и положим
z
i
=
E
i
(e
−
T
). Тогда вектор-столбец с компонентами z
i
, i
∈
I, удо-
влетворяет условиям:
§ 2.12. Вопросы к теории цепей Маркова с непрерывным временем 409
а)
|
z
i
| <
1 для всех i,
б) Qz
=
z.
Более того, z задает минимальное решение, т. е. если
e
z
=
=
(
e
z
i
, i
∈
I)
T
удовлетворяет условиям а) и б), то
e
z
i
6
z
i
для всех
i
∈
I.
Из теоремы вытекает, что для любого следующие условия эквивалент
-
ны:
1) Q не взрывная;
2) Qz
=
z и неравенства
|
z
i
| <
1 для всех i влекут, что z
=
0.
Д о к а з а т е л ь с т в о. В силу марковского свойства цепи скачков при
условии X
J
1
=
k выполняется соотношение
E
i
(e
−
T
explo
|
X
J
1
=
k)
=
∞
Z
0
e
−
u
q
i
e
−
q
i
u
du E
k
(e
−
T
explo
)
=
q
i
z
k
q
i
+
и
z
i
=
X
k
6=
i
q
i
b
p
ik
z
k
q
i
+
. (2.12.4)
В силу соотношений q
i
= −
q
ii
и q
i
b
p
ik
=
q
ik
(2.12.4) эквивалентно уравне
-
нию
z
i
=
X
i
q
ik
z
k
.
Теперь предположим, что
e
z также удовлетворяет условиям а) и б). Тогда
по индукции проверяем, что
e
z
i
6
E
i
(e
−
J
n
). (2.12.5)
Действительно, из а) вытекает неравенство (2.12.6) при n
=
0, а используя
для (2.12.6) для n, проверяем его для n
+
1:
e
z
i
=
X
k
6=
i
q
i
b
p
ik
e
z
k
q
i
+
6
X
k
6=
i
q
i
b
p
ik
q
i
+
E
k
(e
−
J
n
)
=
E
i
(e
−
J
n
+
1
).
В силу теоремы о монотонной сходимости lim
n
→
E
i
(e
−
J
n
+
1
)
=
E
i
(e
−
T
explo
).
Следовательно,
e
z
i
6
z
i
.
Задача 2.12.19. Оборудование в новом офисе начальника департамен
-
та находится под контролем компьютерной системы и ведет себя довольно
странно. Если шторы опущены в момент n, то компьютер их поднимает
в момент n
+
1 с вероятностью
1
; если же шторы подняты в момент n, они
опускаются с вероятностью
2
. Если освещение выключено в момент n, то
410 Глава 2. Цепи Маркова с непрерывным временем
компьютер включает его в момент n
+
1 с вероятностью
1
; если же оно
включено, то выключается оно с вероятностью
2
. Изменения состояний
штор и освещения не зависят друг от друга и от предыдущих состояний.
Начальник департамента входит в свой кабинет в момент 0 и обнару
-
живает, что шторы опущены и освещение выключено. Какова вероятность
того, что в момент его ухода n шторы и освещение будут находится в таком
же состоянии?
Определите предельную пропорцию среднего времени, в течение кото
-
рого одновременно опущены шторы и выключено освещение.
Решение. Обозначим состояния штор Н (опущены вниз) и В (подняты
вверх), матрица перехода имеет вид
1
−
1 1
2
1
−
2
.
Следовательно, вероятность перехода за n шагов определяется по формуле
p
(n)
нн
(n)
=
2
1
+
2
+
1
1
+
2
(1
−
1
−
2
)
n
;
аналогичные формулы можно записать для p
(n)
нв
, p
(n)
вн
и p
(n)
вв
. Инвариантное
распределение задается как
ш
=
(
ш
н
,
ш
в
) и определяется формулами
ш
н
=
2
1
+
2
,
ш
в
=
1
1
+
2
.
Аналогичные формулы имеют место и для инвариантного распределе
-
ния
с
=
(
с
вкл
,
с
выкл
) для освещения (где заменяется на ). Наконец,
в силу независимости находим, что совместные вероятности перехода рав
-
ны произведениям, а именно
p
(n)
(н,вкл) (н,вкл)
=
2
1
+
2
+
1
1
+
2
(1
−
1
−
2
)
n
×
×
2
1
+
2
+
1
1
+
2
(1
−
1
−
2
)
n
,
и совместные инвариантные вероятности также равны произведениям, а
именно
(ш,с)
(н,выкл)
=
1
1
+
2
1
1
+
2
.
Аналогично для предельной пропорции среднего времени получаем вы
-
ражение
2
(
1
+
2
)
2
(
1
+
2
)
.
§ 2.12. Вопросы к теории цепей Маркова с непрерывным временем 411
Задача 2.12.20. Агентство по контролю за качеством высшего обра
-
зования направило комиссию для исследования процесса обучения ма
-
тематике в Кембриджском университете. Во время своего пребывания
в университете комиссия ведет список поступающих претензий. Предполо
-
жим, что в течение временн
´
ого интервала (t, t
+
h) новая жалоба подается
с вероятностью
h
+
o(h), в то же время любая из уже поступивших жалоб
признается необоснованной и удаляется из списка жалоб с вероятностью
h
+
o(h). Введя приемлемые предположения, покажите, что число C(t)
активных жалоб в списке на момент времени t образует процесс рождения
и гибели с интенсивностями рождения
n
=
и интенсивностями смерти
n
=
n .
Получите прямую систему уравнений для вероятностей p
n
(t)
=
=
P(C(t)
=
n). Покажите, что m(t)
=
EC(t) удовлетворяет дифферен
-
циальному уравнению m
0
(t)
= −
m(t), и найдите m(t) при начальном
условии m(0)
=
1.
Найдите инвариантное распределение процесса.
Решение. Предположим, что каждое отдельное удаление жалобы из
списка не зависит от других и что поступление и удаление жалоб также не
зависят друг от друга. Тогда условная вероятность удовлетворяет соотно
-
шению
P (C(t
+
h)
−
C(t)
= −
1
|
C(t)
=
n)
=
nh
+
o(h),
поскольку первое удаление соответствует минимуму n независимых пока
-
зательных случайных величин, т. е. происходит в показательно распреде
-
ленное время с интенсивностью
n. Тогда прямые уравнения
d
dt
P(t)
=
=
P(t)Q таковы:
d
dt
p
0
= −
p
0
+
p
1
,
d
dt
p
n
=
p
n
−
1
−
(
+
n)p
n
+
(n
+
1)p
n
+
1
, n
>
1,
Q
-
матрица имеет вид
Q
=
−
0 0 . . .
−
(
+
) 0 . . .
0 2
−
(
+
2 ) . . .
. . . . . . . . . . . . . . .
,
а уравнение для инвариантного распределения
имеет вид Q
=
0.
Мы можем также рассмотреть уравнения детального баланса
i
−
1
=
i
i , i
>
1,
412 Глава 2. Цепи Маркова с непрерывным временем
откуда получаем
i
=
i
i
−
1
=
. . .
=
i
0
i!
.
Таким образом,
0
=
e
−
/
, а следовательно,
∼
Po(
/
). Уравнение для
m(t) имеет вид
dm
dt
(t)
= −
m(t), m(0)
=
1,
откуда следует, что
m(t)
= +
1
−
e
−
t
.
Специалисты по марковским процессам любят делать это в невозвратном состоянии.
(Из серии
«
Как они делают это
»
.)
Задача 2.12.21. Пусть X
—
ц.м.н.в. на пространстве состояний I
=
= {
1, 2
}
с производящей матрицей
Q
=
−
−
, где ,
>
0.
Покажите, что полугруппа матриц перехода P(t)
=
exp(tG) задается урав
-
нением
P(t)
=
(
+
)
−
1
+
h(t) (1
−
h(t))
(1
−
h(t))
+
h(t)
,
где h(t)
=
e
−
t(
+
)
.
Пусть
P(
)
=
1
−
1
−
, 0
< <
1.
Для ц.м.н.в. X пусть M
—
матрица, у которой (i, j)
-
й элемент равен
P (X(1)
=
j
|
X(0)
=
i) для i, j
∈
S. Покажите, что цепь X с матрицей
M
=
P( ) существует тогда и только тогда, когда
>
1
/
2.
Решение. Самый краткий путь решения
—
это проверить, что матрица
P(t) удовлетворяет уравнениям P
0
(t)
=
P(t)Q
=
QP(t) и сослаться на
теорему о единственности решения.
Задача 2.12.22. Задания поступают на обслуживание согласно про
-
цессу Пуассона ПП (
). Задания последовательно выполняются на един
-
ственном процессоре, времена обслуживания являются н.о.р.с.в. и имеют
показательное распределение с параметром
>
0. После обработки
задание либо покидает систему с вероятностью p, 0
<
p
<
1, либо,
с вероятностью 1
−
p, оно разбивается на два отдельных задания, и оба
§ 2.12. Вопросы к теории цепей Маркова с непрерывным временем 413
эти задания вновь отправляются в общую очередь для их обработки. Пусть
X(t)
—
число заданий в системе в момент времени t.
В случае, когда 1
+
/
<
2p, оцените lim
t
→∞
P (X(t)
=
j), j
=
0, 1, . . . ,
и найти среднее время занятости процессора между двумя последователь
-
ными периодами простоя. Что произойдет, если 1
+
/
>
2p?
Решение. В описанном примере
0
=
и
i
= +
q ,
i
=
p , i
>
1,
где q
=
1
−
p, поэтому
i
=
p
i
−
1
, i
>
1, где
=
+
q
p
.
Если 1
+
/
<
2p, то
<
1, следовательно,
m
=
1
+
p (1
−
)
< ∞
и P (X(t)
=
j)
→
j
/
m при t
→ ∞
.
Среднее время возвращения в 0 в этом случае равно 1
/
(
0
)
=
m
/
,
следовательно, средняя продолжительность периодов занятости будет рав
-
на
(m
−
1)
=
1
p (1
−
)
=
1
(2p
−
1)
−
.
Если 1
+
/
>
2p, то цепь либо имеет нулевую возвратность, либо
невозвратна, а значит, P (X(t)
=
i)
→
0, и средняя продолжительность
периодов занятости становится бесконечной.
Задача 2.12.23. а) Пусть W (t)
—
число ос, приземлившихся на тарелку
с супом в течение интервала времени (0, t], и предположим, что вероят
-
ность прилета осы в течение интервала (u, u
+
h) равна (u)h
+
o(h) для
некоторой заданной функции
. Четко сформулируйте все дополнительные
предположения, необходимые, чтобы представить W как неоднородный
процесс Пуассона с функцией интенсивности
. Покажите, что W (t) имеет
распределение Пуассона со средним
t
R
0
(u) du.
б) Пусть X
1
, X
2
, . . .
—
последовательность поступающих предложений
о покупке дома. Предположим, что X
i
являются н.о.р.с.в. с плотностью
распределения f и функцией распределения F. Будем говорить, что X
n
—
это рекордное значение, если n
=
1 или X
n
>
X
i
при всех i
<
n.
Найдите вероятность того, что X
n
представляет собой рекордное значение.
Найдите также оценку вероятности того, что этот рекорд лежит в интервале
(u, u
+
h), где h
—
малая величина. Пренебрегая всеми членами порядка
o(h) для малых h, найдите вероятность того, что интервал (u, u
+
h) содер
-
жит рекордное значение. Покажите, что число R(t) рекордных значений на
интервале (0, t] имеет среднее
−
ln(1
−
F(t)) при условии F(t)
<
1.
414 Глава 2. Цепи Маркова с непрерывным временем
Решение. а) Предположим, что является
«
хорошей
»
функцией (на
-
пример, она ограничена и интегрируема на каждом интервале (0, t)). Пред
-
положения относительно процесса (W (t), t
>
0), W (0)
=
0, которые мы
будем использовать, таковы:
1) вероятность P (W (u
+
h)
−
W (u)
=
1) того, что на интервале (u, u
+
h)
происходит единственный прилет, равна
(u)h
+
o(h), где o(h) стремится
к 0 при h
→
0 равномерно по u
∈
(0, t);
2) вероятность P (W (u
+
h)
−
W (u)
>
2) нескольких моментов прилета
на интервале (u, u
+
h) равна o(h), где o(h) стремится к 0 при h
→
0
равномерно по u
∈
(0, t);
3) приращения W (t
1
)
−
W (t
0
), . . . , W (t
n
)
−
W (t
n
−
1
) независимы, для
любых моментов времени 0
=
t
0
<
t
1
<
. . .
<
t
n
=
t, т. е.
P (W (t
j
)
−
W (t
j
−
1
)
=
k
j
, 1
6
j
6
n)
=
n
Y
j
=
1
P (W (t
j
)
−
W (t
j
−
1
)
=
k
j
)
для любых k
1
, . . . , k
n
=
0, 1, . . . При этих предположениях W (t)
∼
Po(
Λ
(t)),
где
Λ
(t)
=
t
R
0
(u) du. Действительно, п.ф.м. M
t
( )
=
Ee
W (t)
можно
представить в виде
M
t
( )
=
E exp( [W (t
1
)
−
W (t
0
)]
+
. . .
+
[W (t
n
)
−
W (t
n
−
1
)])
=
=
n
Y
j
=
1
E exp( [W (t
j
)
−
W (t
j
−
1
)]),
и при n
→ ∞
и max[t
j
−
t
j
−
1
]
→
0 для любого заданного
n
Y
j
=
1
E exp( [W (t
j
)
−
W (t
j
−
1
)])
=
=
n
Y
j
=
1
[1
−
(t
j
−
1
) (t
j
−
t
j
−
1
)
+
e (t
j
−
1
) (t
j
−
t
j
−
1
)
+
o(t
j
−
t
j
−
1
)]
=
=
n
Y
j
=
1
[1
+
(e
−
1) (t
j
−
1
) (t
j
−
t
j
−
1
)
+
o(t
j
−
t
j
−
1
)]
=
=
n
Y
j
=
1
exp[(e
−
1) (t
j
−
1
) (t
j
−
t
j
−
1
)
+
o(t
j
−
t
j
−
1
)]
→
exp[(e
−
1)
t
Z
0
(u) du].
Следовательно, M
t
( )
=
exp[(e
−
1)
Λ
(t)], и W (t) является пуассо
-
новской с.в. Po(
Λ
(t)) для любого t
>
0. Аналогично можно показать,
§ 2.12. Вопросы к теории цепей Маркова с непрерывным временем 415
что W (t
+
s)
−
W (s)
∼
Po(
Λ
(t
+
s)
− Λ
(s)). Следовательно, семейство
(W (t), t
>
0) представляет собой неоднородный процесс Пуассона с ин
-
тенсивностью
(t).
б) Если n
=
1, то по определению P (X
1
является рекордным значением)
=
=
1. При n
>
1, используя условное математическое ожидание, при
заданном значении X
n
находим
P (X
n
является рекордным значением)
=
P (X
n
>
X
i
∀
i
=
1, . . . , n
−
1)
=
=
E1(X
n
>
X
i
∀
i
=
1, . . . , n
−
1)
=
=
E (E [1(X
n
>
X
i
∀
i
=
1, . . . , n
−
1)
|
X
n
])
=
+∞
Z
0
f(x)F (x)
n
−
1
dx.
Далее,
P (X
n
является рекордным значением и X
n
∈
(u, u
+
h))
=
=
u
+
h
Z
u
f(x)F (x)
n
−
1
dx
=
f(u)F (u)
n
−
1
h
+
o(h)
и
h min[f(x)F(x)
n
−
1
: u
6
x
6
u
+
h]
6
6
P (X
n
является рекордным значением и X
n
∈
(u, u
+
h))
6
6
h max[f(x)F (x)
n
−
1
: u
6
x
6
u
+
h].
Для того чтобы найти главный член, который вносит основной вклад в
вероятность того, что интервал (u, u
+
h) содержит рекордное значение,
запишем
P ((u, u
+
h) содержит рекордное значение )
=
P (u
<
X
1
<
u
+
h)
+
+
X
n
>
1
P (X
n
является рекордным значением и u
<
X
n
<
u
+
h)
+
o(h)
=
=
h
f(u)
+
X
n
>
1
f(u)F (u)
n
−
1
+
o(h)
=
hf(u)
1
−
F(u)
+
o(h).
Заключаем, что процесс рекордов (R(t)) является неоднородным процес
-
сом Пуассона НПП (
(t)) с интенсивностью (t)
=
f(u)
/
(1
−
F(u)).
416 Глава 2. Цепи Маркова с непрерывным временем
Тогда
E R(t)
=
среднее число рекордных значений на (0, t)
=
=
t
Z
0
(u) du
=
t
Z
0
f(u)
1
−
F(u)
du
=
t
Z
0
dF(u)
1
−
F(u)
=
t
Z
0
d ln[1
−
F(u)]
= −
ln[1
−
F(t)]
при условии, что F(t)
<
1. Мы используем тот факт, что F(0)
=
0,
следовательно, ln[1
−
F(0)]
=
0, в силу того что F имеет плотность f,
сосредоточенную на (0,
+∞
).
Задача 2.12.24. Клиенты прибывают в кондитерскую согласно процес
-
су Пуассона ПП (
). Единственный продавец кондитерской может вирту
-
озно обслуживать одновременно двух клиентов. Таким образом, всякий
раз, когда в очереди находятся два или более клиента, продавец обслужи
-
вает сразу двух клиентов; если же в очереди находится лишь один клиент,
то обслуживают его одного. Периоды обслуживания S
—
независимые
случайные величины, имеющие общую производящую функцию моментов
M(
)
=
E exp( S). Пусть Q
n
—
число людей в кондитерской в момент,
когда завершен n
-
й период обслуживания. Представьте Q
n
+
1
в виде
Q
n
+
1
=
A
n
+
Q
n
−
h(Q
n
),
где соответствующую величину A
n
следует определить, а h(x)
=
min
{
2, x
}
.
Покажите, что Q
=
(Q
n
: n
>
1) является ц.м.д.в., и найдите выражение
для п.ф.м. E x
A
n
, x
6
1.
Покажите, что если Q имеет инвариантное распределение
=
=
(
i
: i
>
0) и производящую функцию G(x)
=
P
i
i
x
i
, то
x
2
G(x)
=
M( (x
−
1))
G(x)
+
X
i
=
0,1
(x
2
−
x
i
)
i
,
|
x
| 6
1.
В случае, когда времена обслуживания имеют показательное распределе
-
ние с параметром
, покажите, что
G(x)
=
(1
−
)
/
(1
−
x),
где
=
2
1
+
p
1
+
4
, где
= <
2.
Решение. Пусть A
n
—
число клиентов, прибывших в течение n
-
го пе
-
риода обслуживания, а S
n
—
длительность n
-
го периода обслуживания,
F
S
(t)
=
P (S
n
<
t)
—
функция распределения, а M( )
=
Ee
S
n
—
п.ф.м..
§ 2.12. Вопросы к теории цепей Маркова с непрерывным временем 417
Тогда при условии S
n
=
t с.в. A
n
имеет распределение Пуассона Po( t).
Следовательно, вероятностная производящая функция имеет вид
ϕ
A
n
(x)
=
E x
A
n
=
E [E (x
A
n
|
S
n
)]
=
=
+∞
Z
0
+∞
X
m
=
0
x
m
( t)
m
m!
e
−
t
dF
S
(t)
=
+∞
Z
0
e
t(x
−
1)
dF
S
(t)
=
M( (s
−
1)),
и она задает распределение A
n
единственным образом. Далее, с.в. A
1
, A
2
,
. . . являются н.о.р.. Согласно описанию очереди
Q
n
+
1
=
A
n
+
Q
n
−
h(Q
n
) и h(Q
n
)
=
min[2, Q
n
],
где A
n
не зависит от Q
n
(на самом деле и от всей последовательности
Q
1
, . . . , Q
n
−
1
). Следовательно, (Q
n
) образует ц.м.д.в.
Далее, если
=
(
n
)
—
инвариантное распределение, то в состоянии
равновесия выполняются соотношения
G(x)
=
E x
Q
n
+
1
=
E x
A
n
E x
Q
n
−
h(Q
n
)
=
M( (x
−
1))
0
+
1
+
2
+
∞
X
i
=
3
i
x
i
−
2
и
x
2
G(x)
=
M( (x
−
1))
0
x
2
+
1
x
2
+
∞
X
i
=
2
i
x
i
=
=
M( (x
−
1)) [(x
2
−
1)
0
+
(x
2
−
x)
1
+
(x
2
−
x
2
)
2
+
G(x)]
=
=
M( (x
−
1))
G(x)
+
X
i
=
0,1
(x
2
−
x
i
)
i
,
что и требовалось.
Предположим теперь, что S
n
∼
Exp( ) и M( )
=
−
. Тогда при
=
=
имеем
M(
(x
−
1))
=
+ −
x
=
1
1
+ −
x
.
Следовательно,
G(x)
=
1
(1
+ −
x)x
2
[G(x)
+
(x
2
−
1)
0
+
(x
2
−
x)
1
].
418 Глава 2. Цепи Маркова с непрерывным временем
Учитывая предложенное выражение для G(x), положим G(x)
=
0
1
−
x
и
1
=
0
. В самом деле, это соответствует геометрическому инвариант
-
ному распределению
i
=
i
0
, i
>
1, и
0
=
1
−
. Тогда мы получаем
0
1
−
x
=
1
(1
+ −
x)x
2
h
0
1
−
x
+
(x
2
−
1)
0
+
(x
2
−
x)
0
i
,
или
1
=
1
(1
+ −
x)x
2
{
1
+
(1
−
x) [x
2
−
1
+
(x
2
−
x)]
} =
=
1
1
+ −
x
(1
−
x
+ −
2
x
+
2
).
Приравнивая коэффициенты при нулевой и первой степенях x, находим
пару (идентичных) соотношений
1
+ =
1
+ +
2
и x
=
x
+
2
x,
откуда получаем
=
−
1
+
p
1
+
4
2
.
Очевидно, следует положить
<
1, т. е.
<
2 (что является необходимым
и достаточным условием существования (и единственности) инвариантного
распределения). При
=
,
=
1 имеем
=
√
5
−
1
2
и
0
=
1
−
.
Задача 2.12.25. В баре имеется N стульев для посетителей. Посе
-
тители входят в бар согласно процессу Пуассона с интенсивностью
.
Если есть свободный стул, прибывший посетитель на нем располагается,
а если нет ни одного свободного
—
посетитель уходит. Времена пребывания
посетителей в баре
—
независимые показательные случайные величины
с параметром
. Вычислите вероятность того, что прибывший посетитель
находит свободный стул, при условии, что система находится в равновесии.
Для системы в состоянии равновесия опишите процесс ухода клиентов
(не считая при этом тех, кто ушел, не найдя свободный стул).
Решение. В задаче описан процесс рождения и гибели на
{
0, 1, . . . , N
}
, который является обратимой ц.м.д.в. Уравнения детального
баланса таковы:
0
=
1
, . . . ,
N
−
1
=
N
;
§ 2.12. Вопросы к теории цепей Маркова с непрерывным временем 419
решают их рекуррентно:
N
−
1
=
N
, . . . ,
0
=
N
N
.
Тогда
N
=
1
+ +
. . .
+
N
−
1
. (2.12.6)
Процесс ухода клиентов образует процесс Пуассона с интенсивностью
; формулу (2.12.6) называют теоремой Бурке для системы с потерями
M
/
M
/
1
/
N.
Все аргументы против этого, а вера
—
за это.
(О появлении духа человека после его смерти.)
С. Джонсон (1709
–
1784), английский издатель и драматург
Задача 2.12.26. Опишите применение теории ц.м.д.в. и ц.м.н.в. для
очередей с одним сервером. Следует обсудить вопрос существования
устойчивой длины очереди, а также вычислить величины, характеризующие
очередь в состоянии равновесия.
Решение. 1. Очередь M
/
M
/
1. Это простейший пример: времена меж
-
ду прибытиями являются н.о.р.с.в. Exp(
), а времена обслуживания
—
н.о.р.с.в. Exp(
). При этом число клиентов X
t
в системе в момент t образует
ц.м.н.в. на
Z
+
= {
0, 1, . . .
}
(процесс рождения и гибели) с интенсивностя
-
ми вида q
ii
+
1
=
, i
>
0, и q
ii
−
1
=
, i
>
1. Если
=
>
=
1,
<
то цепь является
невозвратной,
с нулевой возвратностью,
с положительной возвратностью.
Если
<
1, то инвариантное распределение является геометрическим:
i
=
i
(1
−
), i
>
0.
2. Очередь M
/
G
/
1. Здесь времена между прибытиями A
n
являются
н.о.р.с.в. Exp(
), а времена обслуживания S
n
—
н.о.р.с.в. с заданным рас
-
пределением. Число клиентов в очереди X
n
в момент сразу же после n
-
го
ухода образует ц.м.д.в.:
X
n
+
1
=
X
n
+
Y
n
+
1
−
1(X
n
>
1).
Здесь Y
n
—
число прибытий за время n
-
го периода обслуживания; Y
n
не
зависит от X
n
и Y
n
∼
Po( s) условно по S
n
=
s. Вероятностная произво
-
дящая функция имеет вид
ϕ
Y
(z)
=
Ez
Y
=
E [E (z
Y
|
S)]
=
E (e
(z
−
1)S
)
=
M
S
( (z
−
1)).