トップ 一覧 検索 ヘルプ RSS ログイン

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

  • 追加された行はこのように表示されます。
  • 削除された行はこのように表示されます。
問題・補足→[[半々の確率でコインが増減する箱]]

!!!問題(再掲)

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

!!!解答

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

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

a{{sub 0}} = a{{sub 0}}/2 + a{{sub 1}}/2 + 1

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

同様に、

a{{sub n}} = a{{sub n-1}}/2 + a{{sub n+1}}/2 + 1 (1 ≦ n ≦ N-1)

a{{sub N}} = 0

が成り立つ。これらから

* a{{sub 0}} - a{{sub 1}} = 2
* -a{{sub 0}} + 2a{{sub 1}} - a{{sub 2}} = 2
* -a{{sub 1}} + 2a{{sub 2}} - a{{sub 3}} = 2
:
* -a{{sub N-4}} + 2a{{sub N-3}} - a{{sub N-2}} = 2
* -a{{sub N-3}} + 2a{{sub N-2}} - a{{sub N-1}} = 2
* -a{{sub N-2}} + 2a{{sub 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-3>]   [ 2 ]
 [ 0  0  0  0   -1  2 -1  0 ] [a<N-2>]   [ 2 ]
 [ 0  0  0  0    0 -1  2 -1 ] [a<N-1>]   [ 2 ]
 [ 0  0  0  0    0  0 -1  2 ] [a<N>  ]   [ 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{{sub 0}}の値は一番上の値なので、30回が期待値となる。

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