Classical groups
Finite groups
Group schemes
Topological groups
Lie groups
Super-Lie groups
Higher groups
Cohomology and Extensions
Related concepts
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
…
…
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.
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
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
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
For $\beta \in \mathbb{R}_{\geq 0}$, the exponential of this distance weighted by $- \beta$ is known as the Mallows kernel:
The Mallows kernel (1) is positive definite for all $\beta \geq 0$.
The distance function is due to:
The corresponding exponential kernel is named after
Textbook account:
See also:
Wikipedia, Kendall tau distance
Cicirello_2020, Kendall tau sequence distance: Extending Kendall tau from ranks to sequences, EAI Endorsed Transactions on Industrial Networks and Intelligent Systems, vol. 7, no.23, (DOI=10.4108/eai.13-7-2018.163925)
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 December 25, 2023 at 08:16:35. See the history of this page for a list of all contributions to it.