Timeline for What is the probability that two random walkers will meet?
Current License: CC BY-SA 2.5
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 24, 2017 at 20:58 | comment | added | Douglas Zare | @user929304: I still don't know what difficulty you are having. | |
| May 24, 2017 at 16:22 | comment | added | user88381 | @DouglasZare Dear Douglas, I am confused as to how one should express the sampling "at even steps" mathematically when describing e.g., the end to end vector of the walk [#]. In a simulation of the walk it is easy to interpret this, but analytically I don't know how. Any hints would be extremely helpful. [#]: e.g., in cases where the walk is sampled at each step, then we have a displacement vector for each step, and we write the end to end vector after $N$ steps as: $\mathbf R = \sum_{i=1}^N \mathbf R_i.$ | |
| May 24, 2017 at 14:47 | comment | added | user88381 | @DouglasZare I meant properties such as average position of the newly defined walker or the mean separation from its initial state. By the way, I just noticed that same-site-visits by parity being ruled out is only given if the walk makes jumps of the type $(x,y)\to (x\pm 1, y) $ or $(x,y)\to (x, y\pm 1) $ and not when "diagonal" jumps are possible too (i.e. $(x\pm 1, y\pm 1).$ | |
| May 24, 2017 at 14:27 | comment | added | Douglas Zare | @user929304: I don't know what you mean by characterizing such walks. The set of functions is very large. | |
| May 24, 2017 at 11:04 | comment | added | user88381 | @DouglasZare thanks a lot, I see now. Would you have a pointer/hint as to how one starts characterising such random walks? (Such as the average position or mean separation of the walker from its initial condition) any advice would be much appreciated. | |
| May 24, 2017 at 1:57 | comment | added | Douglas Zare | @user929304: Yes. $\mathbb{Z}^n$ is bipartite. If one walker is at a position with an even coordinate sum and the other is at a position with an odd coordinate sum, then they will always be at positions an odd distance away, so they can never meet. | |
| May 24, 2017 at 0:41 | comment | added | user88381 | @DouglasZare Hi, just to make sure I understand correctly, by sampling a random walk here at even times we simply mean that though it moves randomly at each step, we only record its position at even time steps, right? Finally, could you please explain what you meant by "meeting is ruled out by parity"? Many thanks in advance, sorry for the rather naive questions :( | |
| Dec 1, 2015 at 20:53 | comment | added | Douglas Zare | There are elementary books that mention random walks, such as the one by Doyle and Snell, math.dartmouth.edu/~doyle/docs/walks/walks.pdf. I don't know whether they have the perspective you would like. If you have $w$ walkers in two dimensions, you can subtract off one walker to have a random walk in $2(w-1)$ dimensions, although the coordinates would be correlated. The correlation doesn't affect whether the walk returns to the origin with probability $1$. A walk in two dimensions returns with probability $1$, but in four ($3+$, of course) there is a positive probability it does not. | |
| Dec 1, 2015 at 16:11 | comment | added | Douglas Zare | @Phonon: In two dimensions, more than two random walkers are not almost sure to meet other than pairwise. In one dimension, three walkers of the same parity will meet simultaneously almost surely, and you can subtract one motion from the other two, which would give a $2$-d random walk, but the coordinates would be correlated. | |
| Dec 1, 2015 at 11:19 | comment | added | Ellie | Very neat way of solving it! Does this approach in general remain feasible for multiple (>2) random walkers? | |
| Nov 5, 2010 at 11:41 | comment | added | Spencer | @Jeremiah You might be interested in "The Optimal Strategy for Symmetric Rendezvous Search on K3": arxiv.org/abs/0906.5447v1 The general conjectured best strategy (I think) is you alternate moving one step and standing still: The other person moves when you wait and waits you move. | |
| Aug 27, 2010 at 14:40 | vote | accept | Jeremiah Edwards | ||
| Aug 13, 2010 at 21:03 | comment | added | Yemon Choi | @Gerald: isn't the expected return time of a simple RW on $Z^2$ infinite? | |
| Aug 13, 2010 at 20:41 | comment | added | Gerald Edgar | So, according to the solution here, the probability of eventually meeting is the same if both walk or if only one walks, but the expected time before that meeting is half if both walk. | |
| Aug 13, 2010 at 14:11 | comment | added | Jeremiah Edwards | @Gerry, that's essentially what me ask this question. If you are trying to meet someone at a vaguely defined rendez-vous point, is it better if both of you walk around looking? | |
| Aug 13, 2010 at 13:14 | comment | added | Gerry Myerson | If I'm not mistaken, Polya was inspired by arriving at the same point several times as some couple when he and they were out for (separate) walks. This incident was discussed in an MO question some months ago. | |
| Aug 13, 2010 at 10:35 | comment | added | dvitek | If you're tricky and say that they can meet in the middle of a step - i.e., if one is going from (0,0) to (1,0) and the other is going in reverse - then it's always 1. You just consider that the resultant random walk must hit (1,0) infinitely many times*, and there is probability zero that it will never hit (-1,0) from (1,0). *I'm not actually 100% on this, but the fact that a random walk always returns to the origin makes me think this should be true. Can somebody confirm? | |
| Aug 13, 2010 at 10:31 | history | answered | Douglas Zare | CC BY-SA 2.5 |