Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
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). –  ShawnD Oct 23 '11 at 6:01
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. –  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

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.