Aritalab:Lecture/NetworkBiology/Markov Chains

Latest revision as of 00:35, 21 October 2011

[edit] マルコフ連鎖

離散確率過程 $X_0, X_1, X_2 \ldots$ は

$\mbox{Prob}(X_t = a_t | X_{t-1} = a_{t-1}, X_{t-2} = a_{t-2}, \ldots X_0 = a_0 ) = \mbox{Prob}(X_t = a_t | X_{t-1} = a_{t-1})$

を満たすときにマルコフ連鎖 (Markov chain) と呼ばれます。マルコフとはロシアの統計学者 Andrei A. Markov (1856-1922) のことで、マルコフ連鎖に関する多くの功績を残しました。状態 (state) $X_t$ が状態 $X_{t-1}$ のみに依存して決まる性質をマルコフ性 (Markov property) または無記憶性 (memoryless property) といいます。

マルコフ連鎖において状態 i から j への遷移確率を $p_{ij} = \mbox{Pr}(X_t = j | X_{t-1} = i )$ と書けば、マルコフ連鎖は遷移行列

${\mathbf P} = \begin{bmatrix} p_{11} & p_{12} & \cdots & p_{1j} & \cdots \\ p_{21} & p_{22} & \cdots & p_{2j} & \cdots \\ \vdots & \vdots & \ddots & \vdots & \ddots \\ p_{i1} & p_{i2} & \cdots & p_{ij} & \cdots \\ \vdots & \vdots & \ddots & \vdots & \ddots \\ \end{bmatrix}$

で記述できます。^[1] 遷移確率を表すので行列の行方向に足し合わせた値は必ず 1 になっており、確率行列 (stochastic matrix) と呼ばれます。もし行方向に足し合わせても 1 になる場合、二重確率行列 (doubly stochastic matrix) と呼ばれます。

記法を拡張し、i から j へ正確に m ステップで移る遷移確率を

$p_{ij}^{(m)} = \mbox{Prob}(X_{t+m} = j | X_{t} = i )$

と書きましょう。右肩にある (m) という表記は、m ステップ後という意味で m 乗ではありません。1ステップ目で移動した先を k と書くと $\textstyle p_{ij}^{(m)} = \sum_{k} p_{ik} \cdot p^{(m-1)}_{kj}$ であるから、遷移行列 ${\mathbf P}$ を m 乗すれば正確に m ステップで移った先を示す遷移行列を得ます（数学的帰納法）。また記法をそろえるために

$p_{ij}^{(1)} = p_{ij}$

$p_{ij}^{(0)} = \begin{cases}\textstyle 1 & (j = i)\\ 0 & (j \not= i) \end{cases}$

と定義します。

[edit] チャップマン-コルモゴロフの等式

m ステップの遷移を、 s ステップと m − s ステップに分解する以下の式は、チャップマン-コルモゴロフの等式と呼ばれます^[2]。

$p^{(m)}_{ij} = \textstyle\sum^{\infty}_{k=1} p^{(s)}_{ik} p^{(m-s)}_{kj} \quad (0 < s < m)$

以下でも $p^{(m)}_{ij} \geq p^{(s)}_{ik} p^{(m-s)}_{kj}$ という式をよく使います。

[edit] 既約

状態 i から j へ何ステップかで到達できる場合、j は i から到達可能 (accessible) と呼びます。互いに到達可能な状態 i, j どうしを連結 (communicate) しているといい、 $i \leftrightarrow j$ と書きます。連結性により同値類が形成されます。

反射律 (reflexivity): いかなる状態 i も、 $i \leftrightarrow i$
対称律 (symmetry): $i \leftrightarrow j$ なら $j \leftrightarrow i$
推移律 (transitivity): $i \leftrightarrow j$ かつ $j \leftrightarrow k$ なら $i \leftrightarrow k$

全ての状態が同じ同値類 (communication class) に属すとき、つまり全ての頂点が互いに連結なとき、マルコフ連鎖は既約 (irreducible) といいます。既約なマルコフ連鎖とは、グラフ表現すると強連結 (strongly connected) になっていて、任意の頂点から任意の頂点に移動できる場合に相当します。

また、状態集合 C は、C に属すどの状態からも C 以外の状態に抜け出せないとき、閉じている (closed) といいます。例えば、グラフ表現した際に外に出る辺をもたない状態だけからなる集合は閉じています。

例： 1次元のウォーク

0 と N の間を左右に1ステップずつ移動し、0, N を吸収状態とするランダムウォークを考えます。0 から N までの状態は 3 つの同値類 {0}, {1, 2, ..., N−1}, {N} に分かれ、{0, N} は閉じています。

[edit] 周期性

状態 i に戻ってくるまでのステップ数が自然数 k (>1) の倍数回に限られ、しかも k がこの性質を持つ最大公約数の場合、状態 i は周期 k でといいます。 k = 1 のとき、状態は非周期的であるといいます。マルコフ連鎖の中で同じ同値類に属する (communicativeな) 状態 i, j は同じ周期をもちます^[3]。

例：円周上のウォーク

円周上に配置された N 状態が一方向につながったマルコフ連鎖は、規約で周期 N を持ちます。遷移行列 P を N 乗すると、恒等行列 I になります。

例： 1次元のウォーク

原点からスタートして左右に1ステップずつ移動するウォークでは、原点に戻るまでのステップ数が必ず偶数です。つまり、状態 0 は周期 2 になります。いずれの状態も周期は 2 です。

[edit] 再帰性

状態 i から出発し時刻 t になって初めて j に到達する確率を $f^{(t)}_{ij}$ と書くことにします。前出の $p^{(t)}_{ij}$ は複数回 j を訪れることを許すため、 $f^{(t)}_{ij} \leq p^{(t)}_{ij}$ となります。

[edit] 再帰時間

同じ状態に初めて戻る確率 $f^{(t)}_{ii}$ を初再帰確率 (first return probability) と呼び $f^{(0)}_{ii} = 0$ と定義します。状態 i は

$\textstyle \sum_{t=1}^{\infty} f^{(t)}_{ii} < 1$ であれば再帰不確実 (transient)

$\textstyle \sum_{t=1}^{\infty} f^{(t)}_{ii} = 1$ であれば再帰確実 (recurrent)

と呼びます。全ての状態が再帰確実であれば、マルコフ連鎖自体を再帰確実と呼びます。

