Simple Random Walks

Definition Let $0 < p < 1$, and let $Z_1, Z_2, \dots$ be mutually independent random variables with

for every $i$. The variable $Z_i$ is the increment, or step, at time $i$. Starting from a fixed integer $S_0$, the simple random walk is the process $S_0, S_1, S_2, \dots$ given by

Each step moves the walk to a neighboring integer. More generally, the increment of the walk from time $m$ to time $n > m$ is $S_n - S_m = Z_{m+1} + \cdots + Z_n$, and increments over disjoint blocks of steps are independent. On this page the walk starts at $S_0 = 0$ unless a different start is named. When $p = 1/2$ the walk is called symmetric, and some books reserve the name simple random walk for that case.

Definition The position after $n$ steps is $S_n$. For a walk started at $0$, let $K$ be the number of right steps among the first $n$. Then there are $n - K$ left steps, $K \sim \operatorname{Bin}(n, p)$, and $S_n = K - (n - K)$, that is,

Hence, for each integer $k$ with $0 \le k \le n$,

and every other value has probability $0$. For $1 \le m < n$ the increment $S_n - S_m$ depends only on $Z_{m+1}, \dots, Z_n$, so it is independent of the earlier positions $S_1, \dots, S_m$. The positions $S_m$ and $S_n$ themselves are dependent, because $S_n$ contains $S_m$. A walk started at a fixed integer $S_0 = s_0$ has every position shifted by $s_0$.

Definition The drift of a simple random walk is the expected increment

By linearity of expectation, a walk with fixed start $S_0$ has $E[S_n] = S_0 + n(2p - 1)$. The drift is positive when $p > 1/2$, zero when $p = 1/2$ and negative when $p < 1/2$.

Definition Each increment satisfies $Z_i^2 = 1$, so

Because the increments are independent, their variances add, and a walk with fixed start $S_0$ has

and $\operatorname{SD}(S_n) = 2\sqrt{np(1 - p)}$. The same result follows from $S_n = S_0 + 2K - n$, since $\operatorname{Var}(2K) = 4np(1 - p)$. For $1 \le m \le n$ the shared steps give $\operatorname{Cov}(S_m, S_n) = \operatorname{Var}(S_m) = 4mp(1 - p)$. Without independent increments the variance of the sum would also need covariance terms, and a random start would add its own variance and twice its covariance with the sum of the steps.

Definition For a walk started at $0$, the position $S_n = 2K - n$ has the same parity as $n$, which means that $S_n - n$ is even. Also $\lvert S_n \rvert \le n$. So $P(S_n = x) = 0$ unless $x$ is an integer with $\lvert x \rvert \le n$ and $x - n$ even, and since $0 < p < 1$, every such $x$ has positive probability. The support of $S_n$ is $\{-n, -n + 2, \dots, n - 2, n\}$. For a walk started at $S_0$, the same statements hold for the displacement $S_n - S_0$.

Definition A path of length $n$ is a sequence of steps $(z_1, \dots, z_n)$ with each $z_i$ equal to $1$ or $-1$, or equivalently the sequence of positions it produces. If the path has $r$ right steps, independence gives

The endpoint event $\{S_n = x\}$ is the union of the disjoint events for the paths that end at $x$, and all of those paths have the same number of right steps, so its probability is their number times this common probability. The event that $S_j = x$ for some $j$ with $1 \le j \le n$ is a visit event. It contains the endpoint event, together with any paths that reach $x$ before step $n$ and end elsewhere.