= Five-state harmonic absorption example
{title2=$h_i=i/4,\quad t_i=i(4-i)$}
Take a <birth-death chain> on $\{0,1,2,3,4\}$. At each interior state, move up one state with <probability> $p=1/2$ and down one state with <probability> $q=1/2$. The endpoints are <absorbing states>: $P_{00}=P_{44}=1$. This is a small <gambler's ruin> model in which the state can represent capital, and reaching $4$ is success.
\Image[/harmonic-markov-absorption-network.png]
{title=Five states with fair interior transitions and absorbing endpoints; each displayed value is the probability of reaching 4 before 0.}
Let $T_a=\inf\{n\geq0:X_n=a\}$ be the <hitting time> of endpoint $a$, and let $T=\min(T_0,T_4)$ be the first endpoint <hitting time>. The desired <hitting probability> is $h_i=\mathbb P_i(T_4<T_0)$. <First-step analysis> and the <Markov property> give
$$
h_0=0,\qquad h_4=1,\qquad h_i=\tfrac12h_{i-1}+\tfrac12h_{i+1}\quad(i=1,2,3).
$$
The interior equation says adjacent differences are equal. Four equal increments must bridge the boundary values $0$ and $1$, so
$$
h_i=\frac i4,\qquad (h_0,h_1,h_2,h_3,h_4)=(0,\tfrac14,\tfrac12,\tfrac34,1).
$$
For example, from state $2$ the <hitting probability> is $1/2$, and its one-step average is $\tfrac12(1/4)+\tfrac12(3/4)=1/2$. Individual <sample paths> can wander back and forth, but the same averaging rule already accounts for all of them.
Now ask how long it takes to reach either endpoint. The <expected hitting time> $t_i=\mathbb E_iT$ counts steps, including the transition that first reaches an endpoint. <First-step analysis> gives
$$
t_0=t_4=0,\qquad t_i=1+\tfrac12t_{i-1}+\tfrac12t_{i+1}\quad(i=1,2,3).
$$
This is a discrete <Poisson equation>, $(I-P)t=1$ in the interior. The extra $1$ counts the step just taken. The quadratic values
$$
t_i=i(4-i),\qquad (t_0,t_1,t_2,t_3,t_4)=(0,3,4,3,0)
$$
satisfy the equations; from state $2$, $t_2=1+\tfrac12(3)+\tfrac12(3)=4$ steps. The <hitting probability> is harmonic, whereas the <expected hitting time> has a nonzero source term. These are special cases of <expected duration of symmetric gambler's ruin>; see https://ocw.mit.edu/courses/18-445-introduction-to-stochastic-processes-spring-2015/ddeda684b0dd6a1422418c7eca3ce843_MIT18_445S15_lecture16.pdf[Hao Wu's MIT lecture 16, gambler's ruin, slide 9].
For a <biased random walk> with $p=0.6$ upward and $q=0.4$ downward, keep the same <absorbing states>. The interior harmonic equation becomes $h_i=ph_{i+1}+qh_{i-1}$. Using <biased gambler's ruin probability> with these boundary values gives
$$
r=\frac qp=\frac23,\qquad h_i=\frac{1-r^i}{1-r^4},\qquad (h_0,h_1,h_2,h_3,h_4)=\left(0,\frac{27}{65},\frac9{13},\frac{57}{65},1\right).
$$
The three interior <hitting probabilities> are approximately $0.415385$, $0.692308$, and $0.876923$. Thus starting at $2$ now succeeds about $69.23\%$ of the time. A direct check is $0.6(57/65)+0.4(27/65)=9/13$. The curved profile reflects the unequal transition weights: its successive increments shrink by the factor $q/p=2/3$. The formula, with the endpoint denoted $T$ there, is verified in https://courses.csail.mit.edu/6.042/past-devel/archive/spring00/archive/lectures/L26.pdf[Karger and Lynch's MIT lecture 26, sections 2.3-2.4]; the five-state numbers here are direct substitutions.
\Image[/harmonic-hitting-probability-profiles.png]
{title=Hitting 4 before 0 for fair and upward-biased walks, compared with the fair walk's expected number of steps to either endpoint; lines join discrete state values.}
Why does harmonic averaging produce the correct <hitting probability>? With the <natural filtration> $\mathcal F_n=\sigma(X_0,\ldots,X_n)$, the <Markov property> gives the <conditional expectation> identity
$$
\mathbb E[h(X_{n+1})\mid\mathcal F_n]=(Ph)(X_n).
$$
For a function harmonic everywhere, this makes $h(X_n)$ a <martingale> whenever it is integrable. For a function harmonic only in the interior, $M_n=h(X_{n\wedge T})$ is a <stopped martingale>. In either five-state example, $0\leq M_n\leq1$. Also, from any interior state at most three consecutive upward steps reach $4$, with <probability> at least $p^3>0$. Repeated three-step blocks give $\mathbb P_i(T>3k)\leq(1-p^3)^k$, so $T$ is <almost surely> finite and has finite <expected value>; compare <finite-interval exit times have geometric tails>. Applying <optional stopping> at $n\wedge T$ and then the <bounded convergence theorem> gives
$$
h_i=\mathbb E_i[h(X_T)]=\mathbb P_i(X_T=4).
$$
The boundedness and finite <hitting time> justify this passage to the limit. See https://galton.uchicago.edu/~lalley/Courses/312/HarmonicFunctions.pdf[Steven Lalley's notes, harmonic functions and stopped expectations, theorem 1], and <stopped martingale in discrete time> for this bounded version of <optional stopping>.
Uniqueness has a short <maximum principle> explanation. On a finite <state space>, the difference of two harmonic extensions with the same <boundary conditions> is zero on the boundary. If its positive maximum occurs inside, the weighted average forces every successor with positive <transition probability> to have the same maximum. A path to the boundary propagates that maximum to zero, a contradiction. Applying the argument to the negative of the difference proves uniqueness. Reachability of the boundary is essential: an interior <closed communicating class> can retain an arbitrary constant.
// Target: markov-process.bigb
Back to article page
