2. Preliminaries

In this section we review some existing results. Let F be the uniform distribution on the underlying convex set K. Suppose the underlying set $K\subset\mathbb{R}^d$ is a convex polygon with r ($\ge 3$ ) vertices. Problems related to convex hulls have received much attention from many authors. For $d=2$, according to Cabo and Groeneboom (Reference Cabo and Groeneboom1994), we have, as $n\rightarrow \infty$ ,

(2.1) $$\frac{{|{D_n}|/|K| - {\beta _n}}}{{{\alpha _n}}}\underrightarrow {\text{D}}{\cal N}(0,1),$$

where $\alpha_n=\frac{1}{n}\sqrt{\frac{28}{27}r\log{n}}$ , $\beta_n=\frac{2}{3n}r\log{n}$ , and ‘$$\underrightarrow {\text{D}}$$ ’ is convergence in distribution. For any convex set $K\subset\mathbb{R}^d$ ,

(2.2) \begin{equation} \lim_{n\to\infty}n^{2/(d+1)}{{\rm \mathrm{E}}\,}{(|D_n|)}=c(d)|K|^{2/(d+1)}\int_{\partial{K}}(\kappa(z))^{1/(d+1)}\,{\rm d} z, \label{eqn2} \end{equation}

where $\kappa$ is the generalized Gaussian curvature and c(d) is a constant only depending on d. See Schütt (Reference Schütt1994) for details.

Let K be a convex subset of $\mathbb{R}^2$ . Suppose the boundary of K, i.e. $\partial{K}$ , has curvature bounded away from 0 and $\infty$ , and $\partial{K}\in\mathcal{C}^2(\mathbb{R})$ (the set of all functions with two continuous derivatives with domain $\mathbb{R}$ ). For definitions and more details, see the Appendix A. Let L and $L_n$ be the perimeters of K and $K_n$ respectively. Bräker and Hsing (Reference Bräker and Hsing1998) showed that, as $n\to\infty$ ,

(2.3) \begin{equation} n^{5/6}(|K_n|-{{\rm \mathrm{E}}\,}(|K_n|),L_n-{{\rm \mathrm{E}}\,} (L_n))\xrightarrow{\,{\rm D}\,}\mathcal{N}(\textbf{0},\boldsymbol{\Sigma}), \label{eqn3} \end{equation}

where $\boldsymbol{\Sigma}$ is a constant matrix. Convergence of expectations is given by

$$\mathop {\lim }\limits_{n \to \infty } {n^{2/3}}{\rm{E}}{\mkern 1mu} (L - {L_n}) = {c_1}$$

and

(2.4) \begin{equation} \lim_{n\to\infty} n^{2/3}{{\rm \mathrm{E}}\,}(|D_n|)=c_2, \label{eqn4} \end{equation}

where $c_1$ and $c_2$ are constants.

Let $d\ (\!\ge2)$ and $s\ (\!\le d-1)$ be two nonnegative integers. Let $K\subset\mathbb{R}^d$ be a convex set with $\partial{K}\in\mathcal{C}^2(\mathbb{R}^{d-1})$ and positive Gaussian curvature bounded away from 0 and $\infty$ . Let $\Phi$ be the cumulative distribution function of the standard normal distribution. Then Reitzner (Reference Reitzner2005) proved that there exists a sequence of constants $C_n$ , bounded between two positive constants, depending only on K, and another constant c, such that

(2.5) \begin{equation} \bigg|{{\rm \mathrm{P}}}\bigg(\frac{|K_n|-{{\rm \mathrm{E}}\,}{(|K_n|)}}{\sqrt{C_n n^{-1-2/(d+1)}}\,}\le t\bigg)-\Phi(t)\bigg|\le c\varepsilon(n), \label{eqn5} \end{equation}

where

\begin{equation*}\varepsilon(n)=n^{-1/(2(d+1))}(\!\log{n})^{2+2/(d+1)}.\end{equation*}

Let K be a convex polygon with interior angles $\theta_1,\theta_2,\dots,\theta_r$ . Bräker et al. (Reference Bräker, Hsing and Bingham1998) derived that

(2.6) \begin{equation} \lim_{n\to\infty}{{\rm \mathrm{P}}}(\sqrt{n}H(K,K_n)\le x)=G_1(x), \label{eqn6} \end{equation}

where

\begin{equation*} %\label{G1definition} G_1(x)\,:\!=\prod_{k=1}^r(1-p_k(x)) \end{equation*}

with

