Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I came across a nice problem that I would like to share.

Problem: What is expected value of the area of an $n$-gon whose vertices lie on a circle of radius $r$? The vertices are uniformly distributed.

share|improve this question
    
Try dissecting it into triangles, and use the $2 \pi/n$ angle to find the value. –  Pedro Tamaroff Jun 19 '12 at 16:58
2  
@PeterSheldrick It converges to $\pi$. Uniformly distributed infinite sequence is dense almost surely, so for large n you have a lot of points which are fairly dense, so you're closely approximating the circle. To me it seems like an iterated integral of sines. You can dissect into triangles as Peter Tamaroff said, and you can assume that you're choosing the points in the order they appear on the circle (multiplying by a factorial to discount that fact). –  tomasz Jun 19 '12 at 16:59
    
It converges to $\pi r^2$ where $r$ is the radius. –  Michael Hardy Jun 19 '12 at 17:47
1  
@Peter I don't think it is appropriate to edit questions in that way. To you, it may be obvious that multiplication by $r^2$ at the end is all that's needed to convert from the unit circle. There are many users of this site to which that would not be obvious. –  alex.jordan Jun 19 '12 at 18:52
1  
@Potato: Like alex said. Additionally, such modifications can render incorrect some parts of the answers already posted (and they do in the case at hand). –  Did Jun 19 '12 at 19:20

3 Answers 3

up vote 8 down vote accepted

For $n$ even and $m=(n-2)/2$, the expected area for a unit-radius circle is $$\frac{n!}{2^n \pi^{n-1}} \sum_{k=1}^m (-1)^{k+m} \frac{(2\pi)^{2k}}{(2k)!} \;.$$ For $n$ odd, there is a similar expression. For example, for $n=4$, this leads to $$\frac{4!}{2^4 \pi^{3}} \frac{(2\pi)^2}{2!} = \frac{3}{\pi} \approx 0.955 \;.$$ For $n=32$, the sum is $3.035$, approaching $\pi$ as anticipated. I found this at a Math Pages article entitled "Expected Area of Random Polygon In a Circle".

share|improve this answer
    
To give this some more publicity i'm linking it here On the Variance of Random Polygons. Maybe some of the formulas are applicable. –  Peter Sheldrick Jun 19 '12 at 18:20
5  
Now that everyone's settled, I've removed some comments. –  Zev Chonoles Jun 19 '12 at 19:14
    
@DayLateDon: Thanks for fixing the exponent! –  Joseph O'Rourke Jun 19 '12 at 19:40
1  
+1. By the way, convergence to $\pi$ guaranteed (and obvious?) because --ignoring the factor $(-1)^m$-- the sum tends to the power series of $\cos(2\pi) - 1 = 0$, with the error in the partial sum through term $m$ being bounded by $(2\pi)^{2(m+1)}/(2(m+1))!$ (ie, the "next" term). As the limiting values of the sum is zero, we can use this error term as an approximation of the absolute value of partial sum. Since $m = (n-2)/2$, this approximation is just $(2\pi)^n/n!$, which collapses the "expected area" formula to exactly $\pi$ for each $n$. –  Blue Jun 19 '12 at 20:01

Let $a_n$ denote the angle between a vertex $M$ and the next one $M'$ on the circle, then $[a_n\geqslant u]$ means that none of the $n-1$ other vertices is in an interval of length $u$, hence $\mathrm P(a_n\geqslant u)=\left(1-\frac{u}{2\pi}\right)^{n-1}$. The area of the triangle $OMM'$ is $\frac12\sin(a_n)$. By exchangeability, the expected area of the whole polygon is $n$ times the expected area of $OMM'$ hence $$ A_n=\frac{n}2\mathrm E(\sin(a_n))=-\frac{n}2\int_0^{2\pi}\sin(u)\mathrm d\left(1-\frac{u}{2\pi}\right)^{n-1}=\frac{n}2\int_0^{2\pi}\cos(u)\left(1-\frac{u}{2\pi}\right)^{n-1}\mathrm du, $$ that is, $$ A_n=n\pi\int_0^1\cos(2\pi u)u^{n-1}\mathrm du=\pi n!B_{n-1},\qquad B_n=\int_0^1\cos(2\pi u)\frac{u^n}{n!}\mathrm du. $$ An integration by parts leads to the recursion $$ (2\pi)^2B_n=\frac1{(n-1)!}-B_{n-2}. $$ Since $B_0=B_1=0$, one gets for every $n\geqslant2$, $$ B_n=\sum_{k\geqslant0}\frac1{(2\pi)^{2k+2}}\frac{(-1)^k}{(n-2k-1)!}\,[2k+2\leqslant n], $$ and, finally, for every $n\geqslant3$, $$ A_n=\pi n!B_{n-1}=\pi n!\sum_{k\geqslant1}\frac1{(2\pi)^{2k}}\frac{(-1)^{k+1}}{(n-2k)!}\,[2k+1\leqslant n]. $$


