0

The Kendall tau distance between two permutation is the number of index pairs, for which the two permuations disagree in their order: $$K(\alpha, \beta) := |\{(i, j): i < j.\quad [\alpha(i) < \alpha(j) \wedge \beta(i) > \beta(j)] \vee [\alpha(i) > \alpha(j) \wedge \beta(i) < \beta(j)]\}|$$

For computing the Kendall tau distance, Wikipedia mentions the following technique:

Given two rankings $\tau_1, \tau_2$, it is possible to rename the items such that $\tau_1 = (1, 2, 3, \dots)$. Then, the problem of computing the Kendall tau distance reduces to computing the number of inversions in $\tau_2$.

Now let $\alpha = (4, 2, 1, 3)$ and $\beta = (4, 3, 1, 2)$. According to the above definition, $K(\alpha, \beta) = 1$ since only the index pair $(2, 4)$ is a disagreement. However when we use the above technique, we would translate $\beta$ into $(1, 4, 3, 2)$, for which the inversion count is 3. The new $\beta$ is translated using the following mapping, which maps $\alpha$ to the identity permutaion: $4 \to 1, 2\to2, 1\to3, 3\to4$

Now I wonder whether I or the Wikipedia article is wrong? In the latter case, is there still some way to compute the Kendall tau distance in $\mathcal{O}(n \log(n))$ time, i.e. can we still calculate the Kendall tau distance based on inversion counts?

tierriminator
  • 123

1 Answers1

1

The inversion count for $\alpha=(4,2,1,3)$ and $\beta=(4,3,1,2)$ is -as you say- one:

\begin{array}{|cc|cc|cc|c|} \hline \,i & j & \alpha(i) & \alpha(j) & \beta(i) & \beta(j) & \text{count}\,\\ \hline 1 & 2 & 4 & 2 & 4 & 3 & 0\\ 1 & 3 & 4 & 1 & 4 & 1 & 0\\ 1 & 4 & 4 & 3 & 4 & 2 & 0\\ 2 & 3 & 2 & 1 & 3 & 1 & 0\\ 2 & 4 & 2 & 3 & 3 & 2 & 1\\ 3 & 4 & 1 & 3 & 1 & 2 & 0\\ \hline \end{array}

After renaming we have $\alpha=(1,2,3,4)$ and $\beta=(1,4,3,2)$ and get -as yo say- three:

\begin{array}{|cc|cc|cc|c|} \hline \,i & j & \alpha(i) & \alpha(j) & \beta(i) & \beta(j) & \text{count}\,\\ \hline 1 & 2 & 1 & 2 & 1 & 4 & 0\\ 1 & 3 & 1 & 3 & 1 & 3 & 0\\ 1 & 4 & 2 & 4 & 1 & 2 & 0\\ 2 & 3 & 2 & 3 & 4 & 3 & 1\\ 2 & 4 & 2 & 4 & 4 & 2 & 1\\ 3 & 4 & 3 & 4 & 3 & 2 & 1\\ \hline \end{array}

I suspect what they mean is that the permutations in $\alpha$ should be undone, and the same reverse permutations should be applied synchronically to $\beta.$ This gives $\alpha=(1,2,3,4)$ and $\beta=(1,3,2,4)$ which leads to $K(\alpha,\beta)=1:$

\begin{array}{|cc|cc|cc|c|} \hline \,i & j & \alpha(i) & \alpha(j) & \beta(i) & \beta(j) & \text{count}\,\\ \hline 1 & 2 & 1 & 2 & 1 & 3 & 0\\ 1 & 3 & 1 & 3 & 1 & 2 & 0\\ 1 & 4 & 2 & 4 & 1 & 4 & 0\\ 2 & 3 & 2 & 3 & 3 & 2 & 1\\ 2 & 4 & 2 & 4 & 3 & 4 & 0\\ 3 & 4 & 3 & 4 & 2 & 4 & 0\\ \hline \end{array}

Kurt G.
  • 14,198
  • Ah, I see. So basically $K(\alpha, \beta) = K(I, \beta \circ \alpha^{-1})$ (instead of $K(\alpha, \beta) = K(I, \alpha^{-1} \circ \beta)$ what I initially thought). This identity can also easily be proven, as I see, by simply substituting $(i, j)$ with $(\alpha^{-1}(i), \alpha^{-1}(j))$ in the definition. In fact the identity holds for every permutation, not just for $\alpha^{-1}$. – tierriminator Mar 13 '22 at 22:07