[edit] 平均初再帰時間 MFRT

状態 i における平均初再帰時間 (mean first return time または mean recurrence time) を

$\mu_{ii} = \textstyle\sum^{\infty}_{t=1} tf^{(t)}_{ii}$

と書きます。状態 i が再帰不確実な場合は $\mu_{ii} = \infty$ です。

状態 i が再帰確実でも $\mu_{ii}$ が有限とは限りません。初再帰時間の期待値が有限なとき有限再帰 (positive recurrent)、そうでない場合をゼロ再帰 (null recurrent) と呼びます。ゼロ再帰性を満たすには無限の状態数が必要です。

例：2 × 2 行列

以下の確率行列を持つ 2 状態のマルコフ連鎖は有限再帰的です。

${\mathbf P} = \begin{bmatrix} p_{11} & p_{12} \\ p_{21} & p_{22} \\ \end{bmatrix}\quad 0 < p_{ii} < 1 \ (i = 1,2)$

直感的には 2 状態の間を自由に行き来できるため、必ず戻ってきます^[4] 。

例：ゼロ再帰的なマルコフ連鎖

正の整数値に対応するマルコフ連鎖を仮定し、状態 i から確率 i/(i + 1) で状態 i + 1 に、確率 1/(i + 1) で状態 1 に移動するとします。

${\mathbf P} = \begin{bmatrix} 1/2 & 1/2 & 0 & 0 & \cdots \\ 1/3 & 0 & 2/3 & 0 & \cdots \\ 1/4 & 0 & 0 & 3/4 & \cdots \\ 1/5 & 0 & 0 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots \end{bmatrix}$

高い確率で無限遠に進んでいけるため、状態 1 に初めて戻るまでの期待値は無限大でゼロ再帰的です^[5]。

[edit] 通過時間、平均初通過確率 MFPT

状態 i から始めて j に最初に訪れる確率 $f^{(t)}_{ij}$ を初通過確率 (first passage time probability) と呼び、 $f^{(0)}_{ij} = 0$ と定義します。平均初通過時間 (mean first passage time; MFPT) も同様に定義します。

$\mu_{ij} = \textstyle\sum^{\infty}_{n=1} nf^{(n)}_{ij}$

[edit] 定常分布

マルコフ連鎖の遷移行列 $\mathbf P$ に対して

$\bar\pi = \bar\pi \mathbf P$

を満たし、要素の総和が 1 、つまり $\textstyle \sum_i \pi_i = 1$ となるような行ベクトル $\bar\pi = (\pi_0, \pi_1, \ldots, \pi_n)$ を定常分布 (stationary distribution) といいます。定常分布は P^T の固有値 1 に対応する固有ベクトルともみなせます。状態数が有限の場合は 1 を必ず固有値に持つので定常分布が存在しますが、ただ一つに定まるとは限りません。

例：無限個の定常分布を持つマルコフ連鎖

確率行列が n 次元の単位行列 I のとき、定常状態は無限にあります。固有値 λ (n個) は全て 1 で、このマルコフ連鎖は既約ではありません (reducible)。

例：定常分布を持たないマルコフ連鎖

正の整数値に対応するマルコフ連鎖を仮定し、状態 i から i, i + 1, i + 2 ... にそれぞれ 1/2, 1/4, 1/8 ... の確率で遷移するとします。各状態が再帰不確実なため、定常状態 π はゼロベクトルになってしまいます。

${\mathbf P} = \begin{bmatrix} 1/2 & 1/4 & 1/8 & 1/16 & 1/32 & \cdots \\ 0 & 1/2 & 1/4 & 1/8 & 1/16 & \cdots \\ 0 & 0 & 1/2 & 1/4 & & 1/8 & \cdots \\ 0 & 0 & 0 & 1/2 & 1/4 & \cdots \\ \vdots & \vdots & \vdots & \vdots \end{bmatrix}$

[edit] 定常分布をもつ条件

既約で、再帰確実かつ非周期的（エルゴード的）なマルコフ連鎖は唯一つの定常分布 $\bar\pi$ を持ち、再帰時間の期待値との間に

$\textstyle \pi_i = \lim_{t\rightarrow \infty} p^{(t)}_{ji} = 1/\mu_{ii}$

が成り立ちます。この証明および関連する定理は、定常分布のページを参照してください。これは再帰時間の期待値が出発する状態 j に依存しないことを意味し、再帰までのステップ数期待値が $\mu_{ii}$ ならば状態 i に戻ってくる確率が $1/\mu_{ii}$ であることに対応します。定常状態において、各状態での存在確率は出発点に依存しません。

$\textstyle \lim_{t \rightarrow \infty} p^{(t)}_{ji} = \lim_{t \rightarrow \infty} p^{(t)}_{ii} = 1/\mu_{ii}$

さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意します。つまり全ての状態 i, j に対し、i から出ていく確率の和は、i に入ってくる確率の和に等しく $\pi_i$ になります。

$\textstyle \sum^n_{j=0}\pi_i p_{ij} = \sum^n_{j=0}\pi_j p_{ji} = \pi_i$

エルゴード的であれば定常分布がただ一つに定まることを証明しましょう。仮に定常分布が二つあるとして、もう一つの分布を $\bar\phi$ と書きます。定常分布であるから

$\phi_i = \textstyle\sum_k \phi_k p^{(t)}_{ki} \xrightarrow{t \rightarrow \infty} \sum_k \phi_k \pi_i = \pi_i \sum_k \phi_k = \pi_i$

すなわち $\bar \phi = \bar \pi$ です。

[edit] 参考・解説

