<p>We can write an exact expression for the probability as a single sum using inclusion-exclusion. This sum has terms which can oscillate wildly in magnitude, so some care needs to be taken to evaluate it if you don't use exact arithmetic.</p>

<p>There are $M \choose j$ sets of size $j$. The probability that there are $j$ elements chosen is $M \choose j$ times the probability that the first $j$ elements are chosen.</p>

<p>The probability that all elements chosen are contained in a particular set of size $S$ is easy to compute. It is $\left({S \choose N} \bigg/ {M\choose N} \right)^k$. So, by inclusion-exclusion, the probability that the union of the sets is exactly $\lbrace 1, ..., j \rbrace,$ is</p>

<p>$$\sum_{S \subset \lbrace 1, ..., j \rbrace}  (-1)^{j-|S|} \left( \frac{|S| \choose N}{M\choose N} \right)^k = \sum_{s \le j} (-1)^{j-s} {j\choose s} \left( \frac{s \choose N}{M\choose N} \right)^k.$$</p>

<p>So, the probability that the union of sets has size exactly $j$ is </p>

<p>$$\frac{M \choose j}{{M \choose N}^k} \sum_{s \le j} (-1)^{j-s} {j \choose s}{s \choose N}^k. $$</p>

<p>For example, suppose $M=100$ and we choose $15$ items $5$, $3$, or $1$ at a time, and ask for the probability that the union has size $10$. The probability if you choose the items $5$ at a time is </p>

<p>$$0.000649139 -0.000811423 +0.000320562 - 0.0000450791 + 1.83996\times10^{-6} -1.0222\times 10^{-8}$$</p>

<p>which totals $\frac{256,593,727}{2,230,700,774,400} = 0.000115028.$ The probability if you choose $5$ sets of $3$ distinct elements is $0.000342819.$ The probability if you choose $15$ elements individually is $0.000795413.$</p>

CC BY-SA 3.0
2014-09-04T10:21:45.753Z
Thanks for your answer. I actually obtained another expression for this probability by representing the union as a concatenation of pair-wise unions, using a Markov formulation which is an extension of the balls and bins process.
MJK
CC BY-SA 3.0
2014-09-04T10:43:30.750Z
@MJK: I'm not sure what you mean. Are you using dynamic programming, calculating the probability of each possible size of union for up to $k$ sets? If you mean something else, you might want to post it as an answer, too.
Douglas Zare
CC BY-SA 3.0
2014-09-03T13:44:19.103Z
2014-09-03T13:44:19.103Z
Douglas Zare
<p>For very crude bounds, you could use Chebyshev's inequality.</p>

<p>Let $x$ denote one (fixed) value from the set of $M$ possibilities.  The probability that $x$ appears at least once in the union of the sets is something like</p>

<p>$$p = 1 - \left({{M-1 \choose N} \over {M \choose N}}\right)^k.$$</p>

<p>Now if we let the random variable $X$ denote the number of elements that appear at least once in the union of the sets, we can use linearity of expectation to get that $\mathbb{E}[X] = Mp$.  You should be able to compute $\text{Var}[X]$ using similar methods.  Then, you should be able to use Chebyshev's inequality to bound the probability that $X$ is far away from its expected value.</p>

<p>This will give a pretty weak bound, so it's unlikely that this is the best approach.  Hopefully others will suggest better methods.</p>

CC BY-SA 3.0
2013-08-01T23:56:06.243Z
2013-08-02T00:04:44.897Z
2013-08-02T00:04:44.897Z
D.W.
<p>Using @András' formulation:</p>

<p><em>In an <span class="math-container">$N$</span>-uniform hypergraph over <span class="math-container">$M$</span> vertices, what is the probability that <span class="math-container">$k$</span>
 edges chosen at random (assuming with repeats) cover at least <span class="math-container">$j$</span> vertices?</em></p>

<p>Consider first the case <span class="math-container">$N=1$</span>.  Then the question is, if you throw <span class="math-container">$k$</span> balls randomly (one at a time) into <span class="math-container">$M$</span> bins, what is the distribution of the number of non-empty bins?  Although you can say a lot about this distribution (e.g., its expectation is <span class="math-container">$M-M(1-1/M)^k$</span>), I don't think there is a clean closed form.  If I needed to, say, bound the probability of deviating from the expectation by much, I would probably resort to Chernoff bounds.</p>

