12
$\begingroup$

We draw $N$ samples, each of size $n$, independently from a Normal $(\mu,\sigma^2)$ distribution.

From the $N$ samples we then choose the 2 samples which have the highest (absolute) Pearson correlation with each other.

What is the expected value of this correlation ?

Thanks [P.S. This is not homework]

$\endgroup$
  • 2
    $\begingroup$ (+1) It would make a fairly challenging homework question :-). Do you need a general answer or could you (perhaps) focus your attention on specific values of $N$ or $n$? For instance, it may be possible to develop good approximations when $n$ is much larger than $N$; different approximations would be needed in other cases. $\endgroup$ – whuber Apr 2 '12 at 16:12
  • 1
    $\begingroup$ I was hoping for a general answer, but one where the assumption $n>>N$ would be OK ! For specific values of $N$ and $n$ , it wouldn't be so interesting, as I can look at such specific cases by simulation (that's what I'm doing at the moment), but it might still be of interest. $\endgroup$ – P Sellaz Apr 2 '12 at 16:25
  • 1
    $\begingroup$ I think a general solution of any real utility is probably unlikely, though I could be mistaken. It is fairly closely related to some open problems at the interface of geometry and linear algebra. In applications, the need for information on such quantities arises, for example, in compressed sensing. $\endgroup$ – cardinal Apr 2 '12 at 17:50
  • 1
    $\begingroup$ FWIW, this is the result of a simulation I have just been running: using Normal(0,1), I found that the mean correlation, $\rho$ (over 1000 simulations), and the number of samples $N$ are approximately related by $$\rho=0.025+0.113\ln(N)-0.008\ln(N)^2 $$ for $n=100$ and $4\leq N \leq n$ using a linear regression model. The model fit and usual diagnostics were quite good. I also found that the mean correlation was approximately normally distributed (though slightly right-skew). $\endgroup$ – P Sellaz Apr 2 '12 at 23:29
9
$\begingroup$

I found the following article, which addresses this problem: Jiang, Tiefeng (2004). The Asymptotic Distributions of the Largest Entries of Sample Correlation Matrices. The Annals of Applied Probability, 14(2), 865-880

Jiang shows the asymptotic distribution of the statistic $L_n = \max_{1\leq i<j\leq N} |\rho_{ij}|$, where $\rho_{ij}$ is the correlation between the $i$th and $j$th random vectors of length $n$ (with $i\neq j$), is

$$ \lim_{n \to \infty} \Pr[ nL_n^2 - 4\log n + \log(\log(n)) \leq y] = \exp\left(-\frac{1}{a^2\sqrt{8\pi}}\exp(-y/2)\right) \,, $$ where $a = \lim_{n\to\infty} n/N$ is assumed to exist in the paper and $N$ is a function of $n$.

Apparently this result holds for any distribution distributions with a sufficient number of finite moments (Edit: See @cardinal's comment below). Jiang points out that this is a Type I extreme value distribution. The location and scale are

$$ \sigma=2,\quad\mu = 2\log\left( \frac{1}{a^2\sqrt{8\pi}} \right). $$

The expected value of the Type-I EV distribution is $\mu + \sigma \gamma$, where $\gamma$ denotes Euler's constant. However, as noted in the comments, convergence in distribution does not, in and of itself, guarantee convergence of the means to that of the limiting distribution.

If we could show such a result in this case, then the asymptotic expected value of $n L_n^2 -4\log n + \log(\log(n))$ would be

$$ \lim_{n\to\infty} \mathbb E\left[ nL_n^2 - 4\log n + \log(\log(n)) \right] = -2\log\left(a^2\sqrt{8\pi} \right) + 2\gamma \,. $$

Note that this would give the asymptotic expected value of the largest squared correlation, whereas the question asked for the expected value of the largest absolute correlation. So not 100% there, but close.

I did a few brief simulations that lead me to think either 1) there's a problem with my simulation (likely), 2) there's a problem with my transcription / algebra (also likely), or 3) the approximation isn't valid for the values of $n$ and $N$ I used. Perhaps the OP can weigh in with some simulation results using this approximation?

