9
$\begingroup$

Three points are placed at independently and at random in a unit square. What is the expected value of the area of the triangle formed by the three points?

$\endgroup$
  • 2
    $\begingroup$ See here and here for related questions and answers. $\endgroup$ – cardinal Mar 20 '11 at 3:37
4
$\begingroup$

This isn't a full solution, but it goes most of the way there.

The area of a triangle $(x_1, y_1),(x_2,y_2),(x_3,y_3)$ is given by the formula

$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}|$

If $x_1, x_2, x_3, y_1, y_2, y_3$ are all independently identically uniformly distributed over $[0,1]$, then the average area is just given by:

$\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$

At this point, it's a fairly simple, though tedious, calculation. I recommend using Mathematica or some other computational software if you have access to it. There are also ways to simplify the computation based on inherent symmetries in the problem.

I can't post the final answer because I want to avoid giving a wrong answer, which is totally possible (I don't claim to be able to do the above integral by hand without errors). I can check the answer in Mathematica if you don't have access to it, though it will have to wait until at least Monday.

$\endgroup$
4
$\begingroup$

See here.

$\endgroup$
  • $\begingroup$ to be honest, I haven't read the answer too closely, but I'm a little surprised the argument doesn't fall victim to something like Jensen's inequality. It looks like a "mean-field" like argument to me where the expectation of a function is replaced by a function of the expectation. But, I undoubtedly haven't looked close enough. Like @Sol, I was able to "verify" the answer by Monte Carlo. $\endgroup$ – cardinal Mar 21 '11 at 13:56
  • $\begingroup$ @cardinal: The answer is correct, there's just a small error in the case distinction. The answer is based on the fact that the for fixed orientation area of the triangle is linear in each of the coordinates of the points, since it's the absolute value of a polynomial that's linear in each of the coordinates and changes sign when the orientation changes. Thus the case distinction has to be such that each case only covers triangles with the same orientation. For the case S1, the author seems to have had in mind a mapping from the rectangle formed by $A$ and $C$ to the unit square. (...) $\endgroup$ – joriki May 9 '13 at 6:57
  • $\begingroup$ (...) That may be why in "within the square one of the diagonals of which joins the 2 other points" it says "square" where it should say "rectangle", and, crucially, further down in item 2) the condition is stated as $b\lt v$ where in fact it should say that $B$ is above the diagonal $AC$. With that condition, it's OK to use linearity of expectation, since this is the condition that separates the two orientations of the triangle. $\endgroup$ – joriki May 9 '13 at 7:01
  • $\begingroup$ The linked solution is transcribed as a separate answer. $\endgroup$ – Lee David Chung Lin Mar 29 '18 at 13:04
2
$\begingroup$

User 'Shai Covo' (who seems no longer active) gave a solution as the link to an old webpage maintained by Dr. Les Reid of the math department at Missouri State University. The solution seems to be valid after being fixed by the comments @joriki, and the rigorous integration approach @achille hui supports it (and so much more).

I think the solution is nice and worthy of displaying with a good format so here it is.

The argument below is due to Philippe Fondanaiche (Paris, France), directly lifted from here.

Let $A$ with coordinates $(a,u)$, $B(b,v)$ and $C(c,w)$ be the three points chosen uniformly and at random from a unit square.

As the probability to have 2 or 3 coincident points is nil, we will consider hereafter the strict inequalities between the abscissas/coordinates of the 3 points.

There are 6 positions of the 3 abscissas having the same probability:

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

For each of them, there are 6 equally likely positions of the cordinates: $$\begin{align} u&<v<w & u&<w<v & v&<u<w \\ v&<w<u & w&<u<v & w&<v<u \end{align}$$ So there are globally 36 possible configurations having the same probability 1/36.