↑ 状態 i から j への遷移確率を p_ij とする記法が主流ですが (Karlin & Taylor 1975)、Linda JS Allen (2011 2nd Ed) では j から i への遷移確率を p_ij と定義しています。そうすると定常分布を考える際に以下で書くように行ベクトル π を用いて $\bar\pi = \bar\pi \mathbf P$ とするのではなく、列ベクトルを用いて $\bar\pi = \mathbf P \bar\pi$ と書けるようになります。記法上の問題であり、本質はかわりません。
↑
チャップマン-コルモゴロフの等式の証明
$\begin{align} p^{(m)}_{ij} & = \mbox{Prob}\{X_m = j | X_0 = i \} \\ & = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j, X_s = k | X_0 = i \} \\ & = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j | X_s = k, X_0 = i \} \mbox{Prob}\{ X_s = k | X_0 = i \}\\ & = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j | X_s = k \} \mbox{Prob}\{ X_s = k | X_0 = i \} \\ & = \textstyle\sum^{\infty}_{k=1} p^{(m-s)}_{kj} p^{(s)}_{ik} \end{align}$
↑
同じ同値類に属する状態の周期が等しいことの証明
周期が 0 のときは自明。状態 i の周期が d(i) ≥ 1 と仮定します。状態 i から s ステップで i に戻る確率が 0 より大きくなる場合 $(p^{(s)}_{ii} > 0)$ 、d(i) は s を割り切ります。 i と j が同値類に属する場合、 i → j を m ステップ、 j → i を n ステップで移動することが可能 $(p^{(n)}_{ji} > 0, p^{(m)}_{ij} > 0)$ ですから $p^{(n + ks + m)}_{jj} \geq; p^{(n)}_{ji} \{ p^{(s)}_{ii} p^{(s)}_{ii} ... p^{(s)}_{ii}\} p^{(m)}_{ij} > 0$ となります。状態 j の周期は (n + ks + m) をどんな正の整数 k に対しても割り切るので、s も割り切ります。ここから d(j) ≤ d(i) が導かれます。同様の議論で d(i) ≤ d(j) も成り立つので d(i) = d(j) となります。
↑
例：2 × 2 行列が正再帰的になることの証明
確率行列は行方向の和が必ず 1 になるため、行列の要素は全て正の値をとります。一般に n ≥ 3 について $f^{(n)}_{11} = p_{12}p^{n-2}_{22}p_{21}$ が成立します。状態 1 の再帰確率は 1 になります。状態 2 についても同じです。しかし平均初再帰時間は有限になります。 $\begin{align} \textstyle\sum^{\infty}_{n=1}f^{(n)}_{11} &= p_{11} + p_{12}p_{21}\textstyle\sum^{\infty}_{n=0}p^{n}_{22}\\ &= p_{11} + p_{12}p_{21}\textstyle\frac{1}{(1-p_{22})} = p_{11} + p_{12} = 1\\ \mu_{11} &= \textstyle\sum^{\infty}_{n=1} n \cdot f^{(n)}_{11} = p_{11} + 2 (p_{12}p_{21}) + 3 (p_{12}p_{22}p_{21}) + 4 (p_{12}p_{22}^2p_{21}) + 5 ...\\ &= p_{11} + p_{12}p_{21} \textstyle\sum^{\infty}{n=0}(n+2)p_{22}^n\\ &= p_{11} + p_{12} + p_{12}p_{21} \textstyle\sum^{\infty}{n=0}(n+1)p_{22}^n\\ &= 1 + p_{12}p_{21}\frac{1}{(1 - p_{22})^2}\\ &= 1 + \frac{p_{12}}{p_{21}} \end{align}$
↑
ゼロ再帰性の証明
状態 1 からスタートし最初の t ステップで 1 に戻らない確率は $\textstyle \prod^t_{j=1} \frac{j}{j+1} = \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} 0$ したがって状態 1 は再帰確実 $\textstyle f^{(t)}_{11} = \frac{1}{t (t + 1)}$ （t − 1 ステップ 1 に戻らず、t ステップ目で 1 に戻る）。しかし、状態 1 に初めて戻るまでの期待値は無限大なので、ゼロ再帰。 $\textstyle \mu_{11} = \sum^{\infty}_{t=1} t \cdot f^{(t)}_{11} = \sum^{\infty}_{t=1} \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} \infty$

[0] 状態 i から j への遷移確率を p_ij とする記法が主流ですが (Karlin & Taylor 1975)、Linda JS Allen (2011 2nd Ed) では j から i への遷移確率を p_ij と定義しています。そうすると定常分布を考える際に以下で書くように行ベクトル π を用いて $\bar\pi = \bar\pi \mathbf P$ とするのではなく、列ベクトルを用いて $\bar\pi = \mathbf P \bar\pi$ と書けるようになります。記法上の問題であり、本質はかわりません。

[1] 
チャップマン-コルモゴロフの等式の証明
$\begin{align} p^{(m)}_{ij} & = \mbox{Prob}\{X_m = j | X_0 = i \} \\ & = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j, X_s = k | X_0 = i \} \\ & = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j | X_s = k, X_0 = i \} \mbox{Prob}\{ X_s = k | X_0 = i \}\\ & = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j | X_s = k \} \mbox{Prob}\{ X_s = k | X_0 = i \} \\ & = \textstyle\sum^{\infty}_{k=1} p^{(m-s)}_{kj} p^{(s)}_{ik} \end{align}$

[2] 
同じ同値類に属する状態の周期が等しいことの証明
周期が 0 のときは自明。状態 i の周期が d(i) ≥ 1 と仮定します。状態 i から s ステップで i に戻る確率が 0 より大きくなる場合 $(p^{(s)}_{ii} > 0)$ 、d(i) は s を割り切ります。 i と j が同値類に属する場合、 i → j を m ステップ、 j → i を n ステップで移動することが可能 $(p^{(n)}_{ji} > 0, p^{(m)}_{ij} > 0)$ ですから $p^{(n + ks + m)}_{jj} \geq; p^{(n)}_{ji} \{ p^{(s)}_{ii} p^{(s)}_{ii} ... p^{(s)}_{ii}\} p^{(m)}_{ij} > 0$ となります。状態 j の周期は (n + ks + m) をどんな正の整数 k に対しても割り切るので、s も割り切ります。ここから d(j) ≤ d(i) が導かれます。同様の議論で d(i) ≤ d(j) も成り立つので d(i) = d(j) となります。

