Is it true to say that (pseudo) random variables generated by a deterministic procedure must be correlated in some sense? why?

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.

• 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"? – whuber Jan 1 '17 at 3:40
• 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. – Michael R. Chernick Jan 1 '17 at 4:08
• 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. – Michael R. Chernick Jan 1 '17 at 4:13
• @whuber I'm using it mathematically, that is $Cov(X,Y)=0$ – fizis Jan 2 '17 at 7:54
• @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? – fizis Jan 2 '17 at 8:04

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.
• @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)) – whuber Jan 1 '17 at 18:29
• 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. – fizis Jan 2 '17 at 8:07