These 36 configurations can be split into 2 subsets $S_1$ and $S_2$ representing respectively 12 and 24 possibilities:

  • $S_1$: one of the 3 points ($B$ for example) is within the square one of the diagonals of which joins the 2 other points ($A$ and $C$ for example). In other words, $\min(a,c)< b < \max(a,c)$ and $\min(u,w)< v < \max(u,w)$.

  • $S_2$: any other of the 24 remaining configurations.

It is well known that:

  1. If $a,b,c$ on one hand and $u,v,w$ on the other hand are independent to the ones from the others, then $$\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. If $\min(a,c) < b < \max(a,c)$, $\min(u,w) < v < \max(u,w)$, and $b < v$, then the expected value of $b$ is $\frac12 + \frac13 \frac14 = \frac7{12}$ and the expected value of $v$ is $\frac12- \frac13 \frac14 = \frac5{12}$.

In these conditions, it is easy to check that the "average" position of the $\triangle ABC$ with the subset $S_1$ is the $\triangle T_1$ whose vertices are $(\frac14,\frac14),\, (\frac7{12},\frac5{12}),\, (\frac34,\frac34)$ or one of the three triangles obtained from $\triangle T_1$ by successive rotations of angle $90^\circ$. The 4 triangles are the same area equal to $\frac1{24}.

As far $S_2$ is concerned, the average position of the $\triangle ABC$ is the $\triangle T_2$ whose vertices are $(\frac14, \frac12),\, (\frac12, \frac34),\, (\frac14, \frac34)$ or one of the three triangles obtained from $\triangle T_2$ by successive rotations of angle $90^\circ$. The 4 triangles are the same area equal to $\frac3{32}$.

Therefore the expected area of the resulting triangle is equal to

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


For completeness, below is the transcription of jorki's comment correcting the error of the derivation above.

Small error in the case distinction: The answer is based on the fact that the for fixed orientation area of the triangle is linear in each of the coordinates of the points, since it's the absolute value of a polynomial that's linear in each of the coordinates and changes sign when the orientation changes. Thus the case distinction has to be such that each case only covers triangles with the same orientation. For the case $S_1$, the author seems to have had in mind a mapping from the rectangle formed by $A$ and $C$ to the unit square.

That may be why in "within the square one of the diagonals of which joins the 2 other points" it says "square" where it should say "rectangle", and, crucially, further down in item 2) the condition is stated as $b<v$ where in fact it should say that $B$ is above the diagonal $AC$. With that condition, it's OK to use linearity of expectation, since this is the condition that separates the two orientations of the triangle.

$\endgroup$
  • $\begingroup$ +1 nice to see someone who lift a link only answer to a self-contained one. $\endgroup$ – achille hui Oct 10 '17 at 12:58
1
$\begingroup$

Here's a perl script that confirms the answer Shai linked to via a Monte Carlo approach.

