Expected Area of Random Polygon In a Circle
The area of a unit circle is PI, whereas the area of a regular n-
sided polygon inscribed in the circle is (n/2) sin(2PI/n), which
of course approaches PI as n goes to infinity. Now, suppose that
instead of a regular n-gon we consider a convex polygon whose
vertices are chosen randomly on the perimeter of the circle
(assuming a uniform distribution for the probability density over
the perimeter). In general the area of a random n-gon will be less
than the area of the regular n-gon, but both of them will approach
PI as n goes to infinity. Jim Ferry posed the problem of proving
that the expected value of the deviation from PI for the area of a
random n-gon is, asymptotically, 6 times the deviation for a regular
n-gon in the limit as n goes to infinity.
For sufficiently large values of n the maximum distance between
consecutive vertices of the random n-gon will almost certainly be
small. Of course, for any fixed n, it's possible that the maximum
angular gap between neighboring vertices could be anything less than
2PI, but the probability of the maximum gap being greater than a
certain arc q can be made arbitrarily small by increasing n. On
this basis, we see that the asymptotic behavior of the expectated
area of a random polygon in the limit of increasing n can be deduced
by considering only polygons whose maximum sectors subtend arbitrarily
small angles. (To make this rigorous, just consider the volume of
the state space with a range of maximum angles.)
Now, in a unit circle, the area of an arc sector of angle q is
(q/2PI)PI = q/2, whereas the area of the corresponding sector of
a polygon inscribed in the circle is sin(q)/2, so the discrepancy
is (q-sin(q))/2. Recalling that the power series for sin(x) is
x - x^3/3! + x^5/5! - ... this tells us that the discrepancy is
(q^3/3! - q^5/5! + ...)/2. In the "large n, small angle" limit,
the discrepancy for a sector of arc q goes to (q^3)/12. In other
words, the discrepancy is proportional to the cube of the subtended
angle, and this applies to the sectors of regular and random
polygons alike. Thus the ratio of the discrepancies for regular
and random n-gons approaches the ratio of the sum of cubes of the
sector angles in the respective figures.
Obviously we can focus on partitions of the interval from 0 to 2PI,
but we'll get the same answer (and it's more convenient) to rescale
and consider the partitions of the unit interval from 0 to 1. The
sum of the cubes of the regular n-gon partition of the unit interval
is simply n(1/n)^3, which is 1/n^2. Our question, then, reduces to
finding the expected sum of cubes of the segments of a random
partition of the unit interval into n parts. We will call this
E(n).
One straightforward way of determining the the form of E(n) would be
to simply evaluate the expectation for specific values of n such as
1 x y
/ / / / \
| | | ( (1-x)^3 + (x-y)^3 + (y-z)^3 + (z)^3 ) dz dy dx
/ / / \ /
0 0 0
E(4) = -------------------------------------------------------
1 x y
/ / /
| | | dz dy dx
/ / /
0 0 0
After evaluating a few of these we can easily discern the pattern,
but "discerning the pattern" isn't quite the same as rigorously
establishing the formula. To be a bit more rigorous, we could
proceed inductively. Obviously for n=1 we have E(1)=1. In general,
E(n+1) can be computed from E(n) by the formula
1
/ n-1 / 3 3 \
| (1-x) ( x + (1-x) E(n) ) dx
/ \ /
x=0
E(n+1) = -----------------------------------------
1
/ n-1
| (1-x) dx
/
x=0
This is just the expectation for the (n+1)th part to be of size x,
evaluated for all x from 0 to 1. Each of these x values is "weighted"
by (1-x)^(n-1) because that's the probability of all the other n-1
break-points being in the 1-x region. On that condition, the expected
sum of the cubes is x^3 plus the expected sum of cubes for a partition
of the region 1-x into n parts, which is just E(n) scaled by the
factor (1-x)^3.
If we now define the variable u = 1-x we have du = -dx and the above
formula becomes
0
INT u^(n-1) [(1-u)^3 + u^3 E(n)] du
x=1
E(n+1) = -------------------------------------
0
INT u^(n-1) du
x=1
Evaluating the elementary integrals we get
n 6
E(n+1) = --- E(n) + ---------------
n+3 (n+1)(n+2)(n+3)
Multiplying through by the right hand denominator gives
(n+1)(n+2)(n+3) E(n+1) = n(n+1)(n+2) E(n) + 6
Consequently, each quantity of the form k(k+1)(k+2)E(k) is 6 greater
then the preceding quantity. Thus, to go up n steps we simply add
6n, so we have
(n+1)(n+2)(n+3) E(n+1) = 1(1+1)(1+2) E(1) + 6n
= 6(n+1)
Thus, decrementing the indices by 1, we've proven that
6
E(n) = ----------
(n+1)(n+2)
This is the expected sum of cubes of the segments comprising a
random partition of the unit interval into n parts, assuming the
n-1 interior dividing points are randomly selected from a uniform
distribution. Recall that E(n) for a regular polygons is simply
1/n^2, so the ratio of the discrepancies for random and regular
n-gons is 6/(1 + 3/n + 2/n^2), which goes to 6 as n increases,
completing the proof of Jim Ferry's puzzle.
Incidentally, notice that the solution of this problem makes use
of the formula for the expected value of the sum of the CUBES of
the components of a random partition of the unit interval into n
parts. More generally, we can give the expected sum of pth powers
of the components of a random partition of the unit interval into
n parts. Letting E(n,p) denote this value, we have
n+1
E(n+1,p) = --------
C(n+p,p)
where C(i,j) is the binomial coefficient. (With p=3 this reduces
to our expression 6/((n+1)(n+2) for cubes.) This general formula
is so simple and useful that it ought to be better known than it is.
Obviously the "6" in the answer to Jim's puzzle arises from the p!
with p=3 in this expression. We could also construct other scenarios
involving the general expression, such as allowing a unit interval
to fall onn the floor and break at k random points to give k+1
segments, and then consider the total "volume" given by constructing
p-dimensional rectangular solids with those edge lengths.
Another interesting thought suggested by the puzzle is to give the
EXACT formula for the expected area of an n-sided convex polygon
whose vertices are randomly selected points on the unit circle
(assuming a uniform distribution on the perimeter). To answer this
question we obviously can't make use of the small-angle assumption,
so we must use the full sine formulas. We could still use central
sectors (recognizing that for sector angles greater than PI the area
will be negative), but we can also deal with strictly positive areas
by taking a center on the perimeter of the circle.
So, let's take an arbitrary point on the circumference as our
"origin" O (without loss of generality), and note that the distance
from this point to any other point P on the circle is 2sin(q) where
q is the angle between the line OP and the tangent to the circle
at O. Now, any convex polygon inscribed in the circle with k+1
vertices can be characterized by a set of k increasing angles
q1,q2,..,qk denoting the angles between the tangent at O and the
lines P1,P2,..,Pk respectively. Also, the area of the polygon is
given by the sum of k-1 triangular regions defined by these k
rays. Thus for any set of angles the area of the polygon is
k-1
A = SUM (1/2) (2sin(q_i)) (2sin(q_{i+1}) sin(q_{i+1} - q_i)
i=1
Furthermore, we know that a uniform distribution on the circumference
of the circle maps to a uniform distribution of the q angles in the
range from 0 to PI. Hence we can find the expected area of the
polygon by integrating over the region with q1 from 0 to PI, q2 from
0 to q1, and so on. (Here I've reversed the order of the indices,
so the angles are strictly decreasing.) Letting E[A_n] denote the
expected area of a random n-gon inscribed in a unit circle, we have
E(A_{k+1}) =
PI q1 q2
/ / / k-1
2 | | | ... SUM sin(q )sin(q )sin(q - q ) dq1 dq2 dq3 ...
/ / / i=1 i i+1 i+1 i
0 0 0
----------------------------------------------------------------
PI q1 q2
/ / /
2 | | | ... dq1 dq2 dq3 ...
/ / /
0 0 0
The integrations are all elementary, and we get the following results
for the expected area of a "random n-gon" inscribed in a unit circle:
n E[A_n]
--- --------------------------------------------------------
3! / 2PI \
3 -------- ( ----- )
2^3 PI^2 \ 1! /
4! / (2PI)^2 \
4 -------- ( ------- )
2^4 PI^3 \ 2! /
5! / (2PI) (2PI)^3 \
5 -------- ( - ----- + ------- )
2^5 PI^4 \ 1! 3! /
6! / (2PI)^2 (2PI)^4 \
6 -------- ( - ------- + ------- )
2^6 PI^5 \ 2! 4! /
7! / (2PI) (2PI)^3 (2PI)^5 \
7 -------- ( ----- - ------- + ------- )
2^7 PI^6 \ 1! 3! 5! /
8! / (2PI)^2 (2PI)^4 (2PI)^6 \
8 -------- ( ------- - ------- + ------- )
2^8 PI^7 \ 2! 4! 6! /
and so on. Obviously the quantities in parentheses are partial sums
of the power series expansions of sin(2PI) and 1 - cos(2PI). The
numerical values of E[A_n] for the first several values of n are
listed below:
n E[A_n] n E[A_n] n E[A_n]
--- -------- --- -------- --- --------
3 0.477... 14 2.685... 25 2.973...
4 0.955... 15 2.734... 26 2.985...
5 1.350... 16 2.775... 27 2.995...
6 1.662... 17 2.811... 28 3.005...
7 1.906... 18 2.841... 29 3.013...
8 2.099... 19 2.868... 30 3.021...
9 2.253... 20 2.891... 31 3.028...
10 2.376... 21 2.912... 32 3.035...
11 2.447... 22 2.930...
12 2.559... 23 2.946...
13 2.628... 24 2.960...
In general, for odd n we have the explicit "sine" formula for the
expected area of a random n-gon inscribed in a unit circle:
2k-1
n! m k+m (2PI)
E[A_n] = --------- SUM (-1) ---------
n n-1 k=1 (2k-1)!
2 PI
where m=(n-1)/2, and for even n we have the "1-cosine" formula
2k
n! m k+m (2PI)
E[A_n] = --------- SUM (-1) --------
n n-1 k=1 (2k)!
2 PI
where m=(n-2)/2. If we recall that the area of a regular n-gon in
a unit circle is (n/2)sin(2PI/n), we see that the original proposition
amounts to the assertion
PI - E[A_n]
lim -------------------- = 6
n->oo PI - (n/2)sin(2PI/n)
Thus, letting sin(x,k) denote the kth partial sum of the power
series expansion of sin(x), for odd n we have
n!
1 - ------- |sin(2PI,(n-1/2))|
(2PI)^n
lim --------------------------------- = 6
n->oo n
1 - ----- sin(2PI/n)
(2PI)
Return to MathPages Main Menu
Сайт управляется системой
uCoz