Jaccard Similarity - From Data Mining book - Homework problem 
Exercise 3.1.3 : Suppose we have a universal set U of n elements, and
  we choose two subsets S and T at random, each with m of the n
  elements.
What is the expected value of the Jaccard similarity of S
  and T ?

I am reading the book 
http://infolab.stanford.edu/~ullman/mmds/ch3.pdf
 A: The above answer assumes that an element in $T$ may be repeated several times in $S$ (i.e. $S$ and $T$ are not sets but multisets); else the probability will not be $m/n$ uniformly.
I expect the answer should be more along the following lines:-
Let the number of common elements between $S$ and $T$ be $k$.
Then, as mentioned by ack_inc in the comment to his answer, Jaccard similarity $Sim(S,T)=k/(2m-k)$.
Now, $Pr(Sim(S,T)=k/(2m-k))$ will be $\dfrac{{m\choose {k}} {n-k\choose m-k}}{n\choose m}$ since there are $n$ total elements, of which $m$ are in $S$ and $k$ are common. So the number of ways we can choose $m$ elements for $T$ is given by ${m \choose k}$ (choosing the $k$ common elements from $S$) times ${n-m\choose m-k}$ (choosing remaining $m-k$ elements from $n-k$ elements).
Thus,
$E(Sim(S,T))=\sum_{k=0}^{m} \dfrac{k}{2m-k} \dfrac{{m\choose {k}} {n-m\choose m-k}}{n\choose m}$.
However, simplifying the above expression is beyond my limited knowledge of combinatorial identities. If anyone can do so, kindly update the answer.
A: I'm posting an alternative solution.
Jaccard similarity of two sets $S$ and $T$ is defined as the fraction of elements these two sets have in common, i.e. $\text{sim}(S,T)=|S\cap T|/|S\cup T|$. Suppose we chose $m$-element subsets $S$ and $T$ uniformly at random from an $n$-element set. What is the expected Jaccard similarity of these two sets? Suppose the $|S\cap T|=k$ for some $0\le k\le m$. Notice that for the first set, $S$, we have $\binom{n}{m}$ choices, while for $T$ we have $\binom{m}{k}\binom{n-m}{m-k}$ choices, because $k$ elements must be from $S$ and $m-k$ elements must not be from $S$. This gives us $$\Pr[|S\cap T|=k]=\frac{\binom{m}{k}\binom{n-m}{m-k}}{\binom{n}{m}},$$ meaning that $$\text{E}[\text{sim}(S,T)]=\sum_{k=0}^m\frac{\binom{m}{k}\binom{n-m}{m-k}}{\binom{n}{m}}\frac{k}{2m-k}.$$ Even though $\text{E}[|S\cap T|/|S\cup T|]\neq\text{E}[|S\cap T|]/\text{E}[|S\cup T|]=m/(2n-m)$, this expression seems to give good approximation.
Thanks to Mitja Trampus for pointing out an alternate solution, with $$\Pr[|S\cap T|=k]=\binom{m}{k}\frac{\binom{m}{k}}{\binom{n}{k}}\frac{\binom{n-m}{m-k}}{\binom{n}{m}},$$
giving the following expression:
$$\text{E}[\text{sim}(S,T)]=\sum_{k=0}^m\binom{m}{k}\frac{\binom{m}{k}}{\binom{n}{k}}\frac{\binom{n-m}{m-k}}{\binom{n}{m}}\frac{k}{2m-k}.$$
(The above expressions are, of course, equivalent.)
EDIT: Regarding the simplification, perhaps applying the following identity (from Aigner's book, page 13) could work: $$\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}.$$
A: Each item in T has an $\frac{m}{n}$ chance of also being in S. The expected number of items common to S & T is therefore $\frac{m^2}{n}$.
Exp. $\text{Jaccard Similarity} = \dfrac{\text{No. of common items}}{\text{Size of T} + \text{Size of S} - \text{Number of common items}} = \dfrac{m}{2n - m}$ (after simplification.)
A: I agree with blazs answer - just want to add a small correction (credit to another guy in the course who pointed it out).
The summation does not start at 0. (you'll see it if you make n=100 and m=99)
$$
\text{E}[\text{sim}(S,T)]=\sum_{k=max(0, 2m-n)}^m\binom{m}{k}\frac{\binom{m}{k}}{\binom{n}{k}}\frac{\binom{n-m}{m-k}}{\binom{n}{m}}\frac{k}{2m-k}.
$$
A: I just want to add the following:
As pointed out, ack_inc's answer is not correct and can serve only as an approximation. Also, the lower bound should be $\max\{0, 2m - n\}$ instead of $0$, as GM1313 mentions.
I needed to compute the similarities for $1\leq m\leq n$ where $n = 5000$ or even bigger, so computing all the probabilities $P_{n, m}[|S\cap T| = k]$ (blindly following the definition)


*

*takes a lot of time,

*gives wrong results due to floating-point arithmetics, e.g., $p = 0.0$.


Therefore, I used the fact that ${a \choose b + 1} = \frac{a - b}{b + 1}{a \choose b}$ to speed up the process, and compute the probabilities recursively, starting with the biggest one.
I also used the approximation $m / (2n - m)$ and actually, it is really good, especially for larger values of $n$ (curves for $n\in\{20, 100, 5000\}$):