(2.7) \begin{equation} p_k(x)=\left\{ \begin{aligned} &\int_0^{\theta_k}h_k(x,\theta)\,{\rm d}\theta+\exp\Big\{\!-\frac{x^2}{2|K|}\tan\theta_k\Big\}, %\ \ \quad 0<\theta_k<\frac{\pi}{2}, \\ &\int_{\theta_k-\pi/2}^{\pi/2}h_k(x,\theta)\,{\rm d}\theta, %\ \ \quad \frac{\pi}{2}\le\theta_k<\pi, \end{aligned}\right. \label{eqn7} \end{equation}

and

\begin{equation*}h_k(x,\theta)=\exp\Big\{\!-\frac{x^2}{2|K|}(\!\tan\theta_k+\tan(\theta_k-\theta))\Big\}\frac{x^2}{2|K|}\tan^2\theta.\end{equation*}

Bräker et al. (Reference Bräker, Hsing and Bingham1998) also derived the limit theory for uniform polytopes, when the underlying set K satisfies a certain smoothness condition. Let K be a bounded convex set $K\subset\mathbb{R}^2$ . Suppose the boundary of K has length L and we parameterize it (positively oriented) as $t\to c(t)$ , with t the arc length between c(0) and c(t). Suppose the curvature $\mathcal{K}(t)=|\ddot{c}(t)|$ is well defined, bounded away from 0 and $\infty$ , and has a bounded derivative. Define the function

\begin{equation*}\lambda(t)=|K|\sqrt{\mathcal{K}(t)}, \quad %\ \ 0\le t<L,\end{equation*}

and let $\lambda_0\,:\!=\max_{t\in[0,L)}\lambda(t)$ . Suppose that there exists some bounded sequence of nonnegative constants $\nu_n$ and positive constant $\mu$ such that, as $n\to\infty$ ,

(2.8) \begin{equation} \frac{(\!\log{n})^{\nu_n}}{|K|}\int_0^L\exp\bigg\{\!-\gamma_n\bigg(\frac{\lambda_0}{\lambda(t)}-1\bigg)\log{n}\bigg\}\,{\rm d} t\xrightarrow{\ \ }\mu\in(0,\infty), \label{eqn8} \end{equation}

where

\begin{equation*}\gamma_n=\frac{1}{3}+\bigg(\frac{2}{3}-\nu_n\bigg)\frac{\log{\log{n}}}{\log{n}}.\end{equation*}

Denote

\begin{equation*}c_n=\frac{3\sqrt{2}}{8}\lambda_0\gamma_n, \quad %\ \ a_n=n^{-2/3}(\!\log{n})^{-1/3},\quad %\ \ \mbox{and} \ b_n=n^{-2/3}(c_n\log{n})^{2/3}.\end{equation*}

Then

(2.9) \begin{equation} G_2(x)\,:\!=\lim_{n\to\infty}{{\rm \mathrm{P}}}\bigg(\frac{H(K,K_n)-b_n}{a_n}\le x\bigg)=\exp\{\!-d_1{\rm e}^{-d_2x}\}, \quad %\ \ x\in\mathbb{R}, \label{eqn9} \end{equation}

for some constants $d_1$ and $d_2$ .

In practice, the statistical properties of different functionals of random polytopes are hard to use. For example, the limiting results in (2.6) are impossible to use. To assess the distributions of these functionals, a feasible idea is to apply the bootstrap method. In a general framework, let $S_n=\{X_i\}_{i=1}^{n}$ be a sequence of i.i.d. random points drawn from the underlying distribution F. Let $\phi_n(S_n;\,F)$ be a real-valued functional of interest. To draw a precise inference for $\phi_n$ , we need to know the exact form of the underlying distribution F. The plug-in principle suggests using some other known approximate distribution to replace the underlying distribution F. Efron (Reference Efron1979) suggested replacing F with the empirical distribution $F_n$ , where

\begin{equation} F_n(\!-\!\infty,x]=\frac{1}{n}\sum_{i=1}^{n} %I \mathbf{1}(X_i\le x),\notag \end{equation}

with 1 the indicator function.

However, this plug-in principle will still need to be examined for consistency for every target functional. Specifically, suppose

\begin{equation} {{\rm \mathrm{P}}}\bigg(\frac{\phi_n(S_n;\,F)-b_n}{a_n}\le x\bigg)\to G(x) \quad %,\ \text{as\ }n\to\infty %, \notag \end{equation}

for any continuity point $x\in\mathbb{R}$ of G. Conditional on $S_n$ , draw a bootstrap sample of points $S_{n,m}^{*}=\{X_{n,i}^{*}\}_{i=1}^{m}$ from $F_n$ . For convenience, the regular bootstrap takes $m=n$ ; however, for generality we do not necessarily assume $m=n$ in the forthcoming sections. We would like to have

\begin{equation} {{\rm \mathrm{P}}}\bigg(\frac{\phi_m(S_{n,m}^{*};\,F_n)-b_m}{a_m}\le x \,|\, S_n\bigg)\xrightarrow{\,{\rm P}\,} G(x),\notag \end{equation}

where ‘$\xrightarrow{\,{\rm P}\,}$ ’ is convergence in probability.

However, the asymptotic failure of the regular bootstrap ($m=n$ ) for extremes is well known (see counterexamples in Bickel and Freedman (Reference Bickel and Freedman1981)). Obviously, this asymptotic failure will still be the case for random polytopes (see Zarepour (Reference Zarepour1999)). When the regular bootstrap fails, some authors suggest applying the m out of n resampling method, i.e. setting the resample size as $m=o(n)$ ($m/n\to 0$ as $n\to\infty$ ). By assuming $m=o(n)$ , Zarepour (Reference Zarepour1999) studied the bootstrapping point processes and proved the bootstrap consistency if the underlying distribution F satisfies the regularly varying condition: $nF({a_n}^{-1}X_1\in\cdot)\xrightarrow{\,{\rm V}\,}\mu(\!\cdot\!)$ , where $\mu$ is a Radon measure and ‘$\xrightarrow{\,{\rm V}\,}$ ’ is vague convergence (Kallenberg (Reference Kallenberg1983)). By the continuous mapping theorem, the conclusion can also be applied to the regular bootstrap for convex hulls when the underlying distribution has regularly varying tails.

In this paper we investigate the consistency of some bootstrapping schemes for convex hulls. In Section 3 we examine the consistency of the regular bootstrap for polygons. In Section 4, a semi-parametric bootstrapping scheme is introduced and with two simple examples (in which the underlying set K is either a circle or a rectangle) we discuss how this approach works. This new semi-parametric bootstrapping scheme is developed in more detail for more general underlying sets in Section 5. The bootstrapping consistency of the Hausdorff distance on the uniform polytopes is proved in this section. Moreover, we also derive results for the symmetric difference and the perimeter difference (see the forthcoming definitions) in Section 6. Since the technique is similar to Section 5, only concise proofs are given for these two examples.

3. The consistency of the regular bootstrap on the Euclidean distance

Suppose $S_n=\{X_i\}_{i=1}^{n}$ is a sequence of i.i.d. random points uniformly drawn from a polygon K with vertices ${c_{\bf{1}}},{c_{\bf{2}}}, \ldots ,{c_r}$ and interior angles $\theta_1,\theta_2,\dots,\theta_r$ . Let $d_{\rm e}$ be the Euclidean metric. Define the distance between a point $\bf{\it{x}}\in\mathbb{R}^2$ and a set $A\subset\mathbb{R}^2$ by $d_{\rm e}(\bf{\it{x}},A)\,:\!=\inf\{d_{\rm e}(\bf{\it{x}},\bf{\it{y}})\,:\,\bf{\it{y}}\in A\}$ , and as usual take $K_n={{\rm conv}}(S_n)$ . Given the vertex $\bf{\it{c}}_{\bf{\it{k}}}$ , Bräker et al. (Reference Bräker, Hsing and Bingham1998) proved that

\begin{equation} \lim_{n\to\infty}{{\rm \mathrm{P}}}(\sqrt{n}d_{\rm e}(\bf{\it{c}}_{\bf{\it{k}}},K_n)\le x)=1-p_k(x),\notag \end{equation}

where $p_k$ is defined in (2.7). See Figure 1 for a graphical description of $d_{\rm e}(\bf{\it{c}}_{\bf{\it{k}}},K_n)$ . Now, conditionally on $S_n$ , the bootstrapping points $S_{n,m}^{*}=\{X_{n,i}^{*}\}_{i=1}^{m}$ are drawn from the empirical distribution $F_n(\!-\!\infty,x]=\frac{1}{n}\sum_{i=1}^{n} %I \mathbf{1}(X_i\le x)$ . Define $K_{n,m}^{*}\,:\!={{\rm conv}}(S_{n,m}^{*})$ . We would like to know whether bootstrapping is asymptotically valid for $d_{\rm e}(\bf{\it{c}}_{\bf{\it{k}}},K_{n,m}^{*})$ . To prove consistency, we will combine the point-process techniques in Zarepour (Reference Zarepour1999) and the results in Bräker et al. (Reference Bräker, Hsing and Bingham1998). Using the previously introduced notation, the following theorem is stated as follows.

Figure 1.

A representation of $d_{\rm e}(\bf{\it{c}}_{\bf{\it{k}}},K_n)$ , where the sample points are drawn uniformly from K, and $K_n$ is the convex hull of the sample.

Theorem 3.1. Under the assumptions above, suppose $m=o(n)$. Then for any integer k, where $0\le k\le r$, we have

\[P(\sqrt{m}{{d}_{e}}({{c}_{k}},K_{n,m}^{*})\le x|{{S}_{n}})\underrightarrow{P}1-{{p}_{k}}(x)\]

as $n,m\to\infty$ , where $p_k$ is defined in (2.7).

Step 1: Construction of the original point process. Here and later, the additions and subtractions between a set and a point are Minkowski sum and difference. In other words, if K is a nonempty subset of $\mathbb{R}^d$ and ${\bf x}\in \mathbb{R}^d$ then

\begin{equation*}K\pm {\bf x}=\{k\pm x\,:\, k\in K\}.\end{equation*}

Let $\lambda$ be Lebesgue measure. For any measurable subset $A\subset \mathbb{R}^2$ , we have

\begin{align} n{{\rm \mathrm{P}}}(\sqrt{n}(X_1-\bf{\it{c}}_{\bf{\it{k}}})\in A)&=n{{\rm \mathrm{P}}}\bigg(X_1\in\bigg(\frac{A}{\sqrt{n}}+\bf{\it{c}}_{\bf{\it{k}}}\bigg)\bigg)\notag\\ &=\frac{n}{|K|}\lambda\bigg(\frac{A}{\sqrt{n}}\cap (K-\bf{\it{c}}_{\bf{\it{k}}})\bigg)\notag\\ &=\frac{1}{|K|}\lambda(A\cap\sqrt{n}(K-\bf{\it{c}}_{\bf{\it{k}}}))\notag\\ &\xrightarrow{\ }\frac{1}{|K|}\lambda(A) %,\text{\ \ \ \ \ as } \quad \text{as}\ n\to\infty.\notag \end{align}

This is due to the fact that $\sqrt{n}(K-\bf{\it{c}}_{\bf{\it{k}}})\uparrow\mathbb{R}^2$ . Therefore, according to Resnick (Reference Resnick1987) we have

\begin{equation} nP(\sqrt{n}(X_1-\bf{\it{c}}_{\bf{\it{k}}})\in\cdot)\xrightarrow{\,{\rm V}\,}\frac{1}{|K|}\lambda(\!\cdot\!).\notag \end{equation}

Define the point process $\xi_{n,k}=\sum_{i=1}^{n}\delta_{\sqrt{n}(X_i-\bf{\it{c}}_{\bf{\it{k}}})}$ . Here, $\xi_{n,k}$ can be regarded as a random element in $M_{p}(\text{Cone} \bf{\it{c}}_{\bf{\it{k}}})$ (the collection of all nonnegative point measures on the cone $\bf{\it{c}}_{\bf{\it{k}}}$ ; see Resnick (Reference Resnick1987)) endowed with vague topology. The Laplace functional of $\xi_{n,k}$ will be

\begin{align} \Phi_{\xi_{n,k}}(\kern2ptf)&=\bigg(\int_{\mathbb{R}^2} \exp\{\!-f(\sqrt{n}(\bf{\it{x}}-\bf{\it{c}}_{\bf{\it{k}}}))\}\frac{1}{|K|}\mu({\rm d}\bf{\it{x}})\bigg)^n\notag %\ \ \ \quad \bigg(\mu=\lambda(\cdot\cap K)\bigg)\\ &=\bigg(1-\frac{\int_{\mathbb{R}^2} (1-{\rm e}^{\:f(\bf{\it{y}})})\tilde{\mu}({\rm d}\bf{\it{y}})}{n}\bigg)^n %\ \ \ \quad (\bf{\it{y}}=\sqrt{n}(\bf{\it{x}}-\bf{\it{c}}_{\bf{\it{k}}}))\notag\\ &\to\exp\bigg\{\!-\int_{\mathbb{R}^2} (1-{\rm e}^{\:f(\bf{\it{y}})})\frac{1}{|K|}\lambda({\rm d}\bf{\it{y}})\bigg\},\notag \end{align}

where

\begin{equation*}\tilde{\mu}(A)=\frac{n}{|K|}\lambda\bigg(\bigg(\frac{A}{\sqrt{n}}+\bf{\it{c}}_{\bf{\it{k}}}\bigg)\cap K\bigg)=\frac{1}{|K|}\lambda(A\cap\sqrt{n}(K-\bf{\it{c}}_{\bf{\it{k}}}))\xrightarrow{\ }\frac{1}{|K|}\lambda(A) \quad (n\rightarrow \infty)\end{equation*}

for any Borel set $A\subset\mathbb{R}^2$ . Hence, given the vertex $\bf{\it{c}}_{\bf{\it{k}}}$ , we have $\xi_{n,k}\xrightarrow{\,{\rm D}\,}\xi$ as $n\to\infty$ , where $\xi$ is a Poisson point process with intensity measure $\frac{1}{|K|}\lambda$ .

Step 2: Construction of the bootstrapping point process. Conditionally on $S_n$ , let $\xi_{n,m,k}^{*}=\sum_{i=1}^{m}\delta_{\sqrt{m}(X_{n,i}^{*}-\bf{\it{c}}_{\bf{\it{k}}})}$ , which is also a random element in $M_{p}(\text{Cone} \bf{\it{c}}_{\bf{\it{k}}})$ . The Laplace functional of $\xi_{n,m,k}^{*}$ is

(3.1) \begin{align} \Phi_{\xi_{n,m,k}^{*}}(\it{f})&=\bigg(\int_{\mathbb{R}^2} {\rm e}^{-f(\sqrt{m}(\bf{\it{x}}-\bf{\it{c}}_{\bf{\it{k}}}))}F_n({\rm d}\bf{\it{x}})\bigg)^{m}\\ &=\bigg(\int_{\mathbb{R}^2} {\rm e}^{-f(\sqrt{m}(\bf{\it{x}}-\bf{\it{c}}_{\bf{\it{k}}}))}\frac{1}{n}\sum_{i=1}^{n}\delta_{X_i}({\rm d}\bf{\it{x}})\bigg)^{m}\\ &=\bigg(\frac{1}{n}\sum_{i=1}^{n}{\rm e}^{\:f(\sqrt{m}(X_i-\bf{\it{c}}_{\bf{\it{k}}}))}\bigg)^m\\ &=\bigg(\int_{\mathbb{R}^2}{\rm e}^{\:f(\bf{\it{y}})}\frac{1}{n}\sum_{i=1}^{n}\delta_{\sqrt{m}(X_i-\bf{\it{c}}_{\bf{\it{k}}})}({\rm d}\bf{\it{y}})\bigg)^m\\ &=\bigg(1-\frac{\int_{\mathbb{R}^2}(1-{\rm e}^{-f(\bf{\it{y}})})\frac{m}{n}\sum_{i=1}^{n}\delta_{\sqrt{m}(X_i-\bf{\it{c}}_{\bf{\it{k}}})}({\rm d}\bf{\it{y}})}{m}\bigg)^{m}. \label{eqn10}\end{align}

If

\begin{equation} \eta_{n,m,k}\,:\!=\frac{m}{n}\sum_{i=1}^{n}\delta_{\sqrt{m}(X_i-\bf{\it{c}}_{\bf{\it{k}}})},\notag \end{equation}

then (3.1) becomes

(3.2) \begin{equation} \Phi_{\xi_{n,m,k}^{*}}(\kern2ptf)=\bigg(1-\frac{\int_{\mathbb{R}^2}(1-{\rm e}^{-f(\bf{\it{y}})})\eta_{n,m,k}({\rm d}\bf{\it{y}})}{m}\bigg)^{m}. %\notag \label{eqn11} \end{equation}

Since $m{{\rm \mathrm{P}}}(\sqrt{m}(X_1-\bf{\it{c}}_{\bf{\it{k}}})\in\cdot)\xrightarrow{\,{\rm V}\,}\frac{1}{|K|}\lambda(\!\cdot\!)$ and $({{\text{e}}^x} - 1)/x \to 1$ as $x\to 0$ , we have

\begin{align} & {{\rm \mathrm{E}}}(\!\exp\{t\eta_{n,m,k}(A)\})\notag\\ &\qquad=({\rm e}^{tm/n}{{\rm \mathrm{P}}}(\sqrt{m}(X_1-\bf{\it{c}}_{\bf{\it{k}}})\in A)+1-{{\rm \mathrm{P}}}(\sqrt{m}(X_1-\bf{\it{c}}_{\bf{\it{k}}})\in A))^n\notag\\ &\qquad=\bigg(\frac{m{{\rm \mathrm{P}}}(\sqrt{m}(X_1-\bf{\it{c}}_{\bf{\it{k}}})\in A)(\frac{n}{tm}({\rm e}^{tm/n}-1))t}{n}+1\bigg)^n\notag\\ &\qquad\to\exp\Big\{\frac{t}{|K|}\lambda(A)\Big\} %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty. \notag \end{align}

Therefore, from Kallenberg (Reference Kallenberg1983), Theorem 4.2, page 32, we have

(3.3) \begin{equation} \eta_{n,m,k}\xrightarrow{\,{\rm P}\,}\frac{1}{|K|}\lambda %,\text{\ \ \ as\ } \quad \text{as}\ n,m\to\infty. \label{eqn12} \end{equation}

See also Zarepour (Reference Zarepour1999). Combining (3.3) with (3.2) implies that, as $n,m\to\infty$ ,

(3.4) \begin{equation} \xi_{n,m,k}^{*}\xrightarrow{\,{\rm D}\,}\xi \quad \text{in probability.} \label{eqn13} \end{equation}

Step 3: The continuous mapping theorem. For any measure $\eta \in M_{p}(\text{Cone} \bf{\it{c}}_{\bf{\it{k}}})$ , suppose $f_k$ maps $\eta$ to the smallest distance between the origin and the convex hull of the points of $\eta$ . It is easy to find that

\begin{equation*}f_k(\xi_{n,m,k}^{*})=\sqrt{m}d_{\rm e}(\bf{\it{c}}_{\bf{\it{k}}},K_{n,m}^{*}).\end{equation*}

Now apply Skorokhod’s representation theorem and the continuous mapping theorem on (3.4) to get

\begin{equation} {{\rm \mathrm{P}}}(\sqrt{m}d_e(\bf{\it{c}}_{\bf{\it{k}}},K_{n,m}^{*})\le x \mid S_n)\xrightarrow{\,{\rm P}\,}{{\rm \mathrm{P}}}(\kern2ptf_k(\xi)\le x) %, \notag \end{equation}

as $n\to\infty$ , noticing that $m/n\rightarrow 0$ . From Bräker et al. (Reference Bräker, Hsing and Bingham1998), we have

\begin{equation*}{{\rm \mathrm{P}}}(\kern2ptf_k(\xi)\le x)=1-p_k(x),\end{equation*}

completing the proof.

This proves that the result in Bräker et al. (Reference Bräker, Hsing and Bingham1998), as stated in Theorem 3.1, is valid for the regular bootstrap when $m/n\rightarrow 0$ .

4. New bootstrapping scheme on uniform samples

Here we introduce the maximum likelihood estimator of the underlying set as follows.

Since $ML(S_n)$ is the maximum likelihood estimator for K, the geometric features of K determine the geometric features of $ML(S_n)$ . For example, if we only know that K is a convex set, then $ML(S_n)={{\rm conv}}(S_n)=K_n$ (see Figure 2).

Figure 2.

K is a convex polygon. The sample size $n=100$ . $K_n$ is the convex hull of the sample points.

Based on the maximum likelihood estimator of the underlying set, we introduce the following semi-parametric bootstrap method when we know F to a certain degree. Let F be the underlying distribution with nonempty convex support. Let $F_A$ be the restriction of F on a set $A\subset\mathbb{R}^d$ , i.e. for any Borel set $B\subset\mathbb{R}^d$ ,

\begin{equation} F_{A}(B)=\frac{F(B\cap A)}{F(A)}.\notag \end{equation}

Then in our semi-parametric bootstrapping scheme, points $S_{n,m}^{*}=\{X_{n,i}^{*}\}_{i=1}^{m}$ are independently drawn from $F_{ML(S_n)}$ when the sample points $S_n$ are given.

In the following two examples we consider two simple cases to explain how our approach works. In the first example we assume that the underlying set is a disk with an unknown radius R centered at the origin; in the second, we consider a rectangle as the underlying set. Additionally, the distribution on both sets is assumed to be uniform.

Example 4.1. Let $d_{\rm e}$ be the Euclidean metric on $\mathbb{R}^2$ . Define the Euclidean norm $\|\bf{\it{x}}\|=d_{\rm e}(\textbf{0},\bf{\it{x}})\ %,\forall \text{for all}\ \bf{\it{x}}\in\mathbb{R}^2$ . Denote $B(\textbf{0},r)\,:\!=\{\bf{\it{x}}\in\mathbb{R}^2\,:\,\|\bf{\it{x}}\|\le r\}$ . Let $S_n=\{X_i\}_{i=1}^{n}$ be the i.i.d. random points uniformly drawn from the disk $C\,:\!=B(\textbf{0},R)$ . Let $C_n\,:\!=B(\textbf{0},R_n)$ where

\begin{equation*}R_n=\max_{1\le i\le n}\|X_i\|,\end{equation*}

i.e. $C_n$ is the smallest disk with its center at the origin and containing all the sample points (see Figure 3). It is easy to checkhat $C_n$ is the maximum likelihood estimator for C, i.e. $ML(S_n)=C_n$ . Since the sample points are drawn independently and uniformly from C, we have

\begin{align} {{\rm \mathrm{P}}}(|R_n-R|>\varepsilon) &={{\rm \mathrm{P}}}(R_n<R-\varepsilon)\notag\\ &=\bigg(\frac{\pi (R-\varepsilon)^2}{\pi R^2}\bigg)^n\to 0 \quad \text{as}\ n\to\infty\notag, \end{align}

Figure 3.

C is a disk centered at the origin.

which implies $R_n\xrightarrow{\,{\rm P}\,}R$ . Indeed,

\begin{equation} {{\rm var}\,}{R_n}=\frac{nR^{2}}{(n+1)(2n+1)^2}=\Theta(n^{-2}).\notag \end{equation}

Therefore,

\begin{equation} \sum_{n=1}^{\infty}{{\rm \mathrm{P}}}(|R_n-R|>\varepsilon)\le\varepsilon^{-2}\sum_{n=1}^{\infty}{{\rm var}\,}{R_n}<\infty,\notag \end{equation}

which implies $R_n$ converges to R completely (i.e. $R_n\xrightarrow{\,{\rm C}\,}R$ , which is stronger than almost sure convergence). See Hsu and Robins (1974) for the definition.

Now we can evaluate the asymptotic validity of a functional using our bootstrapping scheme on this sample. Given $S_n$ , define

\begin{equation*}R_{n,m}^{*}\,:\!=\max_{1\le i\le m}\|X_{n,i}^{*}\|,\end{equation*}

where $X_{n,i}^{*}$ , $1\le i\le m$ , are drawn uniformly from $C_n$ . Notice that as $n\to\infty$ we have

(4.1) \begin{align} {{\rm \mathrm{P}}}(n(R-R_n)>x) &={{\rm \mathrm{P}}}(R_n<R-x/n)\notag\\ &=\bigg(\frac{\pi (R-x/n)^2}{\pi R^2}\bigg)^n\to\exp\{\!-2x/R\}, \label{eqn14}\end{align}

and as $n,m\to\infty$ we have

(4.2) \begin{align} {{\rm \mathrm{P}}}(m(R_n-R^*_{n,m})>x \mid C_n) &={{\rm \mathrm{P}}}(R^*_{n,m}<R_n-x/m \mid C_n)\notag\\ &=\bigg(\frac{\pi (R_n-x/m)^2}{\pi R_n^2}\bigg)^m\xrightarrow{\,{\rm a.s.}\,}\exp\{\!-2x/R\}. \label{eqn15}\end{align}

From (4.1) and (4.2), it can be seen that the bootstrap approximation is valid in this example. Notice that the standard condition of $m=o(n)$ (m out of n bootstrapping) is not required.

Example 4.2. Let $(X_i,Y_i)$ , $1\le i\le n$ , be a sequence of i.i.d. random points uniformly distributed on a rectangle $T=[0,a]\times[0,b]$ , where a and b are two unknown positive constants. Let $T_n\,:\!=[\!\min_{1\le i\le n}X_i,\max_{1\le i\le n}X_i]\times[\!\min_{1\le i\le n}Y_i,\max_{1\le i\le n}Y_i]$ , i.e. the smallest rectangle containing all the sample points, and with all edges parallel to the coordinate axes (see Figure 4). Since $T_n$ is the maximum likelihood estimator for T, we have $ML(S_n)=T_n$ . Here, $\partial{T}$ and $\partial{T_n}$ consist of the four edges of T and $T_n$ , respectively. For any $A,B\subset\mathbb{R}^2$ , let h(A,B) be the shortest horizontal or vertical distance between A and B, i.e.

\begin{equation*}h(A,B)=\min\{x_0,y_0\},\end{equation*}

Figure 4.

T is a rectangle with its edges parallel to the coordinate axes.

where

\begin{align*} x_0&=\inf\{|x_1-x_2|\,:\,(x_1,y)\in A,\ (x_2,y)\in B,\ y\in\mathbb{R}\}, \\ % and y_0&=\inf\{|y_1-y_2|\,:\,(x,y_1)\in A,\ (x,y_2)\in B,\ x\in\mathbb{R}\}. \end{align*}

Therefore, as $n\to\infty$ we have

(4.3) \begin{align} {{\rm \mathrm{P}}}(nh(\partial{T},\partial{T_n})>x) &={{\rm \mathrm{P}}}(h(\partial{T},\partial{T_n})>x/n)\notag\\ &={{\rm \mathrm{P}}}^{n}(h(\partial{T},X_i)>x/n)\to {\rm e}^{-2x(a^{-1}+b^{-1})}. \label{eqn16}\end{align}

Given $S_n$ , let $(X_{n,i}^{*},Y_{n,i}^{*})$ , $1\le i\le m$ , be a sequence of i.i.d. random points uniformly drawn from $T_n$ . Denote

\begin{align*} T_{n,m}^{*} & = [\!\min_{1\le i\le m}X_{n,i}^{*},\max_{1\le i\le m}X_{n,i}^{*}]\times[\!\min_{1\le i\le m}Y_{n,i}^{*},\max_{1\le i\le m}Y_{n,i}^{*}], \\ \Delta_{n,1} & \,:\!=\max_{1\le i\le n}X_i-\min_{1\le i\le n}X_i, \\ % \ \text{and}\ \ \Delta_{n,2} & \,:\!=\max_{1\le i\le n}Y_i-\min_{1\le i\le n}Y_i. \end{align*}

Since $\Delta_{n,1}$ and $\Delta_{n,2}$ are both nondecreasing sequences and $\Delta_{n,1}\xrightarrow{\,{\rm P}\,}a$ , $\Delta_{n,2}\xrightarrow{\,{\rm P}\,}b$ , then $\Delta_{n,1}\xrightarrow{\,{\rm a.s.}\,}a$ , $\Delta_{n,2}\xrightarrow{\,{\rm a.s.}\,}b$ . Therefore, as $n,m\to\infty$ , we have

(4.4) \begin{align} {{\rm \mathrm{P}}}(mh(\partial{T_n},\partial{T_{n,m}^{*}})>x \mid S_n) &={{\rm \mathrm{P}}}^{m}(h(\partial{T_n},X_{n,1}^*)>x/m \mid S_n)\notag\\ &=\Delta_{n,1}^{-m}\Delta_{n,2}^{-m}\bigg(\Delta_{n,1}-\frac{2x}{m}\bigg)^m\bigg(\Delta_{n,2}-\frac{2x}{m}\bigg)^m \notag\\ &\xrightarrow{\,{\rm a.s.}\,}{\rm e}^{-2x(a^{-1}+b^{-1})}. \label{eqn17}\end{align}

From (4.3) and (4.4), we can conclude that our bootstrap approximation is valid for the functional h in this example. Again, the condition $m=o(n)$ is not necessary.

In the following sections we prove the consistency results for the Hausdorff distance when applying our semi-parametric bootstrapping scheme on uniform polytopes. In this case, the underlying distribution F is the uniform distribution on an unknown convex set K, which implies that $F_{ML(S_n)}$ is exactly the uniform distribution on $ML(S_n)=K_n={{\rm conv}}(S_n)$ , and the bootstrapping points $S_{n,m}^{*}=\{X_{n,i}^{*}\}_{i=1}^{m}$ are drawn from $F_{ML(S_n)}$ .

5. The bootstrap consistency of the Hausdorff distance on uniform polytopes with a semi-parametric bootstrapping scheme

5.1. Notation

Here and later the following notation is used. Suppose F is the uniform distribution on an unknown convex set K. Let $S_{n}\,:\!=\{X_i\}_{i=1}^{n}$ be a sequence of i.i.d. random points drawn from F and $K_n={{\rm conv}}(S_n)$ . Let $S_{n,m}^{*}\,:\!=\{X_{n,i}^{*}\}_{i=1}^{m}$ be a sequence of i.i.d. random points drawn from $F_{K_n}$ . Let $S_m'\,:\!=\{X_{i}'\}_{i=1}^{m}$ be another sequence of i.i.d. random points drawn from F and independent from $S_n$ . For any set A, we denote $A^n=\underbrace{A\times\cdots\times A}_{n\ \text{times}}$ . For simplicity, we also use the following notation:

