コインゲーム（4）

m=2のとき

すなわち、
1枚コインをかけて当たったら2枚戻ってくるとき。
リターン率が同じなら、その分当たる確率が減る。

当たりがx回、ハズレがy回だったとき、
最初のコインがN枚なら、
コインの枚数は

N + x - y

となる。
これが最初に0になるまでに何回かかるかを調べる。
n回かかる確率は、

P(n) = D_x,Np^x(1-p)^x+N

ここで、

D_x,N

は、平面座標(0, 0)から右または上に1ずつ歩いて、
直線 y = x + N に、(x, x + N)ではじめてぶち当たる経路の数。

図がないので分かりにくいが、
これは、カタラン数を求めるときに似ている。

http://www.bun-eido.co.jp/textbook/sjournal/sj22/sj224654.pdf#page=8

う〜ん、ネット探っても求めているものが出てこない。

直線が y = n で、
ぶちあたってもいいが上に抜けてはいけないのがカタラン数。
その母関数を F と書くことにする。
今回求めたいもので、N=0 のときの経路の数の母関数をGとする。

母関数とは、
数列をまとめて扱うためのもの。
例えば、

a_n = n + 1 (n = 0, 1, 2, ...)

という数列の母関数は、

1 + 2x + 3x₂ + ...

これは、

1/(1-x)² = 1 + 2x + 3x² + ...

と書ける。

1(1-x) = 1 + x + x² + ...

を微分すればよい。
だから、先の数列は簡単な関数の形で書ける。
こうすると非常に計算が楽になることが多い。

C_n を (0, 0) から上へ突き抜けない (n, n) への経路の数、
D_n を (0, 0) から y = x に当たらない (n, n) への経路の数とする。

C_n は、(n, n) までに y = x をさわった地点で場合分けできる。
n = 3 なら、
途中で一度もさわらない、
(1, 1) でさわった、
(2, 2) でさわった、
両方でさわった、
の4通りに分けられる。
最初の経路の数は D₃、
次の経路の数は D₁D₂、
その次の経路の数は D₂D₁、
最後の経路の数は D₁D₁D₁。
合わせると、

C₃ = D₃ + D₁D₂ + D₂D₁ + D₁D₁D₁

これら全てを母関数を使って書くと、

F(x) = 1 + G(x) + G(x)² + ...

（最初のほうを展開してみると分かる）
よく考えると、

D_n+1 = C_n

すなわち、

G(x) = xF(x)

これより、

G/x = 1/(1-G)
G^2 - G - x = 0

これを解いて、

（+のほうだと展開して定数項が2となりまずい）
これと同じように D_x,N を求める。

また分かりにくいものを書いてしまった。
この項、つづく。