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

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 헬벨