\begin{align} K_{m}' & ={{\rm conv}}(S'_m),\notag\\ K_{n,m}^{*} & ={{\rm conv}}(S_{n,m}^{*}).\notag \end{align}

The following convergences are equivalent:

(5.1) \begin{align} % &(1)\ \begin{split} m(1-F(K_n)) & \xrightarrow{\,{\rm P}\,}0 \quad %,\text{\ as\ } \text{as}\ n,m\to\infty, \\ %;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\notag\\ % &(2)\ m\log{(F(K_n))} & \xrightarrow{\,{\rm P}\,}0 \quad %,\text{\ as\ } \text{as}\ n,m\to\infty. \end{split} \label{eqn18} \end{align}

Note that ${{\rm \mathrm{P}}}(m(1-F(K_n))>m(1-\exp\{\!-\varepsilon/m\}))\to0$ if anf only if ${{\rm \mathrm{P}}}(|m\log{(F(K_n))}|>\varepsilon)\to 0$ , where $\varepsilon>0$ and $m(1-\exp{(\!-\varepsilon/m)})\to\varepsilon$ as $m\to\infty$ .

5.2. The problem

For any functional $\phi$ , suppose we have

(5.2) \begin{equation} \frac{\phi(S_n;\,F)-\beta_n}{\alpha_n}\xrightarrow{\,{\rm D}\,}Z, \label{eqn19} \end{equation}