$\endgroup$
  • 1
    $\begingroup$ And an aside: I really liked this question -- I've wondered about this question before. I was surprised by the connection to the Type-I distribution -- I found that to be pretty cool. I just wish I understood the math leading up to it... $\endgroup$ – jmtroos Apr 5 '12 at 2:15
  • 1
    $\begingroup$ (+1) Nice find !! I think we can assume that the positive square root of the this $L_n$ is equivalent to the expected value of the largest absolute correlation ? In your expression for the expectation, can't we just take out all the parts involving $n$ to yield:$$E\left[L_n^2 \right]= \frac{1}{n} \left \{ 2\log\left( \frac{N^2}{n^2\sqrt{8\pi}} \right) + 2\gamma+ 4\log n - \log(\log(n))\right \}$$ ? Anyway, I have compared this to my simulations and it looks quite close ! My R code is really sloppy, so I'll try to tidy it up later today or tomorrow and post it... $\endgroup$ – P Sellaz Apr 5 '12 at 10:19
  • $\begingroup$ BTW, the paper is available directly from here projecteuclid.org/DPubS/Repository/1.0/… $\endgroup$ – P Sellaz Apr 5 '12 at 10:21
  • 3
    $\begingroup$ (+1) This is a very nice paper, and I've only skimmed it, but we need to be a little careful here. Some remarks: (1) The results are for the regime $n/p \to \gamma \in (0,\infty)$, so the dimension of the vectors has to be growing roughly proportional to the number of vectors under consideration for these results to hold. (2) Even in this case, the results do not hold for "any" distribution; indeed, the conditions in the paper require that the random variables be "almost exponentially bounded" ones in the sense that we essentially require the 30th moment to be finite! (cont.) $\endgroup$ – cardinal Apr 5 '12 at 18:02
  • 3
    $\begingroup$ (cont.) (3) Convergence in distribution does not guarantee convergence of the means to that of the limiting distribution. For that, we normally use something akin to uniform integrability of the set $\{L_n\}$. This has not been shown in the paper and, since dealing with extreme-value distributions, might well not be true. One of my favorite examples of this phenomenon is a sequence of random variables that converges in distribution to a $\chi^2_1$, but the means can be made to converge to any positive constant one chooses. $\endgroup$ – cardinal Apr 5 '12 at 18:02
2
$\begingroup$

Further to the answer provided by @jmtroos, below are the details of my simulation, and a comparison with @jmtroos's derivation of the expectation from Jiang (2004), that is:

$$E\left[L_n^2 \right]= \frac{1}{n} \left \{ 2\log\left( \frac{N^2}{n^2\sqrt{8\pi}} \right) + 2\gamma+ 4\log n - \log(\log(n))\right \}$$

The values of this expectation seem to be above the simulated values for small $N$ and below for large $N$ and they appear to diverge slightly as $N$ increases. However, the differences diminish for increasing $n$, as we would expect as the paper claims that the distribution is asymptotic. I have tried various $n \in [100,500]$. The simulation below uses $n=200$. I'm pretty new to R, so any hints or suggestions to make my code better would be warmly welcomed.

set.seed(1)

ns <- 500
# number of simulations for each N

n <- 200
# length of each vector

mu <- 0
sigma <- 1
# parameters for the distribution we simulate from

par(mfrow=c(5,5))
x<-trunc(seq(from=5,to=n, length=20))
#vector of Ns

y<-vector(mode = "numeric")
#vector to store the mean correlations

k<- 1
#index for y

for (N in x) {
# loop over a range of N

    dt <- matrix(nrow=n,ncol=N)

    J <- vector(mode = "numeric")
    # vector to store the simulated largest absolute 
    # correlations for each N

    for (j in 1:ns) {
    # for each N, simulated ns times    

      for (i in 1:N) {
        dt[,i] <- rnorm(n,mu,sigma)
      }
      # perform the simulation

      M<-matrix(cor(dt),nrow=N,ncol=N)
      m <- M
      diag(m) <- NA
      J[j] <- max(abs(m), na.rm=TRUE)   
      # obtain the largest absolute correlation
      # these 3 lines came from stackoverflow
  }

    hist(J,main=paste("N=",N, " n=",n, " N(0,1)", "\nmean=",round(J[j],4))) 
    y[k]<-mean(J)
    k=k+1
}

lm1 <- lm(y~log(x))
summary(lm1)

logx_sq=log(x)^2
lm2<-lm(y~log(x)+logx_sq)
summary(lm2)
# linear models for these simulations

# Jiang 2004 paper, computation:

gamma = 0.5772
yy <- vector(mode = "numeric")
yy <- sqrt((2*log((x^2)/(sqrt(8*pi)*n^2)) + 2*gamma-(-4*log(n)+log(log(n))))/n)


plot(x,yy)
# plot the simulated correlations
points(x,y,col='red')
# add the points using the expectation
$\endgroup$
  • $\begingroup$ See my comments to the other answer, which may (or may not) help explain some of the discrepancies you note. $\endgroup$ – cardinal Apr 5 '12 at 18:03

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.