# Statistics of list permutations - expected similarity of rankings?

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:

• Unrelated to your specific question, but here are some other notions of distance between permutations that may interest you. Jul 28 at 16:05
• You may want to take a look at finmath.stanford.edu/~cgates/PERSI/papers/77_04_spearmans.pdf Jul 28 at 16:22
• The expected sum of absolute ranking differences is $\frac13(n^2-\frac1n)$ which is nearer two-thirds rather than half your $\lfloor n^2/2 \rfloor$ for $n>2$ Jul 28 at 16:47

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.