Solving the recurrences from scratch
Section of Random walks and first passage, part of Stochastic processes
Solving the recurrences from scratch
| Type | Section |
| Taught in | Random walks and first passage |
| Part | Stochastic processes |
Rearrange the hitting equation as
p(h_{x+1}-h_x)=q(h_x-h_{x-1}).
The successive differences \Delta_x=h_x-h_{x-1} form a geometric sequence with ratio q/p: \Delta_{x+1}=(q/p)\Delta_x. Summing from 1 to x and using h_0=0 gives
h_x=\Delta_1\sum_{k=0}^{x-1}\Bigl(\frac{q}{p}\Bigr)^k.
The condition h_d=1 fixes \Delta_1. When p=q every difference equals \Delta_1, the sum is x\Delta_1, and h_d=1 forces \Delta_1=1/d, so h_x=x/d. When p\neq q the geometric sum is \bigl(1-(q/p)^x\bigr)/\bigl(1-q/p\bigr), and the same boundary condition recovers the closed form above.
For the fair duration, the rearranged equation is e_{x+1}-2e_x+e_{x-1}=-2. Try e_x=Ax^2+Bx+C. The second difference of x^2 is 2, so 2A=-2 and A=-1. The boundary e_0=0 gives C=0. The boundary e_d=0 gives -d^2+Bd=0, so B=d. Therefore e_x=x(d-x). The shape of the difference equation suggests the trial solution. The boundary values fix the constants.
Used in
See also
Drift and scale of a random walk · Gambler’s ruin · Expected duration of a random walk · Why the boundary problem is well posed · First-passage time