área esperada de un triángulo determinada por puntos colocados al azar

Question

Se colocan tres puntos de forma independiente y aleatoria en un cuadrado unitario. ¿Cuál es el valor esperado del área del triángulo formado por los tres puntos?

Answer 1

Esto no es una solución completa, pero va casi todo el camino.

El área de un triángulo $(x_1, y_1),(x_2,y_2),(x_3,y_3)$ viene dada por la fórmula

$A(x_1,x_2,x_3,y_1,y_2,y_3)= | \frac{x_1(y_2-y_3) + x_2 (y_3-y_1) + x_3 (y_1-y_2)}{2}|$

Si $x_1, x_2, x_3, y_1, y_2, y_3$ están distribuidos uniformemente de forma independiente e idéntica sobre $[0,1]$ , entonces el área media viene dada simplemente por:

$\int_0^1 \int_0^1 \int_0^1 \int_0^1 \int_0^1 \int_0^1 A(x_1,x_2,x_3,y_1,y_2,y_3) d x_1 d x_2 d x_3 d y_1 d y_2 d y_3$

En este punto, es un cálculo bastante sencillo, aunque tedioso. Te recomiendo que utilices Mathematica o algún otro software de cálculo si tienes acceso a él. También hay formas de simplificar el cálculo basándose en las simetrías inherentes al problema.

No puedo publicar la respuesta final porque quiero evitar dar una respuesta errónea, que es totalmente posible (no pretendo ser capaz de hacer la integral anterior a mano sin errores). Puedo comprobar la respuesta en Mathematica si no tiene acceso a él, aunque tendrá que esperar al menos hasta el lunes.

Answer 2

Ver aquí .

Answer 3

Usuario 'Shai Covo' (que parece que ya no está activo) dio una solución como el enlace a una antigua página web mantenida por el Dr. Les Reid del departamento de matemáticas de la Universidad Estatal de Missouri. La solución parece ser válida después de haber sido arreglada por el comentarios @joriki y el riguroso enfoque de integración que apoya @achille hui (y mucho más).

Creo que la solución es bonita y digna de ser expuesta con un buen formato así que aquí está.

El argumento que sigue se debe a Philippe Fondanaiche (París, Francia), directamente sacado de aquí .

Dejemos que $A$ con coordenadas $(a,u)$ , $B(b,v)$ y $C(c,w)$ sean los tres puntos elegidos uniformemente y al azar de un cuadrado unitario.

Como la probabilidad de tener 2 o 3 puntos coincidentes es nula, consideraremos consideraremos en adelante las desigualdades estrictas entre las abscisas/coordenadas de los 3 puntos.

Hay 6 posiciones de las 3 abscisas que tienen la misma probabilidad:

$$\begin{align} a&<b<c & a&<c<b & b&<a<c \\ b&<c<a & c&<a<b & c&<b<a \end{align}$$

Para cada una de ellas, hay 6 posiciones igualmente probables de las coordenadas: $$\begin{align} u&<v<w & u&<w<v & v&<u<w \\ v&<w<u & w&<u<v & w&<v<u \end{align}$$ Así que hay globalmente 36 configuraciones posibles que tienen la misma probabilidad 1/36.

Estas 36 configuraciones pueden dividirse en 2 subconjuntos $S_1$ y $S_2$ que representan respectivamente 12 y 24 posibilidades:

• $S_1$ Uno de los 3 puntos ( $B$ por ejemplo) está dentro del cuadrado una de cuyas diagonales une los otros 2 puntos ( $A$ y $C$ por ejemplo). En otras palabras, $\min(a,c)< b < \max(a,c)$ y $\min(u,w)< v < \max(u,w)$ .

• $S_2$ Cualquier otra de las 24 configuraciones restantes.

Es bien sabido que:

1. Si $a,b,c$ por un lado y $u,v,w$ por otro lado son independientes a las de los demás, entonces $$\begin{align} \min(a,b,c) &= \min(u,v,w) = \frac14 \\ \max(a,b,c) &= \max(u,v,w) = \frac34 \\ \text{med}(a,b,c) &= \text{med}(u,v,w) = \frac12 \end{align}$$
2. Si $\min(a,c) < b < \max(a,c)$ , $\min(u,w) < v < \max(u,w)$ y $b < v$ entonces el valor esperado de $b$ es $\frac12 + \frac13 \frac14 = \frac7{12}$ y el valor esperado de $v$ es $\frac12- \frac13 \frac14 = \frac5{12}$ .

