How does the Coupon Collector Problem change when you draw two items at the same time?

Question

If there are 100 tickets in an urn, and you draw two at a time, look at them, and replace them both, how does that change the problem? It would obviously take half as many trials, but how does the fact that one ticket will never be a duplicate of the other affect the result?

Answer 1

It helps. The simplest way to analyze is to just say that, for any positive integer $n$, the probability of finishing on or before $n$ rounds of this pairwise selection is greater than or equal to the probability of finishing on or before $2n$ rounds of single selection.

An exact analysis is more complicated but you could define a Markov chain with state $c(t) \in \{0, 1, ..., 100\}$ being the number of coupons you have seen after round $t$ (with $c(0)=0$ and $c(1)=2$). Then for $c \in \{2, ..., 98\}$: \begin{align} P_{c,c+2} &= \frac{{100-c \choose2}}{{100 \choose 2}} \geq \left(\frac{100-c}{100}\right)\left(\frac{100-(c+1)}{100}\right)\\ P_{c, c+1} &= \frac{{100 -c \choose 1}{c \choose 1}}{{100 \choose 2}}\\ P_{c,c} &= \frac{{c \choose 2}}{{100 \choose 2}} \leq \left(\frac{c}{100}\right)^2 \end{align} and you could formally use the inequalities in a stochastic coupling argument to prove the claim in the first paragraph.