Aritalab:Lecture/NetworkBiology/Markov Chains/StationaryDistribution - Revision history

Adm: /* Abel の収束定理 */

2011-10-26T22:41:18Z

‎Abel の収束定理

Adm: /* Abel の収束定理 */

2011-10-26T22:40:51Z

‎Abel の収束定理

Adm: /* Abel の収束定理 */

2011-10-26T22:40:23Z

‎Abel の収束定理

Adm: /* マルコフ連鎖の分類 */

2011-10-20T15:34:20Z

‎マルコフ連鎖の分類

Adm: /* 定常分布の極限定理 */

2011-10-20T15:18:10Z

‎定常分布の極限定理

Adm: /* Abel の収束定理 */

2011-10-20T15:16:35Z

‎Abel の収束定理

Adm: /* 定常分布の極限定理 */

2011-10-17T07:40:24Z

‎定常分布の極限定理

Adm: /* 定常分布の極限定理 */

2011-10-15T08:55:17Z

‎定常分布の極限定理

Adm: /* 定常分布の極限定理 */

2011-10-15T08:40:34Z

‎定常分布の極限定理

Adm: /* Abel の収束定理 */

2011-10-15T07:55:48Z

‎Abel の収束定理

@@ Line 55: / Line 55: @@
 ==Abel の収束定理==
-以下の定理 (Abelの定理) は証明せずに利用します。この定理と母関数の議論から、再帰性を <math>\textstyle\sum_n f^{(n)}</math> ではなく <math>\textstyle\sum_n p^{(n)}</math> で議論できるようになり、再帰性の計算を楽にします。
+以下の定理 (Abelの定理) は証明せずに利用します。この定理と母関数の関係から、再帰性を <math>\textstyle\sum_n f^{(n)}</math> ではなく <math>\textstyle\sum_n p^{(n)}</math> で議論できるようになり、再帰性の計算を楽にします。
 # もし <math>\textstyle\sum^{\infty}_{k=0} a_k</math> が収束する場合、<math> \lim_{s\rightarrow 1^-}\textstyle\sum^{\infty}_{k=0} a_k s^k = \textstyle\sum^{\infty}_{k=0} a^k = a</math>
 # もし <math> a_k \geq 0, \ \lim_{s\rightarrow 1^-} \textstyle\sum^{\infty}_{k=0} a_k = a \leq \infty</math> の場合、<math>\textstyle\sum^{\infty}_{k=0} a^k = a</math>

@@ Line 55: / Line 55: @@
 ==Abel の収束定理==
-以下の定理 (Abelの定理) は証明せずに利用します。この定理と母関数の議論から、再帰性を <math>\textstyle\sum^n f^{(n)}</math> ではなく <math>\textstyle\sum^n p^{(n)}</math> で議論できるようになり、再帰性の計算を楽にします。
+以下の定理 (Abelの定理) は証明せずに利用します。この定理と母関数の議論から、再帰性を <math>\textstyle\sum_n f^{(n)}</math> ではなく <math>\textstyle\sum_n p^{(n)}</math> で議論できるようになり、再帰性の計算を楽にします。
 # もし <math>\textstyle\sum^{\infty}_{k=0} a_k</math> が収束する場合、<math> \lim_{s\rightarrow 1^-}\textstyle\sum^{\infty}_{k=0} a_k s^k = \textstyle\sum^{\infty}_{k=0} a^k = a</math>
 # もし <math> a_k \geq 0, \ \lim_{s\rightarrow 1^-} \textstyle\sum^{\infty}_{k=0} a_k = a \leq \infty</math> の場合、<math>\textstyle\sum^{\infty}_{k=0} a^k = a</math>

@@ Line 55: / Line 55: @@
 ==Abel の収束定理==
