# 定常分布 ## 定義 定常分布(stationary distribution)とは、有向グラフ(またはマルコフ連鎖)の各頂点に割り当てられた確率分布のうち、1 ステップのランダムウォークを経ても分布自体が変化しないものをいう。形式的には、頂点集合上の非負の割り当て `Pr[at x]`(`Σ_x Pr[at x]=1`)が、全頂点 `x` について `Pr[at x] = Pr[go to x at next step] = Σ_{edges⟨y→x⟩} Pr[at y]/outdeg(y)` を満たすとき定常分布と呼ぶ(定義20.2.1)。強連結な有向グラフは高々 1 つの定常分布しか持たず(最大希釈率(maximum dilation)という量を使った背理法で示される)、十分に長いランダムウォークの分布はどの頂点から出発してもこの定常分布に近づく。一方、一般の(強連結でない、あるいは特殊な構造を持つ)有向グラフでは、定常分布が複数存在する場合や、定常分布は存在してもランダムウォークがそこへ収束しない場合がある——後者の典型例は、2 頂点間を確率 1 で往復するだけの周期 2 のグラフで、この場合「一様分布」自体は定常分布の条件を満たすが、1 点から出発したウォークの分布は永久に振動し続け収束しない。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] §20.2.3) ## 横断的知見 - **PageRank を「定常分布」として定式化する際、離散数学の教科書(組合せ論的アプローチ)と統計学の教科書(線形代数的アプローチ)は、同じ数学的対象に到達する 2 つの異なる証明・計算の道具立てを提示する**: Mathematics for Computer Science 第20章は、定常分布の存在・一意性を「強連結性 + 最大希釈率を使った背理法」というグラフ理論的な議論で示し、計算方法についても線形方程式系(20.15)-(20.16)を解く枠組みとして提示するにとどまる。一方 [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] §14.10 は同じ再帰式(`Rank(x)=Σ Rank(y)/outdeg(y)` に相当する式14.107)を行列形式 `p=Ap`(式14.109)として捉え直し、最大固有値 1 に対応する固有ベクトルを**べき乗法(power method)**で数値的に求める具体的アルゴリズムを与え、`A` をランダムサーファーの遷移確率行列とみなすことで PageRank 解がマルコフ連鎖の定常分布に一致すると明示する。両者は「定常分布の存在と一意性の保証」(MCS: グラフ理論的議論)と「定常分布の実際の計算法」(ESL: 線形代数的な反復法)という、同じ概念の異なる側面をそれぞれ担っている。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] §20.2.3, [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] §14.10) - **「強連結性」と「収束性」が独立な性質であることは、MCS 第20章が明示的に注意している一方、ESL 第14章はこの区別に触れず既に良い性質を持つ設定として扱っている**: MCS はスーパー頂点の追加によりグラフを強連結にすることが一意性を保証すると述べつつ、一般の強連結グラフでもランダムウォークの分布が定常分布へ収束するとは限らない(周期性のあるグラフが反例になりうる)ことを演習で扱う(§20.2.3、演習20.8)。ESL は、べき乗法が収束することを前提として提示しており、収束の条件(既約性に加えて非周期性が必要という、マルコフ連鎖理論での標準的な要件)には立ち入らない。教科書の対象読者(離散数学入門 vs 統計的学習理論)の違いが、同じ収束性の議論の掘り下げ方に差を生んでいる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] §20.2.3, [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] §14.10) - **待ち行列理論の生死過程(birth-death process)における定常状態確率の導出は、本ページが扱う離散時間ランダムウォークの定常分布と同じ「釣り合い条件から連立方程式を立てて解く」という構造を、連続時間・可算無限状態空間に拡張した具体例を与える**: [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] の定常分布は、有向グラフ上の1ステップ遷移で分布が変化しないという条件(`Pr[at x] = Σ Pr[at y]/outdeg(y)`)を全頂点について連立させ、線形方程式系を解いて得る。[[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 31 Analysis of a Single Queue]] の生死過程は、状態 n(系内客数、可算無限個)の間の遷移を到着率 λn・サービス率 µn で表し、隣接状態間の局所的な釣り合い条件(流入=流出)0=λj-1pj-1-(µj+λj)pj+µj+1pj+1 から定常状態確率 pn を p0 の関数として求める(定理31.1)。MCS のグラフ理論的定式化(有限または可算の状態・離散時間ステップ・任意の遷移構造)に対し、生死過程は連続時間・無限状態だが遷移が隣接状態間(n↔n±1)に限定されるという特殊構造を持ち、この制約のおかげで pn が p0 の閉じた形の積として表せる——一般のマルコフ連鎖では成り立たない性質である。両者を重ねると、定常分布を求める「釣り合い条件を連立させる」という手法自体は連続/離散・有限/無限状態を問わず共通する一方、状態遷移の構造(隣接状態間のみか、任意のグラフか)が解の閉じた形の可否を左右することが分かる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] §20.2.3, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 31 Analysis of a Single Queue]] §31.1) - **待ち行列ネットワークの積形式(product form)は、生死過程の定常状態確率が p0 の閉じた形の積で書けるという性質(本ページ既出)を、単一のキューから複数のキューが接続されたネットワークへ拡張したものである**: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 31 Analysis of a Single Queue]] §31.1 の生死過程は、状態遷移が隣接状態間(n↔n±1)に限られるという特殊構造のおかげで pn が閉じた形で求まることを示す。[[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 32 Queueing Networks]] §32.2 は、系全体の定常状態確率が各サービスセンターの項 fi(ni) の積として書けるネットワーク(積形式ネットワーク)を示し、この性質が成り立つ条件を Jackson(任意の開放型ネットワーク)、Gordon-Newell(閉鎖型ネットワークへの拡張)、BCMP(サービス規律・ジョブクラス等の条件下でのさらなる一般化)、Denning-Buzen(ジョブフローバランス等のより弱い条件での非マルコフ的拡張)という順に広げてきた研究史として整理する。両者を重ねると、状態空間の次元(1つのキューの客数 対 複数のキューそれぞれの客数)が増えても、遷移構造に一定の局所性・分離可能性がある限り定常分布が積の形で保たれるという、より一般的なパターンが見える。ただし第32章は、積形式が成り立つネットワークの内部フローが一般にポアソン過程ではないことを明示しており、「サービスセンター間が見かけ上独立に見える」ことと「実際に独立な過程が流れている」ことは異なる点に注意が必要である。(Source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 31 Analysis of a Single Queue]] §31.1, [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 32 Queueing Networks]] §32.2) ## 未解決の問い - 積形式ネットワークが成り立つ条件(BCMP・Denning-Buzen)は、本ページが既に指摘した「強連結性+非周期性」という一般マルコフ連鎖の収束条件とどう対応するか。第32章はBCMP・Denning-Buzenの条件を積形式が成り立つための十分条件として提示するのみで、これらの条件と一般マルコフ連鎖の収束理論との関係には立ち入っていない。 - MCS 第20章が演習で示唆する「収束しない強連結グラフ」の反例(周期を持つグラフ)は、マルコフ連鎖理論の「非周期性(aperiodicity)」要件に対応すると考えられるが、本章はこの用語を明示的には使わない。ESL 第14章もべき乗法の収束条件としてこの要件を明示していないため、本 vault 内では「強連結 + 非周期」が定常分布への収束の十分条件であることを明言するソースがまだない。 - べき乗法(ESL)による定常分布の数値計算と、線形方程式系(MCS)を直接解く方法との計算量比較(頂点数が数兆に達する Web グラフでの実用性の違い)は、いずれのソースにも定量的な記述がない。 - 生死過程が定常分布へ実際に収束する条件(既約性・再帰性等、連続時間マルコフ連鎖のエルゴード性に相当する条件)は、[[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 31 Analysis of a Single Queue]] では明示的に述べられていない(安定条件 ρ<1 のみが議論される)。これは MCS が扱う「強連結性+非周期性」に相当する条件と本質的に同じ問いだと考えられるが、連続時間・無限状態への一般化を明示するソースは本 vault 内にまだない。 ## 関連 - 概念: [[ランダムウォーク]] / [[PageRank]] / [[有向グラフ]] / [[待ち行列理論]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 20 Random Walks]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 14 Unsupervised Learning]] / [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 31 Analysis of a Single Queue]] — 生死過程の定常状態確率の導出(§31.1)。 - source: [[@1991__Wiley__The Art of Computer Systems Performance Analysis - Chapter 32 Queueing Networks]] — 積形式ネットワーク(product form)、生死過程の閉じた形の解を複数キューのネットワークへ拡張した性質(§32.2)。 ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 20 §20.2.3. - Hastie, Tibshirani, Friedman, *The Elements of Statistical Learning*, 2nd edition, Chapter 14 §14.10. - Raj Jain, *The Art of Computer Systems Performance Analysis*, John Wiley & Sons, 1991, Chapter 31, §31.1. - Raj Jain, *The Art of Computer Systems Performance Analysis*, John Wiley & Sons, 1991, Chapter 32, §32.2.