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