Symmetry and Reversal of Walk Paths

Two Symmetries of a Simple Walk

For a simple symmetric walk, every finite sequence of up-steps and down-steps has the same probability. This makes certain path transformations especially useful: they pair paths of equal probability and turn one endpoint or path event into another. Two transformations must be kept distinct. Negating a path changes the sign of every position. Reversing the order of the increments rearranges the steps while preserving their total sum.

Work on the probability space \((\Omega,\mathcal{F},\mathbb{P})\), where \(\Omega=\{-1,+1\}^{\{1,2,\ldots\}}\), \(\mathcal{F}\) is the product sigma-field, and the coordinates \(\xi_1,\xi_2,\ldots\) are independent with \(\mathbb{P}(\xi_r=1)=\mathbb{P}(\xi_r=-1)=\tfrac12\). Set \(X_0=0\) and \(X_n=\sum_{r=1}^n\xi_r\) for \(n\ge1\). This is a discrete-time Markov chain on \(S=\mathbb{Z}\). From every \(i\in\mathbb{Z}\), its transition probabilities are \(p_{i,i+1}=\tfrac12\) and \(p_{i,i-1}=\tfrac12\), with all other entries zero; each row sums to \(\tfrac12+\tfrac12=1\).

For a fixed integer \(n\ge1\), a path is specified by its increment word \((\xi_1,\ldots,\xi_n)\), or equivalently by its positions \((X_0,\ldots,X_n)\). Each specified word has probability \(2^{-n}\). The endpoint is \(X_n=\sum_{r=1}^n\xi_r\). Thus, if \(k\) is an integer with the same parity as \(n\) and \(|k|\le n\), then reaching \(k\) requires \((n+k)/2\) up-steps. There are \(\binom{n}{(n+k)/2}\) such words, so \(\mathbb{P}(X_n=k)=2^{-n}\binom{n}{(n+k)/2}\); if the parity or size condition fails, that probability is zero.

Each transformation is a bijection on the \(2^n\) possible length-\(n\) words. Because every word has probability \(2^{-n}\), each bijection preserves probabilities. The theorem below records what the transformations do to endpoints and path events.

Proof. Fix \(n\). The map from a word \((\xi_1,\ldots,\xi_n)\) to \((-\xi_1,\ldots,-\xi_n)\) is its own inverse, so it is a bijection. It takes the endpoint \(\sum_{r=1}^n\xi_r\) to \(-\sum_{r=1}^n\xi_r\). Each word and its image both have probability \(2^{-n}\). Therefore the words ending at \(k\) are paired bijectively with words ending at \(-k\), proving (1), including \(k=0\). The reversal map \((\xi_1,\ldots,\xi_n)\mapsto(\xi_n,\ldots,\xi_1)\) is also its own inverse and preserves the sum of the increments. It pairs the words in \(A\) with the words in \(R(A)\), again with probability \(2^{-n}\) per word, proving (2). If a condition specifies the first \(r\) increments, reversal places those specified increments, in reverse order, among the last \(r\) increments. This is a direct consequence of the definition of the map. \(\square\)

Using the Bijections

Path Events and a Common Pitfall

The bijections apply to sets of paths, not only to endpoint events. A path event can specify any finite collection of increments or positions. To use a symmetry correctly, transform the entire condition: under sign change, every specified position changes sign; under increment-order reversal, initial increments become final increments and intermediate positions change according to \(X_n-X_{n-j}\). A statement about the endpoint alone does not determine what happens to a more detailed path condition.

Proof. The sign-change map and reversal map are each bijections on the finite set of length-\(n\) words. For either map, every word has probability \(2^{-n}\), and its image has the same probability. Summing these equal word probabilities over the words in \(A\) and their images gives equal event probabilities. If \(A\) is empty, both sums are zero and the conclusion still holds. \(\square\)

A frequent error is to treat reversing increments as if it negated the endpoint. For example, for the word \((+1,+1,-1,+1)\), the endpoint is \(2\). A mistaken calculation might say that reversal produces endpoint \(-2\), then identify reversal with negation. But the reversed word is \((+1,-1,+1,+1)\), and its sum is \(1-1+1+1=2\). It is negation that changes the sum to \(-2\). The correction is to write the transformed increments first and add them: reversal changes their order, while sign change changes their signs.

These symmetries are useful because they let one compute a probability for whichever version of an event is easier to count. For instance, an event about the first few increments can be transferred to a condition on the last few increments without changing the endpoint or probability. Sign change can transfer a condition involving positive positions to the corresponding condition involving negative positions. In either case, the bijection supplies the justification; symmetry should not be assumed for a path event until its transformation has been specified.