-以下の定理 (Abelの定理) は証明せずに利用します。
+以下の定理 (Abelの定理) は証明せずに利用します。この定理と母関数の議論から、再帰性を <math>\textstyle\sum^n f^{(n)}</math> ではなく <math>\textstyle\sum^n p^{(n)}</math> で議論できるようになり、再帰性の計算を楽にします。
 # もし <math>\textstyle\sum^{\infty}_{k=0} a_k</math> が収束する場合、<math> \lim_{s\rightarrow 1^-}\textstyle\sum^{\infty}_{k=0} a_k s^k = \textstyle\sum^{\infty}_{k=0} a^k = a</math>
 # もし <math> a_k \geq 0, \ \lim_{s\rightarrow 1^-} \textstyle\sum^{\infty}_{k=0} a_k = a \leq \infty</math> の場合、<math>\textstyle\sum^{\infty}_{k=0} a^k = a</math>

@@ Line 139: / Line 139: @@
 マルコフ連鎖は以下のように分類できます。
 # 既約 or 非既約
-# 過渡的 or ゼロ再帰的 or 正再帰的
+# 再帰不確実 or ゼロ再帰 or 有限再帰
 # 周期的 or 非周期的
-===有限性とゼロ再帰性===
+===連鎖の有限性とゼロ再帰性===
-ゼロ再帰性は、有限マルコフ連鎖で生じません。
-;定理：有限のマルコフ連鎖における状態は過渡的か正再帰的（ゼロ再帰的な状態は無い）。また、全ての状態が過渡的になることもない
+ゼロ再帰性は、有限マルコフ連鎖では生じません。
-全ての状態が過渡的である場合、確率行列によって N ステップ後に移動する状態を考えると
+;定理：有限のマルコフ連鎖における状態は再帰不確実か有限再帰（ゼロ再帰的な状態は無い）。また、全ての状態が再帰不確実になることもない
 <math>\textstyle \lim_{n \rightarrow \infty} \mathbf{P}^{n} = \mathbf{0}</math>
