Consider an integer lattice $\mathbb{Z}^2$ where grid points are separated by a distance $h$. Loosely speaking, a random walk of length $k$ is a sequence of lattice points $(x_1,\cdots,x_k)$ generated by starting out at the origin and repeatedly moving to one of four immediate neighbors with equal probability $\frac{1}{4}$. Let $P_k: \mathbb{Z}^2 \rightarrow \mathbb{R}$ denote the probability that a random walk of length $k$ ends at a given lattice point, and consider the distribution

$$ P = \sum_{k=0}^\infty w_k P_k $$

where $\sum_{k=0}^\infty w_k = 1$. We can interpret $P$ as the probability that our walk ends at a given lattice point, given that we chose to take a path of length $k$ with probability $w_k$.

It is clear that the behavior of $P$ depends heavily on the choice of weights $w_k$. For instance, if we set $w_n=0$ for all $n$ above some fixed index $N$, then the support of $P$ is of course contained in a finite $\ell_1$-ball around the origin. Similarly, if the weights $w_k$ decay very rapidly then for any fixed $n$ the $n$th term will dominate the sum of the remaining terms and again the distribution $P$ will depend primarily on the $\ell_1$ distance to the origin, i.e., the distribution will be sort of ``diamond-shaped.'' (To give at least one concrete example, let $w_k = (4t)^k/(1+4t)^{k+1}$ and consider what happens as $t$ goes to zero.) For weights that decay *less* rapidly, I hear a lot of folklore about how you get something that looks vaguely Gaussian (hence, not diamond-shaped), but I am having a hell of a time tracking down a precise statement of this idea. More specifically, my question is this one:

**Question**: Under what conditions on $w_k$ is the distribution $\lim_{h \rightarrow 0} P$ purely a function of the $\ell_2$ (i.e., Euclidean) distance?

In other words, how do you take a walk around Manhattan but end up with a distribution that is "round" instead of diamond-shaped? If you can't get something that's purely a function of the Euclidean distance, how close can you get? Can you get something that looks like a Gaussian? Etc.

References are appreciated as long as they are relevant to this *specific* question -- I am not just looking to read about Pólya for the $n$th time! :-)

Thanks!

at node $i$. As $t$ goes to zero, this ratio goes to zero. Hence the only term contributing to the distribution at $i$ is the $n$th term, which up to a constant looks like $(4t/1+4t)^n P_k^i$. Take the log of this quantity and you get $n \log (4t/1+4t) + \log(P_k^i)$. But as $t$ goes to zero the first term dominates... $\endgroup$ – TerronaBell Aug 21 '12 at 20:188more comments