Dibujar aleatoriamente $n$ intervalos de $[0,1]$, donde cada punto final a,B son seleccionados a partir de una distribución uniforme entre el $[0,1]$.
¿Cuál es la probabilidad de que al menos uno de los intervalos se superpone con todos los demás?
Respuesta
¿Demasiados anuncios?
jldugger
Puntos
7490
Este post responde a la pregunta y contornos parciales de progreso hacia la prueba correcta.
Para $n=1$, la respuesta es trivialmente $1$. Para todos los mayores $n$, es (para mi sorpresa) siempre $2/3$.
Para ver por qué, primero observar que la pregunta puede ser generalizado a cualquier distribución continua $F$ (en lugar de la distribución uniforme). El proceso por el cual el $n$ intervalos se generan cantidades a dibujar $2n$ iid varia $X_1, X_2, \ldots, X_{2n}$ $F$ y la formación de los intervalos
$$[\min(X_1,X_2), \max(X_1,X_2)], \ldots, [\min(X_{2n-1}, X_{2n}), \max(X_{2n-1}, X_{2n})].$$
Porque todos los $2n$ de la $X_i$ son independientes, son intercambiables. Esto significa que la solución sería la misma si fuéramos al azar para permutar todos ellos. Tomemos, pues, la condición en el orden de las estadísticas obtenidas a través de la clasificación de la $X_i$:
$$X_{(1)} \lt X_{(2)} \lt \cdots \lt X_{(2n)}$$
(donde, debido a $F$ es continuo, no existe la posibilidad de que cualquiera de los dos será igual). El $n$ intervalos que se forman mediante la selección al azar de permutación $\sigma\in\mathfrak{S}_{2n}$ y se conectan en pares
$$[\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)}$, debido a la superposición es conservada por cualquier transformación monotónica $f:\mathbb{R}\to\mathbb{R}$ y hay transformaciones que envían $X_{(i)}$$i$. Por lo tanto, sin pérdida de generalidad, podemos tomar la $X_{(i)}=i$ y la pregunta se convierte en:
Deje que el conjunto de $\{1,2,\ldots, 2n-1, 2n\}$ dividirse en $n$ discontinuo doubletons. Dos de ellos, $\{l_1,r_1\}$ $\{l_2,r_2\}$ ( $l_i \lt r_i$ ), se superponen al$r_1 \gt l_2$$r_2 \gt l_1$. Decir que una partición es "buena" cuando al menos uno de sus elementos se superpone a todos los demás (y de otro modo es "malo"). Como una función de la $n$, ¿cuál es la proporción de bien las particiones?
Para ilustrar, considere el caso en $n=2$. Hay tres particiones,
$$\color{gray}{\{\{1,2\},\{3,4\}\}},\ \color{red}{\{\{1,4\},\{2,3\}\}},\ \color{red}{\{\{1,3\},\{2,4\}\}},$$
de que las dos buenas (la segunda y la tercera) han sido coloreadas de rojo. Por lo tanto la respuesta en el caso de $n=2$$2/3$.
Podemos gráfico particiones $\{\{l_i,r_i\},\,i=1,2,\ldots,n\}$ por el trazado de los puntos de $\{1,2,\ldots,2n\}$ en un número de línea y el dibujo de segmentos de línea entre cada una de las $l_i$$r_i$, compensando un poco para resolver visual se superpone. Aquí están las parcelas de los anteriores tres particiones, en el mismo orden con los mismos colores:
A partir de ahora, en el fin de ajustarse a dichas parcelas fácilmente en este formato, voy a girar hacia los lados. Por ejemplo, aquí están las $15$ particiones para $n=3$, una vez más, de los buenos, de color rojo:
Diez son buenas, así que la respuesta de $n=3$$10/15=2/3$.
La primera situación interesante se produce cuando $n=4$. Ahora, por primera vez, es posible que la unión de los intervalos para abarcar $1$ a través de $2n$ sin que uno de ellos la intersección de los demás. Un ejemplo es $\{\{1,3\},\{2,5\},\{4,7\},\{6,8\}\}$. La unión de los segmentos de línea se ejecuta ininterrumpida de$1$$8$, pero esto no es una buena partición. Sin embargo, $70$ de la $105$ particiones están bien y la proporción sigue siendo $2/3$.
El número de particiones aumenta rápidamente con la $n$: es igual a $1\cdot 3\cdot 5 \cdots \cdot 2n-1 = (2n)!/(2^nn!)$. La enumeración exhaustiva de todas las posibilidades a través de las $n=7$ continúa rindiendo $2/3$ como la respuesta. Simulaciones Monte-Carlo a través de $n=100$ (con $10000$ iteraciones en cada uno), no muestran desviaciones significativas de $2/3$.
Estoy convencido de que hay una inteligente, simple manera de demostrar que siempre hay un $2:1$ proporción del bien y el mal las particiones, pero no he encontrado uno. Una prueba está disponible a través de una cuidadosa integración (a través de la distribución uniforme de la $X_i$), pero es bastante implicada y unenlightening.
