トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

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

問題・補足→半々の確率でコインが増減する箱

問題(再掲)

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

解答

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

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

a0 = a0/2 + a1/2 + 1

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

同様に、

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

aN = 0

が成り立つ。これらから

  • a0 - a1 = 2
  • -a0 + 2a1 - a2 = 2
  • -a1 + 2a2 - a3 = 2

  • -aN-4 + 2aN-3 - aN-2 = 2
  • -aN-3 + 2aN-2 - aN-1 = 2
  • -aN-2 + 2aN-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

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

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