# Definition of random walk as a summation of independent random processes

I have a complete beginner question on random walk. As per this paper

Random walk – the stochastic process formed by successive summation of independent, identically distributed random variable....


I really cannot get past the first line. I thought that the central limit theorem and law of large numbers state that the mean of a large number of independent random processes will approximate a normal process. But the paper seems to indicate that the summation of these random processes is a random walk? So the mean is a normal process but the sum is a random walk? IS this correct?

You need to know what a stochastic process is. In this context, it's just a collection of random variables $(X_0, X_1, X_2, \ldots)$.

Seeing a simple worked example may help. Let's set it up. Suppose you have a collection of independent variables $\mathbf Y = (Y_0, Y_1, \ldots)$, all with the same distribution. For instance, each $Y_i$ could represent the flip of a fair coin using (say) $1$ for heads and $0$ for tails. That's a stochastic process (which we could call a "Bernoulli process").

You can construct new processes out of old. One way is to convert $\mathbf Y$ into its cumulative sum

$$\mathbf X = (Y_0, Y_0+Y_1, Y_0+Y_1+Y_2, \ldots)$$

This is a random walk.

As an example, let's consider a finite random walk of length $3$ based on fair coins. That Bernoulli process $\mathbf Y$ has eight possible outcomes, aka "walks" or "paths," each with equal probabilities of $1/8$:

$$(0,0,0),\ (0,0,1),\ (0,1,0),\ (0,1,1),\ (1,0,0),\ (1,0,1),\ (1,1,0),\ (1,1,1).$$

The associated paths of $\mathbf X$, computed by taking cumulative sums, are therefore

$$(0,0,0),\ (0,0,1),\ (0,1,1),\ (0,1,2),\ (1,1,1),\ (1,1,2),\ (1,2,2),\ (1,2,3).$$

If you like, you can now identify the component variables $X_i$. For instance, $X_0$ takes on the value $0$ four times, for a total probability of $4\times 1/8=1/2$, and the value $1$ four times, for a total probability of $1/2$. $X_1$ takes on the values $0, 1,$ and $2$ with probabilities $1/4, 1/2, 1/4$, respectively. And $X_2$ takes on the values $0,1,2,3$ with probabilities $1/8, 3/8, 3/8, 1/8$, respectively. Notice that these three variables do not have identical distributions. The distributions have different means and variances, too: their means are $1/2, 1, 3/2$ (in order) and their variances are $1/4, 1/2, 3/4$ (in order).

The component variables in a random walk also are dependent. For instance, given that $X_1=0$ (which occurs only in the paths $(0,0,0)$ and $(0,0,1)$), the chance that $X_2=0$ is $1/2$. But given that $X_1=1$, the chance that $X_2=0$ is now zero: it's just not possible. Because these conditional probabilities vary with the value of $X_1$, $X_1$ and $X_2$ are not independent. In fact, no pair of these component variables is independent.

The Central Limit Theorem makes a statement about the distribution of $X_n$ when $n$ gets very large. Besides assuming the $Y_i$ (out of which the $X_n$ are constructed) are independent and identically distributed, it has to assume that this common distribution has a finite variance. The concept of a stochastic process is separate from any idea of limits (which wouldn't even make sense for a finite one, as in the example). The CLT holds only for very special processes.

Both are true.

Imagine I take $T$ steps, $x_t, t=1,...,T$ each normally distributed $x_t \sim N(0,1)$. Before we see any data, and for any $1<s<T$ we have $R_s = \sum_{t=1}^{s}x_t \sim N(0,s)$ - as you suspected.

However suppose we take a peek at the process at some point $s$ and happen to find that $R_s=100$. Then $R_{s+1} \sim N(100,1)$. That is, if we look at successive time steps, their values are linked because they share the same history.

The mean zero case only applies before we look at the data.

There are subtleties when the gap between time steps is reduced to the limit. When we can speak of the $x_t$ though these will generally be random variables not processes, it is $R_s$ which is the process.