Dibujando n intervalos de manera uniforme al azar, probabilidad de que al menos un intervalo se superponga con todos los demás

Esta publicación responde a la pregunta y describe el progreso parcial para demostrar que es correcta.

Para , la respuesta trivial es . Para todos mayor , es (sorprendentemente) siempre . $n=1$ $1$ $n$ $2/3$

Para ver por qué, primero observe que la pregunta puede generalizarse a cualquier distribución continua (en lugar de la distribución uniforme). El proceso por el cual se generan los intervalos equivale a dibujar iid varia desde y formando los intervalos $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})].$

Como los de son independientes, son intercambiables. Esto significa que la solución sería la misma si fuéramos a permutarlos al azar. Por lo tanto, condicionemos las estadísticas de pedido obtenidas ordenando : $2n$ $X_i$ $X_i$

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

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

(donde, debido a que es continua, hay cero posibilidades de que dos sean iguales). Los intervalos se forman seleccionando una permutación aleatoria y conectándolos en pares $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)})].$

Si dos de estos se superponen o no, no depende de los valores de la , $X_{(i)}$ porque cualquier superposición monotónica conserva la superposición y existen tales transformaciones que envían a . Por lo tanto, sin ninguna pérdida de generalidad, podemos tomar y la pregunta es: $f:\mathbb{R}\to\mathbb{R}$ $X_{(i)}$ $i$ $X_{(i)}=i$

Deje que el conjunto se divida en dobles distonados. Dos de ellos, y (con ), se superponen cuando y $\{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$ . Digamos que una partición es "buena" cuando al menos uno de sus elementos se superpone a todos los demás (y de lo contrario es "malo"). En función de , ¿cuál es la proporción de buenas particiones? $n$

Para ilustrar, considere el caso . Hay tres particiones, $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\}\}},$

de los cuales los dos buenos (el segundo y el tercero) han sido coloreados en rojo. Por lo tanto la respuesta en el caso es . $n=2$ $2/3$

Podemos graficar tales particiones trazando los puntos en una línea numérica y dibujando segmentos de línea entre cada y , compensándolos ligeramente para resolver las superposiciones visuales. Aquí hay gráficos de las tres particiones anteriores, en el mismo orden con el mismo color: $\{\{l_i,r_i\},\,i=1,2,\ldots,n\}$ $\{1,2,\ldots,2n\}$ $l_i$ $r_i$

De ahora en adelante, para ajustar fácilmente estos gráficos en este formato, los giraré de lado. Por ejemplo, aquí están las particiones para , una vez más con las buenas de color rojo: $15$ $n=3$

Diez son buenas, así que la respuesta para es $n=3$ $10/15=2/3$ .

La primera situación interesante ocurre cuando . Ahora, por primera vez, es posible que la unión de los intervalos abarque de a sin que ninguno de ellos se cruce con los demás. Un ejemplo es . La unión de los segmentos de línea se ejecuta sin interrupciones de a $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
fuente

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

Dibujando n intervalos de manera uniforme al azar, probabilidad de que al menos un intervalo se superponga con todos los demás

Respuestas: