Skip to main content
corrected
Source Link
Emolga
  • 260
  • 2
  • 7

We permute all the elements of $A \cup B \cup C$ and denote by $p_{A,B}$ the probability that the first element of the permutation that is in $A$ or $B$ is not in $B$both. This probability is equal to $1-\frac{A \cap B}{A \cup B}$, which is the Jaccard distance, because we look at the first element which is in $A \cup B$ and the probability that it is in both sets is $\frac{A \cap B}{A \cup B}$.

Now we are only left to prove that $p_{A,B}+p_{B,C} \geq p_{A,C}$. That's true because if the first element of the permutation that is in $A$ is in index $i(A) \neq i(C)$, then it means that $i(A) \neq i(B)$ or $i(B) \neq i(C)$.

We permute all the elements of $A \cup B \cup C$ and denote by $p_{A,B}$ the probability that the first element of the permutation that is in $A$ is not in $B$. This probability is equal to $1-\frac{A \cap B}{A \cup B}$, which is the Jaccard distance, because we look at the first element which is in $A \cup B$ and the probability that it is in both sets is $\frac{A \cap B}{A \cup B}$.

Now we are only left to prove that $p_{A,B}+p_{B,C} \geq p_{A,C}$. That's true because if the first element of the permutation that is in $A$ is in index $i(A) \neq i(C)$, then it means that $i(A) \neq i(B)$ or $i(B) \neq i(C)$.

We permute all the elements of $A \cup B \cup C$ and denote by $p_{A,B}$ the probability that the first element of the permutation that is in $A$ or $B$ is not in both. This probability is equal to $1-\frac{A \cap B}{A \cup B}$, which is the Jaccard distance, because we look at the first element which is in $A \cup B$ and the probability that it is in both sets is $\frac{A \cap B}{A \cup B}$.

Now we are only left to prove that $p_{A,B}+p_{B,C} \geq p_{A,C}$. That's true because if the first element of the permutation that is in $A$ is in index $i(A) \neq i(C)$, then it means that $i(A) \neq i(B)$ or $i(B) \neq i(C)$.

Source Link
Emolga
  • 260
  • 2
  • 7

We permute all the elements of $A \cup B \cup C$ and denote by $p_{A,B}$ the probability that the first element of the permutation that is in $A$ is not in $B$. This probability is equal to $1-\frac{A \cap B}{A \cup B}$, which is the Jaccard distance, because we look at the first element which is in $A \cup B$ and the probability that it is in both sets is $\frac{A \cap B}{A \cup B}$.

Now we are only left to prove that $p_{A,B}+p_{B,C} \geq p_{A,C}$. That's true because if the first element of the permutation that is in $A$ is in index $i(A) \neq i(C)$, then it means that $i(A) \neq i(B)$ or $i(B) \neq i(C)$.