Consider the following two metrics on permutations of $\{1,2,\dots,n\}$:
$d_{swap}(\sigma,\tau)$ is the minimum number of swaps of adjacent elements that are required to reach $\tau$ from $\sigma$ (or $\sigma$ from $\tau$). Alternatively, it is the number of discordant pairs for $\sigma$ and $\tau$. A pair of distinct elements $(x,y)$ is called a discordant pair for $\sigma$ and $\tau$ if $x$ and $y$ have different relative orderings in the two permutations. If I am not missing anything, $d_{swap}$ is identical to the Kendell tau distance.
$d_{sum}(\sigma, \tau)$ is given by $\sum_{i=1}^n |pos_{\sigma}(i) – pos_{\tau}(i)|$, where $pos_{\pi}$ indicates the position of $i$ in the permutation $\pi$.
I need to understand the relationship between these two metrics for another problem I am working on. In particular, I would like to know whether the following two conjectures I have are true:
- $d_{sum} \geq d_{swap}$
- there exists a constant $C < 1$, such that $d_{swap} \geq C \cdot d_{sum}$
While I am sure that these distances have been well studied, I did not manage to find the answer to these questions. If you know the answer or even any relevant literature feel free to help me out 🙂
Best Answer
This problem was studied by Diaconis and Graham: Spearman's Footrule as a Measure of Disarray.
What you call $d_{\text{swap}}$ they call $I$, and what you call $d_{\text{sum}}$ they call $D$. They show
$$I + T \leq D \leq 2 I$$
where $T$ is the number of transpositions needed to put the permutation in order, also called the reflection-length of a permutation. This language comes from the study of Coxeter Groups.