Exit time of simple random walk on $[-a,b]$

Question

It can be proved using martingales and the optional stopping theorem that the expected exit time of a random walk on $(-a,b)$ beginning at $0$ with $a,b>0$ is $ab$. How can this be shown using a recurrence relation?

Answer 1

Let $u(x)$ be the expected time to hit the boundary starting from $x$, and let $L$ be the generator of your process. Then $u$ satisfies:

$$u(-a)=u(b)=0 \\ Lu=-1.$$

This is a Backward Kolmogorov type equation, and is quite general. In discrete time and discrete space, $L=P-I$, where $P$ is the probability transition matrix. So your $L$ matrix is tridiagonal, with diagonal entries of $-1$ and super/subdiagonal entries of $1/2$.

A quick way to analyze this problem is to see that your $L$ looks like half of an approximation of the second derivative of a smooth function with $h=1$, and that this approximation is actually exact for a quadratic function. Since the right hand side is constant, a quadratic function with second derivative $-2$ satisfies the equation. And we know the roots, so the solution is

$$u(x)=-(x+a)(x-b).$$

A longer but more general way is to read off the recursion $u_{n+2}/2 - u_{n+1} + u_n/2 = -1$ from the matrix equation. The characteristic equation of this recursion is $\lambda^2/2 - \lambda + 1/2 = 0$, which has roots $\frac{1 \pm \sqrt{1-1}}{1}=1$. That is, it has a double root of $1$. Recurrences of this type are fairly well-known to have linear homogeneous solutions. From this perspective you expect a quadratic solution to the inhomogeneous problem (given a polynomial inhomogeneity of degree $n$ and a recurrence of order $m$, the default ansatz for a particular solution is a polynomial of degree $n+m$). Now again you know the roots so you get the same solution.