クーポンコレクターの問題の漸化式

質問

ある食玩には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)　

を導きたいのですが、どうすればよいのでしょうか？

回答No.1

zk43 · ベストアンサー

具体的に確率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)
が出ます。
このように、確率変数を分解して平均を求めることはよくやります。
特に、確率関数を求めることが難しい時や、求まっても複雑なとき
とか。
二項分布もベルヌーイ分布の和に分解できるのも似ていますね。