Probabilidad de que un palo roto al azar en cinco lugares pueda formar un tetraedro

Question

Editar (junio. 2015) Esta pregunta ha sido trasladada a MathOverflow, donde un reciente escrito encuentra una aproximación similar a la del post de leonbloy; ver aquí .

---

Rompe un palo al azar en cinco lugares.

Pregunta: ¿Cuál es la probabilidad de que las seis piezas resultantes puedan formar un tetraedro?

Es evidente que la satisfacción de la desigualdad del triángulo en cada cara es una condición necesaria pero no condición suficiente; a continuación se ofrece un ejemplo.

Además, otro comentarista señala amablemente un referencia que puede ser de ayuda para resolver este problema. En particular, relaciona la cuestión de cuándo seis números pueden ser aristas de un tetraedro con una determinada $5 \times 5$ determinante.

Por último, un tercer comentarista señala que, dado que una de estas construcciones es posible, existe una vecindad admisible en torno a esta disposición, por lo que la probabilidad es de hecho positiva.

En cualquier caso, este problema es mucho más difícil que el clásico $2D$ "formar un triángulo" uno.

A continuación se pueden encontrar varios ataques numéricos; agradeceré si alguien puede proporcionar una solución exacta.

Answer 1

No es una respuesta, pero podría ayudar a avanzar. [La derivación que sigue proporciona un límite estricto -pero prácticamente inútil-. La segunda parte de la respuesta tiene algunos resultados que pueden ser de interés, pero son meramente empíricos]

---

Consideremos el caso (mucho más restringido) de que las seis longitudes formen un tetraedro en cualquier orden. En el pdf enlazado este conjunto de longitudes se denomina "completamente tetraédrico", y se da una condición necesaria-suficiente (Teorema 4.2) que equivale a lo siguiente: $ u \le \sqrt{2}v $ , donde $u,v$ son las longitudes máxima y mínima. Esto, informalmente, correspondería a tetraedros "casi regulares". Calculemos entonces la probabilidad de que las longitudes sean completamente tetraédricas. Dado que los puntos se eligen al azar, de manera uniforme, las longitudes son probabilísticamente equivalentes a un conjunto de variables exponenciales iid con parámetro arbitrario, condicionadas a una suma constante. Como sólo nos interesan las proporciones, podemos incluso ignorar este condicionamiento. Ahora, la probabilidad conjunta del máximo y del mínimo de un conjunto de $n$ variables iid viene dada por

$$ f_{u,v}= n(n-1) f(u) f(v) [F(u) -F(v)]^{n-2}, \hskip{1cm} u\ge v$$

En nuestro caso: $n=6$ , $f(u)=e^{-u}$ y la probabilidad de que $u<a \, v$ es una integral directa, que da:

$$P(u<a \, v)= 5 (a -1)\left( \frac{1}{1+5\,a}-\frac{4}{2+4\,a}+\frac{6}{3+3\,a}-\frac{4}{4+2\,a}+\frac{1}{5+1\,a} \right)$$

Y $P(u<\sqrt{2} v) \approx 7.46 \times 10^{-5}$ Esto debería ser un límite estricto para la probabilidad deseada, pero, seguramente, está lejos de ser ajustado.

[ Actualización : efectivamente, el límite es prácticamente inútil, corresponde a una cola irrelevante. La probabilidad, según mis simulaciones, es de alrededor de $p=0.06528$ ( $N=10^9$ intentos, $3 \, \sigma \approx 2.3 \times 10^{-5}$ ), lo que coincide con otros resultados].

---

El único resultado empírico que puede ser de interés: Es fácil ver que, desde el $6!$ posibles permutaciones de las longitudes, podemos limitarnos a $30$ por consideraciones de simetría; ahora, a partir de mis simulaciones, he encontrado que es suficiente considerar 7 permutaciones, siendo las dos primeras ya suficientes para más de $90\%$ de los éxitos; y la (necesidad de considerar la) séptima es extremadamente pequeña. Estas permutaciones son:

$$p_1 = [0 , 1 , 4 , 5 , 3 , 2] \hskip{1 cm} (0.75837)\\ p_2 = [0 , 1 , 4 , 3 , 5 , 2] \hskip{1 cm} (0.15231)\\ p_3 = [0 , 2 , 4 , 1 , 5 , 3] \hskip{1 cm} (0.08165)\\ p_4 = [0 , 1 , 4 , 5 , 2 , 3] \hskip{1 cm} (0.00404)\\ p_5 = [0 , 1 , 4 , 2 , 5 , 3] \hskip{1 cm} (0.00245)\\ p_6 = [0 , 1 , 3 , 5 , 4 , 2] \hskip{1 cm} (0.00116)\\ p_7 = [0 , 1 , 3 , 4 , 5 , 2] \hskip{1 cm} (0.00002)\\ $$

