Tutorials › Probability Theory (Graduate) › Optional Stopping for Random-Walk Hitting Problems

Home  /  Tutorials  /  Random Walks and Potential Theory

Random Walks and Potential Theory · Tutorial 924 of 946

Optional Stopping for Random-Walk Hitting Problems

Use optional stopping to evaluate random-walk hitting probabilities, while checking carefully when the stopped martingale has the integrability needed for the argument.

Advanced 12 min read

What You'll Learn

  • Define harmonic functions for a Markov chain on an interior domain.
  • Apply optional stopping at a bounded stopping time and verify its hypotheses.
  • Compute hitting probabilities from bounded harmonic functions and boundary values.
  • Use a Poisson equation and a stopped martingale to find an expected exit time.
  • Recognize why almost-surely finite stopping does not by itself justify optional stopping.

Why Optional Stopping Helps with Hitting Problems

A random walk can visit many states before it reaches a specified boundary. Directly listing all possible paths is usually inefficient. A more useful approach is to find a function whose conditional expected value is unchanged by one step of the walk. Such a function produces a martingale, and optional stopping can relate its initial value to its value at the exit state.

The method is powerful only when its hypotheses are checked. In particular, a stopping time being finite almost surely does not, by itself, justify taking expectations at that time. Bounded domains often provide the control needed: if the relevant function is bounded and exit occurs almost surely, bounded stopping followed by a limit gives a rigorous identity.

Harmonic Functions and the Exit Time

Let \((X_n)_{n\geq 0}\) be a Markov chain on a countable state space \(E\), with transition probabilities \(P(x,y)\), and let \(\mathcal F_n=\sigma(X_0,\ldots,X_n)\). For a subset \(D\subseteq E\), define the exit time \(\tau=\inf\{n\geq 0:X_n\notin D\}\), with \(\inf\varnothing=\infty\).

Definition: A function \(h:E\to\mathbb R\) is harmonic at \(x\) if \(\sum_{y\in E}P(x,y)|h(y)|<\infty\) and \(h(x)=\sum_{y\in E}P(x,y)h(y)\). It is harmonic on \(D\) if it is harmonic at every \(x\in D\).

The absolute-integrability condition makes the displayed sum well-defined. Harmonicity is a one-step averaging property. When \(h\) is harmonic on \(D\), it gives a martingale up to exit only if the random variables involved are integrable.

Integrability check: To assert that \(h(X_n)\) is a martingale, require \(\mathbb E|h(X_n)|<\infty\) for every \(n\). For the one-step conditional-expectation identity at time \(n\), \(h(X_{n+1})\) must in particular be integrable; integrability of \(h(X_n)\) alone does not suffice.

Under these integrability conditions, and when \(h\) is harmonic at states occupied at time \(n\), the Markov property gives \(\mathbb E[h(X_{n+1})\mid\mathcal F_n]=h(X_n)\). The same caution applies to stopped processes: integrability must be established, not inferred merely from the harmonic equation.

Optional Stopping at a Bounded Time

A random time \(T\) is a stopping time for \((\mathcal F_n)\) if \(\{T\leq n\}\in\mathcal F_n\) for every \(n\). The following discrete-time result is the basic tool. It requires no uniform-integrability assumption because \(T\) is bounded.

Theorem: Let \((M_n)_{n\geq0}\) be an integrable martingale and let \(T\) be a stopping time such that \(T\leq N\) almost surely for some fixed integer \(N\). Then \(\mathbb E[M_T]=\mathbb E[M_0]\).
Proof. Since \(T\leq N\), the identity \(M_T=M_0+\sum_{k=1}^{N}\mathbf 1_{\{T\geq k\}}(M_k-M_{k-1})\) holds pathwise. The event \(\{T\geq k\}\) belongs to \(\mathcal F_{k-1}\), because its complement \(\{T\leq k-1\}\) belongs to that sigma-field. The martingale property therefore gives \(\mathbb E[\mathbf 1_{\{T\geq k\}}(M_k-M_{k-1})]=0\). Each term is integrable, since \(M_k\) and \(M_{k-1}\) are integrable and the indicator is bounded. Taking expectations in the finite sum proves \(\mathbb E[M_T]=\mathbb E[M_0]\). \(\square\)

For an exit time that may be unbounded, apply this theorem first to \(T=\tau\wedge n\). To pass from \(\tau\wedge n\) to \(\tau\), one needs a separate convergence argument. In a bounded domain, boundedness of the stopped function and almost-sure finiteness of \(\tau\) provide a particularly clean one.

