2
$\begingroup$

Consider the usual generalization of the coupon collector problem where $m$ copies of each coupon need to be collected. Let $T_m$ be the first time m copies of each coupon are collected. Donald J. Newman and Lawrence Shepp showed that $$\mathbf{E} (T_{m})=n\log n+(m-1)n\log \log n+O(n),\ {\text{as}}\ n\to \infty $$

Then Erdős and Rényi showed that:

$$\displaystyle \operatorname {P} {\bigl (}T_{m}<n\log n+(m-1)n\log \log n+cn{\bigr )}\to e^{-e^{-c}/(m-1)!},\ \ {\text{as}}\ n\to \infty .$$

But these statement are asymptotic. Are there known finite sample (upper and lower) bounds on $T_m$ ?

$\endgroup$
2
2
$\begingroup$

What follows is a minor contribution where we compute a formula for the expectation for the case where $j$ instances of each of $n$ types of coupons must be seen. Using the notation from the following MSE link we have from first principles that

$$P[T = m] = \frac{1}{n^m}\times {n\choose 1}\times (m-1)! [z^{m-1}] \left(\exp(z) - \sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1} \frac{z^{j-1}}{(j-1)!} \\ = \frac{n}{n^m}\times {m-1\choose j-1} (m-j)! [z^{m-j}] \left(\exp(z) - \sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1}.$$

We verify that this is a probability distribution. The goal here is to find a closed form for the infinite series in $m$ so that its value may be calculated rather than approximated. Expanding the power we find

$$\sum_{m\ge j} P[T=m] = \frac{n}{n^j} \sum_{m\ge 0} \frac{1}{n^m} \times {m+j-1\choose j-1} m! [z^m] \sum_{k=0}^{n-1} {n-1\choose k} \exp(kz) \\ \times (-1)^{n-1-k} \left(\sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1-k} \\ = \frac{n}{n^j} \sum_{m\ge 0} \frac{1}{n^m} \times {m+j-1\choose j-1} m! \sum_{k=0}^{n-1} {n-1\choose k} \sum_{p=0}^m \frac{k^{m-p}}{(m-p)!} \\ \times (-1)^{n-1-k} [z^p] \left(\sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1-k} \\ = \frac{n}{n^j} \sum_{k=0}^{n-1} {n-1\choose k} (-1)^{n-1-k} \sum_{p\ge 0} [z^p] \left(\sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1-k} \\ \times \sum_{m\ge p}\frac{1}{n^m} \times {m+j-1\choose j-1} m! \times \frac{k^{m-p}}{(m-p)!} \\ = \frac{n}{n^j} \sum_{k=0}^{n-1} {n-1\choose k} (-1)^{n-1-k} \sum_{p\ge 0} n^{-p} [z^p] \left(\sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1-k} \\ \times \sum_{m\ge 0}\frac{1}{n^m} \times {m+p+j-1\choose j-1} (m+p)! \times \frac{k^m}{m!}$$

The inner sum is

$$\frac{1}{(j-1)!} \sum_{m\ge 0} (k/n)^m \frac{(m+p+j-1)!}{m!} = \frac{(p+j-1)!}{(j-1)!} \frac{1}{(1-k/n)^{p+j}}$$

and with $P=(n-1-k)(j-1)$ we obtain

