데이터 과학을 위한 R 알고리즘

쿠폰 수집 문제(Coupon Collection Problem)

1. 쿠폰 수집가 문제 정의 ¹

우표, 기념품, 쿠폰 등 다양한 물건을 수집하자고 가정하자. 이런 경우 서로 다른 쿠폰 \(n\) 개를 수집해야 승리하는 게임을 가정해보자.

• 첫번째 쿠폰을 뽑게 되면 무조건 중복되지 않는 쿠폰이 된다.
• 두번째 다른 쿠폰이 추출될려면 마지막 뽑힌다고 가정하면, 앞서 1개가 뽑혔기 때문에 \(\frac{n-1}{n}\) 확률이 된다. 즉, 기하분포로 이해하면 쉽다.
• 세번째 다른 쿠폰이 추출될려면 마지막 뽑힌다고 가정하면, 앞서 2개를 뽑았기 때문에 \(\frac{n-2}{n}\) 확률이 된다.
• …
• 일반적으로 \(k\) 번째 다른 쿠폰이 추출되려면, \(\frac{n-(k-1)}{n}\) 확률이 된다.

앞선 논리적인 추론을 바탕으로 몇번 추출해야 전체 쿠폰을 모두 갖출 수 있는지 기대값을 구해보면 다음과 같다. 쿠폰을 추출하는 각 사건은 독립이고, 기하분포로 각 쿠폰이 뽑힐 확률을 \(p\)라고 놓으면 기하분포의 기대값은 \(\frac{1}{p}\)로 놓고 수식을 정리한다.

\[\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}\]

여기서 \(H_n\)은 조하평균으로 \(n \rightarrow \inf\) 무한대로 갈때, Euler–Mascheroni 상수 \(\gamma \approx 0.5772156649\) 를 적용하여 근사시킬 수 있다.

\[H_n = \ln{n}+\gamma+\frac{1}{2n}-\sum_{k=1}^\infty \frac{B_{2k}}{2k n^{2k}}=\ln{n}+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}-\cdots\]

2. 신상품 마케팅

코리안 뷰티 사업을 시작한 홍길동 주식회사에서 새로운 신상품을 출시했는데, 상품을 구매하게 되면 상품에 경품에 참여할 수 있는 응모권이 들어있는데 응모권에는 대한민국을 대표하는 연얘인 사진이 포함되어 있다. 모든 상품구매 시에 여자 연애인 사진이 포함되어 있어 각 확률은 \(\frac{1}{10} = 0.1 = 10\%\) 가 되는데, 모든 연예인 사진을 모으게 되면, 즉 중복없이 10명의 연얘인 사진을 모두 모으게 되면 매우 값진 선물을 받게 된다. 여자 연애인 사진 10종 세트를 모두 모으려면 홍길동 주식회사 신상품을 몇개나 구매해야 할까?

\[\operatorname{E}(T) = n \cdot \left(\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{n}\right) = 29.28968 \]

R코드를 작성해서 계산을 하면 55 값이 나온다. 즉, 29.3번 신상품을 구매해야 평균적으로 모든 여자 연애인 사진 10장을 모을 수 있다.

10 * sum(1/(1:10))

[1] 29.28968

조화수열(Harmonic Series)

충분히 큰 \(n\)에 대해서 \(\sum_{i=1}^n \frac{1}{i} \approx \int_{1}^{n} \frac{1}{x}dx = log(n)\) 으로 근사할 수 있다. 따라서, \(\operatorname{E}(T) = \frac{n}{n} + \frac{n}{n-1} + \cdots + \frac{n}{1} \approx n \times log(n)\) 으로 근사식으로 정리할 수 있다.

앞선 예제와 같이 여자연애인 사진이 10장 있는데, 지금까지 신상품을 12개 구매해서 서로 다른 연애인 사진이 몇장이나 나왔을까?

이 문제 대해서 표시함수(Indicator Function)를 사용해서 \(t\)개 상품을 구매했을 때 \(k\)개 연애인 사진이 포함되면 1, 그렇지 않은 경우 0으로 정의한다. 그러면 문제에 대한 해답을 다음과 같이 구할 수 있다.

