Intuitive reason why a simple symmetric random walk is recurrent on $\Bbb Z^2$ and transient on $\Bbb Z^3$.

2.4k Views Asked by At

Polya proved the following very well-known Theorem:

A simple random walk on $\Bbb Z^D$ is recurrent if and only if it is symmetric and $D<3$.

Dropping simplicity (i.e. allowing jumps to non-neighboring states) leaves this result essentially unaltered, as long as the distribution of the increments is not too heavy-tailed (compare e.g. Theorems 5.4.8, 5.4.9, 5.4.14 in the book by Rick Durrett).

I am familiar with common proofs of these results, and of course I am able to see why they work for which dimensions. However, the point of this question is that I'd like to understand these results better on a purely intuitive level.

In view of the law of large numbers (which is very intuitive in itself), it is clear that asymmetry ruins any chance of recurrence. Furthermore, adding dimensions provides more possibilities for the random walker to "get lost", as the probability of walking in "the right direction" decreases. This makes it very plausible that, in the symmetric case, for some $D_0\in\Bbb N \cup \{\infty\}$ we have recurrence in all dimensions $1\le D< D_0$ and transience for all $D\ge D_0$.

It just so happens that this is true and that $D_0=3$. But why? Why not lower or greater? What's so special about two- or three-dimensional space? Is there any geometric reason that makes this more graspable?

I'd be very grateful for any helpful answer!

1

There are 1 best solutions below

7
On

A heuristic argument: The random walk in any dimension tends to stay in a ball of radius $\sqrt{N}$ for the first $N$ steps. In dimension $d$, there are roughly $c N^{d/2}$ points inside the ball of radius $\sqrt{N}$ (for some constant $c$). So, if $d \leq 2$, then it is likely that the $N$ steps of the walk will cover the whole ball and, if $d > 2$, it is unlikely.


Regarding why the walk stays in a ball of radius $N$: Let the individual steps of the walk be $s_1$, $s_2$, ..., $s_N$, so the final position of the walk is $s_1 + s_2 + \cdots + s_N$. Write $E$ for expected value.

We assume that the individual steps are vectors independently drawn from some distribution with $E(s_j) = \vec{0}$ (there is no drift) and $E(|s_j|)$ a constant. Then $$E\left( (s_1 + s_2 + \cdots + s_N)^2 \right) = \sum_{i,j} E(s_i \cdot s_j) = \sum_i E(|s_i|^2) + \sum_{i \neq j} E(s_i) \cdot E(s_j).$$ The first step is linearity of expectation and the second is the statement that $s_i$ and $s_j$ are independent. But we assumed $E(s_i)=\vec{0}$, and the $s_i$ all have the same distribution, so this is just $N E(|s_1|^2)$.

We have shown that $E\left( (s_1 + s_2 + \cdots + s_N)^2 \right)$ grows like $c_1 N$, so we should expect $\left| s_1 + s_2 + \cdots + s_N \right|$ to grow like $c_2 \sqrt{N}$. Making this argument precise will require filling in the exact kind of random walk involved, but hopefully this makes it clear why we expect $\sqrt{N}$.