2
$\begingroup$

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

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ nice example. I hadn't considered cases where some values were equal. thanks $\endgroup$ Jul 24, 2023 at 15:22

You must log in to answer this question.

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