Aritalab:Lecture/NetworkBiology/Markov Chains/StationaryDistribution

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology | Markov Chains(Difference between revisions)
Jump to: navigation, search
m (Created page with "===再帰時間の母関数=== 再帰時間と初再帰時間の間には以下の関係が成立します。 <math> \begin{align} p^{(n)}_{ii} &= f^{(0)}_{ii}p^{(n)}_{ii} + f^...")
 
m (→‎Abel の収束定理)
Line 55: Line 55:
  
 
==Abel の収束定理==
 
==Abel の収束定理==
−
以下の定理は証明せずに利用します。
+
以下の定理 (Abelの定理) は証明せずに利用します。
 
# もし <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>\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>
 
# もし <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 97: Line 97:
  
 
状態 i が再帰的でなければ、i は一時的です。そのため同じ同値類に属す状態集合は、全て再帰的か、すべて一時的のどちらかです。
 
状態 i が再帰的でなければ、i は一時的です。そのため同じ同値類に属す状態集合は、全て再帰的か、すべて一時的のどちらかです。
−
 
  
 
==定常分布の極限定理==
 
==定常分布の極限定理==

Revision as of 16:55, 15 October 2011

再帰時間の母関数

再帰時間と初再帰時間の間には以下の関係が成立します。

\begin{align} p^{(n)}_{ii} &= f^{(0)}_{ii}p^{(n)}_{ii} + f^{(1)}_{ii}p^{(n-1)}_{ii} + f^{(2)}_{ii}p^{(n-2)}_{ii} + ... + f^{(n)}_{ii}p^{(0)}_{ii} \\ &= 0 p^{(n)}_{ii} + f^{(1)}_{ii}p^{(n-1)}_{ii} + f^{(2)}_{ii}p^{(n-2)}_{ii} + ... + f^{(n)}_{ii} 1 \\ &= \textstyle\sum^{n}_{k=1} f^{(k)}_{ii}p^{(n-k)}_{ii} \end{align}

初通過時間も同様にあらわせます。

p^{(n)}_{ij} = \textstyle\sum^{n}_{k=1} f^{(k)}_{ij}p^{(n-k)}_{jj}

関数 fij と pij の母関数をそれぞれ Fij(s) と Pij(s) であらわします[1]。

\begin{align} F_{ij}(s) &= \textstyle\sum^{\infty}_{n=0} f^{(n)}_{ij}s^n \quad |s| < 1 \\ &= 0 s^0 + f^{(1)}_{ij} s + f^{(2)}_{ij} s^2 + f^{(3)}_{ij} s^3 ...\\ P_{ij}(s) &= \textstyle\sum^{\infty}_{n=0} p^{(n)}_{ij}s^n \quad |s| < 1 \\ &= 1 s^0 + p^{(1)}_{ij} s + p^{(2)}_{ij} s^2 + p^{(3)}_{ij} s^3 ... \end{align}

(−1, 1) の間に収束する二つの数列の積はやはり(−1, 1) の間に収束することが知られています (Wade 2000)。

\begin{align} F_{ii}(s) P_{ii}(s) &= \textstyle\sum^{\infty}_{r=1}\Big(\sum^{r}_{k=1}f^{(k)}_{ii}p^{(r-k)}_{ii}\Big) s^r \\ &= \textstyle\sum^{\infty}_{r=1} p^{(r)}_{ii} s^r \\ &= P_{ii}(s) - 1 \end{align}

Pii(s) から 1 を引くのは Fii(s) Pii(s) の第一項が f^{0}_{ii} p^{0}_{ii} = 0 であるのに対し Pii(s) の第一項は 1 になるからです。この関係から以下が導かれます。

\textstyle P_{ii}(s) = \frac{1}{1 - F_{ii}(s)}

同じようにして、通過時間の母関数に対して

F_{ij}P_{jj}(s) = P_{ij}(s) \quad (i \not= j)

が成立します。こちらは Pij(s) から 1 を引きません。これは Pij(s) の第一項が 1 でなく 0 であることに由来します。

Abel の収束定理

