Powered By Blogger

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)

No comments: