The Last Zero Before a Fixed Time

The Last Zero at an Even Horizon

A random walk can visit zero several times before a fixed observation time. The last such visit depends on the whole stretch of the path after that visit: the walk must avoid zero for every remaining step. For a simple symmetric random walk and an even observation time, that requirement leads to a compact exact formula. It separates into the probability of being at zero at a specified time and the probability of avoiding zero afterward.

Let \((\Omega,\mathcal{F},\mathbb{P})\) support independent random variables \((\xi_n)_{n\ge1}\) with \(\mathbb{P}(\xi_n=1)=\mathbb{P}(\xi_n=-1)=\tfrac12\). Define the discrete-time process \(S_n=\sum_{j=1}^n \xi_j\) for \(n\ge1\), with \(S_0=0\). Its state space is \(S=\mathbb{Z}\), and its natural filtration is \(\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). This is the simple symmetric random walk. Fix an integer \(m\ge0\), and define its last zero time through time \(2m\) by \(L_{2m}=\max\{n\in\{0,1,\ldots,2m\}:S_n=0\}\). The maximum exists because \(S_0=0\). Since each step changes the parity of the position, zeros can occur only at even times, so \(L_{2m}\) takes values in \(\{0,2,\ldots,2m\}\).

For an integer \(r\ge0\), write \(u_r=\binom{2r}{r}/4^r\), with \(u_0=1\). The value \(u_r\) is the probability that the walk is at zero after \(2r\) steps: exactly \(r\) of those steps must be \(+1\), and the remaining \(r\) must be \(-1\). The other ingredient is the probability of not returning to zero during a specified number of steps.

Proof. The case \(r=0\) has probability \(1=u_0\). Suppose \(r\ge1\). A path that avoids zero must start with a \(+1\) step and stay strictly positive, or start with a \(-1\) step and stay strictly negative. Reflection of every step’s sign gives a bijection between these two kinds of paths, so it is enough to count the positive paths and double the count.

For a positive path, the first step is \(+1\). Subtract \(1\) from the path’s height after that step. The remaining \(2r-1\) steps then form a path starting at zero that stays nonnegative. Let \(N=2r-1\). For an endpoint \(j\in\{1,3,\ldots,N\}\), there are \(\binom{N}{(N+j)/2}\) unrestricted paths of length \(N\) from zero to \(j\). Among them, the paths that visit \(-1\) are counted by reflection at their first visit to \(-1\): reflecting the steps up to that visit gives an unrestricted path ending at \(j+2\). There are \(\binom{N}{(N+j)/2+1}\) such paths. Thus the number of nonnegative paths ending at \(j\) is the difference of those two binomial coefficients.

Summing over the possible endpoints telescopes: \(\sum_{q=r}^{2r-1}\left[\binom{2r-1}{q}-\binom{2r-1}{q+1}\right]=\binom{2r-1}{r}\), where the final term \(\binom{2r-1}{2r}\) is zero. Consequently the number of paths avoiding zero for all \(2r\) steps is \(2\binom{2r-1}{r}\). Each path has probability \(2^{-2r}\), so the required probability is \(\frac{2\binom{2r-1}{r}}{2^{2r}}=\frac{\binom{2r}{r}}{4^r}=u_r\). \(\square\)

Factorizing the Last-Zero Probability

Proof. Fix \(k\in\{0,\ldots,m\}\). The event \(L_{2m}=2k\) requires \(S_{2k}=0\) and requires that the walk not be at zero at any later time through \(2m\). Odd times cannot be zero, so the latter requirement is exactly that \(S_{2k+2},S_{2k+4},\ldots,S_{2m}\) are all nonzero. It imposes no restrictions when \(k=m\).

The event \(S_{2k}=0\) has probability \(u_k\). It depends only on the first \(2k\) increments. The later increments are independent of \(\mathcal{F}_{2k}\), so, conditional on \(S_{2k}=0\), the probability of avoiding zero for the remaining \(2(m-k)\) steps is \(u_{m-k}\), by the lemma. This conditional probability is meaningful because \(\mathbb{P}(S_{2k}=0)=u_k>0\); for \(k=m\), it is the probability \(1=u_0\) of an empty stretch. Multiplying the two probabilities gives the formula. The parity observation shows that no other last-zero times are possible. \(\square\)

The two factors have distinct roles. The first accounts for all possible paths that return to zero at time \(2k\); the second selects precisely those continuations with no later return. In particular, the formula includes both boundary cases: \(k=0\) asks for no return after the initial time, while \(k=m\) asks only whether the walk is at zero at the observation time.

Why the Probabilities Sum to One

Proof. The events \(\{L_{2m}=2k\}\), for \(k=0,\ldots,m\), are disjoint: a path cannot have two different last-zero times. They cover all paths, because every path has at least one zero time, namely time zero, and its last zero must be an even time no later than \(2m\). Therefore their probabilities sum to \(1\). Substituting the theorem’s formula for each probability gives \(\sum_{k=0}^{m}u_k u_{m-k}=1\). This argument also applies when \(m=0\), where the sum consists only of \(u_0u_0=1\). \(\square\)

This identity is a useful check on both the factorization and arithmetic in a particular case. It is not an assumption in the theorem: it follows because the last-zero events partition the possible paths.

A Common Counting Pitfall

A tempting but incorrect approach is to say that \(L_4=0\) whenever the endpoint \(S_4\) is nonzero. That counts paths that return to zero earlier and then leave again. For example, the path \(+,-,+,+\) has positions \(S_1=1\), \(S_2=0\), \(S_3=1\), and \(S_4=2\). Its endpoint is nonzero, but its last zero is at time \(2\), not time \(0\).

The incorrect endpoint calculation would give \(\mathbb{P}(S_4\ne0)=1-u_2=1-\tfrac38=\tfrac58\). The correct event \(L_4=0\) requires avoiding zero at every positive time through \(4\), and its probability is \(u_2=\tfrac38\). The distinction is between an endpoint condition and a path condition: a last-zero event rules out every later return, not just a zero at the final time.

For any even horizon, the practical steps are to first identify the candidate time \(2k\), require a return at that time, and then require no return over the remaining \(2(m-k)\) steps. Checking these two conditions separately avoids confusing the last-zero event with the simpler event that the endpoint is nonzero.