Aritalab:Lecture/NetworkBiology/Random Walk/Recurrence - Revision history

Adm: /* k = 1 の場合 */

2011-10-27T15:06:30Z

‎k = 1 の場合

Adm at 15:05, 27 October 2011

2011-10-27T15:05:46Z

Adm at 14:42, 27 October 2011

2011-10-27T14:42:58Z

Adm at 13:59, 27 October 2011

2011-10-27T13:59:13Z

Show changes

Adm: /* 二項係数 */

2011-10-27T03:48:01Z

‎二項係数

Adm: /* 二項係数と再帰確率 */

2011-10-20T03:02:42Z

‎二項係数と再帰確率

Adm: /* 二項係数と再帰確率 */

2011-10-20T03:02:14Z

‎二項係数と再帰確率

Adm at 03:01, 20 October 2011

2011-10-20T03:01:19Z

Adm at 00:57, 20 October 2011

2011-10-20T00:57:47Z

Show changes

Adm: /* 再帰確率の母関数 */

2011-10-18T06:46:30Z

‎再帰確率の母関数

@@ Line 166: / Line 166: @@
 です。二項係数 <math>p_k^{(n)}, p^{(n)}</math> を用いて <math>f_k^{(n)}</math> を書き下すことができます。
-=== k = 1 の場合===
+=== k＝1 の場合===
 原点を出発し、 n ステップ目ではじめて k = 1 になる確率 <math>f_1^{(n)}</math> を考えます。

@@ Line 1: / Line 1: @@
-===二項係数===
+==二項係数==
 左右に移動する確率がそれぞれ p, q のランダムウォークを考えます。原点から出発して 2n ステップ後に再び原点に戻っている確率 <math>p^{(2n)}_{0}</math> は、左右にちょうど n 回ずつ移動すればよいので
@@ Line 18: / Line 18: @@
 :<math>\textstyle\sum^{\infty}_{n=0} p^{(2n)}_{0} \sim (1/\sqrt{\pi})\sum^{\infty}_{n=0} (4pq)^n/\sqrt{n} \rightarrow N < \infty</math> なので、有限の値に収束し、非再帰的（再帰不確実）です。
-===二項係数と再帰確率===
+==二項係数と再帰確率==
 原点から出発したランダムウォークが原点に戻ってくる確率を再帰確率といいます。
 n に原点に戻る確率を <math>p^{(2n)}</math>と書き、 2n ステップ後に初めて原点に戻ってくる確率を <math>f^{(2n)}</math> と書きましょう。
@@ Line 47: / Line 47: @@
 が求まり、二項係数 <math>p^{(2n)}</math> を用いて <math>f^{(2n)}</math> を書き下すことができます。
-===再帰確率の母関数===
+==再帰確率の母関数==
 ここでは再帰確率を母関数を用いて求めてみます。 f は 2n 回目で初めて原点に戻ることを意味する関数なので n = 1 からスタートします。この議論の一般形は[[Aritalab:Lecture/NetworkBiology/Markov_Chains/StationaryDistribution|マルコフ連鎖定常分布のページ]]にも記されています。
@@ Line 111: / Line 111: @@
 になります。
-===原点に戻る回数の期待値===
+==原点に戻る回数の期待値==
 再帰確率を r としましょう。ランダムウォークが原点に戻らない確率は (1 &minus; r) です。いったん原点に戻ったら、ランダムウォークを再出発させると考えると、ちょうど1回原点に戻る確率は r (1 &minus; r)、ちょうど2回原点に戻る確率は r<sup>2</sup> (1 &minus; r)、ちょうど n 回原点に戻る確率は r<sup>n</sup> (1 &minus; r) になります。戻る回数の期待値は
@@ Line 139: / Line 139: @@
 となり、母関数を用いた <math>F(1)\,</math> の値と一致します。
-===平均再帰時間===
+==平均再帰時間==
 p = q = 1/2 のときだけ再帰確実であり、平均再帰時間を考えられます。
@@ Line 150: / Line 150: @@
 つまり、原点には必ず戻りますが無限時間かかる可能性があります。
-===到達確率===
+==到達確率==
 原点から出発して n ステップ後に位置 k に初めて到達する確率 <math>f_k^{(n)}</math> は、再帰確率と同様に求められます。ここでは一般性を失わずに k > 0 とし、 n と k の偶奇が一致する制約を無視して議論を進めます。まず n ステップ後に 位置 k にいる確率 <math>\ p_k^{(n)}</math> から求めます。
@@ Line 166: / Line 166: @@
 です。二項係数 <math>p_k^{(n)}, p^{(n)}</math> を用いて <math>f_k^{(n)}</math> を書き下すことができます。
-==== k = 1 の場合====
+=== k = 1 の場合===
 原点を出発し、 n ステップ目ではじめて k = 1 になる確率 <math>f_1^{(n)}</math> を考えます。