Los índices de longitud corresponden a una matriz ordenada (digamos, de forma ascendente), y siguiendo la convención del documento enlazado: los tres primeros lados tienen un vértice común, los tres siguientes son los correspondientes lados opuestos (así, por ejemplo, en la primera permutación, y con diferencia la más favorable, los lados más largos y más cortos son opuestos). Los números de la derecha son la probabilidad de que esta permutación (cuando se intenta en el orden anterior) sea la exitosa (dado que forman un tetraedro). No puedo estar totalmente seguro de si hay algún caso raro que requiera otra permutación (muy improbable, diría yo), pero estoy bastante seguro (a no ser que haya cometido algún error) de que el conjunto no puede reducirse más.

Answer 2

Esto no es una respuesta sino un largo comentario a la petición de detalles de otra persona.

A continuación, algunos detalles de mi simulación. Espero que sea útil para los que se interesan por los números.

En un tetraedro, utilizaré 6 variables $a,b,c,A,B,C$ para representar las longitudes de 6 aristas. $a,b,c$ corresponde a las aristas conectadas a un vértice arbitrario y $A,B,C$ son las longitudes de las aristas opuestas correspondientes.

Paso 1 Genera previamente el conjunto de 120 permutaciones de 5 símbolos y filtra las equivalentes hasta llegar a 30. $$\begin{align} &S\; = \operatorname{Perm}(\{\,1,2,3,4,5\,\})\\ \xrightarrow{\text{filter}} & S' = \{\, \pi \in S : \pi(1) = \min(\pi(1),\pi(2),\pi(4),\pi(5))\, \} \end{align}$$

La condición de filtrado corresponde al hecho de que una vez que un par de bordes opuestos $(a,A)$ se elige, hay una simetría cuádruple en la asignación de los 2 pares restantes de de aristas opuestas. Seguir 4 asignaciones de longitudes conduce a tetraedros equivalentes.

$$(a,b,c,A,B,C) \equiv (a,c,b,A,C,B) \equiv (a,B,C,A,b,c) \equiv (a,C,B,A,c,b)$$

Paso 2 Extraer 5 números aleatorios uniformes de $[0,1]$ clasificarlos y convertirlos en 6 trozos:
$$\begin{align}& X_i = \operatorname{Rand}(0,1), i = 1,\ldots 5\\ \xrightarrow{\text{sort} X_i} & 0 \le X_1 \le \ldots \le X_5 \le 1\\ \xrightarrow{Y_i = X_{i+1}-X_i} &Y_0 = X_1,\,Y_1 = X_2-X_1,\, \ldots,\, Y_5 = 1-X_5 \end{align}$$

Paso 3 Recorrer la lista de permutación en $S'$ para cada permutación $\pi$ asigna las 6 longitudes a las 6 aristas:

$$(Y_0, Y_{\pi(1)}, Y_{\pi(2)}, \ldots, Y_{\pi(5)}) \longrightarrow (a, b, c, A, B, C )$$

Verifica si esta asignación genera un tetraedro válido comprobando:

• Todas las caras satisfacen la desigualdad triangular. Esto se puede representar de forma compacta como $$\min(a+b+c,a+B+C,A+b+C,A+B+c) > \max(a+A,b+B,c+C)$$
• El determinante de Cayler-Menger correspondiente es positivo. Hasta un factor de escala, esto es:

$$\left|\begin{matrix}0 & 1 & 1 & 1 & 1\cr 1 & 0 & {a}^{2} & {b}^{2} & {c}^{2}\cr 1 & {a}^{2} & 0 & {C}^{2} & {B}^{2}\cr 1 & {b}^{2} & {C}^{2} & 0 & {A}^{2}\cr 1 & {c}^{2} & {B}^{2} & {A}^{2} & 0\end{matrix}\right| > 0$$

Si esta configuración es admisible, regístrala y pasa a Paso 2 . Si no es así, pruebe con otras permutaciones de $S'$ .

Algunos comentarios sobre si esto es útil para la respuesta exacta .

A $N = 10^9$ La simulación no es suficiente. La probabilidad de formar un tetraedro es de aproximadamente $p = 0.065$ . Una simulación de este tipo nos dará un número exacto de aproximadamente $\sqrt{\frac{p(1-p)}{N}} \sim 1.5 \times 10^{-5}$ . es decir, una precisión de 5 dígitos.

Hasta lo que he oído, necesitamos unos 7 dígitos de precisión antes de alimentar esto en el existente Inversor de Pluoffe y encontrar si este número se parece a una combinación de constantes matemáticas simples.

