The Symmetric Simple Walk on the Integer Line

The Walk and Its Hitting Times

The symmetric simple walk moves one unit to the left or right at each step, with equal probability. Its steps are independent, so the walk has no preferred direction. Nevertheless, a zero average step does not by itself tell us whether the walk eventually hits a specified point or returns to where it began. We will answer these questions using finite-interval hitting probabilities and the expected number of visits.

Definition: Let \(X_1,X_2,\ldots\) be independent random variables with \(\mathbb{P}(X_k=1)=\mathbb{P}(X_k=-1)=1/2\). Starting from \(x\in\mathbb{Z}\), define \(S_0=x\) and \(S_n=x+\sum_{k=1}^n X_k\). Write \(\mathbb{P}_x\) for probabilities under this starting point. For a state \(a\), define \(T_a=\inf\{n\geq 0:S_n=a\}\) and \(T_a^+=\inf\{n\geq 1:S_n=a\}\), with the infimum of the empty set equal to infinity.

The time \(T_a\) allows a hit at time zero, while \(T_a^+\) requires at least one step. In particular, \(T_0^+\) is the first positive return time when the walk starts at zero. Since a step changes parity, a walk started at zero can return only at an even time.

Hitting a Boundary Before Another Boundary

Fix an integer \(N\geq 2\), and start at \(i\in\{0,1,\ldots,N\}\). The walk must leave the interior of this finite interval eventually. Indeed, from any interior point, \(N\) consecutive steps to the right force it to reach \(N\), and this particular sequence of steps has probability \(2^{-N}\). In successive blocks of \(N\) steps, the conditional probability of not exiting is therefore at most \(1-2^{-N}\). The probability of staying in the interior for \(mN\) steps is at most \((1-2^{-N})^m\), which tends to zero.

Theorem: For \(0\leq i\leq N\), the probability, starting from \(i\), of hitting \(0\) before \(N\) is \[ \mathbb{P}_i(T_0<T_N)=\frac{N-i}{N}. \]

Proof. Put \(u_i=\mathbb{P}_i(T_0<T_N)\). The boundary values are \(u_0=1\) and \(u_N=0\). For \(1\leq i\leq N-1\), conditioning on the first step gives \[ u_i=\frac12 u_{i-1}+\frac12 u_{i+1}. \] Equivalently, \(u_{i+1}-u_i=u_i-u_{i-1}\), so the successive differences are constant. Thus \(u_i=A+Bi\) for constants \(A,B\). The boundary values imply \(A=1\) and \(B=-1/N\), giving \(u_i=(N-i)/N\). This solution is the hitting probability because the walk exits the interval almost surely, as shown above, and its first-step equations with these boundary values determine it uniquely. \(\square\)

Worked Example: Hitting Zero Before Five

Start the walk at \(2\), and ask for the probability that it hits \(0\) before \(5\). The finite-interval formula with \(N=5\) and \(i=2\) gives \[ \mathbb{P}_2(T_0<T_5)=\frac{5-2}{5}=\frac35. \] The boundary cases agree with the interpretation: starting at \(0\) gives probability \(1\), while starting at \(5\) gives probability \(0\). From \(2\), each step is equally likely to move toward either boundary, and the formula accounts for the unequal distances to them.

Hitting Probabilities on the Infinite Line

The finite-interval result gives an infinite-line probability by moving the distant boundary farther away. Fix \(i\geq 1\), start at \(i\), and consider the events \(A_N=\{T_0<T_N\}\) for \(N>i\). These events increase as \(N\) increases: reaching \(0\) before \(N\) entails reaching \(0\) before any larger boundary \(N+1\). Moreover, their union is exactly \(\{T_0<\infty\}\). If the walk hits zero at a finite time, its path before that time has a finite maximum, so every sufficiently large \(N\) is reached only after the hit of zero.

Theorem: For every \(x,a\in\mathbb{Z}\), \(\mathbb{P}_x(T_a<\infty)=1\).

