Suppose you have an $n$-vector $X$. For a fixed real number, $r$ between $-1$ and $1$, can one generate a random permutation of the integers $1,2,\ldots,n$, call it $i_1,i_2,\ldots,i_n$ such that the vector $X$ and the vector $\tilde{X}$ defined by $\tilde{X_j} = X_{i_j}$ have expected sample correlation of $r$? I am looking for a process that generates such permutations. Without loss of generality, I believe one may assume $X$ has zero sample mean, and unit sample standard deviation.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ @kwak Concerning your deleted response: I see vaguely that there is some kind of limited permuting going on until somehow a correlation coefficient below 0.5 (e.g.) is attained, but I cannot quite connect that with the conditions of the original question. Are you saying you just keep applying "small" random permutations until you obtain a correlation within a targeted range of correlations? If that's so, I think it's a really creative idea but some analysis is needed to show it can actually work. Regardless, thanks for sharing it (however briefly!). $\endgroup$– whuber ♦Oct 25, 2010 at 20:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
The answers are no, not for all $r$ in general; yes, for a restricted range of $r$ that is readily computed; but there remain a wide set of choices to be made.
I will use a standard notation where the action of a permutation $\sigma$ is written $ X^\sigma_i = X_{\sigma (i)}$ and the set of all permutations of the $n$ coordinates is $S_n$.
As you note in the question, upon standardizing $X$ it suffices to investigate $\mathbb{E}[{X^\sigma}'X]$. Because $X'X = 1$, a correlation of $r = 1$ is certainly attainable by means of the identity permutation $\epsilon$ (where $\epsilon(i) = i$ for all $i$). However, for any given $X$ there is a minimum attainable correlation: it is realized by associating the $k^\text{th}$ smallest component of $X^\sigma$ with the $k^\text{th}$ largest component of $X$. For example, with $X = (-2,1,1)/\sqrt{6}$ the smallest possible correlation of $-1/2$ is achieved by $X^\sigma = (1,1,-2)/\sqrt{6}$. Let's call this minimum correlation $r_{min}(X)$ and let $\sigma_{min}(X)$ be any permutation achieving this minimum value.
Every possible expected correlation of value between $r_{min}(X)$ and $1$ is attainable by means of a distribution supported on just $\sigma_{min}$ and $\epsilon$. Specifically, set
$$p = \frac{r - r_{min}}{1 - r_{min}}$$
and generate the permutation $\sigma_{min}$ with probability $1 - p$ and the permutation $\epsilon$ with probability $p$. (If $r_{min} = 1$ this formula is undefined but there's nothing to do anyway.)
I suspect you would like a more "interesting" distribution of permutations than this. To create this you will need to add more conditions. Here's one way to frame your problem: to every permutation $\sigma$ corresponds the number $f(\sigma) = {X^\sigma}'X$. An arbitrary probability distribution over the permutations assigns a non-negative value $p(\sigma)$ to each permutation according to the axioms of probability. The expectation of $f$, which is the expected correlation between $X$ and $X^\sigma$, of course equals
$$\sum_{\sigma \in S_n}{p(\sigma)f(\sigma)}.$$
Given a desired expected correlation $r$, you therefore have freedom to choose the $n!$ values $p(\sigma)$ subject to the conditions
$$\sum_{\sigma \in S_n}{p(\sigma)} = 1,$$
$$\sum_{\sigma \in S_n}{p(\sigma)f(\sigma)} = r,$$
$$p(\sigma) \ge 0 \text{ for all } \sigma \in S_n.$$
I have merely demonstrated that this linear program is feasible if and only if $r_{min} \le r \le 1$. You are free to choose among the solutions (a convex set of distributions) in any way you like. For instance, you might prefer to use as uniform a choice of permutations as possible, in which case you might seek to minimize the variance of the $p(\sigma)$ (thought of just as a set of numbers) subject to the preceding conditions. That's a quadratic program, for which there are many good solution methods and much available software. Solving this (exactly) will become problematic once $n$ exceeds about $8$ or so, because it involves $n!$ variables and you'll just overwhelm the software. In such cases you might want to restrict the distributions further, such as requiring them to be only cyclic and anti-cyclic permutations of the sorted coordinates (just $2n$ variables). Another possibility is to choose a bunch of permutations randomly--making sure to include the order-reversing permutation among them so the minimum correlation can be included--and then finding an approximately uniform distribution among them.
-
$\begingroup$ I had suspected there was a 'trivial' algorithm, which generated the identity permutation with probability $r$, and was uniform on all permutations with probability $1-r$, for the case $r > 0$. It looks like that is not exactly correct, and your "uninteresting" solution fixes my error. $\endgroup$ Oct 25, 2010 at 16:29
-
$\begingroup$ @shabbychef You have a fine intuition: picking a permutation uniformly at random gives an expected correlation of zero. To achieve an expectation of r > 0, then, select the identity with probability r and otherwise select any uniformly random permutation (including the identity) with probability 1-r. A similar approach (using the reversal of ranks) will yield any expectation down to the minimum possible value for the data (which depends on the data, not just on how many there are). These solutions don't yield the most uniform distributions overall, though: one permutation clearly is favored. $\endgroup$– whuber ♦Oct 25, 2010 at 18:30
-
$\begingroup$ @whuber yes, I had mistakenly thought that I could also achieve any negative $r$ by this trivial method, by 'reversing' the indices with probability $|r|$. I guess I was tacitly assuming the vector $X$ was symmetric about $0$. The trivial algorithm is unsatisfying, though, as you suspected. $\endgroup$ Oct 25, 2010 at 19:25
-
1$\begingroup$ @shabbychef Then you might want to give some thought to achieving a desired variance in the correlation coefficients that will be generated. You can include that within the constraints and, provided the desired variance is neither too great nor too small, you should still have a nonempty feasible set. For this application it might be wise to achieve as uniform a distribution as possible. Alternatively, you can impose a desired variance by means of a penalty term in the objective function, seeking a balance between uniformity and achieving the target values of variance and expectation. $\endgroup$– whuber ♦Oct 26, 2010 at 16:16
-
1$\begingroup$ @qed It is an expectation, not a sample correlation. For instance, the expectation of a Bernoulli$(p)$ variate is $p$ but the only values that variable can attain are $0$ and $1$. $\endgroup$– whuber ♦Sep 1, 2013 at 15:22