Previous version, leads to complicated expressions: Let $p_n(r)$ denote the probability of the event $B_n(r)$ that the point $(r,0)$ is inside the polygon $Q_n$, for every $0\leqslant r\leqslant1$. Then $p_n(r)$ is also the probability that any point at distance $r$ from the origin is inside $Q_n$. The area of the polygon is $$ |Q_n|=\iint [r\mathrm e^{\mathrm i\theta}\in Q_n]\,r\mathrm dr\mathrm d\theta. $$ Taking expectations yields the mean area $$ A_n=\mathrm E[|Q_n|]=2\pi\int_0^1rp_n(r)\mathrm dr. $$ The event $B_n(r)$ depends only on the locations of the two vertices on the circle on both sides of $(1,0)$. Let $a_n$ and $-b_n$ denote the angles of these locations, then, for every nonnegative $u$ and $v$ such that $u+v\leqslant2\pi$, $[a_n\geqslant u,b_n\geqslant v]$ is the event that the interval $(-v,u)$ on the circle received no vertex at all, hence $$ \mathrm P(a_n\geqslant u,b_n\geqslant v)=\left(\frac{u+v}{2\pi}\right)^n. $$ One sees that $B_n(r)$ is the event that the straight line between $\mathrm e^{\mathrm ia_n}$ and $\mathrm e^{-\mathrm ib_n}$ intersects the horizontal axis on the right of $(r,0)$, that is, that $r\leqslant \varrho_n$, where $$ \varrho_n=\frac{\sin(a_n+b_n)}{\sin(a_n)+\sin(b_n)}. $$ Hence, $[(r,0)\in Q_n]=[r\leqslant \varrho_n]$ and $A_n=\pi\mathrm E(\varrho_n^2)$, that is, $$ A_n=\frac1{4\pi}\iint\left(\frac{\sin(u+v)}{\sin(u)+\sin(v)}\right)^2\,n(n-1)\left(\frac{u+v}{2\pi}\right)^{n-2}\,[u\geqslant0,v\geqslant0,u+v\leqslant2\pi]\,\mathrm du\mathrm dv. $$ And at this point, the thought that another method might be less computationally challenging begins to creep in...

share|improve this answer
    
+1 I was exploring this way, too –  leonbloy Jun 19 '12 at 18:33
    
@leonbloy: It seems YOUR solution can be pushed a little farther. :-) –  Did Jun 19 '12 at 18:45
1  
Yes, you're right, I jumped too quickly to the "lazy asymptotic mode" :-) I'm not sure if the initial formula (sum of triangles) is correct even if the center of the circle is not included in the polygon (we'd have negative areas, then) but I suspect it is. –  leonbloy Jun 19 '12 at 19:03
1  
Bravo! And hooray for exchangeability! –  Byron Schmuland Jun 19 '12 at 19:03
    
@leonbloy: It seems to be, thankfully, since in this case one wants to count the area of this triangle negatively. –  Did Jun 19 '12 at 19:31

A simple asympotics, for large $N$: the central angles $x_i$ (which sum up to $2\pi$, and hence are not independent), can be approximated as iid exponentials $y_i$ with mean $\alpha=2 \pi /N$ (a similar procedure as "Poissonization" for discrete variables - also analogous to change ensemble in statistical physics).

Then, because the area of each triangle is $ \sin(x_i)/2$, we have that the expected area is

$$E(A) = \frac{1}{2}\sum_{i=1}^N E[\sin(x_i)] \approx \frac{N}{2} E[\sin(y_i)] = \frac{N}{2} \int_0^{\infty} \sin(y) \frac{1}{\alpha} \exp{\left(-\frac{y}{\alpha}\right)} \,dy = \frac{N}{2} \frac{\alpha}{1+\alpha^2}$$

So $$E(A)\approx \frac{\pi}{1+(2 \pi/N)^2}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.