toys, cereals and statistics

[m_f_h]

This may be a trivial one but well:
Yesterday morning at breakfast my son was deceived since opennig a new cereal box he found one of the 4 CD's to collect which he already got before. Now for the question:

Given that in the boxes of some cereal brand there is hidden one of N different objects to collect, and each time you buy a box you get any one of the N with the same probability 1/N, how many boxes to you have to buy "in the mean" to have a complete collection ?

[fivemack]

This is a standard problem (usually called coupon-collecting)

To get from a collection of 0 to a collection of 1 takes 1 box
To get from 1 to 2 takes N/(N-1) boxes, since the chance of getting a new toy is (N-1)/N
To get from 2 to 3 takes N/(N-2) ...

So it's N * sum(i=1 .. N) 1/i, which is roughly N log N.

[m_f_h]

Originally Posted by fivemack

This is a standard problem (usually called coupon-collecting)

To get from a collection of 0 to a collection of 1 takes 1 box
To get from 1 to 2 takes N/(N-1) boxes, since the chance of getting a new toy is (N-1)/N
To get from 2 to 3 takes N/(N-2) ...

So it's N * sum(i=1 .. N) 1/i, which is roughly N log N.

sorry, so I was right concerning triviality... mea culpa... and thanks nevertheless.

[davieddy]

See also:
http://mersenneforum.org/showthread.php?t=8673

[davieddy]

Originally Posted by m_f_h

sorry, so I was right concerning triviality... mea culpa... and thanks nevertheless.

I would suggest that this solution is simple but that
its validity not trivial.

[davieddy]

I'm thinking that:

p + 2p(1-p) + 3p(1-p)^2 + 4p(1-p)^3 +.........

must equal 1/p. Is this obvious?

I guess we say 1/p = (1-(1-p))^(-1) and use the binomial theorem.

[davieddy]

Originally Posted by davieddy

I'm thinking that:

p + 2p(1-p) + 3p(1-p)^2 + 4p(1-p)^3 +.........

must equal 1/p. Is this obvious?

I guess we say 1/p = (1-(1-p))^(-1) and use the binomial theorem.

S=p + 2p(1-p) + 3p(1-p)^2 + 4p(1-p)^3 +.........
S-(1-p)S=p(1+(1-p)+(1-p)^2+...)
pS=p/(1-(1-p))
S=1/p

The point being that this practically follows from
the definition of probability.