where $\alpha_n$ and $\beta_n$ are real numbers and Z is a random variable. Since F is the uniform distribution on K, $F_{K_n}$ is the uniform distribution on $K_n$ . Then we will investigate the following two types of convergence:

\begin{align*} \text{Type\ I:} & \quad {\rm \mathrm{P}}\bigg(\frac{\phi(S^{*}_{n,m};\,F)-\beta_m}{\alpha_m}\le x \,|\, S_n\bigg) \xrightarrow{\,{\rm D}\,}{{\rm \mathrm{P}}}(Z\le x) \quad \text{as}\ n,m\to\infty. \\ \text{Type\ II:} & \quad {\rm \mathrm{P}}\bigg(\frac{\phi(S^{*}_{n,m};\,F_{K_n})-\beta_m}{\alpha_m}\le x \,|\, S_n\bigg) \xrightarrow{\,{\rm D}\,}{{\rm \mathrm{P}}}(Z\le x) \quad \text{as}\ n,m\to\infty. \end{align*}

Type I convergence is used for derivation of type II convergence and also for theoretical interest. Of course, type II convergence establishes that the suggested bootstrap scheme works for the given functional $\phi$ .

According to (2.6) and (2.9), the convergence in (5.2) holds if we let

\begin{equation*}\phi(S_n;\,F)=H(K,K_n).\end{equation*}

