# Quantitative/statistical comparison of two orderings/permutations

There is a couple, say, Theresa and Robert.

They assess their preferences on 5 books by ranking them from the most attractive to the least one.

• Theresa: [0,4,3,2,1]
• Robert: [1,4,3,2,0]

What would be the metric that would quantify if they have similar preferences or not? Ideally also with some statistical justification (not necessary).

Attempt so far: Number of necessary moves/edit distance for an order.

[0,4,3,2,1]
[4,0,3,2,1]
[4,3,0,2,1]
[4,3,2,0,1]
[4,3,2,1,0]
[4,3,1,2,0]
[4,1,3,2,0]
[1,4,3,2,0]

Maybe, it relates to bubble sort exchanges. I need 7 swaps to get there. The question is how can I say if 7 is too much or too little (statistically significant or not).

• One standard answer is the fraction of pairs of books where they agree on preferences. In this example, there are 10 (unordered) pairs, and Theresa and Robert agree on only 3 pairs: {2,3}, {2,4}, and {3,4}, so they have 30% agreement. So if you pick two random books, and ask both Robert and Theresa to pick the book that they want, there is a 30% chance of them picking same book, and 70% chance of them picking different books. Jun 16, 2021 at 15:13

Both your proposed bubble-sort and the proportion of pairs in agreement from the comments relate to Kendall's tau distance $$\tau_D$$, and with a little transformation, Kendall's tau correlation $$\tau$$. With two rankings of this size, a permutation test is pretty straight forward and already implemented in many software packages (I see you use Python, so I'll use that too). I'll go through the logic of the approach anyhow, but you can skip to the end if you'd like.

### Rank Distance and Similarity

Take the two ordered lists of $$k$$ objects and convert them to assigned ranks based on their position. Robert for example ranked book 4 second and book 0 last. Then for each object we can count the pairwise disagreements in the ordering of each object, which yields $$\tau_d$$. This corresponds to the number of adjacent swaps to convert permutation $$a$$ to permutation $$b$$, as you've worked out. The maximum number of possible disagreements is $$\tau_{D_{max}}=k(k-1)/2$$, which is sometimes used to normalise the distance between $$[0, 1]$$.

You can implement this in Python like so:

from itertools import combinations, permutations

# First convert to ranks
ranks = lambda perm: [perm.index(x) for x in range(0, len(perm))]

theresa = ranks([0,4,3,2,1])
robert = ranks([1,4,3,2,0])

# Find Kendall's Tau Distance
def kendall(a, b, normalised = False):
k = len(a)
dist = 0
pairs = combinations(range(0, k), 2)
for x, y in pairs:
dist += (a[x] > a[y]) != (b[x] > b[y])
if normalised:
max_dist = (k*(k-1))/2
dist = dist / max_dist
return dist

kendall(theresa, robert)
# 7

In this case, $$k=5$$ and $$\tau_D = 7$$, with a maximum possible distance of $$\tau_{D_{max}}=10$$. This means the proportion of pairwise disagreements is $$7/10 = 0.7$$, and thus the proportion of pairwise agreements is $$0.3$$ (as already noted in Matt's comment). This proportion of agreements might be a bit easier to interpret, and in answer to your question probably better quantifies the similarity of preferences.

### Permutation Test

To test whether the value of $$\tau_D$$ is statistically significant, we can consider the result in relation to all possible distances amongst $$k!$$ possible permutations. A one-sided p-value can be calculated as the proportion of permutations where the disagreements were greater than or equal to the observed statistic $$\tau_D$$.

from statistics import mean

# Permutation Test
perm = [0, 1, 2, 3, 4]
all_dists = [kendall(i, perm) for i in permutations(perm)]
mean([i >= 7 for i in all_dists])
# 0.24166666666666667

Considering the distribution of possible $$\tau_D$$ values, the probability of finding a result this extreme (or more) looks like this:

### Rank Correlation

Notably, $$\tau_D$$, is related to Kendall's tau correlation, $$\tau$$, which is implemented in most statistical software packages. You can convert back and forward between the two by:

$$\tau = 1 - 2 \bigg( \frac{1}{\tau_{D_{max}}} \bigg) \tau_D$$

and

$$\tau_D = \bigg( \frac{1-\tau}{2} \bigg) \tau_{D_{max}}$$

Which means you don't really need the code above, as scipy can calculate both $$\tau$$ and the permutation test, which after a transform or two gives exactly the same results.

from scipy.stats import kendalltau

# 'exact' method mirrors permutation test
tau, p_val = kendalltau(robert, theresa, method = 'exact')

# Calculate normalised distance from Kendall's tau
# p-value is two-sided, so convert to one-sided
(1 - tau)/2, p_val / 2
# (0.7, 0.24166666666666667)

Note that Kendall's $$\tau$$ is just one rank correlation method, although it is arguably the most intuitive and commonly used for permutation data. Other rank correlations based on the Spearman (based on the squared Euclidean), Footrule and Hamming distances are possible. For a nice review, see Chapter 3 of Alvo & Yu (2014).

#### References

Alvo, M. & Yu, L. H. P. (2014). Statistical methods for ranking data. New York: Springer, 2014.

Kendall, M. (1938). A New Measure of Rank Correlation. Biometrika. 30 (1–2): 81–89. doi:10.1093/biomet/30.1-2.81. JSTOR 2332226.