質問: クーポンコレクターの問題の漸化式 ある食玩にはn種類のおまけがついているとします。 一つを買うとそのどれかが入っています。 二つ目を買うと一つ目とダブっていたり、ダブっていなかったりします。 n種類を全部コンプリートしたいとします。 x個買ったところで、おまけがy種類そろう確率をp(y:x)と書くことにします。 p(1:1)=1, p(y:1)=0(yが1以外のとき) p(1:x)=(1/n)^(x-1) p(y:x)=p(y-1:x-1)*(n-y+1)/n + p(y:x-1)*y/n (for 2<=y<=n, x>=2) となります。最後の漸化式は、x-1個買ったところでy-1種類そろっていたときと、x-1個買ったところでy種類そろっていたときに場合分けしたものです。 n個を買ったときに初めてコンプリートする確率は、n-1個買ったところでn-1種類そろっていて、n個目で最後の1個をそろえればよいから、 p(n-1:n-1)*1/n n+1個を買ったときに初めてコンプリートする確率は、n個買ったところでn-1種類そろっていて、n+1個目で最後の1個をそろえればよいから、 p(n-1:n)*1/n 同様に次々と考えていく。n種類を全部コンプリートするとき平均の買う回数(期待値)e(n)は、「回数×確率」の和だから、 e(n)=σ_(x>=n) x*{p(n-1:x-1)*1/n} この後、式変形して、 e(n)=n(1/1+1/2+1/3+...+1/n) を導きたいのですが、どうすればよいのでしょうか?
回答: 具体的に確率p(y:x)から平均を求めようとすると、ちょっとわからなか ったのですが、平均を求めるだけならば、確率関数が具体的に求められ なくても導く方法はあります。 御参考として、それを書きます。 nをn種類得るまでの必要な回数、xiをi-1種類持っている状態で、次の 新しいi種類目を得るまでに要した回数とします。 すると、n=x1+x2+x3+...+xnとなります。 i-1種類持っている状態で、次に買って新しいi種類目を得る確率は、 pi=(n-i+1)/nであり、従って、新しいi種類目を得るまでに要する 回数がk回である確率はp(xi=k)=pi・(1-pi)^(k-1)(幾何分布)なの で、 e(xi)=σ(k≧1)k・p(xi=k)=σ(k≧1)k・pi・(1-pi)^(k-1) =pi・1/pi^2=1/pi=n/(n-i+1) となります。 従って、 e(n)=e(x1)+e(x2)+e(x3)+...+e(xn) =n/n+n/(n-1)+n/(n-2)+...+n/1 =n(1/n+1/(n-1)+1/(n-2)+...+1/1) が出ます。 このように、確率変数を分解して平均を求めることはよくやります。 特に、確率関数を求めることが難しい時や、求まっても複雑なとき とか。 二項分布もベルヌーイ分布の和に分解できるのも似ていますね。