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.

  • 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