Expected Exit Time from a Finite Random-Walk Interval

Why Exit Time Uses Two Martingales

A fair random walk has no directional drift, so its expected position remains at its starting value. That fact determines the probabilities of exiting a finite interval through either endpoint. The expected time to exit is a different quantity: it is obtained from the martingale that subtracts elapsed time from the squared position. Using both martingales gives a direct route to the exit-time formula, provided the stopping argument is justified.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\) carrying independent random variables \((\xi_n)_{n\ge1}\) with \(\mathbb{P}(\xi_n=1)=\mathbb{P}(\xi_n=-1)=\tfrac12\). For an integer starting point \(x\), define the discrete-time random walk \(S_0=x\) and \(S_n=x+\sum_{r=1}^n \xi_r\), with state space \(\mathbb{Z}\). Use the filtration \(\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). Fix integers \(a<b\), and define the exit time from the integer interval by \(T=\inf\{n\ge0:S_n\notin\{a+1,\ldots,b-1\}\}\). Equivalently, when \(a<x<b\), \(T=\inf\{n\ge0:S_n\in\{a,b\}\}\), since each step has size one and cannot jump over an endpoint. If \(x=a\) or \(x=b\), then \(T=0\).

For this walk, \((S_n)\) and \((S_n^2-n)\) are martingales with respect to \((\mathcal{F}_n)\). Indeed, \(\mathbb{E}[\xi_{n+1}\mid\mathcal{F}_n]=0\) gives \(\mathbb{E}[S_{n+1}\mid\mathcal{F}_n]=S_n\). Also, \(\xi_{n+1}^2=1\), so \(\mathbb{E}[S_{n+1}^2-(n+1)\mid\mathcal{F}_n]=S_n^2+1-(n+1)=S_n^2-n\). These martingales suggest the answer, but optional stopping at \(T\) requires care because \(T\) is not initially known to be bounded.

Finiteness and the Stopped-Martingale Argument

First show that \(T\) is finite and integrable. Let \(L=b-a\). Starting from any interior state, a run of \(L\) consecutive \(+1\) increments forces the walk to reach \(b\) within at most \(L\) steps. The probability of this run is \(2^{-L}>0\). In successive blocks of \(L\) increments, independence therefore gives, for every integer \(k\ge0\), \(\mathbb{P}_x(T>kL)\le(1-2^{-L})^k\). In particular, \(T<\infty\) almost surely. The geometric bound also implies \(\mathbb{E}_x[T]<\infty\): grouping the tail sum \(\mathbb{E}_x[T]=\sum_{n\ge0}\mathbb{P}_x(T>n)\) into blocks of length \(L\) bounds it by \(L\sum_{k\ge0}(1-2^{-L})^k=L2^L\).

Proof. Assume first \(a<x<b\), and set \(T_n=T\wedge n\), the minimum of \(T\) and the deterministic integer \(n\). This is a bounded stopping time for \((\mathcal{F}_n)\). Bounded optional stopping applies to each martingale. Thus \(\mathbb{E}_x[S_{T_n}]=x\) and \(\mathbb{E}_x[S_{T_n}^2-T_n]=x^2\). Until exit the walk lies between the endpoints, and after exit it stays at an endpoint when stopped. Consequently \(a\le S_{T_n}\le b\). Since \(T<\infty\) almost surely, \(S_{T_n}\to S_T\) almost surely; bounded convergence gives \(\mathbb{E}_x[S_T]=x\) and \(\mathbb{E}_x[S_{T_n}^2]\to\mathbb{E}_x[S_T^2]\). Also \(T_n\uparrow T\), and the already established integrability of \(T\) gives \(\mathbb{E}_x[T_n]\to\mathbb{E}_x[T]\). Passing to the limit in the two stopped identities yields \(\mathbb{E}_x[S_T]=x\) and \(\mathbb{E}_x[S_T^2]-\mathbb{E}_x[T]=x^2\).

Because \(S_T\) is either \(a\) or \(b\), write \(p=\mathbb{P}_x(S_T=b)\). The first identity says \(a(1-p)+bp=x\), so \((b-a)p=x-a\), or \(p=\frac{x-a}{b-a}\). The probability of exiting at \(a\) is \(1-p=\frac{b-x}{b-a}\). For the second identity, \(\mathbb{E}_x[S_T^2]=\frac{(b-x)a^2+(x-a)b^2}{b-a}\). To simplify without skipping the algebra, the numerator expands as \(xb^2-ab^2+ba^2-xa^2=x(b-a)(a+b)-ab(b-a)\). Therefore \(\mathbb{E}_x[S_T^2]=x(a+b)-ab\), and \(\mathbb{E}_x[T]=x(a+b)-ab-x^2=(x-a)(b-x)\). If \(x=a\) or \(x=b\), \(T=0\) by definition, and the product \((x-a)(b-x)\) is zero. This proves all the claims. \(\square\)

The truncation \(T_n\) is the key justification: optional stopping is used only at bounded times. The limit is then taken using boundedness of the stopped positions and integrability of \(T\), rather than assuming that optional stopping automatically holds at an unbounded time.

Worked Calculations

Common Pitfall: Mixing Up the Endpoint Weights

The probability of the upper endpoint is proportional to the distance from the lower endpoint, not the distance to the upper endpoint. Reversing the weights gives the wrong mean position. For example, with \(a=0\), \(x=2\), and \(b=6\), the upper-exit probability is \(\frac{2}{6}=\frac13\), not \(\frac{6-2}{6}=\frac23\). Using the reversed weights would give endpoint mean \(\frac23\cdot6+\frac13\cdot0=4\), which contradicts \(\mathbb{E}_x[S_T]=x=2\).

A separate algebra error can arise when simplifying the endpoint second moment. The numerator is \((b-x)a^2+(x-a)b^2=ba^2-xa^2+xb^2-ab^2\). For \(a=1\), \(b=4\), and \(x=2\), this is \(4-2+32-16=18\), as it must be from \((4-2)1^2+(2-1)4^2=18\). Replacing the term \(ba^2\) by \(ab^2\) would instead produce \(32-16+16-2=30\), an incorrect value. The correct rearrangement is \(xb^2-ab^2+ba^2-xa^2=x(b-a)(a+b)-ab(b-a)\). Dividing by \(b-a\) gives \(x(a+b)-ab\); subtracting \(x^2\) then gives \((x-a)(b-x)\).

The formula also emphasizes the importance of having two finite boundaries. Moving to a one-sided or unbounded interval changes the stopping problem; the finite-interval calculation does not establish a finite mean exit time in those settings. The proof here relies on a fixed finite distance \(b-a\), which supplies a positive chance of exit within each block of that many steps.