Variant of the Coupon Collector's Problem with Two Probabilities

365 Views Asked by At

The Coupon Collector's Problem is well-known in probability theory. Say there are $n$ types of coupons, where there is a probability of 1/n of getting each coupon with each draw. One expects to draw $n H_n = \Theta(n \ln n)$ (where $H_n$ is the harmonic number) coupons in order to get a complete set of all $n$ coupons.

I'm interested in a variant of this, where the $n$ coupons have two possible probabilities. Say $n_a$ of the coupons each have probability $p_a$ of being drawn, and the remaining $n_b = n - n_a$ coupons have some other probability $p_b$ of being drawn (with total probability $n_a p_a + n_b p_b = 1$, of course). I would like an asymptotic expression for the expected number of draws in order to get a complete set of $n$ coupons.

The exact answer is known. In general, if each coupon has probability $p_i$, then the expected number of draws to get a complete set is $$ \int_0^\infty \left[ 1 - \prod_{i=1}^n \left( 1 - e^{-p_i t} \right) \right] dt. $$ Applying this to the problem at hand, we get $$ \int_0^\infty \left[ 1 - \left( 1 - e^{-p_a t} \right)^{n_a} \left( 1 - e^{-p_b t} \right)^{n_b} \right] dt. $$ Question: Is there an asymptotic expression for this? That is, I'm looking for something analogous to the regular problem's $\Theta(n \ln n)$.