2
$\begingroup$

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

$\endgroup$
3
  • 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

1
+50
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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