Coupon Collector Problem Code

16 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;
end
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
else
y(r) = r; %if not adds the number to the vector in the position of the number
end
end
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
end
end
T_mean = sum(T)/m; %calculates the mean
disp(T_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?

Categories

Find more on Programming in Help Center and File Exchange

Products

Community Treasure Hunt

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

Start Hunting!