http://metabolomics.jp/mediawiki/index.php?action=history&feed=atom&title=Aritalab%3ALecture%2FBasic%2FCoupon_Collector%27s_Problem
Aritalab:Lecture/Basic/Coupon Collector's Problem - Revision history
2026-06-23T04:27:50Z
Revision history for this page on the wiki
MediaWiki 1.19.1
http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Basic/Coupon_Collector%27s_Problem&diff=254422&oldid=prev
Adm: New page: お菓子についてくる ''n'' 種類のおまけを全て集めるには、お菓子を何箱買わねばならないか。 既におまけを ''i-1'' 種持っているとき、新...
2010-07-01T01:07:42Z
<p>New page: お菓子についてくる ''n'' 種類のおまけを全て集めるには、お菓子を何箱買わねばならないか。 既におまけを ''i-1'' 種持っているとき、新...</p>
<p><b>New page</b></p><div>お菓子についてくる ''n'' 種類のおまけを全て集めるには、お菓子を何箱買わねばならないか。<br />
<br />
既におまけを ''i-1'' 種持っているとき、新しいおまけを手に入れる確率は <math>p_i = 1 - (i-1)/n</math>。 その期待値は<br />
<br />
<math> \mathbf{E}[X_i] = 1/p_i = \frac{n}{n-i+1} </math><br />
<br />
従って ''n'' 種類集めるためには<br />
<br />
<math><br />
\begin{align}<br />
\mathbf{E}[X] &= \mathbf{E}[\sum^n_{i=1}X] = \sum^n_{i=1}\mathbf{E}[X_i]\\<br />
&= \sum^n_{i=1} \frac{n}{n-i+1} = n \sum^n_{i=1} \frac{1}{i} \\<br />
&= n \log n + \Theta(n)<br />
\end{align}<br />
</math></div>
Adm