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 am seeking conditions on the distribution of the step sizes that guarantee that a random walk on the 2D lattice will return to the origin (with probability 1). Essentially, under what conditions can Pólya's theorem be proved? Certainly it holds if the steps are of size 1 (and equally probable in all directions), and I believe if the variance of the step sizes is finite, the return probability is still 1. But what about distributions with infinite variance, like the Lévy distribution? Does "Lévy flight" return to the origin? And more generally, are there conditions on the distribution that guarantee this return?

This is likely all well known, and if so, pointers to the relevant literature would be appreciated. Thanks!

share|improve this question
1  
In case you don't know this exists. math.stackexchange.com/questions/536/… –  BBischof Nov 6 '10 at 2:57
    
@BB: Thanks, I did look at that before posting. The answers do not seem to resolve my question, except perhaps by implications I do not see... –  Joseph O'Rourke Nov 6 '10 at 12:20

1 Answer 1

up vote 2 down vote accepted

You are correct. The "crude" criterion for recurrence of a 2d random walk is $\mu=0$ and $\sigma^2<\infty$ for the jump distribution. The jump sizes are otherwise unrestricted.

The "detailed" criterion involves the characteristic function $\phi$ of the jump distribution, i.e., its Fourier transform. It says that 2d random walk is transient or recurrent as the real part of $(1-\phi(\theta))^{-1}$ is Lebesgue integrable on a neighborhood of the origin.

These results are from Section 8 of Spitzer's Principles of Random Walk (2e).

Spitzer gives a detailed example of symmetric one-dimensional random walks, and shows that their recurrence or transience depends on the size of the tail of the jump distribution. That is, he supposes that $$0<\lim_{|x|\to\infty} |x|^{1+\alpha}P(0,x)=c<\infty,$$ and concludes that this walk is recurrent when $\alpha\geq 1$ and transient when $\alpha<1$.

So, somewhat unexpectedly, there exist symmetric transient random walks in one dimension. Their jump distribution has such large tails that the walk leaps back and forth with large jumps and satisfies $\liminf_n X_n=-\infty$ and $\limsup_n X_n=+\infty$ without a guarantee of returning to the origin.

It should be possible to modify his arguments to the two dimensional case.

share|improve this answer
    
This is an amazingly clear and thorough answer. Thanks so much! –  Joseph O'Rourke Nov 6 '10 at 18:00
    
If I may press on one specific point, does "Lévy flight" return to the origin? Or does it depend on the precise exponent of that power law? –  Joseph O'Rourke Nov 6 '10 at 18:52
    
Posted a related question to MO: mathoverflow.net/questions/45098/… . –  Joseph O'Rourke Nov 6 '10 at 21:07

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.