Intersecting Intervals

Solution

We generate \(n\) random intervals in \([0,1]\). Each interval is formed by choosing two independent random points in \([0,1]\) and taking them as its endpoints. The key observation is that the exact numerical values of the endpoints do not matter; only their relative order does. If we list all \(2n\) endpoints in increasing order, we may label them \[ 1,2,3,\dots,2n. \] Each interval corresponds to a pair among these \(2n\) positions, so the whole experiment is equivalent to the following purely combinatorial model: Take the \(2n\) points \(1,2,\dots,2n\) and pair them uniformly at random. Every pairing corresponds to a set of \(n\) intervals. Two intervals intersect exactly when their corresponding pairs interleave. For example, if the pairs are \((a,b)\) and \((c,d)\) with \(a < b\) and \(c < d\), then the intervals intersect unless \[ a < b < c < d \quad \text{or} \quad c < d < a < b. \] The question therefore becomes: Among all random pairings of \(2n\) points, what is the probability that one of the intervals intersects all the others? The proof constructs the pairing step by step. At each stage we choose a point \(A_j\) and randomly assign its partner \(B_j\). The important feature of the construction is that the points are divided into two halves \[ \{1,\dots,n\} \quad \text{(left side)}, \qquad \{n+1,\dots,2n\} \quad \text{(right side)}. \] The algorithm always chooses the next \(A_j\) so that the already chosen points stay balanced between the two sides as much as possible. When the pairs are of the form \[ A_j < B_j \] (the endpoint starts on the left side and ends on the right side), we call them AB-type pairs. When \[ A_j > B_j \] we call them BA-type pairs. While only AB-type pairs appear, the numbers of matched points on the left and right remain equal. Once a BA-type pair appears, the left side temporarily has two extra matched points until the next AB-type pair restores the balance. After choosing \(n-2\) pairs, exactly four points remain unpaired: \[ a < b < c < d. \] Only one final choice remains: which point is paired with \(a\). There are three equally likely possibilities: \[ (a,b), \quad (a,c), \quad (a,d). \] Now examine whether an interval intersecting all others exists. If \[ (a,c) \] is chosen, then the interval \([a,c]\) spans the central region containing the other intervals, so it intersects every one of them. If \[ (a,d) \] is chosen, the interval \([a,d]\) is even larger and clearly intersects all others. Thus in these two cases such an interval exists. Now consider the third possibility: \[ (a,b). \] Then the remaining pair must be \[ (c,d). \] The intervals \([a,b]\) and \([c,d]\) are disjoint, so neither can intersect all others. The proof in the paper shows that in this situation none of the previously formed intervals can intersect all the others either. The structure forced by the construction guarantees that one earlier interval must miss another one. Therefore in this case no universal intersecting interval exists. Since the three pairings of \(a\) are equally likely and exactly two of them produce an interval that intersects all others, the probability is \[ \frac{2}{3}. \] Thus, remarkably, the probability does not depend on \(n\). \[ \Pr(\text{some interval intersects all others}) = \frac{2}{3}. \]