3
$\begingroup$

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.

  • 2
    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).2011-10-23
  • 1
    @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.2011-10-23
  • 0
    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$.2011-10-23

1 Answers 1

5

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\;.$$

  • 0
    Nice solution! Thanks.2011-10-23