Grinstead-Snell-Probability · Problem 11.2.33

Markov Chains

Mathematics · absorbing-markov-chains

Problem

Consider a random walker who moves on the integers 0,1,…,N0, 1, \ldots, N, moving one step to the right with probability pp and one step to the left with probability q=1−pq = 1 - p. If the walker ever reaches 0 or NN he stays there. (This is the Gambler's Ruin problem of Exercise 23.) If p=qp = q show that the function f(i)=if(i) = i is a harmonic function (see Exercise 27), and if p≠qp \neq q then f(i)=(qp)if(i) = \left(\frac{q}{p}\right)^i is a harmonic function. Use this and the result of Exercise 27 to show that the probability biNb_{iN} of being absorbed in state NN starting in state ii is biN={iN,if p=q,(qp)i−1(qp)N−1,if p≠q.b_{iN} = \begin{cases} \dfrac{i}{N}, & \text{if } p = q, \\[6pt] \dfrac{\left(\frac{q}{p}\right)^i - 1}{\left(\frac{q}{p}\right)^N - 1}, & \text{if } p \neq q. \end{cases}
Intuitive explanation

The key insight is that harmonic functions capture the expected long-term behavior of the random walk: if ff satisfies the harmonic property at each interior state, then f(i)f(i) equals the weighted average of its neighbors' values, meaning the walk's expected value doesn't drift. Once you verify that the given functions are harmonic, Exercise 27 tells you they must equal the absorption probabilities at the boundaries—since absorption probabilities also satisfy this averaging property and match the boundary conditions f(0)=0f(0) = 0 and f(N)=1f(N) = 1.

Intuitive explanation

The key insight is that harmonic functions capture the expected long-term behavior of the random walk: if ff satisfies the harmonic property at each interior state, then f(i)f(i) equals the weighted average of its neighbors' values, meaning the walk's expected value doesn't drift. Once you verify that the given functions are harmonic, Exercise 27 tells you they must equal the absorption probabilities at the boundaries—since absorption probabilities also satisfy this averaging property and match the boundary conditions f(0)=0f(0) = 0 and f(N)=1f(N) = 1.

Related theory

Browse the problem library