The Two Coupons, Generic Quota Coupon Collector's Problem
The classic coupon collector's problem asks:
There aredistinct coupons, and we wish to collect each coupon at least once. We may draw a random coupon uniformly in each iteration. How many iteration does it take, in expectation, to complete a full collection?
The problem attracted significant attention over the years, since many stochastic situations can be modelled as the coupon collector's problem or one of its variants.
It is now well-known that
The Two Coupons, Generic Quota Coupon Collector's Problem
Recently, I took interest in one of many generalized versions of the coupon collector's problem, which is as stated below.
Suppose there are two distinct coupons. In each iteration, the probability of sampling type-1 coupon isand that for type-2 coupon is . Our goal is to collect at least of type-1 and of type-2. How many iterations does it take, in expectation, to complete a full collection?
Brown and Ross[1] addressed this and related problems in 2015. Let
Brown and Ross, being mathematicians, thought this problem trivial and did not show the steps required to achieve this expression. Since I am a mathematical dunce compared to them, I would have liked a detailed explanation! Such explanation doesn't seem to exist. So in this post I'll explain every step to replicate their result.
Derivation
We split all possible outcomes into a series of infinite disjoint events. Event \(\mathcal{E}j\) is the event in which
Part I
Let's find expressions for the two terms. The left term is easy. If we collected
The right term is trickier. So far, we have collected
Combining the two terms, we get
Substitute the binomial equation:
Split the left term into two.
The left term represents the expected number of iterations required to collect
Part II
An easy way to simplify the left term is to assert that the expected number of iterations required to collect
Let us simplify the left term
Thus,
Part III
The ugliest part of the right term is the
Bringing both Part II and part III together, we obtain
By symmetry,
Conclusion
When mathematicians go from one equation to another, they are skipping entire pages worth of derivation. Darn it, mathematicians!
[1] Mark Brown and Sheldon M. Ross. 2016. Optimality Results for Coupon Collection. Journal of Applied Probability 53, 3 (September 2016), 930–937. DOI:https://doi.org/10.1017/jpr.2016.51
[2] Felix Marin. Infinite binomial sum. Mathematics Stack Exchange. Retrieved from https://math.stackexchange.com/a/3106913/1102894.