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

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.

• I assume $n$ is the number of different coupons, as usual. But do you really mean the same "$n$" in "$P(N=n)$"? That is, you are asking what is the probability of getting all $n$ different coupons in exactly $n$ trails (given that in each trial, with probability $1/p$, you get a coupon uniformly at random)? Wouldn't that (by a standard conditional probability calculation) just be $(1/p)^n$ times the probability of getting all $n$ coupons in $n$ trials in the regular coupon collectors problem? Seems like a nice homework exercise? Commented May 31, 2021 at 2:15
• No sorry @NealYoung, I didn't give full information in the final statement my mistake. Your solution is correct in your interpretation of the ambiguous problem I wrote though. I am actually trying to solve the problem in general, given a set of k coupons, with a coupon received on each trial with probability 1/p (so 1/pk for a specific coupon) what is the probability of having finished on P(N = n). n having no relation to k the number of coupons. Hopefully the problem makes sense after that edit Commented May 31, 2021 at 3:33
• Did some thinking based on your comment @NealYoung and came up with a conjecture I think is right, but not sure how to prove it or compute it quickly Commented May 31, 2021 at 10:53
• Does this answer your question? Probability distribution in the coupon collector's problem Commented Jun 1, 2021 at 13:24
• No, @AaronCao I reference that post in my conjecture, but that is for the standard coupon collector problem and gives the probability for completion after n coupons, not after n trials. Commented Jun 1, 2021 at 15:02

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.