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 
 A: 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. 
A: 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".
A: I think this is equivalent to one of the walkers standing still and the other taking two steps at a time.
A: 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.
A: 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
