5
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 27, 2010 at 20:15
  • $\begingroup$ 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. $\endgroup$ Jan 27, 2010 at 21:21

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Do you mean "at most (n/r) log(n) steps"? $\endgroup$ Jan 27, 2010 at 20:48
  • $\begingroup$ 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. $\endgroup$
    – Tal K
    Jan 27, 2010 at 20:59
  • $\begingroup$ 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. $\endgroup$ Jan 27, 2010 at 21:26
  • $\begingroup$ 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. $\endgroup$ Jan 27, 2010 at 21:42
  • $\begingroup$ 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). $\endgroup$
    – Tal K
    Jan 27, 2010 at 21:47
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jan 28, 2010 at 1:04
  • $\begingroup$ 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? $\endgroup$ Jan 28, 2010 at 4:47
  • $\begingroup$ 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. $\endgroup$ Jan 28, 2010 at 11:38
1
$\begingroup$

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

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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