[3] 
例：2 × 2 行列が正再帰的になることの証明
確率行列は行方向の和が必ず 1 になるため、行列の要素は全て正の値をとります。一般に n ≥ 3 について $f^{(n)}_{11} = p_{12}p^{n-2}_{22}p_{21}$ が成立します。状態 1 の再帰確率は 1 になります。状態 2 についても同じです。しかし平均初再帰時間は有限になります。 $\begin{align} \textstyle\sum^{\infty}_{n=1}f^{(n)}_{11} &= p_{11} + p_{12}p_{21}\textstyle\sum^{\infty}_{n=0}p^{n}_{22}\\ &= p_{11} + p_{12}p_{21}\textstyle\frac{1}{(1-p_{22})} = p_{11} + p_{12} = 1\\ \mu_{11} &= \textstyle\sum^{\infty}_{n=1} n \cdot f^{(n)}_{11} = p_{11} + 2 (p_{12}p_{21}) + 3 (p_{12}p_{22}p_{21}) + 4 (p_{12}p_{22}^2p_{21}) + 5 ...\\ &= p_{11} + p_{12}p_{21} \textstyle\sum^{\infty}{n=0}(n+2)p_{22}^n\\ &= p_{11} + p_{12} + p_{12}p_{21} \textstyle\sum^{\infty}{n=0}(n+1)p_{22}^n\\ &= 1 + p_{12}p_{21}\frac{1}{(1 - p_{22})^2}\\ &= 1 + \frac{p_{12}}{p_{21}} \end{align}$

[4] 
ゼロ再帰性の証明
状態 1 からスタートし最初の t ステップで 1 に戻らない確率は $\textstyle \prod^t_{j=1} \frac{j}{j+1} = \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} 0$ したがって状態 1 は再帰確実 $\textstyle f^{(t)}_{11} = \frac{1}{t (t + 1)}$ （t − 1 ステップ 1 に戻らず、t ステップ目で 1 に戻る）。しかし、状態 1 に初めて戻るまでの期待値は無限大なので、ゼロ再帰。 $\textstyle \mu_{11} = \sum^{\infty}_{t=1} t \cdot f^{(t)}_{11} = \sum^{\infty}_{t=1} \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} \infty$

[1]

[2]

[3]

[4]

[5]

Aritalab:Lecture/NetworkBiology/Markov Chains

Latest revision as of 00:35, 21 October 2011

Contents

[edit] マルコフ連鎖

[edit] チャップマン-コルモゴロフの等式

[edit] 既約

[edit] 周期性

[edit] 再帰性

[edit] 再帰時間

[edit] 平均初再帰時間 MFRT

[edit] 通過時間、平均初通過確率 MFPT

[edit] 定常分布

[edit] 定常分布をもつ条件

[edit] 参考・解説

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox

@@ Line 6: / Line 6: @@
 離散確率過程<math>X_0, X_1, X_2 \ldots</math>は
-<math>\mbox{Pr}(X_t = a_t | X_{t-1} = a_{t-1}, X_{t-2} = a_{t-2}, \ldots X_0 = a_0 )
+<math>\mbox{Prob}(X_t = a_t | X_{t-1} = a_{t-1}, X_{t-2} = a_{t-2}, \ldots X_0 = a_0 )
-= \mbox{Pr}(X_t = a_t | X_{t-1} = a_{t-1})
+= \mbox{Prob}(X_t = a_t | X_{t-1} = a_{t-1})
 </math>
 を満たすときにマルコフ連鎖 (Markov chain) と呼ばれます。マルコフとはロシアの統計学者 Andrei A. Markov (1856-1922) のことで、マルコフ連鎖に関する多くの功績を残しました。状態 (state) <math>X_t</math> が状態 <math>X_{t-1}</math> のみに依存して決まる性質をマルコフ性 (Markov property) または無記憶性 (memoryless property) といいます。
-マルコフ連鎖において状態 ''i'' から ''j'' への遷移確率を<math>p_{i,j} = \mbox{Pr}(X_t = j | X_{t-1} = i )</math> と書けば、マルコフ連鎖は遷移行列
+マルコフ連鎖において状態 ''i'' から ''j'' への遷移確率を<math>p_{ij} = \mbox{Pr}(X_t = j | X_{t-1} = i )</math> と書けば、マルコフ連鎖は遷移行列
 <math>
 {\mathbf P} =
 \begin{bmatrix}
-   p_{0,0}  & p_{0,1} & \cdots & p_{0,j} & \cdots \\
+   p_{11}  & p_{12} & \cdots & p_{1j} & \cdots \\
-   p_{1,0}  & p_{1,1} & \cdots & p_{1,j} & \cdots \\
+   p_{21}  & p_{22} & \cdots & p_{2j} & \cdots \\
    \vdots   & \vdots  & \ddots & \vdots  & \ddots \\
-   p_{i,0}  & p_{i,1} & \cdots & p_{i,j} & \cdots \\
+   p_{i1}  & p_{i2} & \cdots & p_{ij} & \cdots \\
    \vdots   & \vdots  & \ddots & \vdots  & \ddots \\
 \end{bmatrix}
 </math>
-で記述できます。<ref>状態 i から j への遷移確率を p<sub>i,j</sub> とする記法が主流ですが (Karlin & Taylor 1975)、Linda JS Allen (2011 2nd Ed) では j から i への遷移確率を p<sub>i,j</sub> と定義しています。そうすると定常分布を考える際に 以下で書くように行ベクトル &pi; を用いて <math>\bar\pi = \bar\pi \mathbf P</math> とするのではなく、列ベクトルを用いて <math>\bar\pi = \mathbf P \bar\pi </math> と書けるようになります。記法上の問題であり、本質はかわりません。</ref>
+で記述できます。<ref>状態 i から j への遷移確率を p<sub>ij</sub> とする記法が主流ですが (Karlin & Taylor 1975)、Linda JS Allen (2011 2nd Ed) では j から i への遷移確率を p<sub>ij</sub> と定義しています。そうすると定常分布を考える際に 以下で書くように行ベクトル &pi; を用いて <math>\bar\pi = \bar\pi \mathbf P</math> とするのではなく、列ベクトルを用いて <math>\bar\pi = \mathbf P \bar\pi </math> と書けるようになります。記法上の問題であり、本質はかわりません。</ref>
 遷移確率を表すので行列の行方向に足し合わせた値は必ず 1 になっており、確率行列 (stochastic matrix) と呼ばれます。もし行方向に足し合わせても 1 になる場合、二重確率行列 (doubly stochastic matrix) と呼ばれます。
 記法を拡張し、''i'' から ''j'' へ正確に ''m'' ステップで移る遷移確率を
-<math>p_{i,j}^m = \mbox{Prob}(X_{t+m} = j | X_{t} = i )</math>
+<math>p_{ij}^{(m)} = \mbox{Prob}(X_{t+m} = j | X_{t} = i )</math>
-と書きましょう。1ステップ目で移動した先を ''k'' と書くと
+と書きましょう。右肩にある (m) という表記は、m ステップ後という意味で m 乗ではありません。1ステップ目で移動した先を ''k'' と書くと
-<math>\textstyle p_{i,j}^m = \sum_{k} p_{i,k} \cdot p^{m-1}_{k,j} </math>
+<math>\textstyle p_{ij}^{(m)} = \sum_{k} p_{ik} \cdot p^{(m-1)}_{kj} </math>
 であるから、遷移行列<math>{\mathbf P}</math>を ''m'' 乗すれば正確に ''m'' ステップで移った先を示す遷移行列を得ます（数学的帰納法）。また記法をそろえるために
-<math>p_{i,j}^1 = p_{i,j}</math>
+<math>p_{ij}^{(1)} = p_{ij}</math>
-<math>p_{i,j}^0 =
+<math>p_{ij}^{(0)} =
 \begin{cases}\textstyle
 & (j = i)\\
 & (j \not= i)
-\end{cases}</math> と定義します。
+\end{cases}</math>
+と定義します。
 ===チャップマン-コルモゴロフの等式===
-''m'' ステップの遷移を、 ''s'' ステップと ''m'' &minus; ''s'' ステップに分解する以下の式は、チャップマン-コルモゴロフの等式と呼ばれます。
+''m'' ステップの遷移を、 ''s'' ステップと ''m'' &minus; ''s'' ステップに分解する以下の式は、チャップマン-コルモゴロフの等式と呼ばれます<ref>
+;チャップマン-コルモゴロフの等式の証明
-<math>p^m_{ij} = \sum^{\infty}_{k=1} p^{s}_{ik} p^{m-s}_{kj} \quad (0 < s < m)</math>
-;証明
 <math>
 \begin{align}
-p^m_{ij} & = \mbox{Prob}\{X_m = j | X_0 = i \} \\
+p^{(m)}_{ij} & = \mbox{Prob}\{X_m = j | X_0 = i \} \\
 & = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j, X_s = k | X_0 = i \} \\
 & = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j | X_s = k, X_0 = i \} \mbox{Prob}\{ X_s = k | X_0 = i \}\\
 & = \textstyle\sum^{\infty}_{k=1} \mbox{Prob}\{ X_m = j | X_s = k \} \mbox{Prob}\{ X_s = k | X_0 = i \} \\
-& = \textstyle\sum^{\infty}_{k=1} p^{m-s}_{kj} p^s_{ik}
+& = \textstyle\sum^{\infty}_{k=1} p^{(m-s)}_{kj} p^{(s)}_{ik}
 \end{align}
-</math>
+</math></ref>。
-これから考えたいのは、ネットワーク上を遷移行列に従って無限時間移動した際の、各状態における存在確率（定常分布）です。
+<math>p^{(m)}_{ij} = \textstyle\sum^{\infty}_{k=1} p^{(s)}_{ik} p^{(m-s)}_{kj} \quad (0 < s < m)</math>
-ただしユニークな定常分布が存在するためには、これから述べる規約、再帰性、非周期性という概念が必要になります。
+以下でも <math>p^{(m)}_{ij} \geq p^{(s)}_{ik} p^{(m-s)}_{kj} </math> という式をよく使います。
 ==既約==
 状態 ''i'' から ''j'' へ何ステップかで到達できる場合、''j'' は ''i'' から到達可能 (accessible) と呼びます。
-互いに到達可能な状態 ''i, j'' どうしを連結 (communicate) しているといい、<math>i \leftrightarrow j</math>と書きます。連結性は同値類を形成します。
+互いに到達可能な状態 ''i, j'' どうしを連結 (communicate) しているといい、<math>i \leftrightarrow j</math>と書きます。連結性により同値類が形成されます。
 * 反射律 (reflexivity): いかなる状態 ''i'' も、<math>i \leftrightarrow i</math>
@@ Line 76: / Line 75: @@
 また、状態集合 C は、C に属すどの状態からも C 以外の状態に抜け出せないとき、閉じている (closed) といいます。例えば、グラフ表現した際に外に出る辺をもたない状態だけからなる集合は閉じています。
-;例： 2次元ランダムウォーク
+;例： 1次元のウォーク
-と N の間を左右に移動し、0, N を吸収状態とするランダムウォークを考えます。0, N は吸収状態とします。すると3つの同値類 {0}, {1, 2, ..., N&minus;1}, {N} が存在し、{0, N} は閉じています。
+と N の間を左右に1ステップずつ移動し、0, N を吸収状態とするランダムウォークを考えます。0 から N までの状態は 3 つの同値類 {0}, {1, 2, ..., N&minus;1}, {N} に分かれ、{0, N} は閉じています。
-==再帰性==
-状態 ''i'' から出発し時刻 ''t'' になって初めて ''j'' に到達する確率を<math>r^t_{i,j}</math>と書く。
-前出の<math>p^t_{i,j}</math>は複数回 ''j'' を訪れることを許すため、<math>r^t_{i,j} \leq p^t_{i,j}</math>となることに注意しよう。
-状態 ''i'' を
-: <math>\textstyle \sum_{t= 1}^{\infty} r^t_{i,i} < 1</math>であれば一時的 (transient)
-: <math>\textstyle \sum_{t= 1}^{\infty} r^t_{i,i} = 1</math>であれば再帰的 (recurrent)
-と呼ぶ。全ての状態が再帰的であれば、マルコフ連鎖自体を再帰的と呼びます。
-状態 ''i'' が再帰的であっても、再帰までのステップ数（再帰時間）の期待値 <math>M_{i,i}</math> が有限とは限りません。
-例えば正の整数値に対応するマルコフ連鎖を仮定し、状態 ''i'' から確率 ''i''/(''i'' +1) で状態 ''i'' +1 に、確率 1/(''i'' +1) で状態 1 に移動する系を考えます。
-状態 1 からスタートして最初の ''t'' ステップで 1 に戻らない確率は
-<math>\textstyle \prod^t_{j=1} \frac{j}{j+1} = \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} 0</math>
-したがって状態 1 は再帰的で、<math>r^t_{1,1}</math> = 1/''t'' (''t'' +1)。
-しかし初めて状態 1 に戻ってくるまでのステップ数の期待値は
-<math>\textstyle M_{1,1} = \sum^{\infty}_{t=1} t \cdot r^t_{1,1} = \sum^{\infty}_{t=1} \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} \infty</math>
-再帰時間の期待値が有限な状態を正再帰的 (positive recurrent)、そうでない場合をゼロ再帰的 (null recurrent) と呼びます。
-ゼロ再帰性を満たすには無限の状態数が必要です。
-状態数が ''N'' 個で有限の場合、少なくとも ''N+1'' ステップ目には既に訪れた状態に辿り着きます。
-よって少なくとも一つの再帰的な状態が存在しなくてはならず、そして再帰的な状態であれば、状態数が有限なので必ず正再帰的です。
-;例： 2次元ランダムウォーク
-と N の間を左右に移動し、0, N を吸収状態とするランダムウォークを考えます。0, N は吸収状態とします。同値類 {1,2, ..., N&minus;1} は一時的な状態です。
 ==周期性==
 状態 ''i'' に戻ってくるまでのステップ数が自然数 ''k'' (>1) の倍数回に限られ、しかも ''k'' がこの性質を持つ最大公約数の場合、状態 ''i'' は周期 ''k'' でといいます。
 ''k'' = 1 のとき、状態は非周期的であるといいます。マルコフ連鎖の中で同じ同値類に属する (communicativeな) 状態 i, j は同じ周期をもちます<ref>
