19
$\begingroup$

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

$\endgroup$
1
  • 10
    $\begingroup$ run green particle run... aaargh! :( $\endgroup$ Dec 2, 2012 at 14:01

2 Answers 2

18
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Beautiful analysis! And so satisfying to see the exact median you computed matches the simulations. Thanks! $\endgroup$ Dec 3, 2012 at 11:42
  • 2
    $\begingroup$ And fun to inadvertently learn that $\pi \approx 2(1 + 1/\sqrt{3})$. :-) $\endgroup$ Dec 3, 2012 at 12:53
24
$\begingroup$

Let the circle have 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:-)

$\endgroup$
1
  • $\begingroup$ Very clean and clear---Thanks, Alexandre! $\endgroup$ Dec 2, 2012 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.