Defining the Simple Symmetric Walk

From Independent Steps to a Walk

A random walk turns a sequence of random steps into a process of positions. For the simple symmetric walk on the integers, each step moves exactly one unit to the right or one unit to the left, with equal probability, and each new step is independent of the earlier ones. This simple construction lets us calculate a path one step at a time and find the probability of any specified finite sequence of steps.

Work on the probability space \((\Omega,\mathcal{F},\mathbb{P})\), where \(\Omega=\{-1,+1\}^{\{1,2,\ldots\}}\) is the set of infinite step sequences, \(\mathcal{F}\) is the product sigma-algebra, and \(\mathbb{P}\) is the product probability measure giving each coordinate probability \(\tfrac12\) of either sign. Let \(\xi_k\) be the \(k\)th coordinate, so the random variables \((\xi_k)_{k\ge1}\) are independent and identically distributed, with \(\mathbb{P}(\xi_k=1)=\mathbb{P}(\xi_k=-1)=\tfrac12\). The time index is discrete, \(n\ge0\), the state space is \(S=\mathbb{Z}\), and the walk starts at the origin.

The increments \(\xi_k\) are the steps; the values \(S_n\) are the positions after \(n\) steps. A path records positions at successive times, including \(S_0\). Thus a step of \(+1\) adds one to the current position, and a step of \(-1\) subtracts one. The same position can occur at more than one time, because later steps can undo earlier ones.

For conditioning, use the natural filtration \(\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). Since \(S_0=0\), this is also the information generated by the positions observed through time \(n\): each position is a sum of the increments, and each increment is the difference \(S_k-S_{k-1}\).

Probabilities of Step Sequences

Proof. For \(n\ge1\), independence gives \(\mathbb{P}(\xi_1=a_1,\ldots,\xi_n=a_n)=\prod_{k=1}^{n}\mathbb{P}(\xi_k=a_k)\). Each factor is \(\tfrac12\), whether \(a_k=1\) or \(a_k=-1\), so the product is \((\tfrac12)^n=2^{-n}\). The event specifying no increments imposes no restriction on \(\Omega\); it is all of \(\Omega\), with probability \(1\). \(\square\)

This result concerns a fully specified, ordered sequence: it says that a particular sequence of \(n\) steps has probability \(2^{-n}\). If an event allows several sequences, its probability is the sum of their probabilities, because the distinct specified sequences are disjoint events. Each sequence must be counted once, and the same length must be used when assigning its probability.

The One-Step Transition Rule

The increment construction also specifies the probability of the next position, conditional on the positions already observed. From the current position \(i\), the walk moves to \(i+1\) with probability \(\tfrac12\), to \(i-1\) with probability \(\tfrac12\), and nowhere else in one step. In transition-kernel notation, \(p_{ij}=\mathbb{P}(S_{n+1}=j\mid S_n=i)\); the rule does not depend on \(n\).

Proof. By definition, \(S_{n+1}=S_n+\xi_{n+1}\). The value \(S_n\) is determined by \(\mathcal{F}_n\), while \(\xi_{n+1}\) is independent of \(\mathcal{F}_n\) and takes each of \(+1\) and \(-1\) with probability \(\tfrac12\). Thus, conditional on \(\mathcal{F}_n\), the only possible next positions are \(S_n+1\) and \(S_n-1\), each with probability \(\tfrac12\). This gives the displayed conditional probability. Since its value depends on the past only through the current position \(S_n\), it is the Markov property. Since the rule is the same for every \(n\), the chain is time-homogeneous. \(\square\)

The transition probabilities are row-stochastic: for every state \(i\), the two distinct destinations \(i+1\) and \(i-1\) have probabilities summing to \(\tfrac12+\tfrac12=1\), and every other destination has probability \(0\). The state space is infinite, so the transition rule is specified by its formula rather than by displaying an infinite matrix.

What the Definition Does—and Does Not—Say

The construction defines a process through its increments, not by declaring that each position is an independent draw. Positions accumulate the effects of all previous steps. In fact, the relation \(S_{n+1}=S_n+\xi_{n+1}\) means that once the current position and the next increment are known, the next position is fixed.

The increments are independent and identically distributed; the positions are generally dependent. For example, \(S_2=\xi_1+\xi_2\) contains \(\xi_1\), which is also part of \(S_1=\xi_1\). The event \(S_1=1\) therefore tells us something about \(S_2\): if \(S_1=1\), then \(S_2\) can only be \(0\) or \(2\), not every integer. Independence belongs to the step variables, not to the position variables.

Another useful distinction is between a particular sequence and a condition on a sequence. The probability of one prescribed sequence of \(n\) signs is \(2^{-n}\). An event such as “the first two signs agree” includes more than one sequence, so its probability must include all the allowed cases. When the cases are disjoint, add their probabilities; when the event is naturally described using independence, compute it by conditioning or by multiplying the relevant probabilities.

Common mistake. A frequent error is to assign probability \(\tfrac12\) to a prescribed sequence of several steps, as if specifying the first step determined the probability of the whole sequence. For example, the three-step sequence \((+1,-1,+1)\) has probability \(\tfrac12\), not \(\tfrac18\), according to this incorrect calculation. The correction is to include one factor for every specified independent increment: \((\tfrac12)(\tfrac12)(\tfrac12)=\tfrac18\). The answer also checks against the sequence formula \(2^{-3}=\tfrac18\).

To define or compute a short path reliably, proceed in this order:

1. Write down the increments in their time order.
2. Start with \(S_0=0\) and add each increment to the preceding position.
3. For a specified sequence of \(n\) signs, use probability \(2^{-n}\).
4. If an event allows several sequences, identify its disjoint cases before adding their probabilities.

These steps use only the defining independent fair increments and the sum that constructs each position. They establish the basic language for studying the walk without needing a formula for its endpoint distribution or a method for counting paths by their up-steps.