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.

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)

share|improve this question
add comment

1 Answer

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

share|improve this answer
    
Thanks Robert. I see that the "sum of these probabilities diverge" when we have 1 or 2 dimensions. But is there something special about this simple symmetric random walk that is interacting with the dimension number so that 2 is the largest number of dimensions for which the sum of the probabilities diverge? –  Alex Olssen Sep 19 '12 at 5:26
    
The point is that $\sum_{n=1}^\infty n^{-d/2}$ converges if $d > 2$ and diverges if $d \le 2$. –  Robert Israel Sep 19 '12 at 5:30
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.