0
$\begingroup$

I was wondering about a question about Random Walks. I came across various papers where the probability of 2 random walkers in 1 dimension and 2 dimension starting at the same point and returning to the origin was found. I was doing a research on a question similar to this - What is the probability that 2 random walkers, originating from the same point, meet at a point other than the origin?

I tried solving the cases for 1 dimension and 2 dimension but I was stuck because the displacement does not become 0 in this case. I couldn't handle the displacement term. I would be glad if someone could give me some hint or tell me how I should proceed further.

$\endgroup$
4
  • $\begingroup$ Random walks in how many dimensions? $\endgroup$ Apr 13, 2015 at 5:25
  • $\begingroup$ Random walks in 1d and 2d $\endgroup$ Apr 14, 2015 at 4:58
  • $\begingroup$ It's still unclear to me what the question is. Did you figure out 1D and need a pointer for 2D? Do you need both? If both, maybe just ask about one first, then once you know a little more about asking good questions, ask about the other problem. $\endgroup$
    – David K
    Apr 14, 2015 at 6:56
  • $\begingroup$ I got 1D. I need a hint for 2D. $\endgroup$ Apr 15, 2015 at 15:13

1 Answer 1

3
$\begingroup$

Assuming $1D$ random walk:

For the two random walkers($W_1, W_2$) to meet at some time point $N$, the number of left steps taken by $W_1$ should equal the number of steps taken by $W_2$

The number of sequences of lefts and rights possible for each walker is $2^N$.

Now, in order for $W_1$ and $W_2$ to meet, they must have taken $0\ or\ 1\ or\ 2\ or\ 3\ or\ \ldots \ N $ left steps, which can be done in: $$ \sum_{i=0}^{N} \frac{\binom{N}{i}\binom{N}{i}}{2^N2^N} = \frac{\binom{2N}{N}}{4^N} $$

$\endgroup$
6
  • $\begingroup$ btw, W_1 is outside of the math enviroment $\endgroup$ Apr 13, 2015 at 6:05
  • 1
    $\begingroup$ The final formula is direct if one notices that one asks for the steps of the first walker minus the steps of the second walker to lead to the initial point, or equivalently, that one single walker is again at its starting point after 2N steps. $\endgroup$
    – Did
    Apr 13, 2015 at 6:34
  • $\begingroup$ "Meet at some time point N", what do you mean by time point? $\endgroup$ Apr 14, 2015 at 4:59
  • $\begingroup$ So this is the probability that 2 random walkers, both originating from the same point, meet at a point other than the origin? $\endgroup$ Apr 14, 2015 at 5:57
  • $\begingroup$ Yes. They need to be 'at the same point' when meeting. This should answer your previous question too. $\endgroup$ Apr 14, 2015 at 20:39

You must log in to answer this question.

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