Coupon Collector Problem Code

21 views (last 30 days)
Matthew Corrie
Matthew Corrie on 30 Nov 2019
Answered: Ken Bannister on 29 Apr 2021
I've been trying to create a program to calculate the mean time taken to collect all coupons in the coupon collector problem. It is known that the expected time to do this is roughly n*log(n). Through just general trials with large numbers of repeats, my answer for E(T) never seems to be n*log(n) and I can't figure out why. Can anyone help please? My code is below:
prompt_m = 'How many times would you like to run this?';
prompt_coupon_num = 'How many coupons are in the set?';
m = input(prompt_m); %input amount of repeats
coupon_num = input(prompt_coupon_num); %input number of coupons
x = zeros(1,coupon_num); %create a vector of all nums 1 -> couponnum
for i = 1:coupon_num
x(i) = i;
s = sum(x);
T = zeros(1,m); %create a vector of zeros which will track the steps till completion
for l = 1:m
j = 0; %sets j = 0 at the start of each new repeat
y = zeros(1,coupon_num); %creates a vector of 0's for each new repeat
while j<s
r = randi([1,coupon_num]); %creates a random number between 1 and the max
for k = 1:coupon_num
if r == y(k) %checks if the random number is already in the vector y
y(r) = r; %if not adds the number to the vector in the position of the number
j = sum(y); %tracks to see if all the coupons have been selected
T(l) = T(l) + 1; %counts the number of times a selection has taken place
T_mean = sum(T)/m; %calculates the mean

Answers (2)

Anmol Dhiman
Anmol Dhiman on 6 Dec 2019
There is nothing wrong with the logic. I have tried the code and found it to be correct. I have tried examples from below link.
(n = 55, Ans = 253)
(n= 50 , Ans = 225)
I ran the simulations for 10,000 times. And got values close to approximate values every time. Try with more number of simulations(prompt_m).

Ken Bannister
Ken Bannister on 29 Apr 2021
I have a related question: Suppose we have evenly distributed figurines of the the severn dwarfs across a bunch
of cereal boxes. If the dwarfs are equally distributed, we would have to obtain 1 + 7*(1/6+1/5+1/4+1/3+1/2+1/1) boxes
(18.15 total) to expect to collect a complete set of all the dwarfs.
Howver, suppose the distribution of Dopey figurines is only 1/2 that of the other figurines. How many boxes then
would we need to be bought to expect to collect a complete set?

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!