Remark 4.5.3. 不等式 (4.5) は, 推移確率行列の成分をみているだけではわから ない. 時刻 0 で頂点 j にいて, 時刻 m+n で頂点 j にいく路のうち, 特別な路を たどっているものの確率が (4.5) の右辺を表していると考えればよい.
Definition 4.5.4 (周期性). 既約な確率推移行列 P から作られるランダムウォー クが周期的であるとは, P から作られるグラフのすべての頂点が周期的であるこ とをいう. また,すべての頂点が非周期的であるとき,非周期的であるという.
グラフ Gを強連結としているので, この定義の「すべての頂点」の部分を「あ る頂点」と書き換えてもよい.
周期性の定義はこれでよいのだが, 我々が知りたいのは「行列 P をみて, 周期 的か否かを判定できるか？」ということである. これに関しては, 次の定理が成り 立つ.
Theorem 4.5.5 (非周期的となるための一つの十分条件). 既約な確率行列 P で 定義されたランダムウォークは,P の対角成分{pii}のうち１つでも正のものがあ れば, 非周期的となる.
Proof. P は既約と仮定しているので, P から作られるグラフは G は強連結とな
る. よって, ランダムウォークが非周期的となるためには, どれか一つの頂点が非 周期的であればよい. 仮定より, ある i ∈ {1, . . . N} が存在して, pii >0 となって いる. これは, 頂点 i の周期 ki が ki = 1 であることを意味している. よって, こ のランダムウォークは非周期的である.
ここまでで, 確率行列 P をみて, 非周期性を判定する一つの条件を得ることが できた. 非周期性と固有値の関係としては,以下の定理が成り立つ.
Theorem 4.5.6. 既約な確率行列P で定義されたランダムウォークが非周期的な らば,P の固有値λ で |λ|= 1 となるものはλ= 1に限る. 特に, すべての成分が 正であるような任意の初期分布 π(0)は, t→ ∞ の時,不変分布 π に収束する.
Remark 4.5.7. Theorem 4.5.6 で「すべての成分が正であるような任意の初期分 布」と言っている理由は, Theorem 3.8.1 で,「ほとんどすべての初期ベクトル」と 言っていることに起因する. (cf. Remark 3.8.2.)
Example 4.5.8. Example 4.4.5 で出てきたグラフ G を考えよう.
1
2 3 5
4
このグラフは「周期的」となる例として紹介したもので, PGと周期と思われるPG3 を計算すると,
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
, PG3 =
1
2 0 0 0 12 0 12 0 12 0 0 0 1 0 0 0 12 0 12 0
1
2 0 0 0 12
となっている.
Remark 4.5.9. Example 4.5.8は,PG3 の対角成分に正の値が出てくることから周 期的であり, その周期が 3であると結論したいのだが,実はそうはいかない. 周期 性の定義は,「k ステップで戻ってくる確率が正となるような k の最大公約数が2 以上である」ことなので,例えば, Example 4.5.8では, 3の倍数でないk に対して PGk の対角成分に正の値が出てこないことを示すか, e2πi/3 を固有値に持つことを 示すかをしないと周期的であるとは結論できない. 実際,
x= (1, e2πi/3,2e4πi/3, e2πi/3,1)T
ととると, PGx =e2πi/3x が成り立つので, PG は e2πi/3 を固有値に持つことがわ かる.
Example 4.5.10. 次のようなグラフを考えてみよう.
1
2 3 5
4 6
このグラフの推移確率行列は
PG =
0 1 0 0 0 0
0 0 1/2 0 0 0
1 0 0 0 1 0
0 0 1/2 0 0 0
0 0 0 0 0 1
0 0 0 1 0 0
となり, PG3,P4 はそれぞれ,
PG3 =
1
2 0 0 0 12 0 0 12 0 0 0 12 0 0 12 1 0 0 0 12 0 0 0 12 0 0 12 0 0 0
1
2 0 0 0 12 0
, PG4 =
0 12 0 0 0 12 0 0 14 12 0 0
1
2 0 12 0 12 0 0 0 14 12 0 0
1
2 0 0 0 12 0 0 12 0 0 0 12
となり, 3 ステップと 4 ステップで戻ってくる確率が正である. よって, このグラ フは非周期的となる. 実際, PG の固有値は, 近似的に
{1.0000,−0.17610 + 0.86072i,−0.17610−0.86072i,−0.64780,0,0} となり, 確かに非周期的である.
Remark 4.5.11. Example 4.5.8 のグラフの閉路の長さはすべて 3 の倍数であ るので, このグラフの上の単純ランダムウォークは周期的であると想像できるが,
Example 4.5.10 のグラフの閉路の長さには,少なくとも 3 のものと 4 のものが含
まれて, それらは互いに素であるので, このグラフの上の単純ランダムウォークは 非周期的であると想像できる.
Example 4.5.12. 確率推移行列の対角成分がすべて0 であっても,固有値の絶対 値が 1 になるものがλ = 1に限る例は簡単に見つかる. 下の図で表されるグラフ G を考える.
1
2 3
ととれば,確率推移行列 PG は
PG =
0 1/2 1/2 1/2 0 1/2 1/2 1/2 0
となり, 固有値は {1,−1/2,−1/2} となる.