Kendall tau distance

- group, ∞-group
- group object, group object in an (∞,1)-category
- abelian group, spectrum
- group action, ∞-action
- representation, ∞-representation
- progroup
- homogeneous space

**analysis** (differential/integral calculus, functional analysis, topology)

metric space, normed vector space

open ball, open subset, neighbourhood

convergence, limit of a sequence

compactness, sequential compactness

continuous metric space valued function on compact metric space is uniformly continuous

…

…

The *Kendall tau distance* between two permutations is the minimum number of transpositions (swaps) of *adjacent* elements needed to turn one into the other.

(This is in contrast to the Cayley distance which counts the minimum number of transpositions of any pairs of elements, not necessarily adjacent.)

For $n \in \mathbb{N}$ consider the symmetric group $Sym(n)$ with its structure as a finitely generated group exhibited by the finite set of generators given by the *adjacent* transposition permutations

$Gen
\;\coloneqq\;
\big\{
\sigma_{i,i+1}
\,\vert\,
1 \leq i \lt n
\big\}
\;\subset\;
Sym(n)
\,.$

Then the *Kendall tau distance* (Kendall 1938, see also Diaconis 88, p. 112) is the distance on $Sym(n)$ which is the graph distance of the corresponding Cayley graph, hence the function

$d_K(-,-)
\;\colon\;
Sym(n) \times Sym(n)
\longrightarrow
\mathbb{N}
\hookrightarrow
\mathbb{R}$

which sends any pair of permutations $\sigma_1, \sigma_2 \in Sym(n)$ to the minimum number $d(\sigma_1, \sigma_2) \in \mathbb{N}$ of adjacent transpositions $\sigma_{i_1, i_1 + 1}, \sigma_{i_2, i_2 + 1}, \cdots, \sigma_{i_d, i_d+1}$ such that

$\sigma_2
\;=\;
\sigma_{i_d, i_d+1}
\circ
\cdots
\circ
\sigma_{i_2, i_2 + 1}
\circ
\sigma_{i_1, i_1 + 1}
\circ
\sigma_1
\,.$

For $\beta \in \mathbb{R}_{\geq 0}$, the exponential of this distance weighted by $- \beta$ is known as the *Mallows kernel*:

(1)$(\sigma_1,\sigma_2)
\;\mapsto\;
\exp
\big(
- \beta d_K(\sigma_1, \sigma_2)
\big)$

The Mallows kernel (1) is positive definite for all $\beta \geq 0$.

The distance function is due to:

- Maurice Kendall,
*A new measure of rank correlation*, Biometrika, Volume 30, Issue 1-2, June 1938, Pages 81–93 (doi:10.1093/biomet/30.1-2.81)

The corresponding exponential kernel is named after

- C. L. Mallows,
*Non-Null Ranking Models. I*, Biometrika Vol. 44, No. 1/2 (Jun., 1957), pp. 114-130 (jstor:2333244)

Textbook account:

- Persi Diaconis, Chapter 6B of:
*Group Representations in Probability and Statistics*, IMS Lecture Notes Monogr. Ser., 11: 198pp. (1988) (jstor:i397389, ISBN: 0940600145, pdf)

See also:

- Wikipedia,
*Kendall tau distance*

Review and proof that the exponentiated negative Kendall tau distance (the Mallows kernel) is a positive definite bilinear form:

- Yunlong Jiao, Jean-Philippe Vert,
*The Kendall and Mallows Kernels for Permutations*, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, no. 7, pp. 1755-1769, 1 July 2018 (doi:10.1109/TPAMI.2017.2719680, hal:01279273)

Discussion of weighted variants:

- Yunlong Jiao, Jean-Philippe Vert,
*The Weighted Kendall and High-order Kernels for Permutations*, Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2314-2322, 2018 (arXiv:1802.08526, mlr:v80/jiao18a, hal:hal-01717385)

Last revised on April 23, 2021 at 03:37:26. See the history of this page for a list of all contributions to it.