A few months ago, in the coffee room of our department, I stumbled on an older Bulletin A.M.S and, since I did not have anything pressing to do, I opened it and saw a nice survey by a Hungarian mathematician called Imre Barany. I was intrigued by the title of this beautiful survey: Random points and lattice points in convex bodies. I found many marvelous questions there, questions that never came close to my mind.
One of the problems mentioned in that survey was a problem posed and solved by Renyi and Sulanke sometime in the 60s. Unfortunately, their results were written in German which for me is synonym with Verboten. I tried to find an English source for this paper, and all my Google searches were fruitless. Still, I was very curious how they did it. So, armed with Google Translate, patience and curiosity I proceeded to read the first of their 3 papers. What follows is an exposition of a small part of the first paper. For more details you can look in the first paper of Renyi-Sulanke, that is, if you know enough German to read a math paper. First the problem. $\newcommand{\bR}{\mathbb{R}}$ $\DeclareMathOperator{\area}{Area}$
Suppose that $C$ is a compact convex region in the plane with nonempty interior. Assume that the origin is in the interior of $C$ and $\area(C)=1$. Choose $n$ points $P_1,\dotsc, P_n\in C$ randomly, independently and uniformly distributed. (In technical terms, we choose $n$ independent $\bR^2$-valued random variables with probability distribution $I_Cdxdy$, where $I_C$ is the characteristic function of $C$.) We denote by $\Delta_n=\Delta_n(P_1,\dotsc, P_n)$ the convex hull of this collection of points. This is a convex polygon and we denote by $V_n=V_n(P_1,\dotsc, P_n)$ its number of vertices, by $L_n=L_n(P_1,\dotsc, P_n)$ its perimeter and by $A_n=A_n(P_1,\dotsc, P_n)$ its area. These are random variables and we denote by$\newcommand{\bE}{\mathbb{E}}$ $\bE(V_n)$, $\bE(L_n)$ and respectively $\bE(A_n)$ their expectations. Reny and Sulanke asked to describe the behavior of these expectations as $n\to\infty$. $\newcommand{\bP}{\mathbb{P}}$
Surprisingly, the answer depends in a dramatic fashion on the regularity of the boundary $\newcommand{\pa}{\partial}$ $\pa C$ of $C$. Here I only want to investigate the behavior of $\bE(V_n)$, the expected number of vertices of $\Delta_n$ when $\pa C$ is smooth and has positive curvature at every point. The final answer is the asymptotic relation (\ref{RSv}).
For two points $P,Q\in C$ we denote by $L(P,Q)$ the line determined by them. Denote by $\bP(P,Q)$ the probability that $(n-2)$ points chosen randomly from $C$ lie on the side of $L(P,Q)$. For $i\neq j$ we denote by $E_{ij}$ the event that all the points $P_k$, $k\neq i,j$ lie on the same side of of $L(P_i,P_j)$.
The first crucial observation, one that I missed because I am still not thinking as a probabilist, is that
\begin{equation}
V_n=\sum_{i<j} I_{E_{ij}}.
\end{equation}
In particular,
\[
\bE(V_n)=\sum_{i<j}\bE( I_{E_{ij}})= \sum_{i<j}\bP(E_{ij}).
\]
Since the points $\{P_1,\dotsc, P_n\}$ are independent and identically distributed we deduce that
\[
\bP(E_{ij})=\bP(E_{i'j'}),\;\;\forall i<j,\;\;i'<j'.
\]
We denote by $p_n$ the common probability of the events $E_{ij}$. Hence
\begin{equation}
\bE(V_n)=\binom{n}{2} p_n.
\end{equation}
To compute $p_n =\bP(E_{12})$ we observe that
\[
\bP(E_{12}) =\int_C\int_C \bP(P_1,P_2) dP_1dP_2.
\]
The line $L(P_1,P_2)$ divides the region $C$ into two regions $R_1, R_2$ with areas $a_1(P_1,P_2)$ and $a_2$. The probability that $n-2$ random independent points from $C$ lie in $R_1$ is $a_1(P_1,P_2)^{n-2}$ and the probability $n-2$ random independent points from $C$ lie in $R_2$ is $a_2(P_1,P_2)^{n-2}$. We set
\[
a(P_1,P_2):=\min\bigl\{ a_1(P_1,P_2),\;a_2(P_1,P_2)\}
\]
and we deduce that
\[
\bP(P_1,P_2)= a(P_1,P_2)^{n-2}+\bigl(\;1-a(P_1,P_2)\;\bigr)^{n-2},
\]
\begin{equation}
\bE(V_n)=\binom{n}{2}\int_C\int_C\Bigl\{ \; a(P,Q)^{n-2}+\bigl(\;1-a(P,Q)\;\bigr)^{n-2}\;\bigr\} dPdQ.
\end{equation}
Since $a(P,Q)^{n-2}\leq \frac{1}{2^{n-2}} $, we deduce that
\begin{equation}
\bE(V_n)\sim \binom{n}{2} \int_C\int_C \bigl(1-a(P,Q)\bigr)^{n-2} dPdQ\;\;\mbox{as $n\to\infty$}.
\label{4}
\end{equation}
To proceed further we need to use a formula from integral geometry. Renyi and Sulanke refer to another German source, a book of integral geometry by Blaschke. Fortunately, there is a very good English substitute to Blaschke's book that contains a myriad of exotic formulas. I am referring of course to Luis Santalo's classical monograph Integral Geometry and Geometric Probability. (Santalo was Blaschke's student.)
In Chapter 4, section 1, Santalo investigates the density of pairs of points, more precisely the measure $dPdQ$ used in (\ref{4}). More precisely, he discusses a clever choice of coordinates that is particularly useful in integral geometry.
The line $L(P,Q)$ has a normal $\newcommand{\bn}{\boldsymbol{n}}$ $\bn=\bn(p,q)$
\[
\bn =(\cos \theta,\sin \theta), \;\;\theta\in [0,2\pi],
\]
and it is described by a linear equation.
\[
x\cos \theta+y\sin \theta = p,\;\;p\geq 0.
\]
Once we fix a linear isometry $ T: L(P,Q)\to \bR $, we can identify $P,Q$ with two points $t_1,t_2\in \bR$. Note that $|dt_1dt_2|$ and $|t_1-t_2|$ are independent of the choice of $T$. Santalo op. cit. shows that
\[
|dPdQ|=|t_1-t_2| |dp d\theta dt_1dt_2|.
\]
Now observe that the line $L(P,Q)$ is determined only by the two parameters $p,\theta$ so we will denote it by $L(p,\theta)$. Similarly, $a(P,Q)$ depends only on $p$ and $\theta$ and we will denote it by $a(p,\theta)$. We set
\[
p_0(\theta)=\max\{ s;\;\;s\geq 0, s\bn(\theta)\in C\,\bigr\}.
\]
We denote by $S(p,\theta)$ the segment on $L(p,\theta)$ cut-out by $C$ and by $\ell(p,\theta)$ its length.
\begin{equation}
\bE(V_n)\sim \binom{n}{2}\int_0^{2\pi}\int_0^{p_0(\theta)}\bigl(1-a(p,\theta)\;\bigr)^{n-2}\left(\int_{S(s,\theta)\times S(s,\theta)} |t_1-t_2|dt_1dt_2\right) dp d\theta.
\end{equation}
Observing that for any $\ell>0$ we have
\[
\int_{[0,\ell]\times[0,\ell]}|x-y|dxdy=\frac{ \ell^3}{3}
\]
we deduce
\begin{equation}
\bE(V_n)\sim \frac{1}{3}\binom{n}{2}\int_0^{2\pi}\int_0^{p_0(\theta)}\bigl(1-a(p,\theta)\;\bigr)^{n-2}\ell(s,\theta)^3dp d\theta.
\end{equation}
Now comes the analytical part. For each $\theta\in [0,2\pi]$ we set
\[
I_n(\theta):=\frac{1}{3}\binom{n}{2}\int_0^{p_0(\theta)}\bigl(1-a(p,\theta)\;\bigr)^{n-2}\ell(s,\theta)^3dp ,
\]
so that
\[
\bE(V_n)\sim \int_0^{2\pi} I_n(\theta) d\theta.
\]
Renyi and Sulanke find the asymptotics of $I_n(\theta)$ as $n\to \infty$ by a disguised version of the old reliable Laplace method.
Fix $\theta\in [0,2\pi]$ and set $\newcommand{\ii}{\boldsymbol{i}}$ $\newcommand{\jj}{\boldsymbol{j}}$ $\bn(\theta)=\cos \theta \ii +\sin\theta\jj\in\bR^2$. Since the curvature of $\pa C$ is strictly positive there exists a unique point $P(\theta)\in \pa C$ such that the unit outer normal to $\pa C$ at $P(\theta)$ is $\bn(\theta)$.
For simplicity we set $a(p):=a(p,\theta)$. For $p\in [0,p_0(\theta)]$ we denote by $A(p)=A(p,\theta)$ the area of the cap of $C$ determined by the line $L(p,\theta)$ and the tangent line to $\pa C$ at $P(\theta)$ $x\cos\theta+y\sin\theta=p_0(\theta)$. In Figure 1 below, this cap is the yellow region between the green and the red line.
 |
| Figure 1: Slicing a convex region in directions perpendicular to $\bn(\theta)$. The circle in red is the osculating circle to the boundary at the unique point $P(\theta)$ where the unit outer normal is $\bn(\theta)$. |
\begin{equation}
\si_0<\inf_{\theta\in [0,2\pi]} p_0(\theta) .
\end{equation}
\begin{equation}
a(p,\theta)=A(p,\theta),\;\;\forall p\in [\si_0,p_0(\theta)].
\end{equation}
\begin{equation}
c<a(p,\theta)\leq\frac{1}{2},\;\;\forall p\in [0,s_0].
\label{low}
\end{equation}
\begin{equation}
\frac{d\ell}{dp}<0\;\;\mbox{on $[\si_0,p_0]$}.
\end{equation}
We have
\[
I_n(\theta)\sim\frac{n^2}{6}\int_0^{p_0(\theta)}\bigl(1-a(p)\,\bigr)^{n-2} \ell(p) dp
\]
\[
=\underbrace{\frac{n^2}{6}\int_0^{\si_0}\bigl(1-a(p)\,\bigr)^{n-2} \ell(p) dp}_{=:I_n^0(\theta)}+\frac{n^2}{6}\underbrace{\int_{\si_0}^{p_0(\theta)}\bigl(1-a(p)\,\bigr)^{n-2} \ell(s) dp}_{=J_n(\theta)}.
\]
The condition (\ref{low}) implies that as $n\to\infty$ we have $I_n^0(\theta)=o(1)$, uniformly in $\theta$. Thus
\begin{equation}
I_n(\theta)\sim\frac{n^2}{6} J_n(\theta),\;\;n\to\infty.
\end{equation}
We will use Laplace's method to estimate $J_n(\theta)$. We introduce a new variable $\tau=\tau(p)=p_0(\theta)-p$, $s\in [\si_0, p_0(\theta)]$ so that $\tau\in [0,\tau_0(\theta)]$, $\tau_0(\theta)=p_0(\theta)-\si_0$. Geometrically, $\tau$ denotes the distance to the tangent line $L(p_0(\theta),\theta)$.
We will denote by $L(\tau)$ the line $L(p,\theta)$. Thus, as $\tau$ increases the line $L(\tau)$ moves away from the boundary point $P(\theta)$ and towards the origin. Similarly, we set $a(\tau)=a(p)=a(p,\theta)$ etc. Hence
\[
J_n(\theta)=\int_0^{\tau_0} \bigl(1-a(\tau))^{n-2}\ell(\tau)^3 d\tau.
\]
Observe first that for along the interval $[0,\tau_0]$ we have
\[
\frac{d a}{d\tau}=\frac{dA}{d\tau}=\ell(\tau).
\]
The line $L(\tau)=L(p,\theta)$ intersects the osculating circle to $\pa C$ at $P(\theta)$ along a chord of length $\bar{\ell}(\tau)$. We set $t:=\sqrt{\tau}$. From the definition of the osculating circle we deduce
\[
\ell(t)=\bar{\ell}(t)(1+o(1)),\;\;\frac{d\ell}{dt}=\frac{d\bar{\ell}}{dt}(1+o(1))\;\;\mbox{as $t\to 0$}.
\]
If $r=r_\theta$ denotes the radius of the osculating circle so that $\frac{1}{r_\theta}$ is the curvature of $\pa C$ at $P(\theta)$, then
\[
\bar{\ell}(\tau)= 2\sqrt{r^2-(r-\tau)^2}=2\sqrt{2r\tau-\tau^2}= 2\sqrt{\tau}\sqrt{2r-\tau}=2t\sqrt{2r-t^2}.
\]
Hence
\[
\frac{d\bar{\ell}}{dt}|_{t=0}=2\sqrt{2r}
\]
We denote the $t$-derivative by an upper dot $\dot{}$. Note that
\begin{equation}
\dot{a}=\frac{d\tau}{dt}\frac{da}{d\tau}= 2t\ell(t),\;\;\dot{\ell}(t)=\dot{\ell}(0)+O(t)=2\sqrt{2r}+O(t).
\label{dota}
\end{equation}
We deduce
\begin{equation}
J_n(\theta)=2\int_0^{t_0} \bigl( 1-a(t)\bigr)^{n-2} \ell(t)^3tdt,\;\;t_0=\sqrt{\tau_0}.
\end{equation}
Note that
\[
\ddot{a}(t)=2\ell(t)+2t\dot{\ell}(t),\;\;\frac{d^3a}{dt^3}=4\dot{\ell}(t)+2t\ddot{\ell}(t),
\]
so that
\[
a(0)=\dot{a}(0)=\ddot{a}(0)=0, \;\;\frac{d^3 a}{dt^3}|_{t=0}= 4\dot{\ell}(0)=8\sqrt{2r}.
\]
We deduce
\[
a(t)=\frac{8\sqrt{2r}}{6}t^3+O(t^4)= \underbrace{\frac{4\sqrt{2r}}{3}}_{=:C(r)}\;\;t^3+O(t^4).
\]
We set
\[
\nu:=(n-2),\;\; w_\nu(t)= \bigl( 1-a(t)\bigr)^{\nu} \ell(t)^3t,
\]
\[
\frac{u}{\nu}:=C(r)t^3\iff t=\left(\frac{u}{C(r)\nu}\right)^{\frac{1}{3}}.
\]
Note that
\[
\ell(t)^3=\bigl( 2\sqrt{2r}t+O(t^2)\;\bigr)^3=(6C(r) t)^3 + O(t^4).
\]
Hence
\[
w_\nu(t)dt = \left( 1-\frac{u}{\nu} +O\left(\frac{u}{\nu} \right)^{4/3}\;\right)^\nu \left(\frac{((6C(r))^3}{C(r)\nu} u+ O\left(\frac{u}{\nu}\right)^{4/3}\;\right) \left(\frac{u}{C(r)\nu}\right)^{1/3}\left(\frac{1}{C(r)\nu}\right)^{1/3}\frac{1}{3}u^{-2/3} du
\]
\[
=\frac{(6C(r))^3}{3C(r)^{5/3}\nu^{5/3}} \left( 1-\frac{u}{\nu} +O\left( \frac{u}{\nu} \right)^{4/3}\;\right)^\nu u^{2/3} \left( 1+ O\left(\frac{u^{1/3}}{\nu^{1/3}}\right)\;\right) du
\]
\[
=\frac{6^3C(r))^{4/3}}{3\nu^{5/3}} \left( 1-\frac{u}{\nu} +O\left( \frac{u}{\nu} \right)^{4/3}\;\right)^\nu u^{2/3} \left( 1+ O\left(\frac{u^{1/3}}{\nu^{1/3}}\right)\;\right) du
\]
Hence
\[
J_n(\theta)=\frac{6^3C(r))^{4/3}}{3\nu^{5/3}}\underbrace{\int_0^{u_\nu} \left( 1-\frac{u}{\nu} +O\left( \frac{u}{\nu} \right)^{4/3}\;\right)^\nu u^{2/3} \left( 1+ O\left(\frac{u^{1/3}}{\nu^{1/3}}\right)\;\right) du}_{=:\hat{J}_\nu},\;\; u_\nu=\nu C(r)t_0^3.
\]
Now observe that
\[
\frac{6^3C(r)^{4/3}}{3}= \underbrace{\frac{1}{3}6^3 \left(4\sqrt{2}{3}\right)^{4/3}}_{=:Z_1} r^{2/3}.
\]
and
\[
\lim_{\nu\to\infty} \hat{J}_\nu=\int_0^\infty e^{-u} u^{2/3}=\Gamma(5/3).
\]
Thus
\[
J_n(\theta) \sim Z_1\Gamma(5/3)r^{2/3}\nu^{-5/3}\sim Z_1\Gamma(5/3)r^{2/3}n^{-5/3},
\]
\[
I_n(\theta) \sim \frac{n^2}{6}J_n(\theta)\sim \frac{Z_1\Gamma(5/3)r^{2/3}}{6} n^{1/3}.
\]
Now observe that the curvature at the point $P(\theta)$ is $\kappa(\theta)=\frac{1}{r_\theta}$. hence
\[
I_n(\theta) \sim \frac{n^2}{6}J_n(\theta)\sim \frac{Z_1\Gamma(5/3)\kappa(\theta)^{-2/3}}{6} n^{1/3}
\]
If we denote by $ds$ the arclength on $\pa C$, then, by definition
\[
\frac{d\theta}{ds}=\kappa(\theta)\iff d\theta=\kappa ds.
\]
Thus
\begin{equation}
\bE(V_n)\sim \int_0^{2\pi} I_n(\theta) d\theta \sim \frac{Z_1\Gamma(5/3)}{6} n^{1/3}\int_{\pa C} \kappa^{1/3} ds.
\label{RSv}
\end{equation}
This is one of Renyi-Sulanke's result.
Remark. Before I close, let me mention that the asymptotics of $\bE(V_n)$ for $n$ large depends dramatically on the regulariti of the boundary of $C$. For example, if $C$ itself is a convex polygon with $r$-vertices, then Renyi-Sulanke show that
\[
\bE(V_n) \sim\frac{2r}{3}\log n.
\]
Compare this with the smooth case when the convex hull is expected to have many more vertices $\approx n^{1/3}$.
There are more to say about this story. As the title indicates, I plan to return to it in a later post.
No comments:
Post a Comment