Average Distance between random points

[Swammerdami]

Here's a completely different problem which may appeal to those who like this thread.

Given a parallelogram of unit area, choose three points (with independent uniform distributions) in its interior. What is the expected area of the triangle formed by the three points?

Given the way I've phrased the problem, the shape of the parallelogram shouldn't matter: you might as well assume it's a square. But proving that the shape doesn't matter should remind you of the simplifications available with affine transforms and other linearities, and propel you toward solution (d) below.

There are four ways to approach this problem.
(a) Set up a sextuple integral and presumably let Wolfram solve it. Ugh!! You wouldn't ask Wolfram to smell the roses for you, would you?
(b) Monte Carlo simulation. The answer is a simple rational number; save your PRNG for more pressing work.
(c) Google search. This problem is slightly famous; an answer is shown on Wolfram's own site. Tell us how you found it with Google; my search skills are quite poor.
(d) Use paper, pencil and brain. Fun!! You might end up doing 1 or 2 very trivial integrations, but I think you can avoid even those with simple arguments.

Enjoy?

 

[lpetrich]

For a parallelogram with width w, height h, and tilt t, the points inside can be given by

(w*x, t*x + h*y)

where x and y are independently uniformly distributed between 0 and 1. The shape's corners are given by both being 0 or 1 independently.

There is a simple formula for the area of a polygon in terms of its vertices' coordinates in a rectangular system: the shoelace formula.
\(A = \frac12 \sum_i (x_i y_{i+1} - x_{i+1} y_i) \)

for coordinates (x,y) and with the indexing of them wrapping around.

An interesting feature of this formula is that it can give negative area. If one reverses the order of the points, the area's sign will be reversed.

That will be a big problem if one does this problem naively, because this reversal will make the average area equal to zero.

That result is true for points drawn from *any* distribution, as long as they are independently drawn from it.

 

[lpetrich]

A parallelogram with width, height, tilt, (w,h,t) is equivalent to one with
\( w \to \sqrt{h^2+t^2} \\ h \to w h \sqrt{h^2+t^2} \\ t \to w t /\sqrt{h^2+t^2} \)

One can show that equivalence by rotating a parallelogram with vertices {{0,0},{w,0},{t,h},{w+t,h}} with this rotation matrix:
\( \frac{1}{\sqrt{h^2+t^2}} \begin{pmatrix} t & h \\ h & -t \end{pmatrix} \)

I verified that this operation undoes itself, as negation does -- it is an involution.

The parallelogram's area is w*h, and it is unchanged by this transform, as one might expect.


I then calculated the mean of the square of the triangle area. It is
\( \frac{(w h)^2}{96} \)

 

[Swammerdami]

I must have been in a funny mood when I posted #21, which is NOT an easy problem. I DO think it is a very "nifty" problem: it can be solved via "divide and conquer", and the exploitation of the very nice properties of affine transforms. To leave the JOY of discovery for anyone who wants to tackle it, I'll keep the following hints general.

Using the WIKI tag to point to "Affine transform" would be a logical starting point, but that article babbles on and on with lots of equations and fancy symbols. I'd be intimidated by the article if I didn't already know what an affine transform is, how simple they are, and how elegant their properties are. An affine transform simply applies the same linear operator to every point in a source image; these have useful intuitive properties. For example, if an affine transform preserves ANY area, then it preserves EVERY area!
For 2-D images such a transform has six degrees of freedom:
. . . x' = P₁ x + P₂ y + P₃
. . . y' = P₄ y + P₅ x + P₆
The six degrees of freedom can be broken down as translation (2), horizontal scaling (1), vertical scaling (1), rotation (1) and shear (1). (The equations would have to be reorganized and made slightly more complicated to map the six P_i one-to-one to the six intuitive freedoms.) Clearly rotation and translation have no effect on the area of an object, and the scaling terms just scale the area. Shear is the only operator that might seem troublesome, but if you wish you can get rid of the shears altogether! by doing successive shear-free affine transforms: Rotate -> Horiz_scale -> Rotate back produces a Shear!

The problem in #21 is:
What is the expected area of the triangle (x1, y1) — (x2, y2) — (x3,y3) where 0 ≤ x1,x2,x3,y1,y2,y3 ≤ 1 are six random i.u.d variables?

Without loss of generality, suppose that m=x1 is the largest among (x1,x2,x3) and denote the triangle's expected area as G(m). What is the relationship between G(1) and G(m)? With further thought the problem with six random variables becomes a problem with only five.

Instead of a problem about six random variables, what if there were only two?
What is the expected area of the (0,0) — (1,1) — (x3,y3) triangle? How about (0,0) — (x2,1) — (1,y3)?

 

[Swammerdami]

It may have been inappropriate for me to post this puzzle about a triangle's area but having gone this far, I will want to post a solution. The approach which exploits the simplicity of affine transforms is just too gorgeous -- and too instructive -- to pass up.

But I know that people like to let puzzles like this sit in their subconscious for a few days. If any of you is still cogitating and hoping to get a solution, post a message here! I do not want my Spoiler to rob you of the thrill of discovery!

I will offer some minor hints:

Instead of a problem about six random variables, what if there were only two?
What is the expected area of the (0,0) — (1,1) — (x3,y3) triangle? How about (0,0) — (x2,1) — (1,y3)?

In the (0,0) — (1,1) — (x,y) triangle, (x,y) is an interior point in a larger (0,0) — (1,1) — (0,1) triangle. But, due to the marvelous properties of affine transforms, the expected ratio between the areas of large and small triangles is a constant that doesn't depend on the large triangle's shape! (Any two triangles are equivalent under some affine transform.) Therefore you can make the large triangle equilateral. The interior point will divide that equilateral triangle into three triangular pieces. Where do you go from there?

The (0,0) — (x,1) — (1,y) triangle is one piece of a (0,0) - (0,1) - (1,1) - (1,0) square. The other three pieces are right triangles, each with its own expected area. The sum of the four expected areas must be 1.

 

[Swammerdami]

Choose three random points in the interior of a parallelogram of unit area. What is the expected area (A) of the triangle they form?

Affine transforms preserve the ratios of areas; this fact will be used repeatedly throughout the proof. Immediately see that we can take the parallelogram to be a square; and the three points to be described by (x_i, y_i) coordinates with 0 ≤ x_i, y_i ≤ 1.

Let m be the largest of the x_i and G(m) be the expected area, for that case, of the triangle we seek. A uniform random distribution remains uniform random under affine transform, so the m-by-1 bounding rectangle is affinely equivalent to a 1-by-1 square, and G(m) = m·G(1). Exp[A] = Exp[G(m)] = Exp[m·G(1)] = Exp[m]·G(1). In other words, we can solve our original problem for the case where one coordinate is fixed at 1; and then multiply by Exp[m] to solve our original problem.

The expected value of the r'th smallest among n uniform variates on the unit segment is (r / (n+1)) — this can be shown with an argument based on affine transforms! — so m = 3/4 is the expected value of m. Exp[A] = (3/4)·G(1).

Using similar reasoning, Exp[A] = (2/3)·(3/4)·H = (1/2)·H where H is the expected area when one x is constrained to be 1, and another x constrained to be 0. And Exp[A] = (1/2)·(1/2)·J where J is the expected area when one x and one y are each constrained to be 1, and one x and one y are each constrained to be 0. Six degrees of freedom have been reduced to two!

There are two cases for the arrangement in J:
(a) the three points are (0,0), (x,1), (1,y) — this will arise 2/3 of the time.
(b) the three points are (0,0), (x,y), (1,1) — this will arise 1/3 of the time.

In case (a) the square is partitioned into four triangles: 3 simple right triangles (T₁, T₂, T₃) and our target J. Since the areas T₁ + T₂ + T₃ + J = 1, the four expected areas must also sum to 1. The expected areas of the three trivial right triangles are 1/4, 1/4 and 1/8 — this is easily seen by considering affine transforms! — so the expected area J is 3/8.

In case (b), assume x+y ≤ 1 wlog. and we have an enclosing triangle with area 1/2 and a random interior point. By affine transform we may make the enclosing triangle equilateral; the interior point forms three triangles with the enclosing vertices and by symmetry those triangles will have the same expected area, so that area must be 1/3 of 1/2, i.e. 1/6.

Case (a) contributes (2/3)·(3/8) to the expected area of J; case (b) contributes (1/3)·(1/6). So J = (2/3)·(3/8) + (1/3)·(1/6) = (11/36).

Above we showed Exp[A] = (1/2)·(1/2)·J so (11/144) is the solution to the original puzzle.

Will anyone deny that this is more beautiful than subjecting Heron's complicated formula to a sextuple integral?

 

[lpetrich]

I agree that Heron's formula is a mathematical nightmare in this problem. One has to do coordinates -> side lengths -> Heron's formula. But I tried doing it in general for points in rectangular coordinates, and I got the shoelace formula.  Heron's formula -  Shoelace formula - the Wikipedia article on the latter does the absolute value, when I've omitted it because the sign of its area because it tells us whether the points are in clockwise or counterclockwise order.

Using x for the 2-coordinates, the shoelace formula may be expressed as
\( A = \frac12 \sum_i x_i \cdot \epsilon \cdot x_{i+1} \)

Applying translations a: x -> x + a, it is easy to show that the area is invariant under them. Applying homogeneous linear transform T: x -> T.x we find
\( A = \frac12 \sum_i x_i \cdot T^T \cdot \epsilon \cdot T \cdot x_{i+1} \)

One can show that
\( T^T \cdot \epsilon \cdot T = \epsilon \cdot \det T \)

So A -> det(T)*A

For rotation, A is unchanged, while for reflection, A reverses sign. Scaling by s scales A by s^2.

One can also do sum-to-integral with the shoelace formula to get a general formula for the area integral (reverting to (x,y) for the points):
\( A = \frac12 \oint ( x \, dy - y \, dx ) = \frac12 \oint \left( x \frac{dy}{dt} - y \frac{dx}{dt} \right) dt \)

The integral is done over the curve, thus the circle in the integral sign. The t is some parameter if one has x and y as functions of it.