<p>Chernoff bounds can also be applied to your general problem.  (Let <span class="math-container">$X_i$</span> be a random indicator variable for the event that vertex <span class="math-container">$i$</span> is covered (<span class="math-container">$1\le i\le M$</span>).  Let <span class="math-container">$X=\sum_i X_i$</span> be the number of covered vertices.  The expectation of each <span class="math-container">$X_i$</span> (the probability that vertex <span class="math-container">$i$</span> is covered) is <span class="math-container">$1-(1-N/M)^k$</span>, so the expectation of <span class="math-container">$X$</span> is <span class="math-container">$\mu = M(1-(1-N/M)^k)$</span>. <span class="math-container">$X$</span> is a sum of 0/1-random variables.  These variables are negatively correlated --- conditioning on some vertices being covered only makes it less likely that any other given vertex is covered.  So standard Chernoff bounds apply (<a href="https://cstheory.stackexchange.com/questions/39059/chernoff-bound-for-negatively-correlated-variables">reference</a>].)</p>

<p>To get an intuition for your problem, I suppose I would first consider how the case with <span class="math-container">$j$</span> edges of size <span class="math-container">$N$</span> compares to the case with <span class="math-container">$Nj$</span> edges of size 1.  In the former case, you expect fewer uncovered vertices, but by how much?  The ratio of the expected number of uncovered vertices in the former case over the expected number in the latter case is</p>

<p><span class="math-container">$$\frac{M(1-N/M)^k}{M(1-1/M)^{kN}}
= \Big(\frac{1-N/M}{(1-1/M)^{N}}\Big)^k
\approx \big(\exp(N/M)(1-N/M)\big)^k
= \big(1-\frac{1}{2}(N/M)^2 - O(N/M)^3\big)^k
= \exp(-\Theta(k(N/M)^2)).$$</span></p>

<p>which is small when <span class="math-container">$k \ge (M/N)^2$</span>.</p>

CC BY-SA 4.0
2019-02-18T23:35:19.240Z
2019-02-18T23:35:19.240Z
Neal Young
<p>Say that we have $k$ sets, each with cardinality $N$, where the elements in each set are taken at random from $M \ge N$ possible ones. The elements in each set are known to be distinct.</p>

<p>What is the probability that $j$ ($j=1,...,M$) elements appear at least once in the (union of the) sets?</p>

<p>We know that for $j = N$ the probability is $1$. For $j &gt; N$ I wanted to use the binomial distribution, but the parameter $p$ should be conditioned somehow on the number of elements that already appear in the sets. Should I use some recursive formula for this?</p>

<p><strong>Edit</strong>:</p>

<p>(1) This maybe also be formulated as the famous balls in bins problem, with the twist that the balls are thrown $N$ at a time to $M$ bins, where it is known that each group of $N$ balls falls into <strong>distinct</strong> $N$ bins.</p>

<p>(2) Another option to see this is as the (extended) Coupon Collector's Problem, who acquires $N$ (instead of $1$) distinct coupons at a time, from a set of $M$ distinct coupons. Denoting by $W_t(j)$ the probability that he acquired $j$ distinct coupons at time $t$, my questions is what is the probability distribution of $W_t(j)$, for $j=N,N+1,...,M$, for each time (or set in the original formulation) $t=1,2,...,k$. I saw something relevant here:
<a href="https://math.stackexchange.com/questions/100175/probability-of-non-empty-bins-after-randomly-inserting-balls-by-pairs">https://math.stackexchange.com/questions/100175/probability-of-non-empty-bins-after-randomly-inserting-balls-by-pairs</a></p>

