08/10/02 19:28:42
一応出来たっぽい。
B ≠ 0 のとき a(n+1) - a(n) は指数函数的に増加。
B = 0 のとき a(n + 1) - a(n) → 2 (n → ∞)。
従ってこれを大雑把に評価すれば良い。
（初期位置の座標 3-n から）
確率 1/2 で -1 進み、確率 1/2 で +2 進むという試行を繰り返す。
k 回の試行のうち、 t 回目の試行までに
-1 が x(t) 回、 +2 が y(t) 回出たとして
試行中常に 2y - x ≦ n-1 となる確率を p(n,k) と置く。
p(n,k)は k に関して単調減少、 n に関して単調増加。
a(n)
= ∑_{k=1}^{k=∞} k(p(n,k+1) - p(n,k))
= ∑_{k=1}^{k=∞} p(n,k)。
従って
a(n+1) - a(n)
∑_{k=1}^{k=∞} p(n+1,k) - p(n,k)。
2y(t) - 2x(t) ≦ 2k だから 2k ≦ n-1 つまり k ≦ (n-1)/2 のとき
n が充分でかいから p(n,k) = 1。このとき p(n+1,k) も常に 1 となる。
従って
a(n+1) - a(n)
= ∑_{k=1}^{k=∞} p(n+1,k) - p(n,k)
= ∑_{k=1}^{k=[(n+1)/2]} p(n+1) - p(n,k)
< ∑_{k=1}^{k=[(n+1)/2]} p(n+1) < [(n+1)/2] < (n+1)/2
ここで 0 ≦ p(n+1) ≦ 1 、[ ]は整数部分。
つまり a(n+1) - a(n) は高々 n の一次の速さでしか増大しないので B = 0。
従って実際は a(n) ～ 2n、a(n+1) - a(n) → 2。 □
Catalan数使ってどうにか出来ないか試したりして
結局帰宅後すぐ取り掛かって今になるまで掛かった。長かったー、、