Exact Return Probabilities in One Dimension

Counting Returns in One Dimension

For a random walk, the probability of being back at its starting point at a particular time can encode a long-term property of the whole process. In one dimension, that probability has an exact combinatorial form: returning after \(2n\) steps requires an equal number of left and right steps. Its size decreases as \(n\) grows, but not quickly enough for the sum of return probabilities to be finite. That divergence is the key to the recurrence classification.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((\xi_k)_{k\ge1}\) be independent random variables with \(\mathbb{P}(\xi_k=1)=\mathbb{P}(\xi_k=-1)=\tfrac12\). The simple symmetric random walk is \(X_0=0\) and \(X_n=\sum_{k=1}^n \xi_k\), with discrete time \(n\ge0\) and state space \(S=\mathbb{Z}\). Its natural filtration is \(\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). From every state \(i\), the transition probabilities to \(i+1\) and \(i-1\) are each \(\tfrac12\), so the two possible transition probabilities sum to \(1\). Write \(p_n(0)=\mathbb{P}_0(X_n=0)\).

Proof. After \(m\) steps, \(X_m\) is the number of \(+1\) increments minus the number of \(-1\) increments. If \(m\) is odd, those two counts cannot be equal, so \(X_m\ne0\). For \(m=2n\), the walk is at zero exactly when there are \(n\) increments of each sign. There are \(\binom{2n}{n}\) ways to choose which \(n\) of the \(2n\) increments equal \(+1\). Each specified sequence has probability \((\tfrac12)^{2n}=4^{-n}\), by independence. These sequences are disjoint, so adding their probabilities gives \(p_{2n}(0)=\binom{2n}{n}4^{-n}\). When \(n=0\), the sole length-zero sequence gives \(p_0(0)=1=\binom00\), so the formula includes that case. \(\square\)

The count is exact, not just an approximation. A useful further consequence is a simple ratio between successive even-time probabilities. Define \(a_n=p_{2n}(0)\). Using the exact formula and the factorial expression for the binomial coefficient gives \(a_{n+1}/a_n=(2n+1)/(2n+2)\). This ratio is less than \(1\), so the even-time return probabilities decrease; it also makes individual values easy to check.

Asymptotic Size and Green-Function Divergence

The exact formula also gives the large-\(n\) scale of the return probabilities. We use Stirling’s formula, the standard asymptotic \(m!\sim\sqrt{2\pi m}(m/e)^m\) as \(m\to\infty\). Here \(u_n\sim v_n\) means \(u_n/v_n\to1\). The next result records the resulting asymptotic and its consequence for the Green function.

Proof. For \(n\ge1\), the exact formula gives \(p_{2n}(0)=(2n)!/(n!^2 4^n)\). Apply Stirling’s formula to the numerator and denominator: \((2n)!\sim\sqrt{4\pi n}(2n/e)^{2n}\) and \(n!^2\sim 2\pi n(n/e)^{2n}\). Therefore \(p_{2n}(0)\sim [\sqrt{4\pi n}/(2\pi n)]\,[(2n/e)^{2n}/(n/e)^{2n}]\,4^{-n}\). The middle ratio is \(2^{2n}=4^n\), which cancels \(4^{-n}\), and \(\sqrt{4\pi n}/(2\pi n)=1/\sqrt{\pi n}\). This proves the stated asymptotic. In particular, for all sufficiently large \(n\), \(p_{2n}(0)\ge \tfrac{1}{2\sqrt{\pi n}}\), since the ratio of \(p_{2n}(0)\) to \(1/\sqrt{\pi n}\) tends to \(1\). The series \(\sum_{n\ge1}n^{-1/2}\) diverges: in the block \(2^k\le n<2^{k+1}\), there are \(2^k\) terms, each at least \(1/\sqrt{2^{k+1}}\), so the block sum is at least \(2^{(k-1)/2}\). Thus the even-time probabilities have a divergent sum. Since all Green-function terms are nonnegative and the odd-time terms are zero, \(G(0,0)=\sum_{n\ge0}p_{2n}(0)=\infty\). \(\square\)

The Green function is the expected total number of visits to zero, counting time \(0\). To make the connection to recurrence precise, define the first return time \(T_0^+=\inf\{n\ge1:X_n=0\}\), with \(\inf\varnothing=\infty\), and let \(f=\mathbb{P}_0(T_0^+<\infty)\). A state is recurrent when its return probability is \(1\). For this walk, the Green-function criterion can be justified directly through successive returns.

Proof. Let \(V=\sum_{n\ge0}\mathbf{1}_{\{X_n=0\}}\) be the total number of visits to zero, including the initial visit. By additivity of expectation for nonnegative random variables, \(\mathbb{E}_0[V]=\sum_{n\ge0}\mathbb{P}_0(X_n=0)=G(0,0)\). The increments after a finite return time are independent of the increments up to that time and have the original law: this follows by conditioning on each possible value \(T_0^+=m\) and using independence of the increments after deterministic time \(m\). Repeating this argument at successive return times shows that the probability of at least \(k\) visits, counting the visit at time \(0\), is \(f^{k-1}\) for every integer \(k\ge1\). This also covers \(f=0\), when only the initial visit occurs almost surely. For an integer-valued \(V\ge1\), \(\mathbb{E}_0[V]=\sum_{k\ge1}\mathbb{P}_0(V\ge k)\), so \(G(0,0)=\sum_{k\ge1}f^{k-1}\). If \(f<1\), this geometric series equals \(1/(1-f)<\infty\); if \(f=1\), every term is \(1\), and the series is infinite. Thus \(G(0,0)=\infty\) exactly when \(f=1\). The preceding theorem gives \(G(0,0)=\infty\), hence zero is recurrent. From any \(x\in\mathbb{Z}\), the displacement process \(X_n-x\) has the same increment law as the walk started at zero, so the return probability to \(x\) is also \(1\). Every state is therefore recurrent. Moreover, any two integers communicate because a finite sequence of nearest-neighbor steps connects them, with positive probability. \(\square\)

Interpreting the Classification

Recurrence does not mean that the probability of being at zero at a particular large time stays bounded away from zero. In fact, \(p_{2n}(0)\sim1/\sqrt{\pi n}\) tends to zero. Recurrence instead concerns the probability of returning at some finite time, and repeated returns. The divergence of the sum of the time-specific probabilities is what links these two viewpoints for this walk.

Common pitfall. It is incorrect to argue that the Green function is finite because \(p_{2n}(0)\to0\). A sequence tending to zero need not have a finite sum. Here the asymptotic gives a concrete correction: for all sufficiently large \(n\), \(p_{2n}(0)\ge1/(2\sqrt{\pi n})\), and the blocks \(2^k\le n<2^{k+1}\) contribute at least \(2^{(k-1)/2}\) to the corresponding sum of \(n^{-1/2}\) terms. These block contributions do not even tend to zero; their sum diverges. Another common error is to use the formula \(\binom{2n}{n}/4^n\) at odd times. The formula counts equal numbers of left and right steps, which is impossible after an odd number of steps; the odd-time return probability is exactly zero.