が成り立つ. なぜなら, P は確率行列であったので, P のどの列を取っても, その 要素の和は 1となる. よって,PT のどの行を取っても, その要素の和は 1 となる.
すなわち, 任意の i に対して
N
X
j=1
pji = 1 が成り立つ. 一方, PTe の第j 列を考え ると, その値は
n
X
j=1
pjiei =
n
X
j=1
pji = 1 となるので, PTe = e が成り立つ. すなわ ち, 1は PT の固有値となる.
一方, ガーシュゴリンの定理の帰結（Theorem 3.8.4）を PT に適用すれば,PT のすべての固有値 λ は
|λ| ≤ max
i=1,...,N N
X
j=1
pji = 1
が成り立つ. すなわち 1 は PT の固有値の中で絶対値が最大の固有値である.
ここで,PT の固有値と P の固有値は一致することを使えば, P は 1 を固有値 に持ち, 1 が絶対値最大の固有値であることがわかる. 特に, 固有値 1 の重複度は 1 となる.
ここで,再びペロン・フロベニウスの定理を使えば,P の絶対値最大の固有値1 の固有ベクトルとして,すべての要素が正のものを取ることができる. そのベクト ルを x= (xi) とおいたとき,
π = xi
PN j=1xj
!
ととれば,π は P の固有値 1に対する固有ベクトルであり,確率分布となる.
★ ページランクとの関係
これで一見すると,前節のProblem 4.3.17 またはProblem 4.3.18 の解答を得た ように見える. たしかに, グラフ Gが強連結であれば, Problem 4.3.18は肯定的に 解決できた. しかし, 次のような例を考えれば, Problem 4.3.17 を肯定的に解決し たとは言えない.
Example 4.4.4. 下の図で表されるグラフ G を考える.
このグラフ Gの推移確率行列 PG は
PG= 0 1 1 0
!
であり, その固有値は1,−1となり, すべての固有値の絶対値が1 となる. 特に, 1 に対する固有ベクトルはx1 = 1
1
!
, −1 に対する固有ベクトルはx2 = 1
−1
! と なり, 例えばπ(0) = 1
0
!
= 1
2x1+1
2x2 ととると, lim
n→∞π(n)は存在しない. 特に, π(2n) = 1
0
!
, π(2n+ 1) = 0 1
!
となり, 同じ状態が交互にあらわれる.
この例は極端な例であるが,もう少しだけマトモな例をあげてみよう.
Example 4.4.5. 下の図で表されるグラフ G を考える.
1
2 3 5
4
このグラフ Gの確率推移行列 PG は
PG=
0 1 0 0 0
0 0 1/2 0 0
1 0 0 0 1
0 0 1/2 0 0
0 0 0 1 0
であり,絶対値が1 となる固有値が３つ存在する. （1 以外の絶対値1の固有値は
e2πi/3 とe−2πi/3 である.）この例でも,時刻 0で頂点 3に存在する確率が1 である
と仮定すると, 時刻3n でも頂点 3 に存在する確率が1 となる.
Remark 4.4.6. いずれの例であっても,不変分布の存在は Theorem 4.4.3で保証 されているんだが, 「絶対値最大固有値を計算するベキ乗法」 (Theorem 3.8.1)を 考えると,任意の初期分布 π(0)に対して
n→∞lim Pnπ(0) がいつでも存在することが言えない.
固有値の絶対値が 1 であるような固有値が 1 以外に存在しているので, その固 有値の固有ベクトルが張る部分空間の成分が「くるくると回転する成分」として 出てくるため, 上の極限が存在しないことが想像できる. (cf. Example 3.7.4).
したがって,「ある一定時間ごとに同じ状態が繰り返される」こと,または,「絶 対値が 1である固有値が 1 以外に存在する」ことが, 任意の初期分布に対してそ の長時間後の分布が不変分布に収束しないことの障害になっていると考えられる.