0
$\begingroup$

I am seeking an algorithm with two inputs and one output.

As the first input, consider any sorted finite sequence $s_1, s_2, ..., s_n$. The second input is a rank-order correlation parameter $\rho\in [-1, 1]$. The output of the algorithm is a new sequence of the same length as the original input sequence, call this $(\phi_k)_{k=1}^n$.

My question is the following:

How to generate (in R, preferably) a random sequence $\phi_1, \phi_2, ..., \phi_n$ which is a permutation of the input sequence, such that the two sequences $(s_k)_{k=1}^n$ and $(\phi_k)_{k=1}^n$ have an expected rank-order correlation $\rho$?

Example. Consider as input the simple sequence consisting of all whole numbers from 1 to 12:

1 2 3 4 5 6 7 8 9 10 11 12

Then with perfect correlation ($\rho = 1$), it obviously always returns the same sequence:

1 2 3 4 5 6 7 8 9 10 11 12

With a high but non-perfect ($0\ll\rho < 1$) correlation, it might return:

1 2 4 3 5 6 9 7 8 10 11 12

However, it would return a random sequence, not necessarily that one. Notice that 3 and 4 have changed places, and 7, 8, 9 became 9, 7, 8. As you can see, there is still clearly an increasing trend. Higher numbers are more concentrated in the end and lower numbers in the beginning. But the relation is non-perfect, it is no longer a perfectly sorted sequence.

When $\rho = 0$ the output should be a permutation of the input sequence where there is no expected rank-order relation between the sequences. In other words, that would just be an ordinary random permutation where all possible permutations have equal likelihood of occurring.

When $\rho = -1$ the output would be a complete reversal of the input sequence:

12 11 10 9 8 7 6 5 4 3 2 1

Hope my question makes sense, otherwise please ask for any clarifications. Thanks in advance for any help.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ It sounds like there might be a statistical problem lurking beneath this formulation--and perhaps by disclosing that problem you will convey enough information to indicate what distribution of correlations you need. (Stipulating only the expectation leaves the problem rather wide open to different solutions, many of which might not accomplish your real objective.) $\endgroup$ – whuber♦ Aug 20 '18 at 18:28
  • $\begingroup$ @whuber You're right. I thought a bit about how I should word it exactly, and although not being totally satisfied with it, I chose the wording "expected rank-order correlation." It is by no means important that it should be the expected correlation. I will appreciate anyone with statistical expertise to make adjustments to my formulation within a reasonable reinterpretation of my question. I am simply trying to achieve the following: If $\rho$ is high, then the two sequences will, in some reasonable statistical way, tend to be higher correlated. $\endgroup$ – Eff Aug 20 '18 at 18:33
  • $\begingroup$ @whuber I have no extremely precise requirements, I just want something that produces these trends. If $\rho = 1$, return the same ordered sequence. If $\rho = 0$, then all permutations of the sequence have equal likelihood of being output. For values in between $\rho = 0$ and $\rho = 1$ there should be some gradual trends. If $\rho$ is closer to $1$, then the rank-order correlation will tend to higher than if $\rho$ is closer to $0$. How exactly this is achieved I would be happy for anyone to make a suggestion. $\endgroup$ – Eff Aug 20 '18 at 18:48
  • 1
    $\begingroup$ For example, one possible solution is for each possible value of $\rho \ge 0,$ output a uniform random permutation with probability $1-\rho$ and otherwise output the identity. When $\rho \lt 0,$ apply the preceding approach to $-\rho$ and reverse the output. That doesn't seem like it would be too satisfactory due to its tendency to output the identity permutation (or its reversal). $\endgroup$ – whuber♦ Aug 20 '18 at 19:46
  • 1
    $\begingroup$ It's hard to tell what you're looking for. My (toy) proposal generates all kinds of permutations. The degree of "sortedness" is beautifully controlled by $\rho.$ Unless $\rho=\pm1,$ every possible permutation has a positive probability of being realized, but the expected correlation is $\rho,$ as required. Your objection must have something to do with your not-yet-explicit requirements about the nature of this distribution. $\endgroup$ – whuber♦ Aug 20 '18 at 20:56

Your Answer

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

Browse other questions tagged or ask your own question.