# What does a random walk do exactly?

To be honest, I have read many websites and answers regarding to this question, and none explained it in simple words which are understandable. What I want to do is to understand what a random walk does, and how it can be used for Gene Set Enrichment Analysis.

There is a published paper here http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3205944/ however, I could not really understand it.

Can someone please explain what it does in simple words?

• Those are two very different questions! – Alexis Mar 23 '15 at 21:25
• @Alexis I accepted your revise, I hope now it is clear ! – Learner Mar 23 '15 at 21:45
• @Nemo I removed unrelated tags and added time-series tag. Feel free to edit my changes or add additional tags but tags like r, statistical-significance, or mathematics seem unrelated in here. – Tim Mar 23 '15 at 22:29

A random walk is a series of measurements in which the value at any given point in the series is the value of the previous point in the series plus some random quantity.

For example, suppose you flip a fair coin in a series of tosses, and every time the coin comes up heads you add 1 to the previous value of your serial variable, and every time the coin comes up tails you subtract 1 from the previous value of your serial variable. If the starting value is 0, and if you flip the following sequence of coin tosses:

T H T T T H H H T T H T H T H


The the random walk, $y$ based on these values as described above would be:

0 -1 0 -1 -2 -3 -2 -3 -1 -2 -2 -1 -2 -1 -2 -1


So the value of $y$ is:

$$y_{t} = y_{t-1} + 2\mathcal{Bernoulli}(0.5)–1$$

The distribution of $y$ is dependent on time $t$, giving some interesting properties to a sample of $y$ across different times:

1. The mean of $y$ is undefined. This may seem counter-intuitive, since you might expect that the heads and tails of a balanced coin are centered on zero. This is true as far as it goes, but zero was just an arbitrary starting value of $y$. So there's no real mean!

2. The variance of $y=t$. As time (the number of flips) increases, the variance also increases. For example, at the first flip ($t=1$), the possible values are $1$ or $-1$, and indeed the variance then is 1. But at the second flip ($t=2$) the possible values are $2$, $0$ or $-2$, and the variance is equal to 2. For an infinite number of flips (at $t=\infty$, when the range of all possible values of $y$ goes from $-\infty$ to $\infty$), the variance is infinite.

These two facts play havoc on trying to draw inferences about the distribution of $y$ (rather than $y_{t}$ for a given $y_{0}$) given only a sample when using the basic tools of statistical inference. (How can a finite $\bar{y}$ estimate undefined? How can a finite $s^{2}_{y}$ estimate $\sigma^{2}_{y}=\infty$?)

There are many kinds of random walk, and more generally, of autogregressive process (i.e. any variable that depends in some way on its previous values). The example here uses a simple Bernouli random variable (the coin toss), but one could:

• add a normally distributed random value to successive values of $y$ instead... or indeed a random value drawn from any sort of distribution;
• make the value of $y$ at some point in time depend on previous values of $y$ from more than one point in time (e.g. $y_{t} = y_{t-1} + y_{t-2} + \text{Something Random}$);
• pair the value of $y$ with a random value of $x$ to create a two-dimensional random walk;
• make $y_{t}$ some fancy function of $y_{t-1}$, a simple example is $y_{t} = \alpha y_{t-1} + \text{Something Random}$, where $|\alpha| < 1$, meaning that the memory of any specific moment of $y$ decays over time (with the memory lasting longer the closer $|\alpha|$ is to 1)—per Alecos' comments, this would simply be 'autoregressive' (a pure random walk would have $|\alpha|=1$);
• do lots of other things to make random walks and/or autoregressive processes more complex.

But they are all the Dickens to try and analyze using the basic methods. Which is why we have cointegrating regressions and error correction models and other time series analysis techniques for dealing with these kind of data (which we sometimes refer to as 'non-integrated', 'long-memoried' or 'unit root' among other labels, depending on the details).

The origin of the term "random walk" is from a pair of very brief letters to Nature in 1905.

References
Pearson, K. (1905). Letters to the Editor: The problem of the random walk. Nature, 72(1865):294.

Pearson, K. (1905). Letters to the Editor: The problem of the random walk. Nature, 72(1867):342.

• You write "A random walk is a series of measurements in which the value at any given point in the series depends on values of the previous points in the series." But this describes any autoregressive process, and not all autoregressive processess are random walks. Since obviously you know the subject matter, I believe it would be helpful if you revised this statement in order to bring into the surface what is the unique characteristic(s) of a random walk. – Alecos Papadopoulos Mar 24 '15 at 1:14
• @AlecosPapadopoulos TY! Please help me out here... don't actually have that deep a familiarity with the subject. How would you suggest I differentiate random walks from autoregressive processes? – Alexis Mar 24 '15 at 1:53
• Gladly. There is a large literature on random walk(s), the subject is very diverse. But at the first level, what distinguishes a random walk is that all past values of each step contribute with their full value to the current value of their sum (which is the random walk).In an autoregressive process, usually the effect of the past gradually dies out. You essentially discuss this in your post Also now I re-read your answer, perhaps you want to re-think the use of the word "population": each $y_t$ has a different distribution, so in what sense $y_t, y_{t+1}...$ belong to the same population? – Alecos Papadopoulos Mar 24 '15 at 2:35
• @Nemo You get a specific type of behavior (usually over time): the past fully determines where you are -but, the evolution path does not affect where you will be next. How the process arrived at its current position, doesn't matter for the future. – Alecos Papadopoulos Mar 24 '15 at 10:45
• A random walk is really not "similar to a Kolmogorov-Smirnov test". A derivation of the asymptotic distribution of the K-S test statistic under the null hypothesis uses a notion related to a random walk. The point of drawing that connection seems from my quick look to be to motivate the development in the next section (the GSEA test). I'm not sure that was a good choice; it seems to have led you into confusion rather than helped you see what was going on. I suggest you try to understand random walks separately before trying to understand the connection between random walks and GSEA. – Glen_b -Reinstate Monica Mar 29 '17 at 9:07