expected absolute difference between shuffled range of numbers Suppose I have a range of numbers $\{1,2,3,4...n\}$
What is the expected value if I shuffle them and then calculate the total absolute differences between neighbours?
For $n = 5$, here is an example.
$\{5,2,3,4,1\}$ --> $(3 + 1 + 1 + 3) = 8$
Initially I thought it would be $\frac{n(n-1)}{2}$, since if I consider the number $1$, its neighbour distances can vary from $1$ to $(n-1)$ (average $n/2$) and there are ($n-1$) total neighbours.
However, this isn't correct, since for the number $3$ neighbours only be a maximum of $2$ away.
I did some simulations and it seems to be closer to $\frac{n^2}{3} $ but I'm not at all sure how I could prove this.
I am interested in the topic because of this paper that defines a correlation metric using neighbours' rank differences to quantify dependencies. I was trying to understand what the expected neighbour's rank differences would be for a random rank ordering.
I see you can do something very messy by counting differences for all permutations, but I think there must be something simple that quantifies the total expected absolute differences a function of n however I don't know how to calculate this.
 A: If $X_k$ is the $k$-th number after the shuffle then you want to compute
$$
\mathbb{E}\left[\sum_{k=1}^{n-1}|X_{k+1}-X_k|\right]=\sum_{k=1}^{n-1} \mathbb{E}[|X_{k+1}-X_k|]=(n-1)\mathbb{E}[|X_2-X_1|]
$$
as $\mathbb{E}[|X_{k+1}-X_k|]$ is the same for any $k \in\{1,\ldots,n-1\}$. Finally, observe that
$$
\begin{align*}
\mathbb{E}[|X_2-X_1|]&=\sum_{1\leqslant j,k\leqslant n}|j-k|\Pr [X_1=j]\Pr [X_2=k|X_1=j]\\
&=2\sum_{1\leqslant j<k\leqslant n}(k-j)\frac1{n}\cdot \frac1{n-1}\\
&=\frac{2}{n(n-1)}\sum_{k=2}^n\sum_{j=1}^{k-1}(k-j)\\
&=\frac{2}{n(n-1)}\left(\sum_{k=2}^nk(k-1)-\sum_{k=2}^n\frac{k(k-1)}{2}\right)\\
&=\frac{2}{n(n-1)}\cdot \frac{(n+1)n(n-1)}{6}\\
&=\frac{n+1}{3}
\end{align*}
$$
Therefore
$$
\mathbb{E}\left[\sum_{k=1}^{n-1}|X_{k+1}-X_k|\right]=\frac{(n-1)(n+1)}{3}
$$
A: Say $X$ is the random variable which represents sum of absolute difference of all $(n-1)$ neighboring pairs.
Leaving aside the order of two numbers in a pair, please notice that there are $(n-i)$ pairs with  difference of $~i$
($1 \leq i \leq n-1$).
That means the probability of difference $i$ for a pair of  numbers is, $ \displaystyle ( n-i) / {n \choose 2}$. As there are $(n-1)$ neighboring pairs,
$ \displaystyle \mathbb{E}[X] = \left[(n-1) / {n \choose 2}\right] ~ \sum \limits_{i=1}^{n-1} i (n - i) = \frac{2}{n} \sum \limits_{i=1}^{n-1} (n i - i^2)$
As $~\displaystyle \sum\limits_{i=1}^{n-1} i = \frac{n(n-1)}{2}~~ \text {and } ~ \sum\limits_{i=1}^{n-1} i^2 = \frac{n(n-1)(2n-1)}{6}~$,
$ \displaystyle \mathbb{E}[X] = \frac{n^2-1}{3}$
