6
$\begingroup$

Choose $n$ points $\{z_1, \ldots, z_n\}$ from the unit circle $\partial \mathbb{D} = \{z \in \mathbb{C}: |z| = 1\}$ uniformly at random, and let $P_n$ be the convex hull of the $z_i$'s. Let $X_n = area(P_n)$. What can be said about $X_n$? Can $\mathbb{E}X_n$ be computed? It's easy to see that $P_n$ converges to $\mathbb{D}$ pointwise almost surely, so $X_n \to \pi$ a.s. as $n \to \infty$. What is the rate of convergence?

It is 'easy' to get a direct computation for $\mathbb{E}X_3$, by writing down a formula for the area of the triangle and integrating directly: for example, you can assume $z_1 = 1$, and that $z_2 = e^{i \theta}, z_3 = e^{i \phi}$ with $\theta < \phi$, and integrate directly. But this is a bit tedious, and especially so for large $n$! Is there an easier way to do this computation?

One idea is to rely on order statistics: write $z_k = \exp(i \theta_k)$ for iid uniform variables $\theta_k \in [0,2\pi)$, and let $\{\phi_k\}_{k=1}^n$ be the ordered sequence of the $\theta_k$, i.e.

$\phi_1 = \min\{\theta_1, \ldots, \theta_n\}$,

$\phi_2 = $ 2nd largest element of $\{\theta_1, \ldots, \theta_n\}$,

...

$\phi_n = \max\{\theta_1, \ldots, \theta_n\}$.

The distributions of the $\phi$'s can be written down explicitly - though it's a bit messy - and $P_n$ can be divided into $n$ triangles, yielding

$X_n = \frac{1}{2} \sum_{k=1}^n \sin(\phi_k - \phi_{k-1})$,

with the convention $\phi_0 = \phi_n - 2\pi$. I haven't tried writing down this integral out of fear, but it may be do-able. (I suspect there is a clever symmetry argument to avoid needing the order statistics.)

Heuristically, if the $z_n$ are 'well-distributed,' the angle distance between adjacent $z_i$'s is roughly $\frac{2\pi}{n}$, so the error between the areas of the disk and $P$ is roughly

$n(\frac{\pi}{n} - \frac{1}{2} \sin(\frac{2\pi}{n})) = \frac{4\pi^3}{3} n^{-2} + O(n^{-4})$.

Thus we should have

$n^2(\pi - \mathbb{E}X_n) \to L \in (0,\infty)$ $\hspace{.5cm} (\star)$

Perhaps this argument can be formalized, and the constant $L$ can be determined.

After that, the usual next step is to hope for something like

$n^2(\pi - X_n) \to_d Z$ for some random variable $Z$,

or a CLT like

$\gamma_n (X_n - \mathbb{E}X_n) \to_d N(0,1)$ for some constants $\gamma_n$.

Also: what if the $z_k$ are selected uniformly from the unit sphere in $d$-dimensions? I haven't thought much about this, but maybe a statement analogous to $\star$ can be proved.

Edit 1: A quick google search revealed this site, which has some additional interesting calculations. In particular, it claims to compute $L$ via the method I suggested, which would answer $\star$.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.