From: T.Moore@massey.ac.nz (Terry Moore)
Newsgroups: sci.math
Subject: Re: Random Triangle Problem (LONG summary)
Date: Fri, 08 Aug 1997 14:06:34 +1200
This is rather long because I have summarised some
of the high points of the discussion as well as
filling in the proof for the normal case. If you
are only interested in this case, you can skip to
the end, pausing to look at uniform angles on the
way.
There are two kinds of mathematician.
Those with insight sometimes end up producing
proofs that Paul Erdos would have said are "from
the book", but they can easily make mistakes because
insight is based on intuition and experience, and
one will often have the former before one acquires the
latter. Then there are the plodders who sometimes get
the right answer in the end from long winded
calculations, but have no insight. (That seems
to fit one correspondent in this discussion, but
I'm not saying who. It is sufficient to say that he
hasn't got the right answer yet). You'll see a bit of
plodding and a bit of insight below, I think.
Bill Taylor quite rightly pointed out that the
probability that a random triangle has an obtuse
angle depends upon what is meant by "a random
triangle". If you ask someone to draw a random
triangle, I have a hunch that you will usually
get an acute angled triangle. On the other hand,
people are notoriously bad at judging randomness,
so this is not a good way to decide what a random
triangle is.
While I agree that randomly and independently choosing
the angles of the sides to a fixed direction gives a
reasonable definition, I want to explore other
definitions. Robert Hill has done 1 million simulations
for several possible definitions, and I have repeated
the experiment with 10 million trials. Based on the
binomial distribution, this gives 3 digit accuracy with
almost certainty, but the 4th digit is unreliable. To
get the 4th digit requires 1000 million trials.
Keith Ramsay has drawn our attention to an American
Mathematical Monthly article which has discussed this
question and looked at several distributions for the
vertices. That's a pity as I was thinking this topic
would make a nice Monthly article (jointly with those
who have made substantial contributions and
acknowledging others, of course). One case they
cosidered is when the vertices are independently uniformly
distributed over an n-sphere. It looks to me as though this
should still lead to the probability 3/4 for an obtuse angled
triangle.
The three vertices determine a plane and that plane
intersects the sphere in a circle. Given the plane, the
vertices are uniform over the circle and Ilias Kastanas
has shown (see below) that this leads to the 3/4 answer.
As this is the same for all planes, that is the
answer unconditionally too. Similarly, a uniform
distribution over the inside of the sphere should
lead to the same answer as for a uniform distribution
over the inside of a circle. This seems to contradict
the article, so what is wrong with this reasoning?
I would appreciate any explanation of this.
I will summarise what has been done by other posters
as well as adding some results of my own.
First, a random triangle should have a random
orientation, but, as the orientation has no effect
on the shape, I will also try definitions in which
this requirement is dropped. However, I must insist
on exchangeability of edges and vertices, that is, the
distributions of edge lengths are identical; and so
are the joint distributions of lengths of pairs of
edges. Similarly for angles. Without exchangeability
the angles would be distinguishable in some way
other than by their size. This could occur if the
angles or vertices were chosen sequentially from
different distributions, but this would not lead to
a random triangle by most people's standards. Tony
Richards is the only exception I know of.
I looked at three classes of distribution:
defining a triangle (up to similarity) by its angles,
defining it by its edge lengths,
and defining it by the coordinates of the vertices.
For each class I considered several distributions.
As angles are bounded, it would make sense to use a
uniform distribution, except that the sum of the
angles is pi. This constraint makes independence
impossible because, if one is greater than pi/2,
the others must be less than pi/2. But we can make
the angles of the three sides to a given fixed line
uniformly and independently distributed. This was
essentially Bill Taylor's solution (he chose the
sides perpendicular to three lines drawn at
random angles).
For angles, the uniform distribution is attractive
as, among all distributions on a bounded range, the
uniform distribution has maximum entropy, where
entropy is defined to be Shannon's information, the
expected value of the log of the density. When
I consider lengths of sides or the coordinates
of the vertices, bounded distributions are no
longer appropriate. Instead I shall fix the
standard deviation. This chooses a scale factor
but does not affect the shape. For the sides, the
distribution is unbounded above, and the maximum
entropy distribution is exponential. For the
coordinates of vertices, the distribution is
unbounded above and below and the maximum entropy
distribution is normal.
However, not too much should be made of this as
the maximum entropy property is not invariant to
transformations. But then, nor is any definition
of randomness and this is precisely why this
question is ill-posed.
Ilias Kastanas has given an interesting proof that
the probability of an obtuse angle is 3/4 if the
vertices are distributed independently and
uniformly on a circle. Let the vertices be A, B
and C. The triangle is obtuse angled if all the
vertices are on the same semicircle. In that case
there are 3 mutually exclusive events depending
whether A, B or C is in the middle. Given the
point A, the 3 are on the same semicircle with
B in the middle if B and C are on one of the two
semicircles with A at the end (probability = 1/2)
and with B between A and C (probability = 1/2 by
exchangeability). As these events are independent,
the probability that B is between A and C, given
A, is 1/4. This is independent of A so the result
follows.
Suppose the edges are at random uniform angles.
Using Bill's idea, translating an edge has no
effect on the shape of the triangle (unless the
triangle becomes degenerate), so we could
translate them so they touch a circle of radius 1
(on either side). The points of contact would then
be uniformly distributed around the circle and
could be described by angles between 0 and 2pi.
The circle could be either an incircle of the
triangle or an escribed circle. In the latter
case, translating _one_ of the three sides to the
opposite side of the circle makes the circle into
an inscribed one, while, in the former case,
translating _any_ side to the opposite side of the
circle makes the circle an escribed one. By Ilias's
argument for the circumcircle, the probability
that this gives an incircle is 1/4. (I think
Charles Giffen was the first to point out in
this thread that the circle is not always an
incircle).
Because of complication about whether the
circle is an incircle or not, I will work with
the angles of the sides to a fixed direction
instead. We can describe these as independently
uniform between 0 and pi. The joint distribution
is uniform on a cube with sides from 0 to pi.
That is the density is 1/pi^3. The joint
distribution of the order statistics, U, V, W,
has density 6/pi^3 with 0 < U < V < W < pi. That
is they are uniform over a certain tetrahedron.
The joint density of U, A = V-U and B = W-V,
where U defines the orientation and the A and B
are two interior angles of the triangle, is
6/pi^3 with 0 < U + A + B < pi, U > 0, A > 0, B > 0.
So the marginal density of A and B is
6(pi-A-B)/pi^3 with 0 < A + B < pi, A > 0, B > 0.
The marginal density of A is then 3(pi - A)^2 /pi^3,
0 < A < pi, and the probability that A > pi/2 is
1/8. Similarly, the probability that B > pi/2 is
1/8. Now here comes a surprise. The probability that
the third angle, C, is greater than pi/2 is the
probability that A + B is less than pi/2. This is
not 1/8 but 1/2 as you can show by direct integration.
This gives the required result. Why the asymmetry?
It was implicit in sorting the angles in order of
size. Angle C is supplementary to the difference
between the greatest and least of the three angles
to a fixed line, and this introduces the asymmetry.
This argument is not as neat as Bill's but it's
good old fashioned straightforward analysis.
To restore the symmetry we have to think about
permuting the vertices. The joint density of A
and C is 6C/pi^3, 0 < A + C < pi, A > 0, C > 0
because A and B gives identical information to A
and C and the transformation is linear (Jacobian = 1).
As all permuations of the vertices are equally
likely, we want an equally weighted mixture of
the 6 densities obtained by interchanging A, B and
C. I.e. (2(pi-A-B) + 2A + 2B)/pi^3 = 2/pi^2 and
The joint density of A and B is uniform over the
the region 0 < A + B < pi, A > 0, B > 0.
This gives a much easier way to get the result.
It might be possible to preserve the symmetry
throughout the argument. But, anyway, note that
the marginal distribution for any angle is
triangular. That is why each angle has less than
an equal chance of being obtuse. By integrating the
triangular distribution directy, it is easy to see
tha the probability os 1/4 for the obtuseness of
each vertex.
One can represent a set of variables with constrained
sum using homogeneous coordinates. For three
variables, represent the point as a point in a
cube. This may not satisfy the constraint so we
project this point onto the plane containing three
vertices that does satisfy the constraint. The
part of this plane in the unit cube is an equilateral
triangle and the coordinates are proportional to the
distances of the point from its edges. This is
essentially the coodinate system above, except that
the triangle has been distorted. (In fact, the projection
of the triangle on each coordinate plane gives the
coordinate system above for each pair of vertices).
Our constraint is that the sum of the angles is pi, and
we see that we have captured the idea of a constrained
uniform distribution very well. The marginals are
triangular when there is a constraint.
One answer to the meaning of a random triangle is
therefore that the angles are uniform when expressed
in homogeneous coordinates. In other words we choose
random uniform angles from 0 to pi and then scale them
so that the sum is pi.
We could also choose the side lengths at random.
As a scale factor doesn't affect the shape of the
triangle, we can condition on any given perimeter.
Whatever the distribution of the perimeter, we will
get the same probability of an obtuse angle if,
given the perimeter, the event "triangle is obtuse" is
independent of the distribution of the perimeter. Then
it is sensible to make the conditional distributions
of the side lengths uniform subject to the constraint
on the sum and subject to the triangle inequality.
This suggests using homogenous coordinates (which was
first proposed by a correspondent from the Netherlands,
I forget who) and then rejecting "triangles" which don't
satisfy the triangle inequality. This means choosing a point
uniformly in an equilateral triangle of height 1 and
returning the homogeneous coordinates if the point is in
the middle triangle in the partition of the triangle into four.
This is equivalent to choosing uniformly in a triangle 1/2
the size, and returning 1/2 - the usual coordinates.
A simulation of this gave a probability for obtuse
triangles of 0.682.
However, the definition of a random triangle ought to be
generalisable to random polygons. While basing the
definition on angles or sides defines classes of similar
triangles, it doesn't define classes of similar polygons.
However, if we are only interested in properties of the
angles of polygons, the exterior angles may be sufficient.
If, on the other hand, we want to determine the shape,
then the lengths of the sides are also needed. We might
require that the lengths of the sides should have uniform
distributions, but a uniform distribution on an
infinite range does not exist unless we weaken the axioms
of probability either by only requiring finite additivity,
or by allowing probabilities to be greater than 1. Also,
the lengths of the sides do determine a triangle, but do
not determine a polygon.
Instead let's choose the vertices at random. This corresponds
to the original question. We could choose the coordinates of
each vertex from a bounded uniform distribution, but this
would mean that the vertices are chosen randomly from a square.
This would not be very satisfying. We would like a distribution
with circular symmetry. If the coordinates are independent
then, apart from a degenerate distribution at the origin,
this implies they have the same normal distribution. In
addition we will assume that all the vertices are chosen
independently. We have already remarked that this gives
maximum entropy, a property that no longer applies in
polar coordinates. However, the polar form of the distribution
of each vertex does have maximum entropy if the coordinates
are taken to be the angle and the square of the radius.
We would certainly like circular symmetry. If we want
to weaken the normality condition we have to allow the
coordinates of each vertex to be dependent. In polar
coordinates, we want the radius and angle to be
independent. One attractive possibility is to choose
the vertices randomly in a circle. This will achieve
maximum entropy for the bounded range and this was the
distribution Ilias considered.
It is difficult to imagine any other vertex distributions
apart from the two given above that would correspond to
our intuitive concept of random triangles or polygons.
A difficulty with random polygons is that the vertices
do not determine a polygon uniquely. If we join the
vertices in an arbitrary order there will be a high
probability of producing a self-intersecting polygon.
Suppose the vertices are joined so that, in polar
coordinates with the origin at the centroid of the points,
each point is joined to the next in cyclic order. An
interesting question might be to find the probability
that the polygon is convex? I must confess, that, if
we are only interested in the angles, the lengths of
the sides are not important, so two polygons that have
the same angles, in the same order could be regarded
as equivalent for some purposes. As the sum of the
exterior angles of any non-self-intersecting polygon
is 2pi, we could just try to choose the angles as
uniformly as possible subject to this condition. We
could do this using homogeneous coordinates.
To return to triangles (I won't consider other polygons),
the coordinates of the three vertices form a six variate
normal distribution. Without loss of generality I will
assume they have independent standard normal distributions.
Changing the mean or the variance only changes the location
or scale (so long as the variances are all equal).
One might imagine that for any circularly symmetric
distribution that the angles of the triangle are
uniformly distributed. They are certainly not independent
as their sum is pi. In fact this leads to the correlation
between angles being -0.5 whatever their distribution so
long as they are identically distributed. We have already
seen, however, that a triangular distribution occurs
under some circumstances, and I shall show that this
is true for a normal distribution.
Let the vertices be vectors A, B and C. (This is a
change of notation, these are no longer the angles
of the triangle). These form a 6 variate normal
distribution with all variables independent. The sides
of the triangle are B-A, C-B and A-C and each
coordinate has correlation -0.5 with the corresponding
coordinate of the others (but the x coordinates are all
independent of the y coordinates). However, it is easier
to condition on A. The conditional distribution of B and
C given A is normal and the 4 components are all
independent. But we are now regarding A as fixed, so
the distribution of U = B-A and V = C-A can be found
by substitution. U and V are conditionally independent
even though, unconditionally, their components have
correlation 0.5. If we use polar coordinates centred
on A it follows that, conditionally, U and V have
rotationally symmetric independent distributions.
Thus we are in the case of uniformly and independently
distributed angles. The angle between these then has
the same triangular distribution discussed previously
and, as this is independent of A, the probability that
angle A is obtuse is 1/4. This proves the result.
Alternatively, we can condition on the mid point of BC
and the vector C-B. Then A will have a bivariate
normal distribution, and using the fact that the squared
length of A - (B+C)/2 has an exponential distribution, we
can find the probability that A is in the circle with BC
as diameter. This should lead to the same answer.
Some might wonder whether the first argument would
apply to any distribution with circular symmetry. It
doesn't. We used the properties of conditional
distributions based on a multivariate normal distribtuion.
These do not apply to other distributions. For example,
for a uniform distribution over a circle, if A is near the
circumference, then B and C are very much constrained
and the argument breaks down. The point is that the
conditional distributions are no longer symmetric.
I have done the theory above for those distributions that
interest me. For these and some other distributions I carried
out 10 million random trials with the following results:
square circle triangle angles sides normal Cauchy
0.725 0.720 0.748 0.750 0.682 0.750 0.833
The first three are uniform distributions of vertices over
the respective shapes (the triangle being equilateral),
"sides" means sides uniform in homogeneous coordinates
as discussed above, and "Cauchy" means independent
Cauchy distributed coordinates. I didn't look at
truncated Cauchy radius and uniform angles.
--
Terry Moore, Statistics Department, Massey University, New Zealand.
Theorems! I need theorems. Give me the theorems and I shall find the
proofs easily enough. Bernard Riemann