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:

enter image description here

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:

enter image description here

  • 1
    $\begingroup$ Unrelated to your specific question, but here are some other notions of distance between permutations that may interest you. $\endgroup$
    – angryavian
    Commented Jul 28, 2023 at 16:05
  • 3
    $\begingroup$ You may want to take a look at finmath.stanford.edu/~cgates/PERSI/papers/77_04_spearmans.pdf $\endgroup$ Commented Jul 28, 2023 at 16:22
  • 1
    $\begingroup$ 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$ $\endgroup$
    – Henry
    Commented Jul 28, 2023 at 16:47

1 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .