# Principal Components of Random Walk

In this blog figure 4 shows that the principal components of a random walk are sinusoidal with increasing frequency for decreasing eigenvalue. Is there an intuitive way of understanding this?

If I generate two independent random walks with a mean of zero, why is there a covariance (or correlation) between these trajectories in the first place?

I actually recently wrote a paper on this subject which will appear at NIPS 2018: https://arxiv.org/abs/1806.08805

My collaborator and I proved that in the limit of an infinite number of dimensions the projection of a random walk onto any PCA component is a sinusoid. You are welcome to read the paper for the proof, but perhaps I can attempt a slightly more intuitive explanation.

The random walk process is a translation invariant process. No matter how many steps you take and how far away you get from the origin, the process that determines the next step is exactly the same. (This is in contrast to an Ornstein-Uhlenbeck process, for example, which is a random walk in a quadratic well. In this case the process that determines what your next step will be depends on your distance from the origin.)

Now, the eigenfunctions of any translation invariant operator are Fourier modes. Why is this? Well, in order to be translation invariant, the eigenfunctions need to be periodic, and in order to be an orthogonal basis, they need to be mutually orthogonal. The set of functions that satisfies these properties is the Fourier basis.

As for your second question about two independent random walks seeming to be correlated, this is just an illusion. Although the projection of the trajectory of both random walks onto their first PCA component will be a cosine, the direction of the first PCA component will be completely random. An an analogy, if you do two random walks, each of 10^6 steps, you can be quite sure that both will end up at a distance of about 1000 from the origin. But the two walks had nothing to do with each other, and furthermore the direction that the walk happened to go will be different each time.

• +1. Very nice! Congratulations on having a paper accepted to NIPS. Actually your paper is more interesting than all six papers I had to review for NIPS this year :) Regarding intuition, it's worth noting that Fourier modes appear every time one does PCA of some roughly translation-invariant smooth data. One well-known example is PCA of natural images (e.g. ImageNet). But it happens quite frequently and I recall quite some confusion about it in some fields; see e.g. nature.com/articles/ng.139 for discussion. – amoeba Sep 19 '18 at 20:57
• BTW, this has come up previously, e.g. here stats.stackexchange.com/questions/90484. I see that there is my answer there from several years ago, and it is very inadequate. I should edit it. Meanwhile, perhaps you'll be interested in answering that question too. – amoeba Sep 19 '18 at 20:58
• Another related thread is stats.stackexchange.com/questions/255548. – amoeba Sep 19 '18 at 21:03
• @amoeba is the idea that in a RW of high dimension, most dimensions will be approximately zero, and only a few dimensions will be large – thus, a linear combination of these few dimensions captures most of the variance? – swedishfished Aug 31 at 4:04
• @amoeba In this sense, isn't it a bit misleading to say each RW is explained by only the first few PC values (suggesting that RWs are low dimensional) since one had no way of knowing previously which of these low dimensions that the RW would take? See e.g. ncbi.nlm.nih.gov/pmc/articles/PMC5913756 – swedishfished Aug 31 at 4:07