In this case, in the next section we will establish both type I convergence where

\begin{equation*}\phi(S^{*}_{n,m};\,F)=H(K,K_{n,m}^{*}),\end{equation*}

and type II convergence where

\begin{equation*}\phi(S_{n,m}^{*};\,F_{K_n})=H(K_n,K_{n,m}^{*}).\end{equation*}

5.3. Uniform distribution on convex polygons

Suppose F is the uniform distribution on $K\subset\mathbb{R}^2$ , where K is a convex polygon with r vertices $\bf{\it{c}}_{\textbf{1}},\bf{\it{c}}_{\textbf{2}},\dots,\bf{\it{c}}_{\bf{\it{r}}}$ and interior angles $\theta_1,\theta_2,\dots,\theta_r$ . From (2.6), we have

\begin{equation} \sqrt{n}H(K,K_n)\xrightarrow{\,{\rm D}\,}Z_1, \quad %\ \ \text{as}\ n\to\infty,\notag \end{equation}

where $Z_1$ has the distribution function $G_1$ as in (2.6). Based on this result, we get the following theorem.

Theorem 5.1. Let $m\log{n}/n\rightarrow 0$ as $n\to\infty$ . Then, as $n,m\to\infty$ ,

\begin{equation*}{{\rm \mathrm{P}}}(\sqrt{m}H(K,K_{n,m}^{*})\le x \mid S_n)\xrightarrow{\,{\rm P}\,}G_1(x).\end{equation*}

Proof. Define the event

