I'd like to get asymptotics on the probability that n independent random walks coalesce. Start with n independent walks. As soon as two walks intersect they become one walk and continue evolving as SRW. I want asymptotics as the distance between initial starting points grows. For two SRW this is related to the Green's function and we have $G(x,y) \asymp \frac{1}{|x-y|^{d-2}}$. I know that Greg Lawler (and others?) have studied the probability that two or more random walk paths intersect but this isn't quite what I want. Is what I'm asking a simple consequence of Lawler's work and/or does anyone know if this problem has been looked at before? Thanks very much for any help.
1 Answer
$\begingroup$
$\endgroup$
Intersecting random walks can intersect at any time, colliding walks have to be at the same point at the same time. Collision is a much stronger condition, and gives very different asymptotic behavior, and a different critical dimension.
For intersections, the critical dimension is 4, meaning that below 4 dimensions you expect intersections and above 4 dimensions you don't, with 4 dimensions being marginal. The essence of the argument is that each random walk trajectory has fractal dimension 2, since each epsilon ball you put on the trajectory only covers a time interval of size epsilon squared. So the condition of intersection is similar to that for randomly placed 2-d planes, up to logarithmic corrections.
The critical dimension for your problem is 2, meaning that in more than 2 dimensions, there will be a power-law falloff in the number of collisions in the limit small grid/large distances.
For two D-dimensional random walks x1 and x2, their difference s=x1-x2 is a random walk. The time this walk takes to reach the origin gives the coalescing time, and this is the classical Polya problem with critical dimension 2. For two walks a distance 1 on an $\epsilon$ sized grid, the coalescing probability up to any fixed time vanishes as $\epsilon^{d-2}$ for small $\epsilon$ up to log corrections in 2 dimensions.
I am unsure if you are only interested in the $\epsilon$ power law behavior, or if you are interested in the detailed pattern of coalescing, which depend on the initial geometry. There is always the problem that you are asking about D>2, where chances are that there will be no collision for a finite number of points at large initial positions.
For three random walks, you can consider the three differences s=x1-x2 t=x2-x3 u=x3-x1 which are random walks only correlated to the extent that they obey s+t+u=0, which make skewed coordinates on a 2D hyperplane, and the random walk in x1,x2,x3 becomes an ordinary random walk in 2D dimensions, with absorbing boundaries on s=0,t=0,u=0. Your problem is then the condition that a random walk will hit and stick to these hyperplanes, and then continue walking on the hyperplanes, until it reaches the origin. There is an enormous literature on random walks with these types of absorbing boundaries. But I have the feeling you want the limit of large numbers of walkers, or a finite density of walkers, where this type of thing is useless.
For D=1, for collisions of many one dimensional random walks, variations on this problem have been extensively studied in the physics literature under the name "vicious random walkers". For D=2, the marginal case, and "inbetween" there is an interesting variation on this problem with surprising behavior in this Cardy paper (http://prl.aps.org/abstract/PRL/v77/i23/p4780_1). This is the problem of annihilating walks--- when two walks collide, they both disappear. The (very hard to make rigorous) analysis in his paper should be adaptable to the case of coalescing walks, but both the diagrams and behavior in simulations are different.