En estas condiciones, es fácil comprobar que la posición "media" de el $\triangle ABC$ con el subconjunto $S_1$ es el $\triangle T_1$ cuyos vértices son $(\frac14,\frac14),\, (\frac7{12},\frac5{12}),\, (\frac34,\frac34)$ o uno de los tres triángulos obtenidos de $\triangle T_1$ por rotaciones sucesivas del ángulo $90^\circ$ . Los 4 triángulos tienen la misma área igual a $ \frac1 {24}.

En cuanto a $S_2$ se refiere, la posición media del $\triangle ABC$ es el $\triangle T_2$ cuyos vértices son $(\frac14, \frac12),\, (\frac12, \frac34),\, (\frac14, \frac34)$ o uno de los tres triángulos obtenidos de $\triangle T_2$ por rotaciones sucesivas del ángulo $90^\circ$ . Los 4 triángulos tienen la misma área igual a $\frac3{32}$ .

Por lo tanto, el área esperada del triángulo resultante es igual a

$$ \frac{12}{36} \frac1{24} + \frac{24}{36} \frac3{32} = \frac{11}{144}$$

---

Para completar, a continuación se transcribe el comentario de jorki corrigiendo el error de la derivación anterior.

Pequeño error en la distinción de casos: La respuesta se basa en que el para la orientación fija El área del triángulo es lineal en cada una de las coordenadas de los puntos, ya que es el valor absoluto de un polinomio que es lineal en cada una de las coordenadas y cambia de signo cuando cambia la orientación. Por lo tanto, la distinción de casos tiene que ser tal que cada caso sólo cubra triángulos con la misma orientación. Para el caso $S_1$ el autor parece haber tenido en mente un mapeo desde el rectángulo formado por $A$ y $C$ al cuadrado de la unidad.

Puede ser por eso que en "dentro del cuadrado una de cuyas diagonales une los otros 2 puntos" dice "cuadrado" donde debería decir "rectángulo", y, crucialmente, más abajo en el punto 2) la condición se establece como $b<v$ donde en realidad debería decir que $B$ está por encima de la diagonal $AC$ . Con esa condición, está bien utilizar la linealidad de la expectativa, ya que es la condición que separa las dos orientaciones del triángulo.

Answer 4

La respuesta es $\frac{11}{144}$ .

A continuación se presenta un enfoque que permite calcular el área esperada del casco convexo de $n \ge 3$ puntos aleatorios muestreados uniformemente en un cuadrado unitario.

Dejemos que

• $\mu_1(\cdot)$ , $\mu_2(\cdot)$ sean las medidas estándar de los objetos geométricos 1D y 2D.
• $K \subset \mathbb{R}^2$ sea un cuerpo convexo con área $\mu_2(K) = \Delta$ .
• $p_1, p_2, \ldots, p_n$ sea $n$ puntos aleatorios i.i.d muestreados uniformemente de $K$ .
• $C_n = \text{co}(p_1, \ldots, p_n)$ sea el casco convexo de estos $n$ puntos.
• $\Delta_n = \verb/E/[\mu_2(C_n)]$ sea el área esperada de $C_n$ .

Para cualquier punto $p \ne q \in \mathbb{R}^2$ , dejemos que

• $\ell_{pq}$ sea la línea "orientada" que apunta desde $p$ a $q$ .
• $H_{pq}$ sea el semiespacio abierto en el lado izquierdo de la línea $\ell_{pq}$ .
• $L_{pq} = \mu_1(\ell_{pq} \cap K)$ sea la longitud de esa porción de $\ell_{pq}$ en $K$ .
• $A_{pq} = \mu_2(H_{pq} \cap K)$ sea el área de esa porción de $H_{pq}$ en $K$ .

Para cualquier $p \in K \setminus \{ p_1, \ldots, p_n \}$ Hay varias posibilidades mutuamente excluyentes para su posición en relación con $C_n$ .

• Caso I - $p \in C_n$ ,
• Caso II - $p \notin C_n$ pero $p \in \ell_{p_ip_j}$ para algunos $1 \le i < j \le n$
• Caso III - $p \notin C_n \cup \left( \bigcup\limits_{1\le i, j\le n} \ell_{p_ip_j}\right)$

Dejemos que $E_I, E_{II}$ y $E_{III}$ sean los eventos correspondientes.