${E_{n,m}} \buildrel \Delta \over = \{ {S_{m'}} \subset {K_n}\} $

First, we show that, as $n,m\to\infty$ ,

(5.3) \begin{equation} {{\rm \mathrm{P}}}(E_{n,m} \mid S_n)\xrightarrow{\,{\rm P}\,} 1. \label{eqn20} \end{equation}

This is equivalent to

\begin{equation} \log{({{\rm \mathrm{P}}}(E_{n,m} \mid S_n))}\xrightarrow{\,{\rm P}\,} 0.\notag \end{equation}

Notice that ${{\rm \mathrm{P}}}(E_{n,m} \mid S_n)=(|K_n|/|K|)^m$ . Then we have

\begin{equation} \log{({{\rm \mathrm{P}}}(E_{n,m} \, S_n))}=m\log{(|K_n|/|K|)}.\notag \end{equation}

Let $|D_n|\,:\!=|K\setminus K_n|=|K|-|K_n|$ . Using the equivalence in (5.1), we only need to show that

\begin{equation} m|D_n|/|K|\xrightarrow{\,{\rm P}\,} 0.\notag \end{equation}

Notice that (2.1) shows that $$(|{D_n}|/|K| - {\beta _n})/{\alpha _n}$$ converges weakly where $\beta_n=\frac{2}{3n}r\log{n}$ and $\alpha_n=\frac{1}{n}\sqrt{\frac{28}{27}r\log{n}}$ , and also notice that as $n,m\to\infty$ , $m\alpha_n\to 0$ and $m\beta_n\to 0$ since $m \log n/n\to 0$ . Then, as $n,m\to\infty$ we have

\begin{align} m|D_n|/|K| &=m\bigg(\alpha_n\frac{|D_n|/|K|-\beta_n}{\alpha_n}+\beta_n\bigg)\notag\\ &=m\alpha_n\bigg(\frac{|D_n|/|K|-\beta_n}{\alpha_n}\bigg)+m\beta_n\xrightarrow{\,{\rm P}\,} 0.\notag \end{align}

Now we develop our proof for Theorem 5.1. Define the function $f_n\,:\,\mathbb{R}^n\to\mathbb{R}$ such that

\begin{equation} f_n(\bf{\it{x}}_{\textbf{1}},\dots,\bf{\it{x}}_{\bf{\it{n}}})=\sqrt{n}H(K,{{\rm conv}}\{\bf{\it{x}}_{\textbf{1}},\dots,\bf{\it{x}}_{\bf{\it{n}}}\}).\notag \end{equation}

From (2.6), we get, as $n\to\infty$ ,

\begin{equation} f_n(X_1,\dots,X_n)\xrightarrow{\,{\rm D}\,}Z_1,\notag \end{equation}

i.e. for any continuity point of $G_1$ , say $x\in\mathbb{R}$ , as $n\to\infty$ ,

(5.4) \begin{equation} {{\rm \mathrm{P}}}(\kern2ptf_n(X_1,\dots,X_n)\le x)\to G_1(x). \label{eqn21} \end{equation}

Let $A_n\,:\!=(\kern2ptf_n^{-1}(\!-\!\infty,x])\cap K^n$ , where $f_{n}^{-1}(A)= \{u\,:\,f_{n}(u)\in A\}$ for any subset A of the range of function $f_{n}$ . Since, given $S_n$ , the random vector $(X_{n,1}^{*},\dots,X_{n,m}^{*})$ is independent of $E_{n,m}$ , we have

(5.5) \begin{align} {{\rm \mathrm{P}}}((X_{n,1}^{*},\dots,X_{n,m}^{*})\in A_{m} \mid S_n) &={{\rm \mathrm{P}}}((X_{n,1}^{*},\dots,X_{n,m}^{*})\in A_m \mid S_n,E_{n,m})\notag\\ &={{\rm \mathrm{P}}}((X_{n,1}^{*},\dots,X_{n,m}^{*})\in A_m\cap K_n^m \mid S_n,E_{n,m})\notag\\ &={{\rm \mathrm{P}}}((X_{1}',\dots,X_{m}')\in A_{m}\cap K_n^m \mid S_n,E_{n,m}). \label{eqn22}\end{align}

The last equation holds because the joint distribution of $(X_{1}',\dots,X_{m}')$ is the same as that of $(X_{n,1}^{*},\dots,X_{n,m}^{*})$ when its distribution is restricted on $K_n$ . Applying the multiplication rule to the probability condition on $S_{n}$ (Lemma B.1), we have

(5.6) \begin{align} {{\rm \mathrm{P}}}((X_{1}',\dots,X_{m}')\in A_{m}\cap K_n^m& \mid S_n,E_{n,m}){{\rm \mathrm{P}}}(E_{n,m} \mid S_n)\notag\\ &={{\rm \mathrm{P}}}(\{(X_{1}',\dots,X_{m}')\in A_{m}\cap K_n^m\}\cap E_{n,m} \mid S_n)\notag\\ &={{\rm \mathrm{P}}}((X_{1}',\dots,X_{m}')\in A_{m}\cap K_n^m \mid S_n). \label{eqn23}\end{align}

From (5.3), we have $P(E_{n,m} \mid S_n)\xrightarrow{\,{\rm P}\,}1$ as $n\to\infty$ . Therefore, (5.6) implies

(5.7) \begin{align} |{{\rm \mathrm{P}}}((X_{1}',\dots,X_{m}')\in A_{m}\cap K_n^m \mid S_n,E_{n,m})&-{{\rm \mathrm{P}}}((X_{1}',\dots,X_{m}')\in A_{m}\cap K_n^m \mid S_n)|\notag\\ &\xrightarrow{\,{\rm P}\,}0 %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty. \label{eqn24}\end{align}

Since $(A_m\cap K_n^m)\subset A_m$ and $A_m\setminus(A_m\cap K_{n}^{m})\subset D_{n}^{m}$ , we have

(5.8) \begin{align} |{{\rm \mathrm{P}}}((X_{1}',\dots,X_{m}')\in A_m\cap K_n^m \mid S_n)&-{{\rm \mathrm{P}}}((X_{1}',\dots,X_{m}')\in A_m \mid S_n)|\notag\\ &\le {{\rm \mathrm{P}}}((X_1',\dots,X_m')\in D_n^m \mid S_n)\notag\\ &=(|D_n|/|K|)^m\notag\\ &\xrightarrow{\,{\rm a.s.}\,}0 %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty. \label{eqn25}\end{align}

(Note that for almost all $\omega\in\Omega$ , $|D_n(\omega)|/|K|<|D_3(\omega)|/|K|<1$ implies $(|D_n(\omega)|/|K|)^m$

$\to 0$ , as $n,m\to\infty$ .) Thus, combining (5.5), (5.7), and (5.8) implies that

\begin{align} |{{\rm \mathrm{P}}}((X_{n,1}^{*},\dots,X_{n,m}^{*})\in A_m \mid S_n)&-{{\rm \mathrm{P}}}((X_{1}',\dots,X_{m}')\in A_m \mid S_n)|\notag\\ &\xrightarrow{\,{\rm P}\,}0 %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty.\notag \end{align}

This is equivalent to

(5.9) \begin{align} |{{\rm \mathrm{P}}}(\kern2ptf_m(X_{n,1}^{*},\dots,X_{n,m}^{*})\le x \mid S_n)&-{{\rm \mathrm{P}}}(\kern2ptf_m(X_{1}',\dots,X_{m}')\le x \mid S_n)|\notag\\ &\xrightarrow{\,{\rm P}\,}0 %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty. \label{eqn26}\end{align}

Since $f_m(X_{1}',\dots,X_{m}')$ is independent of $S_n$ , using (5.4) we have

(5.10) \begin{align} {{\rm \mathrm{P}}}(\kern2ptf_m(X_{1}',\dots,X_{m}')\le x \mid S_n) &={{\rm \mathrm{P}}}(\kern2ptf_m(X_{1}',\dots,X_{m}')\le x)\notag\\ &\to G_1(x) %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty. \label{eqn27}\end{align}

Finally, (5.9) and (5.10) imply that

$${\text{P}}({f_m}(X_{n,1}^*, \ldots ,X_{n,m}^*) \le x\mid {S_n})\underrightarrow {\text{P}}{G_1}(x)\% ,\;\;{\text{as}}\;\quad {\text{as}}\;{\text{n}},{\text{m}} \to \infty .$$

In the following theorem, we extend Theorem 5.1, which is of type I convergence, to type II convergence.

Theorem 5.2. Under the same conditions as Theorem 5.1, we have

\begin{equation*}{{\rm \mathrm{P}}}(\sqrt{m}H(K_n,K_{n,m}^{*})\le x \mid S_n)\xrightarrow{\,{\rm P}\,}G_1(x) %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty.\end{equation*}

Proof. In the proof of Theorem 5.1, given $S_n=\{X_i\}_{i=1}^{n}$ , we reset $A_m=(g_m^{-1}(\!-\!\infty,x])\cap K^m$ , where

\begin{equation*}g_m(\bf{\it{x}}_{\textbf{1}},\dots,\bf{\it{x}}_{\bf{\it{m}}})=\sqrt{m}H(K_n,{{\rm conv}}\{\bf{\it{x}}_{\textbf{1}},\dots,\bf{\it{x}}_{\bf{\it{n}}}\}).\end{equation*}

Let x be a continuity point of $G_1$ . Then follow the steps of the proof of Theorem 5.1 to get

\begin{align} |{{\rm \mathrm{P}}}((X_{n,1}^{*},\dots,X_{n,m}^{*})\in A_m \mid S_n)&-{{\rm \mathrm{P}}}((X_{1}',\dots,X_{m}')\in A_m \mid S_n)|\notag\\ &\xrightarrow{\,{\rm P}\,}0 %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty.\notag \end{align}

This is equivalent to

\begin{align} |{{\rm \mathrm{P}}}(g_m(X_{n,1}^{*},\dots,X_{n,m}^{*})\le x \mid S_n)&-{{\rm \mathrm{P}}}(g_m(X_{1}',\dots,X_{m}')\le x \mid S_n)|\notag\\ &\xrightarrow{\,{\rm P}\,}0 %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty.\notag \end{align}

So,

(5.11) \begin{equation} |{{\rm \mathrm{P}}}(\sqrt{m}H(K_n,K_{n,m}^{*})\le x \mid S_n)-{{\rm \mathrm{P}}}(\sqrt{m}H(K_n,K_{m}')\le x \mid S_n)|\xrightarrow{\,{\rm P}\,}0 %, \label{eqn29} \end{equation}

as $n,m\to\infty$ . From Theorem 5.1, we have

(5.12) \begin{equation} {{\rm \mathrm{P}}}(\sqrt{m}H(K_n,K_{n,m}^{*})\le x \mid S_n)\ge {{\rm \mathrm{P}}}(\sqrt{m}H(K,K_{n,m}^{*})\le x \mid S_n) \label{eqn30} \end{equation}

and

(5.13) \begin{equation} {{\rm \mathrm{P}}}(\sqrt{m}H(K,K_{n,m}^{*})\le x \mid S_n)\xrightarrow{\,{\rm P}\,}G_1(x) %, \label{eqn31} \end{equation}

as $n,m\to\infty$ . Notice that $H(K,K_{n,m}^{*})\ge H(K_n,K_{n,m}^{*})$ . Suppose $G_{1,m}$ is the distribution function of $f_m(X_1',\dots,X_m')$ , where $f_m$ is the same as in the proof of Theorem 5.1. Then $\lim_{m\to\infty}G_{1,m}(x)=G_1(x)$ . Since the Hausdorff distance satisfies the triangle inequality

\begin{equation} H(K_n,K_{m}')\ge H(K,K_{m}')-H(K,K_n),\notag \end{equation}

we have

(5.14) \begin{align} {{\rm \mathrm{P}}}(\sqrt{m}H(K_n,K_{m}')\le x \mid S_n)&\le {{\rm \mathrm{P}}}(\sqrt{m}(H(K,K_{m}')-H(K,K_n))\le x \mid S_n)\notag\\ &={{\rm \mathrm{P}}}(\sqrt{m}H(K,K_{m}')\le \sqrt{m}H(K,K_n)+x \mid S_n)\notag\\ &=G_{1,m}\bigg(\sqrt{\frac{m}{n}}(\sqrt{n}H(K,K_n))+x\bigg)\notag\\ &\xrightarrow{\,{\rm P}\,}G_1(x) %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty, \label{eqn32}\end{align}

where the last convergence follows from (2.6) and applying Skorokhod’s representation theorem. Then use Lemma B.4 with (5.11), (5.12), (5.13), and (5.14) to get

[{\text{P}}(\sqrt m H({K_n},K_{n,m}^*) \le x\mid {S_n})\underrightarrow {\text{P}}{G_1}(x),{\text{ as}}\;{\text{n}},{\text{m}} \to \infty .{\text{ }}\square

5.4. Uniform distribution on convex sets with a smooth boundary

A similar technique can also be applied to the smooth case. Let $K\subset\mathbb{R}^2$ be a convex set with $\partial{K}\subset\mathcal{C}^2(\mathbb{R})$ . Suppose the curvature of $\partial{K}$ is bounded away from 0 and $\infty$ and has a bounded derivative. Suppose our underlying distribution F is the uniform distribution on K. Also suppose F satisfies (2.8). From (2.9), we get

\begin{equation} \frac{H(K,K_n)-b_n}{a_n}\xrightarrow{\,{\rm D}\,}Z_2 %,\text{\ \ as\ } \quad \text{as}\ n\to\infty,\notag \end{equation}

where $Z_2$ has the distribution $G_2$ . Based on this result, we have the following theorem.

Theorem 5.3. Let $m/n^{2/3}\rightarrow 0$ as $n\to\infty$ . Then we have

\begin{equation*}{{\rm \mathrm{P}}}\bigg(\frac{H(K,K_{n,m}^{*})-b_{m}}{a_{m}}\le x \,|\, S_n\bigg)\xrightarrow{\,{\rm P}\,}G_2(x) %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty,\end{equation*}

where $G_2(x)=\exp\{\!-d_1{\rm e}^{-d_2x}\}$ , and $a_m$ , $b_m$ , and $G_2$ are all defined in (2.9).

Proof. The proof follows the same lines as in the case of Theorem 5.1. Define the events $E_{n,m} \buildrel \Delta \over = \{S_m'\subset K_n\}$ . First we need to show that, as $n,m\to\infty$ ,

(5.15) \begin{equation} {{\rm \mathrm{P}}}(E_{n,m} \mid S_n)\xrightarrow{\,{\rm P}\,}1. \label{eqn33} \end{equation}

Suppose $D_n=K\setminus K_n$ . Since ${{\rm \mathrm{P}}}(E_{n,m} \mid S_n)=(|K_n|/|K|)^m$ , when taking $\log$ s of both sides and using the equivalence in (5.1), (5.15) becomes

\begin{equation} m|D_n|\xrightarrow{\,{\rm P}\,} 0.\notag \end{equation}

Notice that

\begin{align} m|D_n| &=m(|K|-|K_n|)\notag\\ &=(mn^{-2/3})(n^{2/3}{{\rm \mathrm{E}}}(|D_n|))-(mn^{-5/6})(n^{5/6}(|K_n|-{{\rm \mathrm{E}}}(|K_n|))),\notag \end{align}

where $mn^{-2/3}\to 0$ and $mn^{-5/6}\to 0$ according to our assumption about m. Finally, using (2.3) and (2.4), we complete the proof for ${{\rm \mathrm{P}}}(E_{n,m} \mid S_n)\xrightarrow{\,{\rm P}\,}1$ .

Now, define the function $f_n\,:\,\mathbb{R}^n\to\mathbb{R}$ such that

\begin{equation*}f_n(\bf{\it{x}}_{\textbf{1}},\dots,\bf{\it{x}}_{\bf{\it{n}}})=\frac{H(K,{{\rm conv}}\{\bf{\it{x}}_{\textbf{1}},\dots,\bf{\it{x}}_{\bf{\it{n}}}\})-b_n}{a_n}.\end{equation*}

We only need to follow the steps in the proof of Theorem 5.1 and use (2.9). Therefore, for any continuity point x of $G_2$ , we get

[$${\text{P}}({f_m}(X_{n,1}^*, \ldots ,X_{n,m}^*) \le x\mid {S_n})\underrightarrow P{G_2}(x){\text{ as}}\;{\text{n}},{\text{m}} \to \infty .$$

Again, in the following theorem we extend Theorem 5.3 (which is of type I convergence) to type II convergence.

Theorem 5.4. Under the same conditions as Theorem 5.3, we have

\begin{equation*}{{\rm \mathrm{P}}}\bigg(\frac{H(K_n,K_{n,m}^{*})-b_{m}}{a_{m}}\le x \, |\, S_n\bigg)\xrightarrow{\,{\rm P}\,}G_2(x) %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty.\end{equation*}

Proof. Here we use the same technique as for Theorem 5.1. Given $S_n=\{X_i\}_{i=1}^{n}$ , we reset $A_m=(g_m^{-1}(\!-\!\infty,x])\cap K^m$ , where

\begin{equation*}g_m(\bf{\it{x}}_{\textbf{1}},\dots,\bf{\it{x}}_{\bf{\it{m}}})=\frac{H(K_n,{{\rm conv}}\{\bf{\it{x}}_{\textbf{1}},\dots,\bf{\it{x}}_{\bf{\it{m}}}\})-b_m}{a_m}.\end{equation*}

Let x be a continuity point of $G_2$ . Then follow the steps in the proof of Theorem 5.1 to get

\begin{align} |{{\rm \mathrm{P}}}((X_{n,1}^{*},\dots,X_{n,m}^{*})\in A_m \mid S_n)&-{{\rm \mathrm{P}}}((X_{1}',\dots,X_{m}')\in A_m \mid S_n)|\notag\\ &\xrightarrow{\,{\rm P}\,}0 %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty.\notag \end{align}

This is equivalent to

\begin{align} |{{\rm \mathrm{P}}}(g_m(X_{n,1}^{*},\dots,X_{n,m}^{*})\le x \mid S_n)&-{{\rm \mathrm{P}}}(g_m(X_{1}',\dots,X_{m}')\le x \mid S_n)|\notag\\ &\xrightarrow{\,{\rm P}\,}0 %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty.\notag \end{align}

Therefore, we have

(5.16) \begin{equation} \bigg|{{\rm \mathrm{P}}}\bigg(\frac{H(K_n,K_{n,m}^{*})-b_m}{a_m}\le x \, | \, S_n\bigg)-{{\rm \mathrm{P}}}\bigg(\frac{H(K_n,K_{m}')-b_m}{a_m}\le x \, | \, S_n\bigg)\bigg|\xrightarrow{\,{\rm P}\,}0 %, \label{eqn34} \end{equation}

as $n,m\to\infty$ . From Theorem 5.3, we have

(5.17) \begin{equation} {{\rm \mathrm{P}}}\bigg(\frac{H(K_n,K_{n,m}^{*})-b_m}{a_m}\le x \, | \, S_n\bigg)\ge {{\rm \mathrm{P}}}\bigg(\frac{H(K,K_{n,m}^{*})-b_m}{a_m}\le x \, | \, S_n\bigg) \label{eqn35} \end{equation}

and

(5.18) \begin{equation} {{\rm \mathrm{P}}}\bigg(\frac{H(K,K_{n,m}^{*})-b_m}{a_m}\le x \, | \, S_n\bigg)\xrightarrow{\,{\rm P}\,}G_2(x) %, \label{eqn36} \end{equation}

as $n,m\to\infty$ . Suppose $G_{2,m}$ is the distribution function of $f_m(X_1',\dots,X_m')$ , where $f_m$ is the same as in the proof of Theorem 5.3. Then $\lim_{m\to\infty}G_{2,m}(x)=G_2(x)$ . Since the Hausdorff distance satisfies the triangle inequality

\begin{equation} H(K_n,K_{m}')\ge H(K,K_{m}')-H(K,K_n),\notag \end{equation}

we have

(5.19) \begin{align} {{\rm \mathrm{P}}}\bigg(\frac{H(K_n,K_{m}')-b_m}{a_m}\le x \, | \, S_n\bigg)&\le {{\rm \mathrm{P}}}\bigg(\frac{H(K,K_{m}')-H(K,K_n)-b_m}{a_m}\le x \, | \, S_n\bigg)\notag\\ &={{\rm \mathrm{P}}}\bigg(\frac{H(K,K_{m}')-b_m}{a_m}\le \frac{H(K,K_n)}{a_m}+x \, | \, S_n\bigg)\notag\\ &=G_{2,m}\bigg(\frac{H(K,K_n)}{a_m}+x\bigg). \label{eqn37}\end{align}

Since $a_n/a_m\to0$ and $b_n/a_m\to0$ , we get

(5.20) \begin{equation} \frac{H(K,K_n)}{a_{m}}=\frac{a_n}{a_{m}}\frac{H(K,K_n)-b_n}{a_n}+\frac{b_n}{a_m}\xrightarrow{\,{\rm D}\,}0 %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty. \label{eqn38} \end{equation}

Therefore, according to (5.20) and Skorokhod’s representation theorem, we have

(5.21) \begin{equation} G_{2,m}\bigg(\frac{H(K,K_n)}{a_m}+x\bigg)\xrightarrow{\,{\rm P}\,}G_2(x) %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty. \label{eqn39} \end{equation}

Finally, use Lemma B.4 and (5.16), (5.17), (5.18), (5.19), and (5.21) to get

$${\text{P}}(\frac{{H({K_n},K_{n,m}^*) - {b_m}}}{{{a_m}}} \le x{\mkern 1mu} |{\mkern 1mu} {S_n})\underrightarrow {\text{P}}{G_2}(x)\% ,{\text{as}}\;{\text{n}},{\text{m}} \to \infty .$$

Remark 5.1. We can also get another bonus convergence result:

\begin{equation*}\frac{H(K_n, K_{m}')-b_{m}}{a_{m}}\xrightarrow{\,{\rm D}\,}Z_2 %,\text{\ \ as\ } \quad \text{as}\ m\to\infty.\end{equation*}

(This result is only a by-product of our proof and has nothing to do with our bootstrapping scheme.) By Lemma B.3 and (2.9), it is sufficient to prove

\begin{equation*}\frac{H(K,K_n)}{a_{m}}\xrightarrow{\,{\rm D}\,}0 %,\text{\ \ as\ } \quad \text{as}\ m\to\infty,\end{equation*}

which is similar to (5.20).

6. Two more examples

In addition to the Hausdorff distance, the same technique can also be applied to other functionals. Two noticeable examples are the symmetric difference and the perimeter difference.

The following example is the symmetric difference on $\mathbb{R}^d$ . Suppose $d\ (\!\ge2)$ is a fixed integer and K is a convex set in $\mathbb{R}^d$ such that $\partial{K}\in\mathcal{C}^2(\mathbb{R}^{d-1})$ with positive Gaussian curvature (see Appendix A for details) bounded away from 0 and $\infty$ . With these assumptions, we can use the results in (2.5) and (2.2).

Example 6.1. Let $\phi_1(A,B)$ be the area of the symmetric difference between A and B, i.e. $\phi_1(A,B)=|(A\setminus B)\cup (B\setminus A)|$ . Since $K_n\subset K$ , we have $\phi_1(K,K_n)=|D_n|$ . From (2.5) we have

(6.1) \begin{equation} C_{n}^{-1/2}n^{\frac{1}{2}+\frac{1}{d+1}}(|D_n|-{{\rm \mathrm{E}}}{(|D_n|)})\xrightarrow{\,{\rm D}\,}\mathcal{N}(0,\sigma^2) %,\text{\ \ \ as\ } \quad \text{as}\ n\to\infty, \label{eqn40} \end{equation}

and (2.2) gives

\begin{equation} \lim_{n\to\infty}n^{\frac{2}{d+1}}{{\rm \mathrm{E}}}(|D_n|)= c,\notag \end{equation}

where $\sigma$ and c are constants. Rewrite (6.1) using $\phi_1$ to get

\begin{equation} \frac{\phi_1(K,K_n)-b_n}{a_n}\xrightarrow{\,{\rm D}\,}\mathcal{N}(0,1) %,\text{\ \ \ as\ } \quad \text{as}\ n\to\infty,\notag \end{equation}

where $a_n=\sigma C_{n}^{1/2} n^{-\frac{1}{2}-\frac{1}{d+1}}$ and $b_n={{\rm \mathrm{E}}}{(|D_n|)}=\Theta(n^{-\frac{2}{d+1}})$ . Let $\Phi$ be the cumulative distribution function for the standard normal distribution. Our goal is to find a proper assumption about m such that the type I convergence holds for $\phi_1$ , i.e., as $n,m\to\infty$ we have

(6.2) \begin{equation} {{\rm \mathrm{P}}}\bigg(\frac{\phi_1(K,K_{n,m}^{*})-b_m}{a_m}\le x \, | \, S_n\bigg)\xrightarrow{\,{\rm P}\,}\Phi(x). \label{eqn41} \end{equation}

As before, define the events $E_{n,m} \buildrel \Delta \over = \{S_m'\subset K_n\}$ for the positive integers m and n. To impose a proper assumption on m, we must ensure that

\begin{equation} {{\rm \mathrm{P}}}(E_{n,m} \mid S_n)={{\rm \mathrm{P}}}^m (|K_n|/|K|)\xrightarrow{\,{\rm P}\,} 1 %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty.\notag \end{equation}

Taking $\log$ s of both sides and using the equivalence in (5.1), we have

\begin{equation} m|D_n|\xrightarrow{\,{\rm P}\,}0 %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty.\notag \end{equation}

Since

\begin{align} m|D_n| &=m\phi_1(K,K_n)\notag\\ &=m\bigg[a_n\frac{\phi_1(K,K_n)-b_n}{a_n}+b_n\bigg]\notag\\ &=m a_n\bigg[\frac{\phi_1(K,K_n)-b_n}{a_n}\bigg]+m b_n,\notag \end{align}

the assumption required for m is

\begin{equation*}m a_n\to 0, %\ \ \quad m b_n\to 0\end{equation*}

as $n,m\to\infty$ . So, the resample size m should satisfy $m=o(n^{\frac{2}{d+1}})$ . We omit the details for getting type I convergence in (6.2) as the proof mimics those for Theorems 5.1 and 5.3.

Furthermore, to prove type II convergence for $\phi_1$ , i.e.

\begin{equation} {{\rm \mathrm{P}}}\bigg(\frac{\phi_1(K_n,K_{n,m}^{*})-b_m}{a_m}\le x \, | \, S_n\bigg)\xrightarrow{\,{\rm D}\,}\Phi(x) %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty,\notag \end{equation}

notice that

\begin{equation*}\phi_1(K,K_{n,m}^{*})\ge \phi_1(K_n,K_{n,m}^{*})\end{equation*}

and

\begin{equation*} \phi_1(K_n,K_{m}')\ge\phi_1(K,K_{m}')-\phi_1(K,K_n), \end{equation*}

which are easy to verify. On the other hand, observe that

\begin{equation*}a_n/a_m\to 0, %\ \ \quad b_n/a_m\to 0\end{equation*}

as $n,m\to\infty$ .

Now we can consider the perimeter difference (defined below) on $\mathbb{R}^2$ . To use the result in (2.3), suppose K satisfies $\partial{K}\in\mathcal{C}^2(\mathbb{R})$ with positive curvature bounded away from 0 and $\infty$ .

Example 6.2. Let $d=2$ and define $\phi_2(A,B)=|\text{perimeter of\ }A-\text{perimeter of\ }B|$ . From (2.3) we have

(6.8) \begin{equation} n^{5/6}(L_n-{{\rm \mathrm{E}}} (L_n))\xrightarrow{\,{\rm D}\,}\mathcal{N}(0,(\sigma')^2) %,\text{\ \ as\ } \quad \text{as}\ n\to\infty %, \label{eqn42} \end{equation}

and

\begin{equation} \lim_{n\to\infty} n^{2/3}{{\rm \mathrm{E}}}(L-L_n)=c',\notag \end{equation}

where $\sigma'$ and c’ are two constants. Rewriting (6.8) in terms of $\phi_2$ , we have

\begin{equation} \frac{\phi_2(K,K_n)-b'_n}{a'_n}\xrightarrow{\,{\rm D}\,}\mathcal{N}(0,1) %,\text{\ \ as\ } \quad \text{as}\ n\to\infty,\notag \end{equation}

where $a'_n=\sigma' n^{-5/6}$ and $b'_n={{\rm \mathrm{E}}}{(L-L_n)}=\Theta(n^{-2/3})$ . To prove type I convergence, i.e.

\begin{equation} {{\rm \mathrm{P}}}\bigg(\frac{\phi_2(K,K_{n,m}^{*})-b'_m}{a'_m}\le x \, | \, S_n\bigg)\xrightarrow{\,{\rm P}\,}\Phi(x) %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty,\notag \end{equation}

we need to show that

\begin{equation} {{\rm \mathrm{P}}}(E_{n,m} \mid S_n)={{\rm \mathrm{P}}}^m (|K_n|/|K|)\xrightarrow{\,{\rm P}\,} 1 %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty.\notag \end{equation}

As in Example 6.1, m should satisfy the condition

\begin{equation} m|D_n|\xrightarrow{\,{\rm P}\,}0 %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty.\notag \end{equation}

Thus, our assumption for m should follow $m=o(n^{2/3)})$ . (Notice that $d=2$ .)

To prove type II convergence, i.e.

\begin{equation} {{\rm \mathrm{P}}}\bigg(\frac{\phi_2(K_n,K_{n,m}^{*})-b'_m}{a'_m}\le x \, | \, S_n\bigg)\xrightarrow{\,{\rm P}\,}\Phi(x) %,\text{\ \ as\ } \quad \text{as}\ n,m\to\infty,\notag \end{equation}

notice that

\begin{equation*}\phi_2(K,K_{n,m}^{*})\ge \phi_2(K_n,K_{n,m}^{*})\end{equation*}

and

\begin{equation*} \phi_2(K_n,K_{m}')\ge\phi_2(K,K_{m}')-\phi_2(K,K_n), \end{equation*}

which are easy to verify using Lemma B.2. Obviously,

\begin{equation*}a'_n/a'_m\to 0, %\ \ \quad b'_n/a'_m\to 0\end{equation*}

as $n,m\to\infty$ .