close_btn

  • ※ 사이트 내부 통합검색


  • ※ 카카오페이로 기부하기

  • ※ 사이트 내부 통합검색
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄

https://en.wikipedia.org/wiki/Coupon_collector%27s_problem


카드가 있습니다. 

  1. 카드는 총 n 종류이고, 1회에 1번 카드 덱에서 카드를 받습니다.
    (단, 쿠폰을 뽑는 쿠폰박스의 쿠폰 갯수는 무한대로, 이전에 뽑은 쿠폰의 종류에 영향을 받지 않습니다.)
  2. 이 때, 임의의 한 종류 카드가 뽑힐 확률은 1/n 로 모든 종류의 카드가 동일합니다.  
  3. 중복되는 카드는 다른 사람과 교환할 수 없습니다. 


질문 : 

What is the probability that more than t sample trials are needed to collect all n coupons?

Given n coupons, how many coupons do you expect you need to draw with replacement before having drawn each coupon at least once?


모든 종류의 카드를 모으기 위해서, 

몇번 정도를 카드를 뽑아야 할 것으로 기대할 수 있는가?



\begin{align}
\operatorname{E}(T)& = \operatorname{E}(t_1) + \operatorname{E}(t_2) + \cdots + \operatorname{E}(t_n)
= \frac{1}{p_1} + \frac{1}{p_2} +  \cdots + \frac{1}{p_n} \\
& = \frac{n}{n} + \frac{n}{n-1} +  \cdots + \frac{n}{1}  = n \cdot \left(\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{n}\right) \, = \, n \cdot H_n.
\end{align}


댓글 '4'
?