En el caso III, $p$ será un vértice de un casco convexo mayor $\text{co}(p,p_1,\ldots,p_n) = \text{co}(p,C_n)$ . Si se recorre su frontera en sentido contrario a las agujas del reloj, el siguiente vértice será uno de $p_1, p_2,\ldots,p_n$ . Digamos que es $p_k$ es fácil de ver para todos los demás $p_i$ tenemos $p_i \in H_{pp_k}$ .

Para $1 \le k \le n$ , dejemos que $E_k$ sea el evento $$E_k \stackrel{def}{=} \verb/Event/\left[ p_i \in H_{pp_k}, \forall i \ne k, 1 \le i \le n \right] $$ Es fácil comprobar si hay $1 \le i < j \le n$ tenemos

$$E_I \cap E_i = E_I \cap E_j = E_{III} \cap { E_i \cap E_j } = \emptyset$$

Tomando las expectativas sobre las posiciones de $p_1, \ldots, p_n$ y aviso aviso $\verb/P/[ E_{II} ] = 0$ obtenemos

$$\verb/E/[ p \in C_n ] = 1 - \sum_{k=1}^n \verb/E/[ E_{III} \cap E_k ] = 1 - n\verb/E/[ E_{III} \cap E_1 ] = 1 - n \verb/E/\left[ \left(\frac{A_{pp_1}}{\Delta}\right)^{n-1} \right] $$ Ahora reemplaza $p$ sea un punto aleatorio muestreado uniformemente sobre $K$ y tomar la expectativa, se obtiene la siguiente representación integral del área esperada $\Delta_n$ .

$$\frac{\Delta_n}{\Delta} = 1 - \frac{n}{\Delta^2}\int_K\int_K \left(\frac{A_{pq}}{\Delta}\right)^{n-1} dpdq$$

Para calcular la integral, parametriza los dos puntos $p,q$ por

$$\mathbb{R} \times [0,2\pi) \times \mathbb{R}^2 \ni (u,\theta,t_p,t_q) \quad\mapsto\quad \begin{cases} p &= u(\cos\theta,\sin\theta) + t_p ( -\sin\theta,\cos\theta)\\ q &= u(\cos\theta,\sin\theta) + t_q ( -\sin\theta,\cos\theta) \end{cases} $$ Se trata de una parametrización de dos a uno, $(u,\theta,t_p,t_q)$ y $(-u,\theta+\pi,-t_p,-t_q)$ señala lo mismo $(p,q)$ . Para compensar esta doble contabilidad impondremos la restricción $t_p \le t_q$ .

Bajo esta restricción, la línea $\ell_{pq}$ y medio espacio $H_{pq}$ se convierte en $$\ell_{pq} = \{ (x,y) : x\cos\theta + y\sin\theta = u \} \quad\text{ and }\quad H_{pq} = \{ (x,y) : x\cos\theta + y\sin\theta < u \} $$ Sólo dependen de $u$ y $\theta$ . Como resultado, podemos tratar $L_{pq}$ y $A_{pq}$ como funciones en $(u,\theta)$ solo. Para abusar de la notación, denotaremos como $L(u,\theta)$ y $A(u,\theta)$ respectivamente.

En términos de las nuevas variables, el elemento de volumen tiene la forma $$dp dq = |t_p - t_q| du d\theta dt_p dt_q$$

Integrar sobre $t_p, t_q$ nos da un factor $$\frac{L(u,\theta)^3}{6} = \frac{L(u,\theta)^2}{6}\frac{\partial}{\partial u}A(u,\theta)$$

Cambiar la variable a $(\lambda,\theta)$ donde $\displaystyle\;\lambda = \frac{A(u,\theta)}{\Delta}$ y que $m(\lambda,\theta)$ sea el valor correspondiente de $\frac{L^2(u,\theta)}{\Delta}$ La representación integral anterior se convierte en

$$\frac{\Delta_n}{\Delta} = 1 - \frac{n}{6} \int_{0}^{2\pi} \int_0^1 \lambda^{n-1} m(\lambda,\theta) d\lambda d\theta $$ Volvamos a nuestro problema original en el que $K$ es el cuadrado de la unidad $[0,1]^2$ y $\Delta = 1$ .
Por simetría, sólo tenemos que averiguar qué es $m(\lambda,\theta)$ cuando $\theta \in [0,\frac{\pi}{4}]$ .
Para $\theta \in [0,\frac{\pi}{4}]$ , dejemos que $s = \sin\theta, c = \cos\theta, t = \tan\theta$ no es difícil de calcular

