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.

Advertisements
This entry was posted in combinatorics, permutations. Bookmark the permalink.

One Response to The Maximum Value of Spearman’s Footrule Distance

  1. Alejandro Rosete Suarez says:

    Thanks .. I have a suggestion.
    It would be useful to include the derivation of the formula Max F in term of n (instead of m) because the natural formulation is in terms of n..
    It may be something like this:
    Max F
    (n^2)/2 if n is even
    (n-1)(n+1)/2 if n is odd

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s