4
$\begingroup$

Let $A=\{1,\ldots,n\}$. Now, we uniformly randomly select $k$ subsets, $A_i$ of size $d$ from $A$. What is the probability that $\bigcup_i A_i=A$? This seems to be natural variant of the set cover problem.

$\endgroup$
1
  • $\begingroup$ Do you have a response to the answers below? $\endgroup$ Dec 12, 2021 at 17:12

3 Answers 3

1
$\begingroup$

For $i\in[k]:=\{1,\dots,k\}$ and $j\in[n]$, let $B_{i,j}$ denote the event that $j$ is in the random set $A_i$: \begin{equation} B_{i,j}:=\{j\in A_i\}. \end{equation}

We need to find $P(B)$, where \begin{equation} B:=\bigcap_{j\in[n]}\bigcup_{i\in[k]}B_{i,j}. \end{equation}

By the de Morgan rule,
\begin{equation} B^c=\bigcup_{j\in[n]}C_j,\quad\text{where}\quad C_j:=\bigcap_{i\in[k]}B_{i,j}^c. \end{equation} So, by inclusion-exclusion, \begin{equation} P(B^c)=\sum_{r=1}^n(-1)^{r-1}\sum_{J\in\binom{[n]}r} P\Big(\bigcap_{j\in J}C_j\Big), \end{equation} where $\binom{[n]}r$ is the set of all subsets of $[n]$ of cardinality $r$.

In turn, if $J\in\binom{[n]}r$, then \begin{equation} P\Big(\bigcap_{j\in J}C_j\Big)=P\Big(\bigcap_{i\in[k]}\bigcap_{j\in J}B_{i,j}^c\Big) =P\Big(\bigcap_{j\in J}B_{1,j}^c\Big)^k, \end{equation} by the independence of the $A_i$'s, and \begin{equation} P\Big(\bigcap_{j\in J}B_{1,j}^c\Big)=P\big(A_1\cap J=\emptyset\big) =\binom{n-r}d\Big/\binom nd. \end{equation} Thus, the probability in question is \begin{equation} \begin{aligned} P(B)&=1-\sum_{r=1}^n(-1)^{r-1}\binom nr \binom{n-r}d^k\Big/\binom nd^k \\ &=\sum_{r=0}^n(-1)^r\binom nr \binom{n-r}d^k\Big/\binom nd^k. \end{aligned} \end{equation}


The latter expression is probably impossible to simplify in general. Mathematica can do nothing with it even for $k=2$ (click on the image to enlarge it):

enter image description here

Here is the table of values of $P(B)$ for $k=2$ and $n,d$ such that $1\le d\le n\le10$ (click on the image to enlarge it):

enter image description here

$\endgroup$
0
$\begingroup$

For $k = 2$ the answer is $\frac{\binom{d}{2 d - n}}{\binom{n}{d}} = \frac{\binom{d}{n - d}}{\binom{n}{n - d}}$.

Proof: without loss of generality, we can assume that the first set is $\{ n - d + 1, \dots, n\}$ and the question is now what is the probability that a subset of $\{ 1, \dots, n \}$ of size $d$ contains $\{ 1, \dots, n - d \}$, which is evidently what I said.

Now let us try for $k = 3$. Once again we can assume that the first set is $\{ n - d + 1, \dots, n\}$. Splitting into cases depending on the size of the intersection of the second set with $\{ 1, \dots, n - d \}$ the probability is equal to $$\frac{1}{\binom{n}{d}^2} \sum_{k = 0}^{n - d} \binom{n - d}{k} \binom{d}{d - k} \binom{d + k}{2 d + k - n}$$

In general, one can get a certain multiple sum by splitting into cases depending on the size of the intersection of $A_i$ with the complement of the union of $A_1, \dots, A_{i - 1}$, but for $k > 2$ it doesn't appear to give an expression simpler than the one in Iosif's answer.

$\endgroup$
0
$\begingroup$

The case of $d=1$ is the classic coupon collector's problem . Of course inclusion exclusion applies, but it does not give an answer one can do much with. The expected number of selections until everything is covered has a nice expression. Oversimplifying quite a bit, the expected number of trials is around $n \ln{n}$. The probability of succeeding with $n\ln{n}+cn$ selections converges to $e^{-e^{-c}}$ so about $87\%$ and $95\%$ for $c=2$ and $c=3.$

You could study what was done there and see what you can do for $d>1.$

The probability of succeeding with $k$ $d$-sets is better than the probability of succeeding with $kd$ $1$-sets. So that gives bounds. For small $d$ and large $n$ they might be close.

$\endgroup$

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.