The Coupon Collector's Problem

The coupon collector's problem goes as follows: let's say you want to collect N coupons through draws that have an equal probability of getting any of the N coupons. What's the expected value of the number of draws to get all N coupons?

Follow Me!

[vcubingx]

Small typo: 7:02 should be 1/p_{n-3}. Credit to viewer Kyro for pointing this out!

[KillianDefaoite]

I know I'm being nitpicky here, but words can often get very confusing when dealing with probability, so it's correct to say the expected value of a random variable, not an event.
Great video Vivek!

[patrickbrown]

Great video, thanks. I think there's an error in the bar graph at the end, though. It appears to just show multiples of 4: 0, 4, 8, 12, 16, 20... The real series starts out with 0, 1, 3, 5.5... then approaches the multiples of 4 for a while.

[NovaWarrior]

Nice. Glad I discovered this channel. You've inspired me and given me confidence that I too can master "manim".

[nabilanwari]

First, thanks for this instructive video. Just in the span of time 6:17 of the video, it has been mentionned that the having a new coupon is bernoulli, whereas it is geometric, with probabil(5-i/5)

[giovannifilippi]

Really nice video!
There’s a small typo at 7:02 on the p_{n-3}

[aarush]

i had one doubt can someone please tell me how we can denote E of n as E of n-1 +1/Pn-1 at 6:41

[BALAGE]

What is the distribution of this random variable? Is there a closed form expression for the probability mass function?

[prometheus]

Well made video! I was frankly surprised how card picking leads us to harmonic numbers (not that I collect cards or anything lol)

[mariusy]

Great video! What do you do when the probability of drawing each card is unequal?

[michel.martins]

Could you please explain to me what was done in 7:18? how do you get from one to another. Thanks

[shantanunene]

A slightly different way to solve: Again we want a recurrence between E_N and E_{N-1}. After we draw the first card, we are hunting for the remaining N-1 cards. This can be normally done in E_{N-1}, but we have a chance of a "garbage card", i.e., the same card that was drawn at the start, reappearing. This card will appear roughly 1/N of the times afterwards, so the expected value jumps to N/(N-1) E_(N-1). Thus we get the recurrence E_N=1+N/(N-1) E_(N-1), and we can solve it to get E_N=N H_N.

Of course this is not very rigorous, so the argument can be made better by considering the expected value E(N, M) of drawing N "good" cards from a possibility of N+M total cards, where M of them are "garbage" cards. We can find a recurrence between E(N, M) and E(N-1, M+1), and use the fact that E(0, K)=0 to get E(N, M)=(N+M)H_N.

[hNeg]

what if the probabilities are not equal?

[andrewadoranti]

When you did the card drawing animation, you should replace the cards you have drawn. If you have drawn 1 of the 5 cards, the probability to get a card you don't already have will always be 1 since it will be impossible to duplicate.

[sahilpandit]

Great video! I was wondering, how could this be extended to account for multiple cards per draw (eg. drawing 3 cards, at random, with N total cards)? Would it still be reliant on Expected Values?

[alejrandom]

2:06 put some parenthesis (p1=0.5) my eyes hurt from seeing 0.5=5

[knights_limit]

Hi Vivek and math community, my original intuition was that the first new card be drawn in n/n ways, the second new card drawn in (n-1)/n ways... the last new card can be drawn is 1/n ways. This seems to be how the solution is, but i thought that we would multiply these probabilities, not add, since we want to have the probability of this whole event, which requires the first new card and the second and so on. What’s wrong with this logic?

[AeRUBIKCubing]

Oh god, I need to learn the manim library

[gauravagrawal]

awesome explanation brother, thanks : )