2 1D random walkers separated by a distance d will meet at or before time t.

Question

I'm looking for a solution to a puzzle I found. I'm looking for the formula for the probability of 2 1D random walkers starting separated by a distance d meeting at or before time t

Example

2 walkers a and b. a starts at 0 b starts at 10. At each time step each walker independently walks either left of right with equal probability. What is the probabliltiy that they will meet(pass through the same point) at or before t = 7. 7 time steps.

I have simulated it using a simple program I wrote and get 1/135. How could I do this without simulation?

Thank you for your help :)

Answer 1

Hint: call the probability $P(d,t)$. Condition on the first time step (there are four possibilities) to derive the recurrence $$ P(d,t)=\frac{2P(d,t-1)+P(d-2,t-1)+P(d+2,t-1)}{4}, $$

where the first term in the numerator corresponds to both people's first steps being in the same direction; the second, to them stepping toward each other; and the last, to them stepping away from each other.

Answer 2

This has been asked before.

$\;\;\;\;\;\;$What is the chance two bugs will meet within X timesteps given specific movement patterns?

If by "pass through the same point", you mean pass through the same point at the same integer time (i.e., actually meet at an integer time), then see Ross Millikan's answer which yields a probability of $121/16384$, or approximately $1/135$, agreeing with the results of your simulation.

On the other hand, if by "pass through the same point", you mean pass through the same point, but not necessarily at the same time (i.e., the paths intersect), then see my program-based answer which yields a probability of $151/16384$, or approximately $1/108$.