Randomly draw $n$ intervals from $[0,1]$, where each end point are selected from from the uniform distribution between $[0,1]$.

What's the probability that at least one interval overlaps with all others?

  • $\begingroup$ Should "one" be replaced with "at least one" or "exactly one" or "a particular"? $\;$ $\endgroup$ – user57159 Apr 20 '15 at 1:10
  • $\begingroup$ @RickyDemer thanks, it should be at least one. $\endgroup$ – Vendetta Apr 20 '15 at 1:18
  • $\begingroup$ A solution is given at the end of this document: math.ucdavis.edu/~gravner/MAT135A/resources/chpr.pdf $\endgroup$ – Sameer Kailasa Apr 20 '15 at 5:58

Let $x_1<\dots<x_{2n}$ be the $2n$ points sampled, after sorting them in increasing order (all points are different with probability 1). When are the corresponding intervals all disjoint? Only when $x_1,x_2$ belong to one interval, $x_3,x_4$ to another, and so on. Since all permutations are equally likely, the probability that no two intervals overlap is $$ \frac{2^n n!}{(2n!)}. $$ For small $n$ starting with $1$, these probabilities are $$ 1, \frac{1}{3}, \frac{1}{15}, \frac{1}{105}, \frac{1}{945}, \ldots. $$ The reciprocal sequence has many combinatorial interpretations, see A001147 on the OEIS.

The probability you are after can be calculated along the same lines. Surprisingly, it turns out to be always $2/3$.

  • 1
    $\begingroup$ The complement of the event "no two intervals overlap" is "some two intervals overlap," not "some interval overlaps all others." $\endgroup$ – Sameer Kailasa Apr 20 '15 at 5:56
  • $\begingroup$ @Sameer Yes, I just realized that. But the same method would work. $\endgroup$ – Yuval Filmus Apr 20 '15 at 5:57
  • $\begingroup$ Trying numbers, I immediately get that $\: n=0 \:$ and $\: n=1 \:$ are counterexamples to your claim that the probability the OP is asking about "turns out to be always 2/3." $\;\;\;\;$ $\endgroup$ – user57159 Apr 20 '15 at 11:33
  • $\begingroup$ @RickyDemer Fortunately, these numbers are the only counterexamples. $\endgroup$ – Yuval Filmus Apr 20 '15 at 14:07

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.