Expected duration of a random walk

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

Type	Section
Taught in	Random walks and first passage
Part	Stochastic processes
Questions using it	2

Let e_x=\mathbb{E}_x\tau. One step is used at once, and then the walk restarts from the neighbour it stepped to, so

e_x=1+p\,e_{x+1}+q\,e_{x-1}, \qquad 1\le x\le d-1,

with e_0=e_d=0. Absorption at either barrier stops the clock.

In the symmetric case a quadratic trial function works. The equation becomes e_{x+1}-2e_x+e_{x-1}=-2, a constant second difference, which is what a quadratic has. The boundary conditions e_0=e_d=0 give

e_x=x(d-x).

The expected duration is largest near the middle of the interval, where both barriers are far, and it is zero at either barrier.

If p\neq q, a particular solution is the linear function x/(q-p), and the homogeneous solutions are again 1 and (q/p)^x. Fitting e_0=e_d=0 gives

e_x=\frac{x}{q-p}-\frac{d}{q-p}\cdot\frac{1-(q/p)^x}{1-(q/p)^d}.

The expression has a removable singularity at p=q. At equal probabilities, use x(d-x).

Example 1 (Three steps from ruin, ten from the start) A fair walk is absorbed at 0 and at 10, and it starts at 3.

Question. Find the probability of hitting 10 before 0, and the expected number of steps until absorption.

Solution. Fair steps give h_3=3/10. The expected duration is e_3=3(10-3)=21. The probability 3/10 and the expected time 21 answer different questions. A likely ruin, here probability 7/10, can still take many steps when the interval is long.

Watch the assumption

The formulas use absorption at both ends and steps of size exactly one. On the unbounded integer line, return times, recurrence, and drift are a different problem. That walk is the one on Markov chains.

Used in

Taught in Random walks and first passage
Questions that use it (2) — A fair walk between 0 and 8 (answer) · Checking the duration formula
All 3 questions on Random walks and first passage

Used in

See also