$$L(u,\theta) = \begin{cases} \frac{u}{cs}, & u \in [0,s],\\ \frac{1}{c}, & u \in [s,c],\\ \frac{s+c-u}{cs}, & u \in [c,c+s],\\ 0, &\text{ otherwise } \end{cases} \quad\implies\quad m(\lambda,\theta) = \frac{1}{c^2} \begin{cases} \frac{2\lambda}{t}, & \lambda \in [0,\frac{t}{2}],\\ 1, & \lambda \in [\frac{t}{2},1-\frac{t}{2}],\\ \frac{2(1-\lambda)}{t}, &\lambda \in [1-\frac{t}{2},1] \end{cases} $$ Integrar sobre $\theta$ primero, obtenemos

$$\begin{align} \int_0^{2\pi} m(\lambda,\theta) d\theta &= 8\int_0^{\pi/2} m(\lambda,\theta) d\theta = 8\int_0^1 \min\left\{ \frac{2\lambda}{t}, 1, \frac{2(1-\lambda)}{t} \right\} dt\\ &= 8 \begin{cases} 2\lambda(1-\log(2\lambda)),& \lambda \in [0,\frac12]\\ 2(1-\lambda)(1-\log(2(1-\lambda)), & \lambda \in [\frac12, 1] \end{cases} \end{align} $$ Dividir la integral en dos, una sobre $[0,\frac12]$ y el otro sobre $[\frac12,1]$ . Cambiar la variable a $z = 2\lambda$ o $2(1-\lambda)$ depende de qué intervalos somos, obtenemos: $$\Delta_n = 1 - \frac{2n}{3}\int_0^1 z(1-\log z)\left[\left(\frac{z}{2}\right)^{n-1} + \left(1-\frac{z}{2}\right)^{n-1}\right] dz $$ Integrar por parte dos veces, esto lleva a $$ \begin{align} \Delta_n &= 1 - \frac{4}{3} \int_0^1 \log z \left(\left(\frac{z}{2}\right)^n -\left(1-\frac{z}{2}\right)^n\right) dz \\ &= 1 - \frac{8}{3(n+1)}\int_0^1 \frac{1}{z}\left[1 - \left(1-\frac{z}{2}\right)^{n+1} - \left(\frac{z}{2}\right)^{n+1} \right] dz\\ &= 1 - \frac{8}{3(n+1)}\int_0^1 \left[\frac12\left(\sum_{k=0}^n\left(1-\frac{z}{2}\right)^k\right) - \frac{z^n}{2^{n+1}} \right] dz\\ &= 1 - \frac{8}{3(n+1)} \left[ \sum_{k=1}^{n+1} \frac{1}{k} \left(1 - \frac{1}{2^k}\right) - \frac{1}{(n+1)2^{n+1}} \right] \end{align} $$

Lanzando la última expresión a un CAS, obtenemos:

$$( \Delta_3, \Delta_4, \ldots ) = \left( \frac{11}{144}, \frac{11}{72}, \frac{79}{360}, \frac{199}{720}, \frac{104873}{322560}, \frac{29609}{80640}, \frac{976837}{2419200}, \frac{13183}{30240},\ldots \right) $$

Answer 5

Aquí hay un perl script que confirma la respuesta que Shai enlazó a través de un enfoque de Monte Carlo.

#!/usr/bin/perl -w

$numTrials = 1000000 ;

sub distance {
   my $point1 = $_[0] ;
   my $point2 = $_[1] ;
   return sqrt(($x[$point1]-$x[$point2])**2 + ($y[$point1]-$y[$point2])**2) ;
}

sub heron {
   my $a = $legLength[$_[0]] ;
   my $b = $legLength[$_[1]] ;
   my $c = $legLength[$_[2]] ;
   my $s = ( $a + $b + $c ) / 2 ;
   return sqrt( $s * ( $s - $a ) * ( $s - $b ) * ( $s - $c ) ) ;
}

sub doAtriangle() {
   for ( my $j = 0; $j <= 2 ; $j++ ) {
      $x[$j] = rand(1) ;
      $y[$j] = rand(1) ;
   }   
   $legLength[0] = distance(0,1) ;
   $legLength[1] = distance(1,2) ;
   $legLength[2] = distance(2,0) ;
   return heron(0,1,2) ;   
}

for ( $i = 0 ; $i < $numTrials ; $i++ ) {
   $sum += doAtriangle() ;
}

print $sum/$numTrials . "\n" ;