Rysowanie n przedziałów równomiernie losowo, prawdopodobieństwo, że co najmniej jeden przedział pokrywa się ze wszystkimi innymi

Narysuj losowo $n$ przedziałów od $[0,1]$ , gdzie każdy punkt końcowy A, B jest wybrany z równomiernego rozkładu między $[0,1]$ .

Jakie jest prawdopodobieństwo, że co najmniej jeden przedział pokrywa się ze wszystkimi pozostałymi?

Ten post odpowiada na pytanie i przedstawia częściowy postęp w kierunku udowodnienia, że ​​jest poprawny.

Dla $n=1$ odpowiedź brzmi trywialnie $1$ . Dla wszystkich większych $n$ jest (niespodziewanie) zawsze $2/3$ .

Aby zobaczyć, dlaczego, najpierw zauważ, że pytanie można uogólnić na dowolny ciągły rozkład (zamiast rozkładu równomiernego). Proces, w którym n przedziały są generowane ilości do rysunku 2 N IID zmiennymi X 1 , X 2 , ... , X 2 n z F i formowania przerwach$F$$n$$2n$$X_1, X_2, \ldots, X_{2n}$$F$

Ponieważ wszystkie w X i są niezależne są wymienne. Oznacza to, że rozwiązanie byłoby takie samo, gdybyśmy losowo dokonali permutacji wszystkich z nich. Uwarunkujmy zatem statystyki zamówień otrzymane przez posortowanie X i :$2n$$X_i$$X_i$

(gdzie, ponieważ jest ciągłe, nie ma szans, że dowolne dwa będą równe). Gdy n przedziały są utworzone wybierając losowo permutacji Ď ∈ S ma dwa n i łączenia ich w pary$F$$n$$\sigma\in\mathfrak{S}_{2n}$

To, czy którekolwiek z nich zachodzą na siebie, czy nie, nie zależy od wartości ,$X_{(i)}$ ponieważ zachodzenie na siebie jest zachowane przez dowolną transformację monotoniczną i istnieją takie transformacje, które wysyłają X ( i ) do i . Zatem bez utraty ogólności możemy przyjąć X ( i ) = i i powstaje pytanie:$f:\mathbb{R}\to\mathbb{R}$$X_{(i)}$$i$$X_{(i)}=i$

Niech zbiór zostanie podzielony na n rozłącznych dubletów. Dowolne dwa z nich, { l 1 , r 1 } i { l 2 , r 2 } (z l i < r i ), nakładają się, gdy r 1 > l 2 i 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$. Powiedz, że partycja jest „dobra”, gdy co najmniej jeden z jej elementów nakłada się na wszystkie pozostałe (a poza tym jest „zła”). Jaki jest odsetek dobrych partycji w funkcji ?$n$

Aby to zilustrować, rozważ przypadek . Istnieją trzy partycje,$n=2$

z których dwa dobre (drugi i trzeci) zostały zabarwione na czerwono. Tak więc, odpowiedź w przypadku to 2 / 3 .$n=2$$2/3$

Możemy grafować takie partycje , wykreślając punkty { 1 , 2 , ... , 2 n } na numer linii i rysunku odcinki pomiędzy poszczególnymi l i i r I , kompensację lekko rozwiązać nakładania wizualne. Oto wykresy z poprzednich trzech partycji, w tej samej kolejności z tym samym kolorem:$\{\{l_i,r_i\},\,i=1,2,\ldots,n\}$$\{1,2,\ldots,2n\}$$l_i$$r_i$

Odtąd, aby łatwo dopasować takie wykresy do tego formatu, obrócę je na boki. Na przykład, oto partycji dla n = 3 , jeszcze raz z dobrymi w kolorze czerwonym:$15$$n=3$

Dziesięć są dobre, to odpowiedź dla to 10 / 15 = 2 / 3 .$n=3$$10/15=2/3$

Pierwsza interesująca sytuacja ma miejsce, gdy . Teraz, po raz pierwszy, możliwe jest połączenie przedziałów od 1 do 2 n bez żadnego z nich przecinającego się z innymi. Przykładem jest { { 1 , 3 } , { 2 , 5 } , { 4 , 7 } , { 6 , 8 } } . Połączenie segmentów linii przebiega nieprzerwanie od 1 do $n=4$$1$$2n$$\{\{1,3\},\{2,5\},\{4,7\},\{6,8\}\}$$1$$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.