Note: I asked this question a few months ago here, but received no answer.
Consider the following two metrics on permutations of $\{1,2,\dots,n\}$:
$d_\text{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_\text{swap}$ is identical to the Kendell tau distance.
$d_\text{sum}(\sigma, \tau)$ is given by $\sum_{i=1}^n \left|\operatorname{pos}_\sigma(i) – \operatorname{pos}_\tau(i) \right|$, where $\operatorname{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_\text{sum} \geq d_\text{swap}$
- there exists a constant $C < 1$, such that $d_\text{swap} \geq C \cdot d_\text{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
Both statistics are preserved under right multiplication by a permutation, so you can reduce to the case where $\sigma$ is the identity.
In that case, $d_{\rm swap}$ is the inversion number or equivalently the Coxeter length of the permutation, and $d_{\rm sum}$ is the total displacement, studied by Diaconis and Graham (and more recently by Petersen and Tenner).
Diaconis and Graham proved that total displacement is at least the sum of length and reflection length, so your first conjecture is true.
Your second conjecture is false. Take the family of permutations where $\tau=n2\cdots(n-1)1$ (and $\sigma$ is the identity). Then $d_{\rm swap}=2n-3$ and $d_{\rm sum}=2n-2$, and the limit of the ratios is 1.EDIT: I misread the second conjecture. Diaconis and Graham prove that $C=1/2$ works (and Petersen and Tenner show the bound is realized precisely by the permutations avoiding 321).
EDITED TO ADD REFERENCES: Persi Diaconis and Ronald L. Graham, Spearman's Footrule as a Measure of Disarray. J. R. Stat.Soc. Ser. B. Stat. Methodol. 39 (1977), 262--268.
T. Kyle Petersen and Bridget E. Tenner, The depth of a permutation. J. Comb. 6 (2015) 145--178.