Aritalab:Lecture/Basic/Coupon Collector's Problem

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

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

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

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

$\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}$