주사위의 모든 눈이 최소 한 번씩 나오려면 주사위를 던지는 횟수의 기대 값은?

100종류의 포켓몬 스티커를 모으기 위해 평균 몇 개의 포켓몬 빵을 사먹어야 하는가?

(스티커가 나올 확률은 100종류 모두 동일하다고 가정)

 

Coupon Collector’s Problem (from http://en.wikipedia.org/wiki/Coupon_collector’s_problem)

<br /><br /> \begin{align}<br /><br /> \operatorname{E}(T)& = \operatorname{E}(t_1) + \operatorname{E}(t_2) + \cdots + \operatorname{E}(t_n)<br /><br /> = \frac{1}{p_1} + \frac{1}{p_2} +  \cdots + \frac{1}{p_n} \\<br /><br /> & = \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.<br /><br /> \end{align}<br /><br />

 

주사위 눈은 6개. 총 n번을 던져 모든 주사위 눈을 모은다(collect)고 생각하자.

다음의 notation들은 (i-1)개의 주사위 눈을 이미 가진 상태에서  정의된다.

\$p_i\$ : 던진 주사위에서 새로운 주사위 눈이 나오는 확률.

\$t_i\$  : 새로운 주사위 눈이 나올 때까지 주사위를 던지는 횟수 (Geometric distribution )

\$E(t_i)\$ : (mean of Geometrix dist) \$1/{p_i}\$

 

\$p_1\$ : 첫 시행이므로 새로운 주사위 눈이 나올 확률 = 1

\$p_2\$ : (주사위 눈을 1개 보유 중) 새로운 주사위 눈이 나올 확률  = 5/6

\$p_3\$ : (주사위 눈을 2개 보유 중) 새로운 주사위 눈이 나올 확률 = 4/6

\$p_4\$ : (주사위 눈을 3개 보유 중) 새로운 주사위 눈이 나올 확률 = 3/6

\$p_5\$ : (주사위 눈을 4개 보유 중) 새로운 주사위 눈이 나올 확률 = 2/6

\$p_6\$ : (주사위 눈을 5개 보유 중) 새로운 주사위 눈이 나올 확률 = 1/6

 

주사위의 경우 \$H_n\$ 의 값이 2.45, 즉, 모든 주사위의 눈이 나올 때까지 평균 6 * 2.45 = 14.7 번 던져야 한다.

 

보시다시피 \$H_n\$ 은 조화수열의 합으로 정의되어 있으며, n의 값이 커질수록

$$ E(T) = n \cdot H_n = n \ln n + \gamma n + 1/2 + o(1), \text{as}~~n \to \infty $$ 

와 같이 근사할 수 있다.  (\$ \gamma \approx 0.5772 \$)

대략적인 기대 값 \$E(T)\$는 \$ \Theta(n\log(n))\$ 으로 증가한다고 생각하면 된다.

 

포켓몬 빵의 예에서는 대략 \$E(T) = 100* \ln(100) + 0.577*100\$ = 518.3으로,

빵을 대략 520개는 먹어야 다 모을 수 있다고 기대해 볼만 하다.

'일상 > 그외' 카테고리의 다른 글

[스포있음] 레옹을 다시봤다.  (3) 2015.12.25
네이버 동영상 광고 생략  (2) 2015.11.25
ALL YOUR BAYES ARE BELONG TO US  (0) 2014.07.02
Coupon Collector’s Problem  (2) 2013.11.14
Posted by 헬벨

댓글을 달아 주세요

  1. 해리s 2015.11.08 10:51 신고  댓글주소  수정/삭제  댓글쓰기

    오 ㅋㅋㅋ 전 요즘 Markov chain 책 독학 중인데, 익숙한 내용이네요. :)

  2. 헬벨 2015.11.08 20:23 신고  댓글주소  수정/삭제  댓글쓰기

    오 무슨책인지 알려주실수 있나요? 전 저문제만 우연히 접해서..
    Quora에 올라온 most interesting probability problems 도 링크해드립니당.
    (https://www.quora.com/Probability-statistics-1/What-are-the-most-interesting-or-popular-probability-puzzles-in-which-the-intuition-is-contrary-to-the-solution)
    아직 읽어보진 않았지만요 ㅎㅎ