# What is the probability that two random walkers will meet?

It is a well known result that a random walk on a 2D lattice will return to the origin see Polya's random walk constant. Based on this, it is not a big stretch to conclude that the random walk will visit every point of the plane with probability 1. A bit more surprising is the fact that this is not true in higher dimensions (see the link above).

My question is the following: What is the probability that two random walks with distinct origins will arrive at the same point after the same number of steps?

I think it's pretty clear that the answer will depend on the distance between the origins of the walks. So far, I've been trying reduce this to a problem of one random walk in a higher dimensional lattice, but I'm not sure if this is a good approach.

In case the answer is obvious, this problem is easy generalize (higher dimensional lattices, more random walks, etc.). I'd appreciate a reference or two where I could learn more.

Thanks

-
An accessible introduction: Random Walks and Electric Networks by Doyle and Snell –  Gerald Edgar Aug 13 '10 at 10:25
Sorry I can't get better information, but anyway:  "In 1896 there were only four cars registered in all the United States. Two of them collided with each other in St. Louis."  More trustworthy early records also involve a pedestrian or bicyclist, that does not seem to fit two random walkers.  news.carjunky.com/car_insurance/…  deadlyroads.com/media.html  en.wikipedia.org/wiki/Henry_H._Bliss –  Will Jagy Aug 15 '10 at 0:33
I had heard that the two cars which collided in 1896 were in a parade, which does not seem random. –  Douglas Zare Aug 15 '10 at 5:15
Douglas, I am forced to agree. There seems to have been a National Geographic magazine article that included early automobiles and early accidents and collisions. And there was surely a thriving newspaper in St. Louis by then. –  Will Jagy Aug 17 '10 at 19:29

The difference between the positions is another random walk in the same dimension. You can either view the steps as different, or sample a random walk at even times. So, the probability is $0$ if meeting is ruled out by parity, and $1$ in the plane if meeting is possible.

-
If you're tricky and say that they can meet in the middle of a step - i.e., if one is going from (0,0) to (1,0) and the other is going in reverse - then it's always 1. You just consider that the resultant random walk must hit (1,0) infinitely many times*, and there is probability zero that it will never hit (-1,0) from (1,0). *I'm not actually 100% on this, but the fact that a random walk always returns to the origin makes me think this should be true. Can somebody confirm? –  drvitek Aug 13 '10 at 10:35
If I'm not mistaken, Polya was inspired by arriving at the same point several times as some couple when he and they were out for (separate) walks. This incident was discussed in an MO question some months ago. –  Gerry Myerson Aug 13 '10 at 13:14
@Gerry, that's essentially what me ask this question. If you are trying to meet someone at a vaguely defined rendez-vous point, is it better if both of you walk around looking? –  Jeremiah Edwards Aug 13 '10 at 14:11
So, according to the solution here, the probability of eventually meeting is the same if both walk or if only one walks, but the expected time before that meeting is half if both walk. –  Gerald Edgar Aug 13 '10 at 20:41
@Gerald: isn't the expected return time of a simple RW on $Z^2$ infinite? –  Yemon Choi Aug 13 '10 at 21:03
show 1 more comment

I think this is equivalent to one of the walkers standing still and the other taking two steps at a time.

-

First, if the walks are on a Cartesian grid, then there is a bipartitioning of the network into 2 subsets (say A & B) of sites each consisting of the neighbors of others. The 2 walkers then remain on different sets A & B if they start on different sets, so that the probability of meeting on the same site is 0 -- as already noted by D. Zare above. If a non-bipartite grid (say the triangular grid) is used for the random walk, then this qualification would not apply.

Second, in 1 dim starting on the same (say even) subset of sites, the pair of walkers is equivalent to a single walk taking steps of -2, 0, or +2 with respective probabilities 1/4, 1/2, 1/4 -- and the question devolves to whether this new single walk will ever hit the origin (given that the initial distance from the origin is even). Polya's proof tells us that this new walk will eventually hit the origin with ultimate certainty.

Third, in 2 dim starting on the same subset of sites, the pair of (original) walkers is equivalent to a single walk taking steps of appropriate sizes -- if the step for original walker 1 is s(1) & for original walker 2 is s(2), with joint probability (1/4)x(1/4), then the new walk takes a step S with a probability which is 1/16 times the number of (ordered) pairs s(1) & s(2) which add to give S. Again Polya's proof tells us that the ultimate probability of the new walk hitting the origin is 1.

In higher dimensions the probability again following Polya is strictly less than 1.

The whole idea is that Polya's proof is robust under certain modifications to the random walk. In 2-dim the walk can be modified to have different probabilities for horizontal & vertical steps -- or diagonal steps can also be allowed (though then the "parity" considerations do not apply). Polya's proof however fails if the walk is given an "inversion-nonsymmetric" bias, say with different probabilities in the east & west (or north & south) directions. It also seems to me that if the walk is on a fractal grid, that the certain return should be for dim less than or equal to 2, while uncertain return should apply for dim 2+eps for all eps>0. Questions of what happens with a Cartesian grid for which edges are randomly deleted (with some probability p) also seems interesting -- and I think has perhaps been considered in connection with "percolation theory".

-