The Coupon Collector's Problem
Get 2 months of skillshare premium here! skl.sh/vcubingx
Join my discord server! / discord
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.com
github.com/vivek3141
/ vcubingx
/ vcubingx
Пікірлер: 52
Join my discord server! discord.gg/Kj8QUZU Small typo: 7:02 should be 1/p_{n-3}. Credit to viewer Kyro for pointing this out!
Great video Vivek! :)
@vcubingx
4 жыл бұрын
Thanks papa
@steventhijs6921
4 жыл бұрын
Bruh Papa Flammy in da hood?😳what he gonna integrate doe??😎😎🤔
@mapletreemon4834
4 жыл бұрын
@@steventhijs6921 I don't like this comment
@2false637
4 жыл бұрын
It’s all coming together
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!
@vcubingx
4 жыл бұрын
Thank you! I'll try to run my script by a few more people to catch these errors for next time :p
Nice. Glad I discovered this channel. You've inspired me and given me confidence that I too can master "manim".
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)
Well made video! I was frankly surprised how card picking leads us to harmonic numbers (not that I collect cards or anything lol)
@vcubingx
4 жыл бұрын
i was surprised too!
awesome explanation brother, thanks : )
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.
Really nice video! There’s a small typo at 7:02 on the p_{n-3}
@vcubingx
4 жыл бұрын
Thanks! Sorry about the typo, forgot to change it when I copied the previous equation :p
Oh god, I need to learn the manim library
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.
Great and very informative video! 👍
@vcubingx
3 жыл бұрын
Glad you enjoyed it!
Great video! What do you do when the probability of drawing each card is unequal?
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?
@vcubingx
4 жыл бұрын
That's a fantastic question. I haven't taken a look at the derivation, but there's a few general formulas for the case you're talking about on wikipedia here (at the bottom of the page): en.wikipedia.org/wiki/Coupon_collector%27s_problem
Love your content!
@vcubingx
4 жыл бұрын
Glad you enjoy it!
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.
Very elegant!
@vcubingx
4 жыл бұрын
Thank you! 😊
CS 70 flashbacks
@vcubingx
Жыл бұрын
yuh
what if the probabilities are not equal?
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
@bhartendu_kumar
3 жыл бұрын
E is expected no. Of trails till all n coupons seen. We simpliy add all Xi for E. Xi is no. Of coupons to see after we have seen i the coupon and till we see (i+1), so adding all Xi for E makes sense
Could you please explain to me what was done in 7:18? how do you get from one to another. Thanks
What is the distribution of this random variable? Is there a closed form expression for the probability mass function?
@vcubingx
4 жыл бұрын
Uniform distribution
@112BALAGE112
4 жыл бұрын
@@vcubingx Sorry. I meant X_n as the number of packs necessary to collect at least one of each card, parameterized by n, which is the number of distinct cards.
@vcubingx
4 жыл бұрын
Ah, good question - it's a geometric distribution!
@bhartendu_kumar
3 жыл бұрын
Closed expectation would be : ln n + thetha(n). PMF is already closed wrt n
YAAAAS GIRLLL!
Love you
2:06 put some parenthesis (p1=0.5) my eyes hurt from seeing 0.5=5
Incredible
NoiCe
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?
@francisdavecabanting4453
4 жыл бұрын
we are not finding for the probability but for the expected number of trials until we get all cards. To add, the reason we do not find the usual "multiplying by its weight" is that each card is equally likely to be picked.
@richardmerckling592
3 жыл бұрын
Multiplying these probabilities as you're suggesting would provide you the probability of correctly picking a new card for each n cards. EG. for N = 5, 5/5 * 4/5 * 3/5 * 2/5 * 1/5 = .0384 probability of correctly choosing a new card at each turn.
@bhartendu_kumar
3 жыл бұрын
The thing wrong with this, is YOU HAVE NOT UNDERSTOOD YOUR RANDOM VARIABLE or defined here. Once you DEFINE RANDOM VARIABLE and then get to derive EXPECTATION, you will automatically do SUM!
sponsored POG
This sounds like the cereal box problem: mste.illinois.edu/reese/cereal/
@vcubingx
4 жыл бұрын
They're the same problem! Just a different name
First!