Bounded-Domain Exit Identity

Theorem: Suppose \(\tau=\inf\{n\geq0:X_n\notin D\}\) is finite almost surely under \(\mathbb P_x\). Suppose \(h\) is harmonic on \(D\) and bounded on \(D\) and on the states that can be reached at exit. Then \(\mathbb E_x[h(X_\tau)]=h(x)\) for every \(x\in D\).
Proof. Set \(M_n=h(X_{n\wedge\tau})\). This process is bounded, hence integrable at every time. On \(\{\tau\leq n\}\), it stays fixed from time \(n\) to \(n+1\). On \(\{\tau>n\}\), \(X_n\in D\), so harmonicity and the Markov property give \(\mathbb E[h(X_{n+1})\mid\mathcal F_n]=h(X_n)\). Combining these cases shows that \(M_n\) is a martingale. The bounded-stopping theorem applied at \(\tau\wedge n\) gives \(\mathbb E_x[h(X_{\tau\wedge n})]=h(x)\). Since \(\tau<\infty\) almost surely, \(X_{\tau\wedge n}\to X_\tau\) almost surely. The variables \(h(X_{\tau\wedge n})\) are bounded by one fixed constant, so dominated convergence gives \(\mathbb E_x[h(X_\tau)]=\lim_{n\to\infty}\mathbb E_x[h(X_{\tau\wedge n})]=h(x)\). \(\square\)

One common way to verify the theorem’s exit assumption is to find an integer \(L\geq1\) and a number \(\delta>0\) such that, from every state in \(D\), the chain has probability at least \(\delta\) of leaving \(D\) within the next \(L\) steps. By conditioning at times \(L,2L,\ldots\), the probability of remaining in \(D\) for \(kL\) steps is at most \((1-\delta)^k\), which tends to zero. Thus \(\tau<\infty\) almost surely. This condition is automatic in many finite-state problems where every interior state can reach the boundary.

Worked Example: Hitting a Boundary State in a Finite Chain

Worked Example: Hitting a Boundary State in a Finite Chain

Consider interior states \(u,v\) and absorbing boundary states \(A,B\). From \(u\), the chain moves to \(A\) or \(v\), each with probability \(1/2\). From \(v\), it moves to \(u\) or \(B\), each with probability \(1/2\). Let \(\tau\) be the first time the chain reaches \(\{A,B\}\). Find the probability of reaching \(B\), starting from \(u\) or \(v\).

Set \(h(A)=0\), \(h(B)=1\), and let \(h(u),h(v)\) be the corresponding hitting probabilities. The first-step equations are \(h(u)=\tfrac12h(A)+\tfrac12h(v)=\tfrac12h(v)\) and \(h(v)=\tfrac12h(u)+\tfrac12h(B)=\tfrac12h(u)+\tfrac12\). Substituting the first equation into the second gives \(h(v)=\tfrac14h(v)+\tfrac12\), so \(h(v)=\tfrac23\) and \(h(u)=\tfrac13\).

These values are verified directly: \(\tfrac12(0)+\tfrac12(\tfrac23)=\tfrac13\) at \(u\), and \(\tfrac12(\tfrac13)+\tfrac12(1)=\tfrac23\) at \(v\). From either interior state, the probability of exiting on the next step is \(1/2\). Therefore \(\mathbb P(\tau>n)\leq(1/2)^n\), so \(\tau\) is finite almost surely. The function is bounded, and the bounded-domain exit identity applies. Its boundary values are the indicator of exit at \(B\); hence \(\mathbb P_u(X_\tau=B)=1/3\) and \(\mathbb P_v(X_\tau=B)=2/3\).

Expected Exit Times from a Poisson Equation

Hitting probabilities use a harmonic equation, whose one-step expected change is zero. Expected exit times are often obtained from a related equation with a constant decrement. In the same chain, define \(g(A)=g(B)=0\) and solve, for interior states, \(g(x)=1+\sum_yP(x,y)g(y)\). The added \(1\) accounts for the step just taken. Once a bounded solution is found and exit is almost surely finite, the process \(g(X_{n\wedge\tau})+(n\wedge\tau)\) is a martingale. Bounded stopping then yields an expectation identity.

Worked Example: Expected Time to Reach the Boundary

