Randomly draw $n$ intervals from $[0,1]$, where each end point A,B are selected from the uniform distribution between $[0,1]$.
What's the probability that at least one interval overlaps with all others?
Asked
Active
Viewed 3,253 times
21
-
1You can look at the probability that the last drawn $A_n$ is smaller than the minimum of all previously drawn $A$, and the probability that the last $B_n$ is greater than the maximum of all previously drawn $B$. This should be helpful. Then inflate the probability to account for the fact that we don't need the last one, but any one. (I don't have the time to work through it, but it looks like a fun little problem. Good luck!) – Stephan Kolassa Apr 20 '15 at 07:02
-
1It may be somewhat surprising that (1) the answer does not depend on the distribution (only that it be continuous) and (2) for $n\gt 1$ it is constant! – whuber Apr 22 '15 at 15:41
-
1Is this how the nth interval is construted: i) draw two numbers uniformly at random from [0,1], ii) let the smaller one be $A_n$ and the larger one $B_n$? – KOE Apr 23 '15 at 21:36
1 Answers
8
This post answers the question and outlines partial progress toward proving it correct.
For $n=1$, the answer trivially is $1$. For all larger $n$, it is (surprisingly) always $2/3$.
To see why, first observe that the question can be generalized to any continuous distribution $F$ (in place of the uniform distribution). The process by which the $n$ intervals are generated amounts to drawing $2n$ iid variates $X_1, X_2, \ldots, X_{2n}$ from $F$ and forming the intervals
$$[\min(X_1,X_2), \max(X_1,X_2)], \ldots, [\min(X_{2n-1}, X_{2n}), \max(X_{2n-1}, X_{2n})].$$
Because all $2n$ of the $X_i$ are independent, they are exchangeable. This means the solution would be the same if we were randomly to permute all of them. Let us therefore condition on the order statistics obtained by sorting the $X_i$:
$$X_{(1)} \lt X_{(2)} \lt \cdots \lt X_{(2n)}$$
(where, because $F$ is continuous, there is zero chance that any two will be equal). The $n$ intervals are formed by selecting a random permutation $\sigma\in\mathfrak{S}_{2n}$ and connecting them in pairs
$$[\min(X_{\sigma(1)},X_{\sigma(2)}), \max(X_{\sigma(1)},X_{\sigma(2)})], \ldots, [\min(X_{\sigma(2n-1)}, X_{\sigma(2n)}), \max(X_{\sigma(2n-1)}, X_{\sigma(2n)})].$$
Whether any two of these overlap or not does not depend on the values of the $X_{(i)}$, because overlapping is preserved by any any monotonic transformation $f:\mathbb{R}\to\mathbb{R}$ and there are such transformations that send $X_{(i)}$ to $i$. Thus, without any loss of generality, we may take $X_{(i)}=i$ and the question becomes:
Let the set $\{1,2,\ldots, 2n-1, 2n\}$ be partitioned into $n$ disjoint doubletons. Any two of them, $\{l_1,r_1\}$ and $\{l_2,r_2\}$ (with $l_i \lt r_i$), overlap when $r_1 \gt l_2$ and $r_2 \gt l_1$. Say that a partition is "good" when at least one of its elements overlaps all the others (and otherwise is "bad"). As a function of $n$, what is the proportion of good partitions?
To illustrate, consider the case $n=2$. There are three partitions,
$$\color{gray}{\{\{1,2\},\{3,4\}\}},\ \color{red}{\{\{1,4\},\{2,3\}\}},\ \color{red}{\{\{1,3\},\{2,4\}\}},$$
of which the two good ones (the second and third) have been colored red. Thus the answer in the case $n=2$ is $2/3$.
We may graph such partitions $\{\{l_i,r_i\},\,i=1,2,\ldots,n\}$ by plotting the points $\{1,2,\ldots,2n\}$ on a number line and drawing line segments between each $l_i$ and $r_i$, offsetting them slightly to resolve visual overlaps. Here are plots of the preceding three partitions, in the same order with the same coloring:
From now on, in order to fit such plots easily in this format, I will turn them sideways. For instance, here are the $15$ partitions for $n=3$, once again with the good ones colored red:
Ten are good, so the answer for $n=3$ is $10/15=2/3$.
The first interesting situation occurs when $n=4$. Now, for the first time, it is possible for the union of the intervals to span $1$ through $2n$ without any single one of them intersecting the others. An example is $\{\{1,3\},\{2,5\},\{4,7\},\{6,8\}\}$. The union of the line segments runs unbroken from $1$ to $8$ but this is not a good partition. Nevertheless, $70$ of the $105$ partitions are good and the proportion remains $2/3$.
The number of partitions increases rapidly with $n$: it equals $1\cdot 3\cdot 5 \cdots \cdot 2n-1 = (2n)!/(2^nn!)$. Exhaustive enumeration of all possibilities through $n=7$ continues to yield $2/3$ as the answer. Monte-Carlo simulations through $n=100$ (using $10000$ iterations in each) show no significant deviations from $2/3$.
I am convinced there is a clever, simple way to demonstrate there is always a $2:1$ ratio of good to bad partitions, but I have not found one. A proof is available through careful integration (using the original uniform distribution of the $X_i$), but it is rather involved and unenlightening.
whuber
- 322,774
-
Very cool. I have a hard time following what it means to "condition on the order statistics", would it be possible to add a line of intuition? Seems like a useful technique. I understand up to that the $X_i$ are exchangeable, indeed even $iid$, that that this allows us to consider any permutation. – KOE Apr 24 '15 at 16:10
-
2@Student To "condition on" means to say, let's temporarily hold these values fixed and consider what we can learn from that. Later, we will let those values vary (according to their probability distribution). In this case, once we find that the answer is $2/3$ regardless of the fixed values of the order statistics, then we no longer have to carry out the second step of varying the order statistics. Mathematically, the order stats are a vector-valued variable $\mathbf{X}$ and the indicator of being good is $Y$, so $$\mathbb{E}(Y)=\mathbb{E}(\mathbb{E}(Y|\mathbf{X}))=\mathbb{E}(2/3)=2/3.$$ – whuber Apr 24 '15 at 16:36
-