CC BY-SA 3.0
2013-08-01T08:18:15.897Z
This is not correct:  for $j\le N$ the probability is 1.  It's not well-defined for $j< N$.  Anyway, this question seems off-topic.
Yixin Cao
CC BY-SA 3.0
2013-08-01T08:24:45.033Z
@Yixin, you probably meant for $j=N$. I corrected it.
This problem is a sub-problem of some work I'm doing on graphs.
MJK
CC BY-SA 3.0
2013-08-01T18:34:45.500Z
I don't at all see why this would be viewed as off topic. We frequently have balls-and-bins questions: I myself have asked one that was upvoted.
Suresh Venkat
CC BY-SA 3.0
2013-08-01T22:59:00.187Z
I'm not sure whether I understand the problem yet.  Let the random variable $X$ denote the number of elements that appear at least once in the union of the sets.  Are you asking us to compute $\Pr[X=j]$, or $\Pr[X\ge j]$?
D.W.
CC BY-SA 3.0
2013-08-02T09:00:10.917Z
@D.W., I'm looking for $Pr[X=j]$. I added another formulation in terms of the (extended) CCP.
MJK
CC BY-SA 3.0
2013-08-02T21:26:31.323Z
Another formulation: in an $N$-uniform hypergraph over $M$ vertices, what is the probability that $k$ edges chosen at random (with or without repeats, it is not clear from the question) cover at least $j$ vertices?
András Salamon
<pr.probability><combinatorics>
Probability for an element to appear in at least one set
MJK
# Probability for an element to appear in at least one set

(Asked by: username_0 on 2013-08-01)

Say that we have $k$ sets, each with cardinality $N$, where the elements in each set are taken at random from $M \ge N$ possible ones. The elements in each set are known to be distinct.

What is the probability that $j$ ($j=1,...,M$) elements appear at least once in the (union of the) sets?

We know that for $j = N$ the probability is $1$. For $j > N$ I wanted to use the binomial distribution, but the parameter $p$ should be conditioned somehow on the number of elements that already appear in the sets. Should I use some recursive formula for this?

**Edit**:

(1) This maybe also be formulated as the famous balls in bins problem, with the twist that the balls are thrown $N$ at a time to $M$ bins, where it is known that each group of $N$ balls falls into **distinct** $N$ bins.

(2) Another option to see this is as the (extended) Coupon Collector's Problem, who acquires $N$ (instead of $1$) distinct coupons at a time, from a set of $M$ distinct coupons. Denoting by $W\_t(j)$ the probability that he acquired $j$ distinct coupons at time $t$, my questions is what is the probability distribution of $W\_t(j)$, for $j=N,N+1,...,M$, for each time (or set in the original formulation) $t=1,2,...,k$. I saw something relevant here:
<https://math.stackexchange.com/questions/100175/probability-of-non-empty-bins-after-randomly-inserting-balls-by-pairs>

**Tags:** pr.probability, combinatorics

> **Comments:**
> **username_1**: This is not correct:  for $j\le N$ the probability is 1.  It's not well-defined for $j< N$.  Anyway, this question seems off-topic.  
> **username_0**: @Yixin, you probably meant for $j=N$. I corrected it. This problem is a sub-problem of some work I'm doing on graphs.  
> **username_2**: I don't at all see why this would be viewed as off topic. We frequently have balls-and-bins questions: I myself have asked one that was upvoted.  
> **username_3**: I'm not sure whether I understand the problem yet.  Let the random variable $X$ denote the number of elements that appear at least once in the union of the sets.  Are you asking us to compute $\Pr[X=j]$, or $\Pr[X\ge j]$?  
> **username_0**: @username_3, I'm looking for $Pr[X=j]$. I added another formulation in terms of the (extended) CCP.  
> **username_4**: Another formulation: in an $N$-uniform hypergraph over $M$ vertices, what is the probability that $k$ edges chosen at random (with or without repeats, it is not clear from the question) cover at least $j$ vertices?  

---

## 3 answers

### Answer by username_5 on 2014-09-03. Score: 2

We can write an exact expression for the probability as a single sum using inclusion-exclusion. This sum has terms which can oscillate wildly in magnitude, so some care needs to be taken to evaluate it if you don't use exact arithmetic.

There are $M \choose j$ sets of size $j$. The probability that there are $j$ elements chosen is $M \choose j$ times the probability that the first $j$ elements are chosen.

The probability that all elements chosen are contained in a particular set of size $S$ is easy to compute. It is $\left({S \choose N} \bigg/ {M\choose N} \right)^k$. So, by inclusion-exclusion, the probability that the union of the sets is exactly $\lbrace 1, ..., j \rbrace,$ is

