Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
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 '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
add comment

3 Answers 3

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.

share|improve this answer
    
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
show 1 more comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
1  
The r=1 case is just the coupon collector's problem - en.wikipedia.org/wiki/Coupon_collector%27s_problem. 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 '10 at 17:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.