0
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ In other words, you are setting up a game of Mastermind with sets rather than strings. $\endgroup$
    – Jason Dyer
    Nov 18, 2009 at 14:19
  • $\begingroup$ 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? $\endgroup$ Nov 18, 2009 at 14:20
  • $\begingroup$ 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. $\endgroup$
    – S. Carnahan
    Nov 18, 2009 at 15:44
  • $\begingroup$ Jonah: I mean that I know which A_i x is an element of and which ones it isn't. $\endgroup$ Nov 18, 2009 at 21:23
  • $\begingroup$ 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. $\endgroup$ Nov 18, 2009 at 21:28

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I just edited the question to try and make it clearer that what I'm looking for is an estimate. $\endgroup$ Nov 19, 2009 at 0:01
  • 1
    $\begingroup$ 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$. $\endgroup$ Nov 19, 2009 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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