問題・補足→[[半々の確率でコインが増減する箱]] !!!問題(再掲) 箱にコインが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] [ 2 ] [ 0 0 0 0 -1 2 -1 0 ] [a] [ 2 ] [ 0 0 0 0 0 -1 2 -1 ] [a] [ 2 ] [ 0 0 0 0 0 0 -1 2 ] [a] [ 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)''' となる。