## The Maximum Value of Spearman’s Footrule Distance

Given a permutation $\sigma$ on n elements, Spearman’s Footrule Distance $F(\sigma)$ is the sum of the absolute differences between i and $\sigma(i)$ over all values of i:

$\displaystyle F(\sigma) = \sum_{i=1}^n |\sigma(i) - i|.$

Spearman’s Footrule Distance can be thought of as a measure of the disarray of a permutation.  Another such measure is Kendall’s Tau, which uses the sum of squared deviations rather than the sum of absolute deviations.

In this post we prove that $\displaystyle \max_{\sigma} F(\sigma) = \begin{cases} 2m^2, & n = 2m; \\ 2m^2+2m, & n = 2m+1; \end{cases}$
where the maximum is taken over all permutations $\sigma$ on n elements.  The argument is that given by user4140 in this post on Math.SE with some details added.

First, let’s look at the case where n is even.  Let $n = 2m$.  Let $\sigma$ be any permutation with property P; namely, that $\sigma(i) > m$ if $i \leq m$ and $\sigma(i) \leq m$ if $i > m$.  Then

$\displaystyle F(\sigma) = \sum_{i=1}^{2m} |\sigma(i) - i| = \sum_{i=1}^m (\sigma(i) - i) + \sum_{i=m+1}^{2m} (i - \sigma(i))$.

Now, in the first sum $\sigma(i)$ ranges over the values m+1 through 2m, hitting each exactly once.  In the second sum $\sigma(i)$ does the same with the values 1 through m.  Therefore,

$\displaystyle F(\sigma) = 2 \sum_{i=m+1}^{2m} i - 2 \sum_{i=1}^m i = 2m(2m+1) - m(m+1) - m(m+1)$
$\displaystyle = 2m(2m+1) - 2m(m+1) = 2m(2m+1-m-1) = 2m^2.$

Now, suppose we have a permutation $\sigma$ that does not have property P.  Suppose, without loss of generality, that $\sigma(i) \leq m$ for some $i \leq m$.  Then, by the pigeonhole principle, there exists some $j > m$ such that $\sigma(j) > m$.  Swap $\sigma(i)$ and $\sigma(j)$ to create a new permutation $\sigma'$.  Place the four points $i, \sigma(i), j,\sigma(j)$ on a number line according to their numerical values.  Let A, B, and C denote, respectively, the distances between consecutive points.  Then $|\sigma(i) - i| + |\sigma(j) - j| = A+C$.  Regardless of the order of $i, \sigma(i), j$, and $\sigma(j)$, we have $|\sigma'(i) - i| + |\sigma'(j) - j| = A + C + 2B$.  This is because the A to C distances must both be covered under the $\sigma'$ permutation and the B distance must be covered twice.

Therefore, any permutation that does not have property P cannot be a permutation that achieves the maximum value of Spearman’s Footrule Distance.  Since those permutations $\sigma$ that do have property P have $F(\sigma) = 2m^2$, this must be the maximum value of Spearman’s Footrule Distance for permutations satisfying $n = 2m$.

For $n = 2m+1$ the argument is similar.  We need property Q; namely, that $\sigma(i) > m+1$ if $i \leq m$, $\sigma(m+1) = m+1$, and $\sigma(i) \leq m$ if $i > m+1$.  Then

$\displaystyle F(\sigma) = \sum_{i=1}^{2m+1} |\sigma(i) - i| = \sum_{i=1}^m (\sigma(i) -i) + \sum_{i=m+2}^{2m+1} (i - \sigma(i))$
$\displaystyle = (2m+1)(2m+2) - (m+1)(m+2) - m(m+1) = 2m^2+2m.$

The argument for permutations $\sigma$ that do not satisfy property Q is similar.  This proves the result.

For more information on Spearman’s Footrule Distance, see Diaconis and Graham, “Spearman’s Footrule as a Measure of Disarray,” Journal of the Royal Statistical Society, Series B, Vol. 39, No. 2 (1977) , pp. 262-268.