15
$\begingroup$

Or: Stabbing rolling disks.

Imagine there are $n$ unit-diameter disks rolling between $x=0$ and $x=d$, reflecting off either end. The disk centers start at a random location within $[\frac{1}{2}, d-\frac{1}{2}]$, with uniformly random velocities in $[-1,1]$ per unit time. The goal is to wait until all $n$ disks overlap, at which point you can stab or "spear" them (to arrest their rolling). Here is an example, with $n{=}3$ disks and $d=10$:
      HulaHoops3
In this particular case, triple overlap occurs around $57$ time units—when I have frozen the animation for a bit (after which it resumes [browser dependent]).

Clearly this has nothing to do with circles—one could instead imagine moving intervals of length $1$. I retain the fanciful disks/circles model because my true focus is on the maximum vertical extent of the $n$-fold intersection. But that is for a later investigation, or a future MO question...

My immediate question is:

Q1. For a given $n$ number of randomly placed disks, with randomly assigned rolling velocities, and an interval of length $d$ in which the disks rebound, what is the expected waiting time until all $n$ disks overlap and so the "hula hoops" can be "speared"?

Perhaps $n{=}2$ can be worked out by case analysis [as I mentioned in a comment, simulations suggest that, for $d{=}10$, the expected waiting time is about $7.7$], but for arbitrary $n$, a more general approach seems necessary (and maybe difficult?).