For the chain above, the equations for \(g\) are \(g(u)=1+\tfrac12g(v)\) and \(g(v)=1+\tfrac12g(u)\), since the other transition from each state reaches a boundary state where \(g=0\). Substitution gives \(g(u)=1+\tfrac12(1+\tfrac12g(u))\), so \(g(u)=2\), and then \(g(v)=2\). Both equations check: \(1+\tfrac12(2)=2\).

For \(n\geq0\), define \(Z_n=g(X_{n\wedge\tau})+(n\wedge\tau)\). Before exit, the conditional expectation of the next \(g\)-value is \(g(X_n)-1\), while the time term increases by \(1\); after exit, both terms stay fixed. Thus \(Z_n\) is a martingale. It is integrable for each \(n\), since \(g\) is bounded and \(n\wedge\tau\leq n\). Bounded stopping at \(\tau\wedge n\) gives \(\mathbb E_x[g(X_{\tau\wedge n})+\tau\wedge n]=g(x)\). As \(n\to\infty\), the first term tends to \(g(X_\tau)=0\) and is bounded, while \(\tau\wedge n\) increases to \(\tau\). Dominated convergence for the first term and monotone convergence for the second show \(\mathbb E_x[\tau]=g(x)=2\) from either interior state.

Why Almost-Sure Finiteness Is Not Enough

It is tempting to stop a martingale at any almost-surely finite time and immediately equate expectations. That inference is not valid in general. A stopping time can be finite almost surely while the stopped martingales \(M_{\tau\wedge n}\) fail to have the integrability control needed to pass expectations to a limit. The following example isolates the issue.

Worked Example: A Finite Stopping Time with No Expectation Limit

Toss a fair coin repeatedly, and let \(\tau\) be the time of the first tail. Define \(M_0=1\) and \(M_n=2^n\) if the first \(n\) tosses are all heads, and \(M_n=0\) otherwise. This is a martingale: on a history consisting of \(n\) heads, the next value is \(2^{n+1}\) with probability \(1/2\) and \(0\) with probability \(1/2\), so its conditional mean is \(2^n\); after a tail, it remains zero.

The stopping time is finite almost surely because \(\mathbb P(\tau>n)=2^{-n}\to0\). But \(M_\tau=0\) almost surely. In contrast, \(M_{\tau\wedge n}\) is \(2^n\) if the first \(n\) tosses are heads and is zero otherwise, so \(\mathbb E[M_{\tau\wedge n}]=2^n\cdot2^{-n}=1\) for every \(n\). Thus the expectations do not converge to \(\mathbb E[M_\tau]=0\). The stopped variables are not uniformly integrable: they converge almost surely to zero while their expectations remain one. Almost-sure finiteness alone cannot justify the desired expectation identity.

For the bounded-domain theorem, the issue is avoided because the stopped harmonic function is bounded. In more general problems, one must establish an appropriate condition such as uniform integrability of the stopped martingales, or another valid convergence argument. Do not infer integrability of \(h(X_{n+1})\) from that of \(h(X_n)\); the former is required for the one-step conditional expectation, and integrability at every time is required to call the whole process a martingale.

Practical Checklist

When applying optional stopping to a hitting problem, separate the argument into its distinct tasks:

  1. Specify the domain, exit time, and boundary values.
  2. Check the harmonic or Poisson equation at every interior state.
  3. Verify integrability of the process at every time at which a martingale property is claimed.
  4. Prove exit is almost surely finite, if the limiting argument uses the exit state.
  5. Apply optional stopping first at \(\tau\wedge n\), then justify the limit using boundedness or another stated convergence condition.

In a finite-state model, boundedness is often immediate, but it should still be stated. The equation for a candidate harmonic function alone does not establish every hypothesis required by optional stopping. Correctly identifying those hypotheses is part of the method, not a technical afterthought.

Check Your Understanding

Use the definitions and arguments in this tutorial to answer the following.

  1. What integrability condition is needed for \(h(X_{n+1})\) in the one-step martingale identity?
  2. Why does boundedness of \(h(X_{n\wedge\tau})\), together with almost-surely finite \(\tau\), justify passing to the exit-state expectation?
  3. In the two-interior-state example, verify the two harmonic equations using the computed values.
  4. What equation for \(g\) is used to compute an expected exit time, and why does it produce a martingale after adding the elapsed stopped time?
  5. Why does the coin-toss example show that almost-surely finite stopping does not by itself preserve expectations?

Previous

Next

Back to Tutorials
Clinical Biostats