Why is the Kendall tau distance a metric?

So I am trying to see how the Kendall $\tau$ distance is considered a metric; i.e. that it satisfies the triangle inequality.

The Kendall $\tau$ distance is defined as follows:

$$K(\tau_1,\tau_2) = |(i,j): i < j, ( \tau_1(i) < \tau_1(j) \land \tau_2(i) > \tau_2(j) ) \lor ( \tau_1(i) > \tau_1(j) \land \tau_2(i) < \tau_2(j) )|$$

Thank you in advance.

-

2 Answers

Consider three lists $\tau_1,\tau_2$ and $\tau_3$. Then we want to show that $K(\tau_1, \tau_3) \leq K(\tau_1, \tau_2) + K(\tau_2, \tau_3)$. The number of disagreements between $\tau_1$ and $\tau_3$ could be independent of the number of disagreements between $\tau_1$ and $\tau_2$ and $\tau_2$ and $\tau_3$. For example, consider $\tau_1$: height, $\tau_2$: weight and $\tau_3$: hair count. The number of disagreements between $\tau_1$ and $\tau_3$ would be no greater than the number of disagreements between $\tau_1$ and $\tau_2$ and $\tau_2$ and $\tau_3$.

-
Did you intend "..would be smaller than the number" to actually be "..will be no greater than the number..." in the last sentence ? – Sasha Dec 12 '11 at 20:42
@Sasha: Yes, corrected. – Robert Dec 12 '11 at 20:43

Kendall tau rank distance is a metric only if you compare ranking of the elements.

If you perform Kendall function comparing elements you will find cases where the triangular inequality does not work.

Example:

0    0    0   10   10   10


and

5 5 5 0 0 0

scores 9 (using Kendall comparing elements)

While

0    0    0   10   10   10


and

5 3 5 7 5 2

scores 3

and

5 3 5 7 5 2

and

5 5 5 0 0 0

scores 4

so 9 > 3 + 4. So triangular inequality is not working here.

But if you operate with the sorting position of each element in it vector (aka ranking) triangular inequality is gauaranteed. This happens beacuase of repetitions of elements within vectors.

We should call "Kendall tau ranking distance" to one of the algorithms and "Kendall tau distance" to the other

Best

Mijael

-