5
$\begingroup$

A couple days ago, a friend challenged me to solve a problem:

You have N vertices, each randomly placed on the edge of a unit circle. What is the formula (given N) that yields the average perimeter of these polygons.

Note that the points are not connected by the order in which they were placed, but rather by which points are closest together. i.e. You sweep in a clockwise direction tracing the polygon by the order you come across the points after the points have been randomly placed.

After some hard thought, I came up with what I think may be the solution:

$$n\int_0^{2\pi} \frac{(n-1)(1-\frac{x}{2\pi})^{n-2}}{2\pi} \times \sqrt{2-2\cos {x}} \, dx$$

This formula finds the average secant length length for $n$ vertices and multiplies that length by the number of sides; however, I have a feeling this does not solve the problem because the lengths of the secants in the polygon depend on each other.

I would like someone to confirm my suspicions, tell me that my formula works, or give me a different reason why the formula doesn't work.

Please Do Not Solve This Problem For Me

I still want to solve it on my own if this is not the solution.

$\endgroup$
2
$\begingroup$

Your worries about the dependence of the lengths are unfounded. The nice thing about linearity of expectation, and what makes it so useful in getting results without working out entire probability distributions, is that it doesn't require independence. Assuming that you calculated the average length correctly, this is the correct result. I haven't checked that yet but will do when I get back from catching the last sun rays of this beautiful April day :-)

$\endgroup$
  • $\begingroup$ Thank you for the quick answer! $\endgroup$ – 2.71828-asy Apr 6 '16 at 15:11
  • $\begingroup$ @2.71828-asy: I checked the average secant length, I think it's correct. You can put it in a slightly nicer form by expressing the cosine in terms of half the angle and simplifying. Unfortunately Wolfram|Alpha doesn't give a closed form for the resulting integral. $\endgroup$ – joriki Apr 6 '16 at 15:57
2
$\begingroup$

The problem can be stated in the following way: we want to compute the average of $$ \sum_{k=1}^{N} 2\sin(\pi \theta_k) $$ when $(\theta_1,\ldots,\theta_N)$ is selected at random in the region $E$ given by $\theta_i\geq 0, \sum_{k=1}^{N}\theta_i = 1$.

By the linearity of expectation, the previous average is just $2N$ times the expected value of $\sin(\pi\theta_1)$ over $E$. Now the Dirichlet's distribution comes at hand. By approximating $\sin(\pi x)$ with $4x(1-x)$ over $(0,1)$, we have that the average perimeter is close to: $$ 2N\cdot 4\left(\frac{1}{N!}-\frac{2}{(N+1)!}\right)\cdot (N-1)! =8\cdot\frac{N-1}{N+1}$$ that obviously cannot be a tight approximation for $N\geq 8$ due to the isoperimetric inequality.

Anyway, for any given $N$ we may find a suitable polynomial approximation for $\sin(\pi x)$ over $(0,1)$, then perform the same steps as above. The exact expression for the average perimeter involves a hypergeometric function $_1 F_2$:

$$ 2\pi\cdot\phantom{}_1 F_2\left(1;\frac{1}{2}+\frac{N}{2},1+\frac{N}{2};-\frac{\pi^2}{4}\right)=\color{red}{2\pi-2\pi^2\int_{0}^{1}v^N\sin(\pi v)\,dv} $$

that clearly behaves like $2\pi-O\left(\frac{1}{N^2}\right)$ for large $N$.

An extremely good approximation for large $N$ is $2\pi-\frac{2\pi^3}{(N+1)(N+3)}$.

$\endgroup$
  • 1
    $\begingroup$ OP did say they didn't want the problem solved, though. $\endgroup$ – Brian Tung Apr 6 '16 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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