wilmott.com

Hi all,A cereal manufacturer puts gift in boxes which come in n different colours. He encourages one to collect all n colours.Assuming there is even odds of getting any one of the colours, what is the expected number of boxes one should buy to get all of the colors?More interesting question (that I didn't manage to solve) :If the different colors comes out with different probabilities, say p_i for colour i, what is the expected number of boxes one must buy ?

Here is my two cents:Define a random variable X_i which is the # of additional cereal boxes you need to buy in order to obtain ith color having collected i-1 different colors (obviously i<=n). If you have collected i-1 distinct colors already, the probability of having a different gift out of the cereal box is p_i=1-((i-1)/n). So, the random variable X_i follows a geometric distribution with p_i. Let X denote the expected number of boxes to buy in order to have collected all n distinct colored gifts. ThenIf you have only one color (n=1), then expected number of cereal boxes to buy is 1 (E[X]=1)If you have two colors (n=2), then expected number of cereal boxes to buy is 3 (E[X]=3). Let's say there are two colors available, blue and yellow. You buy the first cereal box which had blue (yellow) colored gift in it, this is the first cereal box you have to buy. Then in order to get a yellow (blue) colored gift, the expected number of cereal boxes you need to buy is 2 (=1/(1/2)) because p=1/2. So, for two colors, you need to buy 3 cereal boxes.The more interesting question can be also addressed in a similar way by substituting p_i into E[X_i].

I find a result by using a kind of recurence relation and a tree. Consider m colour, the probability of having a given colour is then p=1/m.Consider the event X_m, the event "I already obtain m colours".E[X_m]=E[X_(m-1)]+p*sum[k*(1-p)^(k-1)] The last term can be easily found by drawing a tree and sum over all the branches which gives the missing colour.since p=1/m, p*sum[k*(1-p)^(k-1)]=mSo to obtain m colours, you need to buy in average m(m+1)/2 boxes.

Well, I found the same result in the first case but with a different approach ...In the general case I don't really agree, because you overvalue the expected number of boxes:Imagine n=2 :1/p1 -> time till you get the first coupon1/p2 -> time till you get the second couponbut you should substract : 1/(p1+p2) which represents the time to get either the first or second coupon.The general case is much more complicated ...

I agree reaverprog that the general case is far much more complicated. The recurence formula holds only for an equidistribution of the colours. In the general case, I fear that only a complete tree could give the result (by numerical simulation).

My last message was for anilmagSlt FrenchX, I think that your result is incorrect. Could you elaborate, because I can't see your mistake ? I found the following recurrence :for n colours, Denote E_i the expected number of boxes when 0<=i<n colours remain.E_i = (n-i)/n*(E_i+1) + (i/n)*(E_{i-1} +1)=>E_i = E_{i-1} + n/iand : E_0 = 0Then you get the same result as the one of anilmag ...

Yes I can develop and if you can show me where I've made a mistake I would be thanksfull I won't pretend than my result is the good one because to be sincere I have no idea. But I want to learn so your help is more than welcome .The gifts are in number of N. Consider that you miss only 1 gift. What is the expected number of box you need to have the missing gift ? Assume p the probability to have the missing gift (here p=1/N) and so the probability to obtain a gift you already had is (1-p).so to obtain the gift at the next box so (+1 box), the probability is pfor +2 boxes, the probability is (1-p)*p, (you have to obtain nothing new at the first box and the wanted gift at the second box)for +3 it's (1-p)²*p etc...so the expected number of boxes to have the missing gift is p+2*(1-p)*p+3*(1-p)^2*p+4*(1-p)^3*p+...etcIn the case of p=1/N, this sum gives N. for me the expected number of boxes to obtain N gifts is the one to obtain N-1 gifts +the expected number of boxes to have the missing gift (so N).I have E(N)=E(N-1)+N with E(0)=0 et E(1)=1 (1 box to take 1 gift). here E(2)=E(1)+2=3 (the same result than anilmag, a coincidence) but for E(3)=E(2)+3=3+3=6 (for anilmag the result is 5.5 i think) and for the general case with my formula is E(N)=N(N+1)/2I wouldn't be surprised if I've made a stupid error but at the moment I hardly can't see it.

Find the solution to your more interesting question given by wileysw here.QuoteOriginally posted by: reaverprogHi all,A cereal manufacturer puts gift in boxes which come in n different colours. He encourages one to collect all n colours.Assuming there is even odds of getting any one of the colours, what is the expected number of boxes one should buy to get all of the colors?More interesting question (that I didn't manage to solve) :If the different colors comes out with different probabilities, say p_i for colour i, what is the expected number of boxes one must buy ?

FrenchX >> I guess that your mistake, in case where 1 coupon remains, is due to non consideration of what happens when you get a coupon that you've already found : prob p to buy one more box, prob 1-p to buy E_i+1 boxes ...Avtogner >> There is a better formula to express the solution in case of unequal probabilities. Think of :

QuoteOriginally posted by: reaverprogFrenchX >> I guess that your mistake, in case where 1 coupon remains, is due to non consideration of what happens when you get a coupon that you've already found : prob p to buy one more box, prob 1-p to buy E_i+1 boxes ...Indeed I agree. Is there any closed form solution to the simple case ?

frenchX, p is not 1/N all the time - one does not have to collect the colors in a particular order. once you have collected n boxes, any of the remaining N-n boxes would add one new color to your collection, hence p=(N-n)/N (this is where equal probability of getting each box is important). the answer is simply (N times) the N-th harmonic number as anilmag gave (which is the standard "coupon collector's problem").reaverprog, the integral representation seems interesting. it would be great if you could point to some reference for me. besides the link Avtogner pointed, there was also some discussion of the higher moments of this waiting time here

Thanks for your explanation wileysw.

@reaverprog: if you agree that random variable X_i follows a geometric distribution with p_i, then my solution is correct. Thank you wileysw for providing the name for the general problem.