-;同じ同値類に属する状態が同じ周期をもつことの証明
+;同じ同値類に属する状態の周期が等しいことの証明
 周期が 0 のときは自明。状態 i の周期が d(i) &ge; 1 と仮定します。状態 i から s ステップで i に戻る確率が 0 より大きくなる場合 <math>(p^{(s)}_{ii} > 0)</math> 、d(i) は s を割り切ります。 i と j が同値類に属する場合、 i &rarr; j を m ステップ、 j &rarr; i を n ステップで移動することが可能 <math>(p^{(n)}_{ji} > 0, p^{(m)}_{ij} > 0)</math> ですから
@@ Line 117: / Line 88: @@
 となります。状態 j の周期は (n + ks + m) をどんな正の整数 k に対しても割り切るので、s も割り切ります。ここから d(j) &le; d(i) が導かれます。同様の議論で d(i) &le; d(j) も成り立つので d(i) = d(j) となります。
 </ref>。
-;例
+;例：円周上のウォーク
-N 状態がリング状に一方向につながったマルコフ連鎖は、規約で周期 N を持ちます。遷移行列 '''P''' を N 乗すると、恒等行列 '''I''' になります。
+円周上に配置された N 状態が一方向につながったマルコフ連鎖は、規約で周期 N を持ちます。遷移行列 '''P''' を N 乗すると、恒等行列 '''I''' になります。
+;例： 1次元のウォーク
+原点からスタートして左右に1ステップずつ移動するウォークでは、原点に戻るまでのステップ数が必ず偶数です。つまり、状態 0 は周期 2 になります。いずれの状態も周期は 2 です。
-==エルゴード的==
+==再帰性==
-全ての状態が非周期的で正再帰的なマルコフ連鎖を、エルゴード的 (ergodic) であるといいます。有限で規約かつ非周期的なマルコフ連鎖はエルゴード的になります。なぜなら、規約という条件で少なくとも一つの再帰的な状態が存在するため、全ての状態が再帰的になる。さらに有限なため、すべての状態が正再帰的といえるからです。
+状態 ''i'' から出発し時刻 ''t'' になって初めて ''j'' に到達する確率を<math>f^{(t)}_{ij}</math>と書くことにします。
+前出の<math>p^{(t)}_{ij}</math>は複数回 ''j'' を訪れることを許すため、<math>f^{(t)}_{ij} \leq p^{(t)}_{ij}</math>となります。
-==定常分布==
+===再帰時間===
-マルコフ連鎖の遷移行列<math>\mathbf P</math>に対して
+同じ状態に初めて戻る確率 <math>f^{(t)}_{ii}</math> を初再帰確率 (first return probability) と呼び<math>f^{(0)}_{ii} = 0</math> と定義します。状態 ''i'' は
+: <math>\textstyle \sum_{t=1}^{\infty} f^{(t)}_{ii} < 1</math>であれば再帰不確実 (transient)
+: <math>\textstyle \sum_{t=1}^{\infty} f^{(t)}_{ii} = 1</math>であれば再帰確実 (recurrent)
+と呼びます。全ての状態が再帰確実であれば、マルコフ連鎖自体を再帰確実と呼びます。
-<math>\bar\pi = \bar\pi \mathbf P</math>
+===平均初再帰時間 MFRT===
+状態 ''i'' における平均初再帰時間 (mean first return time または mean recurrence time) を
-を満たし、要素の総和が 1 、つまり <math>\textstyle \sum_i \pi_i = 1</math> となるような行ベクトル<math>\bar\pi = (\pi_0, \pi_1, \ldots, \pi_n)</math>を定常分布 (stationary distribution) といいます。
+<math>\mu_{ii} = \textstyle\sum^{\infty}_{t=1} tf^{(t)}_{ii}</math>
-既約でエルゴード的なマルコフ連鎖は唯一つの定常分布 <math>\bar\pi</math> を持ち、 再帰時間の期待値との間に
-<math>\textstyle \pi_i = \lim_{t\rightarrow \infty} p^t_{j,i} = \frac{1}{M_{i,i}} </math>
+と書きます。状態 ''i'' が再帰不確実な場合は <math>\mu_{ii} = \infty</math> です。
-が成り立ちます。
+状態 ''i'' が再帰確実でも <math>\mu_{ii}</math> が有限とは限りません。初再帰時間の期待値が有限なとき有限再帰 (positive recurrent)、そうでない場合をゼロ再帰 (null recurrent) と呼びます。ゼロ再帰性を満たすには無限の状態数が必要です。
-これは再帰時間の期待値が出発する状態 ''j'' に依存しないことを意味し、再帰までのステップ数期待値が <math>M_{i,i}</math> ならば状態 ''i'' に戻ってくる確率が <math>1/M_{i,i}</math> であることに対応します。つまり各状態における存在確率は出発点に依存しません。
-<math>\textstyle \lim_{t \rightarrow \infty} p^t_{j,i} =
+;例：2 &times; 2 行列
-\lim_{t \rightarrow \infty} p^t_{i,i} = \frac{1}{M_{i,i}}</math>
+以下の確率行列を持つ 2 状態のマルコフ連鎖は有限再帰的です。
-さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意します。
+<math>
-つまり全ての状態 ''i, j'' に対し、''i'' から
+{\mathbf P} =
+\begin{bmatrix}
+  p_{11}  & p_{12} \\
+  p_{21}  & p_{22} \\
+\end{bmatrix}\quad
+< p_{ii} < 1 \ (i = 1,2)
+</math>
-<math>\textstyle \sum^n_{j=0}\pi_i p_{i,j} = \sum^0{j=0}\pi_j p_{j, i} = \pi_i</math>
+直感的には 2 状態の間を自由に行き来できるため、必ず戻ってきます<ref>
+;例：2 &times; 2 行列が正再帰的になることの証明
+確率行列は行方向の和が必ず 1 になるため、行列の要素は全て正の値をとります。一般に n &ge; 3 について
-定常分布がただ一つに定まることを証明しましょう。
+<math>f^{(n)}_{11} = p_{12}p^{n-2}_{22}p_{21} </math>
-仮に定常分布が二つあるとして、もう一つの分布を <math>\bar\phi</math> と書きます。
-定常分布であるから
-<math>\phi_i = \sum_k \phi_k p^t_{k,i} \xrightarrow{t \rightarrow \infty}
-\sum_k \phi_k \pi_i = \pi_i \sum_k \phi_k = \pi_i</math>
-すなわち<math>\bar \phi = \bar \pi</math>です。
-===参考===
-<references/>
-==マルコフ連鎖の例==
-===待ち行列===
-窓口に並ぶ客の人数 ''i'' をモデルしよう。
-単位時間において以下の事象が発生する。
-* もし ''i < n'' だったら、確率 ''&alpha;'' で客が一人増える。
-* もし ''i > 0'' なら、確率 ''&beta;'' で先頭から順に客は減る。
-* それ以外の場合、客の数は変化しない。
-時刻 ''t'' における行列の長さを考えると、有限のマルコフ連鎖になっている。遷移確率は以下のようになる。
+が成立します。状態 1 の再帰確率は 1 になります。状態 2 についても同じです。しかし平均初再帰時間は有限になります。
 <math>
 \begin{align}
