2 people within a distance of each other in a random walk (CHMMC individual #2, 2016)

141 Views Asked by At

Alice and Bob find themselves on a coordinate plane at time t = 0 at points A(1, 0), and B(−1, 0). They have no sense of direction, but they want to find each other. They each pick a direction with uniform random probability. Both Alice and Bob travel at speed 1 unit / min in their chosen directions. They continue on their straight line paths forever, each hoping to catch sight of the other. They each have a 1-unit radius field of view: they can see something iff its distance to them is at most 1. What is the probability that they will ever see each other?

So basically we have two lines with random slope through A and B. So the equations of the lines can be $A_x(t)=t, A_y(t) = m_1(t-1)$ and $B_x(t)=t, B_y(t) = m_2(t+1).$ And because we have to account for direction, we have to divide by 4 at the end. How to proceed from here?

Edit 1: As the movement speed of the people have to be constant, the parameterization should be $A_x(t)=t m_2/m_1, A_y(t) = m_1(m_2t/m_1-1)=m_2t-m_1$ and $B_x(t)=t, B_y(t) = m_2(t+1).$

Edit 2: I was thinking, instead of parametizing through a line, it would make more sense to parameterize through an angle. Then $A_x(t) = -1 + t\sin \theta_1, A_y(t) = t\cos\theta_1$, $B_x(t) = 1 + t\sin \theta_2, B_y(t) = t\cos\theta_2$.

1

There are 1 best solutions below

2
On

With probability ${1\over2}$ they both walk into the same (lower or upper) half plane. Conditioning on this we may assume their orbits to be $$a(t)=(1-t\cos\alpha,t\sin\alpha),\qquad b(t)=(-1+t\cos\beta,t\sin\beta)$$ with angles $\alpha$, $\beta$ independently and uniformly distributed in $[0,\pi]$. If $\alpha+\beta>\pi$ then they walk apart right from the start. We therefore condition on $\alpha+\beta\leq\pi$, which introduces another factor ${1\over2}$ in the overall probability of seeing each other.

We now compute $$f(t):=\bigl|a(t)-b(t)\bigr|^2=4-4t(\cos\alpha+\cos\beta)+2t^2(1+\cos(\alpha+\beta)\ .$$ The minimum of this function is assumed at time $$t_*={\cos\alpha+\cos\beta\over1+\cos(\alpha+\beta)}\ ,$$ which is indeed positive when $\alpha+\beta<\pi$. This means that the distance between the two is initially decreasing, assumes the minimal value $$m:=\sqrt{f(t_*)}=2\left|\sin{\alpha-\beta\over2}\right|$$ (Mathematica computed this for me), and then will increase forever. The condition $m\leq1$ amounts to $$|\alpha-\beta|\leq{\pi\over3}\ .\tag{1}$$ We now draw the triangle $\{(\alpha,\beta)\>|\>\alpha\geq0,\ \beta\geq0,\ \alpha+\beta\leq\pi\}$ and compute the fraction $\rho$ of its area defined by $(1)$. One obtains $$\rho={\pi^2/2-2\pi^2/9\over\pi^2/2}={5\over9}\ .$$ The probability $p$ we are looking for is therefore given by $$p={1\over2}\cdot{1\over2}\cdot{5\over9}={5\over36}\ .$$