54
$\begingroup$

How does one prove that a simple (steps of length $1$ in directions parallel to the axes) symmetric (each possible direction is equally likely) random walk in $1$ or $2$ dimensions returns to the origin with probability $1$?

Edit: note that while returning to the origin is guaranteed $(p = 1)$ in $1$ and $2$ dimensions, it is not guaranteed in higher dimensions; this means that something in a correct justification for the $1$- or $2$-d case must fail to extend to $3$-d (or fail when the probability for each direction drops from $\frac14$ to $\frac16$).

  • 0
    Can you think of a reason why it should hit points that are not at the origin?2010-07-23
  • 2
    @Jonathan: I'm not sure what you mean--in 1-d, the random walk hits every integer with probability 1, and in 2-d, the random walk hits every lattice point with probability 1.2010-07-23
  • 0
    Then I guess I am confused by the question :(2010-07-23
  • 0
    do you mean in the limit it will be found at the origin?2010-07-23
  • 0
    What I mean is that P(at some time during the random walk, the point will be back at the origin)=1. This has the consequence that the number of times the random walk visits the origin is infinite.2010-07-23
  • 2
    I think it will hit all points a infinite number of times.2010-07-23
  • 0
    Yes, it will (in 1 and 2 dimensions). The reasoning from returning to the origin once to hitting every point infinitely many times is much easier than the proof (not that I can do either off the top of my head right now).2010-07-23
  • 2
    @Isaac: If you know you will hit every point with probability 1, then you will return to each point with probability 12010-07-23
  • 0
    @Casebash What he means is where is likely to "converge" so it is the ratios that matter.2010-07-23
  • 0
    @Casebash: Yes, this is true, but I know all that from knowing that the probability of returning to the origin is 1. (Er, what I'm trying to say is that talking about the first return to the origin is the simplest version of a number of equivalent statements, including that every point is visited infinitely many times.)2010-07-23
  • 0
    @Isaac: True. There is a non-zero probability of reaching each point from the origin. If you can show you return to the origin, then you get an infinite number of retries2010-07-23
  • 0
    @Casebash good reasoning. Another way is to redefine the origin since there is nothing special about it.2010-07-23
  • 0
    A Modern Course in Statistical Physics 2nd Edition by L. E. REICHL equation 4.101 has the final result. The proof is there.2015-07-29

9 Answers 9