Statistics/Discrete Probability (1) 썸네일형 리스트형 Coupon Collecting Problem $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).. 이전 1 다음