Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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

share|improve this answer

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$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.