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

Adm: /* 反射壁と吸収壁 */

2011-10-27T15:25:39Z

‎反射壁と吸収壁

Adm: /* ギャンブラーの破産問題 */

2011-10-27T15:21:32Z

‎ギャンブラーの破産問題

Adm at 15:12, 27 October 2011

2011-10-27T15:12:25Z

Adm: /* ギャンブラーの破産問題 */

2011-07-06T15:21:43Z

‎ギャンブラーの破産問題

Adm: /* ギャンブラーの破産問題 */

2011-07-04T07:19:50Z

‎ギャンブラーの破産問題

Adm: Created page with "FORCETOC ==反射壁と吸収壁== ここでは1次元のランダムウォークで、左右対称な場合 ''p'' = ''q'' = 1/2 を考えます。ある位置 ''k^{*
2011-07-04T06:51:46Z
Created page with "FORCETOC ==反射壁と吸収壁== ここでは1次元のランダムウォークで、左右対称な場合 ''p'' = ''q'' = 1/2 を考えます。ある位置 ''k</s..."
New page
FORCETOC

==反射壁と吸収壁==

ここでは1次元のランダムウォークで、左右対称な場合 ''p'' = ''q'' = 1/2 を考えます。

ある位置 ''k'' にきたら次のステップは確率 1 で ''k'' - 1 に移動する場合、 ''k'' を反射壁と呼びます。

反射壁があるときは、壁が無いとみなしてランダムウォークをしたあとに壁を折り返して一致する鏡像点の確率を足したものになります。

ウォーク後の位置を ''k'' とするとき、 ''k'' の ''k'' に対する鏡像点は 2 ''k'' - ''k'' なので、以下のようになります。

ある位置 ''k'' にきたら次のステップ以降は移動できなくなる場合、 ''k'' を吸収壁と呼びます。

吸収壁があるときは、壁がないとみなしてランダムウォークをしたあとに壁を折り返して一致する鏡像点の確率を引いたものになります。

* 壁がないとき、''n'' ステップ後に位置 ''k'' に至る経路数は <math> P(k,n) = \binom{n}{(n+k)/2} = \frac{n!}{(\frac{n - k}{2}) ! (\frac{n + k}{2}) !} </math>

* 反射壁があるとき、''n'' ステップ後に位置 ''k'' に至る経路数は <math> P(k, n; k^) = P(k, n) + P(2k^ - k, n) \,</math>

* 吸収壁があるとき、''n'' ステップ後に位置 ''k'' に至る経路数は <math> P(k, n; k^) = P(k, n) - P(2k^ - k, n) \,</math>

==マイナスの値をとらない経路の数==

マイナスの値をとらないことは、−1 の位置に吸収壁があることに相当します。たとえば 2 ''n'' ステップ後に原点に戻るウォークで 0 以上の部分だけを通る経路数は

<math>

\binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1} \binom{2n}{n}

</math>

となり、カタラン数に一致します。

==''n'' ステップ後に初めて吸収壁 ''k'' に到達する経路の数==

''n'' ステップ後に ''k'' にいる経路の総数は <math>\binom{n}{\frac{n+k}{2}}</math> ですが、この中には ''k'' + 1 を経由するものが含まれます。

1 ステップ前の状態を考えると、位置は ''k'' - 1 か、''k'' + 1 です。''k'' + 1 に至る経路の総数は <math>\binom{n-1}{\frac{n+k}{2}}</math> で、''k'' - 1 に至る経路のうち反射壁を通るものの総数も鏡像の原理から <math>\binom{n-1}{\frac{n+k}{2}}</math> と等しくなります。

よって求める経路数は

<math>\binom{n}{\frac{n+k}{2}} - 2 \binom{n-1}{\frac{n+k}{2}} = \frac{k}{n} \binom{n}{\frac{n+k}{2}} </math>

となります。つまり、初めて ''k'' に初めて到達する経路数は通常のランダムウォークを ''k''/''n'' 倍すればよいだけです。

==ギャンブラーの破産問題==

二人のプレーヤーがコインを ''k''1 と ''k''2 枚ずつ持っています。確率 1/2 で勝てばコインを 1 枚うけとり、負ければ 1 枚渡します。勝負は原点から出発して左右に 1/2 の確率で移動するランダムウォークに相当し、時刻 ''t'' における位置はプレーヤー 1 が得たコインの枚数（勝ち数）です。状態 − ''k''1 になったらプレーヤー 1 が破産してゲームは終了し、''k''2 になったらプレーヤー 2 が破産してゲームは終了します。このゲームは、状態 ''k''1 と ''k''2 が吸収壁とみなせます。プレーヤー 1 が破産する前に ''k''2 枚のコインを獲得する確率 ''q'' を求めましょう。

