5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yixin Cao Aug 1 '13 at 8:18
  • $\begingroup$ @Yixin, you probably meant for $j=N$. I corrected it. This problem is a sub-problem of some work I'm doing on graphs. $\endgroup$ – MJK Aug 1 '13 at 8:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Aug 1 '13 at 18:34
  • $\begingroup$ 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]$? $\endgroup$ – D.W. Aug 1 '13 at 22:59
  • $\begingroup$ @D.W., I'm looking for $Pr[X=j]$. I added another formulation in terms of the (extended) CCP. $\endgroup$ – MJK Aug 2 '13 at 9:00
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – MJK Sep 4 '14 at 10:21
  • $\begingroup$ @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. $\endgroup$ – Douglas Zare Sep 4 '14 at 10:43
0
$\begingroup$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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