# Collisions in random walk in $\mathbb{Z}^n$

Given a set $S$ of $r$ points in $\mathbb{Z}^n$, $S=(p_1,p_2,p_3.., p_r)$ , each a starting point for random walk with step size 1. What is the probability they will all eventually meet at the same point?

Ie. at each timestep add either -1 or 1 with 50% probability to a uniformly random coordinate of each point in $S$ separately.

Given S, what is the probability that eventually all points in S are the same?

-
All of them at the same time at the same point? – Fabian Apr 6 '11 at 18:40
@solomoan: You can get the $\mathbb{R}$ symbol using "\mathbb{R}". Also, you need to enclose $\TeX$ markup in dollar signs (like this: \$\mathbb{R}^n\$); else you just get the garbled stuff that you're getting. – joriki Apr 6 '11 at 18:50
@Fabian Yes @jori thanks – user1708 Apr 6 '11 at 18:51
Presumably parity is sorted out - otherwise they can never meet. – Henry Apr 6 '11 at 19:20
@solomoan: Are you aware that for a one dimensional random walk the expected time for first return to the origin is infinite. Several points trying to meet will not arrive faster. – Henry Apr 6 '11 at 19:21

Since a random walk in $n(r-1)$ dimensions is transient (it has a positive probability of not returning to the origin) for $n(r-1) \ge 3$, the probability that your random walk has all $n$ points coincide at some time is less than $1$.

An upper bound for the probability that the walks will coincide at some point is the expected number of meetings $\sum_t P(\text{walks meet at time }t)$. This probability can be written as a multidimensional sum of binomial coefficients over a power of $2n$.

A standard trick for random walks applies. Let $M(x)$ be the generating function for the probability of meeting after $t$ steps. Let $O(x)$ be the generating function for the probability that a random walk starting at the origin returns to the origin in $t$ steps. Let $F(x)$ be the generating function for the probability of first meeting after $t$ steps. Then $M(x) = O(x)F(x)$, so $F(x) = M(x)/O(x)$. To compute the probability of ever meeting $F(1),$ you can compute $M(1)/O(1)$, the expected number of meetings divided by the average time at the origin if the points start at the origin.

I don't anticipate a simple closed form for any of these, although it would not surprise me if there were a way to give the probabilities as values of hypergeometric functions, particularly for $n=1$.

-
I'm curious why this was voted down. – Douglas Zare Apr 7 '11 at 11:56

Please describe your problem more careful - you have some finite set $E\subset \mathbb{R}^n$ and what about random walks? Where does they start, how many of them, of what type?

Say, given $m$ stochastic processes in discrete time you can define $$f(x_1,...,x_m) = \sum\limits_{i\neq j} (x_i - x_j)^2$$ and look for the probability that $f(X_1,...,X_n)$ will reach the zero level. For any finite horizon you can solve it as a iterative procedure. For an infinite horizon it depends on the distribution of your random walks - please provide more details.

Edited: for a compact set the probability will be always $1$. On the other hand, the set $\mathbb{R}^n$ is not a compact. You can consider your process $X = (X_1,...,X_r)$ as a Markov chain - and hence this is a problem of reachability of the line $A = \{x_1=x_2=...=x_n\}$. Since your Markov chain has infinitely many states, I do not think there are developed algorithms to calculate this quantities.

-
Why the downvote? – Yuval Filmus Apr 6 '11 at 20:48
Could you clarify this thing? Is the probability 1 to my question or not ? – user1708 Apr 6 '11 at 20:51