時刻 ''t'' において位置が ''i'' にいる確率を<math>P^t_{i}</math> と書きましょう。すると

<math> \lim_{t\rightarrow \infty} P^t_{-k_1} = 1-q,\ \lim_{t\rightarrow \infty} P^t_{k_2} = q,\ \lim_{t\rightarrow \infty} P^t_{i} = 0 \ (-k_1 

となります。また、ゲームは公正なため、何回目の勝負であってもプレーヤー 1 が持つコイン数の期待値は 0 です。つまり時刻 ''t'' について数学的帰納法を用いると、常に

<math> \sum^{k_2}_{i = -k_1} i P^t_{i} = 0 \ (t = 0, 1, \cdots)</math>

です。極限を取ると

<math> \lim_{t\rightarrow \infty} \sum^{k_2}_{i = -k_1} i P^t_{i} = k_2 q - k_1 (1-q) = 0 </math>

となるので <math>\, q = k_1 / (k_1 + k_2) </math> です。つまりゲームに勝つ確率は、開始時の持ち点に比例します。

;考察

: 公正なコインを用いた賭けでも、資金が少ないギャンブラーが資金の多い胴元に勝つ見込みは少ない。}

@@ Line 5: / Line 5: @@
 ある位置 k<sup>*</sup> にきたら次のステップは確率 1 で k<sup>*</sup> &minus; 1 に移動する場合、 k<sup>*</sup> を反射壁と呼びます。
 反射壁があるときは、壁が無いとみなしてランダムウォークをしたあとに壁を折り返して一致する鏡像点の確率を足したものになります。
-ウォーク後の位置を k とするとき、 k<sup>*</sup> の k に対する鏡像点は 2  k<sup>*</sup> &minus; k なので、以下のようになります。
+ウォーク後の位置を k とするとき、 k<sup>*</sup> の k に対する鏡像点は 2  k<sup>*</sup> &minus; k です。
-−
 ある位置 k<sup>*</sup> にきたら次のステップ以降は移動できなくなる場合、 k<sup>*</sup> を吸収壁と呼びます。
@@ Line 14: / Line 13: @@
 * 反射壁があるとき、n ステップ後に位置 k に至る経路数は <math> P(k, n; k^*) = P(k, n) + P(2k^* - k, n) \,</math>
 * 吸収壁があるとき、n ステップ後に位置 k に至る経路数は <math> P(k, n; k^*) = P(k, n) - P(2k^* - k, n) \,</math>
 ==マイナスの値をとらない経路の数==

@@ Line 52: / Line 52: @@
 です。 <math>P(i)\,</math>を求めましょう。
-; p = 1/2 のとき
+=== p = 1/2 のとき===
 左右に公正に移動するウォークなので、漸化式を満たす<math>P(i)\,</math>として等差数列 <math>\,ai + b</math> を仮定できます。境界条件<math>P(0) = 0\,</math>, <math>P(n) = 1\,</math>から <math>P(i) = i/n\,</math> です。
-; p &ne; 1/2 のとき
+* <math>P(i) = i/n\,</math> （勝率は開始時の所持金に正比例）
 左右に移動するたびに <math>p/(1-p)\,</math>倍に勝率が変わるウォークなので、漸化式から<math>P(i)\,</math>が等比数列 <math>\,ak^i + b</math> と予測できます。これを漸化式に代入しましょう。
@@ Line 72: / Line 75: @@
 となります。
-* ''p'' = 1/2 のとき <math>P(i) = i/n\,</math> （勝率は開始時の所持金に正比例）
+* <math>\textstyle P(i) = \frac{k^i - 1}{k^n - 1}\ (k = \frac{p}{1-p})</math> （勝率は ''k'' の値が 1 を少しでも上回れば 1 に大きく近づく）
-* ''p'' &ne; 1/2 のとき <math>\textstyle P(i) = \frac{k^i - 1}{k^n - 1}\ (k = \frac{p}{1-p})</math> （勝率は ''k'' の値が 1 を少しでも上回れば 1 に大きく近づく）

@@ Line 39: / Line 39: @@
 ==ギャンブラーの破産問題==