Hasta que se pueda acelerar el algoritmo para tener una $N > 10^{13}$ simulación o tener un mejor control de los términos de error. La simulación sólo es útil para realizar comprobaciones cruzadas.

Answer 3

Descargo de responsabilidad : Este es otro comentario largo que informa sobre el intento de atacar el problema numéricamente.

---

En lugar de parametrizar los 6 segmentos del bastón unitario como $$(u_1,u_2-u_1,u_3-u_2,u_4-u_3,u_5-u_4,1-u_5)$$ donde $(u_1,u_2,u_3,u_4,u_5)$ son estadísticos de orden de la distribución uniforme con pdf $$ f_U(u_1,u_2,u_3,u_4,u_5) = 5! \cdot \left[0<u_1<u_2<u_3<u_4<u_5<1 \right] $$ Estoy utilizando una parametrización diferente: $$ (1-w_1, w_1 (1-w_2), w_1 w_2 (1-w_3), w_1 w_2 w_3 (1-w_4), w_1 w_2 w_3 w_4 (1-w_5), w_1 w_2 w_3 w_4 w_5 ) $$ Es fácil de resolver para $\{w_k\}$ en términos de $\{u_k\}$ : $$ w_1 = 1-u_1, w_2 = \frac{1-u_2}{1-u_1}, w_3 = \frac{1-u_3}{1-u_2}, w_4 = \frac{1-u_4}{1-u_3}, w_5 = \frac{1-u_5}{1-u_4} $$ que permite encontrar su medida inducida: $$ f_W(w_1,w_2,w_3,w_4,w_5) = (5 w_1^4 [0<w_1<1]) \cdot (4 w_2^3 [0<w_2<1]) \cdot (3 w_3^2 [0<w_3<1] ) \cdot (2 w_4 [0<w_4<1]) \cdot ( [0<w_5<1] ) $$ lo que significa que $w_k$ son variables aleatorias independientes con diferentes distribuciones de potencia en el intervalo unitario.

Esta parametrización es más amigable para las rutinas de integración numérica.

A continuación, procedemos como @achille-hui . Aquí está Mathematica código que ejecuté:

TriangleInequalities[{a_, b_, c_}] := 
 a < b + c && b < a + c && c < a + b

FacialTetrahedron[{x_, y_, z_, xb_, yb_, zb_}] := 
 TriangleInequalities[{x, y, zb}] && 
  TriangleInequalities[{x, yb, z}] && 
  TriangleInequalities[{xb, y, z}] && 
  TriangleInequalities[{xb, yb, zb}]

TetrahedraSextupleQ[{x_, y_, z_, xb_, yb_, zb_}] := 
 FacialTetrahedron[{x, y, z, xb, yb, zb}] && 
  Det[{{0, x^2, y^2, z^2, 1}, {x^2, 0, zb^2, yb^2, 1}, {y^2, zb^2, 0, 
      xb^2, 1}, {z^2, yb^2, xb^2, 0, 1}, {1, 1, 1, 1, 0}}] > 0

Ahora construimos el suceso de que se puede formar un tetraedro a partir de 6 trozos en los que se divide el palo de la unidad. Lo siguiente lleva un tiempo de cálculo.

