Рисование n интервалов равномерно случайным образом, вероятность того, что хотя бы один интервал перекрывается со всеми остальными

Случайным образом нарисуйте $n$ интервалов из $[0,1]$ , где каждая конечная точка A, B выбрана из равномерного распределения между .$[0,1]$

Какова вероятность того, что хотя бы один интервал перекрывается со всеми остальными?

Этот пост отвечает на вопрос и описывает частичный прогресс в доказательстве его правильности.

Для ответ тривиально равен 1 . Для всех больших $n=1$$1$$n$ , то (удивительно) всегда .$2/3$

Чтобы понять почему, сначала отметим, что вопрос можно обобщить на любое непрерывное распределение (вместо равномерного распределения). Процесс, с помощью которого создаются n интервалов, приводит к вытягиванию 2 n iid переменных X 1 , X 2 , … , X 2 n из F и формированию интервалов$F$$n$$2n$$X_1, X_2, \ldots, X_{2n}$$F$

Поскольку все из X i независимы, они являются взаимозаменяемыми. Это означает, что решение было бы таким же, если бы мы были случайным образом переставить их всех. Поэтому приведем условие для статистики порядка, полученной путем сортировки X i :$2n$$X_i$$X_i$

(где, поскольку непрерывен, существует нулевая вероятность того, что любые два будут равны). В п интервалы формируются путем выбора случайной перестановки сг ∈ š 2 н и соединяя их в парах$F$$n$$\sigma\in\mathfrak{S}_{2n}$

Независимо от того, перекрываются ли эти два параметра или нет, не зависит от значений ,$X_{(i)}$ поскольку перекрытие сохраняется любым монотонным преобразованием и существуют такие преобразования, которые отправляют X ( i ) в i . Таким образом, без потери общности мы можем принять X ( i ) = i, и возникает вопрос:$f:\mathbb{R}\to\mathbb{R}$$X_{(i)}$$i$$X_{(i)}=i$

Пусть множество разбито на n непересекающихся дублетов. Любые два из них, { l 1 , r 1 } и { l 2 , r 2 } (с l i < r i ), перекрываются, когда r 1 > l 2 и r 2 > l $\{1,2,\ldots, 2n-1, 2n\}$$n$$\{l_1,r_1\}$$\{l_2,r_2\}$$l_i \lt r_i$$r_1 \gt l_2$$r_2 \gt l_1$, Скажите, что раздел «хороший», когда хотя бы один из его элементов перекрывает все остальные (а в противном случае «плохой»). Какая доля хороших разбиений зависит от ?$n$

Для иллюстрации рассмотрим случай . Есть три раздела,$n=2$

из которых два хороших (второй и третий) были окрашены в красный цвет. Таким образом, ответ в случае является 2 / 3 .$n=2$$2/3$

Мы можем построить график таких разделов путем построения точек { 1 , 2 , … , 2 n } на числовой линии и рисования отрезков между каждым l i и r i , слегка смещая их для устранения визуальных перекрытий. Вот графики предыдущих трех разделов, в том же порядке с одинаковой раскраской:$\{\{l_i,r_i\},\,i=1,2,\ldots,n\}$$\{1,2,\ldots,2n\}$$l_i$$r_i$

Отныне, чтобы легко разместить такие графики в этом формате, я поверну их вбок. Например, вот разделов для n = 3 , еще раз с хорошими, выделенными красным:$15$$n=3$

Десять хорошо, так что ответ на является 10 / 15 = 2 / 3 .$n=3$$10/15=2/3$

Первая интересная ситуация возникает при . Теперь впервые возможно, чтобы объединение интервалов охватывало от 1 до 2 n, при этом ни один из них не пересекает другие. Примером является { { 1 , 3 } , { 2 , 5 } , { 4 , 7 } , { 6 , 8 } } . Объединение отрезков проходит непрерывно от 1 до $n=4$$1$$2n$$\{\{1,3\},\{2,5\},\{4,7\},\{6,8\}\}$$1$$8$ но это не очень хороший раздел. Тем не менее, из$70$ разделовявляются хорошимии доля остается 2 / 3 .$105$$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.