# Prove that the Jaccard Similarity of bags is always less than or equal to 1/2

Prove that the Jaccard Similarity of bags is always less than or equal to 1/2

I know that the Jaccard Similarity of bags is $= \dfrac{|B\cap C|}{|B\cup C|}$ and if the bags are the same then the similarity $=1$

A bag is a set of elements with order unimportant and repetition allowed.

For example if we have bags $B=\{A,B,B,C,C,C,C,D,D\}$ and $C=\{A,A,B,C,C,D,D,D\}$ then the Jaccard Similarity is $=\dfrac{1+1+2+2}{9+8}=\dfrac{6}{17}$

So we count an element n times in the intersection if n is the minimum number of times the element appears in B and C and the size of the union is the sum of the size of the bags.

But how would I prove it is always $\leq \dfrac{1}{2}$

Without loss of generality we can consider bags with only one kind of element. Let $b=|B|, c=|C|$. Then the formula gives $\min(b,c)/(b+c)$ but then $2\min(b,c)\leq(b+c)$. Note that the formula gives $1/2$ if the bags are equal.
• Why is $2min(b,c)\leq(b+c)$? – Sophie Filer May 8 '17 at 9:20
• We know that $\min(b,c)$ is less than both $b$ and $c$ by definition, so twice that is less than the $b+c$. – Somos May 9 '17 at 3:46
$$\dfrac{n_1 + n_2 + n_3 + \cdots + n_N}{d_1 + d_2 + d_3 + \cdots + d_N}$$ where $2n_i \le d_i$ for each $i$.
So $$d_1 + d_2 + d_3 + \cdots + d_N \ge 2(n_1 + n_2 + n_3 + \cdots + n_N)$$.
Hence $$\dfrac{n_1 + n_2 + n_3 + \cdots + n_N}{d_1 + d_2 + d_3 + \cdots + d_N} \le \dfrac 12$$