7
$\begingroup$

Sorry if this appears to be a naive question! I have three overlapping sets and I want to find the probability of finding a larger/greater intersection for 'A intersect B intersect C' (in the example below, I want to find the probability of finding more than 135 elements that are common in sets A, B & C). For a two set problem, I guess I would do a Fisher or chi-square test. Here is what I have attempted so far:

### Prepare a 3 way contingency table:
mytable <- array(c(135,116,385,6256,
                   48,97,274,9555),
                 dim = c(2,2,2),
                 dimnames = list(
                    Is_C = c('Yes','No'),
                    Is_B = c('Yes','No'),
                    Is_A = c('Yes','No')))

## test
mantelhaen.test(myrabbit, exact = TRUE, alternative = "greater")

Is this the right test (alongwith the current parameters) to determine what I want or is there a more appropriate test for this?

$\endgroup$
6
  • $\begingroup$ Please tell us how these sets arise: without such information, we cannot determine an appropriate probability model and the question will not have any objective answers. $\endgroup$
    – whuber
    Mar 12 '13 at 15:59
  • 1
    $\begingroup$ Thank you. (1) Are the sets drawn with or without replacement? (Obviously replacement occurs in between construction of the individual sets, for otherwise a null intersection would be assured.) (2) Presumably you want an answer in terms of the sizes of the sets or the sizes of the samples, right? (3) Evidently this is a model for some kind of data collection problem. Could you tell us about the data? $\endgroup$
    – whuber
    Mar 14 '13 at 15:16
  • 2
    $\begingroup$ 1) No replacement within a draw. 2) Answer would be a probability of getting more than 135 balls that are common to all three drawings 3) The data is for significance of certain genes, but since that would add another layer of complication, I'd prefer to leave that out for now ;) Thanks for the replies! $\endgroup$
    – user21891
    Mar 14 '13 at 15:30
  • 1
    $\begingroup$ OK. Just to make sure your question is answerable, then, it is essential that you know the total number of balls in the urn and that you know the sizes of the three sets. I am guessing from your R example that you know the latter, but can you verify that you also know the former? $\endgroup$
    – whuber
    Mar 14 '13 at 15:57
  • 1
    $\begingroup$ Correct, the sizes of the three sets are known, and the total number of balls in the urn are also known. $\endgroup$
    – user21891
    Mar 14 '13 at 19:10
5
$\begingroup$

Let there be $n$ elements total with $a$, $b$, and $c$ in the subsets. Consider $N$ already partitioned into $A$ and $N-A$.

The number of ways in which a $b$-element set can be drawn which has $l$ elements in common with $A$ is equal to the number of $l$-element subsets of $A$ times the number of $b-l$ element subsets of $N-A$:

$$\binom{a}{l}\binom{n-a}{b-l}.$$

Ensuant to that, the number of ways in which a $c$-element set can be drawn which has $m$ elements in common with $A\cap B$ is the number of $m$-element subsets of $A\cap B$ times the number of $c-m$-element subsets of $N-(A\cap B)$:

$$\binom{l}{m}\binom{n-l}{c-m}.$$

The total number of such choices of $B$ and $C$ is

$$\binom{n}{b}\binom{n}{c}$$

and they are all equally likely. Summing over the possible values of $l$ gives the probability that the mutual intersection $A\cap B\cap C$ has exactly $m$ elements:

$$\Pr(m) = \frac{1}{\binom{n}{b} \binom{n}{c}}\sum _{l}\binom{a}{l} \binom{n-a}{b-l} \binom{l}{m} \binom{n-l}{c-m}.$$

(The sum extends over all values of $l$ that make sense; by defining $\binom{u}{v}=0$ whenever $v\lt 0$ or $v \gt u$, we do not need to indicate explicit endpoints.)


For instance, here is a plot of the central part of the probability distribution (comprising $99.99$% of the total) for $n=500, a=260, b=320, c=430$:

Figure of PDF

By summing these values from a particular value $m_0$ on up, we obtain the probability that the cardinality of the triple intersection equals or exceeds $m_0$.

In many practical applications, a Normal approximation to this sum works well. As a demonstration, here are the log ratios of the true probabilities to those obtained with a Normal approximation. (The Normal approximation uses the true mean $\mu$ and standard deviation $\sigma$ and estimates the probability of $m$ as $\Phi(\frac{m+1/2-\mu}{\sigma}) - \Phi(\frac{m-1/2-\mu}{\sigma})$ where $\Phi$ is the standard Normal CDF.)

Residuals

The mean is near $143$ and the SD is near $5.9$. (As usual, these are computed by summing $m$ and $m^2$, as weighted by the probabilities, to obtain the raw first and second moments, etc. I have not found a way to estimate either value a priori using simple formulas, but they can be estimated by computing probabilities for a small carefully-chosen selection of values of $m$ and fitting a Normal curve to them.) Evidently, the approximation is excellent (in this case) within one SD of the mean, after which it starts decreasing, but even at three SD from the mean (i.e., around $125$ or $161$) it is still within one or two percent of the correct value. For instance, the Normal approximation suggests the chance that $m \le 135$ is $0.939$ whereas the correct value is $0.928$.

In cases where there is a narrow range of possibilities of $m$, the distribution is far from Normal--but fortunately then the summations are short. For instance, here is the distribution for $n=145, a=b=c=140$:

Probabilities

A simulation of $10^5$ independent instances of this situation tallies closely:

Bar chart

$\endgroup$
3
  • $\begingroup$ Whoa!! Thanks whuber!! It'll take me a little while to get through this completely, but thanks for taking the time and trouble!! $\endgroup$
    – user21891
    Mar 16 '13 at 12:47
  • $\begingroup$ Thank you for such a detailed answer. I am wondering if you can elaborate more on how to iterate over l to get the sum ? I saw your another post where you iterate until min(n1,k) for two sets overlap case [stats.stackexchange.com/questions/14643/….. I am wondering how to iterate l in this scenario. And also Pr(m) would be be Pr(overlap >=m)? $\endgroup$ May 30 '17 at 23:27
  • $\begingroup$ Is there a name for this test? $\endgroup$
    – kmace
    Dec 29 '17 at 10:22

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.