# Need to randomize rank order,

I have a ranking of items, $$X = (x_1, \ldots, x_n)$$. I want to obtain a random sequence $$\hat{X}$$, which is a permutation of $$x_i$$, such that the expected rank-correlation (say, Kendall) between $$X$$ and $$\hat{X}$$ is $$\tau$$, where $$\tau$$ is a parameter in range $$[0, 1]$$.

• I think it is not always possible. Rank-based correlations for finite samples are, kind of, "discrete". Not possible to make it equal to some random real number. – German Demidov Aug 13 '19 at 9:00
• Of course, but I only need this in expectation, which should be possible I think. – Ando Khachatryan Aug 13 '19 at 11:42
• In theory there are myriad ways to do this. Associated with each permutation $\sigma$ there is a rank correlation $\tau(\sigma)$ determined by $\sigma.$ All solutions consist of $n!$ probabilities $p_\sigma$ (indexed by the symmetric group and summing to unity) for which $$\sum_{\sigma\in\mathfrak{S}_n}p_\sigma \tau(\sigma) = \tau.$$ That's one more linear restriction on the probabilities, whence (generically) there is an $n!-2$ dimensional family of solutions. To narrow them down, could you explain more about your underlying statistical problem and objectives? – whuber Aug 13 '19 at 14:20
• Thanks for the comment. I need function which would compute (in Touring sense, i.e. I'm writing a program), efficiently, $\hat{X}$ from $X$, such that rank-correlation is $\tau$ in expectation. – Ando Khachatryan Aug 13 '19 at 14:43

Assuming you have a very large number of items in your rank it should be possible, the precision to which you will be able to match to $$\tau$$ will be determined by the size of your set.

Knowing that, you will want to work backwards from $$\tau$$, assuming that you have $$n$$ observations, we can get the concordant ($$c$$) discordant ($$d$$) pair ratio as follows: $$\tau = \dfrac{c-d}{c+d}$$ We also know that the total number of pairs for $$\tau$$ can be obtained using the following:

$${c+d} = \dfrac{1}{2}n(n+1)$$

Hence: $${c-d} = \dfrac{1}{2}n(n+1)-2d$$

And if we plug that into the $$\tau$$ function: $$\tau = \dfrac{\dfrac{1}{2}n(n+1)-2d} {\dfrac{1}{2}n(n+1)} = 1-\dfrac{4d}{n(n+1)}$$

We can now solve for $$d$$ which is the variable that will determine the correct permutation necessary:

$$d = \dfrac{1}{4}n(n+1)(1 - \tau)$$

This is where my mathematical knowledge reaches its limits, and the permutation will be calculated in python (I'm afraid it's a little convoluted, happy to refactor and add more comments):

#Function to calculate Tau without needing concordant pair number
def tau_from_discordant_and_n(discordant, n):
return 1-(4*discordant)/(n*(n+1))

#Entrypoint to get the right array for a given tau and input array
def permutation_for_tau(items: list, tau: float):
desired_discordant_pairs = 1/4*len(items)*(1+len(items))*(1-tau)
rounded_discordant_pairs = round(desired_discordant_pairs)
permutation = permutator(items, rounded_discordant_pairs)
return permutation, tau_from_discordant_and_n(desired_discordant_pairs, len(items))

# This function creates a permutation of the array increasing the number of discordant pairs by
# one at a time, for the array [1,2,3,4] the progression would be as follows:
# [1,2,3,4] => [2,1,3,4] => [3,1,2,4] => [4,1,2,3] => [4,2,1,3] => [4,3,1,2] => [4,3,2,1]
# The "thresholds" mentioned throughout the function indicate the point at which n number of
# digits are fully reversed within the start of the sequence. The adjustment value is the first
# digit after the sequence of fully reversed digits.

def permutator(items, discordant_pairs):
thresholds = []
previous_threshold = 0
for i in range(len(items) - 1):
current_threshold = len(items) - i - 1 + previous_threshold
thresholds.append(current_threshold)
number_of_fully_reversed_digits = i
if discordant_pairs <= current_threshold:
adjustment_digit = discordant_pairs - previous_threshold + 1
break
previous_threshold = current_threshold

permutation = []
for i in range(number_of_fully_reversed_digits):
permutation.append(len(items) - i)
missing_digits = list(set(items).difference(set(permutation)))
permutation+=missing_digits
return  permutation

array_to_permutate = [1,2,3,4,5,6]
results = [(permutation_for_tau(array_to_permutate, x/10)) for x in range(10, -1, -1)]
[print('Obtained tau of: {} with array: {}'.format(x, x)) for x in results]


Output:

Obtained tau of: 1.0 with array: [1, 2, 3, 4, 5, 6]
Obtained tau of: 0.9 with array: [2, 1, 3, 4, 5, 6]
Obtained tau of: 0.8 with array: [3, 1, 2, 4, 5, 6]
Obtained tau of: 0.7 with array: [4, 1, 2, 3, 5, 6]
Obtained tau of: 0.6 with array: [5, 1, 2, 3, 4, 6]
Obtained tau of: 0.5 with array: [6, 1, 2, 3, 4, 5]
Obtained tau of: 0.4 with array: [6, 2, 1, 3, 4, 5]
Obtained tau of: 0.30000000000000004 with array: [6, 3, 1, 2, 4, 5]
Obtained tau of: 0.19999999999999996 with array: [6, 4, 1, 2, 3, 5]
Obtained tau of: 0.09999999999999987 with array: [6, 5, 1, 2, 3, 4]
Obtained tau of: 0.0 with array: [6, 5, 2, 1, 3, 4]


Let me know if you need any further clarification, hope this helps, I'm sure there are many more efficient ways to do the permutation, but this should be good enough.

• I wrote a comment to the question that characterizes all solutions, no matter what $n$ may be. – whuber Aug 13 '19 at 14:22
• I think it should be $n(n-1)$ instead of $n(n+1)$, right? – Ando Khachatryan Aug 15 '19 at 15:21