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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

§ 6. Цепи Маркова 43
1. Поглощающие марковские системы Нормальная форма
матрицы приводимой марковской системы имеет вид
P
1
.
.
.
P
m
Q
1
. . . Q
m
R
. (3)
Матрица P
l
состоит из вероятностей перехода внутри l-ой минималь-
ной компоненты системы, матрица Q
l
— из вероятностей перехода
из множества невозвратных состояний в состояния l-ой минимальной
компоненты, а матрицу R составляют вероятности перехода внутри
класса невозвратных состояний.
Рассмотрим частный, но важный случай поглощающих марков-
ских систем. Марковская система называется называется поглощаю-
щей, если её минимальные компоненты одноэлементны. Как видно,
свойство быть поглощающей системой есть свойство графа системы.
Дадим описание таких систем, не использующее явно понятие ми-
нимальной компоненты. Вначале определим поглощающее состояние
марковской системы как такое состояние i, из которого нельзя выйти,
то есть, p
ii
= 1. На графе системы поглощающее состояние выделя-
ется тем, что из него выходит единственная дуга — петля.
Упражнение 2. Поглощающая марковская система — это си-
стема, в которой имеются поглощающие состояния, причём из любого
состояния достижимо поглощающее состояние.
Нормальная форма матрицы для поглощающей системы имеет
совсем простой вид: блоки P
1
, . . . , P
m
— это единичные матрицы по-
рядка 1, а блоки Q
1
, . . . , Q
m
представляют собой столбцы. Объединив
их в матрицу Q, получим матрицу вида
P =
µ
E 0
Q R
, соответственно, P
k
=
µ
E 0
Q
(k)
R
k
. (4)
Для вероятностей перехода за k шагов из невозвратных состояний
в поглощающие состояния, составляющих матрицу Q
(k)
, имеет место
формула
Q
(k)
= (
k−1
X
h=0
R
h
)Q, (5)
которая доказывается индукцией по k.
Рассмотрим функцию kAk = max
n
i=1
P
n
j=1
|a
ij
|, определённую на
комплексных матрицах порядка n. Она является матричной нормой
§ 6. Цепи Маркова                                                    43


   1. Поглощающие марковские системы Нормальная форма
матрицы приводимой марковской системы имеет вид
                                     
                       P1
                          ...        
                                     .           (3)
                                Pm   
                       Q 1 . . . Qm R
Матрица Pl состоит из вероятностей перехода внутри l-ой минималь-
ной компоненты системы, матрица Ql — из вероятностей перехода
из множества невозвратных состояний в состояния l-ой минимальной
компоненты, а матрицу R составляют вероятности перехода внутри
класса невозвратных состояний.
    Рассмотрим частный, но важный случай поглощающих марков-
ских систем. Марковская система называется называется поглощаю-
щей, если её минимальные компоненты одноэлементны. Как видно,
свойство быть поглощающей системой есть свойство графа системы.
Дадим описание таких систем, не использующее явно понятие ми-
нимальной компоненты. Вначале определим поглощающее состояние
марковской системы как такое состояние i, из которого нельзя выйти,
то есть, pii = 1. На графе системы поглощающее состояние выделя-
ется тем, что из него выходит единственная дуга — петля.
    Упражнение 2. Поглощающая марковская система — это си-
стема, в которой имеются поглощающие состояния, причём из любого
состояния достижимо поглощающее состояние.
    Нормальная форма матрицы для поглощающей системы имеет
совсем простой вид: блоки P1 , . . . , Pm — это единичные матрицы по-
рядка 1, а блоки Q1 , . . . , Qm представляют собой столбцы. Объединив
их в матрицу Q, получим матрицу вида
             µ         ¶                          µ          ¶
               E 0                            k       E   0
        P =                , соответственно, P =               .    (4)
               Q R                                   Q(k) Rk
    Для вероятностей перехода за k шагов из невозвратных состояний
в поглощающие состояния, составляющих матрицу Q(k) , имеет место
формула
                                 k−1
                                 X
                          (k)
                        Q =(         Rh )Q,                     (5)
                                  h=0
которая доказывается индукцией по k. P
   Рассмотрим функцию kAk = maxni=1 nj=1 |aij |, определённую на
комплексных матрицах порядка n. Она является матричной нормой

Страницы