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!

-
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

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.

-
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