2 person Symmetric Random Walk on a line separated by some distance.

Question

So I practiced some questions for the quant interview on QuantGuide. There I came across this question:
Dominated Turtle:
Two turtles, Tort and Bort, will perform independent simple symmetric random walks on the integers starting at positions 0 and 4 respectively. Compute the probability after 10 steps, Tort and Bort are back at their initial positions and that Tort was strictly behind Bort at all 10 steps.
My Approach: If there was no condition on their positions it would simply have been $\frac{\binom{10}{5}^{2}}{2^{20}}$. But I can't figure out a way to incorporate the constraint on the position. It would be of great help if you could resolve this.

Answer 1

Apply the reflection principle to the distance between the turtles.

The general idea of the reflection principle is to flip the steps after some "bad value" is reached. When applied to the normal random walk, we would flip "up" and "down" after reaching some value $l$. If we know that it then goes back to some value $k$, we know that after flipping it goes to $l-(k-l)$. We establish a bijection "walk to $k$ touching $l$" <=> "walk to $l-(k-l)$", so \begin{align} \#(\text{walk to $k$ not touching $l$}) &= \#(\text{walk to $k$}) - \#(\text{walk to $k$ touching $l$})\\ &=\#(\text{walk to $k$}) - \#(\text{walk to $l-(k-l)$}). \end{align}

In our example the "bad value" is that the turtles meet, or in other words, that their distance drops to 0. The "reflection" we do now is to swap the turtles: After the turtles meet the first time, Bert starts moving as Tort and vice versa. When the distance went down, after swapping it now goes up and vice versa.

Because we know that Tort goes back to 0, and Bert to 4, after swapping it's now Tort who goes to 4 and Bert to 0. Conversely, every walk of Tort to 4 and Bert to 0 has them meeting, and flipping them after meeting gets us back to a walk of Tort to 0, Bert to 4 with them meeting. For Tort to go to 0, it has to go down 7 times and up 3 times. For Bert to go to 4, it has to go up 7 times and down 3 times. So the amount of walks for either Bert or Tort is $\binom{10}{7}$, and $\binom{10}{7}^2$ is the amount of walks {Tort to 0, Bert to 4} and is also the amount of walks {Tort to 4, Bert to 0 and they meet}. The amount of walks {Tort to 4, Bert to 0 and they don't meet} is then given by $$ \binom{10}5^2 - \binom{10}{7}^2 $$ and the probability is thus $$ 2^{-20} \left( \binom{10}5^2 - \binom{10}{7}^2 \right) \approx 6,05\%-1,37\%=4,68\%. $$