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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

46 Глава 2. Ориентированные графы
Мы покажем, что наличие или отсутствие свойства эргодичности
определяется графом матрицы. Но для полного исследования потре-
буются некоторые свойства стохастической матрицы как линейного
оператора на пространстве R
n
столбцов.
Введём коэффициент эргодичности стохастической матрицы.
Вначале заметим, что для любых двух строк стохастической матрицы
P = (p
ij
) верны равенства
0 =
X
j
(p
i
1
j
− p
i
2
j
) =
X
j
+
(p
i
1
j
− p
i
2
j
) +
X
j
−
(p
i
1
j
− p
i
2
j
), (7)
где знаком “+” отмечена сумма положительных разностей, а знаком
“−” — сумма отрицательных. Коэффициентом эргодичности стоха-
стической матрицы P = (p
ij
) называется число
δ(P ) = max
i
1
,i
2
X
j
+
(p
i
1
j
− p
i
2
j
).
Упражнение 3. Докажите,что если P — положительная стоха-
стическая матрица, то δ(P ) < 1.
Пусть x = (x
j
) — столбец с вещественными элементами. Обозна-
чим через [x] отрезок [min
j
x
j
, max
j
x
j
] вещественной прямой, а через
d(x) — длину этого отрезка.
Лемма 3. Для любой стохастической матрицы P = (p
ij
)
1) [P x] ⊆ [x],
2) d(P
k
x) ≤ δ(P
k
)d(x), k = 1, 2, . . ..
Д о к а з а т е л ь с т в о. 1) Действительно,
max
i
(P x)
i
= max
i
(
X
j
p
ij
x
j
) ≤ (
X
j
p
ij
) max
j
x
j
= max
j
x
j
.
Аналогично доказывается, что и левый конец отрезка [P x] лежит в [x].
Пункт 2) достаточно доказать для k = 1, общий случай полу-
чается индукцией по k. Пусть максимальный элемент столбца (P x)
имеет номер i
1
, а минимальный — i
2
. Тогда
d(P x) = (P x)
i
1
− (P x)
i
2
=
P
j
p
i
1
j
x
j
−
P
j
p
i
2
j
x
j
=
=
P
j
(p
i
1
j
− p
i
2
j
)x
j
=
P
j
+
(p
i
1
j
− p
i
2
j
)x
j
+
P
j
−
(p
i
1
j
− p
i
2
j
)x
j
≤
≤
P
j
+
(p
i
1
j
− p
i
2
j
) max
j
x
j
+
P
j
−
(p
i
1
j
− p
i
2
j
) min
j
x
j
= (см. (7))
=
P
j
+
(p
i
1
j
− p
i
2
j
)d(x) ≤ δ(P )d(x). ¤
46                                                      Глава 2. Ориентированные графы


   Мы покажем, что наличие или отсутствие свойства эргодичности
определяется графом матрицы. Но для полного исследования потре-
буются некоторые свойства стохастической матрицы как линейного
оператора на пространстве Rn столбцов.
   Введём коэффициент эргодичности стохастической матрицы.
Вначале заметим, что для любых двух строк стохастической матрицы
P = (pij ) верны равенства
            X                     X+                    X−
      0=       (pi1 j − pi2 j ) =    (pi1 j − pi2 j ) +    (pi1 j − pi2 j ), (7)
                  j                     j                             j

где знаком “+” отмечена сумма положительных разностей, а знаком
“−” — сумма отрицательных. Коэффициентом эргодичности стоха-
стической матрицы P = (pij ) называется число
                               X+
                   δ(P ) = max     (pi1 j − pi2 j ).
                                       i1 ,i2
                                                j

   Упражнение 3. Докажите,что если P — положительная стоха-
стическая матрица, то δ(P ) < 1.
   Пусть x = (xj ) — столбец с вещественными элементами. Обозна-
чим через [x] отрезок [minj xj , maxj xj ] вещественной прямой, а через
d(x) — длину этого отрезка.
   Лемма 3. Для любой стохастической матрицы P = (pij )
   1) [P x] ⊆ [x],
   2) d(P k x) ≤ δ(P k )d(x), k = 1, 2, . . ..
   Д о к а з а т е л ь с т в о. 1) Действительно,
                          X                X
       max(P x)i = max(       pij xj ) ≤ (     pij ) max xj = max xj .
             i                 i                                  j       j
                                   j                j

Аналогично доказывается, что и левый конец отрезка [P x] лежит в [x].
   Пункт 2) достаточно доказать для k = 1, общий случай полу-
чается индукцией по k. Пусть максимальный элемент столбца (P x)
имеет номер i1 , а минимальный — i2 . Тогда
                                        P            P
          d(P x) = (P x)i1 − (P x)i2 = pi1 j xj − pi2 j xj =
                                         j
       P                   P+                      P− j
    = (pi1 j − pi2 j )xj =    (pi1 j − pi2 j )xj +   (pi1 j − pi2 j )xj ≤
         j                         j                          j
         P+                                    P
     ≤           (pi1 j − pi2 j ) max xj + − (pi1 j − pi2 j ) min xj = (см. (7))
         j                          j            j               j
                           P+
                        =         (pi1 j − pi2 j )d(x) ≤ δ(P )d(x). ¤
                           j

Страницы