Hope to add bits of mathematics or mathematical news I find interesting.
Wednesday, November 2, 2022
Monday, December 21, 2020
Wednesday, August 12, 2020
A video conference by Robert D. MacPherson
This videoconference by Bob MacPherson is courtesy Simons Foundation
Tuesday, February 25, 2020
mathUganda
I want to advertise here the efforts of Sergiu Moroianu to help young math olympians from Uganda. I think this is a worthy cause. You can learn more at this site. You too can help by spreading the news about this initiative.
Sunday, December 8, 2019
Random convex polygons III
As I mentioned in one of my earlier posts, the early work of Renyi and Sulanke on random planar polygons was available only in German. This consists of three separate articles published over a couple of years. Now, courtesy of the efforts of Manfred Weis, English translations are available to the non-German-reading audience. What follows is the third in this series of articles.
Z. Wahrscheinlichkeitstheorie verw. Geb. 9, 146-157 (1968)
Random Convex Polygons in a Ring-shaped Region
by
A. Rényi and R. Sulanke
Received June 2nd 1967
1. Introduction
Let $K$ be a non-degenerated, finite convex region of the Euclidean plane and $B$ an arbitrary convex region that is contained in the interior of $K$. We chose $n$ random lines $g_1,\,\ldots,\,g_n$ that intersect $K$ but not $B$.
The $g_i$ shall be independent; their distribution shall be the Euclidean invariant line measure $\mu$ with density $dg$ (W. Blaschke $[1]$, § 2). By $H_i$ we denote the closed halfplane defined by $g_i$ that contains $B$. Then
$$(1.1)\quad\Pi_n=\cap_{i=1}^nH_i$$
is a random convex polygon that contains $B$ and is uniquely defined by the $g_i$. By $X_n$ we denote the number of corners of $\Pi_n$. We want to determine the asymptotic behavior of the mathematical expectation of the number of corners of $X_n$ under various assumptions on $B$.
In § 2 we establish the formulas for the probabilities that are to be investigated and derive some simple estimates that will be applied in §§ 3-5. Further we show that the probability for $\Pi_n$ not being closed, as well as the probability that $\Pi_n$ isn't contained in $K$ is of the order $O(\gamma^n)\ (0\lt\gamma\lt 1)$ tends to zero. In § 3 we consider the case that $B$ degenerates to a point and prove $E(X_n)\to\frac{\pi^2}{2}$ for $n\to+\infty$.
In the case that $B$ has a smooth boundary of limited curvature it holds true that $E(X_n)\sim \mathrm{const}.\,n^{1/3}$(theorem 4. § 4); if finally $B$ is a convex $r$-gon ($r\geqq2$; $r=2$ means that $B$ degenerates to a line segment ), that yields $E(X_n)\sim\frac{2}{3}r\,\log\,n$ (theorem 5, § 5). The order of magnitude with which $E(X_n)$ tends to infinity with $n$ in the last two cases therefore complies with the corresponding orders of magnitude for the case of the corners of the convex hull of $n$ points that are randomly chosen in $B$ (A. Rényi, R. Sulanke $[2]$).
We would like to warmly thank Mr. L. Berg for some hints to the calculations in § 5.
The result of § 3 may be interpreted as follows: We consider a system of $n$ random linear inequalities $a_kx+b_ky\leqq c_k$ ($k =1,\,2,\,\ldots,\,n$). The word "random" shall mean that the distribution of the lines $a_kx+b_ky=c_k$, that are independent from each other and that all shall hit the region $K$, is determined by the invariant line-measure and the point $B(x=0, y=0)\in K$ satisfies all inequalities. Let $X_n$ be the smallest number with the following property: There are $X_n$ of the inequalities such that every point $(x,y)$, that satisfies these $X_n$ inequalities, even satisfies all $n$ inequalities. Our result says that for $n\to\infty$ the expected value of the minimal number $X_n$ of the "critical" inequalities approaches $\pi^2/2$. Therefore one can expect that the solutionto a problem from linear programming with two unknowns and arbitrarily large number of linear inequalities with random data requires on average only a rather small number of steps when following one of the known procedures. So naturally the problem comes up, to treat the analogous task for an arbitrary number of unknowns ( that is for the intersection of random halfspaces of a $k$-dimensional space, $k=3\,,4\,\ldots$). That task was solved recently by Mr. Wolfgang M. Schmidt, when he proved that the average minimal number of "critical" inequalities, also in the $k$-dimensional case ($k=3,\,4,\,\ldots$) approaches a finite value $\lambda_k$ that only depends on $k$; but his prove only yields the existence of the numbers $\lambda_k$ and not their exact value. From the theorem of Mr. Wolfgang M. Schmidt follows the existence of the limit distribution of $X_n$ for the two-dimensional case that we consider. We hope to return to the explicit determination of that limit distribution in another work.
2. Basic formulas and simple estimations
Let $S_{ij}=g_i\cap g_j\ (i\ne j)$. The point $S_{ij}$ exists with probability 1.
If we now set $\varepsilon_{ij}=1$ if $S_{ij}$ is a corner of $\Pi_n$ and $\varepsilon_{ij}=0$ else, then it holds true that
$$(2.1)\quad X_n=\sum_{1\leqq i\lt j\leqq}\varepsilon_{ij}.$$
Let $W\,(n)$ be the probability for $S_{12}$ being a corner of $\Pi_n$. For reasons of symmetry the mathematical expectation turns out to be
$$(2.2)\quad E(X_n)=\binom{n}{2}\,W\,(n).$$
We first want to derive a general formula for $W\,(n)$. The point $S=S_{12}$ is a corner of $\Pi_n$ exactly if none of the lines $g_3,\,\ldots,\,g_n$ hits the convex hull $B_S$ of $B\cup S$. Let $l$ be the circumference of $K$, $b$ the one of $B$ and $l_S$ the one of $B_S$. According to Crofton's formula for convex regions (W. Blaschke $[1]$, § 3, (60))
$$(2.3)\quad \int_{g\,\cap K\ne\emptyset}dg=l$$
yields for the case $S\in K$
$$(2.4)\quad P\left(g_3\,\cap B_S\ne\emptyset\right)=\frac{l-l_S}{l-b}.$$
We decompose $W\,(n)$ into the two probabilities
$$(2.5)\quad W\,(n) = W_1(n)+W_2(n),$$
$$ (2.6)\quad W_1(n) = P\left(S\ \mathrm{corner\ of}\ \Pi_n,\, S\in K\right),$$
$$ (2.7)\quad W_1(n) = P\left(S\ \mathrm{corner\ of}\ \Pi_n,\, S\notin K\right).$$
It holds true that
$$(2.8)\quad W_1=\frac{1}{(l-b)^n}\iint_{g_1\,\cap\,g_2\,\cap \,K\ne\emptyset,\ (g_1\,\cup \,g_2)\cap B=\emptyset}(l-l_S)^{n-2}dg_1\,dg_2.$$
For $W_2(n)$ we give an estimation from which it will follow that $W_2(n)$ will be neglegible compared to $W_1(n)$. If $\mu$ denotes the line-measure then that yields
$$(2.9)\quad W_2\,(n)=\frac{1}{(l-b^n)}\iint_Df(S)^{n-2}dg_1\,dg_2$$
with $f(S)=\mu(g:\,g\,\cap\,B_S=\emptyset,\ g\,\cap\,K\ne\emptyset)$. Integration is over the region $D$ of all line-pairs $g_1,\,g_2$ with $g_1\cap\,K\ne\emptyset,\,g_2\,\cap\,K\ne\emptyset,\,g_1\,\cap\,g_2\,\cap\,K=\emptyset,\,(g_1\,\cup\,g_2)\,\cap\,B=\emptyset$. In order to estimate $f(S)$ we chose a boundary point $R$ of $K$ that lies in $B_S$; then $B_R\subset B_S$ and consequently
$$(2,10)\quad f(S)\leqq f(R)=l-l_R=(l-b)-(l_R-b).$$
By cutting off from $B_R$ by means of an appropriate support-line (i.e. tangent to the boundary) and isosceles triangle (fig. 1) we get
$$(2.11)\quad l_R-b\geqq 2a-c=2a\left(1-\sin\frac{\varphi}{2}\right).$$
If $r$ denotes the distance of the boundaries of $B$ and $K$, then obviously $a\geqq r\gt 0$; further we have, if $\varphi$ is the angle under which $B$ is seen from a boundary point of $K$, $0\leqq\varphi\leqq\varphi_0\le\pi$; because lies completely inside the inner of $K$. So it holds true that
$$(2.12)\quad l-l_b\geqq l_R-b\geqq2r\left(1-\sin\frac{\varphi_0}{2}\right)=\varepsilon\gt 0.$$
From $(2.10)$ and $(2.12)$ follows
$$(2.13)\quad\frac{f(S)}{l-b}\leqq\frac{l-b-\varepsilon}{l-b}=\gamma\ \text{with}\ 0\lt\gamma\lt 1,$$
where $\gamma$ only depends on $B$ and $K$. We get
$$(2.14)\quad W_2(n)=\frac{\gamma^{n-2}}{(l-b)^2}\iint_{\begin{matrix}g_1\,\cap\,K\ne \emptyset,\,g_2\,\cap\,K\ne\emptyset \\ g_1\,\cap\,g_2\,\cap\,K=\emptyset \end{matrix}}dg_1\,dg_2.$$
After a formula of Crofton (W.Blaschke, $[1]$, § 7 ) one gets for the integral $(2.14)$
$$(2.15)\quad\iint\,dg_1\,dg_2 =l^2-2\,\pi\,F$$
where $F$ is the area of $K$. It follows
$$(2.16)\quad W_2(n)=O(\gamma^n)\quad\mathrm{with}\quad 0\lt\gamma\lt1 \,.$$
If the region $B$ degenerates to a point, one gets $(2.16)$ by an even simpler estimation. The thoughts show in general that the portion of line-pairs $g_1,\,g_2$, whose intersection point $S$ lies outside a fixed convex neighborhood $U$ of $B$, is of the order of magnitude $O(\gamma^n)$ where $\gamma$ with $0\lt\gamma\lt 1$ of course depends on the neighborhood $U$.
Theorem 1. Let $B$ be a ( possibly degenrate ) convex region and $K$ a convex neighborhood of $B$. The probability for a corner of $\Pi_n$ to lie outside of $K$ satisfies the relation
$$(2.17)\quad P(\,\mathrm{corner}\ \mathrm{of}\ \Pi_n\notin K )=O(\gamma^n)\quad(0\lt\gamma\lt 1)$$
where $\gamma$ is a constant depending on $K$ and $B$.
It remains to evaluate $(2.8)$. To this end we carry out, after W. Blaschke $[1]$, § 6, (89), the substitution
$$(2.18)\quad dg_1\,dg_2=\left|\sin(\varphi_1-\varphi_2)\right|\,d\varphi_1\,d\varphi_2\,dS\,;$$
here $\varphi_1$, $\varphi_2$ are the angles of $g_1$, resp. $g_2$ with a given fixed direction and, $dS$ the density of the intersection point $S=g_1\cap\,g_2$. Because
$$(2.19)\quad\int_0^\alpha\int_0^\alpha\left|\sin(\varphi_1-\varphi_2)\right|\,d\varphi_1\,d\varphi_2\,dS=2(\alpha-\sin\,\alpha)$$
we get, because we have to integrate over $\psi_1\leqq\varphi_1,\,\varphi_2\leqq\psi_2$,
$$(2.20)\quad W_1(n)=\frac{2}{(l-b)^2}\int_{S\in K\setminus B}\left(1-\frac{l_S-b}{l-b}\right)^{n-2}\left(\alpha(S)-\sin\alpha(S)\right)\,dS\,;$$
here $\alpha=\psi_2-\psi_1=\pi-\omega$ and $\omega$ is the angle under which $B$ is seen from $S$ ($fig.\ 2$). The evaluation of the integral under various preconditions on $B$ is carried out in §§ 3-5.
$$fig.\ 2$$
Before that, we investigate the probability for $\Pi_n$ not being closed. It could be suspected that the polygon $\Pi_n$ doesn't enclose region $B$ also for larger $n$, i.e. isn't finite. That will happen particularly if $B$ comes close to the boundary of $K$ only at one side. Of course the probability that $\Pi_n$ isn't closed tends for $n\to\infty$ towards zero. We now want to estimate the order of magnitude of this convergence.
Let $\varphi_i$ be the angle of the normals of $g_i$, that are directed away from $B$, with a fixed direction. By $\psi_i$ we denote the ordered sample of the $\varphi_i$, i.e. the $\psi_i$ as well as the $\varphi_i$ are ordered according to magnitude: $0\leqq\psi_1\leqq\psi_2\leqq\cdots\leqq\psi_n\le 2\pi$. Let $\delta_i=\psi_i-\psi_{i-1}$ ($i=1,\,\ldots,\,n$), where $\psi_0=\psi_n-2\pi$ shall be set. The polygon is not closed exactly if one of the angles $\delta_i\geqq\pi$ is. Consequently we first have to calculate the distribution function of the angle $\varphi$ under the condition $g\,\cap\,K\ne\emptyset,\ g\,\cap\,B=\emptyset$. If $p_0(\varphi)$ is the support function of $B$ and $p_1(\varphi)$ the one of $K$, then it follows for $0\leqq x\leqq2\pi$
$$(2.21)\quad P(\varphi\leqq x)=\frac{1}{l-b}\int_0^x\int_{p_0(\varphi)}^{p_1(\varphi)}dp\,d\varphi=\frac{1}{l-b}\int_0^x\left(p_1(\varphi)-p_0(\varphi)\right)\,d\varphi\,.$$
This implies: If $p_1(\varphi)-p_0(\varphi)=r$ is constant, i.e. $K$is the outer parallel region at distance $r$ from $B$, then $\varphi$ is equally distributed on the unit circle and it holds true that
$$(2.22)\quad l-b=2\pi r$$
In this case the density of $\varphi$
$$(2.23)\quad f(\varphi)=\frac{p_1(\varphi)-p_(\varphi)}{l-b}$$
is constantly equal to $\frac{1}{2\pi}$; The probability for $\delta_i\geqq\pi$ is equal to the probability that $n-1$ angles $\psi_1,\,\ldots,\,\psi_{i-1},\,\psi_{i+1},\,\ldots,\,\psi_n$ lie between $\psi_i$ and $\psi_i+\pi$, i.e. equal to $2^{-(n-1)}$. As all possibilities $\delta_i\geqq\pi$ are mutually exclusive and equally likely, this yields (c.f. $[3]$)
$$(2.24)\quad P\,(\Pi_n\ \mathrm{not}\ \mathrm{closed})=\frac{n}{2^{n-1}}$$
(if $K$ is a parallel region of $B$).
In the general case it again holds true that
$$(2.25)\quad P\,(\Pi_n\ \mathrm{not}\ \mathrm{closed})=n\int_0^{2\pi}f(\varphi)\left(\int_{\varphi}^{\varphi+\pi}f(\Theta)\,d\Theta\right)^{n-1}d\varphi\,.$$
Now obviously
$$(2.26)\quad f(\varphi)=\frac{p_1(\varphi)-p_0(\varphi)}{l-b}\geqq c\gt0$$
therefore
$$(2.27)\quad \int_{\varphi}^{\varphi+\pi}f(\Theta)\,d\Theta\leqq 1-\pi\,c$$
where
$$(2.28)\quad \pi\,c\lt\int_0^{2\pi}f(\Theta)\,d\Theta=1$$
holds true. From $(2.25) and $(2.27)$ follows
Theorem 2. If $K$ is a parallel region of $B$ then the probability that $\Pi_n$ is not closed is governed by relation $(2.24)$. If $B$ is contained in the inner of $K$, then for this probability in the general case it results in
$$(2.29)\quad P(\Pi_n\ \mathrm{not}\ \mathrm{closed})\leqq n\gamma^{n-1}$$
where $\gamma\,(0\lt\gamma\lt1)$ is a constant that depends on $B$ and $K$.
3. Random polygons around a point
Let $B=O\,\in\,K$ be a fixed point. Then $b=0$ and $l_S=2\left|\,O\,S\,\right|$ is equal to twice the length of the line segment $O\,S$. from $(2.28)$ follows
$$(3.1)\quad W_1=\frac{1}{l^2}\iint_{g_1\,\cap\,g_2\,\cap\,K\ne\emptyset}\left(1-\frac{2\left|\,O\,S\,\right|}{l}\right)^{n-2}dg_1\,dg_2$$
The condition $g_i\,\cap\,O=\emptyset$ need not be taken into consideration because the set of all through a point has measure zero. From $(2.20)$ follows, because in our case $\alpha=\pi$:
$$(3.2)\quad W_1(n)=\frac{2\pi}{l^2}\int_{S\in K}\left(1-\frac{2\left|\,O\,S\,\right|}{l}\right)^{n-2}dS\,.$$
Let $0\lt r\lt\,l/2,\ r$ fixed. Then obviously
$$(3.3)\quad \frac{2\pi}{l^2}\int_{\begin{matrix}S\in K\\ \left|\,O\,S\,\right|\gt r\end{matrix}}\left(1-\frac{2\left|\,O\,S\,\right|}{l}\right)^{n-2}dS = O(\alpha^n),\quad 0\lt\alpha \lt1,$$
where $\alpha=1-(2r)/l$ has to be set. If $K_r$ denotes the circle of radius $r$ around $O,\ K_r\subset K$, it follows that
$$(3.4)\quad W_1(n)=\frac{2\pi}{l^2}\int_{S\in K_r}\left(1-\frac{2\left|\,O\,S\,\right|}{l}\right)^{n-2}dS + O(\alpha^n)$$
with $0\lt\alpha\lt1$. For polar coordinates $\varrho,\ \Theta$ we have $dS=\varrho\,d\varrho\,d\Theta$ and by a simple calculation we get
$$(3.5)\quad E(X_n)=\frac{n(n-1)}{2}W\,(n)=\frac{\pi^2}{2}+O(\gamma^n)\quad \mathrm{with}\quad 0\lt\gamma\lt 1\,.$$
Theorem 3. The mathmatical expectation of the number $X_n$ of corners of a random convex polygon $\Pi_n$ around a point $O$ of a convex set $K$ satisfies the relation $(3.5)$.
4. Ringshaped areal around a smooth region
Concerning $B$ we now assume that the boundary curve is convex and sufficiently often continuously differentiable. Formula $(2.20)$ has to be evaluated under that precondition. In order to estimate the values $\alpha(S)$ and $l_S-b$ we first chose appropriate coordinates $t,\,s$. On the boundary $\mathscr{B}$ of $B$ we introduce the arclength $s$ as the parameter. We orient $\mathscr{B}$ counterclockwise. Let $x=f\,(s),\ y=g\,(s)$ be the equation of $\mathscr{B},\ \mathfrak{t}=\lbrace f'(s),\,g'(s)\rbrace$ the tangential vector and $\mathfrak{n}=\lbrace g',\,-f'\rbrace$ the outer normal vector; the primes denote derivation with respect to $s$. It is then $[\mathfrak{n},\,\mathfrak{t}]=1$ for the determinant of $\mathfrak{n},\,\mathfrak{t}$. The normals
$$(4.1)\quad \frac{\partial(x,\,y)}{\partial(t,\,s)}=1+t\,k(s)\gt 0\quad\mathrm{for}\quad t\gt-\frac{1}{k(s)}\,;$$
here $k(s)\,\geqq\,0$ denotes the curvature of $\mathscr{B}$ in the point $S$. For $dS$ follows
$$(4.3)\quad dS=(1+t\,k(s))\,dt\,ds\,.$$
We now consider a fixed point $Y_0$ of $\mathscr{B}$, for example $s_0=0$, and draw from an outer point $S$ on the normal through $Y_0$ the tangents to $\mathscr{B}$, which shall touch $\mathscr{B}$ in the points $Y\,(\sigma_\alpha),\ \alpha=1,\,2$ (fig. 3). For calculating approximate expressions for the values $\sigma_\alpha$ and $\tau_\alpha=\left|Y_\alpha\,S\right|$ as a function of $t$, we express the curve $\mathscr{B}$ with respect to the accompanying bipod (i.e. in its local Frenet frame) $\mathfrak{n},\ \mathfrak{t}$ in point $Y_0$:
$$\quad\quad\mathfrak{x}=\mathfrak{t}\left(s-\frac{k^2}{3!}s^3-\frac{3k\,k'}{4!}+O(s^5)\right)$$
$$(4.4)$$
$$\quad\quad-\mathfrak{n}\left(\frac{k}{2!}s^2+\frac{k'}{3!}s^3+(k''-k^3)\frac{s^4}{4!}+O(s^5)\right)\,.$$
For the intersection point $S$ of the tangent at $\mathscr{B}$ in point $Y\,(\sigma_\alpha)$ with the normal through $Y_0$ we have to evaluate the relation
$$(4.5)\quad\mathfrak{\sigma}+\tau\,\mathfrak{x}'(\sigma)'=t\mathfrak{n}$$
If we take for $\tau$ an expansion
$$(4.6)\quad\tau=A\,\sigma+B\,\sigma^2+C\,\sigma^3+D\,\sigma^4+O(\sigma^5)$$
and enter it into $(4.5)$, we get, after partitioning into the components related to $\mathfrak{t}$, $\mathfrak{n}$, two scalar equations. From the $\mathfrak{t}$-component follows
$$(4.7)\quad \tau=-\sigma-\frac{k^2}{3}\sigma^3-\frac{3}{8}k\,k'\sigma^4+O(\sigma^5)\,.$$
By comparing the coefficients of the $\mathfrak{n}$-component one gets, when taking into account $(4.7)$:
$$(4.8)\quad t=\frac{k}{2}\sigma^2+\frac{k'}{3}\sigma^3+(3k''+5\,k^3)\,\frac{\sigma^4}{4!}+O(\sigma^5)\,.$$
If we now set $t=u^2$ then an ansatz analog to $\sigma=\sigma(u)$ in $(4.8)$:
$$(4.9)\quad\sigma_{1,\,2}(u)=\pm\sqrt{\frac{2}{k}}u-\frac{2}{3}\frac{k'}{k^2}u2\pm\frac{1}{3}\sqrt{\frac{k}{2}}\left(\frac{10}{3}\frac{k'^2}{k^4}\,-\,\frac{3}{2}\frac{k''}{k^3}-\frac{5}{2}\right)u^3+O(u^4)\,.$$
That expansion makes the precondition $k\gt0$ for $\mathscr{B}$ necessary; the boundary of $B$ must not contain a line-point (Translator's Note: I guess that "Streckpunkt" means a point where the curvature vanishes) and most of all no line segment. The two signs correspond to the two tangents from $S$ to $\mathscr{B}$. Now we can evaluate the integral $(2.20)$, taking into account $(4.3)$. Accounting for the signs of the calculated lengths (fig. 3) it hold true according to $(4.7)$ that:
$$(4.10)\quad l_S-b=(\tau_2+\sigma_2)-(\tau_1-\sigma_1)=\frac{k^2}{3}(\sigma_1^3-\sigma_2^3)+\frac{3}{8}k\,k'\,(\sigma_1^4-\sigma_2^4)+O(\sigma^5)\,.$$
Because of $(4.9)$ we get
$$(4.11)\quad l_S-b=\frac{4}{3}\sqrt{2\,k}\,u^3+O(u^5)\,.$$
For $\alpha-\sin\,\alpha$ we get because of
$$(4.12)\quad\alpha(s,t)=\int_{\sigma_2}^{\sigma_1}k(\sigma)\,d\sigma$$
and taking into account $(4.9)$
$$(4.13)\quad\alpha-\sin\,\alpha=\frac{1}{3!}\left(2\sqrt{2\,k}\,u\right)^3+O(u^4)\,.$$
The integral $(2.20)$ that shall be estimated becomes, because $u=t^{1/2}$, after inserting the obtained expressions $(4.3),\ (4.11),\ (4.13)$
$$W_1(n)=\frac{2}{(l-b)^2}\int_0^b\int_0^{h(s)}\left(1-\frac{4\sqrt{2\,k}\,t^{3/2}}{3\,(l-b)}+O(t^{5/2})\right)^{n-2}\left(\frac{8}{3!}\left(\sqrt{2\,k\,t}\right)^3+O(t^2)\right)(1+tk)\,dt\,ds\,.$$
If we now substitute
$$(4.14)\quad t=\left(\frac{3\,(l-b)}{4\sqrt{2\,k}}\frac{x}{n}\right)^{2/3}$$
that yields after some rearranging
$$(4.15)\quad W_1(n)=2\left(\frac{2}{3\,(l-b)} \right)^{1/3}\int_0^bk^{2/3}\int_0^\infty\left(1-\frac{x}{n}\right)^n\frac{x^{2/3}}{n^{5/3}}\,dx\,ds+O\left(\frac{1}{n^2}\right)\,.$$
From this follows
Theorem 4. Let $B$ be a convexr finite region with smooth boundary, whose curvature $k=k(s)$ is positive and finite. $B$ be in the inner of a convex set $K$; $l$ and $b$ be the circumference of $K$, resp. $B$. For the mathematical expectation of the number of corners of a random convex polygon* $\Pi_n$ around $B$ it then holds true that
$$(4.16)\quad E(X_n)=\left[\left(\frac{2}{3\,(l-b)}\right)^{1/3}\Gamma\left(\frac{5}{3}\right)\int_0^bk^{2/3}\,ds\right]n^{1/3}+O(1)\,.$$
Consequently the order of magnitude of the number of corners is the same as in the case of the convex hull of $n$ points that are randomly chosen in $B$ (cf A.\,Rényi, R.\, Sulanke $[2]$), the factors are however significantly different.
5. Ringshaped areal around a convex polygon
Let $B$ now be a convex $r$-gon. According to theorem 1 the random polygon $\Pi_n$ lies with high probability in an arbitrary, fixed convex surrounding $U$ of $B$; $U$ shall be selected in a way that all intersection points of non-adjacent sides of $B$ are located outside of $U$. The ring-shaped areal $U\,\setminus\,B$, for which the integral $(2.20)$ must be evaluated is partitioned by the sides of $B$ into $r$ corner-regions $E_i$ and $r$ side-regions $T_i$ (fig. 4), in which we carry out the integration separately.
$T$ be one of the side-regions with corners $A,\,A'$ at a side of length $2\,c=\left|\,A\,A'\,\right|$ . For $S\in T$ it holds true that
$$(5.1)\quad l_S-b=\left|\,S\,A\,\right|+\left|\,S\,A'\,\right|-\left|\,A\,A'\,\right|=2\,(a-c)\ ,$$
where a is the semi-major axis of the ellipse with focal points $A,\ A'$ through the point $S$. As coordinates of $S$ we chose $a$ and the distance $x$ of the projection of $S$ onto the major axis of the ellipse from its center. For the area-element $dS$ we obtain in these coordinates
$$(5.2)\quad dS=\frac{a^4-c^2x^2}{a^2\sqrt{(a^2-c^2)(a^2-x^2)}}\,dx\,da\,.$$
For the angle $\alpha$ that is inserted into $(2.20)$ the outer angles of the triangle $A\,A'\,S$ in $S_i$, one calculates
$$(5.3)\quad\sin\,\alpha=\frac{2\,a\,c\sqrt{(a^2-c^2)(a^2-x^2)}}{a^4-c^2x^2}=f(x,\,a)\,.$$
We now replace the region $T$ with a section of the half-circle over $A,\,A'$ that is adjacent to $A\,A'$ and lies in $U$ and in which $\alpha\leqq\pi/2$n; we will later estimate the error that is generated by this. The is determined by $f=1$; for $x,\,a$ we get the integration-region
$$(5.4)\quad c\leqq a\leqq\delta c,\quad\left|x\right|\leqq\frac{a}{c}\sqrt{2\,c^2-a^2}\,,$$
here $\delta\ (1\lt\delta\leqq\sqrt{2})$ is a number that is chosen in a way that the circle-segment lies in $U$. According to $(2.20)$ the integral
$$(5.5)\quad W=\frac{8\,c}{(l-b)^2}\int_c^{\delta\,c}\int_0^{(a/c)\sqrt{2\,c^2-a^2}}\left(1-\frac{2\,(a-c)}{l-b}\right)^{n-2}\left(\frac{\mathrm{arc}\sin\,f\ -\ f}{a\,f}\right)\,dx\,da$$
has to be calculated first. To that end we develop the inner integral
$$(5.6)\quad F(a) =\int_0^{(a/c)\sqrt{2\,c^2-a^2}}\frac{1}{f}(\mathrm{arc}\sin\,f\ -\ f)\,dx$$
according to powers of $a-c$ and set
$$(5.7)\quad\frac{1}{f}(\mathrm{arc}\sin\,f\ -\ f)=\frac{1}{6}f^2+R$$
The integral over the first part yields
$$(5.8)\quad\frac{1}{6}\int_0^{(a/c)\sqrt{2\,c^2-a^2}}f^2dx=-\frac{a^4-c^4}{6\,a^2c}\log(a-c)+O(a-c)\,.$$
For the rest $R$ we show
$$(5.9)\quad\int_0^{(a/c)\sqrt{2\,c^2-a^2}}R\,dx=O(a-c)\,.$$
It holds true that, if
$$\quad\mathrm{arc}\sin\,\xi=\sum_{v=0}^\infty c_v\xi^{2v+1}$$
is set,
$$(5.10)\quad 0\lt R=\sum_{v=2}^\infty c_vf^{2v}\leqq f^4\sum_{v=2}^\infty c_v=f^4\left(\frac{\pi}{2}-\frac{7}{6}\right)\,.$$
Therefore it suffices to prove
$$\quad\int_0^{(a/c)\sqrt{2\,c^2-a^2}}f^4dx=(a-c)\,,$$
that is,
$$(5.11)\quad\int_0^{(a/c)\sqrt{2\,c^2-a^2}}\frac{(a^2-c^2)^2}{(a^4-c^2\,x^2)^4}dx=O\left(\frac{1}{a-c}\right)\,.$$
Now, because $0\leqq x\leqq c\leqq a$
$$(5.12)\quad\frac{(a-x)^2}{16\,a^2\,(a^2-c\,x)^4}\leqq\frac{(a^2-x^2)^2}{(a^4-c^2\,x^2)^4}\leqq\frac{4\,(a-x)^2}{a^6\,(a^2-c\,x)^4}\,.$$
Therefore it remains to show
$$(5.13)\quad\int_0^{(a/c)\sqrt{2\,c^2-a^2}}\frac{(a^2-x^2)^2}{(a^2-c\,x)^4}dx=O\left(\frac{1}{a-c}\right)$$
One easily obtains that relationeasily via the substitution $a^2-c\,x=t$ and some simple estimations. From $(5.6)-(5.9)$ we get
$$(5.14)\quad F(a)=-\frac{a^4-c^4}{6\,a^2\,c}\log\,(a-c)+O(a-c)\,.$$
According to $(5.5)$ it therefore holds true that
$$(5.15)\quad=\frac{-4}{3\,(l-b)^2}\int_0^{\delta c}\left(1-\frac{2\,(a-c)}{(l-b)}\right)^{n-2}\left(\frac{a^4-c^4}{a^3}\log\,(a-c)+O(a-c)\right)\,da\,.$$
The substitution
$$\quad\frac{2\,(a-c)}{l-b}=\frac{Z}{n-2}$$
yields after some simple calculations because of
$$(5.16)\quad\int_c^{\delta c}\left(1-\frac{2\,(a-c)}{(l-b)}\right)^{n-2}\cdot\, O(a-c)\,da=O\left(\frac{1}{n^2}\right)$$
the relation
$$(5.17)\quad W=\frac{4}{3\,n\,(n-1)}\log\,(n-2)+O\left(\frac{1}{n^2}\right)\,.$$
When replacing the side-region $T$ with a half-circle section, we have either integrated a region that is bound by the line of the neighboring side and a circular arc, too much (fig. 5 a) or too little (fig. 5 b).
We show that the errors that are generated by this are of the order of magnitude $O(1/n^2)$. Let
$$(5.18)\quad x(a)=c+(a-c)\,\gamma+O\left((a-c)^2\right)$$
be a representation of the neighboring side. The error in the first case (fig. 5 a) then is
$$(5.19)\quad\Delta=q\int_c^{\delta c}\left(1-\frac{2\,(a-c)}{(l-b)}\right)^{n-2}\frac{1}{a^2\,\sqrt{a^2-c^2}}\int_{x(a)}^{(a/c)\sqrt{2\,c^2-a^2}}(\alpha-\sin\,\alpha)\frac{a^4-c^2\,x^2}{\sqrt{a^2-x^2}}\,dx\,da\,;$$
here $q$ denotes a constant. Because of $(5.16)$ it suffices to show that
$$(5.20)\quad I(a)=\int_{x(a)}^{(a/c)\sqrt{2\,c^2-a^2}}(\alpha-\sin\,\alpha)\frac{a^4-c^2\,x^2}{\sqrt{a^2-x^2}}dx=O\left((a-c)^{3/2}\right)$$
holds. Now $\alpha-\sin\,\alpha$ is bound, so that it suffices to prove
$$(5.21)\quad\int_{x(a)}^{(a/c)\sqrt{2\,c^2-a^2}}\frac{a^4-c^2\,x^2}{\sqrt{a^2-x^2}}dx=O\left((a-c)^{3/2}\right)$$
For the indefinite integral
$$(5.22)\quad Q(x)=\int\frac{a^4-c^2\,x^2}{\sqrt{a^2-x^2}}dx=\frac{c^2\,x}{2}\sqrt{a^2-x^2}-a^2\,\left(a^2-\frac{c^2}{2}\right)\,\mathrm{arc}\cos\,\frac{x}{a}$$
we get, because $\mathrm{arc}\cos\frac{x}{a}=\mathrm{arc}\sin\frac{1}{a}\sqrt{a^2-x^2}$ the series expansion
$$(5.23)\quad Q(x)=\frac{1}{2}\sqrt{a^2-x^2}\,(c^2x-a^3+a(c^2-a^2)+O(a^2-x^2))\,.$$
Substituting the lower bound $x=x(a)$ according to $(5.18)$ immediately yields
$$(5.24)\quad Q(x(a))=O\left((a-c)^{3/2}\right)$$
But the same also holds for the upper bound, because the expression that is to be substituted also is of the form $(5.18)$, of course with a different constant $\gamma$. Quite analogously one also estimates the second error (fig. 5 b). Thus we may replace in $(5.17)$ the half-circle section with the side-region $T$ and alltogether get
$$(5.25)\quad W\,(T)=\frac{4}{3\,n\,(n-1)}\log\,n+O\left(\frac{1}{n^2}\right)\,.$$
This formula is also valid if $B$ degenerates to a line-segment.
Now we consider the corner-region $E=E_i$ at the corner $A_i$ of $B$. We now introduce, as in $(5.2)$, semi-elliptic coordinates; only the basis is now the line-segment $A_{i-1}\,A_{i+1}$, whose length will again be denoted by $2\,c$. With
$$\quad d=\frac{1}{2}(\left|A_{i-1}A_i\right|+\left|A_i A_{i+1}\right|)$$
we have for the difference of distance
$$(5.26)\quad l_S-b=2\,(a-d)\,.$$
Therefore, according to $(2.20)$ and $(5.2)$, for the corresponding probablity
$$(5.27)\quad W\,(E)=\frac{2}{(l-b)^2}\int_d^{a_0}\left(1-\frac{2\,(a-d)}{(l-b)}\right)^{n-2}\int_{x_1(a)}^{x_2(a)}(\alpha-\sin\,\alpha)\frac{a^4-c^2\,x^2}{a^2\sqrt{(a^2-c^2)(a^2-x^2)}}\,dx\,da\,.$$
Here $x_1(a),\ x_2(a)$ denote the $x$-coordinates of the intersection point of the ellipse that belongs to $a$ with the elongations of the sides that are adjacent to $A_i$ beyond $A_i$. As we only consider a sufficiently small surrounding of $B$, it holds true that
$$\quad\left|x\right|\leqq\max\left(\left|x_1(a)\right|,\,\left|x_1(a)\right|\right)\lt a,\quad c\lt d\leqq a\,.$$
From the mean value theorem follows, because of the boudedness and continuity of the integrand,
$$(5.28)\quad \int_{x_1(a)}^{x_2(a)}(\alpha-\sin\,\alpha)\frac{a^4-c^2\,x^2}{a^2\sqrt{(a^2-c^2)(a^2-x^2)}}dx=M(a)\,(x_2(a)-x_1(a))\,,$$
where $M(a)$ remains bounded for all $a$ from the range under consideration: $\left|\,M(a)\,\right|\leqq M_0\,.$
For $a=d$ it holds $x_1(d)=x_2(d)$. The functions $x_i(a)$ are sufficiently often differentiable in location $d$. It follows
$$(5.29)\quad x_2(a)-x_1(a)=h_0(a-d)+O\left((a-d)^2\right)\,,$$
where $h_0$ is a certain constant. If one inserts $(5.28),\ (5.29)$ into $(5.27)$, then according to $(5.16)$ follows immediately
$$(5.30)\quad W\,(E)=O\left(\frac{1}{n^2}\right)\,.$$
Because of theorem 1, $(5.25)$ and $(5.30)$ we get the following
Theorem 5. Let $B$ a convex $r$-gon, $r\geqq2$, that lies in the inner of $K$.For the mathematical expectation of the number of corners $X_n$ of a random polygon $\Pi_n$ it holds true that
$$\quad E(X_n)=\frac{2\,r}{3}\,\log n+O(1)\,.$$
The principal term of this formula matches the corresponding principal term of theorem 1of our work $[2]$ on the convex hull of random points that lie in a polygon.
References
1. Blaschke, W.: Vorlesungen über Integralgeometrie. 3. Aufl. Berlin: VEB Deutscher Verlag der Wissenschaften 1955.
2. Rényi, A., u. R. Sulanke: Über die konvexe Hülle von $n$ zufällig gewählten Punkten. Z. Wahrscheinlichkeitstheorie verw. Geb. 2, 75-84 (1963).
3. Stevens, W.L.: Solution to a geometrical problem in probability. Ann. Eugenics 9, 315-320 (1939.
Dr. R. Sulanke
Mathematisches Institut der
Humboldt-Universität
Berlin
Prof. Dr. A. Rényi
Mathematisches Institut der Ungarischen
Akademie der Wissenschaften
Reáltonada u. 13-15
Budapest V, Ungarn
Z. Wahrscheinlichkeitstheorie verw. Geb. 9, 146-157 (1968)
Random Convex Polygons in a Ring-shaped Region
by
A. Rényi and R. Sulanke
Received June 2nd 1967
1. Introduction
Let $K$ be a non-degenerated, finite convex region of the Euclidean plane and $B$ an arbitrary convex region that is contained in the interior of $K$. We chose $n$ random lines $g_1,\,\ldots,\,g_n$ that intersect $K$ but not $B$.
The $g_i$ shall be independent; their distribution shall be the Euclidean invariant line measure $\mu$ with density $dg$ (W. Blaschke $[1]$, § 2). By $H_i$ we denote the closed halfplane defined by $g_i$ that contains $B$. Then
$$(1.1)\quad\Pi_n=\cap_{i=1}^nH_i$$
is a random convex polygon that contains $B$ and is uniquely defined by the $g_i$. By $X_n$ we denote the number of corners of $\Pi_n$. We want to determine the asymptotic behavior of the mathematical expectation of the number of corners of $X_n$ under various assumptions on $B$.
In § 2 we establish the formulas for the probabilities that are to be investigated and derive some simple estimates that will be applied in §§ 3-5. Further we show that the probability for $\Pi_n$ not being closed, as well as the probability that $\Pi_n$ isn't contained in $K$ is of the order $O(\gamma^n)\ (0\lt\gamma\lt 1)$ tends to zero. In § 3 we consider the case that $B$ degenerates to a point and prove $E(X_n)\to\frac{\pi^2}{2}$ for $n\to+\infty$.
In the case that $B$ has a smooth boundary of limited curvature it holds true that $E(X_n)\sim \mathrm{const}.\,n^{1/3}$(theorem 4. § 4); if finally $B$ is a convex $r$-gon ($r\geqq2$; $r=2$ means that $B$ degenerates to a line segment ), that yields $E(X_n)\sim\frac{2}{3}r\,\log\,n$ (theorem 5, § 5). The order of magnitude with which $E(X_n)$ tends to infinity with $n$ in the last two cases therefore complies with the corresponding orders of magnitude for the case of the corners of the convex hull of $n$ points that are randomly chosen in $B$ (A. Rényi, R. Sulanke $[2]$).
We would like to warmly thank Mr. L. Berg for some hints to the calculations in § 5.
The result of § 3 may be interpreted as follows: We consider a system of $n$ random linear inequalities $a_kx+b_ky\leqq c_k$ ($k =1,\,2,\,\ldots,\,n$). The word "random" shall mean that the distribution of the lines $a_kx+b_ky=c_k$, that are independent from each other and that all shall hit the region $K$, is determined by the invariant line-measure and the point $B(x=0, y=0)\in K$ satisfies all inequalities. Let $X_n$ be the smallest number with the following property: There are $X_n$ of the inequalities such that every point $(x,y)$, that satisfies these $X_n$ inequalities, even satisfies all $n$ inequalities. Our result says that for $n\to\infty$ the expected value of the minimal number $X_n$ of the "critical" inequalities approaches $\pi^2/2$. Therefore one can expect that the solutionto a problem from linear programming with two unknowns and arbitrarily large number of linear inequalities with random data requires on average only a rather small number of steps when following one of the known procedures. So naturally the problem comes up, to treat the analogous task for an arbitrary number of unknowns ( that is for the intersection of random halfspaces of a $k$-dimensional space, $k=3\,,4\,\ldots$). That task was solved recently by Mr. Wolfgang M. Schmidt, when he proved that the average minimal number of "critical" inequalities, also in the $k$-dimensional case ($k=3,\,4,\,\ldots$) approaches a finite value $\lambda_k$ that only depends on $k$; but his prove only yields the existence of the numbers $\lambda_k$ and not their exact value. From the theorem of Mr. Wolfgang M. Schmidt follows the existence of the limit distribution of $X_n$ for the two-dimensional case that we consider. We hope to return to the explicit determination of that limit distribution in another work.
2. Basic formulas and simple estimations
Let $S_{ij}=g_i\cap g_j\ (i\ne j)$. The point $S_{ij}$ exists with probability 1.
If we now set $\varepsilon_{ij}=1$ if $S_{ij}$ is a corner of $\Pi_n$ and $\varepsilon_{ij}=0$ else, then it holds true that
$$(2.1)\quad X_n=\sum_{1\leqq i\lt j\leqq}\varepsilon_{ij}.$$
Let $W\,(n)$ be the probability for $S_{12}$ being a corner of $\Pi_n$. For reasons of symmetry the mathematical expectation turns out to be
$$(2.2)\quad E(X_n)=\binom{n}{2}\,W\,(n).$$
We first want to derive a general formula for $W\,(n)$. The point $S=S_{12}$ is a corner of $\Pi_n$ exactly if none of the lines $g_3,\,\ldots,\,g_n$ hits the convex hull $B_S$ of $B\cup S$. Let $l$ be the circumference of $K$, $b$ the one of $B$ and $l_S$ the one of $B_S$. According to Crofton's formula for convex regions (W. Blaschke $[1]$, § 3, (60))
$$(2.3)\quad \int_{g\,\cap K\ne\emptyset}dg=l$$
yields for the case $S\in K$
$$(2.4)\quad P\left(g_3\,\cap B_S\ne\emptyset\right)=\frac{l-l_S}{l-b}.$$
We decompose $W\,(n)$ into the two probabilities
$$(2.5)\quad W\,(n) = W_1(n)+W_2(n),$$
$$ (2.6)\quad W_1(n) = P\left(S\ \mathrm{corner\ of}\ \Pi_n,\, S\in K\right),$$
$$ (2.7)\quad W_1(n) = P\left(S\ \mathrm{corner\ of}\ \Pi_n,\, S\notin K\right).$$
It holds true that
$$(2.8)\quad W_1=\frac{1}{(l-b)^n}\iint_{g_1\,\cap\,g_2\,\cap \,K\ne\emptyset,\ (g_1\,\cup \,g_2)\cap B=\emptyset}(l-l_S)^{n-2}dg_1\,dg_2.$$
For $W_2(n)$ we give an estimation from which it will follow that $W_2(n)$ will be neglegible compared to $W_1(n)$. If $\mu$ denotes the line-measure then that yields
$$(2.9)\quad W_2\,(n)=\frac{1}{(l-b^n)}\iint_Df(S)^{n-2}dg_1\,dg_2$$
with $f(S)=\mu(g:\,g\,\cap\,B_S=\emptyset,\ g\,\cap\,K\ne\emptyset)$. Integration is over the region $D$ of all line-pairs $g_1,\,g_2$ with $g_1\cap\,K\ne\emptyset,\,g_2\,\cap\,K\ne\emptyset,\,g_1\,\cap\,g_2\,\cap\,K=\emptyset,\,(g_1\,\cup\,g_2)\,\cap\,B=\emptyset$. In order to estimate $f(S)$ we chose a boundary point $R$ of $K$ that lies in $B_S$; then $B_R\subset B_S$ and consequently
$$(2,10)\quad f(S)\leqq f(R)=l-l_R=(l-b)-(l_R-b).$$
By cutting off from $B_R$ by means of an appropriate support-line (i.e. tangent to the boundary) and isosceles triangle (fig. 1) we get
$$(2.11)\quad l_R-b\geqq 2a-c=2a\left(1-\sin\frac{\varphi}{2}\right).$$
If $r$ denotes the distance of the boundaries of $B$ and $K$, then obviously $a\geqq r\gt 0$; further we have, if $\varphi$ is the angle under which $B$ is seen from a boundary point of $K$, $0\leqq\varphi\leqq\varphi_0\le\pi$; because lies completely inside the inner of $K$. So it holds true that
$$(2.12)\quad l-l_b\geqq l_R-b\geqq2r\left(1-\sin\frac{\varphi_0}{2}\right)=\varepsilon\gt 0.$$
From $(2.10)$ and $(2.12)$ follows
$$(2.13)\quad\frac{f(S)}{l-b}\leqq\frac{l-b-\varepsilon}{l-b}=\gamma\ \text{with}\ 0\lt\gamma\lt 1,$$
where $\gamma$ only depends on $B$ and $K$. We get
$$(2.14)\quad W_2(n)=\frac{\gamma^{n-2}}{(l-b)^2}\iint_{\begin{matrix}g_1\,\cap\,K\ne \emptyset,\,g_2\,\cap\,K\ne\emptyset \\ g_1\,\cap\,g_2\,\cap\,K=\emptyset \end{matrix}}dg_1\,dg_2.$$
After a formula of Crofton (W.Blaschke, $[1]$, § 7 ) one gets for the integral $(2.14)$
$$(2.15)\quad\iint\,dg_1\,dg_2 =l^2-2\,\pi\,F$$
where $F$ is the area of $K$. It follows
$$(2.16)\quad W_2(n)=O(\gamma^n)\quad\mathrm{with}\quad 0\lt\gamma\lt1 \,.$$
If the region $B$ degenerates to a point, one gets $(2.16)$ by an even simpler estimation. The thoughts show in general that the portion of line-pairs $g_1,\,g_2$, whose intersection point $S$ lies outside a fixed convex neighborhood $U$ of $B$, is of the order of magnitude $O(\gamma^n)$ where $\gamma$ with $0\lt\gamma\lt 1$ of course depends on the neighborhood $U$.
Theorem 1. Let $B$ be a ( possibly degenrate ) convex region and $K$ a convex neighborhood of $B$. The probability for a corner of $\Pi_n$ to lie outside of $K$ satisfies the relation
$$(2.17)\quad P(\,\mathrm{corner}\ \mathrm{of}\ \Pi_n\notin K )=O(\gamma^n)\quad(0\lt\gamma\lt 1)$$
where $\gamma$ is a constant depending on $K$ and $B$.
It remains to evaluate $(2.8)$. To this end we carry out, after W. Blaschke $[1]$, § 6, (89), the substitution
$$(2.18)\quad dg_1\,dg_2=\left|\sin(\varphi_1-\varphi_2)\right|\,d\varphi_1\,d\varphi_2\,dS\,;$$
here $\varphi_1$, $\varphi_2$ are the angles of $g_1$, resp. $g_2$ with a given fixed direction and, $dS$ the density of the intersection point $S=g_1\cap\,g_2$. Because
$$(2.19)\quad\int_0^\alpha\int_0^\alpha\left|\sin(\varphi_1-\varphi_2)\right|\,d\varphi_1\,d\varphi_2\,dS=2(\alpha-\sin\,\alpha)$$
we get, because we have to integrate over $\psi_1\leqq\varphi_1,\,\varphi_2\leqq\psi_2$,
$$(2.20)\quad W_1(n)=\frac{2}{(l-b)^2}\int_{S\in K\setminus B}\left(1-\frac{l_S-b}{l-b}\right)^{n-2}\left(\alpha(S)-\sin\alpha(S)\right)\,dS\,;$$
here $\alpha=\psi_2-\psi_1=\pi-\omega$ and $\omega$ is the angle under which $B$ is seen from $S$ ($fig.\ 2$). The evaluation of the integral under various preconditions on $B$ is carried out in §§ 3-5.
$$fig.\ 2$$
Before that, we investigate the probability for $\Pi_n$ not being closed. It could be suspected that the polygon $\Pi_n$ doesn't enclose region $B$ also for larger $n$, i.e. isn't finite. That will happen particularly if $B$ comes close to the boundary of $K$ only at one side. Of course the probability that $\Pi_n$ isn't closed tends for $n\to\infty$ towards zero. We now want to estimate the order of magnitude of this convergence.
Let $\varphi_i$ be the angle of the normals of $g_i$, that are directed away from $B$, with a fixed direction. By $\psi_i$ we denote the ordered sample of the $\varphi_i$, i.e. the $\psi_i$ as well as the $\varphi_i$ are ordered according to magnitude: $0\leqq\psi_1\leqq\psi_2\leqq\cdots\leqq\psi_n\le 2\pi$. Let $\delta_i=\psi_i-\psi_{i-1}$ ($i=1,\,\ldots,\,n$), where $\psi_0=\psi_n-2\pi$ shall be set. The polygon is not closed exactly if one of the angles $\delta_i\geqq\pi$ is. Consequently we first have to calculate the distribution function of the angle $\varphi$ under the condition $g\,\cap\,K\ne\emptyset,\ g\,\cap\,B=\emptyset$. If $p_0(\varphi)$ is the support function of $B$ and $p_1(\varphi)$ the one of $K$, then it follows for $0\leqq x\leqq2\pi$
$$(2.21)\quad P(\varphi\leqq x)=\frac{1}{l-b}\int_0^x\int_{p_0(\varphi)}^{p_1(\varphi)}dp\,d\varphi=\frac{1}{l-b}\int_0^x\left(p_1(\varphi)-p_0(\varphi)\right)\,d\varphi\,.$$
This implies: If $p_1(\varphi)-p_0(\varphi)=r$ is constant, i.e. $K$is the outer parallel region at distance $r$ from $B$, then $\varphi$ is equally distributed on the unit circle and it holds true that
$$(2.22)\quad l-b=2\pi r$$
In this case the density of $\varphi$
$$(2.23)\quad f(\varphi)=\frac{p_1(\varphi)-p_(\varphi)}{l-b}$$
is constantly equal to $\frac{1}{2\pi}$; The probability for $\delta_i\geqq\pi$ is equal to the probability that $n-1$ angles $\psi_1,\,\ldots,\,\psi_{i-1},\,\psi_{i+1},\,\ldots,\,\psi_n$ lie between $\psi_i$ and $\psi_i+\pi$, i.e. equal to $2^{-(n-1)}$. As all possibilities $\delta_i\geqq\pi$ are mutually exclusive and equally likely, this yields (c.f. $[3]$)
$$(2.24)\quad P\,(\Pi_n\ \mathrm{not}\ \mathrm{closed})=\frac{n}{2^{n-1}}$$
(if $K$ is a parallel region of $B$).
In the general case it again holds true that
$$(2.25)\quad P\,(\Pi_n\ \mathrm{not}\ \mathrm{closed})=n\int_0^{2\pi}f(\varphi)\left(\int_{\varphi}^{\varphi+\pi}f(\Theta)\,d\Theta\right)^{n-1}d\varphi\,.$$
Now obviously
$$(2.26)\quad f(\varphi)=\frac{p_1(\varphi)-p_0(\varphi)}{l-b}\geqq c\gt0$$
therefore
$$(2.27)\quad \int_{\varphi}^{\varphi+\pi}f(\Theta)\,d\Theta\leqq 1-\pi\,c$$
where
$$(2.28)\quad \pi\,c\lt\int_0^{2\pi}f(\Theta)\,d\Theta=1$$
holds true. From $(2.25) and $(2.27)$ follows
Theorem 2. If $K$ is a parallel region of $B$ then the probability that $\Pi_n$ is not closed is governed by relation $(2.24)$. If $B$ is contained in the inner of $K$, then for this probability in the general case it results in
$$(2.29)\quad P(\Pi_n\ \mathrm{not}\ \mathrm{closed})\leqq n\gamma^{n-1}$$
where $\gamma\,(0\lt\gamma\lt1)$ is a constant that depends on $B$ and $K$.
3. Random polygons around a point
Let $B=O\,\in\,K$ be a fixed point. Then $b=0$ and $l_S=2\left|\,O\,S\,\right|$ is equal to twice the length of the line segment $O\,S$. from $(2.28)$ follows
$$(3.1)\quad W_1=\frac{1}{l^2}\iint_{g_1\,\cap\,g_2\,\cap\,K\ne\emptyset}\left(1-\frac{2\left|\,O\,S\,\right|}{l}\right)^{n-2}dg_1\,dg_2$$
The condition $g_i\,\cap\,O=\emptyset$ need not be taken into consideration because the set of all through a point has measure zero. From $(2.20)$ follows, because in our case $\alpha=\pi$:
$$(3.2)\quad W_1(n)=\frac{2\pi}{l^2}\int_{S\in K}\left(1-\frac{2\left|\,O\,S\,\right|}{l}\right)^{n-2}dS\,.$$
Let $0\lt r\lt\,l/2,\ r$ fixed. Then obviously
$$(3.3)\quad \frac{2\pi}{l^2}\int_{\begin{matrix}S\in K\\ \left|\,O\,S\,\right|\gt r\end{matrix}}\left(1-\frac{2\left|\,O\,S\,\right|}{l}\right)^{n-2}dS = O(\alpha^n),\quad 0\lt\alpha \lt1,$$
where $\alpha=1-(2r)/l$ has to be set. If $K_r$ denotes the circle of radius $r$ around $O,\ K_r\subset K$, it follows that
$$(3.4)\quad W_1(n)=\frac{2\pi}{l^2}\int_{S\in K_r}\left(1-\frac{2\left|\,O\,S\,\right|}{l}\right)^{n-2}dS + O(\alpha^n)$$
with $0\lt\alpha\lt1$. For polar coordinates $\varrho,\ \Theta$ we have $dS=\varrho\,d\varrho\,d\Theta$ and by a simple calculation we get
$$(3.5)\quad E(X_n)=\frac{n(n-1)}{2}W\,(n)=\frac{\pi^2}{2}+O(\gamma^n)\quad \mathrm{with}\quad 0\lt\gamma\lt 1\,.$$
Theorem 3. The mathmatical expectation of the number $X_n$ of corners of a random convex polygon $\Pi_n$ around a point $O$ of a convex set $K$ satisfies the relation $(3.5)$.
4. Ringshaped areal around a smooth region
Concerning $B$ we now assume that the boundary curve is convex and sufficiently often continuously differentiable. Formula $(2.20)$ has to be evaluated under that precondition. In order to estimate the values $\alpha(S)$ and $l_S-b$ we first chose appropriate coordinates $t,\,s$. On the boundary $\mathscr{B}$ of $B$ we introduce the arclength $s$ as the parameter. We orient $\mathscr{B}$ counterclockwise. Let $x=f\,(s),\ y=g\,(s)$ be the equation of $\mathscr{B},\ \mathfrak{t}=\lbrace f'(s),\,g'(s)\rbrace$ the tangential vector and $\mathfrak{n}=\lbrace g',\,-f'\rbrace$ the outer normal vector; the primes denote derivation with respect to $s$. It is then $[\mathfrak{n},\,\mathfrak{t}]=1$ for the determinant of $\mathfrak{n},\,\mathfrak{t}$. The normals
$$(4.1)\quad \frac{\partial(x,\,y)}{\partial(t,\,s)}=1+t\,k(s)\gt 0\quad\mathrm{for}\quad t\gt-\frac{1}{k(s)}\,;$$
here $k(s)\,\geqq\,0$ denotes the curvature of $\mathscr{B}$ in the point $S$. For $dS$ follows
$$(4.3)\quad dS=(1+t\,k(s))\,dt\,ds\,.$$
We now consider a fixed point $Y_0$ of $\mathscr{B}$, for example $s_0=0$, and draw from an outer point $S$ on the normal through $Y_0$ the tangents to $\mathscr{B}$, which shall touch $\mathscr{B}$ in the points $Y\,(\sigma_\alpha),\ \alpha=1,\,2$ (fig. 3). For calculating approximate expressions for the values $\sigma_\alpha$ and $\tau_\alpha=\left|Y_\alpha\,S\right|$ as a function of $t$, we express the curve $\mathscr{B}$ with respect to the accompanying bipod (i.e. in its local Frenet frame) $\mathfrak{n},\ \mathfrak{t}$ in point $Y_0$:
$$\quad\quad\mathfrak{x}=\mathfrak{t}\left(s-\frac{k^2}{3!}s^3-\frac{3k\,k'}{4!}+O(s^5)\right)$$
$$(4.4)$$
$$\quad\quad-\mathfrak{n}\left(\frac{k}{2!}s^2+\frac{k'}{3!}s^3+(k''-k^3)\frac{s^4}{4!}+O(s^5)\right)\,.$$
For the intersection point $S$ of the tangent at $\mathscr{B}$ in point $Y\,(\sigma_\alpha)$ with the normal through $Y_0$ we have to evaluate the relation
$$(4.5)\quad\mathfrak{\sigma}+\tau\,\mathfrak{x}'(\sigma)'=t\mathfrak{n}$$
If we take for $\tau$ an expansion
$$(4.6)\quad\tau=A\,\sigma+B\,\sigma^2+C\,\sigma^3+D\,\sigma^4+O(\sigma^5)$$
and enter it into $(4.5)$, we get, after partitioning into the components related to $\mathfrak{t}$, $\mathfrak{n}$, two scalar equations. From the $\mathfrak{t}$-component follows
$$(4.7)\quad \tau=-\sigma-\frac{k^2}{3}\sigma^3-\frac{3}{8}k\,k'\sigma^4+O(\sigma^5)\,.$$
By comparing the coefficients of the $\mathfrak{n}$-component one gets, when taking into account $(4.7)$:
$$(4.8)\quad t=\frac{k}{2}\sigma^2+\frac{k'}{3}\sigma^3+(3k''+5\,k^3)\,\frac{\sigma^4}{4!}+O(\sigma^5)\,.$$
If we now set $t=u^2$ then an ansatz analog to $\sigma=\sigma(u)$ in $(4.8)$:
$$(4.9)\quad\sigma_{1,\,2}(u)=\pm\sqrt{\frac{2}{k}}u-\frac{2}{3}\frac{k'}{k^2}u2\pm\frac{1}{3}\sqrt{\frac{k}{2}}\left(\frac{10}{3}\frac{k'^2}{k^4}\,-\,\frac{3}{2}\frac{k''}{k^3}-\frac{5}{2}\right)u^3+O(u^4)\,.$$
That expansion makes the precondition $k\gt0$ for $\mathscr{B}$ necessary; the boundary of $B$ must not contain a line-point (Translator's Note: I guess that "Streckpunkt" means a point where the curvature vanishes) and most of all no line segment. The two signs correspond to the two tangents from $S$ to $\mathscr{B}$. Now we can evaluate the integral $(2.20)$, taking into account $(4.3)$. Accounting for the signs of the calculated lengths (fig. 3) it hold true according to $(4.7)$ that:
$$(4.10)\quad l_S-b=(\tau_2+\sigma_2)-(\tau_1-\sigma_1)=\frac{k^2}{3}(\sigma_1^3-\sigma_2^3)+\frac{3}{8}k\,k'\,(\sigma_1^4-\sigma_2^4)+O(\sigma^5)\,.$$
Because of $(4.9)$ we get
$$(4.11)\quad l_S-b=\frac{4}{3}\sqrt{2\,k}\,u^3+O(u^5)\,.$$
For $\alpha-\sin\,\alpha$ we get because of
$$(4.12)\quad\alpha(s,t)=\int_{\sigma_2}^{\sigma_1}k(\sigma)\,d\sigma$$
and taking into account $(4.9)$
$$(4.13)\quad\alpha-\sin\,\alpha=\frac{1}{3!}\left(2\sqrt{2\,k}\,u\right)^3+O(u^4)\,.$$
The integral $(2.20)$ that shall be estimated becomes, because $u=t^{1/2}$, after inserting the obtained expressions $(4.3),\ (4.11),\ (4.13)$
$$W_1(n)=\frac{2}{(l-b)^2}\int_0^b\int_0^{h(s)}\left(1-\frac{4\sqrt{2\,k}\,t^{3/2}}{3\,(l-b)}+O(t^{5/2})\right)^{n-2}\left(\frac{8}{3!}\left(\sqrt{2\,k\,t}\right)^3+O(t^2)\right)(1+tk)\,dt\,ds\,.$$
If we now substitute
$$(4.14)\quad t=\left(\frac{3\,(l-b)}{4\sqrt{2\,k}}\frac{x}{n}\right)^{2/3}$$
that yields after some rearranging
$$(4.15)\quad W_1(n)=2\left(\frac{2}{3\,(l-b)} \right)^{1/3}\int_0^bk^{2/3}\int_0^\infty\left(1-\frac{x}{n}\right)^n\frac{x^{2/3}}{n^{5/3}}\,dx\,ds+O\left(\frac{1}{n^2}\right)\,.$$
From this follows
Theorem 4. Let $B$ be a convexr finite region with smooth boundary, whose curvature $k=k(s)$ is positive and finite. $B$ be in the inner of a convex set $K$; $l$ and $b$ be the circumference of $K$, resp. $B$. For the mathematical expectation of the number of corners of a random convex polygon* $\Pi_n$ around $B$ it then holds true that
$$(4.16)\quad E(X_n)=\left[\left(\frac{2}{3\,(l-b)}\right)^{1/3}\Gamma\left(\frac{5}{3}\right)\int_0^bk^{2/3}\,ds\right]n^{1/3}+O(1)\,.$$
Consequently the order of magnitude of the number of corners is the same as in the case of the convex hull of $n$ points that are randomly chosen in $B$ (cf A.\,Rényi, R.\, Sulanke $[2]$), the factors are however significantly different.
5. Ringshaped areal around a convex polygon
Let $B$ now be a convex $r$-gon. According to theorem 1 the random polygon $\Pi_n$ lies with high probability in an arbitrary, fixed convex surrounding $U$ of $B$; $U$ shall be selected in a way that all intersection points of non-adjacent sides of $B$ are located outside of $U$. The ring-shaped areal $U\,\setminus\,B$, for which the integral $(2.20)$ must be evaluated is partitioned by the sides of $B$ into $r$ corner-regions $E_i$ and $r$ side-regions $T_i$ (fig. 4), in which we carry out the integration separately.
$T$ be one of the side-regions with corners $A,\,A'$ at a side of length $2\,c=\left|\,A\,A'\,\right|$ . For $S\in T$ it holds true that
$$(5.1)\quad l_S-b=\left|\,S\,A\,\right|+\left|\,S\,A'\,\right|-\left|\,A\,A'\,\right|=2\,(a-c)\ ,$$
where a is the semi-major axis of the ellipse with focal points $A,\ A'$ through the point $S$. As coordinates of $S$ we chose $a$ and the distance $x$ of the projection of $S$ onto the major axis of the ellipse from its center. For the area-element $dS$ we obtain in these coordinates
$$(5.2)\quad dS=\frac{a^4-c^2x^2}{a^2\sqrt{(a^2-c^2)(a^2-x^2)}}\,dx\,da\,.$$
For the angle $\alpha$ that is inserted into $(2.20)$ the outer angles of the triangle $A\,A'\,S$ in $S_i$, one calculates
$$(5.3)\quad\sin\,\alpha=\frac{2\,a\,c\sqrt{(a^2-c^2)(a^2-x^2)}}{a^4-c^2x^2}=f(x,\,a)\,.$$
We now replace the region $T$ with a section of the half-circle over $A,\,A'$ that is adjacent to $A\,A'$ and lies in $U$ and in which $\alpha\leqq\pi/2$n; we will later estimate the error that is generated by this. The is determined by $f=1$; for $x,\,a$ we get the integration-region
$$(5.4)\quad c\leqq a\leqq\delta c,\quad\left|x\right|\leqq\frac{a}{c}\sqrt{2\,c^2-a^2}\,,$$
here $\delta\ (1\lt\delta\leqq\sqrt{2})$ is a number that is chosen in a way that the circle-segment lies in $U$. According to $(2.20)$ the integral
$$(5.5)\quad W=\frac{8\,c}{(l-b)^2}\int_c^{\delta\,c}\int_0^{(a/c)\sqrt{2\,c^2-a^2}}\left(1-\frac{2\,(a-c)}{l-b}\right)^{n-2}\left(\frac{\mathrm{arc}\sin\,f\ -\ f}{a\,f}\right)\,dx\,da$$
has to be calculated first. To that end we develop the inner integral
$$(5.6)\quad F(a) =\int_0^{(a/c)\sqrt{2\,c^2-a^2}}\frac{1}{f}(\mathrm{arc}\sin\,f\ -\ f)\,dx$$
according to powers of $a-c$ and set
$$(5.7)\quad\frac{1}{f}(\mathrm{arc}\sin\,f\ -\ f)=\frac{1}{6}f^2+R$$
The integral over the first part yields
$$(5.8)\quad\frac{1}{6}\int_0^{(a/c)\sqrt{2\,c^2-a^2}}f^2dx=-\frac{a^4-c^4}{6\,a^2c}\log(a-c)+O(a-c)\,.$$
For the rest $R$ we show
$$(5.9)\quad\int_0^{(a/c)\sqrt{2\,c^2-a^2}}R\,dx=O(a-c)\,.$$
It holds true that, if
$$\quad\mathrm{arc}\sin\,\xi=\sum_{v=0}^\infty c_v\xi^{2v+1}$$
is set,
$$(5.10)\quad 0\lt R=\sum_{v=2}^\infty c_vf^{2v}\leqq f^4\sum_{v=2}^\infty c_v=f^4\left(\frac{\pi}{2}-\frac{7}{6}\right)\,.$$
Therefore it suffices to prove
$$\quad\int_0^{(a/c)\sqrt{2\,c^2-a^2}}f^4dx=(a-c)\,,$$
that is,
$$(5.11)\quad\int_0^{(a/c)\sqrt{2\,c^2-a^2}}\frac{(a^2-c^2)^2}{(a^4-c^2\,x^2)^4}dx=O\left(\frac{1}{a-c}\right)\,.$$
Now, because $0\leqq x\leqq c\leqq a$
$$(5.12)\quad\frac{(a-x)^2}{16\,a^2\,(a^2-c\,x)^4}\leqq\frac{(a^2-x^2)^2}{(a^4-c^2\,x^2)^4}\leqq\frac{4\,(a-x)^2}{a^6\,(a^2-c\,x)^4}\,.$$
Therefore it remains to show
$$(5.13)\quad\int_0^{(a/c)\sqrt{2\,c^2-a^2}}\frac{(a^2-x^2)^2}{(a^2-c\,x)^4}dx=O\left(\frac{1}{a-c}\right)$$
One easily obtains that relationeasily via the substitution $a^2-c\,x=t$ and some simple estimations. From $(5.6)-(5.9)$ we get
$$(5.14)\quad F(a)=-\frac{a^4-c^4}{6\,a^2\,c}\log\,(a-c)+O(a-c)\,.$$
According to $(5.5)$ it therefore holds true that
$$(5.15)\quad=\frac{-4}{3\,(l-b)^2}\int_0^{\delta c}\left(1-\frac{2\,(a-c)}{(l-b)}\right)^{n-2}\left(\frac{a^4-c^4}{a^3}\log\,(a-c)+O(a-c)\right)\,da\,.$$
The substitution
$$\quad\frac{2\,(a-c)}{l-b}=\frac{Z}{n-2}$$
yields after some simple calculations because of
$$(5.16)\quad\int_c^{\delta c}\left(1-\frac{2\,(a-c)}{(l-b)}\right)^{n-2}\cdot\, O(a-c)\,da=O\left(\frac{1}{n^2}\right)$$
the relation
$$(5.17)\quad W=\frac{4}{3\,n\,(n-1)}\log\,(n-2)+O\left(\frac{1}{n^2}\right)\,.$$
When replacing the side-region $T$ with a half-circle section, we have either integrated a region that is bound by the line of the neighboring side and a circular arc, too much (fig. 5 a) or too little (fig. 5 b).
We show that the errors that are generated by this are of the order of magnitude $O(1/n^2)$. Let
$$(5.18)\quad x(a)=c+(a-c)\,\gamma+O\left((a-c)^2\right)$$
be a representation of the neighboring side. The error in the first case (fig. 5 a) then is
$$(5.19)\quad\Delta=q\int_c^{\delta c}\left(1-\frac{2\,(a-c)}{(l-b)}\right)^{n-2}\frac{1}{a^2\,\sqrt{a^2-c^2}}\int_{x(a)}^{(a/c)\sqrt{2\,c^2-a^2}}(\alpha-\sin\,\alpha)\frac{a^4-c^2\,x^2}{\sqrt{a^2-x^2}}\,dx\,da\,;$$
here $q$ denotes a constant. Because of $(5.16)$ it suffices to show that
$$(5.20)\quad I(a)=\int_{x(a)}^{(a/c)\sqrt{2\,c^2-a^2}}(\alpha-\sin\,\alpha)\frac{a^4-c^2\,x^2}{\sqrt{a^2-x^2}}dx=O\left((a-c)^{3/2}\right)$$
holds. Now $\alpha-\sin\,\alpha$ is bound, so that it suffices to prove
$$(5.21)\quad\int_{x(a)}^{(a/c)\sqrt{2\,c^2-a^2}}\frac{a^4-c^2\,x^2}{\sqrt{a^2-x^2}}dx=O\left((a-c)^{3/2}\right)$$
For the indefinite integral
$$(5.22)\quad Q(x)=\int\frac{a^4-c^2\,x^2}{\sqrt{a^2-x^2}}dx=\frac{c^2\,x}{2}\sqrt{a^2-x^2}-a^2\,\left(a^2-\frac{c^2}{2}\right)\,\mathrm{arc}\cos\,\frac{x}{a}$$
we get, because $\mathrm{arc}\cos\frac{x}{a}=\mathrm{arc}\sin\frac{1}{a}\sqrt{a^2-x^2}$ the series expansion
$$(5.23)\quad Q(x)=\frac{1}{2}\sqrt{a^2-x^2}\,(c^2x-a^3+a(c^2-a^2)+O(a^2-x^2))\,.$$
Substituting the lower bound $x=x(a)$ according to $(5.18)$ immediately yields
$$(5.24)\quad Q(x(a))=O\left((a-c)^{3/2}\right)$$
But the same also holds for the upper bound, because the expression that is to be substituted also is of the form $(5.18)$, of course with a different constant $\gamma$. Quite analogously one also estimates the second error (fig. 5 b). Thus we may replace in $(5.17)$ the half-circle section with the side-region $T$ and alltogether get
$$(5.25)\quad W\,(T)=\frac{4}{3\,n\,(n-1)}\log\,n+O\left(\frac{1}{n^2}\right)\,.$$
This formula is also valid if $B$ degenerates to a line-segment.
Now we consider the corner-region $E=E_i$ at the corner $A_i$ of $B$. We now introduce, as in $(5.2)$, semi-elliptic coordinates; only the basis is now the line-segment $A_{i-1}\,A_{i+1}$, whose length will again be denoted by $2\,c$. With
$$\quad d=\frac{1}{2}(\left|A_{i-1}A_i\right|+\left|A_i A_{i+1}\right|)$$
we have for the difference of distance
$$(5.26)\quad l_S-b=2\,(a-d)\,.$$
Therefore, according to $(2.20)$ and $(5.2)$, for the corresponding probablity
$$(5.27)\quad W\,(E)=\frac{2}{(l-b)^2}\int_d^{a_0}\left(1-\frac{2\,(a-d)}{(l-b)}\right)^{n-2}\int_{x_1(a)}^{x_2(a)}(\alpha-\sin\,\alpha)\frac{a^4-c^2\,x^2}{a^2\sqrt{(a^2-c^2)(a^2-x^2)}}\,dx\,da\,.$$
Here $x_1(a),\ x_2(a)$ denote the $x$-coordinates of the intersection point of the ellipse that belongs to $a$ with the elongations of the sides that are adjacent to $A_i$ beyond $A_i$. As we only consider a sufficiently small surrounding of $B$, it holds true that
$$\quad\left|x\right|\leqq\max\left(\left|x_1(a)\right|,\,\left|x_1(a)\right|\right)\lt a,\quad c\lt d\leqq a\,.$$
From the mean value theorem follows, because of the boudedness and continuity of the integrand,
$$(5.28)\quad \int_{x_1(a)}^{x_2(a)}(\alpha-\sin\,\alpha)\frac{a^4-c^2\,x^2}{a^2\sqrt{(a^2-c^2)(a^2-x^2)}}dx=M(a)\,(x_2(a)-x_1(a))\,,$$
where $M(a)$ remains bounded for all $a$ from the range under consideration: $\left|\,M(a)\,\right|\leqq M_0\,.$
For $a=d$ it holds $x_1(d)=x_2(d)$. The functions $x_i(a)$ are sufficiently often differentiable in location $d$. It follows
$$(5.29)\quad x_2(a)-x_1(a)=h_0(a-d)+O\left((a-d)^2\right)\,,$$
where $h_0$ is a certain constant. If one inserts $(5.28),\ (5.29)$ into $(5.27)$, then according to $(5.16)$ follows immediately
$$(5.30)\quad W\,(E)=O\left(\frac{1}{n^2}\right)\,.$$
Because of theorem 1, $(5.25)$ and $(5.30)$ we get the following
Theorem 5. Let $B$ a convex $r$-gon, $r\geqq2$, that lies in the inner of $K$.For the mathematical expectation of the number of corners $X_n$ of a random polygon $\Pi_n$ it holds true that
$$\quad E(X_n)=\frac{2\,r}{3}\,\log n+O(1)\,.$$
The principal term of this formula matches the corresponding principal term of theorem 1of our work $[2]$ on the convex hull of random points that lie in a polygon.
References
1. Blaschke, W.: Vorlesungen über Integralgeometrie. 3. Aufl. Berlin: VEB Deutscher Verlag der Wissenschaften 1955.
2. Rényi, A., u. R. Sulanke: Über die konvexe Hülle von $n$ zufällig gewählten Punkten. Z. Wahrscheinlichkeitstheorie verw. Geb. 2, 75-84 (1963).
3. Stevens, W.L.: Solution to a geometrical problem in probability. Ann. Eugenics 9, 315-320 (1939.
Dr. R. Sulanke
Mathematisches Institut der
Humboldt-Universität
Berlin
Prof. Dr. A. Rényi
Mathematisches Institut der Ungarischen
Akademie der Wissenschaften
Reáltonada u. 13-15
Budapest V, Ungarn
Tuesday, December 3, 2019
Random convex polygons II
As I mentioned in one of my earlier posts, the early work of Renyi and Sulanke on random planar convex polygons was available only in German. This consists of three separate articles published over a couple of years. Now, courtesy of the efforts of Manfred Weis, English translations are available to the non-German-reading audience. What follows is the second in this series of articles.
Z. Wahrscheinlichkeitstheorie 3, 138-147 (1964)
On the Convex Hull of $n$ Randomly Chosen Points. II
by
A. Rényi and R. Sulanke
Introduction
The present article is a continuation of our work $[1]$. We consider a finite convex region $K$ of the plane. Let $P_i$ ($i=1,\,2,\,\ldots,\,n$$) $ $n$ random points of $K$ which are chosen independently according to the equal distribution. By $H_n$ we denote the convex hull of the $P_i$, by $L_n$ the length of the circumference of $H_n$ and by $F_n$ the area of $H_n$. It is obvious that, as $n\to\infty$, the mathematical expectations $E(L_n)$, resp. $E(F_n)$ approach the circumference $L$, resp. the area $F$ of $K$. The rate of that convergence shall be investigated in the following.
In § 1 initially general formulas for the calculation of $E(L_n)$ and $E(F_n)$ will be established. After that we start with considering the case that $K$ has a sufficiently of continuously differentiable boundary curve, whose curvature $k=k(s)$ is positive and finite: $0\lt k(s)\lt A$ ($s$ denotes arclength).
The approximation formulas that are established in §2 allow us to replace the boundary curve of $K$ in the neighborhood of one of its points by its osculating circle. By means of these formulas we manage in § 3 to determine the asymptotic behavior of $E(L_n)$ and $E(F_n)$. It turns out that the deviations $L-E(L_n)$ and $F-E(F_n)$ both are of the type $\mathrm{const.}\ n^{2/3}+\pmb{0}\left(n^{-1}\right)$; In case of the area the equiaffine length of the boundary of $K$ contributes the most to the constant in the leading term; in case of the circumference however, the functional
$$\quad Q(K)=\int_0^L\left(k(s)\right)^{4/3}ds$$
shows up that apparently hasn't been investigated in geometry. It would be interesting to treat an isoperimetric problem for $Q(K)$.
The investigation of the analogous problems for convex polygons lead to rather confusing calculations. For that reason in § 4 we only consider the case that $K$ is a square. Here it turns out, what is surprising at first sight, that area and circumference exhibit a different asymptotic behavior. While for the circumference of the deviation
$$\quad L-E(L_n)=\mathrm{const.}n^{-1/2}+\pmb{0}(n^{-1})$$
is larger than in the smooth case, we have for the area
$$\quad F-E(F_n)=\mathrm{const.}\frac{\ln n}{n}+\pmb{0}(n^{-1});$$
this approximation is substantially better than the corresponding one for an oval with smooth boundary.
§ 1. Formulas for $E(L_n)$ and $E(F_n)$
Let again $\varepsilon_{ij}=1$ if $i\ne j$ and $\overline{P_i\,P_j}$ is a segment of the boundary of $H_n$, and $\varepsilon_{ij}=0$ else. By $\left|\,P_iP_j\,\right|$ we denote the distance of the points $P_i$, $P_j$. Then it holds true that
$$(1)\quad L_n=\sum_{i\lt j}\left|\,P_iP_j\,\right|\varepsilon_{ij}.$$
From this one immediately obtains $E(L_n)=\binom{n}{2}E\left(\left|\,P_iP_j\,\right|\varepsilon_{ij}\right)$, therefore
$$(2)\quad E(L_n)=\binom{n}{2} \frac{1}{F^n}\int\cdots\int\left|\,P_iP_j\,\right|\varepsilon_{ij}dP_1\,\ldots\,dP_n$$
If we integrate over $P_3\,\ldots,\,P_n$, we have
$$(3)\quad E(L_n) = \binom{n}{2}\frac{1}{F^2}\iint\left|\,P_1P_2\,\right|\left\lbrace\left(1-\frac{f}{F}\right)^{n-2}+\left(\frac{f}{F}\right)^{n-2}\right\rbrace dP_1,dP_2;$$
here $f$ is the smaller area that is cut off of $K$ by the line $g(P_1,\,P_2)$, which implies $f/F\leqq 1/2$. Therefore
$$(4)\quad E(L_n)\sim\frac{\binom{n}{2}}{F^2}\iint\left(1-\frac{f}{F}\right)^{n-2}\left|\,P_1P_2\,\right|dP_1\,dP_2.$$
We now, using the same notation as in $[1],\,(41)$ apply the transformation
$$(5)\quad dP_1\,dP_2=\left|1_1-t_2\right|dt_1\,dt_2\,dp\,d\varphi$$
because $\left|t_1-t_2\right|=\left|P_1P_2\right|$ and
$$(6)\iint_{g(p,\varphi)\cap K}\left|t_1-t_2\right|^2dt_1\,dt_2=\frac{l^4}{6}$$
where $l=l(\varrho,\varphi)$ denotes the length of the chord $g(p,\varphi)\cap K$, we get
$$(7)\quad E(L_n)\sim\frac{\binom{n}{2}}{6F^2}\int_0^{2\pi}\int_0^{p(\varphi)}\left(1-\frac{f}{F}\right)^{n-2}l^4dp\,d\varphi.$$
Here $p(\varphi)$ is the support function of region $K$; we chose as the origin $K$'s center of gravity.
Let now $p(P_i,\,P_j)$ denote the distance of the line $g(P_i,\,P_j)$ from the origin $0$. Then, for the area of $H_n$, we have
$$(8)\quad F_n=\frac{1}{2}\sum_{i\lt j}\varepsilon_{ij}\left|P_i\,P_j\right|p(P_i,\,P_j).$$
By conclusions that are close analogues to those as in the case of the circumference, we get
$$(9)\quad E(F_n)\sim\frac{\binom{n}{2}}{12F^2}\int_0^{2\pi}\int_0^{p(\varphi)}\left(1-\frac{f}{F}\right)^{n-2}l^4p\,dp\,d\varphi.$$
§ 2. The approximation by an osculating circle
Our task is now to evaluate the integrals $(7)$ and $(9)$. In this and in the following paragraph we assume that $K$ has a smooth boundary with curvature $k(s),\ 0\lt k(s)\lt A$. We first fix $\varphi$ and carry out the integration over $p$. As for the asymptotic behavior of the integrals only that contribution is important, for which $f/F$ is small, we may replace the values $l,\, f$ of $K$ with the corresponding values $\bar l,\,\bar f$ of the osculating circle, that shares the tangent $g\left(p(\varphi),\,\varphi\right)$ with $K$, The error that is generated by that replacement shall now be estimated. This will yield improvements of the formulas $[1](47)$.
Instead of $p$ we now introduce the new parameter $\beta$, which is half the central angle from the center $Z$ of the osculating circle$S_{\varphi}$ onto the chord $g(p,\,\varphi)\cap S_{\varphi}$. Then we have (cmp. fig. 1)
$$\quad p=r(\cos \beta\, -\, 1)+p(\varphi).$$
Here $r$ denotes the radius of curvature: $r=1/k$. On the line $g(\beta,\varphi)$ we introduce the arc length $t$ as a parameter and denote by $t_1^-,\,t_1^+$ 1the parameters of the intersection points of $g$ with the boundary of $K$. If we chose the center of the chord $g\cap S_{\varphi}$ as the zero-point of the arc length $t$ then it follows immediately that
$$(11)\quad t_1^-=-r\sin\beta,\ t_1^+=r\sin\beta$$.
We now want to calculate $t_2^-,\,t_2^+$ as functions of $\beta$. For that purpose we represent the boundary of $K$ in a neighborhood of the considered point in the acompanying bipod (i.e. in the Frenet frame). Let $\mathfrak{x}(s)$ be the local vector of a variable point of the the boundary curve from the point of contact, $\mathfrak{t}$ a tangent vector and $\mathfrak{n}$ the normal vector in that point. If we chose the point of contact also as the zero-point of the boundary curve's arc length $s$, then, taking ito account the Frenet formulas of planar differential geometry, Taylor's formula yields the following representation:
$$\quad\quad\mathfrak{x}=\mathfrak{t}\cdot\left\lbrace s-k^2\frac{s^3}{3!}-3k\,k'\frac{s^4}{4!}+\pmb{0}(s^5)\right\rbrace+$$
$$(12)$$
$$\quad\quad+\mathfrak{n}\left\lbrace k\frac{s^2}{2!}+k'\frac{s^3}{3!}+(k''-k^3)\frac{s^4}{4!}+\pmb{0}(s^5)\right\rbrace.$$
Here the coefficients have to be taken at $s=0$; apostrophes denote differentiation w.r.t. arc length.
In this coordinate system the line $g(\beta,\varphi)$ has the parametric representation
$$(13)\quad \mathfrak{z}(t)=\mathfrak{t}\cdot t+\mathfrak{n}\cdot r(1-\cos\beta).$$
The comparison with $(12)$ provides us with the following two relations
$$(14)\quad t_2=s-k^2\frac{s^3}{3!}-3k\,k'\frac{s^4}{4!}+\pmb{0}(s^5).$$
$$(15)\quad r(1-\cos\beta)=k\frac{s^2}{2!}+k'\frac{s^3}{3!}+(k''-k^3)\frac{s^4}{4!}+\pmb{0}(s^5).$$
From $(15)$ we obtain $s$ as a function of $\beta$:
$$(16)\quad s=r\beta-\frac{k'r^3\beta^2}{3!}\beta^2+\frac{r^4}{4!}\left\lbrace\frac{5}{3}k'^2r-k''\right\rbrace\beta^3+\pmb{0}(\beta^4);$$
If we insert that in $(14)$, it follows that
$$(17)\quad t_2=r\beta-\frac{k'r^3}{3!}\beta^2+\left\lbrace\frac{5}{4!3}r^5k'^2-\frac{r^4k''}{4!}-\frac{r}{3!}\right\rbrace\beta^3+\pmb{0}(\beta^4);$$
where obviously $t^-=t_2(-\beta),\ t_2^+=t_2(\beta)$ for $\beta\geqq0$. The power series expansion of $\sin\beta$ and $(11)$ yield
$$(18)\quad t_1-t_2=\frac{k'r^3}{3!}\beta^2+\frac{r^4}{4!}\left\lbrace k''-\frac{5}{3}rk'^2\right\rbrace\beta^3+\pmb{0}(\beta^4);$$
Here again we get $t_1^+-t_2^+$ for positive $\beta$ and $t_1^--t_2^-$ for negative $\beta$.
Now we take into account that the osculating circle of a curve in a point that isn't a vertex point, for which therefore $k'\ne0$, intersects the curve in the tangent point, as is also shown in our illustration. That implies $l-\bar l=(t_1^--t_2^-) -(t_1^+-t_2^+) $, consequently
$$(19)\quad l-\bar l=\frac{r^4}{12}\left(\frac{5}{3}rk'^2-k''\right)\beta^3+\pmb{0}(\beta^4).$$
Because $k'=0$ in a vertex point and there is a contact of at least third order with the osculating circle, $(19)$ is valid even more in that case; that can be seen immediately from $(18)$.
For the areas $f,\ \bar f$ we get from evaluating the integral
$$\quad f-\bar f=\int_p^{p(\varphi)}(l-\bar l)dp
the following approximation formula:
$$(20)\quad f-\bar f=\frac{r^5}{60}\left(\frac{5}{3}r\,k'2-k''\right)\beta^5+\pmb{0}(\beta^6).$$
§ 3. Calculation of $E(L_n)$ and $E(F_n)$ for an oval region with smooth boundary
We switch to the central angle $\alpha=2\beta$ and express the Integrals $(7)$ and $(9)$ via $\alpha$ and $\varphi$. Because of
$$(21)\quad l=2r\sin\frac{\alpha}{2}\quad\text{and}\quad\bar f= \frac{r^2}{2}(\alpha-\sin\alpha)$$
as well as
$$(22)\quad\left|dp\right|=\left(\frac{r}{2}\sin\frac{\alpha}{2}\right)\left|d\alpha\right|$$
$(19)$ yields
$$(23)\quad l^4dp=\left[\frac{r^5\alpha^5}{4}\left(1+G\alpha^2\right)+\pmb{0}(\alpha^8)\right]d\alpha$$
where we have set
$$(24)\quad G=\frac{5}{4!}\left(\frac{r^4r'^2}{3}-\frac{r^3k''}{5}-1\right)$$
for abbreviation. From $(20)$ and $(21)$ we get
$$(25)\quad \frac{f}{F}=\frac{r^2\alpha^3}{12F}+\varkappa\cdot\alpha^5+\pmb{0}(\alpha^5)$$
where
$$(26)\quad\varkappa=\frac{r^2}{5!2\,F\,}\left[\left(\frac{r}{3}\right)^3\left(\frac{5}{3}rk'^2-k''\right)-1\right].$$
The integral $(7)$ now attains the form
$$\quad\quad E(L_n)\sim\frac{\binom{n}{2}}{4!\,F^2}\int_0^{2\pi}r^5\,d\varphi\int_0^{\alpha(\varphi)}\left(1-\frac{r^2\alpha^3}{12F}-\varkappa\alpha^5-\pmb{0}(\alpha^6)\right)^{n-2}\times$$
$$(27)$$
$$\quad\quad\times(\alpha^5+G\alpha^7+\pmb{0}(\alpha^8))d\alpha$$
We first calculate the integrals
$$(28)\quad B_\nu=\int_0^{\alpha(\varphi)}\left(1-\frac{r^2\alpha^3}{12F}-\varkappa\alpha^5-\pmb{0}(\alpha^6)\right)^{n-2}\alpha^\nu\,d\alpha.$$
Via the substitution
$$(29)\quad\frac{r^2\alpha^3}{12F}=\frac{x}{n}$$
we get, taking into account
$$(30)\quad\left(1-\frac{x}{n}-\varkappa_1\left(\frac{x}{n}\right)^{5/3}+\pmb{0}\Big(\left(\frac{x}{n}\right)^2\right)^{n-2}=e^{-x}\left(1-\frac{\varkappa_1x^{5/3}}{n^{2/3}}+\pmb{0}\left(\frac{x^2}{n}\right)\right)$$
the integral $B_\nu$ in the form
$$(31)\quad B_\nu=\frac{1}{3}\left(\frac{12F}{n\,r^2}\right)^{(\nu+1)/3}\int_0^{nr^2\alpha^3(\varphi)/12F}e^{-x}\left(1-\varkappa_1x^{5/3}n^{-2/3}+\pmb{0}\left(\frac{x^2}{n}\right)\right)x^{(\nu-2)/3}dx.$$
where
$$(32)\quad\varkappa_1=\varkappa\left(\frac{12\,F}{r^2}\right)^{5/3}$$
has been set. If we now integrate in $(31)$ not only to the upper bound that has been given here, but to $+\infty$, we introduce an error of exponential order of magnitude that is neglegible. It follows that
$$(33)\quad B_\nu=\frac{1}{3}\left(\frac{12\,F}{n\,r^2}\right)^{(\nu+1)/3}\cdot\left[\Gamma\left(\frac{\nu+1}{3}\right)-\frac{\varkappa_1}{n^{2/3}}\Gamma\left(\frac{\nu}{3}+2\right)\right]+\pmb{0}\left(n^{-(\nu+4)/3}\right).$$
By inserting $(33)$ into $(27)$ we get
$$(34)\quad E(L_n)=L-a(K)n^{-2/3}+\pmb{0}\left(\frac{1}{n}\right).$$
The constant $a(K)$ results from calculating
$$(35)\quad a(K)=\Gamma\left(\frac{11}{3}\right)\int_0^{2\pi}\varkappa_1\,r\,d\varphi-(12\,F)^{2/3}\Gamma\left(\frac{8}{3}\right)\int_0^{2\pi}Gr^{-1/3}d\varphi$$
taking into account $(24)$, $(26)$ and $(32)$ in the form
$$(36)\quad a(K)=\frac{(12\,F)^{2/3}\Gamma\left(\frac{8}{3}\right)}{4!}\int_0^L\left[\frac{9}{5}k^{4/3}+\frac{3}{5}k''k^{-5/3}-k'^{\,2}k^{-8/3}\right]ds.$$
Here, instead of $\varphi$, the arclength $s$ of the boundary curve of $K$ has been introduced as the parameter; as it is valid that $d\varphi=k\,ds$. By partial integration it follows that
$$(37)\quad\frac{3}{5}\int_0^Lk''\,k^{-5/3}ds=\int_0^Lk'^{\,2}k^{-8/3}ds.$$
Therefore, for $a(K)$ we finally get
$$(38)\quad a(K)=\frac{1}{12}\Gamma\left(\frac{2}{3}\right)(12\,F)^{2/3}\int_0^Lk^{4/3}ds.$$
For the calculation of $E(F_n)$ we also carry out the substitution $(22)$ and get
$$\quad\quad E(F_n)\sim\frac{\binom{n}{2}}{12\,F}\int_0^{2\pi}\int_0^{\alpha(\varphi)}\left(1-\frac{r^2\alpha^3}{12\,F}-\varkappa\alpha^5-\pmb{0}(\alpha^6)\right)^{n-2}\times$$
$$(39)$$
$$\quad\quad\times\left[\frac{p(\varphi)r^5\alpha^5}{4}+\left(\frac{Gp(\varphi)r^5}{4}-\frac{r^5}{32}\right)\alpha^7+\pmb{0}(\alpha^8) \right]d\alpha\,d\varphi.$$
According to $(33)$ that yields
$$(40)\quad E(F_n)=F-b(K)n^{-2/3}+\pmb{0}(n^{-1})$$
For the costant $b(K)$ we first find after some calculations
$$(41)\quad b(K)=\frac{1}{16}\Gamma\left(\frac{8}{3}\right)(12\,F)^{2/3}\sigma(K)+c(K);$$
where
$$(42)\quad\sigma(K)=\int_0^Lk^{1/3}ds$$
is the equi affine arclength of the boundary curve of $K$, while $c(K)$ is of the form
$$(43)\quad c(K)=\frac{\Gamma\left(\frac{8}{3}\right)}{4!}(12\,F)^{2/3}\int_0^{2\pi}p\,r^{-1/3}\left(\frac{9}{10}+\frac{3}{10}r^3k''-\frac{1}{2}r^4k'^{\,2}\right)d\varphi.$$
By a dot above we now denote derivations with respect to $\varphi$ and express $k',\,k''$ via $r,\,\dot r,\,\ddot r$. It follows
$$(44)\quad c(K)=\frac{\Gamma\left(\frac{8}{3}\right)(12\,F)^{2/3}}{4!\,10}\int_0^{2\pi}p(9\,r^{-1/3}+4\dot r^2\, r^{-7/3}-3\ddot r\, r^{-4/3})\,d\varphi$$
By integrating partially twice, we get
$$(45)\quad \int_0^{2\pi}(4\,\dot r^2r^{-7/3}-3\ddot r r^{-4/3})p\,d\varphi=9\int_0^{2\pi}r^{-1/3}\ddot p\,d\varphi.$$
We now substitute that into $(44)$. Because $p+\ddot p = r$ (cf e.g. W. Blaschke $[2]$, $p. 30$) that again yields a multiple of $\sigma(K)$. Taking into account $(41)$ finally yields
$$(46)\quad b(K)=\frac{1}{10}\Gamma\left(\frac{8}{3}\right)(12\,F)^{2/3}\sigma(K).$$
The results of this paragraph can be summarized as follows:
Theorem 1. Let $K$ be a planar, finite convex region whose boundary curve is sufficiently often continuously differentiable. The curvature $k(s)$ of the boundary shall satisfy the inequality $0\lt k(s)\lt A$. Let $L$ be the circumference and $F$ the area of $K$. The length $L_n$ of the convex hull $H_n$ of $n$ points in $K$ that are chosen independently and according to equal distribution, possesses the mathematical expectation
$$(47)\quad E(L_n)=L-\frac{\Gamma(2/3)(12\,F)^{2/3}\int_0^Lk^{4/3}ds}{12\,n^{2/3}}+\pmb{0}(n^{-1}).$$
For the mathematical expectation of the area $F_n$ of $H_n$ we have
$$(48)\quad E(F_n)=F-\frac{\Gamma\left(\frac{8}{3}\right)(12\,F)^{2/3}\sigma(K)}{10^{2/3}}+\pmb{0}(n^{-1})$$
where $\sigma(K)$ according to* $(42)$ denotes the equiaffine length of the boundary of $K$
§ 4. Calculation of $E(L_n)$ and $E(F_n)$ for a square
Let $K$ now be a square with side length $a$. We place the coordinate origin in the center of $k$ and the null-direction $\varphi=0$ shall go from $\pmb{0}$ to the center of a side. We have to evaluate the integrals $(7)$ and $(9)$ again. For reasons of symmetry it is sufficient to carry out the integration over $\varphi$ from $0$ to $\pi/4$ and multiply by $8$ accordingly. For the integration over $p$ we distinguish two cases. 1. the line $g(\varrho\,\varphi)$ hits two opposite sides of the square. That happens if
$$(49)\quad 0\leqq p\leqq p_1(\varphi)=\frac{a}{2}(\cos\,\varphi-\sin\,\varphi)$$
holds true. For $l$ and $f$ this implies
$$(50)\quad l=l(\varphi)=\frac{a}{\cos\,\varphi}, \quad f=f(p,\,\varphi)=\frac{a^2}{2}-\frac{ap}{\cos\,\varphi}$$
\2. the line $g(p,\,\varphi)$ hits two adjacent sides of the square. In that case we have
$$(51)\quad p_1(\varphi)\leqq p\leqq p(\varphi)=\frac{a}{2}(\cos\,\varphi+sin\,\varphi).$$
Further we have
$$(52)\quad l=l(p,\,\varphi)=\frac{p(\varphi)-p}{\cos\,\varphi\,\sin\,\varphi},\quad f=f(p,\,\varphi)=\frac{\left(p(\varphi)-p\right)^2}{2\,\sin\,\varphi\,\cos\,\varphi}.$$
Because of this distinction of cases the integrals $(7)$ and $(9)$ appear now as sums
$$(53)\quad E(L_n)\sim I_1+I_2,\quad E(F_n)\sim J_1+J_2$$
and we have to evaluate the following four expressions:
$$(54)\quad I_1=\frac{4}{3}\binom{n}{2}\_0^{\pi/4}\int_0^{p_1(\varphi)}\left(\frac{1}{2}+\frac{p}{a\,\cos\,\varphi}\right)^{n-2}\frac{dp\,d\varphi}{\cos^4\varphi},$$
$$(55)\quad I_2=\frac{4\,\binom{n}{2}}{3\,a^4}\int_0^{\pi/4}\int_{p_1(\varphi)}^{p(\varphi)}\left(1-\frac{\left(p(\varphi)-p\right)^2}{2a^2\sin\,\varphi\,\cos\,\varphi}\right)^{n-2}\frac{\left(p(\varphi)-p\right)^4dp\,d\varphi}{\cos^4\varphi\,\sin^4\varphi},$$
$$(56)\quad J_1=\frac{2}{3}\binom{n}{3}\int_0^{\pi/4}\int_0^{p_1(\varphi)}\left(\frac{1}{2}-\frac{p}{a\,cos\varphi}\right)^{n-2}\frac{p\,dp\,d\varphi}{\cos^4\varphi}.$$
$$(57)\quad J_2=\frac{2\,\binom{n}{2}}{3\,a^4}\int_0^{\pi/4}\int_{p_1(\varphi)}^{p(\varphi)}\left(1-\frac{\left(p(\varphi)-p\right)^2}{2\,a^2\,\sin\,\varphi\,\cos\,\varphi}\right)^{n-2}\frac{\left(p(\varphi)-p\right)^4p\,dp\,d\varphi}{\cos^4\varphi\,sin^4\,\varphi}.$$
We now start with the calculation of $I_1$. Substituting
$$(58)\quad p=x\,a\,\cos\,\varphi$$
yields
$$(59)\quad I_1=\frac{2\,n\,a}{3}\int_0^{\pi/4} \frac{(1-\frac{1}{2}\,tg\,\varphi)^{n-1}}{\cos^3\,\varphi}+\pmb{0}(2^{-n}).$$
If we now substitute
$$(60)\quad tg\,\varphi=t$$
we get $I_1$ in a form that is easy to estimate. It results
$$(61)\quad I_1=\frac{4\,a}{3}+\pmb{0}\left(\frac{1}{n^2}\right).$$
Now we calculate $I_2$. With the substitution
$$(62)\quad \frac{\left(p(\varphi)-p\right)^2}{2\,a^2\,\sin\,\varphi\,\cos\,\varphi}=\frac{x}{n}$$
we have
$$(63)\quad I_2=\frac{2^{5/2}\cdot a(n-1)}{3\,n^{3/2}}\int_0^{\pi/4}(\cos\,\varphi\,\sin\varphi)^{-3/2}\left[\int_0^{(n\,tg\,\varphi)/2}\left(1-\frac{x}{n}\right)^{n-2}x^{3/2}dx\right]\,d\varphi.$$
Now substitute
$$(64)\quad n\,tg\,\varphi = z$$
and get
$$(65)\quad I_2=\frac{2^{5/2}\cdot a(n-1)}{3\,n}\int_0^n\left(\frac{1+\frac{z^2}{n^2}}{z^3}\right)^{1/2}\int_0^{z/2}\left(1-\frac{x}{n}\right)\,x^{3/2}dx\,dz\,.$$
We set
$$(66)\quad\left(1+\frac{z^2}{n^2}\right)^{1/2}=\left[\left(1+\frac{z^2}{n^2}\right)^{1/2}-1\right]+1$$
and thus partition the integral $(65)$ into two components. With the substitution $z=n\,\tau$ we get for the first part:
$$(67)\quad \frac{2^{5/2}\cdot a(n-1)}{3\,n}\int_0^n\frac{\sqrt{1+\frac{z^2}{n^2}}-1}{z^{3/2}}\int_0^{z/2}\left(1-\frac{x}{n}\right)^{n-2}x^{3/2}dx\,dz=\sqrt{\frac{2\pi}{n}}\,aq+\pmb{0}\left(\frac{1}{n}\right)$$
where
$$(68)\quad q=\int_0^1\frac{\sqrt{1+\tau^2}\,-1}{\tau^{3/2}}d\tau$$
For the second part we obtain after several elementary rearrangements
$$(69)\quad\frac{2^{5/2}\cdot a(n-1)}{3\,n}\int_0^n\left(\int_0^{z/2}\left(1-\frac{x}{n}\right)^{n-2}x^{3/2}dx\right)\frac{dz}{z^{3/2}}=\frac{8\,a}{3}-2\sqrt{\frac{2\pi}{n}}\cdot a+\pmb{0}\left(\frac{1}{n}\right)\,.$$
From $(61)$, $(67)$ and $(69)$ we get for the mathematical expectation of $L_N$
$$(71)\quad E(L_n)=4\,a\,-\,\frac{a\,(2-q)\sqrt{2\pi}}{\sqrt{n}}+\pmb{0}\left(\frac{1}{n}\right)\,.$$
For the calculation of $J_1$ one again applies the transformations $(58)$ and after that $(60)$. After some elementary calculations one gets
$$(71)\quad J_1=\frac{1}{3}a^2+\pmb{0}\left(\frac{1}{n}\right)\,.$$
Finally, we also have to calculate the integral $J_2$. The substitution $(62)$ leads to $J_2=R_1-R$ with
$$(72a)\quad R_1=\frac{4\,a^2(n-1)}{3\,n^{3/2}}\int_0^{\pi/4}\frac{\cos\,\varphi+\sin\varphi}{(\sin\,2\,\varphi)^{3/2}}\left(\int_0^{(n\,tg\,\varphi)/2}\left(1-\frac{x}{n}\right)^{n-2}x^{3/2}dx\right)\,d\varphi,$$
$$(72b)\quad R=\frac{8\,a^2(n-1)}{3\,n^2}\int_0^{\pi/4}\left[\int_0^{(n\,tg\,\varphi)/2}\left(1-\frac{x}{n}\right)^{n-2}x^2\,dx\right]\frac{d\varphi}{\sin\,2\,\varphi}\,.$$
The calculation of $R_1$ is easily possible via the substitution $(64)$. It results in
$$(73)\quad R_1=\frac{2}{3}\,a^2+\pmb{0}\left(\frac{1}{n}\right)\,.$$
For $R$ we get via the substitution
$$(74)\quad\frac{n\,tg\,\varphi}{2}=t$$
the expression
$$(75)\quad R=\frac{4\,a^2(n-1)}{3\,n^2}\int_0^{n/2}\left(\int_0^t\left(1-\frac{x}{n}\right)^{n-2}x^2dx\right)\frac{dt}{t}\,.$$
If we integrate over $x$, this yields
$$(76)\quad R=\frac{8\,a^2}{3(n+1)}\int_0^{n/2}\left[1-\left(1-\frac{t}{n}\right)^{n+1}\right]\frac{dt}{t}+\pmb{0}\left(\frac{1}{n}\right)\,.$$
For calculating the integral that appears in $(76)$ we use the formula
$$(77)\quad\frac{1}{t}\left[1-\left(1-\frac{t}{n}\right)^{n+1}\right]=\sum_{k=0}^n\left(1-\frac{t}{n}\right)^k\,.$$
It follows
$$(78)\quad \int_0^{n/2}\left[1-\left(1-\frac{t}{n}\right)^{n+1}\right]\frac{dt}{t}=\ln\,n+C-\log\,2+\pmb{0}\left(\frac{1}{n}\right)\,.$$
here $C$ is the Euler constant. This results in
$$(79)\quad J_2=R_1-R=\frac{2a^2}{3}-\frac{8\,\ln\,n}{3\,n}+\pmb{0}\left(\frac{1}{n}\right)\,.$$
If we take into account formula $(70)$ and $E(F_n)=J_1+J_2$, we can summarize the results of this paragraph in the following theorem:
Theorem 2. In a square $K$ with sidelength $a$ let $H_n$ denote the convex hull of $n$ points chosen independently and equally distributed from $K$. For the mathematical expectation of the circumference $L_n$ of $H_n$ it is valid that
$$(80)\quad E(L_n)=4\,a-\frac{a(2-q)\sqrt{2\pi}}{\sqrt{n}}+\pmb{0}\left(\frac{1}{n}\right)$$
where the constant $q$ is given by $(68)$. For the mathematical expectation of the area $F_n$ of $H_n$ it is valid that
$$(81)\quad E(F_n)=a^2-\frac{8\,a^2\,\ln\,n}{3\,n}+\pmb{0}\left(\frac{1}{n}\right)\,.$$
References
$[1]$ Rényi, A. u. R. Sulanke: Über die konvexe Hülle von $n$ zufällig gewählten Punkten,
Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 2 (1963) 75-84.
$[2]$ Blaschke, W.: Vorlesungen über Integralgeometrie, 3. Aufl., Berlin, VEB Deutscher Verlag der Wissenschaften, 1955.
Budapest, VI, Hungary Benczur u.28
and
Schulzendorf upon Eichwalde near Berlin
Hamburger Straße 4
(Received on 7th October 1963)
Z. Wahrscheinlichkeitstheorie 3, 138-147 (1964)
On the Convex Hull of $n$ Randomly Chosen Points. II
by
A. Rényi and R. Sulanke
Introduction
The present article is a continuation of our work $[1]$. We consider a finite convex region $K$ of the plane. Let $P_i$ ($i=1,\,2,\,\ldots,\,n$$) $ $n$ random points of $K$ which are chosen independently according to the equal distribution. By $H_n$ we denote the convex hull of the $P_i$, by $L_n$ the length of the circumference of $H_n$ and by $F_n$ the area of $H_n$. It is obvious that, as $n\to\infty$, the mathematical expectations $E(L_n)$, resp. $E(F_n)$ approach the circumference $L$, resp. the area $F$ of $K$. The rate of that convergence shall be investigated in the following.
In § 1 initially general formulas for the calculation of $E(L_n)$ and $E(F_n)$ will be established. After that we start with considering the case that $K$ has a sufficiently of continuously differentiable boundary curve, whose curvature $k=k(s)$ is positive and finite: $0\lt k(s)\lt A$ ($s$ denotes arclength).
The approximation formulas that are established in §2 allow us to replace the boundary curve of $K$ in the neighborhood of one of its points by its osculating circle. By means of these formulas we manage in § 3 to determine the asymptotic behavior of $E(L_n)$ and $E(F_n)$. It turns out that the deviations $L-E(L_n)$ and $F-E(F_n)$ both are of the type $\mathrm{const.}\ n^{2/3}+\pmb{0}\left(n^{-1}\right)$; In case of the area the equiaffine length of the boundary of $K$ contributes the most to the constant in the leading term; in case of the circumference however, the functional
$$\quad Q(K)=\int_0^L\left(k(s)\right)^{4/3}ds$$
shows up that apparently hasn't been investigated in geometry. It would be interesting to treat an isoperimetric problem for $Q(K)$.
The investigation of the analogous problems for convex polygons lead to rather confusing calculations. For that reason in § 4 we only consider the case that $K$ is a square. Here it turns out, what is surprising at first sight, that area and circumference exhibit a different asymptotic behavior. While for the circumference of the deviation
$$\quad L-E(L_n)=\mathrm{const.}n^{-1/2}+\pmb{0}(n^{-1})$$
is larger than in the smooth case, we have for the area
$$\quad F-E(F_n)=\mathrm{const.}\frac{\ln n}{n}+\pmb{0}(n^{-1});$$
this approximation is substantially better than the corresponding one for an oval with smooth boundary.
§ 1. Formulas for $E(L_n)$ and $E(F_n)$
Let again $\varepsilon_{ij}=1$ if $i\ne j$ and $\overline{P_i\,P_j}$ is a segment of the boundary of $H_n$, and $\varepsilon_{ij}=0$ else. By $\left|\,P_iP_j\,\right|$ we denote the distance of the points $P_i$, $P_j$. Then it holds true that
$$(1)\quad L_n=\sum_{i\lt j}\left|\,P_iP_j\,\right|\varepsilon_{ij}.$$
From this one immediately obtains $E(L_n)=\binom{n}{2}E\left(\left|\,P_iP_j\,\right|\varepsilon_{ij}\right)$, therefore
$$(2)\quad E(L_n)=\binom{n}{2} \frac{1}{F^n}\int\cdots\int\left|\,P_iP_j\,\right|\varepsilon_{ij}dP_1\,\ldots\,dP_n$$
If we integrate over $P_3\,\ldots,\,P_n$, we have
$$(3)\quad E(L_n) = \binom{n}{2}\frac{1}{F^2}\iint\left|\,P_1P_2\,\right|\left\lbrace\left(1-\frac{f}{F}\right)^{n-2}+\left(\frac{f}{F}\right)^{n-2}\right\rbrace dP_1,dP_2;$$
here $f$ is the smaller area that is cut off of $K$ by the line $g(P_1,\,P_2)$, which implies $f/F\leqq 1/2$. Therefore
$$(4)\quad E(L_n)\sim\frac{\binom{n}{2}}{F^2}\iint\left(1-\frac{f}{F}\right)^{n-2}\left|\,P_1P_2\,\right|dP_1\,dP_2.$$
We now, using the same notation as in $[1],\,(41)$ apply the transformation
$$(5)\quad dP_1\,dP_2=\left|1_1-t_2\right|dt_1\,dt_2\,dp\,d\varphi$$
because $\left|t_1-t_2\right|=\left|P_1P_2\right|$ and
$$(6)\iint_{g(p,\varphi)\cap K}\left|t_1-t_2\right|^2dt_1\,dt_2=\frac{l^4}{6}$$
where $l=l(\varrho,\varphi)$ denotes the length of the chord $g(p,\varphi)\cap K$, we get
$$(7)\quad E(L_n)\sim\frac{\binom{n}{2}}{6F^2}\int_0^{2\pi}\int_0^{p(\varphi)}\left(1-\frac{f}{F}\right)^{n-2}l^4dp\,d\varphi.$$
Here $p(\varphi)$ is the support function of region $K$; we chose as the origin $K$'s center of gravity.
Let now $p(P_i,\,P_j)$ denote the distance of the line $g(P_i,\,P_j)$ from the origin $0$. Then, for the area of $H_n$, we have
$$(8)\quad F_n=\frac{1}{2}\sum_{i\lt j}\varepsilon_{ij}\left|P_i\,P_j\right|p(P_i,\,P_j).$$
By conclusions that are close analogues to those as in the case of the circumference, we get
$$(9)\quad E(F_n)\sim\frac{\binom{n}{2}}{12F^2}\int_0^{2\pi}\int_0^{p(\varphi)}\left(1-\frac{f}{F}\right)^{n-2}l^4p\,dp\,d\varphi.$$
§ 2. The approximation by an osculating circle
Our task is now to evaluate the integrals $(7)$ and $(9)$. In this and in the following paragraph we assume that $K$ has a smooth boundary with curvature $k(s),\ 0\lt k(s)\lt A$. We first fix $\varphi$ and carry out the integration over $p$. As for the asymptotic behavior of the integrals only that contribution is important, for which $f/F$ is small, we may replace the values $l,\, f$ of $K$ with the corresponding values $\bar l,\,\bar f$ of the osculating circle, that shares the tangent $g\left(p(\varphi),\,\varphi\right)$ with $K$, The error that is generated by that replacement shall now be estimated. This will yield improvements of the formulas $[1](47)$.
Instead of $p$ we now introduce the new parameter $\beta$, which is half the central angle from the center $Z$ of the osculating circle$S_{\varphi}$ onto the chord $g(p,\,\varphi)\cap S_{\varphi}$. Then we have (cmp. fig. 1)
$$\quad p=r(\cos \beta\, -\, 1)+p(\varphi).$$
Here $r$ denotes the radius of curvature: $r=1/k$. On the line $g(\beta,\varphi)$ we introduce the arc length $t$ as a parameter and denote by $t_1^-,\,t_1^+$ 1the parameters of the intersection points of $g$ with the boundary of $K$. If we chose the center of the chord $g\cap S_{\varphi}$ as the zero-point of the arc length $t$ then it follows immediately that
$$(11)\quad t_1^-=-r\sin\beta,\ t_1^+=r\sin\beta$$.
We now want to calculate $t_2^-,\,t_2^+$ as functions of $\beta$. For that purpose we represent the boundary of $K$ in a neighborhood of the considered point in the acompanying bipod (i.e. in the Frenet frame). Let $\mathfrak{x}(s)$ be the local vector of a variable point of the the boundary curve from the point of contact, $\mathfrak{t}$ a tangent vector and $\mathfrak{n}$ the normal vector in that point. If we chose the point of contact also as the zero-point of the boundary curve's arc length $s$, then, taking ito account the Frenet formulas of planar differential geometry, Taylor's formula yields the following representation:
$$\quad\quad\mathfrak{x}=\mathfrak{t}\cdot\left\lbrace s-k^2\frac{s^3}{3!}-3k\,k'\frac{s^4}{4!}+\pmb{0}(s^5)\right\rbrace+$$
$$(12)$$
$$\quad\quad+\mathfrak{n}\left\lbrace k\frac{s^2}{2!}+k'\frac{s^3}{3!}+(k''-k^3)\frac{s^4}{4!}+\pmb{0}(s^5)\right\rbrace.$$
Here the coefficients have to be taken at $s=0$; apostrophes denote differentiation w.r.t. arc length.
In this coordinate system the line $g(\beta,\varphi)$ has the parametric representation
$$(13)\quad \mathfrak{z}(t)=\mathfrak{t}\cdot t+\mathfrak{n}\cdot r(1-\cos\beta).$$
The comparison with $(12)$ provides us with the following two relations
$$(14)\quad t_2=s-k^2\frac{s^3}{3!}-3k\,k'\frac{s^4}{4!}+\pmb{0}(s^5).$$
$$(15)\quad r(1-\cos\beta)=k\frac{s^2}{2!}+k'\frac{s^3}{3!}+(k''-k^3)\frac{s^4}{4!}+\pmb{0}(s^5).$$
From $(15)$ we obtain $s$ as a function of $\beta$:
$$(16)\quad s=r\beta-\frac{k'r^3\beta^2}{3!}\beta^2+\frac{r^4}{4!}\left\lbrace\frac{5}{3}k'^2r-k''\right\rbrace\beta^3+\pmb{0}(\beta^4);$$
If we insert that in $(14)$, it follows that
$$(17)\quad t_2=r\beta-\frac{k'r^3}{3!}\beta^2+\left\lbrace\frac{5}{4!3}r^5k'^2-\frac{r^4k''}{4!}-\frac{r}{3!}\right\rbrace\beta^3+\pmb{0}(\beta^4);$$
where obviously $t^-=t_2(-\beta),\ t_2^+=t_2(\beta)$ for $\beta\geqq0$. The power series expansion of $\sin\beta$ and $(11)$ yield
$$(18)\quad t_1-t_2=\frac{k'r^3}{3!}\beta^2+\frac{r^4}{4!}\left\lbrace k''-\frac{5}{3}rk'^2\right\rbrace\beta^3+\pmb{0}(\beta^4);$$
Here again we get $t_1^+-t_2^+$ for positive $\beta$ and $t_1^--t_2^-$ for negative $\beta$.
Now we take into account that the osculating circle of a curve in a point that isn't a vertex point, for which therefore $k'\ne0$, intersects the curve in the tangent point, as is also shown in our illustration. That implies $l-\bar l=(t_1^--t_2^-) -(t_1^+-t_2^+) $, consequently
$$(19)\quad l-\bar l=\frac{r^4}{12}\left(\frac{5}{3}rk'^2-k''\right)\beta^3+\pmb{0}(\beta^4).$$
Because $k'=0$ in a vertex point and there is a contact of at least third order with the osculating circle, $(19)$ is valid even more in that case; that can be seen immediately from $(18)$.
For the areas $f,\ \bar f$ we get from evaluating the integral
$$\quad f-\bar f=\int_p^{p(\varphi)}(l-\bar l)dp
the following approximation formula:
$$(20)\quad f-\bar f=\frac{r^5}{60}\left(\frac{5}{3}r\,k'2-k''\right)\beta^5+\pmb{0}(\beta^6).$$
§ 3. Calculation of $E(L_n)$ and $E(F_n)$ for an oval region with smooth boundary
We switch to the central angle $\alpha=2\beta$ and express the Integrals $(7)$ and $(9)$ via $\alpha$ and $\varphi$. Because of
$$(21)\quad l=2r\sin\frac{\alpha}{2}\quad\text{and}\quad\bar f= \frac{r^2}{2}(\alpha-\sin\alpha)$$
as well as
$$(22)\quad\left|dp\right|=\left(\frac{r}{2}\sin\frac{\alpha}{2}\right)\left|d\alpha\right|$$
$(19)$ yields
$$(23)\quad l^4dp=\left[\frac{r^5\alpha^5}{4}\left(1+G\alpha^2\right)+\pmb{0}(\alpha^8)\right]d\alpha$$
where we have set
$$(24)\quad G=\frac{5}{4!}\left(\frac{r^4r'^2}{3}-\frac{r^3k''}{5}-1\right)$$
for abbreviation. From $(20)$ and $(21)$ we get
$$(25)\quad \frac{f}{F}=\frac{r^2\alpha^3}{12F}+\varkappa\cdot\alpha^5+\pmb{0}(\alpha^5)$$
where
$$(26)\quad\varkappa=\frac{r^2}{5!2\,F\,}\left[\left(\frac{r}{3}\right)^3\left(\frac{5}{3}rk'^2-k''\right)-1\right].$$
The integral $(7)$ now attains the form
$$\quad\quad E(L_n)\sim\frac{\binom{n}{2}}{4!\,F^2}\int_0^{2\pi}r^5\,d\varphi\int_0^{\alpha(\varphi)}\left(1-\frac{r^2\alpha^3}{12F}-\varkappa\alpha^5-\pmb{0}(\alpha^6)\right)^{n-2}\times$$
$$(27)$$
$$\quad\quad\times(\alpha^5+G\alpha^7+\pmb{0}(\alpha^8))d\alpha$$
We first calculate the integrals
$$(28)\quad B_\nu=\int_0^{\alpha(\varphi)}\left(1-\frac{r^2\alpha^3}{12F}-\varkappa\alpha^5-\pmb{0}(\alpha^6)\right)^{n-2}\alpha^\nu\,d\alpha.$$
Via the substitution
$$(29)\quad\frac{r^2\alpha^3}{12F}=\frac{x}{n}$$
we get, taking into account
$$(30)\quad\left(1-\frac{x}{n}-\varkappa_1\left(\frac{x}{n}\right)^{5/3}+\pmb{0}\Big(\left(\frac{x}{n}\right)^2\right)^{n-2}=e^{-x}\left(1-\frac{\varkappa_1x^{5/3}}{n^{2/3}}+\pmb{0}\left(\frac{x^2}{n}\right)\right)$$
the integral $B_\nu$ in the form
$$(31)\quad B_\nu=\frac{1}{3}\left(\frac{12F}{n\,r^2}\right)^{(\nu+1)/3}\int_0^{nr^2\alpha^3(\varphi)/12F}e^{-x}\left(1-\varkappa_1x^{5/3}n^{-2/3}+\pmb{0}\left(\frac{x^2}{n}\right)\right)x^{(\nu-2)/3}dx.$$
where
$$(32)\quad\varkappa_1=\varkappa\left(\frac{12\,F}{r^2}\right)^{5/3}$$
has been set. If we now integrate in $(31)$ not only to the upper bound that has been given here, but to $+\infty$, we introduce an error of exponential order of magnitude that is neglegible. It follows that
$$(33)\quad B_\nu=\frac{1}{3}\left(\frac{12\,F}{n\,r^2}\right)^{(\nu+1)/3}\cdot\left[\Gamma\left(\frac{\nu+1}{3}\right)-\frac{\varkappa_1}{n^{2/3}}\Gamma\left(\frac{\nu}{3}+2\right)\right]+\pmb{0}\left(n^{-(\nu+4)/3}\right).$$
By inserting $(33)$ into $(27)$ we get
$$(34)\quad E(L_n)=L-a(K)n^{-2/3}+\pmb{0}\left(\frac{1}{n}\right).$$
The constant $a(K)$ results from calculating
$$(35)\quad a(K)=\Gamma\left(\frac{11}{3}\right)\int_0^{2\pi}\varkappa_1\,r\,d\varphi-(12\,F)^{2/3}\Gamma\left(\frac{8}{3}\right)\int_0^{2\pi}Gr^{-1/3}d\varphi$$
taking into account $(24)$, $(26)$ and $(32)$ in the form
$$(36)\quad a(K)=\frac{(12\,F)^{2/3}\Gamma\left(\frac{8}{3}\right)}{4!}\int_0^L\left[\frac{9}{5}k^{4/3}+\frac{3}{5}k''k^{-5/3}-k'^{\,2}k^{-8/3}\right]ds.$$
Here, instead of $\varphi$, the arclength $s$ of the boundary curve of $K$ has been introduced as the parameter; as it is valid that $d\varphi=k\,ds$. By partial integration it follows that
$$(37)\quad\frac{3}{5}\int_0^Lk''\,k^{-5/3}ds=\int_0^Lk'^{\,2}k^{-8/3}ds.$$
Therefore, for $a(K)$ we finally get
$$(38)\quad a(K)=\frac{1}{12}\Gamma\left(\frac{2}{3}\right)(12\,F)^{2/3}\int_0^Lk^{4/3}ds.$$
For the calculation of $E(F_n)$ we also carry out the substitution $(22)$ and get
$$\quad\quad E(F_n)\sim\frac{\binom{n}{2}}{12\,F}\int_0^{2\pi}\int_0^{\alpha(\varphi)}\left(1-\frac{r^2\alpha^3}{12\,F}-\varkappa\alpha^5-\pmb{0}(\alpha^6)\right)^{n-2}\times$$
$$(39)$$
$$\quad\quad\times\left[\frac{p(\varphi)r^5\alpha^5}{4}+\left(\frac{Gp(\varphi)r^5}{4}-\frac{r^5}{32}\right)\alpha^7+\pmb{0}(\alpha^8) \right]d\alpha\,d\varphi.$$
According to $(33)$ that yields
$$(40)\quad E(F_n)=F-b(K)n^{-2/3}+\pmb{0}(n^{-1})$$
For the costant $b(K)$ we first find after some calculations
$$(41)\quad b(K)=\frac{1}{16}\Gamma\left(\frac{8}{3}\right)(12\,F)^{2/3}\sigma(K)+c(K);$$
where
$$(42)\quad\sigma(K)=\int_0^Lk^{1/3}ds$$
is the equi affine arclength of the boundary curve of $K$, while $c(K)$ is of the form
$$(43)\quad c(K)=\frac{\Gamma\left(\frac{8}{3}\right)}{4!}(12\,F)^{2/3}\int_0^{2\pi}p\,r^{-1/3}\left(\frac{9}{10}+\frac{3}{10}r^3k''-\frac{1}{2}r^4k'^{\,2}\right)d\varphi.$$
By a dot above we now denote derivations with respect to $\varphi$ and express $k',\,k''$ via $r,\,\dot r,\,\ddot r$. It follows
$$(44)\quad c(K)=\frac{\Gamma\left(\frac{8}{3}\right)(12\,F)^{2/3}}{4!\,10}\int_0^{2\pi}p(9\,r^{-1/3}+4\dot r^2\, r^{-7/3}-3\ddot r\, r^{-4/3})\,d\varphi$$
By integrating partially twice, we get
$$(45)\quad \int_0^{2\pi}(4\,\dot r^2r^{-7/3}-3\ddot r r^{-4/3})p\,d\varphi=9\int_0^{2\pi}r^{-1/3}\ddot p\,d\varphi.$$
We now substitute that into $(44)$. Because $p+\ddot p = r$ (cf e.g. W. Blaschke $[2]$, $p. 30$) that again yields a multiple of $\sigma(K)$. Taking into account $(41)$ finally yields
$$(46)\quad b(K)=\frac{1}{10}\Gamma\left(\frac{8}{3}\right)(12\,F)^{2/3}\sigma(K).$$
The results of this paragraph can be summarized as follows:
Theorem 1. Let $K$ be a planar, finite convex region whose boundary curve is sufficiently often continuously differentiable. The curvature $k(s)$ of the boundary shall satisfy the inequality $0\lt k(s)\lt A$. Let $L$ be the circumference and $F$ the area of $K$. The length $L_n$ of the convex hull $H_n$ of $n$ points in $K$ that are chosen independently and according to equal distribution, possesses the mathematical expectation
$$(47)\quad E(L_n)=L-\frac{\Gamma(2/3)(12\,F)^{2/3}\int_0^Lk^{4/3}ds}{12\,n^{2/3}}+\pmb{0}(n^{-1}).$$
For the mathematical expectation of the area $F_n$ of $H_n$ we have
$$(48)\quad E(F_n)=F-\frac{\Gamma\left(\frac{8}{3}\right)(12\,F)^{2/3}\sigma(K)}{10^{2/3}}+\pmb{0}(n^{-1})$$
where $\sigma(K)$ according to* $(42)$ denotes the equiaffine length of the boundary of $K$
§ 4. Calculation of $E(L_n)$ and $E(F_n)$ for a square
Let $K$ now be a square with side length $a$. We place the coordinate origin in the center of $k$ and the null-direction $\varphi=0$ shall go from $\pmb{0}$ to the center of a side. We have to evaluate the integrals $(7)$ and $(9)$ again. For reasons of symmetry it is sufficient to carry out the integration over $\varphi$ from $0$ to $\pi/4$ and multiply by $8$ accordingly. For the integration over $p$ we distinguish two cases. 1. the line $g(\varrho\,\varphi)$ hits two opposite sides of the square. That happens if
$$(49)\quad 0\leqq p\leqq p_1(\varphi)=\frac{a}{2}(\cos\,\varphi-\sin\,\varphi)$$
holds true. For $l$ and $f$ this implies
$$(50)\quad l=l(\varphi)=\frac{a}{\cos\,\varphi}, \quad f=f(p,\,\varphi)=\frac{a^2}{2}-\frac{ap}{\cos\,\varphi}$$
\2. the line $g(p,\,\varphi)$ hits two adjacent sides of the square. In that case we have
$$(51)\quad p_1(\varphi)\leqq p\leqq p(\varphi)=\frac{a}{2}(\cos\,\varphi+sin\,\varphi).$$
Further we have
$$(52)\quad l=l(p,\,\varphi)=\frac{p(\varphi)-p}{\cos\,\varphi\,\sin\,\varphi},\quad f=f(p,\,\varphi)=\frac{\left(p(\varphi)-p\right)^2}{2\,\sin\,\varphi\,\cos\,\varphi}.$$
Because of this distinction of cases the integrals $(7)$ and $(9)$ appear now as sums
$$(53)\quad E(L_n)\sim I_1+I_2,\quad E(F_n)\sim J_1+J_2$$
and we have to evaluate the following four expressions:
$$(54)\quad I_1=\frac{4}{3}\binom{n}{2}\_0^{\pi/4}\int_0^{p_1(\varphi)}\left(\frac{1}{2}+\frac{p}{a\,\cos\,\varphi}\right)^{n-2}\frac{dp\,d\varphi}{\cos^4\varphi},$$
$$(55)\quad I_2=\frac{4\,\binom{n}{2}}{3\,a^4}\int_0^{\pi/4}\int_{p_1(\varphi)}^{p(\varphi)}\left(1-\frac{\left(p(\varphi)-p\right)^2}{2a^2\sin\,\varphi\,\cos\,\varphi}\right)^{n-2}\frac{\left(p(\varphi)-p\right)^4dp\,d\varphi}{\cos^4\varphi\,\sin^4\varphi},$$
$$(56)\quad J_1=\frac{2}{3}\binom{n}{3}\int_0^{\pi/4}\int_0^{p_1(\varphi)}\left(\frac{1}{2}-\frac{p}{a\,cos\varphi}\right)^{n-2}\frac{p\,dp\,d\varphi}{\cos^4\varphi}.$$
$$(57)\quad J_2=\frac{2\,\binom{n}{2}}{3\,a^4}\int_0^{\pi/4}\int_{p_1(\varphi)}^{p(\varphi)}\left(1-\frac{\left(p(\varphi)-p\right)^2}{2\,a^2\,\sin\,\varphi\,\cos\,\varphi}\right)^{n-2}\frac{\left(p(\varphi)-p\right)^4p\,dp\,d\varphi}{\cos^4\varphi\,sin^4\,\varphi}.$$
We now start with the calculation of $I_1$. Substituting
$$(58)\quad p=x\,a\,\cos\,\varphi$$
yields
$$(59)\quad I_1=\frac{2\,n\,a}{3}\int_0^{\pi/4} \frac{(1-\frac{1}{2}\,tg\,\varphi)^{n-1}}{\cos^3\,\varphi}+\pmb{0}(2^{-n}).$$
If we now substitute
$$(60)\quad tg\,\varphi=t$$
we get $I_1$ in a form that is easy to estimate. It results
$$(61)\quad I_1=\frac{4\,a}{3}+\pmb{0}\left(\frac{1}{n^2}\right).$$
Now we calculate $I_2$. With the substitution
$$(62)\quad \frac{\left(p(\varphi)-p\right)^2}{2\,a^2\,\sin\,\varphi\,\cos\,\varphi}=\frac{x}{n}$$
we have
$$(63)\quad I_2=\frac{2^{5/2}\cdot a(n-1)}{3\,n^{3/2}}\int_0^{\pi/4}(\cos\,\varphi\,\sin\varphi)^{-3/2}\left[\int_0^{(n\,tg\,\varphi)/2}\left(1-\frac{x}{n}\right)^{n-2}x^{3/2}dx\right]\,d\varphi.$$
Now substitute
$$(64)\quad n\,tg\,\varphi = z$$
and get
$$(65)\quad I_2=\frac{2^{5/2}\cdot a(n-1)}{3\,n}\int_0^n\left(\frac{1+\frac{z^2}{n^2}}{z^3}\right)^{1/2}\int_0^{z/2}\left(1-\frac{x}{n}\right)\,x^{3/2}dx\,dz\,.$$
We set
$$(66)\quad\left(1+\frac{z^2}{n^2}\right)^{1/2}=\left[\left(1+\frac{z^2}{n^2}\right)^{1/2}-1\right]+1$$
and thus partition the integral $(65)$ into two components. With the substitution $z=n\,\tau$ we get for the first part:
$$(67)\quad \frac{2^{5/2}\cdot a(n-1)}{3\,n}\int_0^n\frac{\sqrt{1+\frac{z^2}{n^2}}-1}{z^{3/2}}\int_0^{z/2}\left(1-\frac{x}{n}\right)^{n-2}x^{3/2}dx\,dz=\sqrt{\frac{2\pi}{n}}\,aq+\pmb{0}\left(\frac{1}{n}\right)$$
where
$$(68)\quad q=\int_0^1\frac{\sqrt{1+\tau^2}\,-1}{\tau^{3/2}}d\tau$$
For the second part we obtain after several elementary rearrangements
$$(69)\quad\frac{2^{5/2}\cdot a(n-1)}{3\,n}\int_0^n\left(\int_0^{z/2}\left(1-\frac{x}{n}\right)^{n-2}x^{3/2}dx\right)\frac{dz}{z^{3/2}}=\frac{8\,a}{3}-2\sqrt{\frac{2\pi}{n}}\cdot a+\pmb{0}\left(\frac{1}{n}\right)\,.$$
From $(61)$, $(67)$ and $(69)$ we get for the mathematical expectation of $L_N$
$$(71)\quad E(L_n)=4\,a\,-\,\frac{a\,(2-q)\sqrt{2\pi}}{\sqrt{n}}+\pmb{0}\left(\frac{1}{n}\right)\,.$$
For the calculation of $J_1$ one again applies the transformations $(58)$ and after that $(60)$. After some elementary calculations one gets
$$(71)\quad J_1=\frac{1}{3}a^2+\pmb{0}\left(\frac{1}{n}\right)\,.$$
Finally, we also have to calculate the integral $J_2$. The substitution $(62)$ leads to $J_2=R_1-R$ with
$$(72a)\quad R_1=\frac{4\,a^2(n-1)}{3\,n^{3/2}}\int_0^{\pi/4}\frac{\cos\,\varphi+\sin\varphi}{(\sin\,2\,\varphi)^{3/2}}\left(\int_0^{(n\,tg\,\varphi)/2}\left(1-\frac{x}{n}\right)^{n-2}x^{3/2}dx\right)\,d\varphi,$$
$$(72b)\quad R=\frac{8\,a^2(n-1)}{3\,n^2}\int_0^{\pi/4}\left[\int_0^{(n\,tg\,\varphi)/2}\left(1-\frac{x}{n}\right)^{n-2}x^2\,dx\right]\frac{d\varphi}{\sin\,2\,\varphi}\,.$$
The calculation of $R_1$ is easily possible via the substitution $(64)$. It results in
$$(73)\quad R_1=\frac{2}{3}\,a^2+\pmb{0}\left(\frac{1}{n}\right)\,.$$
For $R$ we get via the substitution
$$(74)\quad\frac{n\,tg\,\varphi}{2}=t$$
the expression
$$(75)\quad R=\frac{4\,a^2(n-1)}{3\,n^2}\int_0^{n/2}\left(\int_0^t\left(1-\frac{x}{n}\right)^{n-2}x^2dx\right)\frac{dt}{t}\,.$$
If we integrate over $x$, this yields
$$(76)\quad R=\frac{8\,a^2}{3(n+1)}\int_0^{n/2}\left[1-\left(1-\frac{t}{n}\right)^{n+1}\right]\frac{dt}{t}+\pmb{0}\left(\frac{1}{n}\right)\,.$$
For calculating the integral that appears in $(76)$ we use the formula
$$(77)\quad\frac{1}{t}\left[1-\left(1-\frac{t}{n}\right)^{n+1}\right]=\sum_{k=0}^n\left(1-\frac{t}{n}\right)^k\,.$$
It follows
$$(78)\quad \int_0^{n/2}\left[1-\left(1-\frac{t}{n}\right)^{n+1}\right]\frac{dt}{t}=\ln\,n+C-\log\,2+\pmb{0}\left(\frac{1}{n}\right)\,.$$
here $C$ is the Euler constant. This results in
$$(79)\quad J_2=R_1-R=\frac{2a^2}{3}-\frac{8\,\ln\,n}{3\,n}+\pmb{0}\left(\frac{1}{n}\right)\,.$$
If we take into account formula $(70)$ and $E(F_n)=J_1+J_2$, we can summarize the results of this paragraph in the following theorem:
Theorem 2. In a square $K$ with sidelength $a$ let $H_n$ denote the convex hull of $n$ points chosen independently and equally distributed from $K$. For the mathematical expectation of the circumference $L_n$ of $H_n$ it is valid that
$$(80)\quad E(L_n)=4\,a-\frac{a(2-q)\sqrt{2\pi}}{\sqrt{n}}+\pmb{0}\left(\frac{1}{n}\right)$$
where the constant $q$ is given by $(68)$. For the mathematical expectation of the area $F_n$ of $H_n$ it is valid that
$$(81)\quad E(F_n)=a^2-\frac{8\,a^2\,\ln\,n}{3\,n}+\pmb{0}\left(\frac{1}{n}\right)\,.$$
References
$[1]$ Rényi, A. u. R. Sulanke: Über die konvexe Hülle von $n$ zufällig gewählten Punkten,
Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 2 (1963) 75-84.
$[2]$ Blaschke, W.: Vorlesungen über Integralgeometrie, 3. Aufl., Berlin, VEB Deutscher Verlag der Wissenschaften, 1955.
Budapest, VI, Hungary Benczur u.28
and
Schulzendorf upon Eichwalde near Berlin
Hamburger Straße 4
(Received on 7th October 1963)
Random convex polygons I
As I mentioned in one of my earlier posts, the early work of Renyi and Sulanke on random planar convex polygons was available only in German. This consists of three separate articles published over a couple of years. Now, courtesy of the efforts of Manfred Weis, English translations are available to the non-German-reading audience. What follows is the first in this series of articles.
Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 2 (1963) 75-84.
On the Convex Hull of $n$ Randomly Chosen Points I
by
A.Rényi and R. Sulanke
Introduction
Let $P_i (i=1,2,\cdots, n)$ be $n$ points of the plane chosen randomly according to a certain distribution and, let $H_n$ denote the convex hull of these points, which is a convex polygon as is commonly known. The number $X_n$ of sides of $H_n$ is then a random variable, whose behavior as $n\rightarrow\infty$ under various assumptions on the distribution of the points $P_i$ will be investigated in this paper. To this end It is assumed that the points $P_i$ are distributed independently and according to the same distribution. By $E_n=E(X_n)$ we denote the mathematical expected value of $X_n$.
In § 1 we consider the case that the $P_i (i=1, \cdots,\ n)$ are distributed equally in a convex Polygon $K$ with $r$ corners. It will be shown that $E_n=(2r/3)(\log n+C)+T+\omicron(1)$; here $C$ denotes the Euler constant. The value $T=T(k)$ depends on the region $K$. In § 2 we prove the elementary geometric theorem that $T(k)$ will be maximal for polygons that are affinely equivalent to the regular $r$-gons and only for those. In § 3 the asymptotic behavior of $E_n$ will be investigated if the $P_i$ are distributed in a convex region with smooth boundary. It turns out that $E_n$ has $\sqrt[3]{n}$ order of magnitude. In § 4 we finally prove that $E_n$ behaves as $\sqrt{\log n}$ if the points $P_i$ are normally distributed.
§1 . Random points in a convex polygon
Let $K$ be a convex polygon with corners $A_1,\ A_2,\ \dots,\ A_r$ and the corresponding angles $\vartheta_1,\ \vartheta_2,\ \dots,\ \vartheta_r$. Let $a_k$ denote the length of the side $A_kA_{k+1}$ ($k=1,\ \dots,\ r$; $A_{r+1}=A_1$). Let further $F$ denote the area of $K$.
Let $\varepsilon_{ij}=1$, if $i\ne j$ and the edge $P_iP_j$ is part of the boundary of $H_n$, and $\varepsilon_{ij}=0$ otherwise. Then obviously
$$(1) \quad X_n =\sum_{1\leqq i\lt j\leqq n}{\varepsilon_{ij}}$$
The probability
$$(2)\quad W_n=P(\varepsilon_{ij}=1)$$
is the same for pairs $(i,j)$ of numbers with $1\leqq i\lt j\leqq n$ and it holds true that
$$(3)\quad E_n = E(X_n)=\binom{n}{2}W_n$$
To determine the asymptotic behavior of $E_n$ it therefore suffices to calculate the probability $W_n$. Now $W_n$ is the probability that all points $P_h$ ($h=3,\ 4,\ \dots,\ n$) lie to the same side of the line through $P_1$ and $P_2$. If we denote by $F_1\le F/2$ and $F-F_1$ the areas of the parts of $K$ in which $K$ is divided by the line $P_1P_2$, it holds true that
$$(4)\quad W_n=\frac{1}{F^2}\int_K\int_K\left[\left(1-\frac{F_1}{F}\right)^{n-2}+\left(\frac{F_1}{F}\right)^{n-2}\right]dP_1dP_2$$
Obviously, because $F_1/F\le1/2$,
$$\frac{1}{F^2}\int_K\int_K\left(\frac{F_1}{F}\right)dP_1dP_2\leqq\frac{1}{2^{n-2}}$$
and therefore
$$(5)\quad E_n\sim\frac{\binom{n}{2}}{F^2} \int_K\int_K\left(1-\frac{F_1}{F}\right)^{n-2}dP_1dP_2,$$
where $\sim$ means "asymptotically equal", i.e., $A_n\sim B_n$ means that $\lim_{n\rightarrow+\infty}\frac{A_n}{B_n}=1$.
Let now $f_i$ denote the area of the triangle $A_{i-1}A_iA_{i+1}$ ($A_{r+j}=A_j$), and be $f=\min_{1\leqq i\leqq r}{f_i}$. Obviously we can restrict ourselves to such point pairs $P_1$, $P_2$ for which the line $P_1P_2$ either hits two neighboring sides or two sides that are separated by another side of $K$. This is so because for all other lines $1-F_1/F\leqq1-f/F$. Therefore we can neglect the right side of $(5)$ and it holds true that
$$(6)\quad E_n\sim\frac{\binom{n}{2}}{F^2}\left(\sum_{i=1}^r\left(i+J_i\right)\right),$$
where
$$(7)\quad I_i =\int_{C_i}\left(1-\frac{F_1}{F}\right)^{n-2}dP_1dP_2$$
and
$$(8)\quad I_i =\int_{D_i}\left(1-\frac{F_1}{F}\right)^{n-2}dP_1dP_2$$
Here $C_i$ denotes the set of point pairs $P_1$, $P_2$ for which the line $P_1P_2$ hits the sides $A_{i-1}A_i$ and $A_iA_{i+1}$ of $K$, and $D_i$ the set of point pairs for which the line $P_1P_2$ hits the sides $A_{i-1}A_i$ and $A_{i+1}A_{i+2}$ of $K$.
We first investigate the integral $I_i$. Let $G_{ab}$ denote the set of point pairs $P_1$, $P_2$ for which the $|A_iQ_1|\lt a$ and $|A_iQ_2|\lt b$ holds; here $Q_1$ denotes the intersection point of line $P_1P_2$ with side $A_{i-1}A_i$ and $Q_2$ its intersection point with side $A_iA_{i+1}$, further $|AB\ |$ denotes the length of the segment $AB$.
Via an elementary calculation it turns out that
$$(9)\quad\int_{G_{ab}}dP_1dP_2 =\frac{a^2b^2\sin^2\vartheta_i}{12}$$
The area of the triangle $Q_1A_iQ_2$ that is cut off by the line $P_1P_2$ equals $1/2\ a\,b\sin\vartheta_i$ . Therefore we have
$$(10)\quad I_i=\int_0^{a_{i-1}}\int_0^{a_i}\left(1-\frac{a\,b\sin\vartheta_i}{2F}\right)^{n-2}\sin^2\vartheta_i\frac{a\,b}{3}\,da\, db,$$
where $a_i$ denotes the length of side $A_iA_{i+1}$.
Via the transformation
$$(11)\quad X= a\sqrt{\frac{\sin\vartheta_i}{2\,F}},\quad Y= b\sqrt{\frac{\sin\vartheta_i}{2\,F}}$$
we get
$$(12)\quad I_i =\frac{4\,F^2}{3}\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-2}XY\,dX\,dY,$$
where
$$\quad X_i=a_{i-1}\,\sqrt{\frac{\sin\vartheta_i}{2F}},\quad Y_i=a_i\,\sqrt{\frac{\sin\vartheta_i}{2F}},$$
therefore
$$(13)\quad\varrho_i = X_iY_i=\frac{a_{i-1}a_i\sin\vartheta_i}{2\,F}=\frac{f_i}{F}\lt 1$$
holds true. Now we have
$$\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-2}XY\,dX\,dY=\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-2}dX\,dY-\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-1}XY\,dX\,dY$$
Further it is true that
$$\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-1}XY\,dX\,dY=\int_0^{X_i}\frac{1-\left(1-XY_i\right)^n}{n}dX=$$
$$\quad =\frac{1+\frac{1}{2}+\cdots+\frac{1}{n}-\sum_{k=1}^n{\frac{\left(1-\varrho_i\right)^k}{k}}}{n}$$
thus we get
$$(14)\quad I_i=\frac{4\,F^2}{3}\left\lbrace\frac{\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}}{n(n-1)}-\frac{\sum_{k=1}^{n-1}\frac{(1-\varrho_i)^k}{k}}{n(n-1)}+\frac{(1-\varrho_i)^n}{n^2}\right\rbrace$$
If we set
$$(15)\quad S_i=\sum_{k=1}^\infty\frac{(1-\varrho_i)^k}{k}=\log\frac{1}{\varrho_i},$$
that finally results in
$$(16)\quad E_n=\frac{2}{3}\left(C-1+\log n\right)r-\frac{2}{3}\sum_{i=1}^rS_i+\omicron(1)+\frac{\binom{n}{2}}{F^2}\sum_{i=1}^rJ_i,$$
where $C$ is the Euler constant.
Now we calculate the integral $J_i$ .We extend the sides $A_{i-1}A_i$ and $A_{i+2}A_{i+2}$ to their intersection point $A_i^*$; the case that these sides are parallel can be treated similarly. Let again $Q_1$ be the intersection point of lines $P_1P_2$ with the side $A_{i-1}A_i$ and $Q_2$ be the intersection point with the side $A_{i+1}A_{i+2}$ and let $a' = |A_iA_i^*|$, $b'=|A_{i+1}A_i^*|$, $a=|A_iQ_1|$, $b=|A_{i+1}Q_2|$; $G_{ab}$ be defined as above. We obtain from $(9)$
$$(17)\quad\int_{G_{ab}}dP_1\,dP_2=\frac{\sin^2\gamma_i}{12}\left(a^2+2aa'\right)\left(b^2+2bb'\right)$$
where $\gamma_i$ denotes the angle at $A_i^*$. Consequently
$$(18)\quad J_i=\int_{D_i}\left(1-\frac{(ab+a'b+ab')\sin\gamma_i}{2F}\right)^{n-2}\frac{\sin^2\gamma_i}{3}(a+a')(b+b')da\,db$$
and that integral is asymptotically equal to
$$(19)\quad J_i\sim \int_{D_i}\left(1-\frac{(a'b+ab')\sin\gamma_i}{2F}\right)^{n-2}\frac{\sin^2\gamma_i}{3}a'b'\,da\,db$$
If we carry out the transformation
$$ \quad a=\frac{F}{b'\sin\gamma_i},\quad b=\frac{F}{a'\sin\gamma_i}Y$$
it follows that
$$\quad J_i\sim\frac{F^2}{3}\int_0^{a'_{i-1}}\int_0^{a'_{i+1}}\left(1-\frac{X+Y}{2}\right)^{n-2}dX\,dY=$$
$$\quad=\frac{4\,F^2}{3n(n-1)}\left\lbrace1-\left(1-\frac{a'_{i-1}}{2}\right)^n-\left(1-\frac{a'_{i+1}}{2}\right)^n+\left(1-\frac{a'_{i-1}+a'_{i+1}}{2}\right)^n\right\rbrace,$$
where
$$\quad a'_{i-1} = \frac{a_ib'\sin\gamma_i}{F},\quad a'_{i+1} = \frac{a_{i+2}a'\sin\gamma_i}{F}$$
has been set. Consequently this yields
$$\quad E_n=\frac{2r}{3}\left(\log n+C\right)-\frac{2}{3}\sum_{i=1}^rS_i+\omicron(1).$$
Lets summarize what has been proven in the following theorem:
Theorem 1. Let $K$ be a convex polygon with $r$ sides. The mathematical expectation $E_n$ of the number of sides of the convex hull $H_n$ of $n$ in $K$ randomly chosen points is equal to
$$(20)\quad E_n=\frac{2r}{3}\left(\log n+C\right)+\frac{2}{3}\log\frac{\prod_1^rf_i}{F^r}+\omicron(1)$$
Here $F$ denotes the area of $K$ and $f_i$ the area of the triangle that is defined by corners $A_{i-1}A_iA_{i+1}$ of $K$.
If for example $K$ is a triangle, then $f_1=f_2=f_3=F$ and it follows that
$$(21)\quad E_n=2(\log n+C)+\omicron(1).$$
The formula for $E_n$ doesn't depend on the shape of the triangle. That is reasonable because $E_n$ must obviously be invariant under affine transformations. In §2 we will show the constant
$$(22)\quad Z(K)=\frac{\prod_1^rf_i}{F^r}$$
that appears in $(20)$ and depends on the shape of $K$ becomes maximal for regular $r$-gons (and for the polygons that are affinely equivalent to them).
§ 2. An Extremal Value Problem for Convex Polygons
Before we turn to further asymptotic estimates for $E_n$ under different conditions on the distribution of the points $P_i$, we prove the following
Theorem 2. Let $K$ be a convex polygon with $r$ sides. Then we have with notations of the previous §: The function
$$(23)\quad Z(K)=\frac{1}{F^r}\prod_{i=1}^{r}f_i$$
is maximal if and only if $K$ can be affinely transformed to the regular $r$-gon.
Let $\mathfrak{a}_i=\overrightarrow{A_{i-1}A_i}$, where $A_{r+i}=A_i$ shall be set. Then it holds true that
$$(24)\quad f_i=\frac{1}{2}[\mathfrak{a}_i,\mathfrak{a}_{i+1}],\quad F=\frac{1}{2}\sum_{i=1}^{r-2}[\mathfrak{a}_1+\mathfrak{a}_2+\cdots+\mathfrak{a}_i,\mathfrak{a}_{i+1}]$$
where $[\mathfrak{a},\mathfrak{b}]$ denotes the determinant of vectors $\mathfrak{a},\mathfrak{b}$. The function $Z(K)$ is now a function of the $r$ vectors $\mathfrak{a}_i$ ($i=1,\,\dots,\,r$) , which satisfy the closing condition
$$(25)\quad\sum_{i=1}^r\mathfrak{a}_i=0$$
We now imagine the corners $A_i$ of $K$ subjected to sufficiently small displacements, that depend continuously differentiable on a parameter $t$. As the original polyon $K$ that shall correspond to parameter value $t=0$ is a convex $r$-gon, then also the polygons that are generated by sufficiently small displacements will be convex $r$-gons. The function $Z$ when considered as a function of $t$ must have a maximum at $T=0$ if $K$ is a maximal polygon. As a necessary condition for $K$ being maximal we get by elementary calculation:
$$(26)\quad\sum_{i=1}^r\frac{F}{f_i}\left(\left[\mathfrak{\dot a}_i+\mathfrak{a}_{i+1}\right]+\left[\mathfrak{a}_i+\mathfrak{\dot a}_{i+1}\right]\right )\ -$$
$$\quad\ -\ r\sum_{i=1}^{r-2}\left(\left[\mathfrak{\dot a}_1+\cdots+\mathfrak{\dot a}_i,\mathfrak{a}_{i+1}\right]+\left[\mathfrak{a}_1+\cdots+\mathfrak{ a}_i,\mathfrak{\dot a}_{i+1}\right]\right )=0$$
Here
$$\quad \mathfrak{\dot a}_i=\frac{d}{dt}\mathfrak{a}\Bigg|_{i=0}$$
has been set. The $\mathfrak{\dot a}$ are arbitrary vectors that only have to satisfy the closing conditions
$$(27)\quad\sum_{i=1}^r\mathfrak{\dot a}_i=0$$
that follow from $(25)$. If we now one by one set
$$(28)\quad \mathfrak{\dot a}_j=\mathfrak{b},\ \mathfrak{\dot a}_{j+1}=-\mathfrak{b},\ \mathfrak{\dot a}_i=0 \text{ for } i\ne j,\ j+1,$$
where $\mathfrak{b}$ presently still is an arbitrary vector, the closing condition is obviously fulfilled and for $j\,=\,1,\, \ldots,\,r$ we obtain
$$(29)\quad\frac{F}{r}\left\lbrace\frac{[\mathfrak{a}_j,\mathfrak{b}]}{f_{j-1}}-\frac{[\mathfrak{b},\mathfrak{a}_{j+2}]}{f_{j+1}}+\frac{1}{f_j}[\mathfrak{b},\mathfrak{a}_j+\mathfrak{a}_{j+1}]\right\rbrace=[\mathfrak{b},\mathfrak{a}_j+\mathfrak{a}_{j+1}].$$
if we now set specifically $\mathfrak{b}=-\mathfrak{a}_j$, then consequently
$$(30)\quad\frac{F}{r}\left\lbrace4-\frac{[\mathfrak{a}_j,\mathfrak{a}_{j+2}]}{f_{j+1}}\right\rbrace=2f_j$$
and for setting $\mathfrak{b}=-\mathfrak{a}_{j+1}$ we get
$$(31)\quad\frac{F}{r}\left\lbrace4-\frac{[\mathfrak{a}_{j-1},\mathfrak{a}_{j+1}]}{f_{j-1}}\right\rbrace =2f_j$$
Comparing these formulas yields
$$(32)\quad[\mathfrak{a}_j,\mathfrak{a}_{j+2}]=\frac{f_{j+1}}{f_{j-1}}[\mathfrak{a}_{j-1},\mathfrak{a}_{j+1}]$$
We now write $(31)$ in the form
$$\quad 2\left(2-\frac{rf_j}{F}\right)=\frac{[\mathfrak{a}_{j-1},\mathfrak{a}_{j+1}]}{f_{j-1}}$$
and obtain by repeated application of $(32)$
$$\quad\quad 2\left(2-\frac{rf_j}{F}\right)=\frac{f_j}{f_1\cdot f_2}[\mathfrak{a}_1,\mathfrak{a}_3]$$
or
$$(33)\quad f_j=\frac{2}{\frac{r}{F}+\frac{[\mathfrak{a}_1,\mathfrak{a}_3]}{2f_1\cdot f_2}}$$
For $r=3$ our optimization task is trivial. In case $r\geqq 4$ we first get $f_3=f_4=\cdots=f_r$. By a cyclic exchanging of the numbering of the corners of $K$ it immediately follows that
$$(34)\quad f_1=f_2=\cdots=f_r$$
and according to $(32)$ besides that we get
$$(35)\quad [\mathfrak{a}_i,\mathfrak{a}_{i+2}]= [\mathfrak{a}_1,\mathfrak{a}_3]=\mathfrak{b}\quad(i=1,2,\ldots,r)$$
where $b$ is a certain constant.
Remark In case $b=[\mathfrak{a}_i,\mathfrak{a}_{i+2}]=0$ we have $f_j=2F/r$. Therefore $\mathfrak{a}_[i+2]$ is always parallel to $\mathfrak{a}_i$. That is only possible if $r=4$ and $K$ is a parallelogram.
We now return to the general case. Via an affine transformation we can always achieve that $f_i=1/2$, i.e. we have
$$(36)\quad[\mathfrak{a}_i,\mathfrak{a}_{i+1}]=1$$
Then from $(33)$ follows immediately
$$(37)\quad F=\frac{r}{2(2-b)} \text{ and therefore }b\lt2.$$
As the vectors $\mathfrak{a}_{i-2}$ and $\mathfrak{a}_{i-1}$ are linearly independent, the ansatz $\mathfrak{a}_i=\alpha\mathfrak{a}_{i-2}+\beta\mathfrak{a}_{i-1}$ and keeping in mind $(35)$ and $(36)$ leads to the recursion
$$(38)\quad\mathfrak{a}_i=-\mathfrak{a}_{i-2}+b\mathfrak{a}_{i-1}$$
We have consequently shown that the side's vectors $\mathfrak{a}_i$ of a maximal convex $r$-gon must necessarily satisfy a recursion of type $(38)$. The proof will now be carried to an end by showing that in that case an Euclidean metric can be defined in the affine plane that lets polygon $K$ appear to be a regular $r$-gon.
First we remark that always
$$(39)\quad-1\leqq b\le2$$
must be true. Were namely $b\lt -1$ then side $\mathfrak{a}_3$ would penetrate side $\mathfrak{a}_1$, which would contradict the convexity of $K$. The estimate $b\lt2$ for the upper bound has already been proven ($(37)$).
The Euclidean metric is uniquely determined if we fix the skalar products of the vectors $\mathfrak{a}_1$, $\mathfrak{a}_2$, which we consider to be basis vectors. We define these skalar products via
$$(40)\quad\mathfrak{a}_1^2=\mathfrak{a}_2^2=\frac{2}{\sqrt{4-b^2}},\quad\mathfrak{a}_1\mathfrak{a}_2=\frac{b}{4-b^2}$$
Obviously
$$\quad[\mathfrak{a}_1,\mathfrak{a}_2]^2=\begin{vmatrix}\mathfrak{a}_1^2&\mathfrak{a}_1\mathfrak{a}_2\\ \mathfrak{a}_1\mathfrak{a}_2&\mathfrak{a}_2^2\end{vmatrix}=1$$
Therefore the so defined metric is positiv definite, i.e. Euclidean. Via complete induction, utilizing $(38)$, it is easy to prove that for all $j$
$$\quad\mathfrak{a}_j^2=\frac{2}{\sqrt{4-b^2}},\quad \mathfrak{a}_j\mathfrak{a}_{j+1}=\frac{b}{\sqrt{4-b^2}},\quad[\mathfrak{a}_j,\mathfrak{a}_{j+1}]=1$$
must be true. From this it follows that all sides of our $r$-gon $K$ must have equal length and that two consecutive sides intersect under the same angle. Therefore that $r$-go must be regular with respect to that metric.
Thus the uniqueness of the maximal polygon has been proven. The existence is the result of an easy conclusion from the boundedness of $Z(K)$, as well as the continuity of $F$ and $Z$. Therefore theorem 2 is completely proven.
§ 3. Random points in a convex region with smooth boundary
Let $K$ now be a convex region whose boundary has a curvature that is a continuous function of arclength. With the notations of the previous paragraphs we again have
$$E_n=\binom{n}{2}W_n.$$
According to known theorem of integral geometry (cf. Blaschke[1], p17, (86)) the density for point-pairs can be reformulated as follows:
$$(41)\quad dP_1\,dP_2=|t_1-t_2|\,dt_1\,dt_2\,d\varphi\,dp,$$
with p meaning the distance of the line $P_1\,P_2$ from the coordinate origin and, $\varphi$ the angle with a zero-direction (translator's remark: that means "a reference direction" that corresponds to the angle of 0°) and $t_1,$ $t_2$ the parameter values of the arc-length of points $P_1$, $P_2$ on the line $P_1\,P_2$. Let $f$ denote the area of the part of $K$ that is cut off by the line $P_1\,P_2$. Then we have
$$(42)\quad E_n=\frac{\binom{n}{2}}{F^2}\int_0^{2\pi}\left\lbrace\int_0^{p(\varphi)}\left(1-\frac{f}{F}\right)^{n-2}\left(\iint|t_1-t_2|\,dt_1\,dt_2\right)dp\right\rbrace d\varphi$$
By $l(p,\varphi)$ we denote the length of the chord in which the line with coordinates $p$, $\varphi$ hits region $K$. Then it holds true that
$$(43)\quad\iint\left|t_1-t_2\right|\,dt_1\,dt_2=\frac{l^3(p,\varphi)}{3}$$
From this we get
$$(44)\quad E_n=\frac{\binom{n}{2}}{3F^2}\int_0^{2\pi}\left\lbrace\left(1-\frac{f}{F}\right)^{n-3}l^3(p,\varphi)\,dp\right\rbrace\,d\varphi.$$
When calculating the asymptotic value of $E_n$ one can obviously restrict to pairs of values $p$, $f/F\lt \varepsilon$ because the other value-pair only contribute to an error term of magnitude $n^2(1-\varepsilon)^n=\omicron(1)$. We now consider a fixed value of $\varphi$. Let $P(\varphi)$ be the point in which the tangent of $K$ has direction $\varphi$. In the calculation of $E_n$ one may replace $f$ and $l$ with the corresponding values$\bar f$ and $\bar l$ of the osculating circle in point $P(\varphi)$, as turns out from the following estimations. Let $\alpha$ be the central angle related to chord $\bar l$ and $r(\varphi)$ the radius of the osculating circle in point $P(\varphi)$. Then
$$(45)\quad\bar l = 2r(\varphi)\,sin\,\alpha/2\quad\text{and}\quad\bar f=\frac{1}{2}(\alpha-\sin\alpha)r^2(\varphi)$$
furthermore
$$(46)\quad\left|dp\right|=\frac{1}{2}r(\varphi)\sin\alpha/2\left|d\alpha\right|$$
and finally
$$(47)\quad l-\bar l=\omicron(\alpha^2)\quad\text{and}\quad f-\bar f=\omicron(\alpha^4)$$
From which we get
$$(48)\quad E_n=\frac{\binom{n}{2}}{12F^2}\int_0^{2\pi}r^4\int_0^{\alpha(\varphi)}\left(1-\frac{\alpha^3r^2}{12F^2}+\omicron(\alpha^3)\right)^{n-2}\left(\alpha^4+\omicron(\alpha^5)\right)\,d\alpha\,d\varphi$$.
By substituting
$$(49)\quad\frac{\alpha^3r^2}{12F}=\frac{X}{n}$$
we get
$$\quad\quad S(\varphi)=\int_0^{\alpha(\varphi)}\left(1-\frac{\alpha^3r^2}{12F}+\omicron(\alpha^3)\right)^{n-2}\left(\alpha^4+\omicron(\alpha^5)\right)\,da$$
$$(50)$$
$$\quad\quad S(\varphi)=\frac{1}{3}\left(\frac{12F}{r^2n}\right)^{5/3}\left(\int_0^\infty\left(1-\frac{X}{n}\right)^{n-2}x^{2/3}dx+\omicron(1)\right)=\frac{\Gamma\left(\frac{5}{3}\right)}{3}\left(\frac{12F}{r^2n}\right)^{5/3}(1+\omicron(1)).$$
Therefore
$$(51)\quad E_n\sim\Gamma\left(\frac{5}{3}\right)\sqrt[3]{\frac{2n}{3F}}\int^{2\pi}r^{2/3}d\varphi.$$
If now $s$ denotes the arclength on the boundary of $K$ we get, taking $d\varphi/ds=1/r$ into account, the following theorem:
Theorem 3. If $K$ is a convex region whose boundary curve $L$ possesses the continuous curvature $\varkappa=\varkappa(s)$, then it holds true that
$$(52)\quad E_n\sim\Gamma\left(\frac{5}{3}\right)\sqrt[3]{\frac{2}{3}}\left(F^{-1/3}\int_L\varkappa^{1/3}ds\right)\sqrt[3]{n}.$$
The integral $\int_L\varkappa^{1/3}ds$ that appears in $(52)$ is just the equi-affine length of curve $L$. One easily sees that the factor of $\sqrt[3]{n}$ even is affine invariant. From the affine isoperimetric property of ellipses (Blaschke-Reidemeister) it follows that that factor is maximal for ellipses and only for those.
§ 4. Normally random distributed points
In this paragraph we prove the following theorem:
Theorem 4. Let the points $P_i$ ($i=1,\,2,\,\ldots,\,n$) be chosen independently and according to the same normal distribution in the plane, then
$$(53)\quad E_n\sim2\sqrt{2\pi\log n}$$
Proof. As $E_n$ is obviously invariant under affine transformations of the plane, we may assume that the density function of our normal distribution has the form $\frac{1}{2\pi}e^{-\frac{x^2+y^2}{2}}$. As already in the previous paragraph we have
$$\quad E_n=\binom{n}{2}W_n,$$
where $W_n$ is the probability that all points $P_3,\,\ldots,\,P_n$ lie on the same side of the line $P_1\,P_2$. Because of the integralgeometric formula
$$\quad\quad dP_1\,dP_2=dp\,d\varphi\,\left|t_1-t_2\right|\,dt_1\,dt_2$$
and because of the radial symmetry of the normal distribution we get
$$(54)\quad W_n=\frac{1}{2\pi}\iiint\left(g(p)^{n-2}+\left(1-g(p)\right)^{n-2}\right)\left|t_1-t_2\right|e^{-p^2 -\frac{t_1^2+t_2^2}{2}}dt_1\,dt_2\,dp$$
where
$$(55)\quad g(p)=\int_{-\infty}^{+\infty}\int_p^{+\infty}\frac{e^\frac{x^2+y^2}{2}}{2\pi}dx\,dy=1-\Phi(p)$$
has been set and
$$(56)\quad \Phi(p)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^pe^{-\frac{u^2}{2}}du$$
holds.
Via the transformation
$$(57)\quad u=\frac{t_1-t_2}{\sqrt{2}},\quad v=\frac{t_1+t_2}{\sqrt{2}},\quad\frac{\partial(t_1,\,t_2)}{\partial(u,\,v)}=1$$
we get
$$(58)\quad \frac{1}{2\pi}\iint\left|t_1-t_2\right|e^{-\frac{t_1^2+t_2^2}{2}}dt_1\,dt_2 =\frac{2}{\sqrt{\pi}}$$
therefore
$$(59)\quad W_n=\frac{2}{\sqrt{\pi}}\int_0^\infty\left[\Phi^{n-2}(p)+\left(1-\Phi(p)\right)^{n-2}\right]e^{-p^2}dp$$
and as obviously $1-\Phi(p)\leqq1/2$ for $p\geqq0$ it follows that
$$(60)\quad W_n\sim\frac{2}{\sqrt{\pi}}\int_0^\infty\Phi^{n-2}(p)e^{-p^2}dp.$$
Now for $p\gt1$
$$(61)\quad\Phi(p)=1-\frac{e^{-\frac{p^2}{2}}}{\sqrt{2\pi}p\left(1+\frac{\theta p}{p^2}\right)}$$
where $0\lt\theta_p\lt1$ (A. Renyi, [3],) p. 136, exercise 18). With the substitution
$$(62)\quad p=\sqrt{2\log n-\log(2\log n)}+\frac{u-\log\sqrt{2\pi}}{\sqrt{2\log n}}$$
one finally gets after some calculations
$$\quad\quad W_n\sim\frac{4\sqrt{2\pi\log n}}{n^2}.$$
Therefore
$$\quad\quad E_n\sim 2\sqrt{2\pi\log n}$$
which had to be proven.
References
[1] Blaschke, W.: Integralgeometrie 3rd edition Berling: VEB Deutscher Verlag der Wissenschaften 1955, 1 - 130.
[2]--, and K. Reidemeister. Differentialgeometrie II, Berlin: Springer 1923, 60.
[3] Rényi, A.: Wahrscheinlichkeitsrechnung, mit einem Anhang über Informationstheorie. Berlin: VEB Deutscher Verlag der Wissenschaften 1962, 1 - 547
Magyar Tudományos Akadémia Matematikai
Kutató Intézete Reáltanoda u. 13 - 15
Budapest V
and
Humboldt-Universität
Berlin
*(Received November 10th 1962)*
Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 2 (1963) 75-84.
On the Convex Hull of $n$ Randomly Chosen Points I
by
A.Rényi and R. Sulanke
Introduction
Let $P_i (i=1,2,\cdots, n)$ be $n$ points of the plane chosen randomly according to a certain distribution and, let $H_n$ denote the convex hull of these points, which is a convex polygon as is commonly known. The number $X_n$ of sides of $H_n$ is then a random variable, whose behavior as $n\rightarrow\infty$ under various assumptions on the distribution of the points $P_i$ will be investigated in this paper. To this end It is assumed that the points $P_i$ are distributed independently and according to the same distribution. By $E_n=E(X_n)$ we denote the mathematical expected value of $X_n$.
In § 1 we consider the case that the $P_i (i=1, \cdots,\ n)$ are distributed equally in a convex Polygon $K$ with $r$ corners. It will be shown that $E_n=(2r/3)(\log n+C)+T+\omicron(1)$; here $C$ denotes the Euler constant. The value $T=T(k)$ depends on the region $K$. In § 2 we prove the elementary geometric theorem that $T(k)$ will be maximal for polygons that are affinely equivalent to the regular $r$-gons and only for those. In § 3 the asymptotic behavior of $E_n$ will be investigated if the $P_i$ are distributed in a convex region with smooth boundary. It turns out that $E_n$ has $\sqrt[3]{n}$ order of magnitude. In § 4 we finally prove that $E_n$ behaves as $\sqrt{\log n}$ if the points $P_i$ are normally distributed.
§1 . Random points in a convex polygon
Let $K$ be a convex polygon with corners $A_1,\ A_2,\ \dots,\ A_r$ and the corresponding angles $\vartheta_1,\ \vartheta_2,\ \dots,\ \vartheta_r$. Let $a_k$ denote the length of the side $A_kA_{k+1}$ ($k=1,\ \dots,\ r$; $A_{r+1}=A_1$). Let further $F$ denote the area of $K$.
Let $\varepsilon_{ij}=1$, if $i\ne j$ and the edge $P_iP_j$ is part of the boundary of $H_n$, and $\varepsilon_{ij}=0$ otherwise. Then obviously
$$(1) \quad X_n =\sum_{1\leqq i\lt j\leqq n}{\varepsilon_{ij}}$$
The probability
$$(2)\quad W_n=P(\varepsilon_{ij}=1)$$
is the same for pairs $(i,j)$ of numbers with $1\leqq i\lt j\leqq n$ and it holds true that
$$(3)\quad E_n = E(X_n)=\binom{n}{2}W_n$$
To determine the asymptotic behavior of $E_n$ it therefore suffices to calculate the probability $W_n$. Now $W_n$ is the probability that all points $P_h$ ($h=3,\ 4,\ \dots,\ n$) lie to the same side of the line through $P_1$ and $P_2$. If we denote by $F_1\le F/2$ and $F-F_1$ the areas of the parts of $K$ in which $K$ is divided by the line $P_1P_2$, it holds true that
$$(4)\quad W_n=\frac{1}{F^2}\int_K\int_K\left[\left(1-\frac{F_1}{F}\right)^{n-2}+\left(\frac{F_1}{F}\right)^{n-2}\right]dP_1dP_2$$
Obviously, because $F_1/F\le1/2$,
$$\frac{1}{F^2}\int_K\int_K\left(\frac{F_1}{F}\right)dP_1dP_2\leqq\frac{1}{2^{n-2}}$$
and therefore
$$(5)\quad E_n\sim\frac{\binom{n}{2}}{F^2} \int_K\int_K\left(1-\frac{F_1}{F}\right)^{n-2}dP_1dP_2,$$
where $\sim$ means "asymptotically equal", i.e., $A_n\sim B_n$ means that $\lim_{n\rightarrow+\infty}\frac{A_n}{B_n}=1$.
Let now $f_i$ denote the area of the triangle $A_{i-1}A_iA_{i+1}$ ($A_{r+j}=A_j$), and be $f=\min_{1\leqq i\leqq r}{f_i}$. Obviously we can restrict ourselves to such point pairs $P_1$, $P_2$ for which the line $P_1P_2$ either hits two neighboring sides or two sides that are separated by another side of $K$. This is so because for all other lines $1-F_1/F\leqq1-f/F$. Therefore we can neglect the right side of $(5)$ and it holds true that
$$(6)\quad E_n\sim\frac{\binom{n}{2}}{F^2}\left(\sum_{i=1}^r\left(i+J_i\right)\right),$$
where
$$(7)\quad I_i =\int_{C_i}\left(1-\frac{F_1}{F}\right)^{n-2}dP_1dP_2$$
and
$$(8)\quad I_i =\int_{D_i}\left(1-\frac{F_1}{F}\right)^{n-2}dP_1dP_2$$
Here $C_i$ denotes the set of point pairs $P_1$, $P_2$ for which the line $P_1P_2$ hits the sides $A_{i-1}A_i$ and $A_iA_{i+1}$ of $K$, and $D_i$ the set of point pairs for which the line $P_1P_2$ hits the sides $A_{i-1}A_i$ and $A_{i+1}A_{i+2}$ of $K$.
We first investigate the integral $I_i$. Let $G_{ab}$ denote the set of point pairs $P_1$, $P_2$ for which the $|A_iQ_1|\lt a$ and $|A_iQ_2|\lt b$ holds; here $Q_1$ denotes the intersection point of line $P_1P_2$ with side $A_{i-1}A_i$ and $Q_2$ its intersection point with side $A_iA_{i+1}$, further $|AB\ |$ denotes the length of the segment $AB$.
Via an elementary calculation it turns out that
$$(9)\quad\int_{G_{ab}}dP_1dP_2 =\frac{a^2b^2\sin^2\vartheta_i}{12}$$
The area of the triangle $Q_1A_iQ_2$ that is cut off by the line $P_1P_2$ equals $1/2\ a\,b\sin\vartheta_i$ . Therefore we have
$$(10)\quad I_i=\int_0^{a_{i-1}}\int_0^{a_i}\left(1-\frac{a\,b\sin\vartheta_i}{2F}\right)^{n-2}\sin^2\vartheta_i\frac{a\,b}{3}\,da\, db,$$
where $a_i$ denotes the length of side $A_iA_{i+1}$.
Via the transformation
$$(11)\quad X= a\sqrt{\frac{\sin\vartheta_i}{2\,F}},\quad Y= b\sqrt{\frac{\sin\vartheta_i}{2\,F}}$$
we get
$$(12)\quad I_i =\frac{4\,F^2}{3}\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-2}XY\,dX\,dY,$$
where
$$\quad X_i=a_{i-1}\,\sqrt{\frac{\sin\vartheta_i}{2F}},\quad Y_i=a_i\,\sqrt{\frac{\sin\vartheta_i}{2F}},$$
therefore
$$(13)\quad\varrho_i = X_iY_i=\frac{a_{i-1}a_i\sin\vartheta_i}{2\,F}=\frac{f_i}{F}\lt 1$$
holds true. Now we have
$$\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-2}XY\,dX\,dY=\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-2}dX\,dY-\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-1}XY\,dX\,dY$$
Further it is true that
$$\int_0^{X_i}\int_0^{Y_i}\left(1-XY\right)^{n-1}XY\,dX\,dY=\int_0^{X_i}\frac{1-\left(1-XY_i\right)^n}{n}dX=$$
$$\quad =\frac{1+\frac{1}{2}+\cdots+\frac{1}{n}-\sum_{k=1}^n{\frac{\left(1-\varrho_i\right)^k}{k}}}{n}$$
thus we get
$$(14)\quad I_i=\frac{4\,F^2}{3}\left\lbrace\frac{\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}}{n(n-1)}-\frac{\sum_{k=1}^{n-1}\frac{(1-\varrho_i)^k}{k}}{n(n-1)}+\frac{(1-\varrho_i)^n}{n^2}\right\rbrace$$
If we set
$$(15)\quad S_i=\sum_{k=1}^\infty\frac{(1-\varrho_i)^k}{k}=\log\frac{1}{\varrho_i},$$
that finally results in
$$(16)\quad E_n=\frac{2}{3}\left(C-1+\log n\right)r-\frac{2}{3}\sum_{i=1}^rS_i+\omicron(1)+\frac{\binom{n}{2}}{F^2}\sum_{i=1}^rJ_i,$$
where $C$ is the Euler constant.
Now we calculate the integral $J_i$ .We extend the sides $A_{i-1}A_i$ and $A_{i+2}A_{i+2}$ to their intersection point $A_i^*$; the case that these sides are parallel can be treated similarly. Let again $Q_1$ be the intersection point of lines $P_1P_2$ with the side $A_{i-1}A_i$ and $Q_2$ be the intersection point with the side $A_{i+1}A_{i+2}$ and let $a' = |A_iA_i^*|$, $b'=|A_{i+1}A_i^*|$, $a=|A_iQ_1|$, $b=|A_{i+1}Q_2|$; $G_{ab}$ be defined as above. We obtain from $(9)$
$$(17)\quad\int_{G_{ab}}dP_1\,dP_2=\frac{\sin^2\gamma_i}{12}\left(a^2+2aa'\right)\left(b^2+2bb'\right)$$
where $\gamma_i$ denotes the angle at $A_i^*$. Consequently
$$(18)\quad J_i=\int_{D_i}\left(1-\frac{(ab+a'b+ab')\sin\gamma_i}{2F}\right)^{n-2}\frac{\sin^2\gamma_i}{3}(a+a')(b+b')da\,db$$
and that integral is asymptotically equal to
$$(19)\quad J_i\sim \int_{D_i}\left(1-\frac{(a'b+ab')\sin\gamma_i}{2F}\right)^{n-2}\frac{\sin^2\gamma_i}{3}a'b'\,da\,db$$
If we carry out the transformation
$$ \quad a=\frac{F}{b'\sin\gamma_i},\quad b=\frac{F}{a'\sin\gamma_i}Y$$
it follows that
$$\quad J_i\sim\frac{F^2}{3}\int_0^{a'_{i-1}}\int_0^{a'_{i+1}}\left(1-\frac{X+Y}{2}\right)^{n-2}dX\,dY=$$
$$\quad=\frac{4\,F^2}{3n(n-1)}\left\lbrace1-\left(1-\frac{a'_{i-1}}{2}\right)^n-\left(1-\frac{a'_{i+1}}{2}\right)^n+\left(1-\frac{a'_{i-1}+a'_{i+1}}{2}\right)^n\right\rbrace,$$
where
$$\quad a'_{i-1} = \frac{a_ib'\sin\gamma_i}{F},\quad a'_{i+1} = \frac{a_{i+2}a'\sin\gamma_i}{F}$$
has been set. Consequently this yields
$$\quad E_n=\frac{2r}{3}\left(\log n+C\right)-\frac{2}{3}\sum_{i=1}^rS_i+\omicron(1).$$
Lets summarize what has been proven in the following theorem:
Theorem 1. Let $K$ be a convex polygon with $r$ sides. The mathematical expectation $E_n$ of the number of sides of the convex hull $H_n$ of $n$ in $K$ randomly chosen points is equal to
$$(20)\quad E_n=\frac{2r}{3}\left(\log n+C\right)+\frac{2}{3}\log\frac{\prod_1^rf_i}{F^r}+\omicron(1)$$
Here $F$ denotes the area of $K$ and $f_i$ the area of the triangle that is defined by corners $A_{i-1}A_iA_{i+1}$ of $K$.
If for example $K$ is a triangle, then $f_1=f_2=f_3=F$ and it follows that
$$(21)\quad E_n=2(\log n+C)+\omicron(1).$$
The formula for $E_n$ doesn't depend on the shape of the triangle. That is reasonable because $E_n$ must obviously be invariant under affine transformations. In §2 we will show the constant
$$(22)\quad Z(K)=\frac{\prod_1^rf_i}{F^r}$$
that appears in $(20)$ and depends on the shape of $K$ becomes maximal for regular $r$-gons (and for the polygons that are affinely equivalent to them).
§ 2. An Extremal Value Problem for Convex Polygons
Before we turn to further asymptotic estimates for $E_n$ under different conditions on the distribution of the points $P_i$, we prove the following
Theorem 2. Let $K$ be a convex polygon with $r$ sides. Then we have with notations of the previous §: The function
$$(23)\quad Z(K)=\frac{1}{F^r}\prod_{i=1}^{r}f_i$$
is maximal if and only if $K$ can be affinely transformed to the regular $r$-gon.
Let $\mathfrak{a}_i=\overrightarrow{A_{i-1}A_i}$, where $A_{r+i}=A_i$ shall be set. Then it holds true that
$$(24)\quad f_i=\frac{1}{2}[\mathfrak{a}_i,\mathfrak{a}_{i+1}],\quad F=\frac{1}{2}\sum_{i=1}^{r-2}[\mathfrak{a}_1+\mathfrak{a}_2+\cdots+\mathfrak{a}_i,\mathfrak{a}_{i+1}]$$
where $[\mathfrak{a},\mathfrak{b}]$ denotes the determinant of vectors $\mathfrak{a},\mathfrak{b}$. The function $Z(K)$ is now a function of the $r$ vectors $\mathfrak{a}_i$ ($i=1,\,\dots,\,r$) , which satisfy the closing condition
$$(25)\quad\sum_{i=1}^r\mathfrak{a}_i=0$$
We now imagine the corners $A_i$ of $K$ subjected to sufficiently small displacements, that depend continuously differentiable on a parameter $t$. As the original polyon $K$ that shall correspond to parameter value $t=0$ is a convex $r$-gon, then also the polygons that are generated by sufficiently small displacements will be convex $r$-gons. The function $Z$ when considered as a function of $t$ must have a maximum at $T=0$ if $K$ is a maximal polygon. As a necessary condition for $K$ being maximal we get by elementary calculation:
$$(26)\quad\sum_{i=1}^r\frac{F}{f_i}\left(\left[\mathfrak{\dot a}_i+\mathfrak{a}_{i+1}\right]+\left[\mathfrak{a}_i+\mathfrak{\dot a}_{i+1}\right]\right )\ -$$
$$\quad\ -\ r\sum_{i=1}^{r-2}\left(\left[\mathfrak{\dot a}_1+\cdots+\mathfrak{\dot a}_i,\mathfrak{a}_{i+1}\right]+\left[\mathfrak{a}_1+\cdots+\mathfrak{ a}_i,\mathfrak{\dot a}_{i+1}\right]\right )=0$$
Here
$$\quad \mathfrak{\dot a}_i=\frac{d}{dt}\mathfrak{a}\Bigg|_{i=0}$$
has been set. The $\mathfrak{\dot a}$ are arbitrary vectors that only have to satisfy the closing conditions
$$(27)\quad\sum_{i=1}^r\mathfrak{\dot a}_i=0$$
that follow from $(25)$. If we now one by one set
$$(28)\quad \mathfrak{\dot a}_j=\mathfrak{b},\ \mathfrak{\dot a}_{j+1}=-\mathfrak{b},\ \mathfrak{\dot a}_i=0 \text{ for } i\ne j,\ j+1,$$
where $\mathfrak{b}$ presently still is an arbitrary vector, the closing condition is obviously fulfilled and for $j\,=\,1,\, \ldots,\,r$ we obtain
$$(29)\quad\frac{F}{r}\left\lbrace\frac{[\mathfrak{a}_j,\mathfrak{b}]}{f_{j-1}}-\frac{[\mathfrak{b},\mathfrak{a}_{j+2}]}{f_{j+1}}+\frac{1}{f_j}[\mathfrak{b},\mathfrak{a}_j+\mathfrak{a}_{j+1}]\right\rbrace=[\mathfrak{b},\mathfrak{a}_j+\mathfrak{a}_{j+1}].$$
if we now set specifically $\mathfrak{b}=-\mathfrak{a}_j$, then consequently
$$(30)\quad\frac{F}{r}\left\lbrace4-\frac{[\mathfrak{a}_j,\mathfrak{a}_{j+2}]}{f_{j+1}}\right\rbrace=2f_j$$
and for setting $\mathfrak{b}=-\mathfrak{a}_{j+1}$ we get
$$(31)\quad\frac{F}{r}\left\lbrace4-\frac{[\mathfrak{a}_{j-1},\mathfrak{a}_{j+1}]}{f_{j-1}}\right\rbrace =2f_j$$
Comparing these formulas yields
$$(32)\quad[\mathfrak{a}_j,\mathfrak{a}_{j+2}]=\frac{f_{j+1}}{f_{j-1}}[\mathfrak{a}_{j-1},\mathfrak{a}_{j+1}]$$
We now write $(31)$ in the form
$$\quad 2\left(2-\frac{rf_j}{F}\right)=\frac{[\mathfrak{a}_{j-1},\mathfrak{a}_{j+1}]}{f_{j-1}}$$
and obtain by repeated application of $(32)$
$$\quad\quad 2\left(2-\frac{rf_j}{F}\right)=\frac{f_j}{f_1\cdot f_2}[\mathfrak{a}_1,\mathfrak{a}_3]$$
or
$$(33)\quad f_j=\frac{2}{\frac{r}{F}+\frac{[\mathfrak{a}_1,\mathfrak{a}_3]}{2f_1\cdot f_2}}$$
For $r=3$ our optimization task is trivial. In case $r\geqq 4$ we first get $f_3=f_4=\cdots=f_r$. By a cyclic exchanging of the numbering of the corners of $K$ it immediately follows that
$$(34)\quad f_1=f_2=\cdots=f_r$$
and according to $(32)$ besides that we get
$$(35)\quad [\mathfrak{a}_i,\mathfrak{a}_{i+2}]= [\mathfrak{a}_1,\mathfrak{a}_3]=\mathfrak{b}\quad(i=1,2,\ldots,r)$$
where $b$ is a certain constant.
Remark In case $b=[\mathfrak{a}_i,\mathfrak{a}_{i+2}]=0$ we have $f_j=2F/r$. Therefore $\mathfrak{a}_[i+2]$ is always parallel to $\mathfrak{a}_i$. That is only possible if $r=4$ and $K$ is a parallelogram.
We now return to the general case. Via an affine transformation we can always achieve that $f_i=1/2$, i.e. we have
$$(36)\quad[\mathfrak{a}_i,\mathfrak{a}_{i+1}]=1$$
Then from $(33)$ follows immediately
$$(37)\quad F=\frac{r}{2(2-b)} \text{ and therefore }b\lt2.$$
As the vectors $\mathfrak{a}_{i-2}$ and $\mathfrak{a}_{i-1}$ are linearly independent, the ansatz $\mathfrak{a}_i=\alpha\mathfrak{a}_{i-2}+\beta\mathfrak{a}_{i-1}$ and keeping in mind $(35)$ and $(36)$ leads to the recursion
$$(38)\quad\mathfrak{a}_i=-\mathfrak{a}_{i-2}+b\mathfrak{a}_{i-1}$$
We have consequently shown that the side's vectors $\mathfrak{a}_i$ of a maximal convex $r$-gon must necessarily satisfy a recursion of type $(38)$. The proof will now be carried to an end by showing that in that case an Euclidean metric can be defined in the affine plane that lets polygon $K$ appear to be a regular $r$-gon.
First we remark that always
$$(39)\quad-1\leqq b\le2$$
must be true. Were namely $b\lt -1$ then side $\mathfrak{a}_3$ would penetrate side $\mathfrak{a}_1$, which would contradict the convexity of $K$. The estimate $b\lt2$ for the upper bound has already been proven ($(37)$).
The Euclidean metric is uniquely determined if we fix the skalar products of the vectors $\mathfrak{a}_1$, $\mathfrak{a}_2$, which we consider to be basis vectors. We define these skalar products via
$$(40)\quad\mathfrak{a}_1^2=\mathfrak{a}_2^2=\frac{2}{\sqrt{4-b^2}},\quad\mathfrak{a}_1\mathfrak{a}_2=\frac{b}{4-b^2}$$
Obviously
$$\quad[\mathfrak{a}_1,\mathfrak{a}_2]^2=\begin{vmatrix}\mathfrak{a}_1^2&\mathfrak{a}_1\mathfrak{a}_2\\ \mathfrak{a}_1\mathfrak{a}_2&\mathfrak{a}_2^2\end{vmatrix}=1$$
Therefore the so defined metric is positiv definite, i.e. Euclidean. Via complete induction, utilizing $(38)$, it is easy to prove that for all $j$
$$\quad\mathfrak{a}_j^2=\frac{2}{\sqrt{4-b^2}},\quad \mathfrak{a}_j\mathfrak{a}_{j+1}=\frac{b}{\sqrt{4-b^2}},\quad[\mathfrak{a}_j,\mathfrak{a}_{j+1}]=1$$
must be true. From this it follows that all sides of our $r$-gon $K$ must have equal length and that two consecutive sides intersect under the same angle. Therefore that $r$-go must be regular with respect to that metric.
Thus the uniqueness of the maximal polygon has been proven. The existence is the result of an easy conclusion from the boundedness of $Z(K)$, as well as the continuity of $F$ and $Z$. Therefore theorem 2 is completely proven.
§ 3. Random points in a convex region with smooth boundary
Let $K$ now be a convex region whose boundary has a curvature that is a continuous function of arclength. With the notations of the previous paragraphs we again have
$$E_n=\binom{n}{2}W_n.$$
According to known theorem of integral geometry (cf. Blaschke[1], p17, (86)) the density for point-pairs can be reformulated as follows:
$$(41)\quad dP_1\,dP_2=|t_1-t_2|\,dt_1\,dt_2\,d\varphi\,dp,$$
with p meaning the distance of the line $P_1\,P_2$ from the coordinate origin and, $\varphi$ the angle with a zero-direction (translator's remark: that means "a reference direction" that corresponds to the angle of 0°) and $t_1,$ $t_2$ the parameter values of the arc-length of points $P_1$, $P_2$ on the line $P_1\,P_2$. Let $f$ denote the area of the part of $K$ that is cut off by the line $P_1\,P_2$. Then we have
$$(42)\quad E_n=\frac{\binom{n}{2}}{F^2}\int_0^{2\pi}\left\lbrace\int_0^{p(\varphi)}\left(1-\frac{f}{F}\right)^{n-2}\left(\iint|t_1-t_2|\,dt_1\,dt_2\right)dp\right\rbrace d\varphi$$
By $l(p,\varphi)$ we denote the length of the chord in which the line with coordinates $p$, $\varphi$ hits region $K$. Then it holds true that
$$(43)\quad\iint\left|t_1-t_2\right|\,dt_1\,dt_2=\frac{l^3(p,\varphi)}{3}$$
From this we get
$$(44)\quad E_n=\frac{\binom{n}{2}}{3F^2}\int_0^{2\pi}\left\lbrace\left(1-\frac{f}{F}\right)^{n-3}l^3(p,\varphi)\,dp\right\rbrace\,d\varphi.$$
When calculating the asymptotic value of $E_n$ one can obviously restrict to pairs of values $p$, $f/F\lt \varepsilon$ because the other value-pair only contribute to an error term of magnitude $n^2(1-\varepsilon)^n=\omicron(1)$. We now consider a fixed value of $\varphi$. Let $P(\varphi)$ be the point in which the tangent of $K$ has direction $\varphi$. In the calculation of $E_n$ one may replace $f$ and $l$ with the corresponding values$\bar f$ and $\bar l$ of the osculating circle in point $P(\varphi)$, as turns out from the following estimations. Let $\alpha$ be the central angle related to chord $\bar l$ and $r(\varphi)$ the radius of the osculating circle in point $P(\varphi)$. Then
$$(45)\quad\bar l = 2r(\varphi)\,sin\,\alpha/2\quad\text{and}\quad\bar f=\frac{1}{2}(\alpha-\sin\alpha)r^2(\varphi)$$
furthermore
$$(46)\quad\left|dp\right|=\frac{1}{2}r(\varphi)\sin\alpha/2\left|d\alpha\right|$$
and finally
$$(47)\quad l-\bar l=\omicron(\alpha^2)\quad\text{and}\quad f-\bar f=\omicron(\alpha^4)$$
From which we get
$$(48)\quad E_n=\frac{\binom{n}{2}}{12F^2}\int_0^{2\pi}r^4\int_0^{\alpha(\varphi)}\left(1-\frac{\alpha^3r^2}{12F^2}+\omicron(\alpha^3)\right)^{n-2}\left(\alpha^4+\omicron(\alpha^5)\right)\,d\alpha\,d\varphi$$.
By substituting
$$(49)\quad\frac{\alpha^3r^2}{12F}=\frac{X}{n}$$
we get
$$\quad\quad S(\varphi)=\int_0^{\alpha(\varphi)}\left(1-\frac{\alpha^3r^2}{12F}+\omicron(\alpha^3)\right)^{n-2}\left(\alpha^4+\omicron(\alpha^5)\right)\,da$$
$$(50)$$
$$\quad\quad S(\varphi)=\frac{1}{3}\left(\frac{12F}{r^2n}\right)^{5/3}\left(\int_0^\infty\left(1-\frac{X}{n}\right)^{n-2}x^{2/3}dx+\omicron(1)\right)=\frac{\Gamma\left(\frac{5}{3}\right)}{3}\left(\frac{12F}{r^2n}\right)^{5/3}(1+\omicron(1)).$$
Therefore
$$(51)\quad E_n\sim\Gamma\left(\frac{5}{3}\right)\sqrt[3]{\frac{2n}{3F}}\int^{2\pi}r^{2/3}d\varphi.$$
If now $s$ denotes the arclength on the boundary of $K$ we get, taking $d\varphi/ds=1/r$ into account, the following theorem:
Theorem 3. If $K$ is a convex region whose boundary curve $L$ possesses the continuous curvature $\varkappa=\varkappa(s)$, then it holds true that
$$(52)\quad E_n\sim\Gamma\left(\frac{5}{3}\right)\sqrt[3]{\frac{2}{3}}\left(F^{-1/3}\int_L\varkappa^{1/3}ds\right)\sqrt[3]{n}.$$
The integral $\int_L\varkappa^{1/3}ds$ that appears in $(52)$ is just the equi-affine length of curve $L$. One easily sees that the factor of $\sqrt[3]{n}$ even is affine invariant. From the affine isoperimetric property of ellipses (Blaschke-Reidemeister) it follows that that factor is maximal for ellipses and only for those.
§ 4. Normally random distributed points
In this paragraph we prove the following theorem:
Theorem 4. Let the points $P_i$ ($i=1,\,2,\,\ldots,\,n$) be chosen independently and according to the same normal distribution in the plane, then
$$(53)\quad E_n\sim2\sqrt{2\pi\log n}$$
Proof. As $E_n$ is obviously invariant under affine transformations of the plane, we may assume that the density function of our normal distribution has the form $\frac{1}{2\pi}e^{-\frac{x^2+y^2}{2}}$. As already in the previous paragraph we have
$$\quad E_n=\binom{n}{2}W_n,$$
where $W_n$ is the probability that all points $P_3,\,\ldots,\,P_n$ lie on the same side of the line $P_1\,P_2$. Because of the integralgeometric formula
$$\quad\quad dP_1\,dP_2=dp\,d\varphi\,\left|t_1-t_2\right|\,dt_1\,dt_2$$
and because of the radial symmetry of the normal distribution we get
$$(54)\quad W_n=\frac{1}{2\pi}\iiint\left(g(p)^{n-2}+\left(1-g(p)\right)^{n-2}\right)\left|t_1-t_2\right|e^{-p^2 -\frac{t_1^2+t_2^2}{2}}dt_1\,dt_2\,dp$$
where
$$(55)\quad g(p)=\int_{-\infty}^{+\infty}\int_p^{+\infty}\frac{e^\frac{x^2+y^2}{2}}{2\pi}dx\,dy=1-\Phi(p)$$
has been set and
$$(56)\quad \Phi(p)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^pe^{-\frac{u^2}{2}}du$$
holds.
Via the transformation
$$(57)\quad u=\frac{t_1-t_2}{\sqrt{2}},\quad v=\frac{t_1+t_2}{\sqrt{2}},\quad\frac{\partial(t_1,\,t_2)}{\partial(u,\,v)}=1$$
we get
$$(58)\quad \frac{1}{2\pi}\iint\left|t_1-t_2\right|e^{-\frac{t_1^2+t_2^2}{2}}dt_1\,dt_2 =\frac{2}{\sqrt{\pi}}$$
therefore
$$(59)\quad W_n=\frac{2}{\sqrt{\pi}}\int_0^\infty\left[\Phi^{n-2}(p)+\left(1-\Phi(p)\right)^{n-2}\right]e^{-p^2}dp$$
and as obviously $1-\Phi(p)\leqq1/2$ for $p\geqq0$ it follows that
$$(60)\quad W_n\sim\frac{2}{\sqrt{\pi}}\int_0^\infty\Phi^{n-2}(p)e^{-p^2}dp.$$
Now for $p\gt1$
$$(61)\quad\Phi(p)=1-\frac{e^{-\frac{p^2}{2}}}{\sqrt{2\pi}p\left(1+\frac{\theta p}{p^2}\right)}$$
where $0\lt\theta_p\lt1$ (A. Renyi, [3],) p. 136, exercise 18). With the substitution
$$(62)\quad p=\sqrt{2\log n-\log(2\log n)}+\frac{u-\log\sqrt{2\pi}}{\sqrt{2\log n}}$$
one finally gets after some calculations
$$\quad\quad W_n\sim\frac{4\sqrt{2\pi\log n}}{n^2}.$$
Therefore
$$\quad\quad E_n\sim 2\sqrt{2\pi\log n}$$
which had to be proven.
References
[1] Blaschke, W.: Integralgeometrie 3rd edition Berling: VEB Deutscher Verlag der Wissenschaften 1955, 1 - 130.
[2]--, and K. Reidemeister. Differentialgeometrie II, Berlin: Springer 1923, 60.
[3] Rényi, A.: Wahrscheinlichkeitsrechnung, mit einem Anhang über Informationstheorie. Berlin: VEB Deutscher Verlag der Wissenschaften 1962, 1 - 547
Magyar Tudományos Akadémia Matematikai
Kutató Intézete Reáltanoda u. 13 - 15
Budapest V
and
Humboldt-Universität
Berlin
*(Received November 10th 1962)*
Monday, May 6, 2019
Wednesday, December 26, 2018
Wednesday, October 31, 2018
Tuesday, October 23, 2018
The 9th Congress of Romanian Mathematicians
The 9th Congress of Romanian mathematicians will take place at Galați Romania from June 28 to July 3 2019. More details at the Congress website.
Sunday, October 21, 2018
Notes on Elementary Probability
For the first time, I have self-published with Amazon. I liked how my undergraduate probability notes turned out and I decided to publish them with Amazon. You can get them here. I will still make them available at no cost to my students in electronic form. Here is the cover.
By the way, I here is my author page on Amazon
Monday, October 1, 2018
Wednesday, June 6, 2018
About order statistics.
Suppose that $X_1,\dotsc , X_n$ are independent random variables uniformly distributed in $[0,1]$. Denote by $Y_i=X_{(i)}$ its order statistics.
The random vector $(Y_1,\dotsc, Y_n)$ has distribution
$$
p(y_1,\dotsc, y_n)=\begin{cases}
n!, & 0\leq y_1\leq \cdots \leq y_n\leq 1, \\
0, & {\rm otherwise}.
\end{cases}
$$
The random variable $Y_k$ has distribution
$$
p_k(y_k)=n!\int_{\substack{0\leq y_1\cdots \leq y_k\\ y_k\leq y_{k+1}\leq \cdots \leq y_n\leq 1}}dy_1\cdots dy_{k-1}dy_{k+1}\cdots dy_{n}
$$
$$
= n!\left(\int_{0\leq y_1\leq \cdots \leq y_{k-1} \leq y_k} dy_1\cdots dy_{k-1}\right)\left(\int_{y_k\leq y_{k+1}\leq \cdots \leq y_{n} \leq 1} dy_{k+1}\cdots dy_{n}\right)
$$
$$
= \frac{n!}{(k-1)!(n-k)!} y_k^{k-1}(1-y_k)^{n-k}
$$
Thus $p_k$ is a $B(k,n+1-k)$-distribution. $\newcommand{\bE}{\mathbb{E}}$ We have
$$
\bE[Y_k]=\frac{n!}{(k-1)!(n-k)!}\int_0^1 y^k(1-y)^{n-k} dy=\frac{n!}{(k-1)!(n-k)!}\frac{\Gamma(k+1)\Gamma(n-k+1)}{\Gamma(n+2)}
$$
$$
= \frac{n!}{(k-1)!(n-k)!}\frac{k!(n-k!)}{(n+1)!}=\frac{k}{n+1}.
$$
$$
\bE[Y_k^2]=\frac{n!}{(k-1)!(n-k)!}\int_0^1 y^{k+1}(1-y)^{n-k} dy= \frac{n!}{(k-1)!(n-k)!}\frac{\Gamma(k+2)\Gamma(n-k+1)}{\Gamma(n+3)}
$$
$$
=\frac{n!}{(k-1)!(n-k)!}\frac{(k+1)!(n-k)!}{(n+2)!}=\frac{k(k+1)}{(n+1)(n+2)}.
$$
$\DeclareMathOperator{\Var}{Var}$. Hence
$$
\Var[Y_k]= \frac{k(k+1)}{(n+1)(n+2)}-\left(\frac{k}{n+1}\right)^2=\frac{k}{n+1}\left(\frac{k+1}{n+2}-\frac{k}{n+1}\right)=\frac{k(n+1-k)}{(n+1)^2(n+2)}.
$$
We deduce
$$
\Delta_n=\sum_{k=1}^n \Var[Y_k]=\frac{1}{(n+1)^2(n+2)}\sum_{k=1}^n k(n+1-k).
$$
We have
$$
\sum_{k=1}^nk(n+1-k)= (n+1)\sum_{k=1}^n kn-\sum_{k=1}^n k(k-1)
$$
$$
= \frac{n^2(n+1)}{2}-\sum_{k=1}^nk(k-1).
$$
Now we write
$$
k(k-1)=\frac{1}{3}\Big(\; k^3-(k-1)^3-1\;\Big)
$$
so
$$
\sum_{k=1}^n k(k-1)=\frac{1}{3}\Big(\; n^3 -n\;\Big)=\frac{n(n+1)(n-1)}{3}.
$$
We deduce
$$
\Delta_n= \frac{1}{(n+1)^2(n+2)}\left(\;\frac{n^2(n+1)}{2}-\frac{n(n+1)(n-1)}{3}\;\right)=\frac{n(n+1)(n+2)}{6(n+1)^2(n+2)}=\frac{n}{6(n+1)}.
$$
The random vector $(Y_1,\dotsc, Y_n)$ has distribution
$$
p(y_1,\dotsc, y_n)=\begin{cases}
n!, & 0\leq y_1\leq \cdots \leq y_n\leq 1, \\
0, & {\rm otherwise}.
\end{cases}
$$
The random variable $Y_k$ has distribution
$$
p_k(y_k)=n!\int_{\substack{0\leq y_1\cdots \leq y_k\\ y_k\leq y_{k+1}\leq \cdots \leq y_n\leq 1}}dy_1\cdots dy_{k-1}dy_{k+1}\cdots dy_{n}
$$
$$
= n!\left(\int_{0\leq y_1\leq \cdots \leq y_{k-1} \leq y_k} dy_1\cdots dy_{k-1}\right)\left(\int_{y_k\leq y_{k+1}\leq \cdots \leq y_{n} \leq 1} dy_{k+1}\cdots dy_{n}\right)
$$
$$
= \frac{n!}{(k-1)!(n-k)!} y_k^{k-1}(1-y_k)^{n-k}
$$
Thus $p_k$ is a $B(k,n+1-k)$-distribution. $\newcommand{\bE}{\mathbb{E}}$ We have
$$
\bE[Y_k]=\frac{n!}{(k-1)!(n-k)!}\int_0^1 y^k(1-y)^{n-k} dy=\frac{n!}{(k-1)!(n-k)!}\frac{\Gamma(k+1)\Gamma(n-k+1)}{\Gamma(n+2)}
$$
$$
= \frac{n!}{(k-1)!(n-k)!}\frac{k!(n-k!)}{(n+1)!}=\frac{k}{n+1}.
$$
$$
\bE[Y_k^2]=\frac{n!}{(k-1)!(n-k)!}\int_0^1 y^{k+1}(1-y)^{n-k} dy= \frac{n!}{(k-1)!(n-k)!}\frac{\Gamma(k+2)\Gamma(n-k+1)}{\Gamma(n+3)}
$$
$$
=\frac{n!}{(k-1)!(n-k)!}\frac{(k+1)!(n-k)!}{(n+2)!}=\frac{k(k+1)}{(n+1)(n+2)}.
$$
$\DeclareMathOperator{\Var}{Var}$. Hence
$$
\Var[Y_k]= \frac{k(k+1)}{(n+1)(n+2)}-\left(\frac{k}{n+1}\right)^2=\frac{k}{n+1}\left(\frac{k+1}{n+2}-\frac{k}{n+1}\right)=\frac{k(n+1-k)}{(n+1)^2(n+2)}.
$$
We deduce
$$
\Delta_n=\sum_{k=1}^n \Var[Y_k]=\frac{1}{(n+1)^2(n+2)}\sum_{k=1}^n k(n+1-k).
$$
We have
$$
\sum_{k=1}^nk(n+1-k)= (n+1)\sum_{k=1}^n kn-\sum_{k=1}^n k(k-1)
$$
$$
= \frac{n^2(n+1)}{2}-\sum_{k=1}^nk(k-1).
$$
Now we write
$$
k(k-1)=\frac{1}{3}\Big(\; k^3-(k-1)^3-1\;\Big)
$$
so
$$
\sum_{k=1}^n k(k-1)=\frac{1}{3}\Big(\; n^3 -n\;\Big)=\frac{n(n+1)(n-1)}{3}.
$$
We deduce
$$
\Delta_n= \frac{1}{(n+1)^2(n+2)}\left(\;\frac{n^2(n+1)}{2}-\frac{n(n+1)(n-1)}{3}\;\right)=\frac{n(n+1)(n+2)}{6(n+1)^2(n+2)}=\frac{n}{6(n+1)}.
$$
Tuesday, May 30, 2017
A Puzzle of Clever Connections Nears a Happy End
The puzzle was given a memorable nickname, the “happy ending” problem (or “happy end” problem as originally dubbed by Erdős), for reasons that had nothing to do with math. Instead, it reflected the primary nonmathematical consequence of their discussion of points, lines and shapes: Esther Klein and George Szekeres fell in love and married on June 13, 1937. Yet as the decades passed, mathematicians made virtually no progress in proving the conjecture. (The only other shape whose result is known is a hexagon, which requires at least 17 points, as proved by Szekeres and Lindsay Peters in 2006.) Now, in work recently published in the Journal of the American Mathematical Society, Andrew Suk of the University of Illinois, Chicago, provides nearly decisive evidence that the intuition that guided Erdős and Szekeres more than 80 years ago was correct.
A Puzzle of Clever Connections Nears a Happy End
A Puzzle of Clever Connections Nears a Happy End
Wednesday, May 24, 2017
Tuesday, May 23, 2017
Sunday, May 14, 2017
Saturday, April 15, 2017
Wednesday, March 1, 2017
Monday, December 26, 2016
Thursday, September 1, 2016
Monday, March 28, 2016
Wednesday, January 27, 2016
Friday, January 1, 2016
Tuesday, December 15, 2015
Thursday, December 3, 2015
Wednesday, November 25, 2015
Thursday, November 19, 2015
On a class of random walks
I heard of these random walks from my number-theorist colleague Andrei Jorza who gave me a probabilistic translation of some observations in number theory. What follows is rather a variation on that theme.
There is a whole family of such walks, parametrized by a complex number $\newcommand{\ii}{\boldsymbol{i}}$ $\rho=\cos \theta +\ii \sin\theta$, $\theta\in [0,\pi]$, $\ii=\sqrt{-1}$.
This is discrete time walk on the configuration space $\newcommand{\lan}{\langle}$ $\newcommand{\ran}{\rangle}$
$$ \eC_\rho:= L[\rho] \times C(\rho,-\rho), $$
where $C(\rho,-\rho)$ is the subgroup of $S^1$ generated by $\pm\rho$, i.e.,
$$ C(\rho,-\rho)=\bigl\{\; \pm \rho^k;\;\;k\in\bZ \;\bigr\},$$
and $L[\rho]\subset \bC$ is the additive subgroup of $\bC$ generated by the elements $\rho^n$, $n\in\bZ_{\geq 0}$.
The state of the walk at time $n$ is given by a pair of random variables $(X_n, V_n)$, where one should think of $X_n\in L[\rho]$ as describing the "position'' and $V_n\in G(\rho,-\rho)$ as describing the ``velocity'' at time $n$.
Here is how the random walk takes place. Suppose that at time $n$ we are in the configuration $(X_n, V_n)$. To decide where to go next, toss a fair coin. If a the Head shows up then
$$V_{n+1}=\rho V_n,\;\; X_{n+1}= X_n+V_{n+1}. $$
Otherwise,
$$ V_{n+1}=-\rho V_n,\;\; X_{n+1}= X_n+V_{n+1}. $$
More abstractly, we are given a probability space $(\Omega,\eF,\bP)$ and a sequence of independent, identically distributed variables
$$ S_n:\Omega\to\{-1,1\},\;\;\bP[S_n=\pm 1]=\frac{1}{2},\;\;n\in\bZ_{\geq 0}. $$
If we set
$$
\whS_n:=\prod_{k=1}^nS_k, $$
then we have
$$
V_n= \whS_n \rho^n,\;\;X_n=\sum_{k=1}^n V_n=\sum_{k=1}^n \whS_k\rho_k.
$$
Observing that
$$\bE[\whS_k]=0,\;\;\var[\whS_k]=\prod_{j=1}^k\var[S_j]=1, $$ we deduce
$$\bE[X_n]=0,\;\;\var[S_n]=\bE[X_n\bar{X}_n] $$
$$=\sum_{j,k=1}^n \bE[ \whS_j\whS_k]\rho^{k-j}=\sum_{j=1}^n \bE[ \whS_j^2]+2\sum_{1\leq j<k\leq}^n \bE[ \whS_j\whS_k]\rho^{k-j}=n. $$
Example 1. Suppose that $\theta=\frac{\pi}{2}$ so that $\rho=\ii$. In this case $L[\rho]$ is the lattice $\bZ^2\subset \bC$ and $G(\ii,-\ii)$ is the group of forth order roots of $1$. At time $n=0$, the moving particle is at the origin facing East,. turns right or left (in this case North/South) with equal probability. Once reaches a new intersection, it turns right/left with equal probability. The following MAPLE generated animation a loop describes a 90-step portion of one such walk.
This is somewhat typical of what one observes in general.
Example 2. Suppose that $\theta =\frac{\pi}{3}$. In this case $G(\rho,-\rho)$ is the group of 6th order roots of $1$ and $L[\rho]$ is a lattice in $\bC$. The following MAPLE generated animation depicts a 90 step portion of such a walk and the patterns you observe are typical.
Example 3. Assume that the angle $\theta$ is small and $\frac{\theta}{\pi}$ is not rational, say $\cos \theta=0.95$. The animation below depicts a 90-step stretch of such a walk.
Example 4. For comparison, I have included an animation of a 90-step segment of the usual uniform random walk on $\bZ^2$.
Clearly, I am interested to figure out what is happening and I have a hard time asking a good question. A first question that comes to my mind would be to find statistical invariants that would distinguish the random walk in Example 1 from the random walk in Example 4. I will refer to them as $RW_1$ and $RW_4$
Clear each of these two walks surround many unit squares with vertices in the lattice $\bZ^2$. For $j=1,4$ will denote by $s_j(n)$ the expected number of unit squares surrounded by a walk of $RW_j$ of length $n$.. Which grows faster as $n\to\infty$, $s_1(n)$ or $s_4(n)$?
I will probably update this posting as I get more ideas, but maybe this shot in the dark will initiate a conversation and will suggest other, better questions.
Subscribe to:
Posts (Atom)