-p_{i, i+1} &= \alpha \quad \mbox{if} \quad  i < n; \\
+\textstyle\sum^{\infty}_{n=1}f^{(n)}_{11}
-p_{i, i-1} &= \beta \quad \mbox{if} \quad i > 0; \\
+&= p_{11} + p_{12}p_{21}\textstyle\sum^{\infty}_{n=0}p^{n}_{22}\\
-p_{i, i} &=
+&= p_{11} + p_{12}p_{21}\textstyle\frac{1}{(1-p_{22})}
-\begin{cases}
+= p_{11} + p_{12} = 1\\
-- \alpha & \mbox{if } \quad i=0,\\
+\mu_{11} &= \textstyle\sum^{\infty}_{n=1} n \cdot f^{(n)}_{11} = p_{11} + 2 (p_{12}p_{21}) + 3 (p_{12}p_{22}p_{21}) + 4 (p_{12}p_{22}^2p_{21}) + 5 ...\\
-- \alpha - \beta & \mbox{if } \quad 1 \leq i \leq n - 1, \\
+&= p_{11} + p_{12}p_{21} \textstyle\sum^{\infty}{n=0}(n+2)p_{22}^n\\
-- \beta & \mbox{if } \quad i = n
+&= p_{11} + p_{12} + p_{12}p_{21} \textstyle\sum^{\infty}{n=0}(n+1)p_{22}^n\\
-\end{cases}
+&= 1 + p_{12}p_{21}\frac{1}{(1 - p_{22})^2}\\
+&= 1 + \frac{p_{12}}{p_{21}}
 \end{align}
 </math>
+</ref>
+。
-マルコフ連鎖は既約、有限、非周期的なので唯一の定常分布 <math>\bar \pi</math> を持つ。
+;例：ゼロ再帰的なマルコフ連鎖
-満たすべき式は
+正の整数値に対応するマルコフ連鎖を仮定し、状態 i から確率 i/(i + 1) で状態 i + 1 に、確率 1/(i + 1) で状態 1 に移動するとします。
 <math>
-\begin{align}
+{\mathbf P} =
-\pi_0 &= (1 - \alpha) \pi_0 + \beta \pi_1 \\
+\begin{bmatrix}
-\pi_i &= \alpha \pi_{i-1} + (1 -\alpha -\beta) \pi_i + \beta \pi_{i+1} \\
+/2  & 1/2 & 0   & 0   & \cdots \\
-\pi_n &= \alpha \pi_{n-1} + (1-\beta)\pi_n
+/3  &  0  & 2/3 & 0   & \cdots \\
-\end{align}
+/4  &  0  & 0   & 3/4 & \cdots \\
+/5  &  0  & 0   & 0   & \cdots \\
+  \vdots & \vdots & \vdots & \vdots
+\end{bmatrix}
 </math>
