Particles chasing one another around a circle - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T12:39:26Z http://mathoverflow.net/feeds/question/115138 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115138/particles-chasing-one-another-around-a-circle Particles chasing one another around a circle Joseph O'Rourke 2012-12-02T02:32:35Z 2012-12-03T16:26:52Z <p>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: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/CircleParticles2.gif" alt="Two Particles" /> <br /> 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$).</p> <blockquote> <p>What is the distribution of overtake-times?</p> </blockquote> <p>I was initially studying $n$ particles on a circle, but $n=2$ seems already somewhat interesting...</p> <p><b>Update</b> (<em>2Dec12</em>). 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$ ...)</p> <p><b>Update</b> (<em>3Dec12</em>). 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$.</p> http://mathoverflow.net/questions/115138/particles-chasing-one-another-around-a-circle/115140#115140 Answer by Alexandre Eremenko for Particles chasing one another around a circle Alexandre Eremenko 2012-12-02T02:52:02Z 2012-12-02T02:52:02Z <p>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:-)</p> http://mathoverflow.net/questions/115138/particles-chasing-one-another-around-a-circle/115256#115256 Answer by Vaughn Climenhaga for Particles chasing one another around a circle Vaughn Climenhaga 2012-12-03T07:01:07Z 2012-12-03T16:07:39Z <p>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.</p> <p>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:</p> <ul> <li>$v$ is distributed on $[0,1]$ with density function $2(1-v)$.</li> <li>$\theta$ is uniformly distributed on $[0,1]$.</li> <li>The overtake-time is $t=\theta/v$.</li> </ul> <p>Now we can compute the cumulative density function for the overtake-time. Indeed, we have <code>$P(t&lt;T) = P(\theta/v&lt;T) = P(\theta &lt; Tv)$</code>, which we can get by the following integral: <code>$$P(t&lt;T) = \int_0^1 2(1-v) P(\theta &lt; Tv | v) \,dv.$$</code> The probability <code>$P(\theta &lt; Tv | v)$</code> 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 <code>$P(t&lt;T) = T/3$</code>, while for $T\geq 1$, we integrate and find <code>$$P(t&lt;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}.$$</code> So in the end the cumulative density function for the overtake-time is <code>$$P(t&lt;T) = \begin{cases} \frac T3 &amp; T\leq 1, \\ 1 - \frac 1T + \frac 1{3T^2} &amp; T \geq 1. \end{cases}$$</code> 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$.</p> <p>As for the median, it looks as though any proximity to $\pi/2$ is just a red herring, because solving for <code>$P(t&lt;T) = 1/2$</code> yields $T=1 + \frac 1{\sqrt{3}} \approx 1.57735\dots$.</p>