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