-これを解くと <math>\pi_i = \pi_0 \Big( \frac{\alpha}{\beta} \Big)^i </math>。
+高い確率で無限遠に進んでいけるため、状態 1 に初めて戻るまでの期待値は無限大でゼロ再帰的です<ref>
-更に <math>\sum^n_{i=0} \pi_i = \pi_0 \sum^n_{i=0} \Big( \frac{\alpha}{\beta} \Big)^i = 1 </math>より
+;ゼロ再帰性の証明
+状態 1 からスタートし最初の ''t'' ステップで 1 に戻らない確率は
-<math> \pi_i = \frac{ (\alpha/\beta)^i }{\sum^n_{i=0} (\alpha/\beta)^i} </math>
+<math>\textstyle \prod^t_{j=1} \frac{j}{j+1} = \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} 0</math>
-;結論
+したがって状態 1 は再帰確実 <math>\textstyle f^{(t)}_{11} = \frac{1}{t (t + 1)}</math> （''t'' &minus; 1 ステップ 1 に戻らず、''t'' ステップ目で 1 に戻る）。しかし、状態 1 に初めて戻るまでの期待値は無限大なので、ゼロ再帰。
-* ''&alpha;'' > ''&beta;'' のときは行列が長い確率の方が大きい
-* ''&alpha;'' = ''&beta;'' のとき、行列の長さは0からnまで等確率
-同じ結果は、定常状態において ''&alpha; &pi;<sub>i</sub>'' = ''&beta; &pi;''<sub>''i'' +1</sub> という考察からも導くことができる。''&pi;<sub>i</sub>'' = (''&alpha;/&beta;'') ''&pi;''<sub>''i'' +1</sub> から帰納法で ''&pi;<sub>i</sub>'' = ''&pi;<sub>0</sub>''(''&alpha;/&beta;'')<sup>''i''</sup> となる。
+<math>\textstyle \mu_{11} = \sum^{\infty}_{t=1} t \cdot f^{(t)}_{11} = \sum^{\infty}_{t=1} \frac{1}{t+1} \xrightarrow{t \rightarrow \infty} \infty</math>
+</ref>。
-列の長さに上限 ''n'' が無い場合、マルコフ連鎖は有限ではない。もし定常分布があるとしたら（ない可能性もある）
+===通過時間、平均初通過確率 MFPT===
+状態 i から始めて j に最初に訪れる確率 <math>f^{(t)}_{ij}</math> を初通過確率 (first passage time probability) と呼び、 <math>f^{(0)}_{ij} = 0</math> と定義します。平均初通過時間 (mean first passage time; MFPT) も同様に定義します。
+<math> \mu_{ij} = \textstyle\sum^{\infty}_{n=1} nf^{(n)}_{ij}</math>
+==定常分布==
+マルコフ連鎖の遷移行列<math>\mathbf P</math>に対して
+<math>\bar\pi = \bar\pi \mathbf P</math>
+を満たし、要素の総和が 1 、つまり <math>\textstyle \sum_i \pi_i = 1</math> となるような行ベクトル<math>\bar\pi = (\pi_0, \pi_1, \ldots, \pi_n)</math>を定常分布 (stationary distribution) といいます。定常分布は '''P<sup>T</sup>''' の固有値 1 に対応する固有ベクトルともみなせます。状態数が有限の場合は 1 を必ず固有値に持つので定常分布が存在しますが、ただ一つに定まるとは限りません。
+;例：無限個の定常分布を持つマルコフ連鎖
+確率行列が n 次元の単位行列 '''I''' のとき、定常状態は無限にあります。固有値 &lambda; (n個) は全て 1 で、このマルコフ連鎖は既約ではありません (reducible)。
+;例：定常分布を持たないマルコフ連鎖
+正の整数値に対応するマルコフ連鎖を仮定し、状態 i から i, i + 1, i + 2 ... にそれぞれ 1/2, 1/4, 1/8 ... の確率で遷移するとします。各状態が再帰不確実なため、定常状態 &pi; はゼロベクトルになってしまいます。
 <math>
-\begin{align}
+{\mathbf P} =
-\pi_0 &= (1 - \alpha) \pi_0 + \beta \pi_1 \\
+\begin{bmatrix}
-\pi_i &= \alpha \pi_{i-1} + (1 -\alpha -\beta) \pi_i + \beta \pi_{i+1} \ (i \geq 1)
+/2  & 1/4  & 1/8 & 1/16 & 1/32 & \cdots \\
-\end{align}
+& 1/2 & 1/4 & 1/8 & 1/16 & \cdots \\
+& 0 & 1/2 & 1/4 & & 1/8 & \cdots \\
+& 0 & 0 & 1/2 & 1/4 & \cdots \\
+  \vdots & \vdots & \vdots & \vdots
+\end{bmatrix}
 </math>
-の解が存在しなくてはならない。前出の解から類推して
+===定常分布をもつ条件===
-<math>\pi_i = \frac{ (\alpha/\beta)^i }{\sum^\infty_{i=0} (\alpha/\beta)^i} = \Big(\frac{\alpha}{\beta}\Big)^i\Big(1-\frac{\alpha}{\beta}\Big)</math>
+既約で、再帰確実かつ非周期的（エルゴード的）なマルコフ連鎖は唯一つの定常分布 <math>\bar\pi</math> を持ち、 再帰時間の期待値との間に
-が答えになる。このとき　''&alpha;'' < ''&beta;'' でないと定常分布は存在しない。
+<math>\textstyle \pi_i = \lim_{t\rightarrow \infty} p^{(t)}_{ji} = 1/\mu_{ii} </math>
-===出生死亡過程===
+が成り立ちます。この証明および関連する定理は、[[Aritalab:Lecture/NetworkBiology/Markov Chains/StationaryDistribution|定常分布のページ]]を参照してください。
-[[Aritalab:Lecture/NetworkBiology/Markov Chains/Birth-death Process|このページ]]を参照。
+これは再帰時間の期待値が出発する状態 ''j'' に依存しないことを意味し、再帰までのステップ数期待値が <math>\mu_{ii}</math> ならば状態 ''i'' に戻ってくる確率が <math>1/\mu_{ii}</math> であることに対応します。定常状態において、各状態での存在確率は出発点に依存しません。
+<math>\textstyle \lim_{t \rightarrow \infty} p^{(t)}_{ji} =
+\lim_{t \rightarrow \infty} p^{(t)}_{ii} = 1/\mu_{ii}</math>
+さらに定常分布においては、各状態に入る確率と出る確率が等しいことにも注意します。
+つまり全ての状態 i, j に対し、i から出ていく確率の和は、i に入ってくる確率の和に等しく <math>\pi_i</math> になります。
+<math>\textstyle \sum^n_{j=0}\pi_i p_{ij} = \sum^n_{j=0}\pi_j p_{ji} = \pi_i</math>
+エルゴード的であれば定常分布がただ一つに定まることを証明しましょう。
+仮に定常分布が二つあるとして、もう一つの分布を <math>\bar\phi</math> と書きます。
+定常分布であるから
+<math>\phi_i = \textstyle\sum_k \phi_k p^{(t)}_{ki} \xrightarrow{t \rightarrow \infty}
+\sum_k \phi_k \pi_i = \pi_i \sum_k \phi_k = \pi_i</math>
+すなわち<math>\bar \phi = \bar \pi</math>です。
+==参考・解説==
+<references/>