MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a number of discrete finite sets, $A_0$ through $A_n$. I do not actually know their contents, but I know the size of each set and the size of the intersection between $A_0$ and each of the other sets.

If necessary, I can also know the size of the "universe" - ie: how many elements exist in total (it's finite, though large), though I'd prefer to not use this information if possible. Let's call that value $N$.

Given the above, and the set of sets $A_1$ through $A_n$ that some element $x$ is a member of, how can we estimate the probability that $x$ is a member of $A_0$? Please state additional assumptions if you need to make any. For example, it may be reasonable to assume that the individual sets $A_1$ through $A_n$ are independent (ie: membership or lack therof in one of those sets does not affect the probability membership in any of the other sets, except $A_0$).

share|cite|improve this question
In other words, you are setting up a game of Mastermind with sets rather than strings. – Jason Dyer Nov 18 '09 at 14:19
In the last paragraph, do you mean that x is a member of each A_i, or that you know which A_i x is an element of and which ones it isn't? – Jonah Ostroff Nov 18 '09 at 14:20
Are we assuming X is chosen from the union of A_i with uniform probability? Even if so, we can only put bounds on the probability, since we don't seem to know the sizes of the intersections between the other sets. – S. Carnahan Nov 18 '09 at 15:44
Jonah: I mean that I know which A_i x is an element of and which ones it isn't. – Laurence Gonsalves Nov 18 '09 at 21:23
Scott: That is correct: I don't have the sizes of the intersections between the other sets. That's why I mentioned the possibility of additional assumptions. – Laurence Gonsalves Nov 18 '09 at 21:28

Let $A=\cup_{0\le i\le n} A_i$ be the universe. Given $x\in A$, let $I_x$ be the set on indices between $1$ and $n$ such that $x\in A_i$. Note that if $i\notin I_x$, then $x\in A_i^c$, where $E^c$ denotes the complemet of the set $E$ in $A$. Then what you are asking for is the probability that $x\in A_0$ conditioned to the fact that $$ x\in \(\cap_{i\in I_x} A_i\)\cap\(\cap_{i\notin I_x} A_i^c\). $$ Denoting by $|E|$ the cardinal of a set $E$, this is given by $$ \frac{|A_0\cap\(\cap_{i\in I_x} A_i\)\cap\(\cap_{i\notin I_x} A_i^c\)|}{|\(\cap_{i\in I_x} A_i\)\cap\(\cap_{i\notin I_x} A_i^c\)|}. $$ If I understand your question, you know $|A_i|$, $|A_0\cap A_i|$ for $1\le i\le n$, and $|A|$. This is not enough to compute the desired probability.

share|cite|improve this answer
I just edited the question to try and make it clearer that what I'm looking for is an estimate. – Laurence Gonsalves Nov 19 '09 at 0:01
Consider the case $n=2$, and assume that we know that $x\in A_1\cap A_2$ (no loss of generality if we know N). Given positive integers $n_i$, $i=0,1,2$, $n_{0,i}$, $i=1,2$ and $N$ such that $n_{0,i}\le n_i$, $i=1,2$ and $n_0+n_1+n_2-N-n_{0,1}-n_{0,2}=z\ge0$, for any integer $y$ such that $0\le y\le \min(n_{0,1},n_{0,2})$ there exists sets $A_i$ such that $|A_i|=n_i$, $|A_0\cap A_i|=n_{0,i}$, $|A_0\cup A_1\cup A_2|=N$ and the probability that $x\in A_0$ is equal to $y/(y+z)$. For the same data, we have a wide range of possible answers. Something similar must happen for larger $n$. – Julián Aguirre Nov 19 '09 at 15:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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