What does a random walk do exactly?

Question

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?

Answer 1

I am going to try and answer your first question

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.