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