7
$\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$
  • 1
    $\begingroup$ This may be helpful (e.g. page 62). $\endgroup$ – zhoraster Nov 23 '19 at 9:33
1
$\begingroup$

Both the site you linked to and the thesis linked to by zhoraster yield $L=4\pi^3$.

From the site, we have

$$ \lim_{n\to\infty}\frac{\pi-\mathbb EX_n}{\pi-\frac n2\sin\left(\frac{2\pi}n\right)}=6\;. $$

With $\pi-\frac n2\sin\left(\frac{2\pi}n\right)=\frac23\pi^3n^{-2}+O\left(n^{-4}\right)$, it follows that $\lim_{n\to\infty}n^2\left(\pi-\mathbb EX_n\right)=4\pi^3$.

From the thesis, we have (p. $63$)

$$ \mathbb EX_n=\frac3{\pi^2}\binom n3\int_0^\pi\sin^2h\left(\frac h\pi\right)^{n-3}\mathrm dh\;. $$

This is convenient for calculating $\mathbb EX_n$ for small $n$, but we can obtain a simpler form that's more convenient for large $n$ by repeatedly integrating by parts and substituting $x=2h$, yielding

\begin{eqnarray*} \mathbb EX_n&=&\frac n2\int_0^{2\pi}\cos x\left(\frac x{2\pi}\right)^{n-1}\mathrm dx\\ &=&\pi+\pi\int_0^{2\pi}\sin x\left(\frac x{2\pi}\right)^n\mathrm dx\;. \end{eqnarray*}

Integrating by parts twice more yields

\begin{eqnarray*} \mathbb EX_n&=&\pi+\frac{4\pi^3}{(n+1)(n+2)}+O\left(n^{-4}\right)\\ &=&\pi+4\pi^3n^{-2}+O\left(n^{-3}\right)\;, \end{eqnarray*}

again leading to $L=4\pi^3$.

| cite | improve this answer | |
$\endgroup$

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.