A random walk moves from k to k+1 with probability 1/2 and to k-1 with probability 1/2, except when k=n, in which case it remains at n with probability 1/2 and moves to n-1 with probability 1/2. Suppose it starts at n. Let T be the first time the path reaches 0. What is the expected value of T?
Is there an easy way to solve this using well known facts about Markov chains? This is problem 2.3 of the book Markov Chains and Mixing Times (by David A. Levin, Yuval Peres, and Elizabeth Wilmer). Their solution is clearly wrong as it seems to assume the path goes down to n-1 with probability 1.
Best Answer
The general rule for $k\ne n$ yields the recurrence
$$t_k=\frac{t_{k-1}+t_{k+1}}2+1$$
with general solution
$$t_k=-k^2+ak+b\;.$$
The boundary conditions are $t_0=0$ and $t_n=\frac12(t_n+t_{n-1})+1$, which leads to $b=0$ and
$$\frac12\left(n^2-an-(n-1)^2+a(n-1)\right)+1=0\;,$$
$$n-\frac a2+\frac12=0,$$
$$a=2n+1\;,$$
and thus
$$t_n=-n^2+(2n+1)n=n^2+n\;.$$