Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.