Given a permutation on n elements, Spearman’s Footrule Distance is the sum of the absolute differences between i and over all values of 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
where the maximum is taken over all permutations 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 . Let be any permutation with property P; namely, that if and if . Then
Now, in the first sum ranges over the values m+1 through 2m, hitting each exactly once. In the second sum does the same with the values 1 through m. Therefore,
Now, suppose we have a permutation that does not have property P. Suppose, without loss of generality, that for some . Then, by the pigeonhole principle, there exists some such that . Swap and to create a new permutation . Place the four points on a number line according to their numerical values. Let A, B, and C denote, respectively, the distances between consecutive points. Then . Regardless of the order of , and , we have . This is because the A to C distances must both be covered under the 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 that do have property P have , this must be the maximum value of Spearman’s Footrule Distance for permutations satisfying .
For the argument is similar. We need property Q; namely, that if , , and if . Then
The argument for permutations 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.