0
$\begingroup$

I have a set of $N$ elements from which I do $V$ extractions with replacement.

Given a subset of size $k$. What is the probability that all the $k$ elements are extracted at least once?

In other words what is the probability that $\{{x_1, x_2, ..., x_k}\} \subseteq \{{x_{i_1}, ... , x_{i_V}}\} $ where the right term are the V extracted values?

I think in the case $N=V$ this should be $k!/N^k$. How does this generalize to $V>N$ ?

$\endgroup$
0
$\begingroup$

This is a variant of the Coupon Collector's Problem. To make the connection clear, and to cast the problem in more concrete terms, let's say that every carton of Nozalla Cola contains a coupon. There are $N$ different types of coupons, of which $k$ are red and $N-k$ are blue. All the types are equally likely. If the coupon collector has bought $V$ cartons of cola, what is the probability that he has a complete set of all the red types? (The standard Coupon Collector's Problem is the case $k=N$.)

We give two solutions, one based on the Principle of Inclusion/Exclusion (PIE), and one based on exponential generating functions.

To use PIE, it is easier if we find the probability that the collector does not have a complete set of red coupons. So let's say a collection of coupons has Property $i$ if the collection has no red coupon of type $i$, for $1 \le i \le k$. Let $S_j$ be the total of the probabilities of the collections that have $j$ of the properties, i.e. that are missing $j$ of the red coupons, for $1 \le j \le k$. If the collection is missing a set of $j$ coupons, there are $\binom{N}{j}$ ways to pick the set, and the probability that a given set of $j$ is absent is $((N-j)/N)^V$. So $$S_j = \binom{k}{j} \left( \frac{N-j}{N} \right)^V$$ By PIE, the probability that a collection has a least one of the properties, i.e. the probability that there is at least one red type of coupon missing, is $$q = \sum_{j=1}^k (-1)^{j+1} S_j = \sum_{j=1}^k (-1)^{j+1} \binom{k}{j} \left( \frac{N-j}{N} \right)^V$$ The answer to the original problem, the probability that the collections does contain at least one of each red type of coupon is $1-q$.


In solving the problem with generating functions, it is simpler to return to the original problem formulation and find the probability that a collection of $V$ coupons has at least one of each red type. There are $N^V$ possible sequences of $V$ coupons, all of which we assume are equally likely. We want to count the number of sequences in which each red coupon type appears at least once. The exponential generating function for a sequence limited to a single type that appears at least once is $e^x-1$. For a type that may appear an arbitrary number of times, possibly zero, the EGF is $e^x$. So the EGF for a sequence of $k$ types each of which appears at least once and $N-k$ types that appear an arbitrary number of times is $$\begin{align} f(x) &= (e^x-1)^k \; (e^x)^{N-k} \\ &= e^{(N-k)x} \sum_{j=0}^k (-1)^j \binom{k}{j} e^{(k-j)x} \tag{*}\\ &= \sum_{j=0}^k (-1)^j \binom{k}{j} e^{(N-j)x} \\ &= \sum_{j=0}^k (-1)^j \binom{k}{j} \sum_{n=0}^{\infty} \frac{1}{n!} (N-j)^n x^n \end{align}$$ where we have applied the Binomial Theorem at $(*)$. The number of sequences with at least one of each red type of coupon is $V!$ times the coefficent of $x^V$ in $f(x)$: $$V! [x^V]f(x) = \sum_{j=0}^k (-1)^j \binom{k}{j} (N-j)^V$$ So the probability of a complete collection of red coupon types is $$\frac{V! [x^V]f(x)}{N^V} = \sum_{j=0}^k (-1)^j \binom{k}{j} \left ( \frac{N-j}{N} \right)^V$$ (If you are not familiar with generating functions, some resources can be found in the answers to this question: How can I learn about generating functions?)

$\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.