# Expected absolute difference between shuffled range of numbers

expected valuepermutationsprobabilityuniform distribution

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.

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
$$\mathbb{E}\left[\sum_{k=1}^{n-1}|X_{k+1}-X_k|\right]=\frac{(n-1)(n+1)}{3}$$