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. Kis 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/2n; 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. Kis 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/2n; 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 circleS_{\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 circleS_{\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)