Simple Random Walks as Markov Chains

From Step Directions to States

A simple random walk records a position that changes by one unit at each step. It is a useful first example of a Markov chain because its state has a direct interpretation: the current position. The next position depends on that current position and on a new random step, not on the route taken to get there. To specify the model, give the set of possible positions, the initial position or initial distribution, and the probabilities of stepping right and left.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space. Let \((\xi_n)_{n\ge1}\) be independent and identically distributed random variables taking values in \(\{-1,+1\}\), with \(\mathbb{P}(\xi_n=+1)=p\) and \(\mathbb{P}(\xi_n=-1)=q=1-p\), where \(0\le p\le1\). For a fixed initial position \(x_0\in\mathbb{Z}\), define \(X_0=x_0\) and \(X_n=x_0+\sum_{r=1}^n \xi_r\) for \(n\ge1\). Thus \(X_n\) is the position after \(n\) steps. The symmetric simple random walk is the special case \(p=q=\tfrac12\).

To state the Markov property, use the natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\), the information generated by the positions through time \(n\). The Markov property says that, conditional on this history, the distribution of \(X_{n+1}\) depends only on \(X_n\). More precisely, the transition kernel below gives \(\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n)=p_{X_nj}\) almost surely. Conditional probabilities given an individual state \(X_n=i\) are directly defined when \(\mathbb{P}(X_n=i)>0\); the increment construction also defines the transition probabilities for states that are not reached at that time.

The Transition Kernel

If the current position is \(i\), a right step gives \(i+1\), and a left step gives \(i-1\). There are no other possible next positions. With rows indexed by the current state and columns by the next state, the transition matrix \(P=(p_{ij})\) is therefore described by

This is a countably infinite matrix because \(S=\mathbb{Z}\). Every row sums to \(p+q=1\), so it is row-stochastic, including when \(p=0\) or \(p=1\). The initial distribution is the row vector \(\mu_0\) with \(\mu_0(x_0)=1\) and \(\mu_0(i)=0\) for \(i\ne x_0\). In particular, a fixed starting position is an initial distribution concentrated at one state; it is separate from the transition probabilities, which describe what happens from every state.

Proof. The past positions \(X_0,\ldots,X_n\) are functions of \(\xi_1,\ldots,\xi_n\). The increment \(\xi_{n+1}\) is independent of those increments, so it is independent of \(\mathcal{F}_n\). Since \(X_{n+1}=X_n+\xi_{n+1}\), conditional on \(\mathcal{F}_n\) the next position is \(X_n+1\) with probability \(p\), and \(X_n-1\) with probability \(q\). It cannot be any other value. Hence for each \(j\in\mathbb{Z}\), \(\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n)=p\mathbf{1}_{\{j=X_n+1\}}+q\mathbf{1}_{\{j=X_n-1\}}=p_{X_nj}\) almost surely. The right-hand side depends on time only through the current state and uses the same \(p,q\) at every \(n\), so the chain is time-homogeneous. Finally, each row has sum \(p+q=1\), with this equality also valid when either probability is zero. \(\square\)

The theorem explains the modeling choice: the state is the current location, not the most recent direction. The location contains the information needed to determine the next location once a fresh independent step is supplied. The chain can move both right and left from any integer, even if a particular starting position and time make some positions unreachable at that time.

Why the Increment and Chain Descriptions Agree

The independent-increment construction is one way to define the walk. There is also a converse: if a chain starts at a fixed integer and uses the same nearest-neighbor transition probabilities at every state, then its successive directions are independent with the specified probabilities. This makes precise why the transition description captures the simple random walk, rather than merely matching its one-step behavior.

Proof. The transition rule implies \(D_n\in\{-1,+1\}\). For any \(n\ge1\), conditional on the history \(\mathcal{F}_{n-1}=\sigma(X_0,\ldots,X_{n-1})\), the Markov property gives \(\mathbb{P}(D_n=+1\mid\mathcal{F}_{n-1})=p_{X_{n-1},X_{n-1}+1}=p\) and \(\mathbb{P}(D_n=-1\mid\mathcal{F}_{n-1})=q\). To verify independence, take any \(m\ge1\) and any choices \(d_1,\ldots,d_m\in\{-1,+1\}\). Repeated conditioning, starting with \(D_m\), gives \(\mathbb{P}(D_1=d_1,\ldots,D_m=d_m)=\prod_{r=1}^m\mathbb{P}(D_r=d_r)\): at each conditioning step the next direction has conditional probability \(p\) if its specified value is \(+1\), and \(q\) if it is \(-1\), independent of the earlier directions. This product identity for every finite list of direction values is the definition of independence for these discrete random variables. The same conditional probabilities show that each direction has the asserted distribution. No division by a possibly zero event is needed, so the argument also covers \(p=0\) and \(p=1\). \(\square\)

Common Modeling Pitfalls

A frequent error is to make the transition probability depend on the numerical value of the current position when the model specifies a fixed probability for the direction. For the biased walk with \(p=\tfrac23\), a mistaken rule might assign probability \(\tfrac23\) to the move from state \(3\) to state \(4\) but probability \(\tfrac34\) to that move because the current state is \(3\). The second calculation has confused the state label with a probability. The correct row for state \(3\) assigns \(\tfrac23\) to state \(4\) and \(\tfrac13\) to state \(2\), and the row sum is \(\tfrac23+\tfrac13=1\). The identical directional probabilities apply from state \(2\), state \(-4\), and every other integer.

A second error is to restrict the state space to a small interval without changing the model. The simple random walk on \(\mathbb{Z}\) can move beyond any chosen finite interval, so deleting those states would remove possible transitions and leave some row sums below \(1\). For example, restricting the symmetric walk to \(\{0,1\}\) while keeping its original transition probabilities gives only one of the two possible destinations from state \(0\), namely \(1\), and omits the transition to \(-1\). The retained probability in that row is only \(\tfrac12\), not \(1\). A finite-state model would need additional rules at its boundaries; those would describe a different process.

To specify a simple random walk reliably, keep three items distinct: \(S=\mathbb{Z}\) is the state space, \(x_0\) or \(\mu_0\) is the starting law, and \(p,q\) are the probabilities of the two step directions. Checking that every row sums to one confirms that the transition description assigns a full probability distribution to the next state from each current state.