# How many trial picks expectedly sufficient to cover a sample space?

Consider a sequence of independent events where an $r$ element subset of an $n$ element set is picked uniformly randomly (ie. any of the $\begin{pmatrix}n\newline r\end{pmatrix}$ possibilities being equally likely).

What is the expected number of subsets one has pick to cover the whole set?

Here the terminology means: a sequence of picks $A_1,A_2,\ldots,A_n$ covers the whole set if $|A_1 \cup \cdots \cup A_n| = n$. A sequence $A_1, A_2,\ldots$ succeeds to cover the whole set in $n$ steps, if $A_1,\ldots,A_n$ covers the whole set but $A_1,\ldots, A_{n-1}$ does not.

The expected numbers seems to be much higher than one would imagine. But I could not quite come up with a closed form. But chances are, its always a rational number.

• You should edit your question to not use $n$ for both the cardinality of the set and the number of steps to cover the set. Also, interesting question! I look forward to seeing what people come up with for this one. – Zev Chonoles Jan 27 '10 at 20:15
• As you expected, it is always rational. If you let F(n,k,r) denote the expected number of additional sets you need when you already have covered k elements of your n, then you can set up a linear recurrence for F(n,k,r) in terms of F(n, k-1, r), F(n, k-2, r), ..., F(n, k-r, r) by looking at how many elements are covered by your next set. Combined with the boundary condition F(n,0,r)=0, you could in theory solve to get F(n,0,r) as a rational number. This is what is done in the "coupon collector" problem referenced by Tal K (the case r=1), but is impractical for, say, n/r bounded. – Kevin P. Costello Jan 27 '10 at 21:21

This process will cover the set faster than making $r$ random selections of a single element at each step ("sampling with replacement", producing a multiset of $r$ not-necessarily-distinct elements instead of a set of $r$ distinct elements). The latter is taking $r$ steps at a time in the Coupon Collector process which takes $n * log(n)$ steps. So we need at least $(n/r) * log(n)$ steps on average. This should be a close approximation when $n/r$ is large and within a bounded (not necessarily constant) factor of the truth when $n/r$ is bounded. The case when $n=2r$ is close to the "20 questions" problem of Erdos and Renyi.

• Do you mean "at most (n/r) log(n) steps"? – Reid Barton Jan 27 '10 at 20:48
• Yes, "at most", meaning that the slower coverage process takes (n/r)*log(n). Thanks for catching that. Also, when I say "a close approximation" I suppose that the asymptotic difference between the with- and without- replacement expected times (in the case when n/r is large) would be an additive difference of O(log n), not a multiplicative difference of a constant factor in the larger main term. In the n/r bounded case there could well be some log-periodic function as the "constant", as in the Erdos-Renyi problem. It would take a more detailed calculation to find out. – Tal K Jan 27 '10 at 20:59
• It seems like even when n/r is bounded that n/r log n should be the right answer up to a (1+o(1)) multiplicative factor. If we considered an alternative model where each element is included in a set INDEPENDENTLY with some probability p, then it's easy to see (e.g. by computing the second moment of the number of omitted elements) that the threshold is log n/p sets. But the threshold is monotone in p, and you can sandwich the original problem with r=cn in between p=c-o(1) and p=c+o(1) with high probability. – Kevin P. Costello Jan 27 '10 at 21:26
• If you fill cartons of r distinct coupons, it takes an average of (n/n + n/(n-1) + ... + n/(n-r+1)) coupons to fill a carton. So, a random r selection is like taking that many steps in the coupon collector process. – Douglas Zare Jan 27 '10 at 21:42
• Kevin, your alternative model with p=1/2 is the Erdos-Renyi "20 Questions" problem, and the expected coverage time in that case involves both the [base 2] log(n) and some function of the fractional part of log(n). That's not necessarily inconsistent with your remark (for instance the log-periodic term could be additive, not multiplicative, I don't have the reference handy to check which it is). – Tal K Jan 27 '10 at 21:47

