確率１０－６
389 名前：１３２人目の素数さん[sage] 投稿日：2005/10/11(火) 08:42:28
1 から n までの数字の書かれた玉が２個ずつ合計 n 個袋に入っている。
無作為に２個ずつ取り出し、数字が同じなら捨て、異なるなら袋に戻す操作を
なくなるまで繰り返すとき、なくなるまでに行う操作の平均回数を求めよ。
391 名前：１３２人目の素数さん[sage] 投稿日：2005/10/11(火) 09:19:22
>>389
× ： 1 から n までの数字の書かれた玉が２個ずつ合計 n 個袋に入っている。
○ ： 1 から n までの数字の書かれた玉が２個ずつ合計 2n 個袋に入っている。
書き間違いでした。
解答
390 名前：１３２人目の素数さん[sage] 投稿日：2005/10/11(火) 09:08:00
袋に玉が2k個ずつ入っている状態を Sk とする。
Sk から S{k-1} に状態遷移するまでに
必要な試行回数をあらわすランダム変数を Xk,
N=∑Xk (k=1からn)とすると、求めるものはE[N]=∑E[Xk].
Sk から S{k-1} に状態遷移する確率は k/2kC2 = 1/(2k-1) で
平均回数はこの逆数になるので
E[Xk] = 2k-1
よって
E[N]=∑(2k-1)= n(n+1) - n = n^2
