1
$\begingroup$

Suppose I have a circle with circumference $A$. Along the circumference of this circle, I randomly drop $N$ arcs with fixed length $a < A$. Now suppose I drop a single additional arc ($N+1$). What is the probability $P(N, a/A)$ that this arc does not overlap with any previously dropped arcs?

My intuition is that this has something to do with the Stirling numbers, because given something like $3$ arcs, the overlap scheme could be no overlapping, three possible ways of three overlapping, or all overlapping. However, I cannot figure out how to approach the problem of finding the probability of overlap. I found some relevant notes on meeting probabilities here and here, but I can't quite see how to apply this to my problem

$\endgroup$
  • 1
    $\begingroup$ What do you mean, "randomly?" $\endgroup$ – Ben W Dec 3 '18 at 23:36
  • $\begingroup$ The midpoint of the dropped interval is selected randomly on $[0, 2 \pi]$, independently of where previous intervals have been dropped $\endgroup$ – wil3 Dec 3 '18 at 23:38
  • 1
    $\begingroup$ I think this may not have a closed-form answer. It is clear that we need only consider cases where $a\leq A/2$. Let us, as a special case, consider that $a\geq A/3$ and that the radius is 1. Then the probability is given by $\frac{N!}{(2\pi)^N}\int_{\theta_1}^{2\pi-a}\int_{\theta_2}^{2\pi-a}\cdots\int_{\theta_{N-1}}^{2\pi-a}\int_{\theta_N+\Theta}^{2\pi-a}d\theta_{N+1}\;d\theta_N\cdots d\theta_3\;d\theta_2$, where $\theta_1=0$. Of course, the computation here depends heavily on the fact that $a\geq A/3$. If $a<A/3$ then the computation will be dramatically different. $\endgroup$ – Ben W Dec 4 '18 at 0:21
  • $\begingroup$ @BenW I looked at the paper linked in the answer below (which uses counting arguments rather than defining a pdf) and it looks like it works---would you agree? I can't quite tell yet if there is a subtle issue with the paper (perhaps with the boundary conditions) $\endgroup$ – wil3 Dec 4 '18 at 1:01
  • 1
    $\begingroup$ you may be right. Frankly, I've had a few drinks and will have to wait till tomorrow to respond intelligently to your question. You may be right. But my intuition tells me this is far more complicated than we might wish. $\endgroup$ – Ben W Dec 4 '18 at 1:17
1
$\begingroup$

This can be quite delicate but lots are known, going back to a classic paper by Flatto and Konheim available here.

Let $n-1$ uniform points be independently selected on the circle, and denote the the $n$ interval lengths they (with probability one, being distinct) split the circle into by $X_1,\ldots,X_n.$

For example, the following quantities are calculated in this paper and they can directly answer your question and similar questions.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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