$$\bbox[5px,border:2px solid #00A000]{ n \sum_{k=0}^{n-1} {n-1\choose k} \frac{(-1)^{n-1-k}}{(n-k)^j} \times \sum_{p=0}^P \frac{1}{(n-k)^p} \frac{(p+j-1)!}{(j-1)!} [z^p] \left(\sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1-k}.}$$

We claim that the inner sum is $(n-k)^{j-1},$ proof for $j=2$ at end of document. With this the sum reduces to

$$n \sum_{k=0}^{n-1} {n-1\choose k} \frac{(-1)^{n-1-k}}{n-k} \\ = - \sum_{k=0}^{n-1} {n\choose k} (-1)^{n-k} = 1 - \sum_{k=0}^{n} {n\choose k} (-1)^{n-k} = 1$$

and we see that we indeed have a probability distribution.

Continuing with the expectation and re-capitulating the earlier computation we find

$$E[T] = \sum_{m\ge j} m P[T = m] = \frac{n}{n^j} \sum_{k=0}^{n-1} {n-1\choose k} (-1)^{n-1-k} \sum_{p\ge 0} n^{-p} [z^p] \left(\sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1-k} \\ \times \sum_{m\ge 0}\frac{1}{n^m} \times {m+p+j-1\choose j-1} (m+p)! (m+p+j) \times \frac{k^m}{m!}$$

The inner sum has two pieces, the first is

$$\frac{1}{(j-1)!} \sum_{m\ge 1} (k/n)^m \frac{(m+p+j-1)!}{(m-1)!} = \frac{1}{(j-1)!} \frac{k}{n} \sum_{m\ge 0} (k/n)^m \frac{(m+p+j)!}{m!} \\ = \frac{k}{n} \frac{(p+j)!}{(j-1)!} \frac{1}{(1-k/n)^{p+j+1}} = \frac{k}{n-k} \frac{(p+j)!}{(j-1)!} \frac{1}{(1-k/n)^{p+j}}$$

and the second has been evaluated when we summed the probabilities to give

$$(p+j) \frac{(p+j-1)!}{(j-1)!} \frac{1}{(1-k/n)^{p+j}} = \frac{(p+j)!}{(j-1)!} \frac{1}{(1-k/n)^{p+j}}.$$

Substituting these into the outer sum we thus obtain

$$\bbox[5px,border:2px solid #00A000]{E[T] = n^2 \sum_{k=0}^{n-1} {n-1\choose k} \frac{(-1)^{n-1-k}}{(n-k)^{j+1}} \times \sum_{p=0}^P \frac{1}{(n-k)^p} \frac{(p+j)!}{(j-1)!} [z^p] \left(\sum_{q=0}^{j-1} \frac{z^q}{q!}\right)^{n-1-k}.}$$

There is a very basic program which confirmed this formula for several digits of precision by simulation which is written in C and goes as follows.

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <time.h>

int main(int argc, char **argv)
{
  int n = 6 , j = 3, trials = 1000; 

  if(argc >= 2){
    n = atoi(argv[1]);
  }

  if(argc >= 3){
    j = atoi(argv[2]);
  }

  if(argc >= 4){
    trials = atoi(argv[3]);
  }

  assert(1 <= n);
  assert(1 <= j);
  assert(1 <= trials);

  srand48(time(NULL));
  long long data = 0;

  for(int tind = 0; tind < trials; tind++){
    int seen = 0; int steps = 0; 
    int dist[n];

    for(int cind = 0; cind < n; cind++){
      dist[cind] = 0;
    }

    while(seen < n){
      int coupon = drand48() * (double)n;

      steps++;

      if(dist[coupon] == j-1)
        seen++;
      dist[coupon]++;
    }

    data += steps;
  }

  long double expt = (long double)data/(long double)trials;
  printf("[n = %d, j = %d, trials = %d]: %Le\n", 
         n, j, trials, expt);

  exit(0);
}

Proof of inner sum for $j=2.$ Setting $j=2$ we have to show that

$$n-k = \sum_{p=0}^{n-1-k} {n-1-k\choose p} \frac{1}{(n-k)^p} (p+1)!.$$

This is

$$\frac{1}{(n-1-k)!} = \sum_{p=0}^{n-1-k} \frac{1}{(n-1-k-p)!} \frac{p+1}{(n-k)^{p+1}}.$$

Re-writing as follows

$$\frac{1}{m!} = \sum_{p=0}^{m} \frac{1}{(m-p)!} \frac{p+1}{(m+1)^{p+1}}.$$

and introducing

$$\frac{1}{(m-p)!} = \frac{1}{2\pi i} \int_{|w|= \gamma} \frac{1}{w^{m-p+1}} \exp(w) \; dw$$

we obtain for the sum (the integral vanishes nicely when $p\gt m$ so we may extend $p$ to infinity)

$$\frac{1}{2\pi i} \int_{|w|= \gamma} \frac{1}{w^{m+1}} \exp(w) \frac{1}{m+1} \sum_{p\ge 0} \frac{p+1}{(m+1)^p} w^p \; dw \\ = \frac{1}{m+1} \frac{1}{2\pi i} \int_{|w|= \gamma} \frac{1}{w^{m+1}} \exp(w) \frac{1}{(1-w/(m+1))^2} \; dw.$$

We now use the fact that residues sum to zero and the poles are at $w=0$, $w=m+1$ and $w=\infty.$ We get for the residue at infinity

$$-\frac{1}{m+1} \mathrm{Res}_{w=0} \frac{1}{w^2} w^{m+1} \exp(1/w) \frac{1}{(1-1/w/(m+1))^2} \\ = - \frac{1}{m+1} \mathrm{Res}_{w=0} w^{m+1} \exp(1/w) \frac{1}{(w-1/(m+1))^2} \\ = - (m+1) \mathrm{Res}_{w=0} w^{m+1} \exp(1/w) \frac{1}{(1-w(m+1))^2} \\ = -(m+1) [w^{-(m+2)}] \exp(1/w) \frac{1}{(1-w(m+1))^2}.$$

Extracting coefficients we find

$$-(m+1)\sum_{q\ge 0} \frac{1}{(q+m+2)!} (q+1) (m+1)^q.$$

This is

$$-(m+1) \left(\sum_{q\ge 0} \frac{1}{(q+m+1)!} (m+1)^q - \sum_{q\ge 0} \frac{1}{(q+m+2)!} (m+1)^{q+1}\right) \\ = -(m+1) \left(\sum_{q\ge 0} \frac{1}{(q+m+1)!} (m+1)^q - \sum_{q\ge 1} \frac{1}{(q+m+1)!} (m+1)^{q}\right) \\ = -(m+1) \frac{(m+1)^0}{(m+1)!} = - \frac{1}{m!}.$$

We thus have the claim if we can show the residue at $w=m+1$ is zero. We use

$$(m+1)\frac{1}{2\pi i} \int_{|w|= \gamma} \frac{1}{w^{m+1}} \exp(w) \frac{1}{(w-(m+1))^2} \; dw.$$

and observe that

$$\left.\left(\frac{1}{w^{m+1}} \exp(w) \right)'\right|_{w=m+1} \\= \left.\left( -(m+1)\frac{1}{w^{m+2}} \exp(w) + \frac{1}{w^{m+1}} \exp(w) \right)\right|_{w=m+1} \\ = \exp(m+1) \left(-(m+1)\frac{1}{(m+1)^{m+2}}+\frac{1}{(m+1)^{m+1}}\right) = 0$$

as required. This concludes the computation.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.