Checking the duration formula

Topic: Random walks and first passage · more questions on this topic
‹ A biased walk on four steps

Show directly that e_x=x(d-x) satisfies the symmetric expected-duration recurrence and both boundary conditions.

Worked answer (click to show)

Let e_x=x(d-x). Then e_0=0 and e_d=0. For the interior,

\frac{e_{x+1}+e_{x-1}}{2} =\frac{(x+1)(d-x-1)+(x-1)(d-x+1)}{2} =x(d-x)-1 =e_x-1.

Rearrangement is e_x=1+(e_{x+1}+e_{x-1})/2, which is the fair recurrence e_x=1+\tfrac12 e_{x+1}+\tfrac12 e_{x-1}.