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.
Best Answer
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}.$$