-になってしまうので、'''P''' が確率行列であることと矛盾します。次にゼロ再帰性について考えます。マルコフ連鎖は有限なので、ゼロ再帰的な状態が属す、ゼロ再帰的な同値類 C が存在します。この同値類に対応する確率行列（'''P'''の部分行列）'''P' '''を考えると、ゼロ再帰性からこの部分行列について
+これは '''P''' が確率行列であることと矛盾します。
 <math>\textstyle \lim_{n \rightarrow \infty} \mathbf{P'}^{n} = \mathbf{0}</math>
-でなくてはなりません。しかし C に対応する部分行列も再帰性から確率行列を満たさなくてはならないので、矛盾します。
+しかし C に対応する部分行列は再帰的ですから確率行列でもあるので、矛盾します。
-つまり、ゼロ再帰的な状態と過渡的な状態はいずれも <math>\textstyle \lim_{n \rightarrow \infty} p^{(n)}_{ii} = 0</math> を満たすので有限の数で再帰性を満たせないというわけです。
+つまり、ゼロ再帰的な状態と再帰不確実な状態はいずれも <math>\textstyle \lim_{n \rightarrow \infty} p^{(n)}_{ii} = 0</math> を満たすので有限の状態数で再帰性を満たせないというわけです。
-;定理：有限のマルコフ連鎖に含まれる同値類は、閉じているなら正再帰的
+;定理：有限のマルコフ連鎖に含まれる同値類は、閉じているなら有限再帰
-正再帰的な状態集合は必ず閉じています。なぜなら閉じていない場合は、いずれかの状態 i において j &rarr; j という集合外への遷移が存在し、状態 i の再帰確率はこの遷移確率 p<sub>ij</sub> 分 1 より少なくなるからです。これは再帰的であることの定義に反します。
+有限再帰な状態集合は必ず閉じています。なぜなら閉じていない場合は、いずれかの状態 i において j &rarr; j という集合外への遷移が存在し、状態 i の再帰確率はこの遷移確率 p<sub>ij</sub> ぶん 1 より少なくなるからです。これは再帰的であることの定義に反します。
-逆に閉じた同値類が正再帰的でない、つまり過渡的であると仮定します。すると同値類に含まれる状態全てが過渡的になってしまうので、一つ前の定理と同じ理由で矛盾となります。
+閉じた同値類が有限再帰でない、つまり再帰不確実であると仮定します（ゼロ再帰ではありえない）。すると同値類に含まれる状態全てが再帰不確実のはずです。しかし全てが再帰不確実の場合、同値類の中から集合外への遷移が無くてはなりません。これは閉じていることと矛盾します。
 ===正規行列===
-マルコフ連鎖の世界では、全ての要素が p<sub>ij</sub> > 0 となる確率行列を 正規行列 (regular matrix) と呼ぶことがあります。確率行列が正規な場合、マルコフ連鎖は規約で非周期的（全ての状態間を行き来できる）です。このため正規な確率行列を持つマルコフ連鎖は、正再帰的でもあります。
+マルコフ連鎖の世界では、全ての要素が p<sub>ij</sub> > 0 となる確率行列を 正規行列 (regular matrix) と呼ぶことがあります。確率行列が正規な場合、マルコフ連鎖は規約で非周期的（全ての状態間を行き来できる）です。このため正規な確率行列を持つマルコフ連鎖は、有限再帰的でもあります。
 ペロン・フロベニウスの定理によると、非負の行列 P が既約であれば
@@ Line 172: / Line 175: @@
 # 最大固有値に対応する固有ベクトルの成分は、全て正か又は全て負 （当然だが、定常分布は全て正）
-が成立します。つまり最大固有値 1 がただ一つの定常分布に対応するためには、確率行列 P は正規（既約かつ非周期的）でなくてよく、規約なだけで十分です。非周期性は、唯一の定常分布に収束するために必要な条件です。
+が成立します。つまり最大固有値 1 がただ一つの定常分布に対応するためには、確率行列 P は正規（既約かつ非周期的）でなくてよく、規約なだけで十分です。非周期性は、唯一の定常分布に収束するために必要な条件となります。
 ;<big>補足</big>
 <references/>

@@ Line 101: / Line 101: @@
 以下の定理の証明はいずれもKarlin & Tayler (1975) を参照してください。
-;定理：既約、再帰的、非周期的なマルコフ連鎖は以下を満たす
+;定理：既約、再帰確実、非周期的なマルコフ連鎖は以下を満たす
 <math>\lim_{n \rightarrow \infty} p^{(n)}_{ij} = 1 / \mu_{jj}</math>
@@ Line 107: / Line 107: @@
 ここで <math>\mu_{jj}</math> は状態 j の平均再帰時間です。i の値に関係ない (j に依存する)値に収束する点に注意します。
-;定理：既約、再帰的、周期 d のマルコフ連鎖は以下を満たす
+;定理：既約、再帰確実、周期 d のマルコフ連鎖は以下を満たす
 周期 d を持つ場合、d の倍数にあたる遷移の時だけ
@@ Line 115: / Line 115: @@
 それ以外は <math>p^{(m)}_{ii} = 0 \ (m \not= nd)</math> になります。
-状態 i が正再帰的な場合は <math>\mu_{ii}</math> が有限の値ですが、ゼロ再帰的な場合は無限大、つまり <math>\lim_{n \rightarrow \infty} p^{(n)}_{ii} = 0</math> になります。
+状態 i が有限再帰な場合は <math>\mu_{ii}</math> が有限の値ですが、ゼロ再帰な場合は無限大、つまり <math>\lim_{n \rightarrow \infty} p^{(n)}_{ii} = 0</math> になります。
-;定理：規約、正再帰的、非周期的なマルコフ連鎖は、定常分布 <math> \bar\pi = (\pi_1, \pi_2, ...) </math> をただ一つ持つ
+;定理：規約、有限再帰、非周期的なマルコフ連鎖は、定常分布 <math> \bar\pi = (\pi_1, \pi_2, ...) </math> をただ一つ持つ
 <math>\pi_j = \lim_{n \rightarrow \infty} p^{(n)}_{ij} \ (i, j = 1, 2, ...)</math>
-マルコフ連鎖は有限でなくても良い点に注意します。定常分布をただ一つ持つような条件を、エルゴード的と呼びます。
+マルコフ連鎖自体は有限でなくても良い点に注意しましょう。定常分布をただ一つ持つような条件を、エルゴード的と呼びます。
-状態 i がエルゴード的な時、i は正再帰的、非周期的です。マルコフ連鎖がエルゴード的になるには、全ての状態がエルゴード的かつ規約でなくてはなりません。このとき、確率行列は以下を満たします。
+状態 i がエルゴード的な時、i は有限再帰、非周期的です。マルコフ連鎖がエルゴード的になるには、全ての状態がエルゴード的かつ規約でなくてはなりません。このとき、確率行列は以下を満たします。
 <math>

@@ Line 59: / Line 59: @@
 # もし <math> a_k \geq 0, \ \lim_{s\rightarrow 1^-} \textstyle\sum^{\infty}_{k=0} a_k = a \leq \infty</math> の場合、<math>\textstyle\sum^{\infty}_{k=0} a^k = a</math>
-;定理： 状態 i が再帰的（一時的）であることと <math> \textstyle\sum^{\infty}_{n=0} p^{(n)}_{ii} = \infty </math> は同義
+;定理： 状態 i が再帰確実（不確実）であることと <math> \textstyle\sum^{\infty}_{n=0} p^{(n)}_{ii} = \infty </math> は同義
-状態 i が再帰的であると仮定します。すなわち
+状態 i が再帰確実と仮定します。すなわち
 <math> \textstyle\sum^{\infty}_{n=0} f^{(n)}_{ii} = 1 </math>
@@ Line 75: / Line 75: @@
 したがって再びAbelの定理から <math> \textstyle\sum^{\infty}_{n=0} p^{(n)}_{ii} = \infty </math> となります。
-逆方向は背理法で示します。 <math> \textstyle\sum^{\infty}_{n=0} p^{(n)}_{ii} = \infty</math> のときに状態 i が一時的 (transient) と仮定します。このときAbelの定理から
+逆方向は背理法で示します。 <math> \textstyle\sum^{\infty}_{n=0} p^{(n)}_{ii} = \infty</math> のときに状態 i が再帰不確実 (transient) と仮定します。このときAbelの定理から
 <math>\lim_{s\rightarrow 1^-} \textstyle\sum^{\infty}_{n=0} f^{(n)}_{ii} s^n = \sum^{\infty}_{n=0} F_{ii}(s) \leq 1 </math>
@@ Line 89: / Line 89: @@
 状態 i, j が同じ同値類に属すと仮定し、m,n ステップでそれぞれ i &rarr; j, j &rarr; i の遷移が可能とします。すなわち <math> p^{(m)}_{ij} > 0, p^{(n)}_{ji} > 0</math> です。
-状態 i が再帰的 <math>\textstyle\sum^{\infty}_{k=0} p^{(k)}_{ii}= \infty</math> と仮定します。状態 j について以下が成立するので、j もやはり再帰的です。
+状態 i が再帰確実 <math>\textstyle\sum^{\infty}_{k=0} p^{(k)}_{ii}= \infty</math> と仮定します。状態 j について以下が成立するので、j もやはり再帰確実です。
 <math>\textstyle\sum^{\infty}_{k=0} p^{(k)}_{jj} \geq
@@ Line 96: / Line 96: @@
 = \infty</math>
-状態 i が再帰的でなければ、i は一時的です。そのため同じ同値類に属す状態集合は、全て再帰的か、すべて一時的のどちらかです。
+状態 i が再帰確実でなければ、i は不確実です。そのため同じ同値類に属す状態集合は、全て再帰確実か、すべて不確実のどちらかです。
 ==定常分布の極限定理==

@@ Line 125: / Line 125: @@
 <math>
-\lim_{n \rightarrow \infty} P^{n} =
+\lim_{n \rightarrow \infty} \mathbf{P}^{n} =
 \begin{bmatrix}
    \pi_1 & \pi_2  & \pi_3 & \cdots  \\
@@ Line 136: / Line 136: @@
 つまり初期値に依存しない値になります。上の定理とあわせると、<math>\ \pi_i = 1/\mu_{ii} > 0 </math> が導かれます。
-;補足
+==マルコフ連鎖の分類==
 <references/>