1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – German Demidov Aug 13 at 9:00
  • 1
    $\begingroup$ Of course, but I only need this in expectation, which should be possible I think. $\endgroup$ – Ando Khachatryan Aug 13 at 11:42
  • $\begingroup$ 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? $\endgroup$ – whuber Aug 13 at 14:20
  • $\begingroup$ 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. $\endgroup$ – Ando Khachatryan Aug 13 at 14:43
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.