The expected number of picks needed equals the sum of the probabilities that at least $t$ picks are needed, which means that $t-1$ subsets left at least one value uncovered. We can use inclusion-exclusion to get the probability that at least one value is uncovered.

The probability that a particular set of $k$ values is uncovered after $t-1$ subsets are chosen is

$$\Bigg(\frac{n-k \choose r}{n \choose r}\Bigg)^{t-1}$$

So, by inclusion-exclusion, the probability that at least one value is uncovered is

$$\sum_{k=1}^n {n \choose k}(-1)^{k-1}\Bigg(\frac{n-k \choose r}{n \choose r}\Bigg) ^{t-1}$$

And then the expected number of subsets needed to cover everything is

$$\sum_{t=1}^\infty \sum_{k=1}^n {n \choose k}(-1)^{k-1} \Bigg(\frac{n-k \choose r}{n \choose r}\Bigg)^{t-1}$$

Change the order of summation and use $s=t-1$:

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

The inner sum is a geometric series.

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

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

I'm sure that should simplify further, but at least now it's a simple sum. I've checked that this agrees with the coupon collection problem for $r=1$.

Interestingly, Mathematica "simplifies" this sum for particular values of $r$, although what it returns even for the next case is too complicated to repeat, involving EulerGamma, the gamma function at half-integer values, and PolyGamma[0,1+n].

• Maple doesn't give a simpler form even for r=2, although there's no guarantee that there's not some trick it doesn't see. Also, your answer seems to agree with Tal K's asymptotics below. – Michael Lugo Jan 28 '10 at 1:04
• If you plug r=1 into that formula, it still takes some manipulation to convert the alternating sum of (n choose k)/k to (1 + 1/2 + 1/3 + ... + 1/n). Can one express it as a similar sum of positive decreasing terms? – Douglas Zare Jan 28 '10 at 4:47
• For r=2, here is what Mathematica reports: n/(4^n (1-2n)^2 Sqrt[Pi]) * (Gamma[1/2-n](-2n^2 Gamma[n] + Gamma[1+n])) + n(n-1)/(1-2n)^2*(1+EulerGamma(-1+2n)+(-1+2n)PolyGamma[0,1+n]). I've tried to simplify this by cancelling a few terms, and I hope I haven't introduced any errors. Note that 2n-1 or n-1/2 shows up in many places. For r=3, the formula involves many occurrences of Sqrt[1+6n-3n^2] which is imaginary for n \ge 3. – Douglas Zare Jan 28 '10 at 11:38

EDIT: While the $r=1$ case is the easiest, I thought it would be helpful to work it out anyway. I get that the expected number of picks necessary for $r=1$ is $nH_n$, where $H_n$ is the $n$th harmonic number, which is in line with Tal K's answer since $H_n\approx\ln(n)$.

Suppose the total number of elements covered by our picks so far is $k$. If we calculate the expected number of picks it will take to get to $k+1$, then we simply take the sum of our result from $k=0$ to $k=n-1$. There are $n-k$ elements we still need to hit, so there is an $\frac{n-k}{n}$ probability of having $k+1$ covered after 1 pick, $\frac{n-k}{n}(\frac{k}{n})$ probability of having $k+1$ covered after exactly 2 picks, and in general $\frac{n-k}{n}(\frac{k}{n})^j$ probability of going to $k+1$ after exactly $j$ picks. Thus, the expected number of picks to go from $k$ covered to $k+1$ covered is $(\frac{n-k}{n})\sum_{j=1}^\infty k(\frac{k}{n})^{k-1}$, which by the standard derivative trick we know is $(\frac{n-k}{n})\frac{1}{(1-\frac{k}{n})^2}=\frac{n}{n-k}$. Thus the expected number of picks of 1 element subsets necessary to cover an $n$ element set is $\sum_{k=0}^{n-1}\frac{n}{n-k}=n\sum_{k=1}^n\frac{1}{k}=nH_n$.