Expected distance between two permutations? 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! 
 A: 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$.
