問題

考察

よくわからない有理数がなんとかは後ろの方で説明。
ある状態でチョコを食べる時、チョコが十分にある場合は $\frac 1 2$ であるが、片方のチョコがなくなってしまう場合には $0$ or $1$ となっているためチョコがなくなっているケースを考慮する必要がある。
$i$ 番目に黒のチョコを食べる確率は以下のようになる。ただし黒のチョコが存在しない確率と白のチョコが存在しない確率をそれぞれ $P_i,Q_i$ とおいた。

$(1-P_i-Q_i) \times \frac 1 2 + P_i \times 0 + Q_i \times 1$

整理すると

$\frac 1 2 (1 - P_i + Q_i)$

となる。この式から $P_i,Q_i$ を求めることで解が得られることになる。上の式はだいたい $\frac 1 2$ だけど食べきってしまう分の補正項が括弧の分だけありますよ、というのが表現されている。

$P_i,Q_i$ の求め方

$P_i$ の求め方と $Q_i$ の求め方は同様なので、以下は $P_i$ の求め方を記述する。

$i \lt B$ の場合

明らかに $P_i=0$ である。(食べきることはないので)

$i=B$ の場合

$[0, B)$ の間にすべて黒を選んだ場合にのみ黒がなくなってしまうので、 $P_i = {2}^i$ である。

$i \gt B$ の場合

本題である。黒が $B$ 個、白が $B-i$ 個の順列を考えると以下のような式が成立しそうな気がするが、これは過剰に低く見積もってしまっている。

$P_i = {}_i C _{B-i} \times 2^i$

これは例えば初めに前半にすべての黒のチョコを食べて後半に白のチョコを食べるというケースを考えることでわかる。このケースの生起確率は ${2}^i$ ではなく ${2}^B$ である。なぜなら黒のチョコを連続で $B$ 個食べる確率は ${2}^B$ であるが、その後白のチョコを食べ続ける確率は $1$ であるためである。このケースから上のcombinationを用いた式は成り立っていなさそうなことがわかる。
ここでdpを考える。 $i$ 番目に $B$ 個のチョコが食べられている確率は、 $i-1$ 番目に $B$ 個のチョコが食べられている確率と $B-1$ 個のチョコが食べられている確率をがわかると得られそうである。結果以下のdpが得られた。 $P$ に添字を一つ追加して現在食べた黒のチョコの数を識別した。

$p_{i+1,B} = P_{i,B} + \frac{1}{2} P_{i,B-1}$

2項目の $\frac 1 2$ は黒を食べる場合と白を食べる場合と2通りあるためである。 $P_{i,B}$ はメモ化して順次求めていく。( $i=B$ は上の方で求めてある) $P_{i,B-1}$ の方はどちらかを食べきってしまうことはないので、普通にcombinationが使えるため以下の式が成り立ち $P_{i+1,B}$ が得られた。