Coupon Problem

This problem was presented to me by a former graduate of my University.

The Wikipedia article on this is quite comprehensive, giving both the exact solution, asymptotic solution and the complexity rate.

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

Below is  a very crude simulation with nCoupon = 50.

It was deliberately written in a lapply() way, so that mclapply can be easily applied if need.

 

set.seed(10)
nExp = 5000L
nCoupon = 50L

oneCompetition = function(nCoupon,...){
  loop = 1
  coupons = c()
  capturedLoop = c()
  while(length(coupons) < nCoupon){
    newCoupon = sample(c(1:nCoupon), size = 1, replace = T)
    if(!(newCoupon %in% coupons)) { ## If this newCoupon is new...
    coupons = c(coupons, newCoupon)
    capturedLoop = c(capturedLoop, loop)
    }
    loop = loop + 1 
  }
  result = list(
    finalLoops = loop - 1,
    capturedLoop = capturedLoop
  )
  return(result)
}


# oneCompetition(nCoupon = 20)

start = Sys.time()
simulatedResult = lapply(as.list(1:nExp), oneCompetition, nCoupon = nCoupon)
end = Sys.time()
end - start
## Time difference of 9.273844 secs
mean(sapply(simulatedResult, function(dummy) dummy$finalLoops))
## [1] 225.0608
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s