-===ゲームに勝つ確率===
+コインを ''i'' 枚持つギャンブラーが確率 ''p'' で表の出るコインを投げ、表がならコインを 1 枚受け取り、裏なら 1 枚失います。コインを全て失う前に ''n'' 枚に増える確率を考えましょう。
-プレーヤー 1 が破産する前に ''k''<sub>2</sub> 枚のコインを獲得する確率 ''q'' を求めましょう。
-時刻 ''t'' において位置が ''i'' にいる確率を<math>P^t_{i}</math> と書きましょう。すると
+これは確率 ''p'' &minus; 1, ''p'' で左右にそれぞれ 1 移動し、位置 0 と ''n'' を吸収壁とみなしたランダムウォークです。位置 0 が破産、位置 ''n'' を勝ちとみなして、位置 ''i'' における勝率を考えます。
-<math> \lim_{t\rightarrow \infty} P^t_{-k_1} = 1-q,\ \lim_{t\rightarrow \infty} P^t_{k_2} = q,\ \lim_{t\rightarrow \infty} P^t_{i} = 0 \ (-k_1 < i < k_2) </math>
+勝率が満たす漸化式は
-となります。また、ゲームは公正なため、何回目の勝負であってもプレーヤー 1 が持つコイン数の期待値は 0 です。つまり時刻 ''t'' について数学的帰納法を用いると、常に
+<math>
-<math> \sum^{k_2}_{i = -k_1} i P^t_{i} = 0 \ (t = 0, 1, \cdots)</math>
+です。 <math>P(i)\,</math>を求めましょう。
-です。極限を取ると
+; p = 1/2 のとき
-<math> \lim_{t\rightarrow \infty} \sum^{k_2}_{i = -k_1} i P^t_{i} = k_2 q - k_1 (1-q) = 0 </math>
+; p &ne; 1/2 のとき
-となるので <math>\, q = k_1 / (k_1 + k_2) </math> です。つまりゲームに勝つ確率は、開始時の持ち点に比例します。
+<math>
-つまり、公正なコインを用いた賭けでさえ、資金が少ないギャンブラーが資金の多い胴元に勝つ見込みは少なくなります。
+\begin{align}

@@ Line 39: / Line 39: @@
 ==ギャンブラーの破産問題==
-二人のプレーヤーがコインを ''k''<sub>1</sub> と ''k''<sub>2</sub> 枚ずつ持っています。確率 1/2 で勝てばコインを 1 枚うけとり、負ければ 1 枚渡します。勝負は原点から出発して左右に 1/2 の確率で移動するランダムウォークに相当し、時刻 ''t'' における位置はプレーヤー 1 が得たコインの枚数（勝ち数）です。状態 &minus; ''k''<sub>1</sub> になったらプレーヤー 1 が破産してゲームは終了し、''k''<sub>2</sub> になったらプレーヤー 2 が破産してゲームは終了します。このゲームは、状態 ''k''<sub>1</sub> と ''k''<sub>2</sub> が吸収壁とみなせます。プレーヤー 1 が破産する前に ''k''<sub>2</sub> 枚のコインを獲得する確率 ''q'' を求めましょう。
+二人のプレーヤーがコインを ''k''<sub>1</sub> と ''k''<sub>2</sub> 枚ずつ持っています。確率 1/2 で勝てばコインを 1 枚うけとり、負ければ 1 枚渡します。勝負は原点から出発して左右に 1/2 の確率で移動するランダムウォークに相当し、時刻 ''t'' における位置はプレーヤー 1 が得たコインの枚数（勝ち数）です。状態 &minus; ''k''<sub>1</sub> になったらプレーヤー 1 が破産してゲームは終了し、''k''<sub>2</sub> になったらプレーヤー 2 が破産してゲームは終了します。このゲームは、状態 ''k''<sub>1</sub> と ''k''<sub>2</sub> が吸収壁とみなせます。
 時刻 ''t'' において位置が ''i'' にいる確率を<math>P^t_{i}</math> と書きましょう。すると
@@ Line 54: / Line 57: @@
 となるので <math>\, q = k_1 / (k_1 + k_2) </math> です。つまりゲームに勝つ確率は、開始時の持ち点に比例します。
+つまり、公正なコインを用いた賭けでさえ、資金が少ないギャンブラーが資金の多い胴元に勝つ見込みは少なくなります。
-;考察
-: 公正なコインを用いた賭けでも、資金が少ないギャンブラーが資金の多い胴元に勝つ見込みは少ない。

@@ Line 2: / Line 2: @@
 ==反射壁と吸収壁==
-ここでは1次元のランダムウォークで、左右対称な場合 ''p'' = ''q'' = 1/2 を考えます。
+ここでは1次元のランダムウォークで、左右対称な場合 p = q = 1/2 を考えます。
-ある位置 ''k<sup>*</sup>'' にきたら次のステップは確率 1 で ''k<sup>*</sup>'' - 1 に移動する場合、 ''k<sup>*</sup>'' を反射壁と呼びます。
+ある位置 k<sup>*</sup> にきたら次のステップは確率 1 で k<sup>*</sup> &minus; 1 に移動する場合、 k<sup>*</sup> を反射壁と呼びます。
 反射壁があるときは、壁が無いとみなしてランダムウォークをしたあとに壁を折り返して一致する鏡像点の確率を足したものになります。
-ウォーク後の位置を ''k'' とするとき、 ''k<sup>*</sup>'' の ''k'' に対する鏡像点は 2  ''k<sup>*</sup>'' - ''k'' なので、以下のようになります。
+ウォーク後の位置を k とするとき、 k<sup>*</sup> の k に対する鏡像点は 2  k<sup>*</sup> &minus; k なので、以下のようになります。
-ある位置 ''k<sup>*</sup>'' にきたら次のステップ以降は移動できなくなる場合、 ''k<sup>*</sup>'' を吸収壁と呼びます。
+ある位置 k<sup>*</sup> にきたら次のステップ以降は移動できなくなる場合、 k<sup>*</sup> を吸収壁と呼びます。
 吸収壁があるときは、壁がないとみなしてランダムウォークをしたあとに壁を折り返して一致する鏡像点の確率を引いたものになります。
-* 壁がないとき、''n'' ステップ後に位置 ''k'' に至る経路数は <math> P(k,n) = \binom{n}{(n+k)/2} = \frac{n!}{(\frac{n - k}{2}) ! (\frac{n + k}{2}) !} </math>
+* 壁がないとき、n ステップ後に位置 k に至る経路数は <math>\textstyle P(k,n) = \binom{n}{(n+k)/2} = \frac{n!}{(\frac{n - k}{2}) ! (\frac{n + k}{2}) !} </math>
-* 反射壁があるとき、''n'' ステップ後に位置 ''k'' に至る経路数は <math> P(k, n; k^*) = P(k, n) + P(2k^* - k, n) \,</math>
+* 反射壁があるとき、n ステップ後に位置 k に至る経路数は <math> P(k, n; k^*) = P(k, n) + P(2k^* - k, n) \,</math>
-* 吸収壁があるとき、''n'' ステップ後に位置 ''k'' に至る経路数は <math> P(k, n; k^*) = P(k, n) - P(2k^* - k, n) \,</math>
+* 吸収壁があるとき、n ステップ後に位置 k に至る経路数は <math> P(k, n; k^*) = P(k, n) - P(2k^* - k, n) \,</math>
 ==マイナスの値をとらない経路の数==
-マイナスの値をとらないことは、&minus;1 の位置に吸収壁があることに相当します。たとえば 2 ''n'' ステップ後に原点に戻るウォークで 0 以上の部分だけを通る経路数は
+マイナスの値をとらないことは、&minus;1 の位置に吸収壁があることに相当します。たとえば 2 n ステップ後に原点に戻るウォークで 0 以上の部分だけを通る経路数は
 <math>
-\binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1} \binom{2n}{n}
+\textstyle \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n+1} \binom{2n}{n}
 </math>
 となり、カタラン数に一致します。
-==''n'' ステップ後に初めて吸収壁 ''k'' に到達する経路の数==
+==n ステップ後に初めて吸収壁 k に到達する経路の数==
 ''n'' ステップ後に ''k'' にいる経路の総数は <math>\binom{n}{\frac{n+k}{2}}</math> ですが、この中には ''k'' + 1 を経由するものが含まれます。
@@ Line 72: / Line 72: @@
 となります。
-* ''p'' = 1/2 のとき <math>P(i) = i/n\,</math>。つまり勝率は開始時の所持金に正比例します。
+* ''p'' = 1/2 のとき <math>P(i) = i/n\,</math> （勝率は開始時の所持金に正比例）
-* ''p'' &ne; 1/2 のとき <math>\textstyle P(i) = \frac{k^i - 1}{k^n - 1}\ (k = \frac{p}{1-p})</math>。つまり勝率は ''k'' の値が 1 を少しでも上回れば 1 に大きく近づきます。
+* ''p'' &ne; 1/2 のとき <math>\textstyle P(i) = \frac{k^i - 1}{k^n - 1}\ (k = \frac{p}{1-p})</math> （勝率は ''k'' の値が 1 を少しでも上回れば 1 に大きく近づく）