以下の定理 (Abelの定理) は証明せずに利用します。

  1. もし \textstyle\sum^{\infty}_{k=0} a_k が収束する場合、 \lim_{s\rightarrow 1^-}\textstyle\sum^{\infty}_{k=0} a_k s^k = \textstyle\sum^{\infty}_{k=0} a^k = a
  2. もし a_k \geq 0, \ \lim_{s\rightarrow 1^-} \textstyle\sum^{\infty}_{k=0} a_k = a \leq \infty の場合、\textstyle\sum^{\infty}_{k=0} a^k = a
定理： 状態 i が再帰的（一時的）であることと \textstyle\sum^{\infty}_{n=0} p^{(n)}_{ii} = \infty は同義

状態 i が再帰的であると仮定します。すなわち

\textstyle\sum^{\infty}_{n=0} f^{(n)}_{ii} = 1

このときAbelの定理から

\lim_{s\rightarrow 1^-} \textstyle\sum^{\infty}_{n=0} f^{(n)}_{ii} s^n = \sum^{\infty}_{n=0} F_{ii}(s) = 1

母関数の関係 P(s) = 1/(1 - F(s)) を用いると

\lim_{s\rightarrow 1^-} \textstyle\sum^{\infty}_{n=0} p^{(n)}_{ii} s^n = \sum^{\infty}_{n=0} P_{ii}(s) = \infty

したがって再びAbelの定理から \textstyle\sum^{\infty}_{n=0} p^{(n)}_{ii} = \infty となります。

逆方向は背理法で示します。 \textstyle\sum^{\infty}_{n=0} p^{(n)}_{ii} = \infty のときに状態 i が一時的 (transient) と仮定します。このときAbelの定理から

\lim_{s\rightarrow 1^-} \textstyle\sum^{\infty}_{n=0} f^{(n)}_{ii} s^n = \sum^{\infty}_{n=0} F_{ii}(s) \leq 1

母関数の関係 P(s) = 1/(1 - F(s)) を用いると

\lim_{s\rightarrow 1^-} \textstyle\sum^{\infty}_{n=0} p^{(n)}_{ii} s^n = \sum^{\infty}_{n=0} P_{ii}(s) < \infty

これは \textstyle\sum^{\infty}_{n=0} p^{(n)}_{ii} = \infty と矛盾するので定理が証明できました。

補題：同じ同値類に属する状態は、再帰性に関する性質が等しい

状態 i, j が同じ同値類に属すと仮定し、m,n ステップでそれぞれ i → j, j → i の遷移が可能とします。すなわち p^{(m)}_{ij} > 0, p^{(n)}_{ji} > 0 です。

状態 i が再帰的 \textstyle\sum^{\infty}_{k=0} p^{(k)}_{ii}= \infty と仮定します。状態 j について以下が成立するので、j もやはり再帰的です。

\textstyle\sum^{\infty}_{k=0} p^{(k)}_{jj} \geq \sum^{\infty}_{k=0} p^{(n)}_{ji} p^{(k)}_{ii} p^{(m)}_{ji} = p^{(n)}_{ji} p^{(m)}_{ji} \sum^{\infty}_{k=0} p^{(k)}_{ii} = \infty

状態 i が再帰的でなければ、i は一時的です。そのため同じ同値類に属す状態集合は、全て再帰的か、すべて一時的のどちらかです。

定常分布の極限定理

定理：既約、再帰的、非周期的なマルコフ連鎖は以下を満たす

\lim_{n \rightarrow \infty} p^{(n)}_{ij} = 1 / \mu_{jj}

ここで \mu_{jj} は状態 j の平均再帰時間です。それに対し、周期 d を持つ場合は、d の倍数にあたる遷移の時だけ

\lim_{n \rightarrow \infty} p^{(nd)}_{ij} = d / \mu_{jj}

それ以外は p^{(n)}_{ii} = 0 になります。証明はKarlin & Tayler (1975) を参照してください。

状態 i が正再帰的な場合は \mu_{ii} が有限の値ですが、ゼロ再帰的な場合は無限大、つまり \lim_{n \rightarrow \infty} p^{(n)}_{ii} = 0 になります。


補足
  1. ↑ fij と pijは一時的 (transient) かもしれないため総和は 1 以下の可能性があります。したがって確率母関数にはなっていません。
Retrieved from "http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/NetworkBiology/Markov_Chains/StationaryDistribution&oldid=255138"
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox