1
$\begingroup$

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 :)

$\endgroup$
3
  • $\begingroup$ I get $\frac{53}{8192} \doteq \frac{1}{154.57}$, which is the sum of the constant and lower-order terms in $z^{10} \left(\frac14 z^{-2}+\frac12+\frac14 z^2\right)^7$. See the Wikipedia article on generating functions. $\endgroup$
    – Brian Tung
    Commented Mar 17, 2017 at 23:56
  • $\begingroup$ You could take the difference between the two (and then divide by two) and thus reduce it to a single random walk with $0.25$ probability at each time step to walk left, same for right, and $0.5$ to stay still. Then ask about the probability of reaching the position five to the right of where you started​ within seven time steps. $\endgroup$
    – Arthur
    Commented Mar 18, 2017 at 0:18
  • $\begingroup$ Basically a duplicate of math.stackexchange.com/q/2135578/265466 and, more recently, math.stackexchange.com/q/2191128/265466. $\endgroup$
    – amd
    Commented Mar 18, 2017 at 0:58

2 Answers 2

Reset to default
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

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