Computing the expected value of the Jaccard similarity of two random sets I'm trying to solve the following exercise, I just wanted to know if I'm going in the right direction, and if not maybe a little hint would be appreciated.
Given a universe U of n elements, we randomly generate two sets S and T of size m each. We want to compute the expected value of $J(S,T)$ defined as follows:
$$J(S,T)=\frac{\vert S\cap T\vert }{\vert S \cup T\vert} $$
So we want to compute this:
$$\Bbb E[J(S,T)]=\Bbb E[\frac{\vert S\cap T\vert }{\vert S \cup T\vert}]$$
If the intersection has $k$ elements then we have $2m-k$ distinct elements in the symmetric difference right?
So basically we can see the process we're trying to study as this:


*

*Choose a subset X of $k$ elements from $U$

*S picks all the elements of X

*T picks all the elements of X

*The remaining $2m-k$ elements are picked at random from $U-X$


So I think:
$\Bbb P(\vert S \cap T \vert=k)=\binom{n}{k}(\frac{1}{n})^{2k}(\frac{1}{n-k})^{2m-k} $
Is this correct so far?
 A: You're way off the mark. (To confirm that, either note that these probabilities would be tiny and would never sum to $1$ if you sum over $k$, and/or calculate a few values for small $n$ and $k$.)
To get the right probability, without loss of generality fix $S$, and then calculate the probability of picking $k$ elements for $T$ from $S$ and $m-k$ from $U\setminus S$.
Edit (since a comment contains the wrong probabilities):
Fix $S$ of size $m$ and uniformly randomly pick $T$ of size $m$. The probability of picking $k$ elements from $S$ and $m-k$ elements from $U\setminus S$ is
$$
\frac{\binom mk\binom{n-m}{m-k}}{\binom nm}\;,
$$
so the expected similarity is
\begin{eqnarray}
\mathbb E[J(S,T)]
&=&
\sum_{k=0}^m\frac{\binom mk\binom{n-m}{m-k}}{\binom nm}\frac k{2m-k}\;.
\end{eqnarray}
Wolfram|Alpha expresses this sum in terms of the generalized hypergeometric function, so it probably doesn't have a simpler form than that.
For example, for $n=10$, $m=5$ the result is $\frac{5563}{15876}\approx0.35$, and for $n=2m$ with $m\to\infty$ the result tends to $\frac13$, as it should.
