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

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

2
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 2010 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 2010 at 21:21

## 3 Answers

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 2010 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 2010 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 2010 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 2010 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 2010 at 21:47
show 1 more comment

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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

-

1
The r=1 case is just the coupon collector's problem - en.wikipedia.org/wiki/…. Look at the 'calculating the expectation' section of the linked page for a much simpler and more elegant way of getting your result. – Jeff Hussmann Jan 28 2010 at 17:42

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 2010 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 2010 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 2010 at 11:38
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 50, "mathjax_display_tex": 6, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9344167709350586, "perplexity_flag": "middle"}