Probability of two people passing through same point on random walk

Question

Background

I've come across this problem and I just can't figure it out. I know it revolves around the ideas of markov chains and/or one dimensional random walks.

I've been able to find solutions for some cases of intersections/collisions on one dimensional random walks but they're usually based on both parties starting at the same point e.g. http://mtdevans.com/projects/physics-problems/random-walk-of-two-drunks/

I haven't been able to expand upon these ideas to cover the following problem. Any insight is greatly appreciated, I'm a bit stumped.

The Problem

Two people are walking randomly on a line.

They start 10 metres from each other. At each time interval, each person has a probability of 1/2 to move 1 metre to the left, and probability 1/2 to move 1 metre to the right.

What's the probability that after 7 time intervals, the people have passed through the same point?

Thanks for any help in advance.

Answer 1

Let we follow how distance $d_n$ between this persons changes. Initially it is equal to $d_0=10$. After one time interval both persons can step right or left and distance stay the same. Or they can step in different directions and move away from each other. Or they can step into each other and the distance between them will decrease. $$ \mathbb P(d_{n+1}=k-2|d_n=k)=\frac14,\quad \mathbb P(d_{n+1}=k+2|d_n=k)=\frac14, \quad \mathbb P(d_{n+1}=k|d_n=k)=\frac12. $$ To get $d_7 = 0$ exactly after $7$ time intervals, you need either to have the event $d_n \mapsto d_n-2$ five times and twice $d_n$ remain unchanged, or once $d_n$ is increased and $6$ times decreased. Therefore $$ \mathbb P(d_7=0\,|\,d_0=10)=\binom{7}{2}\left(\frac14\right)^5\left(\frac12\right)^2+\binom{7}{1}\left(\frac14\right)^6\frac14 = \dfrac{91}{4^7}=\dfrac{91}{16384}. $$

If meetings before $n=7$ should be also taken into account, one calculate probability $\mathbb P(d_5=0 \vee d_6=0 \vee d_7=0)$ directly. Mark step "down" $d_n \mapsto d_n-2$ by $d$, step "right" $d_n \mapsto d_n$ by $r$ and step "up" $d_n \mapsto d_n+2$ by $u$.

$$\mathbb P(d_5=0 \vee d_6=0 \vee d_7=0)=\mathbb P(d_5=0)+\mathbb P(d_5\neq 0, d_6=0)+\mathbb P(d_5\neq 0, d_6\neq 0, d_7=0).$$ $$\mathbb P(d_5=0)=\mathbb P(ddddd)=\dfrac{1}{4^5},$$ $$\mathbb P(d_5\neq 0, d_6=0) = \mathbb P(\underbrace{rddddd \vee\ldots\vee ddddrd}_{5}) =5\dfrac{1}{2}\dfrac{1}{4^5}$$. Note that the last step cannot be $r$ here. Next, $$\mathbb P(d_5\neq 0, d_6\neq 0, d_7=0) = \mathbb P(\underbrace{udddddd\vee\ldots\vee ddddudd}_{5} \vee \underbrace{rrddddd\vee\ldots\vee ddddrrd}_{\binom62})= $$ $$=5\dfrac{1}{4^7}+\binom62 \dfrac{1}{2^2}\dfrac{1}{4^5}.$$ Here $\binom62$ variants appears since last step should be $d$ and two letters $r$ can be at any other six places.

Total probability is $$\mathbb P(d_5=0 \vee d_6=0 \vee d_7=0)=\dfrac{1}{4^5}+5\dfrac{1}{2}\dfrac{1}{4^5}+5\dfrac{1}{4^7}+\binom62 \dfrac{1}{2^2}\dfrac{1}{4^5}=\dfrac{121}{4^7}.$$

Answer 2

Let $D(t)$ be the distance between them at time $t$. Define $X(t)=D(t+1)-D(t)$. $X$ has the following distribution: $$\mathbb P (X=2)= \frac 14$$ $$\mathbb P (X=0)= \frac 12$$ $$\mathbb P (X=-2)= \frac 14$$ And notice that $$\sum_{k=0}^{n-1} X(k)=D(n)-D(0)=D(n)-10$$ The event that they meet after $n$ steps is equivalent to the event that the above sum equals $-10$. This means they cannot possibly meet if $n\le 4$. For $n=5$, all $X(k)$'s must equal $-2$, since they are independent, this means that the probability they meet at $n=5$ is $\frac {1}{4^5}$. For them to meet at $n=6$, one $X(k)$ must equal $0$, we therefore get $6\frac 12\frac {1}{4^5}$ as the respective probability. For $n=7$ we have two options, either two $X(k)$'s equal $0$, or six of them equal $-2$ and another equals $2$. These two are mutually exclusive, so the probability overall is $\binom{7}{2}\frac {1}{2^2}\frac {1}{4^5} +7\frac {1}{4^7}$. Now the application of the inclusion exclusion principle is a simple matter. If they meet at $n=k$, they can only meet again at $n=k+1$ if they move in the same direction, i.e $X=0$. If they meet at $n=5$ they can only meet at $n=7$ if they move in the same direction twice, or if they walk away and walk back. For them to meet at $n=5$, $n=6$ and $n=7$, they must move in the same direction twice. Then we have $$\begin{align} P &=\frac {1}{4^5}+6\frac 12\frac {1}{4^5}+\binom{7}{2}\frac {1}{2^2}\frac {1}{4^5} +7\frac {1}{4^7} \\ &-\frac {1}{4^5}\frac {1}{2}-6\frac {1}{2^2}\frac {1}{4^5}-\frac {1}{4^5}\left(\frac {1}{2^2}+\frac {2}{4^2} \right)\\ & + \frac {1}{4^5}\frac {1}{2^2}\end{align}$$