Coupon Collector 쿠폰 수집가 문제

Summary

쿠폰 수집가 문제를 simulation 해본다.

쿠폰 수집가 문제는, n 개의 서로 다른 쿠폰이 있을 때, n 개 모두 획득할 때까지 평균적으로 몇 번의 시도를 해야 할까? 라는 것이다.

예를 들어, 10개의 캐릭터가 있고, 과자 봉지 당 하나의 캐릭터가 있다. 나는 평균적으로 몇 개의 과자 봉지를 사야 10개 캐릭터 모두를 얻을 수 있을까?

참고로 보통 n 이 클 경우, n log n 에 근사한다고 알려져 있다.

n <- 10 # 쿠폰 총 종류 
coupon <- 1:n # 쿠폰 생성

num_trials <- 1000 # simulation 시도 횟수 

# 1번의 게임을 실행함
my_trial <- function()
{
  result <- c() # 획득한 쿠폰
  while (TRUE) {
    one_trial <- sample(coupon, 1) # 쿠폰 한장을 뽑고
    result <- c(result, one_trial) # 뽑은 쿠폰을 저장한다.
    
    # 모든 쿠폰을 모았는지 확인하고, 
    if(length(unique(result)) == n) {
      # 모든 쿠폰을 모았을 때까지의 총 시도 횟수를 반환한다.
      return (length(result))
    }
  }
}
my_trial() # 함수 기능 테스트

## [1] 25

trial_result <- sapply(1:num_trials, function(i) my_trial()) # simulation
trial_result_prop <- table(trial_result) / length(trial_result) # 상대도수를 구한다.
round(trial_result_prop, 2)

## trial_result
##   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26 
## 0.00 0.01 0.01 0.02 0.02 0.02 0.03 0.03 0.04 0.05 0.04 0.04 0.05 0.05 0.05 0.04 
##   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42 
## 0.04 0.03 0.04 0.03 0.04 0.04 0.03 0.03 0.02 0.03 0.02 0.02 0.02 0.01 0.01 0.01 
##   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58 
## 0.01 0.01 0.01 0.01 0.00 0.00 0.01 0.01 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 
##   59   60   62   63   64   65   66   67   68   69   71   72   75   76   91   99 
## 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00

# 상대도수에 대한 histogram 을 그린다.
plot(trial_result_prop)

# 기대값을 구한다.
mean(trial_result)

## [1] 28.834

# 이론적인 기대값
theorical_result <- n * sum(1/coupon)
theorical_result

## [1] 29.28968

Coupon Collector 쿠폰 수집가 문제

Kong, Seokkyu

2021-05-15

Summary