Expected distance between two permutations? [closed]

Question

Consider the integer vector ${\bf w}=[1,2,3,\dots,n]$ and permutations of such vector. If we define the function $$d({\bf u},{\bf v})=\sum_{i=1}^n |u_i - v_i|, $$ where $\bf u$ and $\bf v$ are any generic permutation of $\bf w$, then it is straightforward that $d\leq N(N-1)$, where the upper bound is reached, for instance, for ${\bf u}={\bf w}$ and ${\bf v}=[N,N-1,\dots,1]$. The question is, then, what is the expected value of $d$? What would I get (typically) for $d({\bf u},{\bf v})$?

Thanks!

Answer 1

Let your two permutations be $\vec{u} = (U_1, U_2, \ldots, U_n)$ and $\vec{v} = (V_1, V_2, \ldots, V_n)$. Then what you're asking for is

$$E \left( \sum_{i=1}^n |U_i - V_i| \right)$$

and by linearity of expectation this is

$$\sum_{i=1}^n E (|U_i - V_i|).$$

Now for any given $i$, $U_i$ is uniformly distributed on $\{1, 2, \ldots n\}$; $V_i$ has the same distribution; and the two are independent. (This is because they come from different permutations! $U_1$ and $U_2$, for example, are not independent.)

Now, let's find $E(|U_i - V_i|)$. Clearly $P(U_i = j, V_i = k) = 1/n^2$ for any $j, k$ with $1 \le j, k \le n$. So you're looking for

$$ E(|U_i - V_i|) = {1 \over n^2} \sum_{j=1}^n \sum_{k=1}^n |j-k| $$

but we can just include all the terms where $j > k$, if we include them twice -- the $(j, k)$ term wil be the same as the $(k, j)$ term. This gives

$$ E(|U_i - V_i|) = {2 \over n^2} \sum_{j=1}^n \sum_{k=1}^{j-1} (j-k). $$

Now the inner sum is just $1 + 2 + \ldots + (j-1) = j(j-1)/2$, so you get

$$ E(|U_i - V_i|) = {2 \over n^2} \sum_{j=1}^n {j(j-1) \over 2} = {1 \over n^2} \sum_{j=1}^n (j^2 - j). $$

By well-known formulas for the sum of the first $n$ integers and the first $n$ squares this is

$$ {1 \over n^2} \left( {n(n+1)(2n+1) \over 6} - {n(n+1) \over 2} \right) = {1 \over n^2} {n^3 - n \over 3}. $$

At last the expectation you wanted is $n$ times this, or $(n^2 - 1)/3$.