Take the 2-minute tour ×

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.

share|improve this question
The chain in this problem is the same as the distance to zero of a random walk on the points $\{-n, \cdots, 0, \cdots n\}$ (where with probability $1/2$, starting at $\pm n$ you move to $\mp n$). Perhaps that allows you to reduce to a known problem (this is how i interpreted the answer in the back of the book). –  ShawnD Oct 23 '11 at 6:01
@Shawn Yes, for the random walk on a circle the expected time to hit $y$ starting at $x$ is the product of the clockwise and counterclockwise distances between $x$ and $y$. For your chain, these give $n$ and $n+1$ which explains the answer that joriki got using difference equations. –  Byron Schmuland Oct 23 '11 at 6:28
Thanks Shawn and Byron. I get it now. Still the book does not seem to specify that you can go from n to -n and back, and without this detail the distance to zero is not really equivalent, so they get the wrong answer $n^2$. –  wircho Oct 23 '11 at 17:30
add comment

1 Answer

up vote 4 down vote accepted

The general rule for $k\ne n$ yields the recurrence


with general solution


The boundary conditions are $t_0=0$ and $t_n=\frac12(t_n+t_{n-1})+1$, which leads to $b=0$ and


$$n-\frac a2+\frac12=0,$$


and thus


share|improve this answer
Nice solution! Thanks. –  wircho Oct 23 '11 at 17:31
add comment

Your Answer


