# Expected intersection between a random set and a collection of random sets

I suspect this question has been posted but I'm unable to find it because I'm not a stats person and might not be using the right terms to search.

A is a set of X random numbers. I have Y other sets of random numbers that are the same size as A. I will create a union, Z, from N members of Y and then measure the intersection between A and Z.

I'd like a formula that expresses the expected intersection of A and Z as a percentage of A.

• You'll need to specify how large the sets are, how large the population from which the elements are drawn is, and how the elements of the sets are selected. For example, if the underlying population is the set of reals, the size of $A$ etc. is $5$, and elements are selected by independent sampling from a Normal distribution, you'll never get coverage of $A$ (with probability $1$) no matter how many other sets you draw. Commented Oct 1, 2018 at 17:41
• Wouldn't the size of A and the size of the population from which its entries are drawn be part of the equation? In practice, A is ~20,000 entries drawn from a population of 2 x 10^8.
– blue
Commented Oct 1, 2018 at 17:57
• Ah, for some reason (not enough coffee, perhaps) I thought you were asking for a numerical result, not a formula. My bad. Commented Oct 1, 2018 at 18:03
• Did you mean to write "union" instead of "intersection" in this question?
– whuber
Commented Oct 1, 2018 at 18:09
• whuber: Thanks for the feedback. I edited the post and hope it's clearer now.
– blue
Commented Oct 1, 2018 at 18:35

There are multiple formulas, depending on how the random numbers are selected, but they all have much in common.

In any case, we can describe all samples by means of suitable collections of random variables. Index the elements of the population with the integers $$j = 1, 2, \ldots, n$$ in such a way that $$A$$ consists of those with indexes $$1$$ through $$m.$$ Let $$\mathcal Y$$ be a collection of $$s$$ additional samples of size $$m,$$ written

$$\mathcal Y = \{Y_1, Y_2, \ldots, Y_s\}.$$

For $$1 \le i \le s$$ and $$1 \le j \le n,$$ define the random variable $$X_{ij}$$ to equal $$1$$ when $$j$$ is in $$Y_{ij}.$$ Using the notation of indicator functions $$\mathcal I,$$ this is

$$X_{ij} = \mathcal{I}(j\in Y_i).$$

Consider an element $$j\in A.$$ It is not in the union $$\bigcup \mathcal Y$$ if and only if $$X_j = \max_{1\le i \le s} X_{ij} = 0;$$ that is, $$X_{ij}=0$$ for all $$i.$$

At this point we need to consider how the samples were obtained. Let $$\pi_{ij}$$ be the probability that $$j \notin Y_i.$$ Assuming the samples in $$\mathcal Y$$ were taken independently of each other means these probabilities multiply:

$$\Pr(X_{1j}=X_{2j}=\cdots=X_{sj}=0) = \pi_{1j}\pi_{2j}\cdots\pi_{sj} = \prod_{i=1}^s \pi_{ij} = \pi_j.$$

(The last equation defines $$\pi_j.$$)

Thus,

$$\Pr(j \in \bigcup \mathcal Y) = 1 - \pi_j,$$

whence

$$E(X_{j}) = \Pr(j \notin \bigcup \mathcal Y)\times 0 + \Pr(j \in \bigcup \mathcal Y)\times 1 = 1 - \pi_j.$$

The number of elements in $$\bigcup \mathcal Y$$ common to $$A$$ is just the sum of the $$X_j$$ for $$j=1,2,\ldots, m,$$ whence the expectation of this number is

$$E\left(\left| A \cap \bigcup \mathcal Y \right|\right) = \sum_{j=1}^m E(X_j) = \sum_{j=1}^m 1 - \pi_j.$$

Let's now make some more restrictive assumptions: assume all $$Y_i$$ were obtained in a similar fashion and that all elements of the population have equal chances $$p$$ of being included. This implies all the $$\pi_i$$ are equal to a common value $$(1-p)^s.$$ The foregoing simplifies to

$$\sum_{j=1}^m 1 - \pi_j = m(1-(1-p)^s).$$

Dividing by $$m = \left| A \right|$$ gives the answer as

$$\frac{E\left(\left| A \cap \bigcup \mathcal Y \right|\right)}{\left| A \right|} = 1-(1-p)^s.$$

I'll give two explicit values to cover standard sampling schemes.

• For sampling with replacement, $$p = m/n.$$

• For sampling without replacement, $$p = 1-\left(1 - 1/n)\right)^m \approx 1-e^{-m/n}.$$

The last approximation is excellent when $$sm \ll n.$$