Why the boundary problem is well posed

Section of Random walks and first passage, part of Stochastic processes

Type	Section
Taught in	Random walks and first passage
Part	Stochastic processes

There are d-1 interior states. From any one of them, d consecutive upward steps reach d, and d consecutive downward steps reach 0. If 0<p<1, each of those runs has probability at least \min(p,q)^d>0, whatever the current interior state is. Split time into blocks of d steps. The probability of still being inside after m blocks is at most (1-\min(p,q)^d)^m, a geometric tail. Absorption occurs with probability 1, and \mathbb{E}\tau<\infty, because a geometric number of blocks has finite mean. That finiteness is what justifies writing the equation for e_x and solving it inside a finite linear system.

The formulas can be checked without repeating the derivation. At x=0 the hitting formula gives 0, and at x=d it gives 1. If p>q the hitting probability sits above the fair line x/d. If p<q it sits below. The duration is zero at both ends and positive in between.

Key idea

Condition on the first step. The probability of hitting the upper barrier, and the expected time until absorption, each satisfy a linear recurrence on the interior with known values at 0 and at d. Fair steps make the hitting probability the relative distance x/d and the expected duration x(d-x).

Used in

Taught in Random walks and first passage
All 3 questions on Random walks and first passage

Used in

See also