Дискретная математика: графы и автоматы. Альпин Ю.А - 45 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

§ 6. Цепи Маркова 45
Далее, из формулы (5) видно, что элементы матрицы Q
(k)
с ро-
стом k могут лишь возрастать, а поскольку они, будучи вероятно-
стями, ограничены сверху числом 1, то матрицы Q
(k)
сходятся при
k → ∞ к некоторому пределу Q
(∞)
.
Мы доказали, что lim
k→∞
P
k
существует и имеет форму, указан-
ную в теореме. Чтобы вывести формулу для Q
(∞)
, заметим, что ра-
венство PP
k
= P
k+1
при k → ∞ переходит в равенство P P
∞
=
P
∞
. Приравнивая левые нижние блоки этих блочных матриц, имеем
Q + RQ
(∞)
= Q
(∞)
⇒ Q = (E − R)Q
(∞)
. Поскольку матрица R удо-
влетворяет условию леммы 3, то из последнего равенства получаем
Q
(∞)
= (E − R)
−1
Q. ¤
Задача 1. Найдите предельные вероятности перехода для по-
глощающей марковской системы из примера 1.
Замечание 1. Результаты относительно поглощающих систем
применимы к приводимым марковским системам общего вида. По-
ясним это применение неформально. Составим поглощающую си-
стему, заменив в матрице (3) блоки P
1
, . . . , P
m
единицами, а бло-
ки Q
1
, . . . , Q
m
— суммами столбцов этих блоков. Эта упрощённая
(укрупнённая) модель отражает поведение исходной системы: веро-
ятность перехода за k шагов из невозвратного состояния в i-ую ком-
поненту равна вероятности для новой системы оказаться в i-ом по-
глощающем состоянии. Равны и соответствующие предельные веро-
ятности.
2. Эргодические марковские системы. Марковская систе-
ма с матрицей переходных вероятностей P = (p
ij
) называется эрго-
дической, если для всех i, j существуют положительные пределы
lim
k→∞
p
(k)
ij
= π
j
, (6)
не зависящие от i.
Другими словами, марковская система с матрицей P переход-
ных вероятностей — эргодическая, если последовательность P
k
при
k → ∞ сходится к стохастической матрице вида
P
∞
=
π
1
. . . π
n
.. . . . ..
π
1
. . . π
n
с положительными элементами.
§ 6. Цепи Маркова                                                 45


   Далее, из формулы (5) видно, что элементы матрицы Q(k) с ро-
стом k могут лишь возрастать, а поскольку они, будучи вероятно-
стями, ограничены сверху числом 1, то матрицы Q(k) сходятся при
k → ∞ к некоторому пределу Q(∞) .
   Мы доказали, что lim P k существует и имеет форму, указан-
                       k→∞
ную в теореме. Чтобы вывести формулу для Q(∞) , заметим, что ра-
венство P P k = P k+1 при k → ∞ переходит в равенство P P ∞ =
P ∞ . Приравнивая левые нижние блоки этих блочных матриц, имеем
Q + RQ(∞) = Q(∞) ⇒ Q = (E − R)Q(∞) . Поскольку матрица R удо-
влетворяет условию леммы 3, то из последнего равенства получаем
Q(∞) = (E − R)−1 Q. ¤
   Задача 1. Найдите предельные вероятности перехода для по-
глощающей марковской системы из примера 1.
   Замечание 1. Результаты относительно поглощающих систем
применимы к приводимым марковским системам общего вида. По-
ясним это применение неформально. Составим поглощающую си-
стему, заменив в матрице (3) блоки P1 , . . . , Pm единицами, а бло-
ки Q1 , . . . , Qm — суммами столбцов этих блоков. Эта упрощённая
(укрупнённая) модель отражает поведение исходной системы: веро-
ятность перехода за k шагов из невозвратного состояния в i-ую ком-
поненту равна вероятности для новой системы оказаться в i-ом по-
глощающем состоянии. Равны и соответствующие предельные веро-
ятности.
   2. Эргодические марковские системы. Марковская систе-
ма с матрицей переходных вероятностей P = (pij ) называется эрго-
дической, если для всех i, j существуют положительные пределы
                                  (k)
                             lim pij = πj ,                      (6)
                           k→∞

не зависящие от i.
    Другими словами, марковская система с матрицей P переход-
ных вероятностей — эргодическая, если последовательность P k при
k → ∞ сходится к стохастической матрице вида
                                        
                             π1 . . . πn
                     P ∞ =  .. . . . .. 
                             π1 . . . πn
с положительными элементами.

Страницы