1
$\begingroup$

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!

Improve this question
$\endgroup$
13
  • $\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$
    – Douglas Zare
    Commented Aug 21, 2012 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$
    – TerronaBell
    Commented Aug 21, 2012 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$
    – Douglas Zare
    Commented Aug 21, 2012 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$
    – TerronaBell
    Commented Aug 21, 2012 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$
    – TerronaBell
    Commented Aug 21, 2012 at 20:19

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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$
    – TerronaBell
    Commented Aug 21, 2012 at 17:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .