exactly simulating a random walk from infinity

2011-06-07T23:11:25Z

In diffusion-limited aggregation on the square lattice, one lets a particle do "random walk from infinity" until it hits the current aggregate, at which point the site occupied by the particle is added to the aggregate; then the particle is started from infinity again, and so on.

This begs the question: What does it mean to let a particle do random walk from infinity? Or, in a more practical vein, how does one simulate such a walk?

The answer to the first question is, Random walk from infinity is just the limit as $v$ goes to infinity of random walk started at $v$. More precisely, for each $v$, we can look at random walk that starts from $v$ and stops when it hits (0,0) $T$ time-steps later (where the hitting-time $T$ is random), and we can re-index it so that it starts at $v$ at time $-T$ and hits (0,0) at time 0. This gives us a probability measure on paths that end at (0,0). Now we take the limit as $v$ gets farther and farther from (0,0), and we do some work and show that the law of the random path approaches a limit, and that this limit doesn't depend on how $v$ goes off to infinity. Actually I'm bluffing; I don't know how to prove this. I assume it's in the literature; can anyone point me to a relevant book or article?

Now we come to the problem of simulation. What we want is a black box that prints out the path in reverse, chugging away until we turn it off. Note that this is not the same as having a black box that, for any $n$, prints out the last $n$ steps of the path; for, after the box has printed out that path, if we decide we want to know "What happened before that?", we can't find out by increasing $n$ and consulting the box again, because then the black box will give us the last $n+1$ steps of a DIFFERENT random path. On the other hand, if we had a box that, given the last $n$ steps of the path, could sample from its (up to 4 different) continuations one step back into the past with the appropriate conditional probabilities, one could use this box iteratively to build the sort of black box I want. It might be very hard to compute these conditional probabilities in the case of the square grid, but I suppose that would be one way to do it. A more robust (and, to my way of thinking, prettier) solution would be something more combinatorial, using ideas like coupling and domination.

Answer by Ori Gurel-Gurevich for exactly simulating a random walk from infinity

2011-06-08T06:40:18Z

To answer your first question (regarding existence of the limit): I never remember references, but all you have to do here is show that for any two far enough starting points, there is a coupling of the RWs started at them, such that with high probability the two paths hit the aggregate at the same point (for example, because they start walking together before hitting the aggregate). In $\mathbb{Z}^2$ it's pretty straightforward to do: if you let one walker walk till it hits the aggregate, then with high probability its path will separate the aggregate from the starting point of the second walker. Then you let the second walker walk till it hits the first path and follow this path thereafter.

As for the second question: as I said, I never remember references, but I believe that you can find how to calculate the harmonic measure exactly using the 2d potential kernel in Spitzer's "Principles of Random Walks".

To elaborate on George's comment and your reply (again, I'm pretty sure all this appears in Spitzer): Let $A$ be a finite set of vertices and start a SRW at $X_0=x$ and for some $y\in A$ we look at $\mathbb{P}(X_{\tau_A}=y)$, where $\tau_A$ is the hitting time of $A$. Then this probability is equal to $\sum_w \mathbb{P}(w)$ where the sum is over all paths starting at $x$ and ending at $y$ and not going through $A$. Since the SRW on $\mathbb{Z}^2$ is reversible this is equal to the sum over paths strating at $y$ and ending at $x$ and not going through $A$. This is exactly the expected number of visits to $x$ for a SRW started at $y$ and killed upon returning to $A$. This is proportional to the probability of hitting $x$ before returning to $A$ (again, when starting at $y$). If we take $x$ to be far away we see that conditioning on hitting $x$ before returning to $A$ is the same (asymptotically) as conditioning on the walk not returning to $A$ for a long time.

More can be said about the distribution of the conditioned RW, but right now I have to go.

exactly simulating a random walk from infinity - MathOverflow

exactly simulating a random walk from infinity

Answer by Ori Gurel-Gurevich for exactly simulating a random walk from infinity