Disjoint Intervals

[Laramie]

The endpoints of n intervals are randomly chosen in the interval [0,1]. Let P(n) be the probability that each interval is disjoint from at least one of the other intervals. What is P(n)?

[Zag]

Suppose we choose 4 points randomly and label them A, B, C, D, in order of least to most, there are 3 ways in which they can connect into segments: A-B & CD ---- AC & BD ---- AD & BC, with equal probability. Only one of those has no overlap, so P(2) = 1/3.

For the next step, I'm not sure. I know I could calculate the chance that U(n), where U(n) is the chances that there are no overlaps at all. But I don't know how to calculate P(n).

[L'lanmal]

Edit: I just reread and realized I missed the word "each" in the original statement. That puts me in a similar boat as Zag: I found the probability that there exists a pair of disjoint intervals.

Previous text:
I was going to raise the standard objection to "random" not being defined, but most definitions will lead to the same answer in this case.

Claim: Take the 2n end points of the n intervals and color each point with a color representing the interval. This gives n colors, with two points each. Then some pair of intervals is non-overlapping if, and only if, of the first n points (in numeric order), two points are the same color.

There are [(2n)!] / [(2^n)] ways to make this coloring. There are n! ways of coloring the left half n colors, and n! ways of coloring the right half n colors. Therefore, if the claim holds, P(n) = [(n!)*(n!)*(2^n)] / [(2n)!].

-------------------

Proof of Claim:

Suppose two of the first n points are the same color. Then, by the pigeonhole priniciple, some color does not appear in the first n points. These two colors represent non-overlapping intervals.

Suppose that all of the first n points are different colors. Then the segment between the nth and (n+1)st point is contained in all intervals. Therefore all intervals overlap.

[Laramie]

L'lanmal: I do like your proof, but as you noted it is for a slightly different problem.

To be clear, suppose that for n=3 and that paired endpoints are denoted A, B, and C. The sequence ABBCCA would represent an overlapping scenario while ABBACC would represent a disjoint scenario.

[ralphmerridew]

For n=3:

Color the endpoints as described in L'lanmal's method. Let A be the first color, B the second, C the third.

Cases:
AABBCC yes
AABCBC yes
AABCCB yes
ABABCC yes
ABACBC no
ABACCB no
ABBACC yes
ABBCAC no
ABBCCA no
ABCABC no
ABCACB no
ABCBAC no
ABCBCA no
ABCCAB no
ABCCBA no

P(3) = 1/3.

Computer search gives P(n) = 1/3 for n=2,3,4,5,6,7,8,9

[Laramie]

ralphmerridew is correct, but there is an elegant proof of that for all n.

[L'lanmal]

I'm still looking, off and on. Induction has been difficult, because adding a color can not overlap with previously overlapping intervals, or add an interval that overlaps all of a set of non-overlapping. Knowing that the answer is 1/3rd may help some in the direction of a combinatorial proof.

[Laramie]

A hint for anyone still interested: I don't recommend a combinatorial approach (mostly because I needlessly wasted hours on it). Rather, I recommend thinking about how you might label pairs of endpoints in a useful order.

[L'lanmal]

Well, I for one am ready to see your answer.

[esme]

[Thok]

[esme]