10
$\begingroup$

Consider the classical coupon collectors problem. Given a particular coupon $i$ we can ask for the probability that $i$ is the last coupon collected. We asked this question on cstheory and got a wonderful answer from James Martin introducing us to the idea of Poissonization in coupon collecting:

$Pr(L=i) = \int_{0}^{\infty} n_i e^{n_i t} \prod_{j\neq i} (1-e^{n_j t}) dt$

where $L$ is the last coupon collected and $n_i$ is the number of coupons of type $i$, with $\sum_i n_i = k$.

For example:

$\int_0^\infty a e^{-a t} \left(1-e^{-b t}\right) \left(1-e^{-c t}\right) \left(1-e^{-d t}\right) \left(1-e^{-e t}\right) \left(1-e^{-f t}\right) \, dt$,

gives the following in Mathematica:

$a \left[ \frac{1}{a}-\frac{1}{a+b}-\frac{1}{a+c}+\frac{1}{a+b+c}-\frac{1}{a+d}+\frac{1}{a+b+d}+\frac{1}{a+c+d}-\frac{1}{a+b+c+d}- \right.$ $\left. \frac{1}{a+e}+\frac{1}{a+b+e}+\frac{1}{a+c+e}-\frac{1}{a+b+c+e}+\frac{1}{a+d+e}-\frac{1}{a+b+d+e}-\frac{1}{a+c+d+e}+ \right.$ $\left. \frac{1}{a+b+c+d+e}-\frac{1}{a+f}+\frac{1}{a+b+f}+\frac{1}{a+c+f}-\frac{1}{a+b+c+f}+\frac{1}{a+d+f}-\frac{1}{a+b+d+f}- \right.$ $\left. \frac{1}{a+c+d+f}+\frac{1}{a+b+c+d+f}+\frac{1}{a+e+f}-\frac{1}{a+b+e+f}-\frac{1}{a+c+e+f}+\frac{1}{a+b+c+e+f}- \right.$ $\left. \frac{1}{a+d+e+f}+\frac{1}{a+b+d+e+f}+\frac{1}{a+c+d+e+f}-\frac{1}{a+b+c+d+e+f} \right]$.

The trouble is that this expression takes exponential time in the number of coupons to evaluate and has an exponential number of terms. We are looking for a way to bound this asymptotically in $k$, but any further references or information would be greatly appreciated.

  • 0
    I added $t$ and $dt$ to the first integration, as it is not obvious what is being integrated with respect to what. Change it back if this is wrong.2011-11-30
  • 0
    Sorry about that! You're edit is correct.2011-11-30

2 Answers 2