← Older revision		Revision as of 14:42, 27 October 2011
Line 1:		Line 1:
−	==~~1次元ランダムウォーク~~==	+	===二項係数===
		+	左右に移動する確率がそれぞれ p, q のランダムウォークを考えます。原点から出発して 2n ステップ後に再び原点に戻っている確率 <math>p^{(2n)}_{0}</math> は、左右にちょうど n 回ずつ移動すればよいので
		+
		+	<math>\textstyle p^{(2n)}_{0} = \frac{2n!}{n! n!} p^n q^n \ </math>
		+
		+	ここで p(0) = 1 です。スターリングの近似式 <math> n! \sim n^n e^{-n} \sqrt{2\pi n}</math> を使うと
		+
		+	<math>\textstyle
		+	p^{(2n)}_{0} = \frac{2n!}{n! n!} p^{n} q^{n} \sim \frac{(2n)^{2n}e^{-2n} \sqrt{4 \pi n}}{n^{2n} e^{-2n} 2\pi n } p^{n} q^{n} = \frac{(4pq)^n}{\sqrt{\pi n}}
		+	</math>
		+
		+	となります。
		+
		+	* p = q = 1/2 のとき 4pq = 1
		+	:<math>\textstyle\sum^{\infty}_{n=0} p^{(2n)}_{0} \sim \sum^{\infty}_{n=0} 1/\sqrt{\pi n} > (1/\sqrt{\pi}) \sum 1/n = \infty </math> なので原点には無限回戻ってくることになり、再帰確実です。
		+
		+	* p ≠ 1/2 のとき 4pq < 1
		+	:<math>\textstyle\sum^{\infty}_{n=0} p^{(2n)}_{0} \sim (1/\sqrt{\pi})\sum^{\infty}_{n=0} (4pq)^n/\sqrt{n} \rightarrow N < \infty</math> なので、有限の値に収束し、非再帰的（再帰不確実）です。

	===二項係数と再帰確率===		===二項係数と再帰確率===

@@ Line 6: / Line 6: @@
 左右に移動する確率がそれぞれ p, q のランダムウォークを考えます。原点から出発して 2n ステップ後に再び原点に戻っている確率 ''p'' (2n) は、左右にちょうど ''n'' 回ずつ移動すればよいので
-<math> p(2n) = \frac{2n!}{n! n!} p^n q^n \ </math>
+<math>\textstyle p(2n) = \frac{2n!}{n! n!} p^n q^n \ </math>
 になります。''p'' (0) = 1 です。スターリングの近似式 <math> n! \sim n^n e^{-n} \sqrt{2\pi n}</math> を使うと
-<math>
+<math>\textstyle
 p(2n) = \frac{2n!}{n! n!} p^{n} q^{n} \sim \frac{(2n)^{2n}e^{-2n} \sqrt{4 \pi n}}{n^{2n} e^{-2n} 2\pi n } p^{n} q^{n} = \frac{(4pq)^n}{\sqrt{\pi n}}
 </math>
@@ Line 20: / Line 20: @@
 * p &ne; 1/2 のとき 4pq < 1 となります。
-:<math>\textstyle\sum^{\infty}_{n=0} p(2n) \sim (1/\sqrt{\pi})\sum^{\infty}_{n=0} (4pq)^n/\sqrt{n} \rightarrow N < \infty</math> なので、有限の値に収束し、非再帰的になります。
+:<math>\textstyle\sum^{\infty}_{n=0} p(2n) \sim (1/\sqrt{\pi})\sum^{\infty}_{n=0} (4pq)^n/\sqrt{n} \rightarrow N < \infty</math> なので、有限の値に収束し、非再帰的（再帰不確実）になります。
 ===二項係数と再帰確率===

@@ Line 49: / Line 49: @@
 </math>
-が求まり、二項係数 ''p'' ( 2 ''n'' ) を用いて ''f'' ( 2 ''n'' ) を書き下すことができます。
+が求まり、二項係数 p(2n) を用いて f(2n) を書き下すことができます。
 ===再帰確率の母関数===

@@ Line 24: / Line 24: @@
 ===二項係数と再帰確率===
-これは原点に何回戻ってもよい確率なので、 2''n'' ステップ後に初めて原点に戻ってくる再帰確率を ''f'' ( 2 ''n'' ) と書くと、
+さきの p(2n) という関数は原点に何回戻ってもよい条件で 2n ステップ後に原点にいる確率なので、 2n ステップ後に初めて原点に戻ってくる再帰確率を ''f'' (2n) と書くと、
 <math>

@@ Line 36: / Line 36: @@
 ===再帰確率の母関数===
-ここでは再帰確率を母関数を用いて求めてみます。 ''f'', ''g'' の母関数を考えます。 ''g'' は 2 ''n'' 回目で初めて原点に戻ることを意味する関数なので ''n'' = 1 からスタートするところに注意しましょう。
+ここでは再帰確率を母関数を用いて求めてみます。 ''f'', ''g'' の母関数を考えます。 ''g'' は 2 ''n'' 回目で初めて原点に戻ることを意味する関数なので ''n'' = 1 からスタートするところに注意しましょう。この議論の一般形は[[Aritalab:Lecture/NetworkBiology/Markov_Chains/StationaryDistribution|マルコフ連鎖定常分布のページ]]にも記されています。
 <math>