The Coupon Collector Problem
HTML-код
- Опубликовано: 28 авг 2024
- MIT 6.041SC Probabilistic Systems Analysis and Applied Probability, Fall 2013
View the complete course: ocw.mit.edu/6-0...
Instructor: Kuang Xu
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
![The most beautiful equation in math, explained visually [Euler’s Formula]](http://i.ytimg.com/vi/f8CXG7dS-D0/mqdefault.jpg)
In order to fully grasp this video, one needs to understand:
1. Linearity of expectations.
2. Geometric distribution and its expected value.
3. Random variables.
If you do not have in-depth knowledge of the above topics, go and watch a few videos to learn them first. You'll understand this video much better after it. When I first watched this video, I didn't get it much. But I can appreciate the method described, now that I know these concepts.
I'd put 3. in 1st
What if you don't want to understand any of it but just to memorize a routine to get the answer given K? Is that possible?
You don't need in depth anything, those aren't hard thing to know and you can learn them pretty quickly
Where should i learn these from sir
Great presentation, thanks. Minor typo at the end (6:46) the last sum is from 1 to K (as opposed to K-1).
I was trying to figure out why was it like that for a few minutes :S Thanks!
Thank you! I have a midterm later today and could not understand this very well. Kudos to you!
wonderful ! so we took a random variable which essentially is a function and decomposed it into sum of other random variables (functions) whose expectations are much easy to calculate. Decomposition looks magical to me , wonder if there is a thought process that leads to finding correct decomposition quickly for a given problem.
thanks for the great video. isn't there a small mistake at the end? the last but one expression should read k, sum i = 1 to k, 1 over i ?
You are right. Or we can make it sum i=0 to k-1 of 1 over k-i
i dont want to be the only critic but i guess i learn different and i learn through the asking of why per step.. this video is very difficult to chew
people who has iq as low as u do should not watch this video
ignore this rujia hao.. sounds like a child.
what is the coupons collector problem?
I'm sure this is a basic question, but why is E[Xi] the *inverse* of the geometric distribution? Around 4:50
E[X] = 1 / p for any geometric random variable X
If success parameter of geometric distribution is (p), here (n-i/n ), then E(Xi) = 1/p I.e. (n/n-i) here
E[X] for a geometric random variable is Σk.p.(1 - p)^(k-1) as per the definition of discrete expectation. You can solve this by differentiating the expression for infinite sum of a geometric series and getting an equivalent expression from there, or from knowledge of generating functions. Generally, Σ(k + 1).x^(k) has the expression 1/(1 - x)^2.
So here Σk.p.(1 - p)^(k-1) = p.Σk.(1 - p)^(k-1) = p.Σ(k + 1).(1 - p)^(k) = p/(1 - (1 - p))^2 = 1/p. I changed the limits of the sum here, which I can't show, but this is the gist of the algebraic explanation for geometric expectation.
In the second to last line he writes 6 Sum from i to 6 of 1/i. When he generalizes to k cases, he writes k Sum from i to k-1 of 1/i. Why the k-1 expression when he summed to 6 when k=6?
That was Beautifully explained; thanks!
k*ln(k) = 6 * 1.71 = 10.75
This gives wrong answer?
Can someone help here?
If I'm not wrong, the idea is that the expected value is equal to k * the kth harmonic number (since it's k * (1+1/2+1/3+...+1/k)). Now the ln(k) comes into play as it's meant to serve as the approximation for the kth harmonic number. The approximation is that the kth harmonic number is roughly ln(k)+γ, where γ is the Euler-Mascheroni constant (0.57721...). Using this should get you into the same ballpark of values - the approximation is better for larger values of k.
Ah! Thanks.
Actually Sigma (1/i) = ln n + thetha (1) So, there would be some disparity in approximation if n is not asymptotically larger
@@sahilpandit285 Thanks!!!!!!!! I've wanted to just know how to do the calculation for years literally. But every time I asked in places like discord math servers the elitist jerks told me I have to take courses in this that and the other first. I'm going to go back gloat to their face that I knew was right that they were just being priiks because now I can get a very good approximate answer without having to understand all that.
@@sahilpandit285 I knew there had to be at least one nice person in the world of math that would actually help you and give you the information you needed instead of trying to make you feel lesser.
Very clear explanation
excellent presentation, thank you
why the inverse of geo would be expected value of indicatpr variable?
people who has iq as low as u do should not watch this video
@@TheJustinmulli rujia said the same to another commenter. Daniel is just mocking him for it.
Very awkwardly presented.
What a God awful presentation!
1- For grades collection to qualify as a coupon collector problem, you should make it clear that the grades are uniformly distributed, which you didn't, and that the papers are being replaced back into the stack, which you also missed.
2- What on earth is Xi = Geo(6-x/6)? Xi is a random variable who's probability distribution is geometric not the variable itself!
3- You should've hinted at "n-th Harmonic" when you got stuck evaluating that God awful summation at the end since the entire problem can be reduced to n*Hn ;-).
that is because u are an idiot
bad comments.
Yes, it's not well presented.
Very helpful.. :+1: