0

Take a one dimensional random walk where the person is initially at the origin, and can move to (x+1,0), or to (x-1,0), each with probability 0.5. What is the expected number of moves to reach the origin? My attempt:

After the first move, you are either at (1,0) or (-1,0). E(reaching origin) = E(reaching (1,0) from (1,0) after the move to (1,0) in step 1) = E(reaching (-1,0) from (-1,0) after the move to (-1,0) in step 1). Hence

$E= 1/2(E + 1)$

$ (1/2)E=(1/2) $

$ E = 1.$

Is this correct?

user2277550
  • 2,194
  • 1
    No, that's not correct. Think about it, you need at least 2 steps to get back to the origin, so the expected value cannot be $1$. Your calculation doesn't make much sense to me, it's hard to tell where exactly you go wrong. I don't know where the $1/2$ comes from, for example. – Ingix Jul 19 '22 at 13:31
  • Try set $E(x)$ is the expectation of steps that starts from $x$ and reaches the origin at the first time, and solves a series of equations on expectation. If you have learned stochastic process, there are some conclusions that can ease the computations. – VicaYang Jul 19 '22 at 13:38
  • Let $E$ expected number of moves to return to origin. Then $E=1+F_1$, where $F_1$ is expected number of moves from origin to 1. $F_1=\frac{1}{2}+\frac{1}{2} (1+F_2)$, where $F_2$ is expected number of moves from origin to 2. $F_2=\frac{1}{2}(1+F_1)+\frac{1}{2}(1+F_3)$. And so on. It seems that $F_i=iE-i^2$, then $E$ must be infinity, because $F_n > 0$ for any natural $n$. – Ivan Kaznacheyeu Jul 19 '22 at 14:41
  • Using Catalan numbers one can write expression $E=\sum_{n=0}^\infty \frac{C_n}{2^{2n+1}}(2n+2)=\infty$ – Ivan Kaznacheyeu Jul 19 '22 at 15:02

2 Answers2

1

No, this is not correct. The number of steps cannot be less than $2$, so the average is at least $2$. You are trying to define $E$ as the expected number of steps to return to the origin, but you did not account for the cases where the second step is away from the origin. You are then not in the starting case, so the approach will not work. You could define $E(n)$ as the expected time to get to the origin from point $n$ and you could write $E(0)=1+\frac 12E(1)+\frac 12E(-1)$ and use the symmetry in $n$ to make this $E(0)=1+E(1)$. You can make an infinite set of equations like this.

Ross Millikan
  • 374,822
  • I think this is helpful, but it may be useful to extend this and explain how the next equation in this set would come about. Though I would probably use generating equations for answering this question. – Gregory Jul 19 '22 at 13:42
0

No. The expected number of steps to reach any point (including returning to $0$ after completing the first step) is $\infty$. See Expected number of steps for reaching $K$ in a random walk .

Andreas Tsevas
  • 2,520