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?

probability

— Wendeta
źródło

Możesz zajrzeć na prawdopodobieństwo, że ostatni sporządzony

jest mniejszy niż minimum wszystkich uprzednio przygotowanego

, a prawdopodobieństwo, że ostatnia

jest większa niż maksimum wszystkich uprzednio przygotowanego

. To powinno być pomocne. Następnie zwiększ prawdopodobieństwo, aby uwzględnić fakt, że nie potrzebujemy ostatniego , ale żadnego . (Nie mam czasu, żeby się tym zająć, ale wygląda to na zabawny mały problem. Powodzenia!)

A_{n}

$A_n$

A

$A$

B_{n}

$B_n$

B

$B$

— S. Kolassa - Przywróć Monikę

Może być nieco zaskakujące, że (1) odpowiedź nie zależy od rozkładu (tylko, że jest ciągła) i (2) dla

n > 1

$n\gt 1$ jest stała!

— whuber

Jest to, w jaki sposób n th Interval construted: i) opracowuje dwa numery równomiernie losowo z [0,1], ii) niech mniejszy być

a większy

A_{n}

$A_n$

B_{n}

$B_n$

— ekvall

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 przedziały są generowane ilości do rysunku IID zmiennymi z i formowania przerwach $F$ $n$ $2n$ $X_1, X_2, \ldots, X_{2n}$ $F$

[min (X_{1}, X_{2}), max (X_{1}, X_{2})], \dots, [min (X_{2 n - 1}, X_{2 n}), max (X_{2 n - 1}, X_{2 n})] .

$[\min(X_1,X_2), \max(X_1,X_2)], \ldots, [\min(X_{2n-1}, X_{2n}), \max(X_{2n-1}, X_{2n})].$

Ponieważ wszystkie w 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 : $2n$ $X_i$ $X_i$

X_{(1)} < X_{(2)} < \dots < X_{(2 n)}

$X_{(1)} \lt X_{(2)} \lt \cdots \lt X_{(2n)}$

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

[min (X_{σ (1)}, X_{σ (2)}), max (X_{σ (1)}, X_{σ (2)})], \dots, [min (X_{σ (2 n - 1)}, X_{σ (2 n)}), max (X_{σ (2 n - 1)}, X_{σ (2 n)})] .

$[\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)})].$

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ą do . Zatem bez utraty ogólności możemy przyjąć i powstaje pytanie: $f:\mathbb{R}\to\mathbb{R}$ $X_{(i)}$ $i$ $X_{(i)}=i$

Niech zbiór zostanie podzielony na rozłącznych dubletów. Dowolne dwa z nich, i (z ), nakładają się, gdy i $\{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$

{{1, 2}, {3, 4}}, {{1, 4}, {2, 3}}, {{1, 3}, {2, 4}},

$\color{gray}{\{\{1,2\},\{3,4\}\}},\ \color{red}{\{\{1,4\},\{2,3\}\}},\ \color{red}{\{\{1,3\},\{2,4\}\}},$

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

Możemy grafować takie partycje , wykreślając punkty na numer linii i rysunku odcinki pomiędzy poszczególnymi 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 , jeszcze raz z dobrymi w kolorze czerwonym: $15$ $n=3$

Dziesięć są dobre, to odpowiedź dla to . $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 do bez żadnego z nich przecinającego się z innymi. Przykładem jest . Połączenie segmentów linii przebiega nieprzerwanie od 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.

— whuber
źródło

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}

$X_i$ are exchangeable, indeed even

i i d

$iid$ , that that this allows us to consider any permutation.

— ekvall

@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

$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

X

$\mathbf{X}$ and the indicator of being good is

Y

$Y$ , so

E (Y) = E (E (Y | X)) = E (2 / 3) = 2 / 3.

$\mathbb{E}(Y)=\mathbb{E}(\mathbb{E}(Y|\mathbf{X}))=\mathbb{E}(2/3)=2/3.$

— whuber