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! :-)


  • $\begingroup$ I don't understand in what sense the distribution is diamond-shaped. The bulk of the probability is roughly circularly arranged, although on the lattice. Only exponentially small wisps fill out a diamond shape instead. So, in what sense are you concentrating on the exponentially small parts? $\endgroup$ Aug 21 '12 at 1:20
  • $\begingroup$ Nope, it's not just exponentially small wisps -- the proof is just too big for the margins. :-) But if you want to see what happens, fix $n$ and consider the ratio $\sum_{k=n+1}^\infty w_k P_k / w_n P_n$ for the weights I gave. Then take the log as $t$ goes to zero; you'll see that the resulting function depends only on the graph distance. $\endgroup$ Aug 21 '12 at 17:18
  • $\begingroup$ If I fix $n=2$, the result of exponentially decreasing weights in that formula is to concentrate on the positive probabilities of smallest $k \gt n$, $k=4$, and the ratio between $P_4$ and $P_2$ is not constant on points of equal graph distance. Specifically, $P_2(2,0) = P_4(2,0) = 1/16$ but $P_2(1,1) = 1/8 \ne P_4(1,1)=3/32.$ $\endgroup$ Aug 21 '12 at 20:09
  • $\begingroup$ Sorry -- let me be more clear. Consider a node at a graph distance $n$ from the origin. The first $n-1$ terms in the sum $\sum_{k=0}^\infty w_k P_k$ are zero (since no random walk of length $n-1$ reaches the node of interest). But evaluate the ratio defined above 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$ Aug 21 '12 at 20:18
  • $\begingroup$ ..and hence the (log of the) solution is proportional to just $n$, the graph distance. (I should also mention that I have performed this experiment numerically and you do indeed recover the diamond-shaped graph distance. This is not merely a guess!!) $\endgroup$ Aug 21 '12 at 20:19

I don't think the decay rate has much to do with it. Instead, the more time passes, the more Gaussian-shaped the function becomes. Indeed, suppose we let $w_k=1$ if $k=\lfloor C h^{-2}\rfloor $ and $0$ otherwise. Then by the Central Limit Theorem, the distribution approaches a Gaussian, and thus in the limit depends entirely on the $l^2$ norm.

  • $\begingroup$ Yeah, I think we're on the same page -- allowing more time to pass is equivalent to putting larger weights on larger values of $k$. So if the weights decay slowly then the central limit theorem will take over. (And if they decay quickly, it won't!) $\endgroup$ Aug 21 '12 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.