Reflecting a Walk at Its First Visit
A walk that reaches a level and later finishes below it has a useful counterpart: keep the path unchanged up to its first visit to the level, then reverse every later step. The endpoint moves to the opposite side of the level. For a simple symmetric walk, this operation pairs paths of equal probability, so counting or computing the probability of one set of paths reduces to counting or computing the other.
Work on the probability space \((\Omega,\mathcal{F},\mathbb{P})\) supporting independent increments \((\xi_k)_{k\ge1}\), each equal to \(+1\) or \(-1\) with probability \(\tfrac12\). For a starting state \(x\in\mathbb{Z}\), define the simple symmetric walk by \(S_0=x\) and \(S_n=x+\sum_{k=1}^n\xi_k\), with state space \(\mathbb{Z}\) and discrete time \(n\ge0\). Its natural filtration is \(\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). Fix an integer \(a>x\), and define \(T_a=\inf\{n\ge0:S_n=a\}\), where \(\inf\varnothing=\infty\). This is a stopping time for the stated filtration: whether \(T_a\le n\) is determined by the first \(n\) increments.
The reflected endpoint is \(2a-y\), the point obtained by mirroring \(y\) across \(a\). Since \(y<a\), this endpoint is strictly greater than \(a\). The theorem says that paths which reach \(a\) and end at \(y\) correspond one-to-one with paths that end at the reflected point.
Proof. Fix \(n\), and consider any path \((s_0,\ldots,s_n)\) starting at \(x\), with steps of size one, that reaches \(a\) by time \(n\) and ends at \(y<a\). Let \(t\) be its first time at \(a\), so \(t=T_a\). Construct a new path by setting \(s'_k=s_k\) for \(k\le t\), and \(s'_k=2a-s_k\) for \(t<k\le n\). Up to time \(t\) the path is unchanged. After time \(t\), each step is negated: if \(s_k-s_{k-1}\) is \(+1\) or \(-1\), then \(s'_k-s'_{k-1}=-(s_k-s_{k-1})\), which is also \(+1\) or \(-1\). Thus the transformed path is a valid walk, its first visit to \(a\) is still at time \(t\), and its endpoint is \(s'_n=2a-y\).
This transformation is its own inverse. Indeed, the transformed path has the same first visit time \(t\), and reflecting its steps after \(t\) again restores the original path. Conversely, every path starting at \(x<a\) and ending at \(2a-y>a\) must visit \(a\): a path with steps of size one cannot move from below \(a\) to above \(a\) without being at \(a\). Reflecting that path after its first visit gives a path ending at \(y\). Hence the transformation is a bijection between the two specified path sets. Every length-\(n\) path has probability \(2^{-n}\), because its \(n\) independent steps each have probability \(\tfrac12\). The two sets therefore have equal probabilities, proving the identity. If either path set is empty, the bijection shows the other is empty as well. \(\square\)
The key hypothesis in the probability statement is symmetry of the step probabilities: reflecting the tail preserves the probability of each path. The path transformation itself still produces a valid nearest-neighbor path without that hypothesis, but its probability need not be preserved. The endpoint identity is often applied by first fixing the endpoint below the barrier, then replacing the event of reaching the barrier and ending there with an unrestricted endpoint probability.
Worked Example: A Path and Its Reflection
Start at \(0\), set the barrier to \(a=2\), and consider the six-step path with increments \(+1,+1,-1,-1,-1,+1\). Its successive positions are \(0,1,2,1,0,-1,0\). It first reaches \(2\) at time \(2\) and ends at \(y=0\). Reflecting the steps after time \(2\) changes the final four increments to \(+1,+1,+1,-1\), so the reflected path has increments \(+1,+1,+1,+1,+1,-1\) and positions \(0,1,2,3,4,5,4\). Its endpoint is \(4=2a-y\), as claimed. Both paths have probability \(2^{-6}=\tfrac1{64}\).
Now compute the probability of all six-step paths that reach \(2\) and end at \(0\). The theorem reduces it to \(\mathbb{P}_0(S_6=4)\). To end at \(4\) after six steps requires five up-steps and one down-step. There are \(\binom65=6\) such paths, each with probability \(\tfrac1{64}\), so $$ \mathbb{P}_0(T_2\le6,\ S_6=0)=\mathbb{P}_0(S_6=4)=\frac6{64}=\frac3{32}. $$
Check by splitting according to the first visit. To end at \(0\) after reaching \(2\), the first visit to \(2\) can occur at time \(2\) or \(4\); it cannot occur at time \(6\), since the endpoint is \(0\). If the first visit is at time \(2\), the first two steps must be \(++\). The remaining four steps must have net displacement \(-2\), requiring one up-step and three down-steps, which can be arranged in \(\binom41=4\) ways. If the first visit is at time \(4\), the first four steps can be \(-+++\) or \(+-++\): these are the two paths that first reach \(2\) at time \(4\). The final two steps must both be down. The total is \(4+2=6\) paths, giving \(6/64=3/32\), in agreement with reflection.
From Endpoint Identities to Hitting Probabilities
The reflection principle also gives a formula for the probability of reaching the barrier by a fixed time. Partition the event \(\{T_a\le n\}\) by the endpoint \(S_n\). If \(S_n\ge a\), the path must have reached \(a\), because it starts below \(a\) and has steps of size one. If the endpoint is \(y<a\), the reflection theorem applies. Therefore $$ \mathbb{P}_x(T_a\le n) = \mathbb{P}_x(S_n\ge a) + \sum_{y<a}\mathbb{P}_x(S_n=2a-y). $$
The sum only needs to include endpoints \(y\) that are attainable at time \(n\); all other terms are zero. For example, a walk started at \(x\) can end only at an integer \(r\) with \(|r-x|\le n\) and \(r-x\) having the same parity as \(n\). This lattice restriction is important: the reflection formula remains true when an endpoint is unattainable, but it then contributes zero.
Proof. The events \(\{S_n=r\}\), over integers \(r\), are disjoint and cover the sample space. Among paths with \(S_n\ge a\), every path has \(T_a\le n\), so these paths contribute \(\mathbb{P}_x(S_n\ge a)\). For each endpoint \(y<a\), the paths with \(T_a\le n\) and \(S_n=y\) contribute \(\mathbb{P}_x(S_n=2a-y)\) by the reflection theorem. Adding these disjoint contributions over the possible endpoints below \(a\) proves the formula. Only finitely many endpoints are possible at a fixed time \(n\), so the sum is finite after zero terms are omitted. \(\square\)
Worked Example: Probability of Reaching Level Two by Time Five
For a walk started at \(0\), compute \(\mathbb{P}_0(T_2\le5)\). At time \(5\), the attainable endpoints are \(-5,-3,-1,1,3,5\). For a simple symmetric walk, an endpoint \(r\) is reached by choosing the number \((5+r)/2\) of up-steps, so its probability is \(\binom{5}{(5+r)/2}/2^5\) when that number is an integer between \(0\) and \(5\).
Endpoints at or above \(2\) are \(3\) and \(5\). Their probabilities are \(\binom54/32=5/32\) and \(\binom55/32=1/32\), giving \(6/32\). The endpoints below \(2\) reflect as follows: \(1\) maps to \(3\), with probability \(5/32\); \(-1\) maps to \(5\), with probability \(1/32\); \(-3\) maps to \(7\), and \(-5\) maps to \(9\). Endpoints \(7\) and \(9\) are unattainable in five steps from \(0\), so those probabilities are zero. Thus $$ \mathbb{P}_0(T_2\le5) =\frac6{32}+\frac5{32}+\frac1{32} =\frac{12}{32} =\frac38. $$
Check by first-visit times. The first visit to \(2\) can occur at time \(2\) or \(4\) by time \(5\). If it occurs at time \(2\), the first two steps are \(++\), and the remaining three steps are unrestricted, giving \(2^3=8\) paths. If it occurs at time \(4\), the first four steps are either \(-+++\) or \(+-++\), and the fifth step is unrestricted, giving \(2\cdot2=4\) paths. There are \(8+4=12\) successful paths out of \(2^5=32\), again giving \(12/32=3/8\).
When Reflection Does Not Preserve Probability
The bijection is a statement about paths, but the equality of probabilities also uses the equal weighting of all paths of the same length. In a biased walk, reflecting the tail swaps up-steps and down-steps. The transformed path is still valid, but paths with different numbers of up-steps generally have different probabilities.
Worked Example: A Biased Walk Breaks the Unweighted Identity
Suppose each step is \(+1\) with probability \(\tfrac23\) and \(-1\) with probability \(\tfrac13\), independently. Start at \(0\), take \(a=1\), \(y=0\), and \(n=2\). The only two-step path that reaches \(1\) and ends at \(0\) is \(+-\), with probability \(\tfrac23\cdot\tfrac13=\tfrac29\). Its reflected path is \(++\), which ends at \(2a-y=2\) and has probability \(\tfrac23\cdot\tfrac23=\tfrac49\). Thus $$ \mathbb{P}_0(T_1\le2,\ S_2=0)=\frac29 \qquad\text{but}\qquad \mathbb{P}_0(S_2=2)=\frac49. $$
The path map remains a bijection, but the two paths do not have equal weight. Applying the symmetric-walk probability identity to this biased walk would therefore give the wrong answer. The correction is to track how reflecting the tail changes the number of up-steps and hence the path probability.
Common mistake. One might argue that reflection always gives equal probabilities because it is a one-to-one map. A bijection alone preserves the number of paths, not their probabilities. In the biased example, the one path on each side has probabilities \(\tfrac29\) and \(\tfrac49\), respectively. The correction is to check the probability assigned to each path under the model: for a simple symmetric walk every length-\(n\) path has probability \(2^{-n}\), so the bijection does preserve probability; for a biased walk it generally does not.
The principle is useful whenever a barrier event is difficult to describe directly but its reflected endpoint is easy to compute. Its scope here is specific: a nearest-neighbor walk, a fixed level first reached before the endpoint, and equal probabilities for the two step directions. The first-hit rule matters: reflecting at an arbitrary visit need not define the same bijection, because the inverse operation must identify the same cut point on the path.
Check Your Understanding
For each question, specify the starting state, barrier, endpoint, and time before applying reflection. Keep unattainable endpoints as zero-probability cases.
- For a simple symmetric walk from \(0\), what endpoint corresponds under reflection to paths that hit \(a=3\) by time \(8\) and end at \(y=1\)?
- Use reflection to compute \(\mathbb{P}_0(T_1\le4,\ S_4=0)\). Show the endpoint probability calculation.
- Why must every path starting below \(a\) and ending strictly above \(a\) visit \(a\), given that steps have size one?
- For a simple symmetric walk from \(0\), list the attainable endpoints at time \(4\). Which of them are at or above \(2\)?
- In the biased two-step example, identify the original path and its reflected path, and explain why their probabilities differ.