半々の確率でコインが増減する箱/解答

問題（再掲）

箱にコインが1枚もない状態から、以下のことを繰り返す。
「コインを受け取り、それを投げる。それが表なら箱に入れる。それが裏なら、箱からコインを1枚取り除き（箱にコインが入っていない場合は何もしない）、投げたコインも捨てる。」
これを箱のコインがN枚になるまで繰り返すとき、コインを投げる回数の期待値は何回か。

解答

a_nを「すでに箱にコインがn枚入っているときに、あと何回コインを投げれば箱のコインがN枚になるかの期待値」とおく。このとき、a₀が求める答えである。

このとき、以下の関係が成り立つ。

a₀ = a₀/2 + a₁/2 + 1

（箱にコインが入ってない状態でコインを投げた結果は、箱にコインが入ってないか1枚入っているかのどちらかで、それが半々の確率で起きる。よって残るコインを投げる回数の期待値は、1にこの2通りにおける回数の期待値を足したものである。）

同様に、

a_n = a_n-1/2 + a_n+1/2 + 1 (1 ≦ n ≦ N-1)

a_N = 0

が成り立つ。これらから

a₀ - a₁ = 2
-a₀ + 2a₁ - a₂ = 2
-a₁ + 2a₂ - a₃ = 2

：

-a_N-4 + 2a_N-3 - a_N-2 = 2
-a_N-3 + 2a_N-2 - a_N-1 = 2
-a_N-2 + 2a_N-1 = 2

となる。一次方程式を解く行列で書けば、

[ 1 -1  0  0    0  0  0  0 ] [a<1>  ]   [ 2 ]
[-1  2 -1  0    0  0  0  0 ] [a<2>  ]   [ 2 ]
[ 0 -1  2 -1    0  0  0  0 ] [a<3>  ]   [ 2 ]
[ 0  0 -1  2    0  0  0  0 ] [a<4>  ]   [ 2 ]
[            …            ]     :    =   :
[ 0  0  0  0    2 -1  0  0 ] [a<N-4>]   [ 2 ]
[ 0  0  0  0   -1  2 -1  0 ] [a<N-3>]   [ 2 ]
[ 0  0  0  0    0 -1  2 -1 ] [a<N-2>]   [ 2 ]
[ 0  0  0  0    0  0 -1  2 ] [a<N-1>]   [ 2 ]

のようになる。（一番左上だけ「2」ではなく「1」であることに注意）

これを例えばN=5で解いてみると、

1 -1  0  0  0 |  2
0  1 -1  0  0 |  4 ←2が加えられる
0 -1  2 -1  0 |  2
0  0 -1  2 -1 |  2
0  0  0 -1  2 |  2

1  0 -1  0  0 |  6 ←4が加えられる
0  1 -1  0  0 |  4
0  0  1 -1  0 |  6 ←4が加えられる
0  0 -1  2 -1 |  2
0  0  0 -1  2 |  2

1  0  0 -1  0 | 12 ←6が加えられる
0  1  0 -1  0 | 10 ←6が加えられる
0  0  1 -1  0 |  6
0  0  0  1 -1 |  8 ←6が加えられる
0  0  0 -1  2 |  2

1  0  0  0 -1 | 20 ←8が加えられる
0  1  0  0 -1 | 18 ←8が加えられる
0  0  1  0 -1 | 14 ←8が加えられる
0  0  0  1 -1 |  8
0  0  0  0  1 | 10 ←8が加えられる

1  0  0  0  0 | 30 ←10が加えられる
0  1  0  0  0 | 28 ←10が加えられる
0  0  1  0  0 | 24 ←10が加えられる
0  0  0  1  0 | 18 ←10が加えられる
0  0  0  0  1 | 10

のようになる。このうちa₀の値は一番上の値なので、30回が期待値となる。

一般に、同様の計算により、回数の期待値は a₀ = 2 + 4 + … + 2N = N(N+1) となる。