Aritalab:Lecture/NetworkBiology/Random Walk/Reflection

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology | Random Walk(Difference between revisions)
Jump to: navigation, search
m (Created page with "__FORCETOC__ ==反射壁と吸収壁== ここでは1次元のランダムウォークで、左右対称な場合 ''p'' = ''q'' = 1/2 を考えます。 ある位置 ''k<sup>*</s...")
 
m (→‎反射壁と吸収壁)
 
(4 intermediate revisions by one user not shown)
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>
 
<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>
 
</math>
  
 
となり、カタラン数に一致します。
 
となり、カタラン数に一致します。
  
−
==''n'' ステップ後に初めて吸収壁 ''k'' に到達する経路の数==
+
==n ステップ後に初めて吸収壁 k に到達する経路の数==
  
 
''n'' ステップ後に ''k'' にいる経路の総数は <math>\binom{n}{\frac{n+k}{2}}</math> ですが、この中には ''k'' + 1 を経由するものが含まれます。
 
''n'' ステップ後に ''k'' にいる経路の総数は <math>\binom{n}{\frac{n+k}{2}}</math> ですが、この中には ''k'' + 1 を経由するものが含まれます。
Line 39: Line 37:
  
 
==ギャンブラーの破産問題==
 
==ギャンブラーの破産問題==
−
二人のプレーヤーがコインを ''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'' を求めましょう。
 
  
−
時刻 ''t'' において位置が ''i'' にいる確率を<math>P^t_{i}</math> と書きましょう。すると
+
コインを ''i'' 枚持つギャンブラーが確率 ''p'' で表の出るコインを投げ、表がならコインを 1 枚受け取り、裏なら 1 枚失います。コインを全て失う前に ''n'' 枚に増える確率を考えましょう。
  
−
<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>
+
これは確率 ''p'' &minus; 1, ''p'' で左右にそれぞれ 1 移動し、位置 0 と ''n'' を吸収壁とみなしたランダムウォークです。位置 0 が破産、位置 ''n'' を勝ちとみなして、位置 ''i'' における勝率を考えます。
  
−
となります。また、ゲームは公正なため、何回目の勝負であってもプレーヤー 1 が持つコイン数の期待値は 0 です。つまり時刻 ''t'' について数学的帰納法を用いると、常に
+
勝率が満たす漸化式は
  
−
<math> \sum^{k_2}_{i = -k_1} i P^t_{i} = 0 \ (t = 0, 1, \cdots)</math>
+
<math>
 +
P(i) = p P(i-1) + (1-p) P(i+1)\,
 +
</math>
  
−
です。極限を取ると
+
です。 <math>P(i)\,</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>
+
=== 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> です。
 +
 
 +
* <math>P(i) = i/n\,</math> （勝率は開始時の所持金に正比例）
 +
 
 +
 
 +
=== p &ne; 1/2 のとき===
 +
左右に移動するたびに <math>p/(1-p)\,</math>倍に勝率が変わるウォークなので、漸化式から<math>P(i)\,</math>が等比数列 <math>\,ak^i + b</math> と予測できます。これを漸化式に代入しましょう。
 +
 
 +
<math>
 +
\begin{align}
 +
k^i &= p k^{i-1} + (1-p)k^{i+1}\\
 +
k &= p + (1-p) k^2
 +
\end{align}
 +
</math>
 +
 
 +
これを解いて <math>\textstyle k = 1,\quad k = \frac{p}{1-p}</math>。このうち前者は ''p'' = 1/2 に対応するので除外します。境界条件<math>P(0) = 0\,</math>, <math>P(n) = 1\,</math>から <math>P(i) = a k^i+b\,</math> の係数 ''a'', ''b'' を求めると
 +
<math>\textstyle
 +
P(i) = \frac{k^i - 1}{k^n - 1}
 +
</math>
  
−
となるので <math>\, q = k_1 / (k_1 + k_2) </math> です。つまりゲームに勝つ確率は、開始時の持ち点に比例します。
+
となります。
  