#!/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" ;
$\endgroup$
  • 1
    $\begingroup$ 0.5*(+/%#)(([: | [: -/ .* (3 1 \$ 1) ,.~ 3 2 \$ [: ? 6 # ])"0) 1000000#0 NB. A terse way in J ! $\endgroup$ – gar Jun 1 '14 at 12:39
1
$\begingroup$

The answer is $\frac{11}{144}$.

Following is an approach which allow one to work out the expected area of the convex hull of $n \ge 3$ random points sampled uniformly from a unit square.

Let

  • $\mu_1(\cdot)$, $\mu_2(\cdot)$ be the standard measures for 1D and 2D geometric objects.
  • $K \subset \mathbb{R}^2$ be a convex body with area $\mu_2(K) = \Delta$.
  • $p_1, p_2, \ldots, p_n$ be $n$ i.i.d random points sampled uniformly from $K$.
  • $C_n = \text{co}(p_1, \ldots, p_n)$ be the convex hull of these $n$ points.
  • $\Delta_n = \verb/E/[\mu_2(C_n)]$ be the expected area of $C_n$.

For any point $p \ne q \in \mathbb{R}^2$, let

  • $\ell_{pq}$ be the "oriented" line pointing from $p$ to $q$.
  • $H_{pq}$ be the open half space on left-hand side of line $\ell_{pq}$.
  • $L_{pq} = \mu_1(\ell_{pq} \cap K)$ be the length of those portion of $\ell_{pq}$ in $K$.
  • $A_{pq} = \mu_2(H_{pq} \cap K)$ be the area of those portion of $H_{pq}$ in $K$.

For any $p \in K \setminus \{ p_1, \ldots, p_n \}$, there are several mutually exclusive possibilities for its position relative to $C_n$.

  • Case I - $p \in C_n$,
  • Case II - $p \notin C_n$ but $p \in \ell_{p_ip_j}$ for some $1 \le i < j \le n$
  • Case III - $p \notin C_n \cup \left( \bigcup\limits_{1\le i, j\le n} \ell_{p_ip_j}\right)$

Let $E_I, E_{II}$ and $E_{III}$ be the corresponding events.

In case III, $p$ will be a vertex of a larger convex hull $\text{co}(p,p_1,\ldots,p_n) = \text{co}(p,C_n)$. If one walk along its boundary in counterclockwise direction, the next vertex will be one of $p_1, p_2,\ldots,p_n$. Let's say it is $p_k$, it is easy to see for all other $p_i$, we have $p_i \in H_{pp_k}$.

For $1 \le k \le n$, let $E_k$ be the event $$E_k \stackrel{def}{=} \verb/Event/\left[ p_i \in H_{pp_k}, \forall i \ne k, 1 \le i \le n \right] $$ It is easy to check for $1 \le i < j \le n$, we have

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

Taking expectations over the positions of $p_1, \ldots, p_n$ and notice notice $\verb/P/[ E_{II} ] = 0$, we obtain

$$\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] $$ Now replace $p$ be a random point sampled uniformly over $K$ and take expectation, one obtain following integral representation of the expected area $\Delta_n$.

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

To compute the integral, parametrize the two points $p,q$ by

$$\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} $$ This is a two to one parametrization, $(u,\theta,t_p,t_q)$ and $(-u,\theta+\pi,-t_p,-t_q)$ points to same $(p,q)$. To compensate this double counting, we will impose the constraint $t_p \le t_q$.

Under this constraint, the line $\ell_{pq}$ and half-space $H_{pq}$ becomes $$\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 \} $$ They depends only on $u$ and $\theta$. As a result, we can treat $L_{pq}$ and $A_{pq}$ as functions in $(u,\theta)$ alone. To abuse notation, we will denote them as $L(u,\theta)$ and $A(u,\theta)$ respectively.

In terms of the new variables, the volume element has the form $$dp dq = |t_p - t_q| du d\theta dt_p dt_q$$

Integrate over $t_p, t_q$ gives us a factor $$\frac{L(u,\theta)^3}{6} = \frac{L(u,\theta)^2}{6}\frac{\partial}{\partial u}A(u,\theta)$$

Change variable to $(\lambda,\theta)$ where $\displaystyle\;\lambda = \frac{A(u,\theta)}{\Delta}$ and let $m(\lambda,\theta)$ be corresponding value of $\frac{L^2(u,\theta)}{\Delta}$, above integral representation becomes

$$\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 $$ Let's back to our original problem where $K$ is the unit square $[0,1]^2$ and $\Delta = 1$.
By symmetry, we only need to figure out what is $m(\lambda,\theta)$ when $\theta \in [0,\frac{\pi}{4}]$.
For $\theta \in [0,\frac{\pi}{4}]$, let $s = \sin\theta, c = \cos\theta, t = \tan\theta$, it is not hard to work out

$$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} $$ Integrate over $\theta$ first, we get

$$\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} $$ Split the integral to two, one over $[0,\frac12]$ and the other over $[\frac12,1]$. Change variable to $z = 2\lambda$ or $2(1-\lambda)$ depends which intervals we are one, we obtain: $$\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 $$ Integrate by part twice, this leads to $$ \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} $$

Throwing last expression to a CAS, we get:

$$( \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) $$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.