Proof. First suppose \(x=i>0\) and \(a=0\). By continuity of probability for increasing events and the finite-interval formula, \[ \mathbb{P}_i(T_0<\infty) =\lim_{N\to\infty}\mathbb{P}_i(T_0<T_N) =\lim_{N\to\infty}\frac{N-i}{N} =1. \] For \(i<0\), reflecting every position \(s\) to \(-s\) preserves the step probabilities and turns the problem into the one just proved. If \(x=a\), then \(T_a=0\). Finally, translating the walk by \(-a\) reduces any other pair \(x,a\) to the case of hitting zero. Hence the stated probability is one in every case. \(\square\)

Worked Example: Hitting Zero from Minus Three

Start at \(-3\). For any integer \(M>3\), apply the finite-interval result after reflecting the walk: the probability of reaching \(0\) before \(-M\) is \[ \mathbb{P}_{-3}(T_0<T_{-M})=\frac{M-3}{M}. \] For example, with \(M=12\) this probability is \(9/12=3/4\). As \(M\) increases, the events of hitting zero before \(-M\) increase, and their union is the event of ever hitting zero. Their probabilities tend to \(1\), so the probability of eventually hitting zero from \(-3\) is \(1\).

In particular, if the walk starts at zero, its first step puts it at either \(1\) or \(-1\). From either location it hits zero almost surely. Thus the walk returns to zero almost surely. Translation shows the same for every starting state: the symmetric simple walk on \(\mathbb{Z}\) is recurrent.

Exact Probabilities of Returning at a Fixed Time

Almost-sure return is a statement about whether a return eventually occurs. We can also calculate the probability of being at the origin at a specified time. To be back at zero after \(2n\) steps, the walk must take exactly \(n\) right steps and \(n\) left steps. There are \(\binom{2n}{n}\) such step sequences, all equally likely among \(2^{2n}\) possible sequences.

Proposition: For a walk started at zero, \[ \mathbb{P}_0(S_{2n}=0)=\frac{\binom{2n}{n}}{2^{2n}} \quad(n\in\mathbb{N}_0), \qquad \mathbb{P}_0(S_{2n+1}=0)=0 \quad(n\in\mathbb{N}_0). \]

Proof. At time \(2n\), each path corresponds to a sequence of \(2n\) steps. Its endpoint is zero precisely when the number of \(+1\) steps equals the number of \(-1\) steps, hence when exactly \(n\) steps are \(+1\). Choosing their positions gives \(\binom{2n}{n}\) paths, each of probability \(2^{-2n}\). At an odd time, the sum of the steps is odd, so it cannot be zero. When \(n=0\), the even-time formula gives \(\binom00/1=1\), as required. \(\square\)

Worked Example: Return Probabilities at Times Two and Four

At time \(2\), the walk returns to zero if its steps are \(+1,-1\) or \(-1,+1\). Thus \[ \mathbb{P}_0(S_2=0)=\frac{\binom21}{2^2}=\frac{2}{4}=\frac12. \] At time \(4\), it needs two steps of each sign. There are \(\binom42=6\) possible arrangements among \(2^4=16\) equally likely paths, so \[ \mathbb{P}_0(S_4=0)=\frac{\binom42}{2^4}=\frac{6}{16}=\frac38. \] At time \(3\), return is impossible by parity, so \(\mathbb{P}_0(S_3=0)=0\).

Green-Function Divergence and Recurrence

The Green function at the origin is the expected total number of visits to zero, counting the initial visit at time zero: \[ G(0,0)=\sum_{n=0}^{\infty}\mathbb{P}_0(S_n=0). \] This sum can be infinite even though each individual term is at most one. For the symmetric walk, the fixed-time formula shows that the sum diverges. We first establish a lower bound that makes this divergence explicit.

Theorem: The Green function at the origin for the symmetric simple walk is infinite: \(G(0,0)=\infty\).