\[\begin{align} \operatorname{E}[I_k ] &= \operatorname{P}(\text{t개 상품을 구매했을 때 k개 연애인 사진이 포함}) \\ &= 1- \operatorname{P}(\text{t개 상품을 구매했을 때 k개 연애인 사진이 미포함}) \\ &= 1 - (\frac{n-1}{n})^t \end{align}\]

\[\operatorname{E}[X] = E[I_1] + E[I_2] + \cdots + E[I_n] = n \left [ 1 - (\frac{n-1}{n})^t \right ]\]

이를 바탕으로 신상품 12개를 구매했을 때 평균적으로 몇장의 서로 다른 연애인 사진을 구할 수 있는지 계산하면 다음과 같다.

\[ 10 \left [ 1 - (\frac{10-1}{10})^{12} \right ] = 7.175705\]

10*(1-(9/10)^12) R 코드로 작성하여 계산하면 7.1757046 값이 도출된다.

3. 쿠폰 수집가 문제 모의실험 ^{2 3}

• 쿠폰 갯수를 지정: coupons <- 1:n
• 총시행횟수를 초기화: trials <-0
• 모든 쿠폰을 최소 1개 이상 뽑게되면 루프 탈출: while (sum(collect) < n)
• 쿠폰을 1 개 무작위로 추출: i <- sample(coupons, 1)
• 뽑기한 쿠폰을 n개 쿠폰 스롯 중에 1 값을 할당: collect[i] <- 1
• while 루프 조건이 만족되지 않을 때마다 총시행횟수를 증가시킴: trials <- trials + 1

주사위를 던졌을 때 모든 숫자 1,2,3,4,5,6 이 나오려면 몇번을 던져야 할까? 이 문제를 쿠폰 6개를 모두 수집할 때까지 몇번 걸리는지를 1,000번 모의실험한다.

# library(tidyverse)
# library(ggthemes)
# library(extrafont)
# loadfonts()

# 1. 쿠폰수집문제 ----------------------------------------

simulate_coupon <-function(n) {
    
    coupons <- 1:n 
    collect <- numeric(n)
    
    trials <-0
    
    while (sum(collect) < n){
        i <- sample(coupons, 1)
        collect[i] <- 1
        trials <- trials + 1
    }
    return(trials)
}

coupon_sim <- replicate(1000, simulate_coupon(6))

mean(coupon_sim)

[1] 14.649

3.1. 쿠폰 수집가 문제 모의실험 시각화

쿠폰을 1개 부터 100개 까지 확장하여 각 쿠폰별로 모든 쿠폰을 모으려면 몇번 시행을 수행해야 하는지 수행횟수를 계산해 보면 다음과 같다.

# 2. 쿠폰수집문제 시각화 ----------------------------------------
## 2.1. 쿠폰 갯수별 시행횟수 
trials <- 10^3
coupon_v <- numeric(19)
coupon_idx <- numeric(19)

for(i in 1:100) {
    if(i <= 10) {
        coupon_idx[i] <- i
        coupon_v[i] <- mean(replicate(trials, simulate_coupon(i)))
    } else if(i %% 10 == 0) {
        coupon_idx[i] <- i
        coupon_v[i] <- mean(replicate(trials, simulate_coupon(i)))
    } else {
        coupon_idx[i] <- NA
        coupon_v[i] <- NA
    }
}

coupon_idx <- coupon_idx[!is.na(coupon_idx)]
coupon_v <- coupon_v[!is.na(coupon_v)]

coupon_df <- data.frame(쿠폰갯수 = coupon_idx, 시행횟수=coupon_v)

## 2.2. 쿠폰 갯수별 시행횟수 표 및 그래프 정리 

DT::datatable(coupon_df) %>% 
    DT::formatRound(c(2), digits=2)

coupon_df %>% 
  ggplot(aes(x=쿠폰갯수, y=시행횟수)) +
    geom_point() +
    theme_bw(base_family="NanumGothic") +
    labs(x="쿠폰갯수", y="시행횟수", title="쿠폰 수집자 문제", 
         subtitle="모든 연예인 사진을 모으는데 필요한 평균 시행횟수")

---

1. 위키피디아 - Coupon collector problem↩

2. Wiley, Probability: With Applications and R↩

3. How long does it take to collect all coupons?↩