Skip to main content

Coupon Collector Problem

Source: Peter Winkler book, Placement quant company interview, Wikipedia

Problem:
1) How many times do you need to flip a coin before you expect to see both heads and tails?
2) How many times do you need to roll a die before you expect to see all the numbers 1-6?
3) A company — say Coca-Cola, for concreteness — is holding a contest where everyone who collects one each of n different "coupons" wins some prize. You get a coupon with each purchase of a Coke, and each coupon is equally likely. What’s the expected number of Cokes you have to buy in order to collect all the coupons?

Update (10/01/10): Solution posted by Giridhar (IITK alumnus, Yahoo! Engineer) in comments!!

Comments

  1. when do you expect an event to happen? i guess when its probability is more than 1/2. if thats the case, here is the solution.
    solving the last part first, let us calculate the probability of the event not happening, that is, he is not able to collect at least one coupon, that is, every time he takes a coupon, it is out of the n-1 remaining coupons. probability of that happening is (n-1)/n. let k be the number of coke bottles required. then possibility of event not happening is n*((n-1)/n)^k (we multiply by n because it could be any of the n coupons he doesn't get). this should be less than 1/2. thus, k is the ceiling function of log(1/2n)/log((n-1)/n).
    the first two parts are similar. n being 2 in the first part, and 6 in the second. the answers being 3 for the first part and 14 for the second.
    is it right?

    ReplyDelete
  2. actually the ceiling function of log(1/2n)/log((n-1)/n)+epsylon, to make it greater than 50%

    ReplyDelete
  3. @suyash..
    In how many chances I expect E to happen? is equivalent to
    What is the expectation value of the number of chances for E to happen.

    For eg: Expected number of times I need roll a dice to get a 2 is 6.
    This is because probability of getting 2 in x rolls is (5/6)^(x-1)1/6 = 5^(x-1)/6^x

    So, Expected value = sigma (x=1 to infinity) (x/5)*(5/6)^x
    Expected value = 6

    Refer wikipedia link here

    ReplyDelete
  4. Divide the whole process in to stages. Each stage ends with collecting a coupon which is new ( different from the coupons we already have )

    Let C_i be the random variable which denotes the number of coupons we buy in the stage i.

    Let C be the random variable which denoted the number of coupons we buy in order to get all n coupons
    Now,
    C= C_1 + C_2 + ... + C_n
    Note C_1 = 1;
    In general, while we are during stage i , we already have with us (i-1) different coupons. So, the probability of getting a new coupon is p_i = n-(i-1)/n. Also note that each C_i is a Geometrically distributed random variable with success probability equal to p_i. So, E(C_i) = 1/p_i = n/(n-i+1).
    By using Linearity of Expectations,
    E(C) = E(C_1) +E(C_2) + ...+E(C_n)
    = n(1/n + 1/(n-1)+ ... +1)
    ~ nlogn.

    ReplyDelete
  5. @Giridhar.. Nice solution.. Thanx

    Just finding the answers using the way suggested by Giridhar:

    1) 2/2+2/1 = 3
    2) 6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1 = 14.7
    3) n*(H_n) ~ n(ln n)

    ReplyDelete

Post a Comment

Popular posts from this blog

Asking a girl out

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P

Most of my friends already read an article that I wrote more than an year back - "Speak Up"


Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it!

Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis.

@Consultants, correct me if I am wrong in my estimates. :P

Why is there a need to be selective?

From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once every week right …

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process.

1) Calculate P{X>Y}
2) What's the expected value of X
3) What's the expected value of Y

This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment.

Solution:
1)
(Solved by me finally after 13 months :))

Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently.

So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0"

f(State) = P(X>Y | "State" configuration initially)

f(0,0) = 1/4[f(…

Fraction Brainteaser

Source:
Sent to me by Gaurav Sinha

Problem:
Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions. In total, Siddhant scores 25 out of 34. 

Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34.

Note that
a) Vaibhav scores more than Siddhant
b) Siddhant score better than Vaibhav in both individual topics - 5/6 > 20/25 and 20/28 > 6/9

How is it possible?