variation on the coupon collector problem

Question

I'm considering a twist on the classic coupon collector problem. The user has k urn and needs to collect m different balls from each urn. I need to calculate the expected time for the user to collect m different ball form each urn.(k*m balls in total)

I'm not a mathematician any help is welcome.

Thank you very much,

Answer 1

If you draw from one urn at a time, then because the urns are independent, there's no loss of generality to draw from the first urn until you win, then the second urn until you win, and so on.

If $E_{m}$ is the expected time until you draw $m$ balls with replacement from an urn of $m$ balls, then because of the linearity of expectation, the expected time here is $$k\cdot E_m,$$

the number of urns times the expected amount of time to solve the ordinary $m$-coupons problem.

---

If you are not allowed to choose which urn to draw from, but instead must choose uniformly at random from the urns you haven't "won" yet, my intuition says that the expectation is still:

$$k\cdot E_m$$

The reasoning is as follows:

• To play the game, you select an urn uniformly at random from the ones you haven't won yet. You draw a ball from that urn, then replace it. If you've seen all $m$ balls in that urn, you've "won" that urn.
• Here's a variation I think is equivalent:
• At the start, for each urn, draw balls from that urn with replacement until you "win"; write down the sequence of draws that you've made. Now you have a sequence of draws, one sequence per urn.
• The expected length of each sequence is $E_m$.
• To play the game, we'll cross off elements of these sequences. Until all of the elements have been crossed off, uniformly at random pick a sequence that still has uncrossed elements, and cross off the first uncrossed element in that sequence. Evidently it will take exactly $k\cdot E_m$ steps to cross off all elements, since we cross off exactly one element per turn.

---

If you don't stop drawing from an urn once you've won, then you spend $r/k$ fraction of the time doing useless work, where $r$ is the number of urns you've already won. Again using some loose intuitionistic reasoning, it seems like it will take $E_m$ to win one urn, then $\frac{k}{k-1} E_m$ to win the second urn, then $\frac{k}{k-2} E_m$ to win the third, and so on.

Hence if you keep including urns that you've already won, I'd think the total expected time to win overall is:

$$E_m \sum_{r=0}^{k-1} \frac{k}{k-r} = k E_m \sum_{s=1}^{k} \frac{1}{s} = \left[k E_m\right] H_k$$

where $H_k$ is the $k$th "harmonic number". However, this is probably not quite right. It's probably closer to something like $kE_m + a H_k$, given that by the time you "win" one urn, the other urns should also be close to winning; they should have almost the right number of successes.