Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
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

5 Answers 5

up vote 27 down vote accepted

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.

share|improve this answer
4  
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
2  
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
1  
@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
1  
@Gerald: isn't the expected return time of a simple RW on $Z^2$ infinite? –  Yemon Choi Aug 13 '10 at 21:03

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

share|improve this answer

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".

share|improve this answer

As above, partition all the points of the lattice into two sets (even vs. odd) based on the point's Manhattan-distance from the origin point of the lattice in which the random-walk occurs. If walker A and walker B both start in the odd partition or both start in the even partition, then given infinite time, and given that each walker must move one step with probability 1/4 for the N-E-S-W directions for each time step, then ultimately the two walkers will at some point occupy the same lattice point. If at the start, walker A begins in the odd partition and walker B begins in the even partition (or vice-versa, walker A starts in even, walker B starts in odd), then the probability that they will occupy the same lattice point is zero.

share|improve this answer

If your "steps" correspond to time, then this is like asking for the time for a diffusion limited chemical reaction of two particles, A+A->B. There is a paper on this problem by David Torney, from 1983; it may be useful for you in its approach. Dave Dunlap http://pubs.acs.org/doi/pdf/10.1021/j100234a023

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.