5
$\begingroup$

I've been answering old unanswered coupon collection questions recently, and in thinking what other variations might be interesting I came up with this:

There are $n$ coupon types. You successively draw coupons of independently uniformly distributed types. Your friend will give you any type of coupon for a pair of coupons of one type. What is the expected number of draws until you can have a complete set of all types?

There's no point in trading away doubles, so we can assume that you trade if you have a triple (thereby converting it into two singles).

We can consider two variations:

a) You can trade whenever you like.

b) You have to trade immediately when you get a triple.

a) is more favourable, since you can wait until the end to get exactly the coupon types you're still missing, whereas in b) you might trade for a coupon type that you'll draw afterwards anyway.

The setup seems simple enough, but I don't see how to get an expression for the expected number.

Unlike in the standard coupon collector's problem, a continuous approximation is straightforward. Let $m(t)$, $s(t)$ and $d(t)$ denote the fractions of missing, single and double coupon types, respectively, at time $t$, with the initial conditions $m(0)=1$, $s(0)=d(0)=0$. We can approximate the discrete procedure by a continuous process governed by differential equations.

In a), we can consider any triple to be immediately converted to a single plus a pair that we can trade as soon as the number of pairs is equal to the number of missing types. Then $m'=-m$, with solution $m=\mathrm e^{-t}$. Also $s'=m+d-s$ and $d'=s-d$, so $(s-d)'=m-2(s-d)$, with solution $s-d=\mathrm e^{-t}-\mathrm e^{-2t}$. For the fraction $p$ of pairs, $p'=d$ with $p(0)=0$, so, since $d'=s-d$ and $d(0)=0$, we get $p$ by twice integrating $\mathrm e^{-t}-\mathrm e^{-2t}$, yielding $p=\frac12t-\frac34+\mathrm e^{-t}-\frac14\mathrm e^{-2t}$. The process ends when $p=m$, that is, when $\mathrm e^{-2t}=2t-3$, which occurs at $t=\frac12\left(W\left(\mathrm e^{-3}\right)+3\right)\approx1.52374$ (where $W$ is the Lambert W function).

In b), where a triple is immediately converted into two singles,

$$ \pmatrix{m\\s\\d}'=\pmatrix{-1&0&-1\\1&-1&2\\0&1&-1}\pmatrix{m\\s\\d}\;. $$

Diagonalising yields the solution

$$ \pmatrix{m\\s\\d}=\pmatrix{-2+\sqrt5\\\frac12(1-\sqrt5)\\\frac12(3-\sqrt5)}\frac{\mathrm e^{-\frac12(3+\sqrt5)t}}{\sqrt5}+\pmatrix{2+\sqrt5\\\frac12(-1-\sqrt5)\\\frac12(-3-\sqrt5)}\frac{\mathrm e^{-\frac12(3-\sqrt5)t}}{\sqrt5}+\pmatrix{-1\\1\\1}\;, $$

so the process ends with $m=0$ when $(-2+\sqrt5)\mathrm e^{-\frac12(3+\sqrt5)t}+(2+\sqrt5)\mathrm e^{-\frac12(3-\sqrt5)t}=\sqrt5$, which occurs at $t\approx1.67614$ (Wolfram|Alpha computation).

Simulations suggest that in both cases, for $n\to\infty$ the expected number of draws (normalised by $n$) converges to the values from these continuous approximations. (Here's the code.)

I'd be interested in any ideas (for one or both of the variations) for obtaining the expected number of draws or the distribution of the number of draws, or at least obtaining the limits derived above combinatorially rather than by solving differential equations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.