Return Probabilities at Even Times

Counting Returns at Even Times

For a simple symmetric random walk, each step moves one unit to the right or left with probability one half. A return to the origin can happen only after an even number of steps: every right step must be balanced by a left step. At time \(2m\), that balance turns the return-probability calculation into a count of paths with exactly \(m\) steps in each direction. The count is a central binomial coefficient, and its ratio across successive values of \(m\) makes comparisons between even horizons especially direct.

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\). Define the walk on the state space \(S=\mathbb{Z}\), at discrete times \(n\ge0\), by \(S_0=0\) and \(S_n=\sum_{k=1}^n \xi_k\). From every state \(i\), the one-step transition probabilities are \(\tfrac12\) to \(i+1\) and \(\tfrac12\) to \(i-1\), with probability zero to all other states. Their sum is \(\tfrac12+\tfrac12=1\), so these are valid transition probabilities.

At time \(2m\), suppose the walk has taken \(u\) steps to the right and \(d\) steps to the left. Then \(u+d=2m\), while \(S_{2m}=u-d\). The walk returns to zero exactly when both equations hold, which requires \(u=d=m\). Thus the returning paths are precisely the paths whose \(2m\) step positions contain \(m\) right steps. Choosing those positions determines the entire path.

Proof. Fix \(m\ge0\). There are \(2^{2m}\) possible sequences of \(2m\) steps, because each of the \(2m\) positions has two possible increments. By independence, each specified sequence has probability \((\tfrac12)^{2m}=2^{-2m}\). A sequence returns to zero exactly when it has \(m\) right steps and \(m\) left steps. The positions of the right steps can be chosen in \(\binom{2m}{m}\) ways, so adding the equal probability of each such sequence gives \(p_m=\binom{2m}{m}2^{-2m}\). For \(m=0\), this count gives one empty sequence out of one, as required.

For the ratio, substitute the formula just proved and use the factorial definition of the binomial coefficient: $$ \frac{p_{m+1}}{p_m} =\frac{\binom{2m+2}{m+1}}{2^{2m+2}}\frac{2^{2m}}{\binom{2m}{m}} =\frac{(2m+2)!}{(m+1)!(m+1)!}\frac{m!m!}{(2m)!}\frac14 =\frac{(2m+2)(2m+1)}{(m+1)^2}\frac14 =\frac{2m+1}{2m+2}. $$ The denominator \(2m+2\) exceeds the numerator \(2m+1\) by one, and both are positive. The ratio is therefore strictly between zero and one. Since \(p_m>0\), this proves \(p_{m+1}<p_m\) for every \(m\ge0\). \(\square\)

The formula gives an exact probability at any even time, while the ratio compares consecutive even horizons without requiring the full path count each time. In particular, when the horizon increases from \(2m\) to \(2m+2\), the return probability is multiplied by \((2m+1)/(2m+2)\). This factor depends on the current horizon: it is not a constant discount applied at every step. There is also no return at an odd time, because a sum of an odd number of increments, each equal to \(1\) or \(-1\), cannot equal zero.

Comparing Even Horizons

For two different even horizons, one can calculate each central binomial coefficient directly, or start from a known return probability and multiply successive ratios. The second approach often makes the comparison clearer: every factor is positive and strictly less than one, so each additional pair of steps reduces the probability. The reduction from one even horizon to the next can also be written as a difference: $$ p_m-p_{m+1} =p_m\left(1-\frac{2m+1}{2m+2}\right) =\frac{p_m}{2m+2}>0. $$ This shows both the direction of the change and its exact size relative to the current return probability.

The ratio calculation also shows that the probabilities become small over long even horizons. An elementary bound makes this conclusion precise without approximating the binomial coefficient. Since \(p_0=1\), induction using the ratio gives $$ p_m\le\frac{1}{\sqrt{m+1}}\qquad(m\ge0). $$ Indeed, if the bound holds at \(m\), then $$ p_{m+1} \le\frac{1}{\sqrt{m+1}}\frac{2m+1}{2m+2} \le\frac{1}{\sqrt{m+2}}. $$ For the second inequality, both sides are positive, and squaring and cross-multiplying reduces it to $$ (2m+1)^2(m+2)\le4(m+1)^3. $$ The right side minus the left side is \(3m+2\), which is positive for \(m\ge0\). This proves the induction step. Since \(1/\sqrt{m+1}\) tends to zero, so does \(p_m\). The bound is not an exact formula; the central-binomial expression remains the exact probability.

A Common Counting Error

A frequent mistake is to divide the number of returning paths by \(2^m\), rather than by \(2^{2m}\). There are \(2m\) independent steps, each with two possibilities, so the total number of equally likely paths is \(2^{2m}\). For example, at time four, \(m=2\), and there are \(\binom{4}{2}=6\) returning paths. The incorrect calculation \(6/2^2=6/4=3/2\) cannot be a probability. The correct denominator counts all four-step paths: \(2^4=16\), giving \(6/16=3/8\). A check against the ratio formula gives \(p_1=1/2\) and \(p_2=p_1(3/4)=3/8\), confirming the correction.

Keep the distinction between a return probability at a fixed time and a probability of returning at some time in mind. Here \(p_m\) refers only to the event \(S_{2m}=0\). It does not count paths that visit zero at an earlier time and then move away, and the strict decrease compares these fixed-time events at different even horizons. The path count works because every complete path has the same probability in this symmetric walk; if step probabilities differed, the number of paths alone would not determine their total probability.