View source for Aritalab:Lecture/Basic/Coupon Collector's Problem

お菓子についてくる ''n'' 種類のおまけを全て集めるには、お菓子を何箱買わねばならないか。

既におまけを ''i-1'' 種持っているとき、新しいおまけを手に入れる確率は　<math>p_i = 1 - (i-1)/n</math>。　その期待値は

<math> \mathbf{E}[X_i] = 1/p_i = \frac{n}{n-i+1} </math>

従って ''n'' 種類集めるためには

<math>
\begin{align}
\mathbf{E}[X] &= \mathbf{E}[\sum^n_{i=1}X] = \sum^n_{i=1}\mathbf{E}[X_i]\\
&= \sum^n_{i=1} \frac{n}{n-i+1} = n \sum^n_{i=1} \frac{1}{i} \\
&= n \log n + \Theta(n)
\end{align}
</math>