$X_i$가 1~n 까지의 값을 가질 수 있는 i.i.d 확률변수라고 하자.
$T_{n,k}$를 $n$개의 수들 중에서 $k$개의 서로다른 수를 뽑는데까지 걸리는 시간이라고 한다면,
$$P[|T_{n,n}-n\sum\limits^n_{i=1}\frac{1}{i}|\geq \epsilon n \log n] \rightarrow 0$$
$\tau_{n,k}:= T_{n,k}-T_{n,k-1}$ 은 $1- \frac{k-1}{n}$의 확률의 Geometric Random Variable 이라는 것을 알 수 있다.
따라서 $ E\tau_{n,k} = (1- \frac{k-1}{n})^{-1}$이고 $E T_{n,n} = \sum\limits_{k=1}^n 1-\frac{k-1}{n} = \Omega (nlon)$이 된다.
$Var \tau_{n,k} \leq (1- \frac{k-1}{n})^{-2} = \Theta (n^2)$이다.
따라서 Chebysev 부등식에 의해
$$P[|T_{n,n} - E[T_{n,n}] \geq \epsilon n \log n|] \leq \frac{Var T_{n,n}}{(\epsilon n lon )^2} \rightarrow 0 $$