Statistics of list permutations - expected similarity of rankings?

Question

I created a website where users create rankings, so for each user I have an ordered list of distinct elements $[e_1, e_2, ..., e_n]$

I calculate the similarity of two users by summing up the absolute index differences for each element and dividing the result by the maximum possible total difference ($ \lfloor n^2/2 \rfloor $), then subtracting that from one.

Users with similarity 1 have the exact same ranking.

Now it seems that for most users the average difference to all other users isn't 50%, but below that. I calculated the difference for all permutations for $n=10$ from one specific ranking and got this result:

and this seems to confirm this phenomenon - assuming that user rankings (element permutations) are random, the average similarity to other users is indeed less than 50%. But why? What kind of distribution is this and what is its most common value for a given $n$?

Since with $n$ elements, there are $n!$ possible permutations, it isn't possible to "brute-force-plot" this for large n, unless (randomly) sampling a subset which I've done here:

Answer 1

The reference Catalin Zara gave to Diaconis and Graham in the comments provides the information you need. This is also sequence A062869 in OEIS. Following Diaconis and Graham, let$$ D(\pi,\sigma)=\sum_{i=1}^n|\pi(i) - \sigma(i)|. $$ The statistics of $D(\pi,\sigma)$ over $\pi$ are the same for any $\sigma$, so we only need to consider $D(\pi) = D(1,\pi)$, where $1$ denotes the identity permutation. Your statistic is$$ S(\pi) = 1-\frac{1}{\lfloor n^2/2 \rfloor} D(\pi). $$ Diaconis and Graham state that $D$ approaches a normal distribution as $n \rightarrow \infty$, and that the asymptotic mean and variance are $\mathbb{E}[D] = n^2/3$ and $\mathrm{var}[D] = 2n^3/45$. Therefore the $S$ is also asymptotically normal with asymptotic mean and variance equal to $$ \begin{align} \mathbb{E}[S]&=\frac{1}{3},\;\text{and}\\ \mathrm{var}[S]&=\frac{8}{45n}. \end{align} $$ In particular, for $n=100$ the asymptotic mean of $1/3$, the asymptotic standard deviation of $0.042$, and the asymptotic normality of the distribution are all consistent with your histogram.