# exactly simulating a random walk from infinity

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.

-
It should just be the same thing as a random walk conditioned not to hit the origin at any positive time. –  George Lowther Jun 7 '11 at 23:23
That's believable, but can you prove it to me? (Indeed, what does it mean to condition on this event, given that the event has measure zero? I guess it means, condition on the event no-return-to-the-origin-up-to-time-T and then take the limit as T goes to infinity.) Also, assuming that your assertion is true, does it give a workable simulation scheme? I don't think that the law of this conditioned walk is just "pick a random neighbor as long as it isn't the origin". –  James Propp Jun 8 '11 at 12:40
I edited my answer to explain the equivalence. I may add more later. –  Ori Gurel-Gurevich Jun 8 '11 at 17:34

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.

-
This looks like the right way to think about backwards walk, but I got lost at "This is exactly the expected number of visits to x for a SRW started at x and killed upon returning to A." Is there a typo here? What has happened to the dependence on y? –  James Propp Jun 9 '11 at 2:36
That was a typo, I edited it now. –  Ori Gurel-Gurevich Jun 9 '11 at 3:37
The inclusion of y helps, but I still don't get it. Try it on the 3-vertex path-graph {0,1,2} with transition probabilities p(0,1) = p(2,1) = 1, p(1,0) = p(1,2) = 1/2, taking y=0, x=1, and A = {y}. Then the path-sum is just p(0,1) = 1. On the other hand, the expected number of visits to 1 for a SRW started at 0 and killed upon returning to 0 is 2 (and even without knowing anything about geometric random variables one can see that it's strictly greater than 1, since the walk gets to visit 1 once for free, and gets to visit again with positive probability). Am I missing something? –  James Propp Jun 9 '11 at 12:26
For Uri's argument to work you need to be doing the walk on a regular graph, otherwise there is another factor which is the ratio of the degrees of $x$ and $y$. –  Louigi Addario-Berry Jun 9 '11 at 13:00
What Louigi said (also, Ori, not Uri). –  Ori Gurel-Gurevich Jun 9 '11 at 15:04