$$\sum\_{S \subset \lbrace 1, ..., j \rbrace} (-1)^{j-|S|} \left( \frac{|S| \choose N}{M\choose N} \right)^k = \sum\_{s \le j} (-1)^{j-s} {j\choose s} \left( \frac{s \choose N}{M\choose N} \right)^k.$$

So, the probability that the union of sets has size exactly $j$ is

$$\frac{M \choose j}{{M \choose N}^k} \sum\_{s \le j} (-1)^{j-s} {j \choose s}{s \choose N}^k. $$

For example, suppose $M=100$ and we choose $15$ items $5$, $3$, or $1$ at a time, and ask for the probability that the union has size $10$. The probability if you choose the items $5$ at a time is

$$0.000649139 -0.000811423 +0.000320562 - 0.0000450791 + 1.83996\times10^{-6} -1.0222\times 10^{-8}$$

which totals $\frac{256,593,727}{2,230,700,774,400} = 0.000115028.$ The probability if you choose $5$ sets of $3$ distinct elements is $0.000342819.$ The probability if you choose $15$ elements individually is $0.000795413.$

> **Comments:**
> **username_0**: Thanks for your answer. I actually obtained another expression for this probability by representing the union as a concatenation of pair-wise unions, using a Markov formulation which is an extension of the balls and bins process.  
> **username_5**: @username_0: I'm not sure what you mean. Are you using dynamic programming, calculating the probability of each possible size of union for up to $k$ sets? If you mean something else, you might want to post it as an answer, too.  

---

### Answer by username_3 on 2013-08-01. Score: 2

For very crude bounds, you could use Chebyshev's inequality.

Let $x$ denote one (fixed) value from the set of $M$ possibilities. The probability that $x$ appears at least once in the union of the sets is something like

$$p = 1 - \left({{M-1 \choose N} \over {M \choose N}}\right)^k.$$

Now if we let the random variable $X$ denote the number of elements that appear at least once in the union of the sets, we can use linearity of expectation to get that $\mathbb{E}[X] = Mp$. You should be able to compute $\text{Var}[X]$ using similar methods. Then, you should be able to use Chebyshev's inequality to bound the probability that $X$ is far away from its expected value.

This will give a pretty weak bound, so it's unlikely that this is the best approach. Hopefully others will suggest better methods.


---

### Answer by username_6 on 2019-02-18. Score: 0

Using @András' formulation:

*In an $N$-uniform hypergraph over $M$ vertices, what is the probability that $k$
edges chosen at random (assuming with repeats) cover at least $j$ vertices?*

Consider first the case $N=1$. Then the question is, if you throw $k$ balls randomly (one at a time) into $M$ bins, what is the distribution of the number of non-empty bins? Although you can say a lot about this distribution (e.g., its expectation is $M-M(1-1/M)^k$), I don't think there is a clean closed form. If I needed to, say, bound the probability of deviating from the expectation by much, I would probably resort to Chernoff bounds.

Chernoff bounds can also be applied to your general problem. (Let $X\_i$ be a random indicator variable for the event that vertex $i$ is covered ($1\le i\le M$). Let $X=\sum\_i X\_i$ be the number of covered vertices. The expectation of each $X\_i$ (the probability that vertex $i$ is covered) is $1-(1-N/M)^k$, so the expectation of $X$ is $\mu = M(1-(1-N/M)^k)$. $X$ is a sum of 0/1-random variables. These variables are negatively correlated --- conditioning on some vertices being covered only makes it less likely that any other given vertex is covered. So standard Chernoff bounds apply ([reference](https://cstheory.stackexchange.com/questions/39059/chernoff-bound-for-negatively-correlated-variables)].)

To get an intuition for your problem, I suppose I would first consider how the case with $j$ edges of size $N$ compares to the case with $Nj$ edges of size 1. In the former case, you expect fewer uncovered vertices, but by how much? The ratio of the expected number of uncovered vertices in the former case over the expected number in the latter case is

$$\frac{M(1-N/M)^k}{M(1-1/M)^{kN}}
= \Big(\frac{1-N/M}{(1-1/M)^{N}}\Big)^k
\approx \big(\exp(N/M)(1-N/M)\big)^k
= \big(1-\frac{1}{2}(N/M)^2 - O(N/M)^3\big)^k
= \exp(-\Theta(k(N/M)^2)).$$

which is small when $k \ge (M/N)^2$.


---

