Need to randomize rank order,

Question

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]$.

Answer 1

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)
    if adjustment_digit != 0:
        permutation.append(adjustment_digit)
    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[1], x[0])) 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.