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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

48 Глава 2. Ориентированные графы
P
d
:
P =
0 P
12
0 ... 0
0 0 P
23
... 0
.. .. .. .. ..
0 0 0 0 P
d−1,d
P
d1
0 0 0 0
, P
d
=
P
(d)
11
.
.
.
P
(d)
dd
.
Стохастические матрицы P
(d)
11
, . . . , P
(d)
dd
— см. §4, — примитивны. Рас-
сматривая их как матрицы новых эргодических марковских систем,
видим, что существует
lim
l→∞
P
dl
= (P
d
)
∞
=
(P
(d)
11
)
∞
.
.
.
(P
(d)
dd
)
∞
c положительными равнострочными стохастическими матрицами на
диагонали. Обозначим
((P
d
)
∞
)
jj
= lim
l→∞
p
(dl)
jj
= π
j
.
Число π
j
равно предельной вероятности перехода в j из j (а также из
любого состояния циклического класса [j]) через число шагов, крат-
ное d. Cуществуют также пределы
lim
l→∞
P
dl+r
= P
r
(P
d
)
∞
, r = 1, . . . , d − 1.
Матрица P
r
(P
d
)
∞
имеет ту же блочную структуру, что и P
r
, причём
с учётом теоремы 2 §3
(P
r
(P
d
)
∞
)
ij
= lim
l→∞
p
(dl+r)
ij
= π
j
, если t
ij
= r,
(P
r
(P
d
)
∞
)
ij
= p
(dl+r)
ij
= 0, l = 1, 2, . . . , если t
ij
6= r.
Таким образом, для любых состояний i, j последовательность p
(k)
ij
стремится к периодическому повторению с периодом d, при котором
серия d − 1 нулей сменяется числом π
j
.
Задача 2. Докажите, что марковская система с тремя состояни-
ями из примера 1 — эргодическая и найдите предельные вероятности
состояний.
48                                                   Глава 2. Ориентированные графы


Pd :
                                            
             0 P12 0         ...  0                                                
                                                                 (d)
            0  0 P23        ...  0                            P11
                                                                    ...          
     P =    .. .. ..        ..   ..         , Pd =                               .
            0  0  0          0 Pd−1,d                                       (d)
                                                                             Pdd
            Pd1 0  0          0   0
                                 (d)           (d)
Стохастические матрицы P11 , . . . , Pdd — см. §4, — примитивны. Рас-
сматривая их как матрицы новых эргодических марковских систем,
видим, что существует
                                                        
                                      (d) ∞
                                   (P )
                 dl   d ∞     11           ...          
            lim P = (P ) =                              
           l→∞                                     (d) ∞
                                                (Pdd )
c положительными равнострочными стохастическими матрицами на
диагонали. Обозначим
                                                     (dl)
                       ((P d )∞ )jj = lim pjj = πj .
                                           l→∞

Число πj равно предельной вероятности перехода в j из j (а также из
любого состояния циклического класса [j]) через число шагов, крат-
ное d. Cуществуют также пределы
                lim P dl+r = P r (P d )∞ , r = 1, . . . , d − 1.
               l→∞

Матрица P r (P d )∞ имеет ту же блочную структуру, что и P r , причём
с учётом теоремы 2 §3
                                          (dl+r)
             (P r (P d )∞ )ij = lim pij            = πj , если tij = r,
                                 l→∞

                            (dl+r)
        (P r (P d )∞ )ij = pij         = 0, l = 1, 2, . . . , если tij 6= r.
                                                                                         (k)
   Таким образом, для любых состояний i, j последовательность pij
стремится к периодическому повторению с периодом d, при котором
серия d − 1 нулей сменяется числом πj .
    Задача 2. Докажите, что марковская система с тремя состояни-
ями из примера 1 — эргодическая и найдите предельные вероятности
состояний.

Страницы