Finding the CDF for a Modified Coupon Collector Problem with Bernoulli Trials

Question

I'm working with a problem that combines the coupon collector problem with Bernoulli trials and I'm not sure how to work out the probability function.

In the classic coupon collector problem we get a coupon on every attempt and only care about if its new.

In this version we first do a Bernoulli trial with probability $1/p$ to get a coupon. For the expected value its simple, we have the classical solution of coupon collector problem with $k$ coupons $E[X] = k * H_k$ and for the Benoulli trial with success rate $1/p$, $E[X] = p$, so by linearity of expectation the expectation for our modified coupon collector problem is $E[X] = p * k * H_k$

However what I am not sure how to work out is the probability $P(N = n)$ for successfully completing the set of $k$ coupons on the $n$th Bernoulli trial.

I hope this makes sense, I'm not the best at formatting on here.

Update: I have a conjectured solution based on jumping off of the explanation for a simpler case in the comments, with some numerical support, but I don't know how to prove it.

We have for the classical coupon collector problem[1]

$$ \def\stir#1#2{\left\{#1\atop#2\right\}} P(N=n)=\frac{m!}{m^n}\stir{n-1}{m-1}\; $$

where

$$\stir nk=\frac1{k!}\sum_{j=0}^k(-1)^{k-j}\binom kjj^n$$

is a Stirling number of the second kind and counts the number of partitions of a set of n labeled objects into k non-empty unlabeled subsets.

So the we have a CDF for the classical problem

$$P(N <= n) = \sum_{j=0}^{n} \frac{m!}{m^j}\stir{j-1}{m-1}\;$$

Conjecture:

The CDF for our modified problem is:

$$ P(N <= n) = \sum_{k=0}^{n}\sum_{j=1}^{k} {n \choose k}(p)^{k}(1-p)^{n-k} \frac{m!}{m^j}\stir{j-1}{m-1}\;, $$

Where $n$ is the number of Bernoulli trials, $k$ is the number of successful trials, $p$ is the probability of a successful trial and $m$ is the size of the full collection of coupons.

The sum over j is simply the CDF for the classical problem, but we weight it by the binomial probability formula for the likelihood of each possible outcome.

This formula matches what we would expect small cases, for example with $n=4, p=\frac{1}{6},$ and $m=5$ we get that

$$P(N <= 4) = \sum_{k=0}^{4}\sum_{j=1}^{k} {4 \choose k}(\frac{1}{6})^{k}(\frac{5}{6})^{4-k} \frac{5!}{5^j}\stir{j-1}{5-1}\;, $$

But since $k$ is always less than 5, $j$ is also always less than 5, the Stirling Number term is always 0, so the whole product is 0 and we get that

$$P(N <= 4) = 0$$

as expected, since it is trivially impossible to complete a set of 5 coupons in only 4 trials.

In the n=5 case of the same problem we have that

$$P(N <= 5) = \sum_{k=0}^{5}\sum_{j=1}^{k} {5 \choose k}(\frac{1}{6})^{k}(\frac{5}{6})^{5-k} \frac{5!}{5^j}\stir{j-1}{5-1}\;, $$

From before we have that all the terms where $n<5$ are $0$, so looking at the $n=5$ term we have

$$ P(N <= 5) = P(N = 5) = \sum_{j=1}^{5} {5 \choose k}(\frac{1}{6})^{5} \frac{5!}{5^j}\stir{j-1}{5-1}\;, $$

We know that the Stirling Number terms are 0 when $j < 5$ so we can further simplify to just the $j = 5$ case

$$ P(N = 5) = {5 \choose 5}(\frac{1}{6})^{5} \frac{5!}{5^5}\stir{5-1}{5-1}\; = \frac{1}{6^{5}} * \frac{5!}{5^{5}} $$

Which is exactly the same result we get working out the $P(N=5)$ case by itself through calculating the odds of succeeding 5 times in a row, and the odds of each of the 5 coupons being distinct and completing the set.

Numerically as I compute the conjectured CDF with fixed coupon size and trial success probability as the number of trials $n$ becomes very large the value asymptotically approaches 1 which makes me think that it is a CDF and is correct.

EDIT: More numerical evidence for the conjecture being correct, after running for several hours with m = 20,000 I got the result

$$\sum_{n=0}^{m} P(N > n) = 5704.149 \approx E[X] = 5708.\overline{3}$$

However I cannot prove it, and the computation of the CDF is very slow and I do not know how to simplify the expression to speed up the computations.

Answer 1

First some remarks about your attempts:

You seem to have denoted the success probability for the Bernoulli trials first by $1/p$ but later by $p$; I’ll go with the more usual $p$.

There’s no need to use a sum to represent $P(N\le n)$ in the classical problem. The answer that you linked to provides not only $P(N=n)$ but also

$$ \def\stir#1#2{\left\{#1\atop#2\right\}} P(N\le n)=\frac{m!}{m^n}\stir nm\;. $$

I’m not entirely sure I understand your way of including the binomial distribution in $P(N\le n)$, but as far as I can see it doesn’t work that way. The factor $\binom nk p^k(1-p)^{n-k}$ is the probability that $k$ out of $n$ trials succeed and yield a coupon, but $P(N\le n)$ also covers cases with $N\lt n$ that would have to be weighted with probabilities for less than $n$ trials.

I think the easier approach here to recover the expected number of draws is through $\sum_nnP(N=n)$ rather than $\sum_nP(N\gt n)$. Denoting the required number of coupons (i.e. successful trials) by $K$, we have

$$ P(N=n)=\sum_{k=1}^n\binom{n-1}{k-1}p^k(1-p)^{n-k}P(K=k)\;, $$

since we need to first have $k-1$ successful trials and $n-k$ unsuccessful ones, and then finally one successful trial. Thus

\begin{eqnarray} E[N]&=&\sum_{n=1}^\infty nP(N=n)\\ &=&\sum_{n=1}^\infty\sum_{k=1}^nn\binom{n-1}{k-1}p^k(1-p)^{n-k}P(K=k)\\ &=&\sum_{k=1}^\infty\sum_{n=k}^\infty n\binom{n-1}{k-1}p^k(1-p)^{n-k}P(K=k)\\ &=&\sum_{k=1}^\infty\sum_{n=k}^\infty k\binom nkp^k(1-p)^{n-k}P(K=k)\\ &=&\sum_{k=1}^\infty kp^kP(K=k)\sum_{n=k}^\infty\binom nk(1-p)^{n-k}\\ &=&\sum_{k=1}^\infty kp^kP(K=k)p^{-(k+1)}\\ &=&\frac1p\sum_{k=1}^\infty kP(K=k)\\ &=&\frac{E[K]}p\;, \end{eqnarray}

as expected.

The cumulative distribution function, in case you need it, is

\begin{eqnarray} P(N\le n)&=&\sum_{m=1}^nP(N=m)\\ &=& \sum_{m=1}^n\sum_{k=1}^m\binom{m-1}{k-1}p^k(1-p)^{n-k}P(K=k)\;. \end{eqnarray}

I don’t see any way to simplify that.