Bias in sampling for set intersections Say I have 2 sets, $A$ and $B$ with $n_{A}$ and $n_{B}$ elements respectively, which I assume is known.  I would like to estimate $| A \bigcup B |$ using samples of $\tilde{A} \subset A$ and $ \tilde{B} \subset B$.  
That is if $\tilde{A}$'s elements are uniformly sampled from $A$, and likewise for $\tilde{B}$, will $ \frac{| \tilde{A} \bigcup \tilde{B} |}{| \tilde{A} | + |  \tilde{B} |}$ be an unbiased estimate for  $\frac{| A \bigcup B |}{| A |+|B |}$?  If not, is there some another estimator that will allow me estimate $| A \bigcup B |$ without bias?
 A: $ \frac{| \tilde{A} \bigcup \tilde{B} |}{| \tilde{A} | + |  \tilde{B} |}$ is not an unbiased estimate for  $\frac{| A \bigcup B |}{| A |+|B |}$. Similarly $ \frac{| \tilde{A} \bigcap \tilde{B} |}{| \tilde{A} | + |  \tilde{B} |}$ is not an unbiased estimate for  $\frac{| A \bigcap B |}{| A |+|B |}$.  I think for the intersection you should be using multiplication not addition in the denominator.
To take a simple example, suppose $A=B=A \cap B$ and $n_A=n_B =100$ and you take a sample size $m_\tilde{A}=1$ from $A$ and a sample size $m_\tilde{B}=1$ from $B$.  Then $E\left[\frac{| \tilde{A} \bigcup \tilde{B} |}{| \tilde{A} | + |  \tilde{B} |}\right] = 0.995$  and $E\left[\frac{| \tilde{A} \bigcap \tilde{B} |}{| \tilde{A} | + |  \tilde{B} |}\right] = 0.005$ but $\frac{| A \bigcup B |}{| A |+|B |} =\frac{| A \bigcap B |}{| A |+|B |}= 0.5$.  By contrast $E\left[\frac{| \tilde{A} \bigcap \tilde{B} |}{| \tilde{A} | \times |  \tilde{B} |}\right] = \frac{| A \bigcap B |}{| A |\times |B |}= 0.01.$
The probability an individual element of $A$ is in the sample  $\tilde{A}$ is $\frac{m_\tilde{A}}{n_A}$ and similarly with an individual element of $B$;  the probability that an individual element of $A \cap B$ is in both samples is therefore the product of those probabilities, and the expected number of elements appearing in both samples is $E\left[| \tilde{A} \cap \tilde{B} |\right] = |A\cap B|\frac{m_\tilde{A} m_\tilde{B}}{n_A n_B}$.  So $$\frac{| \tilde{A} \cap \tilde{B} |}{| \tilde{A} | \times |  \tilde{B} |}$$ is an unbiased estimator of $$\frac{| A \cap B |}{| A | \times |B |}$$ and I think this is what you want.  The equivalent statement for the union is more complicated to state but easily calculated in practice.
A: I am replying to this thread half a year late.  I had a similar problem and came up with this calculation.  It's not very rigorous, and I would appreciate another pair of eyes to look through it, but perhaps it can be of some help.  I only estimated the size of the intersection but, as you say, this is equivalent to having an estimate of the union.
