# expected number of coupons

• Feb 17th 2011, 05:10 PM
nikie1o2
expected number of coupons
suppose there are N different types of coupons and each time one obtains a coupon, it is equally likely to be any one of the N types. Find the expected number of coupons one needs to collect before obtaining a complete set of atleast one of each type
• Feb 17th 2011, 05:24 PM
harish21
what have you done so far?
• Feb 17th 2011, 05:29 PM
nikie1o2
i let X= the # of different types of coupons in a set of n coupons and X(i)= type of coupon but i honestly have no clue how to set this problem up or execute it.
• Feb 17th 2011, 08:54 PM
harish21
Let X denote the number of coupons collected before a complete set is attained.

Let $X_i \;\;i=0,\cdots,N-1$ be the number of additional coupons that need to be obtained after i distinct types have been collected in order to obtain another distinct type.

So, $X=X_0+X_1+\cdots+X_{N-1}$

when you have collected i distinct coupons, you will obtain a new coupon with a probability of $\dfrac{N-i}{N}$

$P(X_i = k)= \bigg(\dfrac{N-i}{N}\bigg)\;\bigg(1-\dfrac{N-i}{N}\bigg)^{k-1}\;\;\; k\geq 1,$

figure out what distribution this is and find its expected value.
• Feb 18th 2011, 02:11 AM
mr fantastic
Quote:

Originally Posted by nikie1o2
suppose there are N different types of coupons and each time one obtains a coupon, it is equally likely to be any one of the N types. Find the expected number of coupons one needs to collect before obtaining a complete set of atleast one of each type

Coupon collector's problem - Wikipedia, the free encyclopedia