event2 = Assuming[
   0 < w1 < 1 && 0 < w2 < 1 && 0 < w3 < 1 && 0 < w4 < 1 && 0 < w5 < 1,
    Simplify[
    Apply[Or, 
     Simplify[TetrahedraSextupleQ[#]] & /@ 
      Permutations[{(1 - w1), 
        w1 (1 - w2), w1 w2 (1 - w3), w1 w2 w3 (1 - w4), 
           w1 w2 w3 w4 (1 - w5), w1 w2 w3 w4 w5 }]]]];

Por lo tanto, yo guardado el predicado resultante en la pasta de la caja. A continuación se explica cómo importarlo:

event2 = ToExpression[
   Import["http://pastebin.com/raw.php?i=399MDkGQ", "Text"], 
   InputForm];

Ahora definimos una función de filtro compilada para decidir si un vector aleatorio dispara el evento.

cfFunc2 = With[{ee = event2},                                                   
           Compile[{{arg, _Real, 1}}, Block[{w1, w2, w3, w4, w5},               
             {w1, w2, w3, w4, w5} = arg;                                        
             If[ee, 1, 0]], RuntimeAttributes -> Listable]];

La función anterior permite ejecutar eficazmente la simulación de Monte-Carlo. Aquí está la simulación que dura unas 4,7 horas:

In[3]:= Block[{sample, tot = 0, suc = 0},                                       
          While[suc <= 10^9,                                                    
           sample =                                                             
            RandomVariate[                                                      
             ProductDistribution[PowerDistribution[1, 5],                       
              PowerDistribution[1, 4], PowerDistribution[1, 3],                 
              PowerDistribution[1, 2], UniformDistribution[]], 3*10^8];         
           tot += Length[sample];                                               
           suc += Total[cfFunc2[sample]];                                       
           ];                                                                   
          {suc, tot}                                                            
          ] // AbsoluteTiming                                                   

Out[3]= {16994.098510, {1018403735, 15600000000}}

Se trata de lo siguiente $(1-10^{-8})/2$ -de nivel de confianza:

In[38]:= Block[{suc = 1018403735, tot = 15600000000}, 
 PlusMinus[N[suc/tot], 
  Sqrt[2.] InverseErfc[10^-8] Sqrt[
    With[{p = suc/tot}, p (1 - p)/tot]]]]

Out[38]= 0.0652823 \[PlusMinus] 0.0000113341

La ventaja del $w$ -es que se pueden aplicar las reglas de cuadratura cartesianas. Utilizando el hecho de que $w_k = 2^{-1/k}$ para $1 \leqslant k \leqslant 5$ proporciona una división tetraédrica:

In[160]:= event2 /. {w1 -> (1/2)^(1/5), w2 -> (1/2)^(1/4), 
  w3 -> (1/2)^(1/3), w4 -> (1/2)^(1/2), w5 -> 1/2`}

Out[160]= True

podemos ayudarnos del algoritmo de cuadratura numérica para encontrar un punto de muestra dentro de la región de interés. Así que con suficiente tiempo a mano debería ser posible obtener una respuesta de cuadratura más precisa:

AbsoluteTiming[
 prob = NIntegrate[
   f[w1, w2, w3, w4, w5], {w1, 0, (1/2)^(1/5), 1}, {w2, 
    0, (1/2)^(1/4), 1}, {w3, 0, (1/2)^(1/3), 1}, {w4, 0, (1/2)^(1/2), 
    1}, {w5, 0, 1/2, 1}, 
   Method -> {"CartesianRule", "SymbolicProcessing" -> 0}, 
   MaxRecursion -> 14]]

Sin embargo, después de unas 20 horas, este comando de integración sigue funcionando... Publicaré la respuesta una vez que se haya completado la evaluación.

Answer 4

Demasiado largo para un comentario: Las condiciones necesarias y suficientes que describen su tetraedro son:

1. La suma de los seis segmentos es constante: $$(a+b+c)+(x+y+z)=L$$

2. Y tres de estos segmentos forman los lados de un triángulo: $$\begin{cases}a+b>c\\b+c>a\\c+a>b\end{cases}$$

3. Y dos segmentos más forman un triángulo con al menos uno de los tres lados anteriores: $$\begin{cases}a+x>y\\a+y>x\\x+y>a\end{cases}\qquad\text{ or}\qquad\begin{cases}b+x>y\\b+y>x\\x+y>b\end{cases}\qquad\text{or}\qquad\begin{cases}c+x>y\\c+y>x\\x+y>c\end{cases}$$

4. Y el sexto y último lado z tiene que ser menor que la longitud de la "otra" diagonal del cuadrilátero formado por estos cinco lados anteriores cuando la figura (incompleta) se estira sobre un plano o superficie plana. (Uno de los tres primeros lados [ a , b , c ] es, por supuesto, la "primera" diagonal de la figura geométrica formada por las otras cuatro).

¿Es este enfoque útil ? ¿Ayuda? borrar cosas, o hacerlas más fácil ?

Answer 5

Esto no es una respuesta, sino otro comentario largo.

He intentado simplificar el problema original para ver si hay alguna posibilidad de resolver el problema con sistemas de álgebra computacional como Mathematica.

Así, ignoré la restricción no lineal procedente del determinante de Cayley-Menger, y calculé la probabilidad de que seis longitudes de arista uniformemente aleatorias e independientes satisfagan cuatro desigualdades triangulares. Para simplificar aún más las cosas, también supuse que las longitudes de las aristas estaban en orden decreciente, pero, por supuesto, esto no es una gran restricción.

Incluso con estas suposiciones Mathematica tiene problemas, pero finalmente da el resultado $19/72$ , lo que se confirma con la siguiente simulación MC:

nn = 10^7;
cnt = 0;
e = RandomReal[{0, 1}, {nn, 6}];
For[n = 1, n <= nn, n = n + 1,
   etemp = Sort[e[[n, All]]];
   If[And @@ (Abs[#[[2]] - #[[3]]] < #[[1]] < #[[2]] + #[[3]] &@
   Part[etemp, #] & /@ {{1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6}}), cnt = cnt+1];
];
p = cnt/nn // N
Sqrt[(p (1 - p))/nn]

No soy optimista respecto a que Mathematica sea capaz de manejar el problema original.