What is the autocorrelation for a random walk? Seems like it is really high, but this is counterintuitive to me. Can somebody please explain? I am very confused by this issue and would appreciate a detailed, insightful explanation.
Thanks a lot in advance!
 A: (I wrote this as an answer to another post, which was marked as a duplicate of this one while I was composing it; I figured I'd post it here rather than throw it away. It looks like it says quite similar things to whuber's answer but it is just different enough that someone might get something out of this one.)
A random walk is of the form $y_t = \sum_{i=1}^t \epsilon_i$
Note that $y_t = y_{t-1}+ \epsilon_t$
Hence $\text{Cov}(y_t,y_{t-1})=\text{Cov}(y_{t-1}+ \epsilon_t,y_{t-1})=\text{Var}(y_{t-1})$.
Also note that $\sigma^2_t=\text{Var}(y_t) = t\,\sigma^2_\epsilon$
Consequently $\text{corr}(y_t,y_{t-1})=\frac{\sigma_{t-1}^2}{\sigma_{t-1}\sigma_t} =\frac{\sigma_{t-1}}{\sigma_t}=\sqrt{\frac{t-1}{t}}=\sqrt{1-\frac{1}{t}}\approx 1-\frac{1}{2t}$.
Which is to say you should see a correlation of almost 1 because as soon as $t$ starts to get large, $y_t$ and $y_{t-1}$ are almost exactly the same thing -- the relative difference between them tends to be fairly small.
You can see this most readily by plotting $y_t$ vs $y_{t-1}$.

We can now see it somewhat intuitively -- imagine $y_{t-1}$ has drifted down to $-20$ (as we see it did in my simulation of a random walk with standard normal noise term). Then $y_t$ is going to be pretty close to $-20$; it might be $-22$ or it might be $-18.5$ but it's nearly certain to be within a few units of $-20$. So as the series drifts up and down, the plot of $y_t$ vs $y_{t-1}$ is going to nearly always stay within quite a narrow range of the $y=x$ line... yet as $t$ grows the points will cover greater and greater stretches along that $y=x$ line (the spread along the line grows with $\sqrt{t}$, but the vertical spread remains roughly constant); the correlation must approach 1.
A: In the context of your previous question, a "random walk" is one realization $(x_0, x_1, x_2, \ldots, x_n)$ of a binomial random walk.  Autocorrelation is the correlation between the vector $(x_0, x_1, \ldots, x_{n-1})$ and the vector of the next elements $(x_1,x_2, \ldots, x_n)$. 
The very construction of a binomial random walk causes each $x_{i+1}$ to differ from each $x_i$ by a constant.  After running the walk for a while, the values of $x_i$ will have wandered away from the initial value $x_0$ and thereby will usually cover a good range, typically proportional to $\sqrt{n}$ in length.  Thus the lag-1 scatterplot of the $(x_i, x_{i+1})$ pairs will consist of points lying only on the lines $y=x\pm 1$, on average being close to the line $y=x$.  The residuals will be close to $\pm 1$.  Therefore, in the vast majority of realizations, the variance of the residuals (about $1$) compared to the variance of the values (roughly on the order of $(\sqrt{n}/2)^2 = n/4$) will be small.  We would expect $R^2$ to be approximately
$$R^2 \approx 1 - \frac{1}{n/4} = 1 - \frac{4}{n}.$$
Here is a picture of $n=1000$ steps in a random walk (on the left) and its lag-1 scatterplot (on the right). Color coding is used to help you find corresponding points in the two plots.  Notice that $R^2$ is very close indeed to $1 - 4/n$ in this case. 


Here is the R code that produced the images.
set.seed(17)
n <- 1e3
x <- cumsum((runif(n) <= 1/2)*2-1)          # Binomial random walk at x_0=0
rho <- format(cor(x[-1], x[-n]), digits=3)  # Lag-1 correlation

par(mfrow=c(1,2))
plot(x, type="l", col="#e0e0e0", main="Sample Path")
points(x, pch=16, cex=0.75,  col=hsv(1:n/n, .8, .8, .2))
plot(x[-n], x[-1], asp=1, pch=16, col=hsv(1:n/n, .8, .8, .2),
     main="Lag-1 Scatterplot",
     xlab="Current value", ylab="Next value")
mtext(bquote(rho == .(rho)))

