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]$.
-
$\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 '19 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 '19 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 '19 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 '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)
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.
-
1$\begingroup$ I wrote a comment to the question that characterizes all solutions, no matter what $n$ may be. $\endgroup$ – whuber♦ Aug 13 '19 at 14:22
-
$\begingroup$ I think it should be $n(n-1)$ instead of $n(n+1)$, right? $\endgroup$ – Ando Khachatryan Aug 15 '19 at 15:21