Proof. For \(n\geq1\), let \(Y\) be the number of right steps among the first \(2n\) steps. Then \(Y\) has mean \(n\) and variance \(n/2\), and \[ \mathbb{P}_0(S_{2n}=0)=\mathbb{P}(Y=n). \] Chebyshev’s inequality gives \[ \mathbb{P}(|Y-n|\geq\sqrt{2n}) \leq\frac{n/2}{2n}=\frac14. \] Consequently, the interval \(|Y-n|<\sqrt{2n}\) has probability at least \(3/4\). It contains at most \(2\sqrt{2n}+1\) integer values. Among all values of \(Y\), the probability at \(n\) is maximal: for \(0\leq k<2n\), \[ \frac{\mathbb{P}(Y=k+1)}{\mathbb{P}(Y=k)} =\frac{2n-k}{k+1}, \] which is greater than one for \(k<n\) and less than one for \(k\geq n\). Therefore \[ \mathbb{P}_0(S_{2n}=0) \geq \frac{3}{4(2\sqrt{2n}+1)} \geq \frac{3}{4(2\sqrt{2}+1)\sqrt n}. \] The last inequality uses \(n\geq1\). Since \(\sum_{n=1}^{\infty}n^{-1/2}\) diverges, the sum of the even-time return probabilities diverges. All terms in \(G(0,0)\) are nonnegative, so \(G(0,0)=\infty\). \(\square\)

Worked Example: A Lower Bound on the Fourth-Time Return Probability

For \(n=2\), the random variable \(Y\) counts right steps in four trials. It has mean \(2\), variance \(1\), and \(\mathbb{P}(Y=2)=6/16=3/8\). The general Chebyshev argument gives a weaker bound, but illustrates how a sum of return probabilities can be controlled without needing an exact asymptotic formula. For every \(n\geq1\), it yields a constant \(c=3/[4(2\sqrt{2}+1)]>0\) such that \(\mathbb{P}_0(S_{2n}=0)\geq c/\sqrt n\). Summing this bound over \(n\) proves divergence.

To see why this divergence implies recurrence, let \(f=\mathbb{P}_0(T_0^+<\infty)\), the probability of at least one positive-time return. At each return, the future steps are independent of the past and have the same law as a fresh walk from zero. Consequently, the probability of making at least \(k\) positive-time returns is \(f^k\). If \(R\) denotes the total number of positive-time returns, the tail-sum formula for a nonnegative integer-valued random variable gives \(\mathbb{E}_0[R]=\sum_{k\geq1}f^k\). Thus the expected total number of visits, including time zero, is finite when \(f<1\) and infinite when \(f=1\). In particular, Green-function divergence forces \(f=1\). This is the Green-function criterion for recurrence in this setting, obtained directly from the return decomposition.

Two Views of the Same Recurrence

The gambler’s-ruin limit and the Green-function argument establish recurrence in different ways. The first computes the probability of hitting zero before a distant boundary and then sends that boundary to infinity. The second counts visits at fixed times and shows that their expected total number is infinite. In this walk, both methods give almost-sure return, and the finite-time calculation also shows why returns occur only at even times.

A useful distinction is that \(\mathbb{P}_0(S_n=0)\) is not the probability of having returned by time \(n\). It asks whether the walk is at zero at exactly that time. The probability of ever returning is instead \(\mathbb{P}_0(T_0^+<\infty)=1\). In particular, the zero probabilities at odd times are fully consistent with recurrence.

Check Your Understanding

Use the formulas and arguments above to answer these questions.

Starting from \(i\), what is the probability of hitting \(0\) before \(N\), and what boundary values determine it?
Why do the events \(\{T_0<T_N\}\) increase as \(N\) tends to infinity?
Why is the probability of being at zero at any odd time equal to zero?
How many paths return to zero after \(2n\) steps, and what is the probability of each path?
How does divergence of the Green function imply that the probability of a positive-time return is one?