nLab
Kendall tau distance

Contents

Context

Group Theory

Analysis

Contents

Idea

An adaptation of the Kendall tau rank correlation?, 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 quantity can also be defined as the total number of discordant pairs? between the two permutations.

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

This quantity is also referred to as the bubble sort distance, since bubble sorting algorithms repeatedly iterate over a list and swap adjacent elements if they are out of order.

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 July 15, 2021 at 14:29:55. See the history of this page for a list of all contributions to it.