# Particles chasing one another around a circle

Two particles start out at random positions on a unit-circumference circle. Each has a random speed (distance per unit time) moving counterclockwise uniformly distributed within $[0,1]$. How long until they occupy the same position? In the example below, the red particle catches the green particle at $t=5.9$, i.e., nearly six times around the circle:

The distribution of overtake-times is quite skewed, indicating perhaps the mean could be $\infty$. For example, in one simulation run, it took more than $3$ million times around the circle before one particle finally caught the other. So I don't trust the means I am seeing (about $25$).

What is the distribution of overtake-times?

I was initially studying $n$ particles on a circle, but $n=2$ seems already somewhat interesting...

Update (2Dec12). Alexandre Eremenko concisely established that the expected overtake-time (the mean) is indeed $\infty$. But I wonder what is the median, or the mode? Simulations suggest the median is about $1.58$ and the mode of rounded overtake-times is $1$, reflecting a distribution highly skewed toward rapid overtake. (The median is suspiciously close to $\pi/2$ ...)

Update (3Dec12). Fully answered now with Vaughn Climenhaga's derivation of the distribution, which shows that the median is $1 + \frac 1{\sqrt{3}} \approx 1.577$.

-
run green particle run... aaargh! :( –  Pietro Majer Dec 2 '12 at 14:01

To answer your questions about median and mode, one can take Alexandre's answer a little further and compute the exact distribution function for the overtake-times.

Note that the overtake-time doesn't depend on $v_1,v_2$ directly, but only on their difference. Call the difference $v$. Now $v$ is the difference of two uniformly distributed random variables on $[0,1]$, so it is supported on $[-1,1]$ with probability density function $1-|v|$. Moreover, since $\theta$ is uniformly distributed we can without loss of generality identify the cases $(v,\theta)$ and $(-v,1-\theta)$ and reduce everything to the following set-up:

• $v$ is distributed on $[0,1]$ with density function $2(1-v)$.
• $\theta$ is uniformly distributed on $[0,1]$.
• The overtake-time is $t=\theta/v$.

Now we can compute the cumulative density function for the overtake-time. Indeed, we have $P(t<T) = P(\theta/v<T) = P(\theta < Tv)$, which we can get by the following integral: $$P(t<T) = \int_0^1 2(1-v) P(\theta < Tv | v) \,dv.$$ The probability $P(\theta < Tv | v)$ is given by the function $f(\theta,v) = \max(Tv,1)$. Thus for $T\leq 1$, we have $f(\theta,v)=Tv$ for all $v\in[0,1]$, so integrating gives $P(t<T) = T/3$, while for $T\geq 1$, we integrate and find $$P(t<T) = \int_0^{1/T} 2(1-v)Tv\,dv + \int_{1/T}^1 2(1-v)\,dv = 1-\frac 1T + \frac 1{3T^2}.$$ So in the end the cumulative density function for the overtake-time is $$P(t<T) = \begin{cases} \frac T3 & T\leq 1, \\ 1 - \frac 1T + \frac 1{3T^2} & T \geq 1. \end{cases}$$ The term $1/T$ in the last expression will give you the infinite mean, since upon differentiating the CDF you'll get a term $1/T^2$, which upon multiplying by $T$ and integrating to get the mean you end up integrating $1/T$ from $1$ to $\infty$.

As for the median, it looks as though any proximity to $\pi/2$ is just a red herring, because solving for $P(t<T) = 1/2$ yields $T=1 + \frac 1{\sqrt{3}} \approx 1.57735\dots$.

-
Beautiful analysis! And so satisfying to see the exact median you computed matches the simulations. Thanks! –  Joseph O'Rourke Dec 3 '12 at 11:42
And fun to inadvertently learn that $\pi \approx 2(1 + 1/\sqrt{3})$. :-) –  Joseph O'Rourke Dec 3 '12 at 12:53

Let the circle has length $1$ unit. Let $\theta$ be the angle (anticlockwise) from the first particle to the second at the initial position. Let $v_1,v_2$ be the speeds of the particles. I suppose they move anti-clockwise, as in your movie. If $v_1>v_2$, they collide in time $T(v_1,v_2,\theta)=\theta/(v_1-v_2).$ If $v_2>v_1$, they collide in time $T(v_1,v_2,\theta)=(1-\theta)/(v_2-v_1)$. The expectation of the time is $$\int_Q T(v_1,v_2,\theta)dv_1dv_2d\theta,$$ where $Q=[0,1]^3$. The integral is easy to evaluate by breaking $Q$ into two pieces. But it is indeed $+\infty$, as you guessed:-)

-
Very clean and clear---Thanks, Alexandre! –  Joseph O'Rourke Dec 2 '12 at 14:06