nLab
Kendall tau distance

Contents

Context

Group Theory

Analysis

Contents

Idea

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

Definition

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

Gen{σ i,i+1|1i<n}Sym(n). 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)Sym(n) which is the graph distance of the corresponding Cayley graph, hence the function

d K(,):Sym(n)×Sym(n) d_K(-,-) \;\colon\; Sym(n) \times Sym(n) \longrightarrow \mathbb{N} \hookrightarrow \mathbb{R}

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

σ 2=σ i d,i d+1σ i 2,i 2+1σ i 1,i 1+1σ 1. \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 β 0\beta \in \mathbb{R}_{\geq 0}, the exponential of this distance weighted by β- \beta is known as the Mallows kernel:

(1)(σ 1,σ 2)exp(βd K(σ 1,σ 2)) (\sigma_1,\sigma_2) \;\mapsto\; \exp \big( - \beta d_K(\sigma_1, \sigma_2) \big)

Properties

Theorem

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

(Jiao-Vert 18, Theorem 1)

References

The distance function is due to:

The corresponding exponential kernel is named after

Textbook account:

See also:

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

Discussion of weighted variants:

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