19
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ An accessible introduction: Random Walks and Electric Networks by Doyle and Snell $\endgroup$
    – Gerald Edgar
    Commented Aug 13, 2010 at 10:25
  • $\begingroup$ 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 $\endgroup$
    – Will Jagy
    Commented Aug 15, 2010 at 0:33
  • $\begingroup$ I had heard that the two cars which collided in 1896 were in a parade, which does not seem random. $\endgroup$
    – Douglas Zare
    Commented Aug 15, 2010 at 5:15
  • $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Commented Aug 17, 2010 at 19:29

5 Answers 5

Reset to default
30
$\begingroup$

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.

Improve this answer
$\endgroup$
16
  • 4
    $\begingroup$ 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? $\endgroup$
    – dvitek
    Commented Aug 13, 2010 at 10:35
  • 2
    $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Commented Aug 13, 2010 at 13:14
  • 1
    $\begingroup$ @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? $\endgroup$
    – Jeremiah Edwards
    Commented Aug 13, 2010 at 14:11
  • $\begingroup$ 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. $\endgroup$
    – Gerald Edgar
    Commented Aug 13, 2010 at 20:41
  • 1
    $\begingroup$ @Gerald: isn't the expected return time of a simple RW on $Z^2$ infinite? $\endgroup$
    – Yemon Choi
    Commented Aug 13, 2010 at 21:03
11
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .