# Alternate proof for two random walks in $d$ dimension meeting

I was coming up with an alternate approach to finding the probability of two random walks starting at origin in $$d$$ dimensions. Let $$S_n$$ be the Manhattan distance between the points at time $$n$$. Since both points change the Manhattan distance by $$\{ -1,1 \}$$ with equal probability, $$S_n$$ is a random walk with step $$X_n$$ being $$2$$ and $$-2$$ with probability $$0.25$$ each, and $$0$$ with probability $$0.5$$.

Now, since $$S_n$$ is a one-dimensional random walk, independent of the original dimension $$d$$, it must return to the origin. If $$S_n$$ is $$0$$, it means the random walks intersect with probability $$1$$.

But doesn't this contradict a result by Polya as given in the Wikipedia link for random walk. Any help is appreciated.

Another variation of this question which was also asked by Pólya is: "if two people leave the same starting point, then will they ever meet again?"[10] It can be shown that the difference between their locations (two independent random walks) is also a simple random walk, so they almost surely meet again in a 2-dimensional walk, but for 3 dimensions and higher the probability decreases with the number of the dimensions.>

• Check those probabilities again. What happens if $A$ moves $+(1,0)$ and $B$ moves $-(1,0)$? Commented Jul 24, 2023 at 14:44
• Sorry, was a typo on my part. it's {2,-2,0} Commented Jul 24, 2023 at 15:17

If the points are at $$(3,8,9)$$ and $$(7,8,9)$$ after $$n$$ steps then your $$S_n=|7-3|+|8-8|+|9-9|=4$$ and
• the probability it becomes $$S_{n+1}=2$$ is $$\frac1{36}$$ (they both move towards each other),
• the probability it stays at $$S_{n+1}=4$$ is $$\frac{10}{36}$$ (one moves towards the other but the other moves away)
• the probability it becomes $$S_{n+1}=6$$ is $$\frac{25}{36}$$ (they both move away from each other).
So $$S_n$$ is not a symmetric random walk. Another issue is that the probabilities depend on the relative positions.