−
;考察
+
* <math>\textstyle P(i) = \frac{k^i - 1}{k^n - 1}\ (k = \frac{p}{1-p})</math> （勝率は ''k'' の値が 1 を少しでも上回れば 1 に大きく近づく）
−
: 公正なコインを用いた賭けでも、資金が少ないギャンブラーが資金の多い胴元に勝つ見込みは少ない。
+
*

Latest revision as of 00:25, 28 October 2011

Contents

[edit] 反射壁と吸収壁

ここでは1次元のランダムウォークで、左右対称な場合 p = q = 1/2 を考えます。 ある位置 k* にきたら次のステップは確率 1 で k* − 1 に移動する場合、 k* を反射壁と呼びます。 反射壁があるときは、壁が無いとみなしてランダムウォークをしたあとに壁を折り返して一致する鏡像点の確率を足したものになります。 ウォーク後の位置を k とするとき、 k* の k に対する鏡像点は 2 k* − k です。

ある位置 k* にきたら次のステップ以降は移動できなくなる場合、 k* を吸収壁と呼びます。 吸収壁があるときは、壁がないとみなしてランダムウォークをしたあとに壁を折り返して一致する鏡像点の確率を引いたものになります。

  • 壁がないとき、n ステップ後に位置 k に至る経路数は \textstyle P(k,n) = \binom{n}{(n+k)/2} = \frac{n!}{(\frac{n - k}{2}) ! (\frac{n + k}{2}) !}
  • 反射壁があるとき、n ステップ後に位置 k に至る経路数は P(k, n; k^*) = P(k, n) + P(2k^* - k, n) \,
  • 吸収壁があるとき、n ステップ後に位置 k に至る経路数は P(k, n; k^*) = P(k, n) - P(2k^* - k, n) \,

[edit] マイナスの値をとらない経路の数

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

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

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

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

n ステップ後に k にいる経路の総数は \binom{n}{\frac{n+k}{2}} ですが、この中には k + 1 を経由するものが含まれます。 1 ステップ前の状態を考えると、位置は k - 1 か、k + 1 です。k + 1 に至る経路の総数は \binom{n-1}{\frac{n+k}{2}} で、k - 1 に至る経路のうち反射壁を通るものの総数も鏡像の原理から \binom{n-1}{\frac{n+k}{2}} と等しくなります。 よって求める経路数は

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

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


[edit] ギャンブラーの破産問題

コインを i 枚持つギャンブラーが確率 p で表の出るコインを投げ、表がならコインを 1 枚受け取り、裏なら 1 枚失います。コインを全て失う前に n 枚に増える確率を考えましょう。

これは確率 p − 1, p で左右にそれぞれ 1 移動し、位置 0 と n を吸収壁とみなしたランダムウォークです。位置 0 が破産、位置 n を勝ちとみなして、位置 i における勝率を考えます。

勝率が満たす漸化式は

P(i) = p P(i-1) + (1-p) P(i+1)\,

です。 P(i)\,を求めましょう。

[edit] p = 1/2 のとき

左右に公正に移動するウォークなので、漸化式を満たすP(i)\,として等差数列 \,ai + b を仮定できます。境界条件P(0) = 0\,, P(n) = 1\,から P(i) = i/n\, です。

  • P(i) = i/n\, （勝率は開始時の所持金に正比例）


[edit] p ≠ 1/2 のとき

左右に移動するたびに p/(1-p)\,倍に勝率が変わるウォークなので、漸化式からP(i)\,が等比数列 \,ak^i + b と予測できます。これを漸化式に代入しましょう。

\begin{align} k^i &= p k^{i-1} + (1-p)k^{i+1}\\ k &= p + (1-p) k^2 \end{align}

これを解いて \textstyle k = 1,\quad k = \frac{p}{1-p}。このうち前者は p = 1/2 に対応するので除外します。境界条件P(0) = 0\,, P(n) = 1\,から P(i) = a k^i+b\, の係数 a, b を求めると \textstyle P(i) = \frac{k^i - 1}{k^n - 1}

となります。

  • \textstyle P(i) = \frac{k^i - 1}{k^n - 1}\ (k = \frac{p}{1-p}) （勝率は k の値が 1 を少しでも上回れば 1 に大きく近づく）
Retrieved from "http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/NetworkBiology/Random_Walk/Reflection&oldid=255263"
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox