Gleichmäßig zufälliges Zeichnen von n Intervallen, Wahrscheinlichkeit, dass sich mindestens ein Intervall mit allen anderen überschneidet

In diesem Beitrag wird die Frage beantwortet und ein Teil der Fortschritte bei der Prüfung der Richtigkeit beschrieben.

Für ist die Antwort trivial . Für alle größeren ist es ( überraschend) immer . $n=1$ $1$ $n$ $2/3$

Um zu sehen, warum, stellen Sie zunächst fest, dass die Frage auf jede stetige Verteilung (anstelle der gleichmäßigen Verteilung) verallgemeinert werden kann . Der Prozess, durch den die Intervalle erzeugt werden, entspricht dem Zeichnen von iid, das von abweicht und die Intervalle bildet $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})].$

Da alle des unabhängig sind, sind sie austauschbar. Dies bedeutet, dass die Lösung dieselbe wäre, wenn wir alle zufällig permutieren würden. Bedingen wir also die durch Sortieren des erhaltene Ordnungsstatistik : $2n$ $X_i$ $X_i$

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

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

(Wo, weil stetig ist, gibt es keine Chance, dass zwei gleich sind). Die Intervalle werden gebildet, indem eine zufällige Permutation und paarweise verbunden werden $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)})].$

Ob sich zwei davon überlappen oder nicht, hängt nicht von den Werten von , $X_{(i)}$ da die Überlappung durch irgendeine monotone Transformation erhalten bleibt und es solche Transformationen gibt, die zu senden . Ohne Verlust der Allgemeinheit können wir also und die Frage lautet: $f:\mathbb{R}\to\mathbb{R}$ $X_{(i)}$ $i$ $X_{(i)}=i$

Die Menge sei in disjunkte Dubletten unterteilt. Zwei beliebige von ihnen, und (mit ), überlappen sich, wenn und $\{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$ . Angenommen, eine Partition ist "gut", wenn mindestens eines ihrer Elemente alle anderen überlappt (und ansonsten "schlecht" ist). Wie hoch ist der Anteil guter Partitionen in Abhängigkeit von ? $n$

Betrachten Sie zur Veranschaulichung den Fall . Es gibt drei Partitionen, $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\}\}},$

von denen die zwei guten (die zweite und die dritte) rot gefärbt sind. Somit ist die Antwort im Fall ist . $n=2$ $2/3$

Wir können solche Partitionen grafisch darstellen durch die Punkte Plotten auf einer Zahlengeraden und Zeichenliniensegmente zwischen jedem und ,verschmieren sie leicht visuelle Überlappungen zu lösen. Hier sind Diagramme der vorhergehenden drei Partitionen in derselben Reihenfolge mit derselben Färbung: $\{\{l_i,r_i\},\,i=1,2,\ldots,n\}$ $\{1,2,\ldots,2n\}$ $l_i$ $r_i$

Abbildung 1

Von nun an drehe ich sie zur Seite, um solche Zeichnungen in dieses Format zu integrieren. Zum Beispiel sind hier die Partitionen für , noch einmal mit den guten, die rot gefärbt sind: $15$ $n=3$

Figur 2

Zehn gut sind, so ist die Antwort für ist , . $n=3$ $10/15=2/3$

Die erste interessante Situation tritt auf, wenn . Jetzt ist es zum ersten Mal möglich, dass die Vereinigung der Intervalle bis ohne dass eines der Intervalle die anderen schneidet. Ein Beispiel ist . Die Vereinigung der Liniensegmente verläuft ungebrochen von bis $n=4$ $1$ $2n$ $\{\{1,3\},\{2,5\},\{4,7\},\{6,8\}\}$ $1$ $8$ Dies ist jedoch keine gute Partition. Trotzdem der Partitionen sind gut und der Anteil bleibt . $70$ $105$ $2/3$

Die Anzahl der Partitionen steigt mit rapide an : Sie entspricht . Erschöpfende Aufzählung aller Möglichkeiten durch weiterhin ergeben als Antwort. Monte-Carlo-Simulationen mit (jeweils Iterationen) zeigen keine signifikanten Abweichungen von $n$ $1\cdot 3\cdot 5 \cdots \cdot 2n-1 = (2n)!/(2^nn!)$ $n=7$ $2/3$ $n=100$ $10000$ . $2/3$

Ich bin überzeugt, dass es eine clevere und einfache Methode gibt, um zu demonstrieren, dass es immer ein Verhältnis zwischen guten und schlechten Partitionen gibt, aber ich habe keine gefunden. Ein Beweis ist durch sorgfältige Integration (unter Verwendung der ursprünglichen Gleichverteilung des ) verfügbar , aber er ist ziemlich kompliziert und nicht aufschlussreich. $2:1$ $X_i$

whuber
quelle

Sehr cool. Es fällt mir schwer zu verstehen, was es heißt, "die Auftragsstatistik zu bestimmen". Wäre es möglich, eine Intuitionslinie hinzuzufügen? Scheint eine nützliche Technik zu sein. Ich verstehe , dass bis zu dem

austauschbar sind, ja sogar

, dass , dass diese uns jede Permutation zu prüfen erlaubt.

X_{i}

$X_i$

i i d

$iid$

ekvall

@Student "Bedingung ein" bedeutet zu sagen, dass wir diese Werte vorübergehend festhalten und überlegen, was wir daraus lernen können. Später lassen wir diese Werte variieren (entsprechend ihrer Wahrscheinlichkeitsverteilung). In diesem Fall , wenn wir feststellen , dass die Antwort ist

unabhängig von den festen Werten der Auftragsstatistik, dann müssen wir nicht mehr den zweiten Schritt führen die Auftragsstatistik zu variieren. Mathematisch gesehen sind die Ordnungsstatistiken eine vektorielle Variable

und der Indikator für das Gute ist

, also

2 / 3

$2/3$

X

$\mathbf{X}$

Y

$Y$

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.$

Gleichmäßig zufälliges Zeichnen von n Intervallen, Wahrscheinlichkeit, dass sich mindestens ein Intervall mit allen anderen überschneidet

Antworten: