First-Return Time Probabilities

From Return Paths to First-Return Paths

For a random walk, being at the starting point at time \(n\) does not necessarily mean that the walk has just returned there: it may have visited the starting point earlier. The first-return time isolates paths that avoid the origin at every intermediate step. For the simple symmetric walk, this restriction turns a return-path count into a Catalan count.

Work on the probability space \((\Omega,\mathcal{F},\mathbb{P})\) of infinite sequences of independent increments \((\xi_n)_{n\ge1}\), where \(\mathbb{P}(\xi_n=1)=\mathbb{P}(\xi_n=-1)=\tfrac12\). Let the state space be \(S=\mathbb{Z}\), the time index be discrete \(n\ge0\), and define \(X_0=0\) and \(X_n=\sum_{k=1}^n \xi_k\). The natural filtration is \(\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). The first positive return time is \(T=\inf\{n\ge1:X_n=0\}\), with \(\inf\varnothing=\infty\). It is a stopping time because \(\{T\le n\}=\bigcup_{k=1}^n\{X_k=0\}\in\mathcal{F}_n\).

Every particular path of length \(n\) has probability \(2^{-n}\), since its \(n\) independent increments each have probability \(\tfrac12\). Also, \(X_n\) has the same parity as \(n\): after \(n\) steps, the position is the number of up-steps minus the number of down-steps, which is \(2u-n\) if there are \(u\) up-steps. Thus \(X_n=0\) requires \(n\) even.

Proof. The parity calculation shows that an odd-time return is impossible. Fix \(m\ge1\) and consider paths with \(T=2m\). On such a path the first step is either \(+1\) or \(-1\). If it is \(+1\), the positions at times \(1,\ldots,2m-1\) must all be strictly positive: a zero at any of those times would be an earlier return, and the walk cannot reach a negative position without first passing through zero. Delete the initial up-step and the final down-step. The remaining \(2m-2\) steps form a bridge from level \(1\) to level \(1\); subtracting \(1\) from its positions gives a nonnegative bridge from \(0\) to \(0\). Conversely, any nonnegative bridge of length \(2m-2\), shifted up by \(1\) and placed between an initial up-step and a final down-step, gives a path whose first return is exactly at time \(2m\). These operations are inverse, so there are \(C_{m-1}\) paths with first step up. Reflecting every step, \(+1\leftrightarrow-1\), gives another \(C_{m-1}\) paths with first step down; the two classes are disjoint. Hence there are \(2C_{m-1}\) qualifying paths among \(2^{2m}\) equally likely paths. Their probability is \(2C_{m-1}/2^{2m}=C_{m-1}/2^{2m-1}\). Substituting the Catalan formula gives the displayed binomial expression. \(\square\)

Computing the First-Return Probabilities

The Generating Function and Almost-Sure Return

The point probabilities can be collected into a probability generating function. It also checks that the formula accounts for all probability, rather than leaving a possible positive probability at \(T=\infty\).

Proof. Write \(C(x)=\sum_{r\ge0}C_rx^r\). The Catalan decomposition of a nonempty nonnegative bridge gives \(C_{r+1}=\sum_{j=0}^r C_jC_{r-j}\): the bridge splits uniquely into the part between its first up-step and matching return down-step, and the remaining bridge. Multiplying the recurrence by powers of \(x\) gives \(C(x)=1+xC(x)^2\). The series converges for \(0\le x<\tfrac14\), since \(C_r\le 4^r\): the Catalan paths form a subset of all \(2^{2r}=4^r\) step sequences. Solving the quadratic and choosing the root that tends to \(C(0)=1\) yields \(C(x)=\frac{1-\sqrt{1-4x}}{2x}\) for \(0<x<\tfrac14\), with the value at \(x=0\) given by continuity.

By the first-return formula, for \(0\le s<1\) we have $$ \sum_{n\ge1}\mathbb{P}(T=n)s^n =\sum_{m\ge1}\frac{C_{m-1}}{2^{2m-1}}s^{2m} =\frac{s^2}{2}C\!\left(\frac{s^2}{4}\right) =1-\sqrt{1-s^2}. $$ For the final equality, substitute \(x=s^2/4\) into the expression for \(C(x)\); at \(s=0\), both sides are zero. As \(s\) increases to \(1\), the nonnegative series on the left increases to \(\sum_{n\ge1}\mathbb{P}(T=n)=\mathbb{P}(T<\infty)\). The right side tends to \(1\), so \(\mathbb{P}(T<\infty)=1\). This proves both claims. \(\square\)

Equivalently, using \(s^2\) as the variable, the generating function is \(1-\sqrt{1-s^2}\); only even powers occur because odd-time returns are impossible. Almost-sure return does not mean that the expected return time is finite. Indeed, differentiating the generating function for \(0\le s<1\) gives \(s/\sqrt{1-s^2}\), which grows without bound as \(s\) increases to \(1\). Since the coefficients are nonnegative, this shows that the mean return time is infinite. The distinction is useful: a return happens with probability one, but its time has a sufficiently heavy tail to have infinite mean.

A Common Counting Error

A common mistake is to use the probability of being at zero at time \(4\) as the probability of the first return at time \(4\). There are \(\binom42=6\) paths ending at zero at time \(4\), so the return probability at that time is \(6/16=3/8\). But two of those six paths, \(UDUD\) and \(DUDU\), hit zero at time \(2\). Removing them leaves four paths that have not returned before time \(4\)? This count needs care: the length-four paths ending at zero are \(UUDD, UDUD, DUUD, DUDU, DDUU, UDDU\), and among these, only \(UDUD\) and \(DUDU\) return at time \(2\). However, \(DUUD\) and \(UDDU\) also return at time \(2\) by their second steps? Checking positions shows \(DUUD\) has positions \(-1,0,1,0\), and \(UDDU\) has positions \(1,0,-1,0\), so these too return at time \(2\). Thus four paths have an earlier return, leaving \(UUDD\) and \(DDUU\), and the first-return probability is \(2/16=1/8\).

The correction illustrates why path membership must be checked at every intermediate time, not just at the endpoint. More directly, the first-return paths at time \(4\) are precisely \(UUDD\) and \(DDUU\); the remaining four endpoint-return paths have a zero at time \(2\). This agrees with the Catalan count \(2C_1=2\), not the endpoint count \(\binom42=6\).