0
$\begingroup$

I just read a proof that simple symmetric random walks on discrete state spaces are recurrent in 1 and 2 dimensions but transient in 3 or more dimensions. Does anyone have some intuition as to why this is true? Examining the proof isn't helping me that much.

After reading Robert's answer (which actually resembles the proof I read!) I feel that I wasn't clear enough with my question.

In particular, is there something that is making 2 dimensions the magic number? (or 3 depending on how you look at it)

1 Answers 1

1

It's convenient to consider the variant of the 2D walk that has you take both a horizontal and a vertical step at the same time, thus executing an ordinary random walk on a larger lattice at a 45 degree angle to the first (the black squares on a checkerboard). This makes your $x$ and $y$ coordinates independent random variables, which they are not for the ordinary 2D walk. Now the probability that $x=0$ at time $2n$ is ${{2n} \choose n}/2^{2 n}$ which is approximately $const/\sqrt{n}$.

An "intuitive" plausibility argument for this is that the variance of $x$ increases by 1 at each step, so the standard deviation is $\sqrt{n}$, i.e. there should be something like $\sqrt{n}$ possible values that have comparable probabilities, so about $1/\sqrt{n}$ for each.

Thus the probability that both $x=0$ and $y=0$ at time $2n$ is the square of this probability, which is approximately $const/n$.

Now the expected number of returns to the origin is the sum of these probabilities, which is $\infty$ since the harmonic series diverges.

But if the probability of ever returning to the origin was $p < 1$, the expected number of returns would be the finite number $p/(1-p)$ (think of a sequence of independent coin-flips with probability $p$ of heads: the expected number of consecutive heads is $p/(1-p)$).

In 3D, the analogous calculation (actually for a walk on a body-centred cubic lattice) shows that the probability of return at time $2n$ is approximately $const/n^{3/2}$. But this time the series is convergent, so the expected number of returns is finite, and therefore the probability of ever returning must be less than $1$.

  • 0
    The point is that $\sum_{n=1}^\infty n^{-d/2}$ converges if d > 2 and diverges if $d \le 2$.2012-09-19