# Estimating probability of set membership

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

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