3
$\begingroup$

Suppose I have a pseudo random generator rand, I am using it to generate two random variables X and Y as follows:

for(i = 0; i < N; ++i) {
   x = rand();
   y = rand();
}

Question: in theory, can X and Y be uncorrelated? If yes, I want a simple example with proof (a simple rand procedure that produce uncorrelated X and Y). If no, please tell me the reason.

Naively speaking, since X and Y are generated by a deterministic way, they must be correlated a little bit in theory.

$\endgroup$
  • 4
    $\begingroup$ It's so easy to construct counterexamples (that is, pseudorandom number generators that are perfectly uncorrelated) that I suspect you might be using "correlated" in a more colloquial sense than is usual in statistics. Could you clarify what you mean by "correlated"? $\endgroup$ – whuber Jan 1 '17 at 3:40
  • 2
    $\begingroup$ This may have to do with the fact that pseudo-random number generators eventually cycle although good one go a very long time before cycling. What this means is that after a very long sequence, that long sequences will repeat. So let's say the cycle length is c then the first "random" number generated will be identical to the c + 1st and the second with the c + 2nd etc. $\endgroup$ – Michael R. Chernick Jan 1 '17 at 4:08
  • 1
    $\begingroup$ That would mean that if x is the first and y is the c + 1st they are identical. But x and y are realizations, so it doesn't mean correlated in the statistical sense. If X and Y were random variables that are identical this could be viewed as perfect correlation. $\endgroup$ – Michael R. Chernick Jan 1 '17 at 4:13
  • $\begingroup$ @whuber I'm using it mathematically, that is $Cov(X,Y)=0$ $\endgroup$ – fizis Jan 2 '17 at 7:54
  • $\begingroup$ @MichaelChernick $Corr(X,Y)$ can be calculated from the realizations, in practice. If they are perfect correlated, they should equal to 1. So, what do you imply when we cycle enough iterations? the value goes to 1? $\endgroup$ – fizis Jan 2 '17 at 8:04
5
$\begingroup$

If we consider a standard pseudo-random generator, like runif in R, it produces a sequence $(x_t)$ of values on $(0,1)$ through a deterministic transform, $x_t=\Psi(x_{t-1})$. In that practical sense, the outcomes of a pseudo-random generation are correlated, as noted by W. Huber. And one does not need to wait for the period of the random generator to see perfect correlation between $x_t$ and $x_{t+c}$. But, since the sequence is deterministic, it enjoys no randomness and correlation in the probabilistic sense remains undefined.

However, the same standard pseudo-random generators are reproducing the simulation of an iid random U(0,1) sequence, in the sense that they withstand any battery of statistical tests on this null hypothesis, "the sequence is an iid random U(0,1) sequence".

$\endgroup$
  • 1
    $\begingroup$ @X'ian Bill Huber did not say that the outcome of pseudo-random number generation are correlated in a practical sense. All he said was that he suspected the OP had a different understanding of correlated from the standard statistical concept and asked for clarification. $\endgroup$ – Michael R. Chernick Jan 1 '17 at 14:38
  • $\begingroup$ Xi'an I agree that pseudo-random number generators provide a deterministic sequence. The last I remember the congruential pseudo-random number generators were favored because they have very long cycle times. Correlation in the statistical sense doesn't apply. What you mean by correlation in the practical sense and what the OP means by correlation is still not clear. I would say that good ones "look" like random sequences and will pass most statistical tests for uniformity and randomness. The idea I expressed in my comment differs from yours, $\endgroup$ – Michael R. Chernick Jan 1 '17 at 14:50
  • $\begingroup$ The comment was only intended to see what the OP was driving at. Fundamentally I think we are in agreement but may differ in semantics. $\endgroup$ – Michael R. Chernick Jan 1 '17 at 14:52
  • 2
    $\begingroup$ @Mich is correct: I was not referring to standard PRNs, but only to the question as asked. As an example of what I had in mind, here is an R implementation of rand. The output is always zero correlation and x and y individually are practically indistinguishable from iid uniform variates. rand <- function() { if (length(SEED)==0) { SEED <<- runif(2); SEED <<- c(SEED, SEED * c(-1,1)) } x <- SEED[1]; SEED <<- SEED[-1]; return(x) } N <- 1e3; x <- y <- rep(NA_real_, N); SEED <- double(); for (i in 1:N) { x[i] <- rand(); y[i] <- rand(); } (cor(x,y)) $\endgroup$ – whuber Jan 1 '17 at 18:29
  • $\begingroup$ I can't understand " perfect correlation between xt and xt+c." in your answer, if they are perfectly correlated, then $Corr(X,Y)$ calculated should equal to 1, but this is not the case. $\endgroup$ – fizis Jan 2 '17 at 8:07

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.