(Added—A more focused and accessible question, suggested by one of Douglas Zare's comments:)

Q2. Is there an easy proof that the expected waiting time is finite, for any $n \ge 2$ and $d>2$?

$\endgroup$
7
  • 2
    $\begingroup$ My sister had this saying involving a rolling donut. Or doughnut. $\endgroup$
    – Will Jagy
    Mar 15, 2014 at 1:39
  • 3
    $\begingroup$ Do you expect much of a difference between reflections in an interval versus moving around a circle? $\endgroup$ Mar 15, 2014 at 12:44
  • 2
    $\begingroup$ I think for $n=2$, there is a qualitative difference in that the expected time is infinite for a circle, but finite for an interval. $\endgroup$ Mar 15, 2014 at 12:53
  • 7
    $\begingroup$ This question (at least its analogue where the discs (intevals) move around a circle) is in some sense the opposite of the lonely runner conjecture (en.wikipedia.org/wiki/Lonely_runner_conjecture). $\endgroup$ Mar 15, 2014 at 14:30
  • 1
    $\begingroup$ On the circle the expected time is infinite for $n=2$ (the probability that you have to wait for time $T$ is at least the probability that the initial distance is at least 2 and the speed difference is at most $1/T$, which is about $c/T$, so it shouldn't be hard to prove that for large $n$ (most likely, even for $n\ge 3$) the expectation does not exist. However the question about the distribution is well-posed and, probably, tractable if you want just the order of magnitude rather than an exact number. $\endgroup$
    – fedja
    Mar 26, 2014 at 0:51

2 Answers 2

7
$\begingroup$

The waiting time is almost surely finite. More explicitly, if the speeds of the hoops are linearly independent over $\mathbb{Q}$ then the waiting time is finite for all initial positions, and furthermore the average proportion of the the time which is spent in a spearable position equals the probability that the hoops could be speared at time 0.

Fix $n \geq 2$ and $d>2$. For each $i=1,\ldots,n$ I will say that the state of the $i^{th}$ hoop at time $t$, denoted $x_i(t)$, is the value in $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ given by $(2d-2)^{-1}(y-\frac{1}{2})$ if at time $t$ the centre of the hoop is at $y \in [\frac{1}{2},d-\frac{1}{2}]$ and the hoop is moving to the right, and by $1-(2d-2)^{-1}(y-\frac{1}{2})$ if at time $t$ the centre of the hoop is at $y \in [\frac{1}{2},d-\frac{1}{2}]$ and the hoop is moving to the left. If for each $i$ the $i^{th}$ hoop begins at state $\beta_i \in \mathbb{T}$ and moves with speed $(2d-2)\alpha_i$, then the vector of states of the hoops at time $t$ is given by $(x_1(t),x_2(t),\ldots,x_n(t))=(\beta_1+t\alpha_1,\beta_2+t\alpha_2,\ldots,\beta_n+t\alpha_n)$. Define $f \colon \mathbb{R}/\mathbb{Z} \to \mathbb{R}$ by $$f(x):=\left\{\begin{array}{cl}\frac{1}{2}+(2d-2)x&\text{if }0 \leq x \leq \frac{1}{2}\\ \frac{1}{2}+(2d-2)(1-x)&\text{if }\frac{1}{2}\leq x<1, \end{array}\right.$$ then the hoops can be speared at time $t$ if and only if the vector $(x_1(t),\ldots,x_n(t))$ belongs to the open set $$A:=\left\{(z_1,\ldots,z_n) \in \mathbb{T}^n\colon |f(z_i)-f(z_j)|<\frac{1}{2}\text{ for all }1 \leq i \leq j \leq n\right\}$$ which is of course nonempty since it contains the diagonal of $\mathbb{T}^n$. If $\alpha_1,\ldots,\alpha_n$ are linearly independent over $\mathbb{Q}$ then it is well-known that the flow $(\phi_t)_{t \in \mathbb{R}}$ given by the maps $\phi_t \colon \mathbb{T}^n \to \mathbb{T}^n$ defined by $\phi_t(y_1,\ldots,y_n):=(y_1+t\alpha_1,\ldots,y_n+t\alpha_n)$ is minimal and uniquely ergodic, with Lebesgue measure being its sole invariant Borel probability measure. In particular, by the ergodic theorem for uniquely ergodic flows, the average proportion of time spent in $A$ along each trajectory of the flow is precisely the Lebesgue measure of $A$. Since the initial states $\beta_i$ are chosen independently according to Lebesgue measure, the probability that the hoops can be speared at time 0 is also equal to the Lebesgue measure of $A$. Finally I note that the probability that the speeds $\alpha_i$ are linearly independent over $\mathbb{Q}$ is $1$ and so it is almost certain that the flow is ergodic and the waiting time is finite.

This analysis also shows that if the speeds are linearly independent over the rationals then the limit superior of the height of the region defined by the intersection of the hoops is $2$, since the flow, being minimal, will take any starting configuration into any specified open neighbourhood of the diagonal infinitely often. The long-term average of the height of their intersection could also be calculated using an ergodic theorem.

The matter of the expectation of the waiting time is more delicate. Knowing the Lebesgue measure of $A$ and that the flow is ergodic unfortunately does not automatically give clear information as to the expected time of first entry to $A$. For example, if we partition a one-dimensional torus into $n$ equidistant intervals each of length $1/2n$ then the expected time of first entry to the union of the intervals tends to zero as $n \to \infty$, but the Lebesgue measure of the union of these intervals is $\frac{1}{2}$ for every $n$. Worse, knowing the Lebesgue measure of $A$ does not permit us an upper bound on the expected time of first entry to $A$: if we consider the flow on $\mathbb{T}^2$ and imagine (for the sake of argument) that $A$ is a small disc, then the expected time of first entry to $A$ tends to infinity as the direction of flow tends towards being parallel to one of the co-ordinate axes whilst the speed of the flow remains constant. So in order to estimate the expected entry time to $A$ it would seem to be necessary to understand something about the geometry of the set $A$ defined above.

When the number of discs is at least three it is clear that we may have to wait an arbitrarily long time for the first entry to $A$, but the set of configurations which lead to long waiting times may yet be ``small enough'' that we can obtain a finite expected waiting time (but I am not sure). By an easy multiple integration argument it would be enough to show that the expected waiting time is finite if we assume additionally that the fastest hoop is moving at speed 1. Perhaps drawing some sketches of the region $A$ in low dimensions will lead to further insight.

$\endgroup$
1
  • 1
    $\begingroup$ "it is almost certain that the flow is ergodic and the waiting time is finite"---Very nice! $\endgroup$ Mar 17, 2014 at 1:02
9
$\begingroup$

As a start, consider the probability that the randomly distributed circles all overlap to begin with. Assume $d\ge2$ since otherwise the probability is 1.

There are $n$ choices for the leftmost circle, $n-1$ choices for the rightmost circle, and then all the others have to be between them, which gives $$n(n-1)\int_{1/2}^{d-1/2}\int_x^{\min(x+1,d-1/2)} \frac{(y-x)^{n-2}}{(d-1)^n}dy\thinspace dx \ = \ \frac{n(d-2)+1}{(d-1)^n}$$ as the probability that the waiting time is 0.

$\endgroup$
2
  • $\begingroup$ Nice! So for $n=2$, $d=10$, that probability is $\frac{17}{81} \approx 0.21$. $\endgroup$ Mar 16, 2014 at 0:29
  • 3
    $\begingroup$ Simulation, $10^6$ trials: probability $= 0.209$. :-) $\endgroup$ Mar 16, 2014 at 0:51

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.