Desenhar n intervalos uniformemente aleatoriamente, probabilidade de que pelo menos um intervalo se sobreponha a todos os outros

Desenhe aleatoriamente $n$ intervalos de $[0,1]$ , onde cada ponto final A, B é selecionado a partir da distribuição uniforme entre $[0,1]$ .

Qual é a probabilidade de que pelo menos um intervalo se sobreponha a todos os outros?

Este post responde à pergunta e descreve o progresso parcial para provar que está correto.

Para , a resposta trivialmente é 1 . Para todos maior n , é (surpreendentemente) sempre 2 / 3 .$n=1$$1$$n$$2/3$

Para entender por que, observe primeiro que a questão pode ser generalizada para qualquer distribuição contínua (no lugar da distribuição uniforme). O processo pelo qual os n intervalos são gerados equivale a desenhar 2 n iid varia X 1 , X 2 , … , X 2 n de F e formar os intervalos$F$$n$$2n$$X_1, X_2, \ldots, X_{2n}$$F$

Como todos os do X i são independentes, eles são trocáveis. Isso significa que a solução seria a mesma se permitíssemos aleatoriamente todos eles. Portanto, vamos condicionar as estatísticas de ordem obtidas ordenando o X i :$2n$$X_i$$X_i$

(onde é contínuo, não há chance de dois serem iguais). Os intervalos n são formados selecionando uma permutação aleatória σ ∈ S 2 n e conectando-os em pares$F$$n$$\sigma\in\mathfrak{S}_{2n}$

Se dois deles se sobrepõem ou não, não depende dos valores de ,$X_{(i)}$ porque a sobreposição é preservada por qualquer transformação monotônica e existem essas transformações que enviam X ( i ) para i . Assim, sem qualquer perda de generalidade, podemos tomar X ( i ) = i e a questão passa a ser:$f:\mathbb{R}\to\mathbb{R}$$X_{(i)}$$i$$X_{(i)}=i$

Deixe o conjunto ser particionado em n doubletons separados. Quaisquer dois deles, { l 1 , R 1 } e { l 2 , R 2 } (com l i < r i ), se sobrepõem quando r 1 > l 2 e 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$. Diga que uma partição é "boa" quando pelo menos um de seus elementos se sobrepõe a todas as outras (e, caso contrário, é "ruim"). Em função de , qual é a proporção de boas partições?$n$

Para ilustrar, considere o caso . Existem três partições,$n=2$

dos quais os dois bons (o segundo e o terceiro) foram de cor vermelha. Assim, a resposta no caso é 2 / 3 .$n=2$$2/3$

Podemos representar graficamente essas partições , plotando os pontos { 1 , 2 , … , 2 n } em uma linha numérica e desenhando segmentos de linha entre cada l i e r i , deslocando-os levemente para resolver sobreposições visuais. Aqui estão os gráficos das três partições anteriores, na mesma ordem e com a mesma cor:$\{\{l_i,r_i\},\,i=1,2,\ldots,n\}$$\{1,2,\ldots,2n\}$$l_i$$r_i$

A partir de agora, para encaixar tais parcelas facilmente neste formato, eu as virarei de lado. Por exemplo, aqui estão as partições para n = 3 , mais uma vez com as boas coloridas em vermelho:$15$$n=3$

Dez são boas, de modo que a resposta para é 10 / 15 = 2 / 3 .$n=3$$10/15=2/3$

A primeira situação interessante ocorre quando . Agora, pela primeira vez, é possível que a união dos intervalos abranja 1 a 2 n sem que nenhum deles cruze os outros. Um exemplo é { { 1 , 3 } , { 2 , 5 } , { 4 , 7 } , { 6 , 8 } } . A união dos segmentos de linha corre ininterrupta de 1 a $n=4$$1$$2n$$\{\{1,3\},\{2,5\},\{4,7\},\{6,8\}\}$$1$$8$mas essa não é uma boa partição. No entanto, dos 105 partições são boas e a proporção permanece 2 / 3 .$70$$105$$2/3$

O número de partições aumenta rapidamente com : é igual a 1 ⋅ 3 ⋅ 5 ⋯ ⋅ 2 n - 1 = ( 2 n ) ! / ( 2 n n ! ) . Enumeração exaustiva de todas as possibilidades através n = 7 continua para se obter 2 / 3 como a resposta. As simulações de Monte Carlo através de n = 100 (usando 10000 iterações em cada) não mostram desvios significativos de $n$$1\cdot 3\cdot 5 \cdots \cdot 2n-1 = (2n)!/(2^nn!)$$n=7$$2/3$$n=100$$10000$ .$2/3$

$2:1$$X_i$