Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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:
           Two Particles
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$.

share|improve this question
7  
run green particle run... aaargh! :( –  Pietro Majer Dec 2 '12 at 14:01
add comment

2 Answers

up vote 12 down vote accepted

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

share|improve this answer
1  
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
1  
And fun to inadvertently learn that $\pi \approx 2(1 + 1/\sqrt{3})$. :-) –  Joseph O'Rourke Dec 3 '12 at 12:53
add comment

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

share|improve this answer
    
Very clean and clear---Thanks, Alexandre! –  Joseph O'Rourke Dec 2 '12 at 14:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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