# On $k$-clusters of high-intensity random geometric graphs††thanks: Supported
by EPSRC grant EP/T028653/1

Mathew D. Penrose Department of Mathematical Sciences, University of Bath,
Bath BA2 7AY, United Kingdom<EMAIL_ADDRESS>Xiaochuan Yang
Department of Mathematics, Brunel University London, Uxbridge, UB8 3PH, United
Kingdom<EMAIL_ADDRESS>
(August 28, 2024)

###### Abstract

Let $k,d$ be positive integers. We determine a sequence of constants that are
asymptotic to the probability that the cluster at the origin in a
$d$-dimensional Poisson Boolean model with balls of fixed radius is of order
$k$, as the intensity becomes large. Using this, we determine the asymptotics
of the mean of the number of components of order $k$, denoted $S_{n,k}$ in a
random geometric graph on $n$ uniformly distributed vertices in a smoothly
bounded compact region of $R^{d}$, with distance parameter $r(n)$ chosen so
that the expected degree grows slowly as $n$ becomes large (the so-called
mildly dense limiting regime). We also show that the variance of $S_{n,k}$ is
asymptotic to its mean, and prove Poisson and normal approximation results for
$S_{n,k}$ in this limiting regime. We provide analogous results for the
corresponding Poisson process (i.e. with a Poisson number of points).

We also give similar results in the so-called mildly sparse limiting regime
where $r(n)$ is chosen so the expected degree decays slowly to zero as $n$
becomes large.
Keywords: Random geometric graph; continuum percolation; Poisson
approximation; Stein’s method; Normal approximation
MSC2020 Classification: 05C80; 60K35

##  1 Overview

###  1.1 Introduction and background

The Poisson blob model (PBM) is perhaps the simplest model of random
clustering in a continuous space. Cluster formation is governed entirely by
spatial proximity of particles, and their locations are governed by complete
spatial randomness with no interactions, i.e. a homogeneous spatial Poisson
process. The random geometric graph (RGG) is obtained by restricting the PBM
to a finite window, or in an alternate version, by specifying the number of
particles in the window.

In the present paper we investigate these models at high intensity, i.e. with
a high density of particles relative to the range at which connections form.
For high densities, one can expect most of the particles to lie in a single
giant cluster, but the spatial randomness means that from time to time smaller
clusters may also be seen. We consider here clusters of fixed order $k$. We
provide precise asymptotics on the frequency of these clusters as the
intensity increases, and moreover describe the fluctuations of the number of
clusters in a window that grows in size simultaneously with the growth of the
intensity; the window needs to be large enough to observe clusters of order
$k$. We also describe the limiting internal spatial distribution of the
$k$-clusters (suitably rescaled) at high intensity, and show it is governed by
an interesting energy functional defined on configurations of $k$ points.

Formally, the RGG based on a random sample ${\cal X}$ of points in
$\mathbb{R}^{d}$ (with $d\in\mathbb{N}$) is the graph $G({\cal X},r)$ with
vertex set ${\cal X}$ and with an edge between each pair of points distant at
most $r$ apart, in the Euclidean metric, for a specified distance parameter
$r>0$. Such graphs are important in a variety of applications (see [15]), such
as wireless communications (see [3]) and topological data analysis (see [5]).

The PBM amounts to the study of the graph $G({\cal H}_{\lambda},1)$ where
${\cal H}_{\lambda}$ is a homogeneous Poisson process of intensity $\lambda$
in $\mathbb{R}^{d}$. The PBM is the simplest model of continuum percolation, a
topic of considerable interest; see e.g. [13], [11], [22]. In the terminology
of e.g. [13], the PBM is also known as the Poisson Boolean model with balls of
fixed radius, or as the Poisson random connection model with connection
function given by the indicator function of a ball centred on the origin.

In this paper we consider, for fixed $k\in\mathbb{N}$, the number of
components of order $k$ (i.e., having $k$ vertices) of the graph $G({\cal
X},r)$, here denoted $K_{k,r}({\cal X})$, where ${\cal X}$ is either a random
sample of $n$ points, denoted ${\cal X}_{n}$, uniformly distributed over a
compact set $A$ in $\mathbb{R}^{d}$ with a smooth boundary or the
corresponding Poisson process, denoted ${\cal P}_{n}$. In particular, we
investigate asymptotic properties of $K_{k,r}({\cal X}_{n})$ and
$K_{k,r}({\cal P}_{n})$ for large $n$ with $r=r(n)$ specified and decaying to
zero according to a certain limiting regime (see (1.1) and (1.2) below). In
the special case $k=1$, $K_{1,r}({\cal X})$ is the number of isolated vertices
in $G({\cal X},r)$.

Some limiting regimes have been considered already. In the thermodynamic
limiting regime with $nr^{d}$ held constant, $K_{k,r}({\cal X}_{n})$ is known
to grow proportionately to $n$, with a strong law of large numbers (LLN) (see
[15, Theorem 3.15]) and there are central limit theorems (CLTs) both for
$K_{k,r}({\cal X}_{n})$ (see [15, Theorem 3.14]) and for $K_{k,r}({\cal
P}_{n})$ (see [15, Theorem 3.11]). There is also a strong LLN for
$K_{k,r}({\cal X}_{n})$ in the sparse regime with $nr^{d}\to 0$, subject to
some further conditions on $r(n)$; see [15, Theorem 3.19]. Within the sparse
regime, when $n(nr^{d})^{(k-1)}\to\infty$ but $n(nr^{d})^{k}\to 0$, a CLT for
$K_{k,r}({\cal X}_{n})$ can be derived from [15, Theorem 3.5] and the fact
that the second condition implies that the number of components of order
larger than $k$ vanishes, in probability. In fact the results in [15] are
stated for the number of components isomorphic to some specified connected
graph $\Gamma$, but results for $K_{k,r}({\cal X}_{n})$ or $K_{k,r}({\cal
P}_{n})$ can then be obtained by summing over all possible $\Gamma$ with $k$
vertices.

In the logarithmic regime we take $n\theta r^{d}=b\log n$ for some constant
$b$, where $\theta$ denotes the volume of the unit radius ball in
$\mathbb{R}^{d}$. Provided $d\geq 2$ and $b$ exceeds the critical value
$b_{c}=(2-2/d){\rm Vol}(A)$ (where ${\rm Vol}$ denotes Lebesgue measure), it
is known that with probability tending to 1 as $n\to\infty$, $G({\cal
X}_{n},r)$ is fully connected so that $K_{k,r}({\cal X}_{n})=0$ (see [15,
Theorem 13.7]).

The main limiting regime for $r=r(n)$ that we consider here is to make the
assumptions

$\displaystyle\lim_{n\to\infty}(nr^{d})$ $\displaystyle=\infty;$ (1.1)
$\displaystyle\limsup_{n\to\infty}((\theta nr^{d})/\log n)$
$\displaystyle<\min((2/d),1){\rm Vol}(A).$ (1.2)

We call this the intermediate or mildly dense regime because the average
vertex degree is of order $\Theta(nr^{d})$ and therefore grows to infinity as
$n$ becomes large, but only slowly in this regime. Our intermediate regime
includes the logarithmic regime for small values of the constant $b$; we
discuss the significance of the upper bound in (1.2) later on.

###  1.2 Summary of results

Regarding the Poisson blob model, the number of components of order $k$ in
$G({\cal H}_{\lambda},1)$ will be infinite. Instead, we consider the
probability $p_{k}(\lambda)$ that an inserted point at the origin $o$ lies in
a component of order $k$ of $G({\cal H}_{\lambda}\cup\\{o\\},1)$. This can be
interpreted, loosely speaking, as the proportion of vertices in $G({\cal
H}_{\lambda},1)$ that lie in components of order $k$.

Our first result, Theorem 2.1, determines the asymptotic behaviour of
$p_{k}(\lambda)$ for large $\lambda$. This result is both of interest in its
own right, and important for understanding the asymptotics for number of
components of order $k$ in RGGs in the mildly dense regime. We shall also
provide a result on the limiting distribution of the (rescaled) points of this
component given that it is of order $k$ (Theorem 2.2).

We now describe our main results on finite RGGs. Let $A\subset\mathbb{R}^{d}$
be compact with smooth boundary, and let $X_{1},X_{2},\ldots$ be independent
identically distributed random $d$-vectors, uniformly distributed over $A$.
For $n\in\mathbb{N}$ set ${\cal X}_{n}:=\\{X_{1},\ldots,X_{n}\\}$, which is a
binomial point process (see e.g. [11]). Also, for $n\in(0,\infty)$ let $Z_{n}$
be a Poisson random variable with mean $n$, independent of
$(X_{1},X_{2},\ldots)$, and set ${\cal P}_{n}:={\cal X}_{Z_{n}}$. Then (see
[11, Proposition 3.5]) ${\cal P}_{n}$ is a Poisson point process in $A$ with
intensity measure $(n/{\rm Vol}(A))dx$ (in this case $n$ does not need to be
an integer).

Our results are concerned with the variables $S_{n,k}:=K_{k,r}({\cal X}_{n})$
and $S^{\prime}_{n,k}:=K_{k,r}({\cal P}_{n}$), with $r=r(n)$ given, satisfying
(1.1) and (1.2) unless stated otherwise. For now we present them as asymptotic
results as $n\to\infty$ with $k$ fixed, but the precise statements of these
results later on come with bounds on the rates of convergence.

As first-order results we shall give the asymptotic behaviour of
$\mathbb{E}[S_{n,k}]$ and $\mathbb{E}[S^{\prime}_{n,k}]$. Setting
$I_{n,k}:=\mathbb{E}[S^{\prime}_{n,k}]$, we show in Theorem 3.3 that

$\displaystyle I_{n,k}\sim cn(nr^{d})^{(1-k)(d-1)}\exp(-(\theta/{\rm
Vol}(A))nr^{d})$ (1.3)

as $n\to\infty$, where $c$ is a constant (depending on $d$, $f_{0}$ and $k$)
that we shall give fairly explicitly; see (3.6). We show in Proposition 3.2
also that $\mathbb{E}[S_{n,k}]\sim I_{n,k}$ as $n\to\infty$.

Turning to second-order results, we shall show in Propositions 4.1 and 4.3
that

$\displaystyle\mathbb{V}\mathrm{ar}[S_{n,k}]\sim\mathbb{V}\mathrm{ar}[S^{\prime}_{n,k}]\sim
I_{n,k}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ {\rm
as}\leavevmode\nobreak\ n\to\infty.$ (1.4)

Note that (1.3), (1.1) and (1.2) together imply that $I_{n,k}\to\infty$ as
$n\to\infty$. It is immediate from the asymptotics already described, and
Chebyshev’s inequality, that we have the weak LLNs
$(S_{n,k}/I_{n,k})\overset{\mathbb{P}}{\longrightarrow}1$ and
$(S^{\prime}_{n,k}/I_{n,k})\overset{\mathbb{P}}{\longrightarrow}1$ as
$n\to\infty$, and hence using (1.3) we have
$S_{n,k}/(cn(nr^{d})^{(1-k)(d-1)}e^{-f_{0}\theta
nr^{d}})\overset{\mathbb{P}}{\longrightarrow}1$ and likewise for
$S^{\prime}_{n,k}$, where $c$ is as before. In Theorem 4.4, under the extra
condition $\limsup((n\theta r^{d})/\log n)<{\rm Vol}(A)/2$, we improve the
weak LLNs to strong LLNs, i.e. we prove almost sure convergence

$\displaystyle S_{n,k}/(cn(nr^{d})^{(1-k)(d-1)}e^{-f_{0}\theta
nr^{d}})\overset{a.s.}{\longrightarrow}1\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ {\rm
as}\leavevmode\nobreak\ n\to\infty,$

and likewise for $S^{\prime}_{n,k}$. We do this by giving concentration of
measure results for $S_{n,k}$ and for $S^{\prime}_{n,k}$.

Turning to CLTs, in Theorem 5.1 we show that as $n\to\infty$,

$\displaystyle I_{n,k}^{-1/2}(S^{\prime}_{n,k}-I_{n,k})\overset{{\cal
D}}{\longrightarrow}N(0,1);\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
I_{n,k}^{-1/2}(S_{n,k}-\mathbb{E}[S_{n,k}])\overset{{\cal
D}}{\longrightarrow}N(0,1).$ (1.5)

We shall give two approaches to proving (1.5); one via approximating $S_{n,k}$
by a Poisson distribution with mean $I_{n,k}$ (of interest in itself), and the
other via more direct normal approximation. Both methods provide bounds on
rates of convergence in various metrics on probability distributions.

Finally, in Section 6 we shall present some new results in the sparse limiting
regime, where instead of (1.1) we assume $nr^{d}\to 0$ and
$n(nr^{d})^{k-1}\to\infty$ as $n\to\infty$. In this case, instead of (1.3) we
have $I_{n,k}\sim cn(nr^{d})^{k-1}$ for appropriate $c$. Again in this regime
we can show that $\mathbb{E}[S_{n,k}]\sim I_{n,k}$, and that (1.4) and (1.5)
still hold, by similar arguments to those we use in the mildly dense regime.

It is natural to ask whether our results on $S_{n,k}$ and $S^{\prime}_{n,k}$
generalize to non-uniform distributions. To answer this, we shall present
these results in greater generality. We shall assume $X_{1},X_{2},\ldots$ are
independent random $d$-vectors having a common probability distribution $\nu$
with density $f$, supported by $A$ (so that $\mathbb{P}[X_{i}\in
dx]=\nu(dx)=f(x)dx$ for $x\in A,i\in\mathbb{N}$). We then define ${\cal
X}_{n}$ and ${\cal P}_{n}$ as already described.

For all of our results on the mildly dense limiting regime, we shall assume
that $f$ is continuous on $A$, and that $f_{0}>0$, where we set

$f_{0}:=\inf_{x\in A}f(x);\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ f_{1}:=\inf_{x\in\partial A}f(x);\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ f_{\rm max}:=\sup_{x\in A}f(x),$

and $\partial A$ denotes the boundary of $A$. By compactness of $A$ and
continuity of $f$, we have $f_{\rm max}<\infty$; moreover $f_{1}\geq f_{0}$.
In the special case where $f$ is constant on $A$, we have $f_{0}=f_{1}=f_{\rm
max}=1/{\rm Vol}(A)$; we call this the uniform case.

In the general (non-uniform) case, instead of (1.2) we assume

$\displaystyle\limsup_{n\to\infty}((\theta nr^{d})/\log
n)<\frac{1}{\max(f_{0},d(f_{0}-f_{1}/2))},$ (1.6)

which reduces to (1.2) in the uniform case. This condition may be understood
as follows. Suppose $\theta nr_{n}^{d}=b\log n$ for some constant $b$. A
‘back-of-the envelope’ calculation suggests that the mean number of components
of order $k$ (which we shall call $k$-components or $k$-clusters for short) in
the interior of $A$ is roughly of the order $n(nr^{d})^{k-1}e^{-f_{0}\theta
nr^{d}}\approx n^{1-bf_{0}}$ (up to logarithmic factors), which tends to
infinity if $b<1/f_{0}$. Similarly the mean number of $k$-clusters within
distance $kr$ of the boundary of $A$ is of order
$nr(nr^{d})^{k-1}e^{-f_{1}\theta nr^{d}/2}\approx n^{1-(1/d)-(bf_{1}/2)}$. If
$b$ is less than the right hand side of (1.6), then $bf_{0}<(1/d)+bf_{1}/2$,
so there are more $k$-clusters in the interior of $A$ than near the boundary,
suggesting we can ignore boundary effects when analysing the asymptotic
behaviour of $S_{n,k}$ and $S^{\prime}_{n,k}$. If $b$ were larger than this,
we would have to take boundary effects into account more carefully, for
example to determine the analogue to (1.3) in the uniform case, and we leave
this as possible future research.

All of the results for $S_{n,k}$ and $S^{\prime}_{n,k}$ described earlier for
the uniform case remain valid in the general (non-uniform) case under
assumptions (1.1) and (1.6), except for the asymptotic (1.3). In general,
$I_{n,k}=\mathbb{E}[S^{\prime}_{n,k}]$ is equal to a multiple integral, given
at (3.3). In the non-uniform case we are not able to describe the limiting
behaviour of $I_{n,k}$ so explicitly, but we do show that $I_{n,k}\to\infty$
and $(nr^{d})^{-1}\log(I_{n,k}/n)\to-\theta f_{0}$ as $n\to\infty$; see Lemma
3.1 and Theorem 3.5.

######  Remark 1.1.

  1. 1.

As alluded to earlier, in the thermodynamic or sparse limiting regime, it is
of interest to further distinguish between different components of order $k$,
according to which of the possible graphs $\Gamma$ they are isomorphic to. In
the mildly dense limiting regime considered here, this is of less interest,
because of the compression phenomenon already noted in [1]; for fixed $k$ and
large $n$, nearly all of the components of order $k$ are likely to be
compressed into balls of diameter less than $r$ (in fact, less than $\delta r$
for any fixed $\delta>0$), and therefore fully connected. In other words,
nearly all of the components of order $k$ are likely to be cliques.

  2. 2.

To prove our Gaussian approximation results, we shall use the local dependence
methods of Chen and Shao [7] to deal with $S^{\prime}_{n,k}$ and those of
Chatterjee [6] to deal with $S_{n,k}$. For the Poisson approximation, we shall
use the coupling bounds from e.g. Lindvall [12] for $S_{n,k}$ and from Penrose
[17] for $S^{\prime}_{n,k}$. All of these approximation bounds are obtained by
a blend of Stein’s method and stochastic analysis of general Poisson or
binomial point process functionals. For a systematic account of the subject,
we refer the reader to [21, 4, 8, 14, 11], and to [2] for some recent
developments about the methodology.

  3. 3.

Our results hold for all $d\geq 2$, and also for $d=1$ with the sole exception
of our result on Poisson approximation for $S_{n,k}$ (Proposition 5.6); we
conjecture that even this result could be proved by other means for $d=1$.
Many of our results seem to be new even for the special case with $k=1$ (i.e.,
the isolated vertex count) and/or $d=1$.

  4. 4.

As well as the number of components of fixed order $k$ in $G({\cal X}_{n},r)$
or $G({\cal P}_{n},r)$, it is of interest to consider the total number of
components (of all orders), in the mildly dense limiting regime. This issue is
beyond the scope of the present paper, but we intend to address it in future
work.

###  1.3 Notation

We use the following notation for asymptotics. Given
$g:(0,\infty)\to\mathbb{R}$, and $h:(0,\infty)\to(0,\infty)$, we write
$g(x)=O(h(x))$ if $\limsup|g(x)|/h(x)<\infty$, and $g(x)=o(h(x))$ if
$\limsup|g(x)|/h(x)=0$, and $g(x)=\Omega(h(x))$ if $\liminf|g(x)|/h(x)>0$, and
$g(x)=\Theta(h(x))$ if both $g(x)=O(h(x))$ and $g(x)=\Omega(h(x))$, and
$g(x)\sim h(x)$ if $g(x)/h(x)$ tends to $1$. Here, the limit is taken either
as $x\to 0$ or $x\to\infty$, to be specified in each appearance.

For $x\in\mathbb{R}^{d}$, $r>0$ we set
$B_{r}(x)=\\{y\in\mathbb{R}^{d}:\|y-x\|\leq r\\}$, where $\|\cdot\|$ is the
Euclidean norm. We denote the origin in $\mathbb{R}^{d}$ by $o$, and write
just $B_{r}$ for $B_{r}(o)$. Also for finite ${\cal X}\subset\mathbb{R}^{d}$
and $r>0$, we define the set $B_{r}({\cal X}):=\cup_{x\in{\cal X}}B_{r}(x)$,
and the function $h_{r}({\cal X})$ to be the indicator of the event that
$G({\cal X},r)$ is connected. Also for $m\in\mathbb{N}$ and ${\bf
x}=(x_{1},\ldots,x_{m})\in(\mathbb{R}^{d})^{m}$ we define $B_{r}({\bf x})$ and
$h_{r}({\bf x})$ similarly, identifying ${\bf x}$ with
$\\{x_{1},\ldots,x_{m}\\}$; that is

$\displaystyle B_{r}({\bf x}):=\cup_{i=1}^{m}B_{r}(x_{i});\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ h_{r}({\bf
x})=\mathbbm{1}\\{G(\\{x_{1},\ldots,x_{m}\\},r)\leavevmode\nobreak\ {\rm
is\leavevmode\nobreak\ connected}\\}.$ (1.7)

Also we define $h^{*}_{r}({\bf x})$ to be the product of $h_{r}({\bf x})$ and
the indicator of the event that $x_{1}$ precedes all of $x_{2},\ldots,x_{m}$
in the lexicographic ordering (that is, $x_{1}$ is the left-most point of
$\\{x_{1},\ldots,x_{m}\\}$).

For $A\subset\mathbb{R}^{d}$, we set $A^{(r)}:=\\{x\in A:B_{r}(x)\subset
A\\}$, and $A^{o}:=\cup_{r>0}A^{(r)}$, the interior of $A$. If ${\cal
X}\subset\mathbb{R}^{d}$, and $a>0$ let $a{\cal X}:=\\{ax:x\in{\cal X}\\}$. If
also ${\cal Y}\subset\mathbb{R}^{d}$ and ${\cal X}$ and ${\cal Y}$ are locally
finite and non-empty, let $\operatorname{dist}({\cal X},{\cal
Y}):=\min_{x\in{\cal X},y\in{\cal Y}}\|y-x\|$.

For $n\in\mathbb{N}$, set $[n]:=\\{1,\ldots,n\\}$. If $\ell,m\in\mathbb{N}$
and ${\bf x}=(x_{1},\ldots,x_{\ell})\in(\mathbb{R}^{d})^{\ell}$, ${\bf
y}=(y_{1},\ldots,y_{m})\in(\mathbb{R}^{d})^{m}$, then we set
$\operatorname{dist}({\bf x},{\bf
y}):=\min_{i\in[\ell],j\in[m]}\|x_{i}-y_{j}\|$.

Given a random vector ${\bf X}$ and an event $\mathscr{E}$ on the same
probability space, let $\mathscr{L}({\bf X})$ denote the probability
distribution (also called the law) of ${\bf X}$, and $\mathscr{L}({\bf
X}|\mathscr{E})$ the conditional probability distribution of ${\bf X}$ given
that event $\mathscr{E}$ occurs.

Given $r>0$, given locally finite ${\cal X}\subset\mathbb{R}^{d}$ and given
$x\in{\cal X}$, let ${\cal C}_{r}(x,{\cal X})$ denote the vertex set of the
component of the graph $G({\cal X},r)$ containing $x$, and $|{\cal
C}_{r}(x,{\cal X})|$ the number of elements of this set.

Given $m\in\mathbb{N}$ and $p\in[0,1]$, we write $\mathrm{Bin}(m,p)$ for a
Binomial random variable with parameters $m,p$,

##  2 High-intensity Boolean model

Given $\lambda>0$, let ${\cal H}_{\lambda}$ be a homogeneous Poisson point
process in $\mathbb{R}^{d}$ of intensity $\lambda$ (viewed as a random set of
points), and let ${\cal H}_{\lambda,0}:={\cal H}_{\lambda}\cup\\{o\\}$. Then
for $r>0$ the graph $G({\cal H}_{\lambda},r)$ is the intersection graph of a
PBM, i.e. a Boolean model of continuum percolation with balls of fixed radius
$r/2$. See [11, 13] for background information on models of this type.

Let ${\cal C}(\lambda):={\cal C}_{1}(o,{\cal H}_{\lambda,0})$. For
$k\in\mathbb{N}$ let $p_{k}(\lambda):=\mathbb{P}[|{\cal C}(\lambda)|=k]$. This
section is concerned with the large-$\lambda$ asymptotics of $p_{k}(\lambda)$
for fixed $k$, and the asymptotic conditional distribution of the point
process ${\cal C}(\lambda)$ given $|{\cal C}(\lambda)|=k$. These are relevant
to the RGG model described in the Section 1, as we shall show later on.

In [1, Theorem 2.2] Alexander proved (among other things) that as
$\lambda\to\infty$ we have

$\displaystyle
p_{k+1}(\lambda)=\Theta\left(\lambda^{-k(d-1)}e^{-\theta\lambda}\right).$
(2.1)

In other words, $\lambda^{k(d-1)}e^{\theta\lambda}p_{k+1}(\lambda)$ remains
bounded away from $0$ and $\infty$ as $\lambda\to\infty$. This suggests that
this quantity might tend to a positive finite limit as $\lambda\to\infty$, but
this is not proved in [1]. Our next result shows that this is indeed the case,
and provides a rate of convergence. To describe the limit, we define for each
${\bf z}=(z_{1},\ldots,z_{k})\in(\mathbb{R}^{d})^{k}$ the set

$\displaystyle D({\bf z}):=\cup_{i=1}^{k}B_{\|z_{i}\|/2}(z_{i}/2),$ (2.2)

that is, the union of balls $B_{1}^{*},\ldots,B_{k}^{*}$, where for each $i$
the ball $B_{i}^{*}$ has opposite poles at $o$ and $z_{i}$ (Figure 1 shows an
example with $d=2$). Define the function $g:(\mathbb{R}^{d})^{k}\to[0,\infty)$
by

$\displaystyle g({\bf z})=\int_{D({\bf z})}\|x\|^{1-d}dx,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ {\bf
z}\in(\mathbb{R}^{d})^{k}.$ (2.3)

When $d=2$, this can be interpreted as the gravitational energy of a flat
object with the shape of $D({\bf z})$ and mass equal to the area of $D({\bf
z})$, and with its mass evenly spread, with respect to a large point mass at
the origin; that is, the energy required to remove the object from the
gravitational field of the point mass. We are not aware of any physical
interpretation of $g(\cdot)$ in other dimensions, but nevertheless refer to
$g({\bf z})$ as the quasi-gravitational energy of the set $D({\bf z})$. Set
$\alpha_{1}:=\alpha_{1}(d):=1$, and for $k\in\mathbb{N}$ define the constant

$\displaystyle\alpha_{k+1}:=\alpha_{k+1}(d):=(1/k!)\int_{(\mathbb{R}^{d})^{k}}\exp(-g({\bf
z}))d{\bf z}.$ (2.4)

######  Theorem 2.1.

Let $k\in\mathbb{N}\cup\\{0\\}$. Then as $\lambda\to\infty$,

$\displaystyle\lambda^{k(d-1)}e^{\theta\lambda}p_{k+1}(\lambda)=\alpha_{k+1}+O(\lambda^{-1}).$
(2.5)

Let $k\in\mathbb{N}$. Another part of [1, Theorem 2.2] says, in effect, that
conditionally on $|{\cal C}(\lambda)|=k+1$, the random variable $\lambda{\rm
Diam}({\cal C}(\lambda))$ is bounded away from zero and infinity in
probability (here ${\rm Diam}$ is Euclidean diameter); in other words, ${\rm
Diam}({\cal C}(\lambda))=\Theta(\lambda^{-1})$ in probability as
$\lambda\to\infty$, given $|{\cal C}(\lambda)|=k$. This phenomenon is known as
compression [1, 13]: the density of points in the cluster ${\cal C}(\lambda)$
is of the order of $\lambda^{d}$, compared to an ambient density of $\lambda$.

We give a stronger result here, namely convergence in distribution of the
point process $\lambda{\cal C}(\lambda)$. To describe the limit, let
$(U_{1},\ldots,U_{k})$ be a random vector in $(\mathbb{R}^{d})^{k}$ with joint
density with respect to $(dk)$-dimensional Lebesgue measure, given by
$(k!\alpha_{k+1})^{-1}\exp(-g(\cdot))$, i.e. with

$\displaystyle\mathbb{P}[(U_{1},\ldots,U_{k})\in d{\bf
z}]=(k!\alpha_{k+1})^{-1}\exp(-g({\bf z}))d{\bf z},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ {\bf z}\in(\mathbb{R}^{d})^{k},$ (2.6)

with the energy function $g$ given at (2.3), and $\alpha_{k+1}$ given at
(2.4). Informally, our result says that the point process $\lambda{\cal
C}(\lambda)\setminus\\{o\\}$ converges in distribution to the point process
$\\{U_{1},\ldots,U_{k}\\}$.

To make this precise while avoiding technicalities on point process
convergence, we list the points of our point processes in increasing
lexicographic order to get random vectors in $(\mathbb{R}^{d})^{k}$
(alternatively we could use distance from the origin for the ordering). Let
$Y_{1,\lambda},\ldots,Y_{k,\lambda}$ be the points of ${\cal
C}(\lambda)\setminus\\{o\\}$ taken in increasing lexicographic order, and let
$V_{1},\ldots,V_{k}$ be the points of $\\{U_{1},\ldots,U_{k}\\}$ taken in
increasing lexicographic order.

######  Theorem 2.2.

The conditional distribution of the random vector $(\lambda
Y_{1,\lambda},\ldots,\lambda Y_{k,\lambda}),$ given $|{\cal C}(\lambda)|=k+1$,
converges weakly, as $\lambda\to\infty$, to the distribution of
$(V_{1},\ldots,V_{k})$.

######  Remark 2.3.

  1. 1.

The result (2.1) (but not (2.5)) also appears in [13, Section 5.3]. The
results in [1, 13] are also presented for components of order $k+1$ in
$G({\cal H}_{\lambda,0},s)$ for general fixed $s>0$ (rather than just for
$s=1$). It is easy to generalize (2.5) to this setting, since by Poisson
scaling (see e.g. [13], or the Mapping Theorem in [11])

$\mathbb{P}[|{\cal C}_{s}(o,{\cal H}_{\lambda,0})|=k]=\mathbb{P}[|{\cal
C}_{1}(o,s^{-1}{\cal H}_{\lambda,0})|=k]=p_{k}(\lambda s^{d}).$

  2. 2.

When $d=1$ we can compute $\alpha_{k+1}$ exactly. In this case we have
$g(z)=\max_{i\in[k]}z_{i}^{+}+\max_{i\in[k]}z_{i}^{-}$, and considering
separately the case where $z_{1},\ldots,z_{k}$ all have the same sign and the
case where they do not, we obtain that

$\displaystyle k!\alpha_{k+1}$
$\displaystyle=2k\int_{0}^{\infty}z^{k-1}e^{-z}dz+k(k-1)\int_{0}^{\infty}du\int_{0}^{\infty}dv(u+v)^{k-2}e^{-(u+v)}$
$\displaystyle=2k!+k(k-1)\int_{0}^{\infty}w^{k-2}e^{-w}wdw$
$\displaystyle=2k!+k!(k-1),$

so $\alpha_{k+1}(1)=k+1$.

  3. 3.

We can also compute $\alpha_{2}(d)$ more explicitly for general $d$. Indeed,
when $k=1$ it can be seen directly from (2.8) below that
$g(z)=\lim_{r\downarrow 0}g_{r}(z)=\theta_{d-1}\|z\|$ for all
$z\in\mathbb{R}^{d}$, where $\theta_{d-1}$ denotes the volume of a unit radius
ball in $d-1$ dimensions. Then by (2.4) we have

$\displaystyle\alpha_{2}(d)$
$\displaystyle=\int_{\mathbb{R}^{d}}\exp(-\theta_{d-1}\|z\|)dz=\theta_{d-1}^{-d}\int_{\mathbb{R}^{d}}e^{-\|u\|}du=\theta_{d-1}^{-d}d\theta\int_{0}^{\infty}e^{-r}r^{d-1}dr$
$\displaystyle=d!\theta/\theta_{d-1}^{d}.$

  4. 4.

It may be possible to improve the right hand side of (2.5) to an infinite
power series in $\lambda^{-1}$ and to compute the first few coefficients. This
series expansion would provide a high-intensity complement to the low-
intensity expansions in $\lambda$ which have been considered previously in the
literature dating back to [9]; see [20], [22, p.242] and references therein.

For the proof of Theorem 2.1, we introduce the following notation. Given ${\bf
x}=(x_{1},\ldots,x_{k})\in(\mathbb{R}^{d})^{k}$, recalling $B_{r}({\bf
x}):=\cup_{i=1}^{k}B_{r}(x_{i})$, we define

$\displaystyle V({\bf x}):={\rm Vol}(B_{1}({\bf x}));\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ V^{\prime}({\bf x}):={\rm
Vol}(B_{1}({\bf x})\setminus B_{1}(o));\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \rvert\rvert\rvert{\bf
x}\rvert\rvert\rvert:=\max_{1\leq i\leq k}\|x_{i}\|.$ (2.7)

The proof of Theorem 2.1 will use the following geometrical lemma, which
begins to show the relevance of $g({\bf z})$, defined above at (2.3) as the
quasi-gravitational energy of $D({\bf z})$.

######  Lemma 2.4.

For ${\bf z}\in(\mathbb{R}^{d})^{k}$, and $r>0$, set $g_{r}({\bf
z}):=r^{-1}V^{\prime}(r{\bf z})$. There exists a constant
$c=c(d)\in(0,\infty)$ such that for all $r\in(0,1]$ and ${\bf
z}\in(\mathbb{R}^{d})^{k}$ with $r\rvert\rvert\rvert{\bf
z}\rvert\rvert\rvert\leq 1$,

$\displaystyle|g_{r}({\bf z})-g({\bf z})|\leq cr\rvert\rvert\rvert{\bf
z}\rvert\rvert\rvert^{2}.$ (2.8)

###### Proof.

When $d=1$, it is easy to see directly that $g_{r}({\bf
z})=\max_{i}z_{i}^{+}+\max_{i}z_{i}^{-}=g({\bf z})$ whenever
$r\rvert\rvert\rvert{\bf z}\rvert\rvert\rvert\leq 1$, and hence that (2.8)
holds in this case. Therefore we can and do assume from now on that $d\geq 2$.

Let $r\in(0,1]$ and ${\bf z}=(z_{1},\ldots,z_{k})\in(\mathbb{R}^{d})^{k}$ with
$r\rvert\rvert\rvert{\bf z}\rvert\rvert\rvert\leq 1$. Using polar coordinates,
write

$g_{r}({\bf z})=r^{-1}\int_{\partial
B_{1}}\int_{0}^{\infty}\mathbbm{1}\\{(1+s)x\in\cup_{i=1}^{k}B_{1}(rz_{i})\\}(1+s)^{d-1}ds\sigma(dx),$

where the outer integral is a surface integral with the surface measure
denoted $\sigma$.

Given $x\in\partial B_{1}$, $y\in B_{1}$, let $s(x,y):=(\max\\{s:(1+s)x\in
B_{1}(y)\\})^{+}$. Then

$\displaystyle g_{r}({\bf z})$ $\displaystyle=r^{-1}\int_{\partial
B_{1}}\int_{0}^{\max_{i}s(x,rz_{i})}(1+s)^{d-1}ds\sigma(dx)$
$\displaystyle=\int_{\partial
B_{1}}(rd)^{-1}((1+\max_{i}s(x,rz_{i}))^{d}-1)\sigma(dx).$ (2.9)

By the triangle inequality, $s(x,rz_{i})\leq r\|z_{i}\|$, so the integrand in
(2.9) is bounded by a constant independent of $x$. We shall prove that the
limit $\lim_{r\downarrow 0}r^{-1}s(x,rz_{i})$ exists, for each $i\in[k]$ and
$x\in\partial S$, with a rate of convergence.

Figure 1: The union of the disks is the set $D((z_{1},z_{2},z_{3}))$. Figure
2: Illustration of the proof of Lemma 2.4.

The reader is invited to refer to Figure 2 now. Let $i\in[k]$ and set
$z=z_{i}$. If $z=o$ then $s(x,rz)=0$. Given $r\in(0,1]$, $z\in
B_{1/r}\setminus\\{o\\}$ and $x\in\partial B_{1}$, let $\alpha=\alpha(x,z)$ be
the angle between $x$ and $z$, i.e the angle of $(x,o,z)$, and assume
$\alpha<\pi/2$ (otherwise, it is not hard to see that $s(x,rz)=0$). Set
$s=s(x,rz)$. Let $\beta=\beta(r,x,z)$ be the angle of $((1+s)x,rz,z)$, i.e.
the angle between $(1+s)x-rz$ and $z$. Then $\|(1+s)x-rz\|=1$, and by the
cosine rule,

$(1+s)^{2}=\|rz+((1+s)x-rz)\|=(r\|z\|)^{2}+1+2r\|z\|\cos\beta.$

Also $\beta>\alpha$, and $\beta-\alpha$ is the most acute angle shown in
Figure 2; in other words, $\beta-\alpha=\arcsin(r\|z\|\sin\alpha)$.

If $t=\sin\omega$ with $\omega\in[0,\pi/2]$ then $t\geq(2/\pi)\omega$, so that
$\arcsin(t)=\omega\leq(\pi/2)t$. Hence for all $r\in(0,1]$, $z\in
B_{1/r}\setminus\\{o\\}$ and all $x\in\partial B_{1}$ such that
$\alpha(x,z)\in[0,\pi/2)$, we have
$0<\beta(r,x,z)-\alpha(x,z)\leq(\pi/2)r\|z\|$.

There is a constant $c_{1}$ such that for all $t\geq-1$ we have
$|(1+t)^{1/2}-1-t/2|\leq c_{1}t^{2}$. Hence there is another constant $c_{2}$
such that for all $r\in(0,1]$, $z\in B_{1/r}\setminus\\{o\\}$ and
$x\in\partial B_{1}$ with $\alpha(x,z)\in(0,\pi/2)$ we have

$\displaystyle|s(x,rz)-r\|z\|\cos\alpha(x,z)|=|(1+2r\|z\|\cos\beta(r,x,z)+r^{2}\|z\|^{2})^{1/2}-1-r\|z\|\cos\alpha(x,z)|$
$\displaystyle\leq|r\|z\|(\cos\beta(r,x,z)-\cos\alpha(x,z))|+\frac{r^{2}}{2}\|z\|^{2}+c_{1}(r\|z\|\cos\beta(r,x,z)+r^{2}\|z\|^{2})^{2}$
$\displaystyle\leq c_{2}r^{2}\|z\|^{2}.\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ $

There is a further constant $c_{3}$ such that for $t,u\in[0,1]$ we have
$|(1+u)^{d}-1-dt|\leq c_{3}(|u|^{2}+|u-t|).$ Therefore

$((1+\max_{i}s(x,rz_{i}))^{d}-1-rd\max_{i}\\{\|z_{i}\|(\cos\alpha(x,z_{i}))^{+}\\}\leq
c_{3}(\max_{i}s(x,rz_{i})^{2}+c_{2}r^{2}\rvert\rvert\rvert{\bf
z}\rvert\rvert\rvert^{2}).$

Hence by (2.9), and the inequality $s(x,rz_{i})\leq r\|z_{i}\|$, there is a
constant $c_{4}$ such that

$\displaystyle\left|g_{r}({\bf z})-\int_{\partial
B_{1}}\max_{i\in[k]}\\{\|z_{i}\|(\cos\alpha(x,z_{i}))^{+}\\}\sigma(dx)\right|\leq
c_{4}r\rvert\rvert\rvert{\bf z}\rvert\rvert\rvert^{2}.$ (2.10)

Using Thales’ theorem, one can show that
$\max_{i}\|z_{i}\|(\cos\alpha(x,z_{i}))^{+}$ is the distance from the origin
to the furthest point from the origin in the direction of $x$ lying in the set
$D({\bf z})$, defined at (2.2) (this is illustrated in Figure 1; the triangle
shown there is right angled.). Therefore using polar coordinates again, we can
verify that $g({\bf z})$, defined at (2.3), equals the integral in (2.10). ∎

###### Proof of Theorem 2.1.

Since $\mathbb{P}[|{\cal C}(\lambda)|=1]=e^{-\lambda\theta}$, and we set
$\alpha_{1}=1$, (2.5) is immediate for $k=0$. Therefore we can and do assume
from now on that $k\geq 1$.

Recall the definitions of $h_{r}(\cdot)$ and $B_{r}(\cdot)$ at (1.7), and
$V(\cdot)$ at (2.7). It is known (see e.g. [16]) that

$\displaystyle
p_{k+1}(\lambda)=\frac{\lambda^{k}}{k!}\int_{\mathbb{R}^{d}}\cdots\int_{\mathbb{R}^{d}}h_{1}((o,x_{1},\ldots,x_{k}))\exp(-\lambda
V((o,x_{1},\ldots,x_{k})))dx_{k}\cdots dx_{1}.$ (2.11)

This formula is a consequence of the multivariate Mecke formula (see e.g.
[11]); a similar formula to (2.11) is derived later on at (3.3).

Since $V((o,x_{1},\ldots,x_{k}))=V^{\prime}((x_{1},\ldots,x_{k}))+\theta$ by
(2.7), we obtain from (2.11) that

$\displaystyle p_{k+1}(\lambda)$
$\displaystyle=\frac{\lambda^{k}e^{-\lambda\theta}}{k!}\int_{(\mathbb{R}^{d})^{k}}h_{1}(o,{\bf
x})\exp(-\lambda V^{\prime}({\bf x}))d{\bf x}$
$\displaystyle=\frac{\lambda^{k-kd}e^{-\lambda\theta}}{k!}\int_{(\mathbb{R}^{d})^{k}}h_{1}((o,\lambda^{-1}{\bf
z}))\exp(-\lambda V^{\prime}(\lambda^{-1}{\bf z}))d{\bf z}.$ (2.12)

If $\rvert\rvert\rvert{\bf z}\rvert\rvert\rvert\leq\lambda/2$ then
$h_{1}((o,\lambda^{-1}{\bf z}))=h_{\lambda}((o,{\bf z}))=1$, and if
$\rvert\rvert\rvert{\bf z}\rvert\rvert\rvert>k\lambda$ then
$h_{\lambda}((o,{\bf z}))=0$. Thus provided $\lambda\geq 4$ so that
$\lambda^{1/2}\leq\lambda/2$, recalling the definition $g_{r}({\bf
z}):=r^{-1}V^{\prime}(r{\bf z})$, by (2.12) and (2.4) we have

$\displaystyle
k!|\lambda^{k(d-1)}e^{\lambda\theta}p_{k+1}(\lambda)-\alpha_{k+1}|\leq\int_{(B_{\sqrt{\lambda}})^{k}}|e^{-g_{1/\lambda}({\bf
z})}-e^{-g({\bf z})}|d{\bf z}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle+\int_{(B_{\lambda
k})^{k}\setminus(B_{\sqrt{\lambda}})^{k}}\exp(-g_{1/\lambda}({\bf z}))d{\bf
z}+\int_{(\mathbb{R}^{d})^{k}\setminus(B_{\sqrt{\lambda}})^{k}}e^{-g({\bf
z})}d{\bf z}.$ (2.13)

There is a constant $c=c(d)>0$ such that $g_{r}({\bf z})\geq
c\rvert\rvert\rvert{\bf z}\rvert\rvert\rvert$, for all $r>0$ and ${\bf
z}\in(\mathbb{R}^{d})^{k}$ with $\rvert\rvert\rvert r{\bf
z}\rvert\rvert\rvert\leq k$. Hence $g_{1/\lambda}({\bf z})\geq
c\rvert\rvert\rvert{\bf z}\rvert\rvert\rvert$ whenever $\rvert\rvert\rvert{\bf
z}\rvert\rvert\rvert\leq k\lambda$, and when $\rvert\rvert\rvert{\bf
z}\rvert\rvert\rvert>k\lambda$ we have $h_{1}((o,\lambda^{-1}{\bf z}))=0$.
Moreover by (2.8) we also have $g({\bf z})=\lim_{r\downarrow 0}g_{r}({\bf
z})\geq c\rvert\rvert\rvert{\bf z}\rvert\rvert\rvert$ for all ${\bf
z}\in(\mathbb{R}^{d})^{k}$. Therefore the second integral in (2.13) is bounded
by $\int_{(B_{\lambda
k})^{k}\setminus(B_{\sqrt{\lambda}})^{k}}\exp(-c\rvert\rvert\rvert{\bf
z}\rvert\rvert\rvert)d{\bf z},$ and hence by $\theta^{k}(\lambda
k)^{dk}\exp(-c\lambda^{1/2})$.

The third integral in (2.13) is bounded by
$\int_{(\mathbb{R}^{d})^{k}\setminus(B_{\lambda^{1/2}}(o))^{k}}e^{-c\rvert\rvert\rvert{\bf
z}\rvert\rvert\rvert}$, which is $O(\exp(-c^{\prime}\lambda^{1/2}))$ as
$\lambda\to\infty$, for some $c^{\prime}>0$..

The integrand in the first integral in (2.13) can be written as $e^{-g({\bf
z})}|e^{g({\bf z})-g_{1/\lambda}({\bf z})}-1|$. By Lemma 2.4, there are
constants $c^{\prime\prime},c^{\prime\prime\prime}$ such that for all large
$\lambda$ and all ${\bf z}\in(B_{\sqrt{\lambda}})^{k}$ we have $|g({\bf
z})-g_{1/\lambda}({\bf z})|\leq
c^{\prime\prime}\lambda^{-1}\rvert\rvert\rvert{\bf z}\rvert\rvert\rvert^{2}$
and thus $|e^{g({\bf z})-g_{1/\lambda}({\bf z})}-1|\leq
c^{\prime\prime\prime}\lambda^{-1}\rvert\rvert\rvert{\bf
z}\rvert\rvert\rvert^{2}$, so that the first integral in (2.13) is bounded by

$c^{\prime\prime\prime}\lambda^{-1}\int_{(\mathbb{R}^{d})^{k}}e^{-g({\bf
z})}\rvert\rvert\rvert{\bf z}\rvert\rvert\rvert^{2}d{\bf z},$

and since $g({\bf z})\geq c\rvert\rvert\rvert{\bf z}\rvert\rvert\rvert$ for
all ${\bf z}$, the last integral is finite and the result is proved. ∎

###### Proof of Theorem 2.2.

Let $f:(\mathbb{R}^{d})^{k}\to\mathbb{R}$ be bounded and continuous. Write
${\bf Y}_{\lambda}:=(Y_{1,\lambda},\ldots,Y_{k,\lambda})$. We need to show
that $\mathbb{E}[f(\lambda{\bf Y}_{\lambda})|\\{|{\cal
C}(\lambda)|=k+1\\}]\to\mathbb{E}[f(V_{1},\ldots,V_{k})]$. For
$(x_{1},\ldots,x_{k})\in(\mathbb{R}^{d})^{k}$ let
$f^{*}((x_{1},\ldots,x_{k})):=f((x_{(1)},\ldots,x_{(k)}))$, where
$x_{(1)},\ldots,x_{(k)}$ are the elements of $\\{x_{1},\ldots,x_{k}\\}$ taken
in increasing lexicographic order. Then $f^{*}$ is a symmetric function of
$(x_{1},\ldots,x_{k})$. By the multivariate Mecke formula

$\displaystyle\mathbb{E}[f(\lambda{\bf Y}_{\lambda})\mathbbm{1}\\{|{\cal
C}(\lambda)|=k+1\\}]$
$\displaystyle=\frac{\lambda^{k}}{k!}\int_{(\mathbb{R}^{d})^{k}}f^{*}(\lambda{\bf
x})h_{1}((o,{\bf x}))\exp(-\lambda V((o,{\bf x})))d{\bf x}$
$\displaystyle=\frac{e^{-\lambda\theta}\lambda^{k(1-d)}}{k!}\int_{(\mathbb{R}^{d})^{k}}f^{*}({\bf
z})h_{1}((o,\lambda^{-1}{\bf z}))\exp(-g_{1/\lambda}({\bf z}))d{\bf z}.$

We divide by $\mathbb{P}[|{\cal C}(\lambda)|=k+1]$ and take the
$\lambda\to\infty$ limit. By Lemma 2.4 the integrand tends to $f^{*}({\bf
z})e^{-g({\bf z})}$, and it is dominated by an integrable function of ${\bf
z}$, as in the proof of Theorem 2.1. Hence, using (2.5) and the dominated
convergence theorem we obtain that

$\displaystyle\lim_{\lambda\to\infty}\mathbb{E}[f(\lambda{\bf
Y}_{\lambda}))|\\{|{\cal C}(\lambda)|=k+1\\}]$
$\displaystyle=(k!\alpha_{k+1})^{-1}\int_{(\mathbb{R}^{d})^{k}}f^{*}({\bf
z})\exp(-g({\bf z}))d{\bf z}$
$\displaystyle=\mathbb{E}[f^{*}((U_{1},\ldots,U_{k}))],$

the last line coming from (2.6) and the law of the unconscious statistician.
Since $f((V_{1},\ldots,V_{k}))=f^{*}((U_{1},\ldots,U_{k}))$, the result is
proved. ∎

##  3 First order asymptotics

Now we return to the model of finite random geometric graphs, described in
Section 1. To recall, we let $A\subset\mathbb{R}^{d}$ be compact with ${\rm
Vol}(A)>0$. If $d\geq 2$ then assume, for the rest of this paper, that $A$ has
a smooth boundary in the sense that for each $x\in\partial A$ there exists a
neighbourhood $U$ of $x$ and a real-valued function $\phi$ that is defined on
an open set in $\mathbb{R}^{d-1}$ and twice continuously differentiable, such
that $\partial A\cap U$, such that $\partial A\cap U$, after a rotation, is
the graph of the function $\phi$. If $d=1$ we assume $A$ is an interval.

Recall that $(X_{1},X_{2},\ldots)$ is a sequence of independent random
$d$-vectors, each of which has distribution, denoted $\nu$, with density
function $f$ with support $A$ and with $0<f_{0}\leq f_{\rm max}<\infty$.
Recall the point processes ${\cal X}_{n}:=\\{X_{1},\ldots,X_{n}\\}$ and ${\cal
P}_{n}:=\\{X_{1},\ldots,{\cal X}_{Z_{n}}\\}$, where $Z_{n}$ is Poisson with
parameter $n$ (in the second case $n$ need not be an integer). Then ${\cal
X}_{n}$ is a binomial point process, and ${\cal P}_{n}$ is a Poisson point
process in $A$ with $\mathbb{E}[{\cal P}_{n}(dx)]=nf(x)dx$. In the uniform
case we take $f=f_{0}\mathbbm{1}_{A}$, with $f_{0}=1/{\rm Vol}(A)$. For $n>0$
let $r=r_{n}=r(n)>0$ be given, satisfying (1.1) and (1.6), which we re-state
here:

$\displaystyle\lim_{n\to\infty}nr_{n}^{d}=\infty;\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \limsup_{n\to\infty}n\theta
r_{n}^{d}/(\log n)<\frac{1}{\max(f_{0},d(f_{0}-f_{1}/2))}.$ (3.1)

We shall continue to assume (3.1) throughout the rest of this paper, except
for Section 6.

Let $k\in\mathbb{N}$, and recall that $S^{\prime}_{n,k}$ denotes the number of
components of $G({\cal P}_{n},r)$ of order $k$ (again, $n$ need not be an
integer here).

We give a formula for $I_{n,k}:=\mathbb{E}[S^{\prime}_{n,k}]$. With
$h_{r}(\cdot)$ and $B_{r}(\cdot)$ defined at (1.7),

$\displaystyle S^{\prime}_{n,k}=\sum_{\varphi\subset{\cal
P}_{n},|\varphi|=k}h_{r}(\varphi)\mathbbm{1}\\{({\cal
P}_{n}\setminus\varphi)\cap B_{r}(\varphi)=\varnothing\\}.$ (3.2)

Hence by the multivariate Mecke formula,

$\displaystyle
I_{n,k}=\mathbb{E}[S^{\prime}_{n,k}]=\frac{n^{k}}{k!}\int_{A^{k}}h_{r}({\bf
x})\exp(-n\nu(B_{r}({\bf x})))\nu^{k}(d{\bf x}).$ (3.3)

It will be useful to have a lower bound on this expectation.

######  Lemma 3.1.

Let $f_{0}^{+}$ be any constant with $f_{0}^{+}>f_{0}$. Then as $n\to\infty$,

$\displaystyle n\exp(-\theta f_{0}^{+}nr^{d})=o(I_{n,k}).$ (3.4)

In particular, $I_{n,k}\to\infty$ as $n\to\infty$.

###### Proof.

Let $f_{0}<\alpha<\alpha^{\prime}<f_{0}^{+}$. By the definition of $f_{0}$ and
the assumption that $f$ is continuous on $A$, we can (and do) choose $x_{0}\in
A^{o}$ with $f(x_{0})<\alpha$ and $f$ continuous at $x_{0}$. Choose $r_{0}>0$
such that $B(x_{0},2r_{0})\subset A$ and $f(y)\leq\alpha$ for all $y\in
B(x_{0},2r_{0})$. Let $\varepsilon\in(0,1/2)$ with
$\alpha(1+\varepsilon)^{d}<\alpha^{\prime}$. If $2r\leq r_{0}$, and ${\bf
x}=(x_{1},\ldots,x_{k})\in A^{k}$ with $x_{1}\in B(x_{0},r_{0})$, and
$\\{x_{1},\ldots,x_{k}\\}\subset B(x_{1},\varepsilon r)$ then $B_{r}({\bf
x})\subset B_{r(1+\varepsilon)}(x_{1})$ and $\nu(B_{r}({\bf
x}))\leq\alpha\theta(1+\varepsilon)^{d}r^{d}<\alpha^{\prime}\theta r^{d}$;
also $h_{r}({\bf x})=1$. Hence by (3.3), for all large enough $n$,

$\displaystyle I_{n,k}$
$\displaystyle\geq\frac{n^{k}}{k!}\int_{B(x_{0},r_{0})}\int_{B(x_{1},\varepsilon
r)^{k-1}}\exp(-n\alpha^{\prime}\theta
r^{d})\nu^{k-1}(d(x_{2},\ldots,x_{k}))\nu(dx_{1})$ $\displaystyle\geq
n(f_{0}^{k}\theta^{k}r_{0}^{d}/k!)(n(\varepsilon
r)^{d})^{k-1}\exp(-n\alpha^{\prime}\theta r^{d}),$

so that $(ne^{-n\theta f_{0}^{+}r^{d}})/I_{n,k}$ tends to zero by the first
part of (3.1), and hence (3.4).

Since the assumption (3.1) implies $\limsup_{n\to\infty}((\theta
f_{0}nr_{n}^{d})/\log n)<1$, (3.4) implies $I_{n,k}\to\infty$ as $n\to\infty$.
∎

We next determine the asymptotics for $\mathbb{E}[S_{n,k}]$.

######  Proposition 3.2 (Mean $k$-cluster count in binomial process).

There exists $c>0$ such that as $n\to\infty$, with $I_{n,k}$ defined at (3.3),
we have

$\displaystyle\mathbb{E}[S_{n,k}]=I_{n,k}(1+O(e^{-cnr^{d}})).$

###### Proof.

Observe that

$\displaystyle\mathbb{E}[S_{n,k}]=\binom{n}{k}\int_{A^{k}}h_{r}({\bf
x})(1-\nu(B_{r}({\bf x})))^{n-k}\nu^{k}(d{\bf x}).$ (3.5)

We compare this with (3.3). Let ${\bf x}\in A^{k}$ and set $p=\nu(B_{r}({\bf
x}))$. Then

$\displaystyle|e^{-np}-(1-p)^{n-k}|\leq
e^{-np}|1-(e^{p}(1-p))^{n}|+(1-p)^{n-k}|(1-p)^{k}-1|.$

Now $e^{p}(1-p)\leq e^{p}e^{-p}=1$, and moreover
$e^{p}(1-p)\geq(1+p)(1-p)=1-p^{2}$. Therefore

$0\leq e^{-np}(1-(e^{p}(1-p))^{n})\leq e^{-np}(1-(1-p^{2})^{n})\leq
np^{2}e^{-np}.$

Moreover $1-(1-p)^{k}=O(r^{d})$. Thus $|e^{-np}-(1-p)^{n-k}|=O(nr^{2d})$,
uniformly over ${\bf x}\in A^{k}$. Also $\int_{A^{k}}h_{r}({\bf
x})\nu^{k}(d{\bf x})=O(r^{d(k-1)})$. Therefore

$\displaystyle\binom{n}{k}\int_{A^{k}}h_{r}({\bf x})|e^{-n\nu(B_{r}({\bf
x}))}-(1-\nu(B_{r}({\bf x})))^{n-k}|\nu^{k}(d{\bf
x})=O(n^{k}r^{d(k-1)}(nr^{2d})),$

which is $O((\log n)^{k+1})$ by (3.1). By Lemma 3.1 and (3.1) there exists
$\delta>0$ such that $I_{n,k}=\Omega(n^{2\delta})$. Hence by (3.1) again there
exists $c>0$ such that $(\log
n)^{k+1}/I_{n,k}=O(n^{-\delta})=O(e^{-cnr^{d}})$. Thus the last display is
$O(e^{-cnr^{d}}I_{n})$ for some $c>0$. Moreover

$\displaystyle\left|\frac{n^{k}}{k!}-\binom{n}{k}\right|\int_{A^{k}}h_{r}({\bf
x})e^{-n\nu(B_{r}({\bf x}))}\nu^{k}(d{\bf x})=O(n^{-1}I_{n,k}),$

which is $O(e^{-cnr^{d}}I_{n,k})$ for some other $c>0$. Combining these
estimates, and using (3.5) and (3.3), we obtain that
$|\mathbb{E}[S_{n,k}]-I_{n,k}|=O(e^{-cnr^{d}}I_{n,k})$ for some $c>0$, as
required. ∎

We now verify the asymptotic expression (1.3) for $I_{n,k}$ in the uniform
case, showing that the constant denoted $c$ there equals
$k^{-1}\alpha_{k}f_{0}^{(1-k)(d-1)}$, with $\alpha_{k}$ given at (2.5), and
with a bound on the rate of convergence.

######  Theorem 3.3 (Asymptotic for $I_{n,k}$ in the uniform case).

Let $k\in\mathbb{N}$. In the uniform case,

$\displaystyle n^{-1}(f_{0}nr^{d})^{(k-1)(d-1)}e^{f_{0}\theta
nr^{d}}I_{n,k}=k^{-1}\alpha_{k}+O((nr^{d})^{-1})\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ {\rm
as}\leavevmode\nobreak\ \leavevmode\nobreak\ n\to\infty.$ (3.6)

Before proving this, we give a lemma that we shall use repeatedly later on to
deal with boundary effects.

######  Lemma 3.4.

Writing $\kappa(\partial A,r)$ for the number of balls of radius $r$ required
to cover $\partial A$, we have

$\displaystyle\limsup_{s\downarrow 0}s^{d-1}\kappa(\partial A,s)<\infty.$
(3.7)

Moreover

$\displaystyle\liminf_{s\downarrow 0}(s^{-d}\inf_{x\in A}{\rm Vol}(A\cap
B_{s}(x)))\geq\theta/2.$ (3.8)

Finally, as $s\downarrow 0$ we have $\limsup(s^{-1}{\rm Vol}(A\setminus
A^{(s)}))<\infty$.

###### Proof.

If $d=1$ we are assuming $A$ is a compact interval, and all the assertions of
the lemma are clear.

Suppose $d\geq 2$. Then by our smoothness assumption, and [18, Lemma 6.7],
$\partial A$ is a $(d-1)$-dimensional $C^{2}$ submanifold of $\mathbb{R}^{d}$.
Then by [15, Lemma 5.4] we have (3.7), and by [15, Lemma 5.7], we have (3.8).

For the last assertion, given $s>0$, set $\kappa_{s}:=\kappa(\partial A,s)$.
By definition of $\kappa_{s}$, we can find
$x_{1},\ldots,x_{\kappa_{s}}\in\mathbb{R}^{d}$ such that $\partial
A\subset\cup_{i=1}^{\kappa_{s}}B(x_{i},s)$. Then $A\setminus
A^{(s)}\subset\cup_{i=1}^{\kappa_{s}}B(x_{i},2s)$. Also
$\kappa_{s}=O(s^{1-d})$ as $s\downarrow 0$, by (3.7). Hence by the union
bound,

${\rm Vol}(A\setminus A^{(s)})\leq\sum_{i=1}^{\kappa_{s}}{\rm
Vol}(B(x_{i},2s))=O(s),$

which is the last assertion. ∎

###### Proof of Theorem 3.3.

Assume $\nu$ is uniform on $A$. By definition
$I_{n,k}=\mathbb{E}[S^{\prime}_{n,k}]$. Hence, by the (univariate) Mecke
formula, writing ${\cal P}_{n}^{x}$ for ${\cal P}_{n}\cup\\{x\\}$, we have

$\displaystyle I_{n,k}=\frac{n}{k}\int_{A}\mathbb{P}[|{\cal C}_{r}(x,{\cal
P}_{n}^{x})|=k]f_{0}dx,$ (3.9)

By the multivariate Mecke formula, setting $V_{r}({\bf x}):={\rm
Vol}(B_{r}({\bf x}))$ for ${\bf x}\in(\mathbb{R}^{d})^{k}$, for $x\in
A^{(kr)}$ we have

$\mathbb{P}[|{\cal C}_{r}(x,{\cal
P}_{n}^{x})|=k]=\frac{(nf_{0})^{k-1}}{(k-1)!}\int_{(\mathbb{R}^{d})^{k-1}}h_{r}((x,{\bf
x}))\exp(-nf_{0}V_{r}((x,{\bf x})))d{\bf x},$

where we used the fact that if $x\in A^{(kr)}$ and $h_{r}((x,{\bf x}))=1$ then
$B_{r}((x,{\bf x}))\subset A$. Hence by translation invariance, for $x\in
A^{(kr)}$, writing $h_{r}(o,{\bf x})$ for $h_{r}((o,{\bf x}))$ and
$V_{r}(o,{\bf x})$ for $V_{r}((o,{\bf x}))$ we have

$\displaystyle\mathbb{P}[|{\cal C}_{r}(x,{\cal P}_{n}^{x})|=k]$
$\displaystyle=\frac{(nf_{0})^{k-1}}{(k-1)!}\int_{(\mathbb{R}^{d})^{k-1}}h_{r}(o,{\bf
x})\exp(-nf_{0}V_{r}(o,{\bf x}))d{\bf x}$
$\displaystyle=\frac{(nf_{0}r^{d})^{k-1}}{(k-1)!}\int_{(\mathbb{R}^{d})^{k-1}}h_{r}(o,r{\bf
y})\exp(-nf_{0}V_{r}(o,r{\bf y}))d{\bf y}$
$\displaystyle=\frac{(nf_{0}r^{d})^{k-1}}{(k-1)!}\int_{(\mathbb{R}^{d})^{k-1}}h_{1}(o,{\bf
y})\exp(-nf_{0}r^{d}V_{1}(o,{\bf y}))d{\bf y}$

and by (2.11), this equals $p_{k}(f_{0}nr^{d})$. Therefore using (2.5) and the
last part of Lemma 3.4 we obtain that as $n\to\infty$,

$\displaystyle\int_{A^{(kr)}}\mathbb{P}[|{\cal C}_{r}(x,{\cal
P}_{n}^{x})|=k]f_{0}dx=(1+O(r))\alpha_{k}(f_{0}nr^{d})^{(1-k)(d-1)}e^{-\theta
f_{0}nr^{d}}(1+O((nr^{d})^{-1})).$ (3.10)

To deal with $x\in A\setminus A^{(kr)}$, let $f_{0}^{-}\in(0,f_{0})$. By the
smoothness assumption and Lemma 3.4 we have for all large enough $n$ and all
$x\in A$ that $\nu(B_{r}(x))\geq\theta f_{0}^{-}r^{d}/2$. Therefore using the
multivariate Mecke formula we have for all large enough $n$ and all $x\in A$
that

$\mathbb{P}[|{\cal C}_{r}(x,{\cal
P}_{n}^{x})|=k]\leq\frac{(nf_{0})^{k-1}}{(k-1)!}\int_{A^{k-1}}h_{r}(x,{\bf
x})\exp(-n\theta f_{0}^{-}r^{d}/2)d{\bf x},$

which is $O((nr^{d})^{k-1}\exp(-n\theta f_{0}^{-}r^{d}/2))$, uniformly over
$x\in A$. Hence by the last part of Lemma 3.4 we obtain that

$\int_{A\setminus A^{(kr)}}\mathbb{P}[|{\cal C}_{r}(x,{\cal
P}_{n}^{x})|=k]f_{0}dx=O(r(nr^{d})^{k-1}\exp(-n\theta f_{0}^{-}r^{d}/2)),$

which is negligible compared to the right hand side of (3.10) by (3.1),
provided we take $f_{0}^{-}$ close enough to $f_{0}$ (here $f_{0}=f_{1}$ so
(3.1) implies $\limsup_{n\to\infty}(n\theta f_{0}r_{n}^{d}/\log n)<2/d$). Thus
using (3.9) we obtain (3.6). ∎

In the non-uniform case, we do not have such precise asymptotics for
$I_{n,k}$. However we do have the following, which formalises back-of-the-
envelope calculations suggesting $I_{n,k}\approx n\exp(-n\theta
f_{0}r_{n}^{d})$.

######  Theorem 3.5 (Limiting behaviour of $I_{n,k}$ in the non-uniform case).

Let $k\in\mathbb{N}$. Then

$\displaystyle\lim_{n\to\infty}\left((nr^{d})^{-1}\log(I_{n,k}/n)\right)=-\theta
f_{0}.$ (3.11)

###### Proof.

By Lemma 3.1, given $f_{0}^{+}>f_{0}$ we have for large $n$ that $I_{n,k}\geq
n\exp(-n\theta f_{0}^{+}r^{d})$, so that $\log(I_{n,k}/n)\geq-n\theta
f_{0}^{+}r^{d}$, and hence

$\liminf_{n\to\infty}\left((nr^{d})^{-1}\log(I_{n,k}/n)\right)\geq-\theta
f_{0}.$

For a bound the other way, note that $\nu(B_{r}(x))\geq\theta f_{0}r^{d}$ for
$x\in A^{(r)}$. Also using Lemma 3.4, given $f_{1}^{-}<f_{1}$ we have for $n$
large enough that $\nu(B_{r}(x))\geq(\theta/2)f_{1}^{-}r^{d}$ for all $x\in
A$. Therefore using the last part of Lemma 3.4, we have that

$\displaystyle I_{n,k}\leq$ $\displaystyle n\nu(A^{(r)})(nf_{\rm
max}\theta((k-1)r)^{d})^{k-1}\exp(-n\theta f_{0}r^{d})$
$\displaystyle+O(nr(nr^{d})^{k-1}\exp(-n(\theta/2)f_{1}^{-}r^{d})).$ (3.12)

The second term in the right-hand side of (3.12), divided by the first term,
is bounded by a constant times $r\exp(n\theta r^{d}(f_{0}-f^{-}_{1}/2))$, and
using (3.1) we can show this tends to zero, provided $f_{1}^{-}$ is chosen
close enough to $f_{1}$. Hence by (3.12) we can deduce that

$\limsup_{n\to\infty}\left((nr^{d})^{-1}\log(I_{n,k}/n)\right)\leq-\theta
f_{0},$

and hence (3.11). ∎

##  4 Variance asymptotics and laws of large numbers

In this section, we show that the variance of the $k$-cluster count $S_{n,k}$
and its expectation are asymptotically equivalent, with explicit rates, and
likewise for $S^{\prime}_{n,k}$. As mentioned in Section 1, this is enough to
yield weak laws of large numbers for $S_{n,k}$ and $S^{\prime}_{n,k}$ but we
shall also derive concentration results which yield strong laws of large
numbers.

###  4.1 Variance asymptotics in the Poisson setting

######  Proposition 4.1.

Let $k\in\mathbb{N}$. Then there exists $c>0$ such that as $n\to\infty$,

$\displaystyle\mathbb{V}\mathrm{ar}[S^{\prime}_{n,k}]=\mathbb{E}[S^{\prime}_{n,k}](1+O(e^{-cnr^{d}}))=I_{n,k}(1+O(e^{-cnr^{d}})).$

###### Proof.

Since $S^{\prime}_{n,k}(S^{\prime}_{n,k}-1)$ is the number of ordered pairs of
distinct $k$-clusters in $G({\cal P}_{n},r)$, with $h(\cdot):=h_{r}(\cdot)$ as
given at (1.7), we can write $S^{\prime}_{n,k}(S^{\prime}_{n,k}-1)$ as follows

$\displaystyle\sum_{\varphi,\psi\subset{\cal
P}_{n},|\varphi|=|\psi|=k}h(\varphi)h(\psi)\mathbbm{1}\\{({\cal
P}_{n}\setminus\varphi\setminus\psi)\cap
B_{r}(\varphi\cup\psi)=\varnothing,\operatorname{dist}(\varphi,\psi)>r\\}.$

Indeed, for distinct $k$-subsets $\psi,\varphi$ of ${\cal P}_{n}$, their
distance must be larger than $r$ in order that they are both connected
components of order $k$, for otherwise $\psi$ and $\varphi$ are connected with
$|\psi\cup\varphi|>k$. Thus by the multivariate Mecke equation
$\mathbb{E}[(S^{\prime}_{n,k})^{2}]-\mathbb{E}[S^{\prime}_{n,k}]$ equals

$\displaystyle\frac{n^{2k}}{k!k!}\int_{A^{k}}\int_{A^{k}}h({\bf x})h({\bf
y})\exp(-n\nu(B_{r}({\bf x},{\bf y})))\mathbbm{1}\\{\operatorname{dist}({\bf
x},{\bf y})>r\\}\nu^{k}(d{\bf y})\nu^{k}(d{\bf x}),$

where $B_{r}({\bf x},{\bf y}):=B_{r}({\bf x})\cup B_{r}({\bf y})$. We compare
this integral with

$\displaystyle\mathbb{E}[S^{\prime}_{n,k}]^{2}=\frac{n^{2k}}{k!k!}\int_{A^{k}}\int_{A^{k}}h({\bf
x})h({\bf y})\exp(-n[\nu(B_{r}({\bf x}))+\nu(B_{r}({\bf y}))])\nu^{k}(d{\bf
y})\nu^{k}(d{\bf x}),$

which comes from (3.3). Observe that $\nu(B_{r}({\bf x},{\bf
y}))=\nu(B_{r}({\bf x}))+\nu(B_{r}({\bf y}))$ whenever
$\operatorname{dist}({\bf x},{\bf y})>2r$. Therefore
$|\mathbb{V}\mathrm{ar}[S^{\prime}_{n,k}]-\mathbb{E}[S^{\prime}_{n,k}]|\leq
J_{1,n}+J_{2,n}$, where

$\displaystyle J_{1,n}$
$\displaystyle:=\frac{n^{2k}}{k!k!}\int_{A^{k}}\int_{A^{k}}h({\bf x})h({\bf
y})\exp(-n\nu(B_{r}({\bf x},{\bf y})))\mathbbm{1}\\{\operatorname{dist}({\bf
x},{\bf y})\in(r,2r]\\}\nu^{k}(d{\bf y})\nu^{k}(d{\bf x});$ (4.1)
$\displaystyle J_{2,n}$ $\displaystyle:=\frac{n^{2k}}{k!k!}\int_{A^{2k}}h({\bf
x})h({\bf y})\exp(-n[\nu(B_{r}({\bf x}))+\nu(B_{r}({\bf
y}))])\mathbbm{1}\\{\operatorname{dist}({\bf x},{\bf y})\leq
2r\\}\nu^{2k}(d({\bf x},{\bf y})).$ (4.2)

We estimate $J_{1,n}$ in Lemma 4.2 below. For $J_{2,n}$, note that by Lemma
3.4 there exists $n_{0}$ such that for all $n\geq n_{0}$ and all ${\bf y}\in
A^{k}$ we have $\nu(B_{r}({\bf y}))\geq(\theta/3)f_{0}r^{d}$. Hence for ${\bf
x}\in A^{k}$ we have

$\frac{n^{k}}{k!}\int_{A^{k}}h({\bf y})\exp(-n\nu(B_{r}({\bf
y})))\mathbbm{1}\\{\operatorname{dist}({\bf x},{\bf y})\leq 2r\\}\nu^{k}(d{\bf
y})=O((nr^{d})^{k}\exp(-n(\theta/3)f_{0}r^{d})),$

and hence $J_{2,n}=O(I_{n,k}(nr^{d})^{k}\exp(-nf_{0}(\theta/3)r^{d}))$, which
is $O(I_{n,k}\exp(-nf_{0}(\theta/4)r^{d}))$. Combined with Lemma 4.2, this
completes the proof. ∎

######  Lemma 4.2.

Let $J_{1,n}$ be given by (4.1). There exists $c>0$ such that
$J_{1,n}=O(e^{-cnr^{d}}I_{n,k})$ as $n\to\infty$.

###### Proof.

Let us write ${\bf x}\prec{\bf y}$ if there exists
$y\in\\{y_{1},\ldots,y_{k}\\}$ such that all points of
$\\{x_{1},\ldots,x_{k}\\}$ precede $y$ in the lexicographic ordering (or in
other words, the rightmost entry of ${\bf x}$ lies to the left of the
rightmost entry of ${\bf y}$). Since the integrand in $J_{1}$ is symmetric in
${\bf x}$ and ${\bf y}$, $J_{1}$ is twice the same expression with the inner
integral restricted to ${\bf y}$ satisfying ${\bf x}\prec{\bf y}$.

Suppose ${\bf x},{\bf y}\in(\mathbb{R}^{d})^{k}$ with $h({\bf x})=h({\bf
y})=1$ and $\operatorname{dist}({\bf y},{\bf x})\in(r,2r]$. These conditions
imply that ${\bf y}\in(B_{2kr}(x_{1}))^{k}$, where we write ${\bf
x}=(x_{1},\ldots,x_{k})$. Thus, if also ${\bf x}\in(A^{(9kr)})^{k}$ then ${\bf
y}\in(A^{(7kr)})^{k}$, and if moreover ${\bf x}\prec{\bf y}$, by considering
the right half of the ball of radius $r$ centred on the right-most entry of
${\bf y}$, we see that $\nu(B_{r}({\bf y})\setminus B_{r}({\bf x}))\geq(\theta
f_{0}/2)r^{d}$. Therefore since $B_{r}({\bf x},{\bf y})=B_{r}({\bf
x})\cup(B_{r}({\bf y})\setminus B_{r}({\bf x}))$ and this is a disjoint union,

$\displaystyle J_{1,n}\leq\frac{2n^{k}}{k!}\int_{(A^{(9kr)})^{k}}h({\bf
x})\exp(-n\nu(B_{r}({\bf x})))a({\bf x})\nu^{k}(d{\bf x})+z_{n},$

where

$\displaystyle a({\bf x}):=\frac{n^{k}}{k!}\int_{A^{k}}e^{-(\theta
f_{0}/2)nr^{d}}h({\bf y})\mathbbm{1}\\{\operatorname{dist}({\bf x},{\bf
y})\in(r,2r],{\bf x}\prec{\bf y}\\}\nu^{k}(d{\bf y}),$ (4.3)

and $z_{n}$ is a remainder term from ${\bf x}$ near $\partial A$ (to be dealt
with later).

As already mentioned, if ${\bf x},{\bf y}\in A^{k}$ with $h({\bf x})=h({\bf
y})=1$ and $r<\operatorname{dist}({\bf x},{\bf y})\leq 2r$, then ${\bf
y}\in(B_{2kr}(x_{1}))^{k}$, and consequently

$\displaystyle a({\bf x})\leq\frac{(nf_{\rm max})^{k}}{k!}e^{-(\theta
f_{0}/2)nr^{d}}\theta^{k}(2kr)^{kd}=O((nr^{d})^{k}e^{-(\theta
f_{0}/2)nr^{d}})=O(e^{-(\theta f_{0}/3)nr^{d}}),$

uniformly over ${\bf x}\in A^{k}$. Therefore by virtue of (3.3), we have
$J_{1,n}-z_{n}=O(e^{-(\theta f_{0}/3)nr^{d}}I_{n,k})$.

For the remainder term, note that given $f_{1}^{-}<f_{1}$, by Lemma 3.4 and
the assumed continuity of $f|_{A}$, there exists $n_{0}$ such that for all
$n\geq n_{0}$ and all ${\bf x}\in A^{k}\setminus(A^{(9r)})^{k}$, we have
$\nu(B_{r}({\bf x}))\geq n(\theta f_{1}^{-}/2)r^{d}$. Also if ${\bf
x}=(x_{1},\ldots,x_{k})\in A^{k}\setminus(A^{(9kr)})^{k}$ then at least one of
$x_{1},\ldots,x_{k}$ lies in $A\setminus A^{(9kr)}$. Introducing a factor of
$k$ we can assume this is $x_{1}$, and hence deduce that

$\displaystyle|z_{n}|\leq\frac{2(nf_{\rm max})^{2k}}{(k-1)!}\int_{A\setminus
A^{(9kr)}}(\theta(2kr)^{d})^{2k-1}dx_{1}e^{-n\theta
f_{1}^{-}r^{d}/2}=O(nr(nr^{d})^{2k-1}e^{-n\theta f_{1}^{-}r^{d}/2}).$

Combined with (3.4) this shows that $z_{n}/I_{n,k}=O(r\exp(n\theta
r^{d}(f_{0}^{+}-f_{1}^{-}/2)))$, for any $f_{0}^{+}>f_{0}$. Using (3.1), we
can choose $\varepsilon>0$, $f_{0}^{+}>f_{0}$ and $f_{1}^{-}<f_{1}$ in such a
way that this upper bound implies $z_{n}/I_{n,k}=O(rn^{(1/d)-\varepsilon})$,
and using (3.1) again we see that this is $O(e^{-cnr^{d}})$ for some $c>0$.
Thus $J_{1,n}=O(e^{-cnr^{d}}I_{n,k})$ for some $c>0$. ∎

###  4.2 Variance asymptotics in the binomial case

######  Proposition 4.3.

There exists $c>0$ such that as $n\to\infty$,

$\displaystyle\mathbb{V}\mathrm{ar}[S_{n,k}]=\mathbb{E}[S_{n,k}](1+O(e^{-cnr^{d}})).$
(4.4)

###### Proof.

Let $\prec$ denote the lexicographic ordering on $\mathbb{R}^{d}$. Write
$S_{n,k}=\sum_{i=1}^{n}\xi_{i}$, here taking

$\displaystyle\xi_{i}:=\mathbbm{1}\\{|{\cal C}_{r}(X_{i},{\cal
X}_{n})|=k,X_{i}\prec y\leavevmode\nobreak\ \forall y\in{\cal
C}_{r}(X_{i},{\cal X}_{n})\setminus\\{X_{i}\\}\\}.$ (4.5)

Then $\mathbb{E}[S_{n,k}]=n\mathbb{E}[\xi_{1}]$, and
$\mathbb{E}[S_{n,k}^{2}]=n\mathbb{E}[\xi_{1}^{2}]+n(n-1)\mathbb{E}[\xi_{1}\xi_{2}],$
so that
$\mathbb{E}[S_{n,k}^{2}]=\mathbb{E}[S_{n,k}]+n(n-1)\mathbb{E}[\xi_{1}\xi_{2}]$.
Hence,

$\displaystyle\mathbb{V}\mathrm{ar}[S_{n,k}]-\mathbb{E}[S_{n,k}]=-n\mathbb{E}[\xi_{1}\xi_{2}]+n^{2}(\mathbb{E}[\xi_{1}\xi_{2}]-\mathbb{E}[\xi_{1}]\mathbb{E}[\xi_{2}]).$
(4.6)

In view of Proposition 3.2 we need to show the right hand side of (4.6) is
$O(e^{-cnr^{d}}I_{n,k})$.

For ${\bf x}=(x_{1},\ldots,x_{k})\in(\mathbb{R}^{d})^{k}$, recall from (1.7)
that $h^{*}_{r}({\bf x})$ is the indicator variable of the event that
$G(\\{x_{1},\ldots,x_{k}\\},r)$ is connected and moreover $x_{1}\prec x_{i}$
for $i=2,\ldots,k$. Then

$\displaystyle\mathbb{E}[\xi_{1}]=\binom{n-1}{k-1}\int_{A^{k}}h^{*}_{r}({\bf
x})(1-\nu(B_{r}({\bf x})))^{n-k}\nu^{k}(d{\bf x}).$ (4.7)

Consider the first term in the right hand side of (4.6). Observe that if
$\xi_{1}=\xi_{2}=1$ then ${\cal C}_{r}(X_{2},{\cal X}_{n})\cap B_{r}({\cal
C}_{r}(X_{1},{\cal X}_{n}))=\varnothing$. Hence, using the bound $1-t\leq
e^{-t}$ for all $t\geq 0$ and writing $B_{r}({\bf x},{\bf y}):=B_{r}({\bf
x})\cup B_{r}({\bf y})$, we have that $n\mathbb{E}[\xi_{1}\xi_{2}]$ equals

$\displaystyle
n\binom{n-2}{k-1}\binom{n-1-k}{k-1}\int_{A^{k}}\int_{(A\setminus B_{r}({\bf
x}))^{k}}h_{r}^{*}({\bf x})h_{r}^{*}({\bf y})(1-\nu(B_{r}({\bf x},{\bf
y})))^{n-2k}\nu^{k}(d{\bf y})\nu^{k}(d{\bf x})$ (4.8)
$\displaystyle\leq\frac{2n^{2k-1}}{(k-1)!^{2}}\int_{A^{k}}\int_{(A\setminus
B_{r}({\bf x}))^{k}}h_{r}^{*}({\bf x})h_{r}^{*}({\bf y})\exp(-n\nu(B_{r}({\bf
x},{\bf y})))\nu^{k}(d{\bf y})\nu^{k}(d{\bf x}),$ (4.9)

provided $n$ is large enough so that $e^{2k\nu(B_{r}({\bf x},{\bf y}))}\leq 2$
for all ${\bf x},{\bf y}\in A^{k}$.

Let $\alpha<\min(f_{0},f_{1}/2)$. Using Lemma 3.4, we have for all large
enough $n$ and all ${\bf x}\in A^{k}$, ${\bf y}\in(A\setminus B_{2r}({\bf
x}))^{k}$ that $\nu(B_{r}({\bf x},{\bf y}))\geq\nu(B_{r}({\bf
x}))+\theta\alpha r^{d}$. Hence for such $({\bf x},{\bf y})$ the integrand in
(4.9) is bounded by $h^{*}_{r}({\bf x})h^{*}_{r}({\bf y})e^{-n\nu(B_{r}({\bf
x}))}e^{-\alpha\theta nr^{d}}$. Since $\int_{A^{k}}h^{*}_{r}({\bf
y})\nu^{k}(d{\bf y})=O(r^{d(k-1)})$, and
$I_{n,k}=\frac{n^{k}}{(k-1)!}\int_{A^{k}}h^{*}_{r}({\bf x})e^{-n\nu(B_{r}({\bf
x}))}\nu^{k}(d{\bf x})$ by the multivariate Mecke formula,

$\displaystyle n^{2k-1}\int_{A^{k}}\int_{(A\setminus B_{2r}({\bf
x}))^{k}}h_{r}^{*}({\bf x})h_{r}^{*}({\bf y})e^{-n\nu(B_{r}({\bf x},{\bf
y}))}\nu^{k}(d{\bf y})\nu^{k}(d{\bf x})=O((nr^{d})^{k-1}e^{-n\theta\alpha
r^{d}}I_{n,k}).$

On the other hand, if ${\bf y}\in A^{k}\setminus(A\setminus B_{2r}({\bf
x}))^{k}$, and $h_{r}^{*}({\bf y})=1$, then ${\bf y}\in(B_{2kr}(x_{1}))^{k}$,
and hence $\int_{A^{k}\setminus(A\setminus B_{2r}({\bf x}))^{k}}h_{r}^{*}({\bf
y})\nu^{k}(d{\bf y})=O(r^{dk})$, and $\nu(B_{r}({\bf x},{\bf
y}))\geq\nu(B_{r}({\bf x}))$, so that

$\displaystyle n^{2k-1}\int_{A^{k}}\int_{A^{k}\setminus(A\setminus B_{2r}({\bf
x}))^{k}}h_{r}^{*}({\bf x})h_{r}^{*}({\bf y})e^{-n\nu(B_{r}({\bf x},{\bf
y}))}\nu^{k}(d{\bf y})\nu^{k}(d{\bf x})=O(r^{d}(nr^{d})^{k-1}I_{n,k}),$

which is $O(e^{-cnr^{d}}I_{n,k})$ for some $c>0$ by (3.1). Thus the first term
in the right hand side of (4.6) is $O(e^{-cnr^{d}}I_{n,k})$ for some $c>0$.

Now consider the second term in the right hand side of (4.6). Given $n$, for
${\bf x},{\bf y}\in(\mathbb{R}^{d})^{k}$ let $p_{\bf x}=\nu(B_{r}({\bf x}))$
and $p_{{\bf x},{\bf y}}:=\nu(B_{r}({\bf x},{\bf y}))$. By (4.7) and (4.8),

$\displaystyle\mathbb{E}[\xi_{1}\xi_{2}]-\mathbb{E}[\xi_{1}]\mathbb{E}[\xi_{2}]=\int_{A^{k}}\int_{(A\setminus
B_{2r}({\bf x}))^{k}}\left[\binom{n-2}{k-1}\binom{n-1-k}{k-1}(1-p_{\bf
x}-p_{\bf y})^{n-2k}\right.$
$\displaystyle\left.-\binom{n-1}{k-1}^{2}(1-p_{\bf x})^{n-k}(1-p_{\bf
y})^{n-k}\right]h^{*}_{r}({\bf x})h^{*}_{r}({\bf y})\nu^{k}(d{\bf
y})\nu^{k}(d{\bf x})$
$\displaystyle+\binom{n-2}{k-1}\binom{n-1-k}{k-1}\int_{A^{k}}\int_{(A\setminus
B_{r}({\bf x}))^{k}\setminus(A\setminus B_{2r}({\bf x}))^{k}}h^{*}_{r}({\bf
x})h^{*}_{r}({\bf y})(1-p_{{\bf x},{\bf y}})^{n-2k}\nu^{k}(d{\bf
y})\nu^{k}(d{\bf x})$
$\displaystyle-\binom{n-1}{k-1}^{2}\int_{A^{k}}\int_{A^{k}\setminus(A\setminus
B_{2r}({\bf x}))^{k}}h^{*}_{r}({\bf x})h^{*}_{r}({\bf y})(1-p_{\bf
x})^{n-k}(1-p_{\bf y})^{n-k}\nu^{k}(d{\bf y})\nu^{k}(d{\bf x}).$ (4.10)

Note that $p_{\bf x}\leq kf_{\rm max}\theta r^{d}$ for all ${\bf x}\in A^{k}$.
Writing $p$ for $p_{\bf x}$ and $q$ for $p_{\bf y}$, and using the fact that
as $n\to\infty$ with $k$ fixed,

$\binom{n-1}{k-1}^{2}\div\left[\binom{n-2}{k-1}\binom{n-1-k}{k-1}\right]=1+O(n^{-1}),$

we estimate the integrand in the first term in the right hand side of (4.10)
as follows:

$\displaystyle\binom{n-2}{k-1}\binom{n-1-k}{k-1}(1-p-q)^{n-2k}-\binom{n-1}{k-1}^{2}(1-p-q+pq)^{n-k}$
$\displaystyle=\binom{n-2}{k-1}\binom{n-1-k}{k-1}(1-p-q)^{n-k}\left[(1-p-q)^{-k}-(1+O(n^{-1}))\left(1+\frac{pq}{1-p-q}\right)^{n-k}\right]$
$\displaystyle\leq\frac{n^{2k-2}}{(k-1)!^{2}}\exp\left((n-k)\log(1-p-q)\right)\times[(n-k)pq+O(r^{d})+O(n^{-1})]$
$\displaystyle\leq\frac{n^{2k-1}}{(k-1)!^{2}}e^{-np}(kf_{\rm
max}\theta)^{2}r^{2d}e^{-nq}(1+o(1)).$ (4.11)

By Lemma 3.4, for all large enough $n$ and all ${\bf y}\in A^{k}$ we have
$q=p_{\bf y}\geq(f_{0}\theta/3)r^{d}$. Multiplying the expression at (4.11) by
$h^{*}_{r}({\bf x})h^{*}_{r}({\bf y})$ and integrating over ${\bf
y}\in(A\setminus B_{2r}({\bf x}))^{k}$ yields an expression bounded by

$\displaystyle
c^{\prime}n^{k}(nr^{d})^{k-1}\exp(-(f_{0}\theta/3)nr^{d})\exp(-np_{\bf
x})r^{2d}h^{*}_{r}({\bf x}),$

for some constant $c^{\prime}$ independent of $n$. Recalling
$I_{n,k}=\frac{n^{k}}{(k-1)!}\int e^{-np_{\bf x}}h^{*}_{r}({\bf
x})\nu^{k}(d{\bf x})$, we find that the absolute value of the first term in
the right hand side of (4.10), multiplied by $n^{2}$, is bounded above by

$\displaystyle
c^{\prime}(k-1)!(nr^{d})^{k+1}I_{n,k}\exp(-(f_{0}\theta/3)nr^{d})=O(I_{n,k}\exp(-(f_{0}\theta/4)nr^{d})).$

We turn to the second term in the right hand side of (4.10). By the bound
$1-t\leq e^{-t}$, for large $n$ this term, multiplied by $n^{2}$, is bounded
by

$\frac{2n^{2k}}{(k-1)!^{2}}\int_{A^{k}}\int_{(A\setminus B_{r}({\bf
x}))^{k}\setminus(A\setminus B_{2r}({\bf x}))^{k}}h_{r}^{*}({\bf
x})h_{r}^{*}({\bf y})\exp(-n\nu(B_{r}({\bf x},{\bf y})))\nu^{k}(d{\bf
x})\nu^{k}(d{\bf y}).$

By the multivariate Mecke formula, the last displayed expression equals twice
the expected number of ordered pairs $(\varphi,\psi)$ of distinct $k$-clusters
of $G({\cal P}_{n},r)$ with $\operatorname{dist}(\varphi,\psi)<2r$. Hence by a
further application of the multivariate Mecke formula, it is precisely equal
to $2J_{1,n}$, where $J_{1,n}$ was defined at (4.1). Therefore by Lemma 4.2,
the second term in the right hand side of (4.10), multiplied by $n^{2}$, is
$O(e^{-cnr^{d}}I_{n,k})$ for some $c>0$.

We turn to the last term in the right hand side of (4.10). For large enough
$n$, by Lemma 3.4 we have $p_{\bf y}\geq f_{0}(\theta/3)r^{d}$ and also
$(1-p_{\bf x})^{-k}(1-p_{\bf y})^{-k}\leq 2$ for all ${\bf x},{\bf y}\in A$.
Then

$\displaystyle n^{2+2(k-1)}\int_{A^{k}}\int_{A^{k}\setminus(A\setminus
B_{2r}({\bf x}))^{k}}h^{*}_{r}({\bf x})h^{*}_{r}({\bf y})(1-p_{\bf
x})^{n-k}(1-p_{\bf y})^{n-k}\nu^{k}(d{\bf y})\nu^{k}(d{\bf x})$
$\displaystyle\leq cn^{2k}r^{dk}\int_{A^{k}}h^{*}_{r}({\bf x})e^{-np_{\bf
x}}e^{-(f_{0}\theta/3)nr^{d}}\nu^{k}(d{\bf x})$ $\displaystyle=I_{n,k}\times
O((nr^{d})^{k}e^{-f_{0}(\theta/3)nr^{d}}),$

which is $O(I_{n,k}\exp(-(f_{0}\theta/4)nr^{d}))$. Thus there exists $c>0$
such that all terms in the right hand side of (4.10), multiplied by $n^{2}$,
are $O(e^{-cnr^{d}}I_{n,k})$. Therefore the right hand side of (4.6) is
$O(e^{-cnr^{d}}I_{n,k})$, as required. ∎

###  4.3 LLNs and concentration results for $S_{n,k}$ and $S^{\prime}_{n,k}$

A sequence of random variables $(\xi_{n})_{n\in\mathbb{N}}$ is said to
converge completely to a constant $C$ (written
$\xi_{n}\overset{c.c.}{\longrightarrow}C$) as $n\to\infty$ if
$\mathbb{P}[|\xi_{n}-C|>\varepsilon]$ is summable in $n$ for any
$\varepsilon>0$. In particular, complete convergence implies almost sure
convergence for any sequence of random variables defined on the same
probability space. We now prove
$S_{n,k}/I_{n,k}\overset{c.c.}{\longrightarrow}1$ and
$S^{\prime}_{n,k}/I_{n,k}\overset{c.c.}{\longrightarrow}1$ under an extra
condition on $r=r_{n}$, namely

$\displaystyle\limsup_{n\to\infty}(\theta nr_{n}^{d}/(\log n))<1/(2f_{0}).$
(4.12)

Using our results about $I_{n,k}$, we can then give a sequence of constants
that are almost surely asymptotic to $S_{n,k}$ (in the uniform case) or to
$\log(S_{n,k}/n)$ (in the general case).

######  Theorem 4.4 (Concentration results for $S_{n,k}$ and
$S^{\prime}_{n,k}$).

Suppose that $r=r_{n}$ satisfies (4.12) as well as (3.1). Given
$\varepsilon>0$, there exist $\delta,n_{1}\in(0,\infty)$ such that for all
$n\geq n_{1}$,

$\displaystyle\mathbb{P}[|(S_{n,k}/I_{n,k})-1|>\varepsilon]\leq\exp(-n^{\delta});$
(4.13)
$\displaystyle\mathbb{P}[|(S^{\prime}_{n,k}/I_{n,k})-1|>\varepsilon]\leq\exp(-n^{\delta}).$
(4.14)

In particular, as $n\to\infty$ we have the complete convergence
$(S_{n,k}/I_{n,k})\overset{c.c.}{\longrightarrow}1,$ and also

$\displaystyle(nr^{d})^{-1}\log(S_{n,k}/n)\overset{c.c.}{\longrightarrow}-\theta
f_{0},$ (4.15)

and likewise for $S^{\prime}_{n,k}$ (as $n\to\infty$ through $\mathbb{N}$).
Finally, in the uniform case,

$\displaystyle n^{-1}e^{f_{0}\theta
nr^{d}}(nr^{d})^{(k-1)(d-1)}S_{n,k}\overset{c.c.}{\longrightarrow}k^{-1}f_{0}^{(1-k)(d-1)}\alpha_{k},$
(4.16)

and likewise for $S^{\prime}_{n,k}$.

######  Remark 4.5.

If (3.1) holds but (4.12) does not, then as mentioned in Section 1, we still
have $S_{n,k}/I_{n,k}\overset{\mathbb{P}}{\longrightarrow}1$, and (4.15) and
(4.16) with convergence in probability.

When $f_{0}=f_{1}$, the upper bound in (3.1) is $f_{0}^{-1}\min(2/d,1)$, so
(4.12) is a stronger condition than the upper bound in (3.1) when $d\leq 3$
(but not when $d\geq 4$).

###### Proof of Theorem 4.4..

By definition $\mathbb{E}[S^{\prime}_{n,k}]=I_{n,k}$. Hence by Lemma 3.1,
given any $\varepsilon>0$ and $f_{0}^{+}>f_{0}$, for $n$ large enough,

$\displaystyle\mathbb{P}[|S^{\prime}_{n,k}-I_{n,k}|\geq\varepsilon
I_{n,k}]\leq\mathbb{P}[|S^{\prime}_{n,k}-\mathbb{E}[S^{\prime}_{n,k}]|\geq
ne^{-f_{0}^{+}\theta nr^{d}}].$

Partition $\mathbb{R}^{d}$ into cubes of side length $r$. Then the number of
$k$-clusters intersecting a fixed cube in the partition is bounded by a
constant $c^{\prime}$ depending only on $d$. Therefore, removing all the
Poisson points in any fixed cube of the partition reduces or increases the
total number of $k$-clusters by at most a constant depending only on $d$.

Enumerate the cubes in the partition that intersect $A$ as
$C_{1},...,C_{m_{n}}$, where $m_{n}=O(r^{-d})$ as $n\to\infty$. For each
$\ell\in[m_{n}]$, let $\mathcal{F}_{\ell}$ be the sigma-algebra generated by
${\cal P}_{n}\cap(\cup_{i=1}^{\ell}C_{i})$. Set
$D_{i}=\mathbb{E}[S^{\prime}_{n,k}|\mathcal{F}_{i}]-\mathbb{E}[S^{\prime}_{n,k}|\mathcal{F}_{i-1}]$
for $i\in[m_{n}]$. Then $S^{\prime}_{n,k}$ is written as the sum of martingale
differences
$S^{\prime}_{n,k}-\mathbb{E}[S^{\prime}_{n,k}]=\sum_{i=1}^{m_{n}}D_{i}$. To
see why $|D_{i}|$ is bounded from above by a finite constant, we re-sample the
Poisson points in $C_{i}$ from an independent copy ${\cal P}^{\prime}_{n}$
defined on the same probability space. By the superposition theorem [11],
recalling that $K_{k,r}({\cal X})$ is the number of $k$-clusters of $G({\cal
X},r)$, we have that

$\displaystyle D_{i}=\mathbb{E}[K_{k,r}({\cal P}_{n})-K_{k,r}(({\cal
P}^{\prime}_{n}\cap C_{i})\cup({\cal P}_{n}\setminus
C_{i}))|\mathcal{F}_{i}].$

Hence $|D_{i}|\leq 2c^{\prime}$ uniformly in $i\in[m_{n}]$, as discussed in
the last paragraph. From here, it follows easily by an application of Azuma’s
inequality [15, page 33] that for all $n$ large

$\displaystyle\mathbb{P}[|S^{\prime}_{n,k}-\mathbb{E}[S^{\prime}_{n,k}]|\geq
ne^{-nf_{0}^{+}\theta r^{d}}]$ $\displaystyle\leq
2\exp\left(-\frac{n^{2}e^{-2nf_{0}^{+}\theta
r^{d}}}{8(c^{\prime})^{2}m_{n}}\right).$

By the assumption (4.12), we may assume $f_{0}^{+}$ is chosen so that
$\limsup_{n\to\infty}n\theta f_{0}^{+}r^{d}/(\log n)<1/2$. Using this we can
find $\delta>0$ and $c>0$ such that for $n$ large, the last bound is at most
$2\exp(-c^{\prime\prime}n^{\delta})$. This gives us the result (4.14).

Now consider $S_{n,k}$ (i.e. the binomial case). By Proposition 3.2 we have
for some $c>0$ that $\mathbb{E}[S_{n,k}]=I_{n,k}(1+O(e^{-cnr^{d}})),$ and
hence for $n$ large,

$\displaystyle\mathbb{P}[|S_{n,k}-I_{n,k}|\geq\varepsilon I_{n,k}]$
$\displaystyle\leq\mathbb{P}[|S_{n,k}-\mathbb{E}[S_{n,k}]|\geq\varepsilon
I_{n,k}/2]$ $\displaystyle\leq\mathbb{P}[|S_{n,k}-\mathbb{E}[S_{n,k}]|\geq
ne^{-nf_{0}^{+}\theta r^{d}}].$

Then (4.13) can be proved in the same manner as (4.14) with the filtration now
given by $\mathcal{F}_{\ell}=\sigma(X_{i}:i\leq\ell)$ and
$D_{i}=\mathbb{E}[K_{k,r}({\cal X}_{n})-K_{k,r}({\cal
X}_{n+1}\setminus\\{X_{i}\\})|\mathcal{F}_{i}]$. We omit the details.

It is immediate from (4.13) and (4.14) that
$(S_{n,k}/I_{n,k})\overset{c.c.}{\longrightarrow}1,$ and
$(S^{\prime}_{n,k}/I_{n,k})\overset{c.c.}{\longrightarrow}1.$

For (4.15), note that since
$(S_{n,k}/I_{n,k})\overset{c.c.}{\longrightarrow}1$ and $nr^{d}\to\infty$,
$(nr^{d})^{-1}\log(S_{n,k}/I_{n,k})\overset{c.c.}{\longrightarrow}0$, and thus
by Theorem 3.5,

$(nr^{d})^{-1}\log(S_{n,k}/n)=(nr^{d})^{-1}\log(S_{n,k}/I_{n,k})+(nr^{d})^{-1}\log(I_{n,k}/n)\overset{c.c.}{\longrightarrow}-\theta
f_{0},$

which is (4.15). We obtain a similar result for $S^{\prime}_{n,k}$ using the
fact that $(S^{\prime}_{n,k}/I_{n,k})\overset{c.c.}{\longrightarrow}1$.

In the uniform case, we obtain (4.16) using (3.6). ∎

##  5 Asymptotic distribution of the $k$-cluster count

To present Poisson and normal approximation results for $S_{n,k}$ and
$S^{\prime}_{n,k}$, we recall three notions of distance which measure the
proximity between the distributions of real-valued random variables $X,Y$. The
Kolmogorov distance is defined by

$\displaystyle d_{\mathrm{K}}(X,Y):=\sup_{z\in\mathbb{R}}|\mathbb{P}[X\leq
z]-\mathbb{P}[Y\leq z]|$

The Wasserstein-1 distance is defined by

$\displaystyle
d_{\mathrm{W}}(X,Y):=\sup_{h\in\mathrm{Lip}_{1}}|\mathbb{E}[h(X)]-\mathbb{E}[h(Y)]|,$

where $\mathrm{Lip}_{1}$ denotes the family of Lipschitz continuous functions
with Lipschitz constant at most one. The total variation distance is defined
by

$\displaystyle
d_{\mathrm{TV}}(X,Y):=\sup_{A\in\mathcal{B}(\mathbb{R})}|\mathbb{P}[X\in
A]-\mathbb{P}[Y\in A]|,$

where the supremum is taken over all Borel measurable subsets of $\mathbb{R}$.
If $X,Y$ both take values in $\mathbb{Z}$, then this is the same as
$(1/2)\sum_{n\in\mathbb{Z}}|\mathbb{P}[X=n]-\mathbb{P}[Y=n]|$. Convergence in
any of the three aforementioned distances implies convergence in distribution.

In this section we prove the following result, concerning the asymptotic
distributions of $S_{n,k}$ (the number of $k$-clusters in $G({\cal X}_{n},r)$)
and $S^{\prime}_{n,k}$ (the number of $k$-clusters in $G({\cal P}_{n},r)$), in
the mildly dense regime. Recall from (3.3) that
$\mathbb{E}[S^{\prime}_{n,k}]=I_{n,k}$. Recall that $Z_{t}$ denotes a Poisson
variable with mean $t$, and let $\mathcal{N}$ denote a standard normal random
variable.

######  Theorem 5.1 (Distributional results on the $k$-cluster count).

Suppose that $r=r(n)$ satisfies (3.1), and set
$b:=\limsup_{n\to\infty}(n\theta r^{d}/\log n)$. Let $k\in\mathbb{N}$. There
exists a finite $c>0$ such that for all large enough $n$,

$\displaystyle d_{\mathrm{TV}}(S^{\prime}_{n,k},Z_{I_{n,k}})\leq
e^{-cnr^{d}},$ (5.1)

and if $d\geq 2$ then for all large enough $n$,

$\displaystyle d_{\mathrm{TV}}(S_{n,k},Z_{\mathbb{E}[S_{n,k}]})\leq
e^{-cnr^{d}},$ (5.2)

Moreover (for all $d$), given $\varepsilon>0$ we have

$\displaystyle
d_{\mathrm{K}}(\mathbb{V}\mathrm{ar}[S^{\prime}_{n,k}]^{-1/2}(S^{\prime}_{n,k}-I_{n,k}),\mathcal{N})=O(n^{\varepsilon+(bf_{0}-1)/2});$
(5.3)

and

$\displaystyle
d_{\mathrm{W}}(\mathbb{V}\mathrm{ar}[S_{n,k}]^{-1/2}(S_{n,k}-\mathbb{E}[S_{n,k}]),\mathcal{N})=O(n^{\varepsilon+(3bf_{0}-1)/2}),$
(5.4)

Also if $d\geq 2$ then there exists $c>0$ such that for all large enough $n$,

$\displaystyle
d_{\mathrm{K}}(\mathbb{V}\mathrm{ar}[S_{n,k}]^{-1/2}(S_{n,k}-\mathbb{E}[S_{n,k}]),\mathcal{N})\leq
e^{-cnr^{d}},$ (5.5)

and a similar result holds for $S^{\prime}_{n,k}$ for all $d\geq 1$.

######  Remark 5.2.

  1. 1.

The normal approximation (5.5) (and the corresponding result for
$S^{\prime}_{n,k}$) will be proved via Poisson approximation, while (5.3) and
(5.4) will be obtained by approximating $S_{n,k}$ or $S^{\prime}_{n,k}$ by
directly by a normal random variable. It is of interest to compare the rates
of normal convergence in these results with one another.

When $b=0$, the rates are better in (5.3) and (5.4) than in (5.5) since
$e^{-cnr^{d}}$ decays more slowly than $n^{-\varepsilon}$ for any
$\varepsilon>0$. To fully compare when $b>0$, we would need to optimize the
value of $c$ in (5.5), which is beyond the scope of this paper.

  2. 2.

We conjecture that the rates in (5.3), and in (5.4) for $b=0$, are optimal up
to a factor of $n^{\varepsilon}$. When $b>0$ the rate of convergence given for
$S_{n,k}$ in (5.4) is worse than the rate given for $S^{\prime}_{n,k}$ in
(5.3). We expect that in this case the rate in (5.4) is sub-optimal.

  3. 3.

When $bf_{0}\geq 1/3$, (5.4) does not give a CLT for $S_{n,k}$ at all.
However, provided $d\geq 2$ and (3.1) holds (which amounts to $bf_{0}<2/d$
when $f_{0}=f_{1}$), we do still have a CLT for $S_{n,k}$ (possibly with a
sub-optimal rate of convergence) by (5.5).

  4. 4.

In (5.4) we found it more convenient to use use $d_{\mathrm{W}}$ rather than
$d_{\mathrm{K}}$. The proof of (5.4) is based on a general result on normal
approximation (in $d_{\mathrm{W}}$) for stabilizing functionals of binomial
point processes (Lemma 5.12) which is itself based on a result in [6]. It
might be possible to obtain a similar result with $d_{\mathrm{K}}$ instead of
$d_{\mathrm{W}}$ by utilizing [10] instead of [6].

  5. 5.

A result along the lines of (5.3) (without any rate of convergence) is proved
in [17] for a class of soft RGGs where the probability of two vertices being
connected given their locations at $x,y$ say, is some function of $x$ and $y$
(called the connection function), rather than being $\mathbbm{1}\\{\|y-x\|\leq
r\\}$ as in the graphs considered here. However, the result in [17] requires
the connection function to be bounded away from 1, so the result there does
not cover the RGGs that we consider here.

###  5.1 Poisson approximation for $S^{\prime}_{n,k}$

Let $\mathbf{N}(\mathbb{R}^{d})$ be the space of all finite subsets of
$\mathbb{R}^{d}$, equipped with the smallest $\sigma$-algebra ${\cal
S}(\mathbb{R}^{d})$ containing the sets $\\{{\cal
X}\in\mathbf{N}(\mathbb{R}^{d}):|{\cal X}\cap B|=m\\}$ for all Borel
$B\subset\mathbb{R}^{d}$ and all $m\in\mathbb{N}\cup\\{0\\}$. Given
$m\in\mathbb{N}$, let $\mathbf{N}_{m}(\mathbb{R}^{d}):=\\{{\cal
X}\in\mathbf{N}(\mathbb{R}^{d}):|{\cal X}|=m\\}$.

Our main tool for proving the Poisson approximation result (5.1) in Theorem
5.1 is the following coupling bound in [17] adapted to our situation (i.e.
without marking). The function $g$ in the next result has nothing to do with
the $g$ in Section 2.

######  Lemma 5.3 ([17, Theorem 3.1]).

Let
$g:\mathbf{N}_{k}(\mathbb{R}^{d})\times\mathbf{N}(\mathbb{R}^{d})\to\\{0,1\\}$
be measurable. Define

$\displaystyle W:=F({\cal P}_{n}):=\sum_{\psi\subset{\cal
P}_{n},|\psi|=k}g(\psi,{\cal P}_{n}\setminus\psi).$

Let $n>0,k\in\mathbb{N}$. For ${\bf
x}=(x_{1},...,x_{k})\in(\mathbb{R}^{d})^{k}$ with distinct entries, set
$p({\bf x}):=\mathbb{E}[g(\\{x_{1},\ldots,x_{k}\\},{\cal P}_{n})]$ and set
$\mu=n\nu$. Assume that for $\mu^{k}$-a.e. ${\bf x}$ with $p({\bf x})>0$, we
can find coupled random variables $U_{\bf x},V_{\bf x}$ such that

  * •

$\mathscr{L}(U_{\bf x})=\mathscr{L}(W)$;

  * •

$\mathscr{L}(1+V_{\bf x})=\mathscr{L}(F({\cal
P}_{n}\cup\\{x_{1},...,x_{k}\\})|g(\\{x_{1},\ldots,x_{k}\\},{\cal P}_{n})=1)$.

Then

$\displaystyle
d_{\mathrm{TV}}(W,Z_{\mathbb{E}[W]})\leq\frac{\min(1,\mathbb{E}[W]^{-1})}{k!}\int\mathbb{E}[|U_{\bf
x}-V_{\bf x}|]p({\bf x})\mu^{k}(d{\bf x}).$ (5.6)

We restate the first Poisson approximation result (5.1) from Theorem 5.1 in
the following proposition. Recall that $Z_{t}$ denotes a Poisson variable with
mean $t$.

######  Proposition 5.4.

Let $k\in\mathbb{N}$. Then there exist finite constants $c,n_{0}>0$ such that

$d_{\mathrm{TV}}(S^{\prime}_{n,k},Z_{I_{n,k}}))\leq
e^{-cnr^{d}},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\leavevmode\nobreak\ n\geq
n_{0}.$

###### Proof.

In view of (3.2), we apply Lemma 5.3 with

$g(\psi,\varphi):=h_{r}(\psi)\mathbbm{1}\\{\varphi\cap
B_{r}(\psi)=\varnothing\\}.$

For ${\bf x}\in(\mathbb{R}^{d})^{k}$, with $h_{r}({\bf x})=1$, we construct
coupled random variables $(U_{\bf x},V_{\bf x})$ as follows. Define $U_{\bf
x}:=\sum_{\varphi\subset{\cal P}_{n},|\varphi|=k}g(\varphi,{\cal
P}_{n}\setminus\varphi)$, and

$\displaystyle V_{\bf x}:=\sum_{\varphi\subset{\cal P}_{n}\setminus B_{r}({\bf
x}),|\varphi|=k}g(\varphi,{\cal P}_{n}\setminus B_{r}({\bf
x})\setminus\varphi).$

This coupling satisfies the distributional requirement because the conditional
distribution of ${\cal P}_{n}$ given the event $\\{g({\bf x},{\cal
P}_{n})=1\\}$ is the same as the distribution of ${\cal P}_{n}\setminus
B_{r}({\bf x})$.

There are two sources of contribution to the change $U_{\bf x}-V_{\bf x}$ of
$k$-cluster counts after removing all the Poisson points in $B_{r}({\bf x})$.
First, after removal, all $k$-clusters of $G({\cal P}_{n},r)$ that were
originally intersecting $B_{r}({\bf x})$ are destroyed, therefore reducing the
$k$-cluster count. Second, every $k$-set $\varphi\subset{\cal P}_{n}\setminus
B_{r}({\bf x})$ satisfying the two properties

  * (a)

$g(\varphi,{\cal P}_{n}\setminus B_{r}({\bf x})\setminus\varphi)=1$;

  * (b)

${\cal P}_{n}(B_{r}({\bf x})\cap B_{r}(\varphi))\geq 1$;

becomes a $k$-cluster _only_ after removing all the Poisson points in
$B_{r}({\bf x})$, thereby increasing the number of $k$-clusters. Let
$\xi_{1}({\bf x})$ denote the number of $k$-clusters of $G({\cal P}_{n},r)$
that intersect $B_{r}({\bf x})$ and let $\xi_{2}({\bf x})$ denote the number
of $k$-subsets $\varphi$ of ${\cal P}_{n}\setminus B_{r}({\bf x})$ satisfying
property (a) and property (c) $B_{r}(\varphi)\cap B_{r}({\bf
x})\neq\varnothing$. It is clear that (b) implies (c) and

$\displaystyle|U_{\bf x}-V_{\bf x}|\leq\xi_{1}({\bf x})+\xi_{2}({\bf x}).$
(5.7)

We estimate $\mathbb{E}[\xi_{1}({\bf x})]$ and $\mathbb{E}[\xi_{2}({\bf x})]$
separately. Since

$\xi_{1}({\bf x})=\sum_{\varphi\subset{\cal P}_{n}:|\varphi|=k,\varphi\cap
B_{r}({\bf x})\neq\varnothing}h_{r}(\varphi)\mathbbm{1}\\{({\cal
P}_{n}\setminus\varphi)\cap B_{r}(\varphi)=\varnothing\\},$

applying the multivariate Mecke equation leads to

$\mathbb{E}[\xi_{1}({\bf x})]=\frac{1}{k!}\int_{A^{k}\setminus(A\setminus
B_{r}({\bf x}))^{k}}h_{r}({\bf y})e^{-n\nu(B_{r}({\bf y}))}(n\nu)^{k}(d{\bf
y}).$

If ${\bf y}\in A^{k}\setminus(A\setminus B_{r}({\bf x}))^{k}$ and $h_{r}({\bf
y})=1$ then ${\bf y}\subset B_{kr}({\bf x})^{k}$. Moreover by Lemma 3.4, if
$n$ is large enough then $\nu(B_{r}({\bf y}))\geq f_{0}(\theta/3)r^{d}$ for
any ${\bf y}\in A^{k}$. Hence for all $n$ large enough and all ${\bf x}$,

$\mathbb{E}[\xi_{1}({\bf x})]\leq\frac{n^{k}}{k!}(k\theta(kr)^{d}f_{\rm
max})^{k}e^{-f_{0}(\theta/3)nr^{d}}.$

Therefore setting
$p((x_{1},\ldots,x_{k}))=\mathbb{E}[g(\\{x_{1},\ldots,x_{k}\\},{\cal
P}_{n})]$, and using (3.3), we have

$\displaystyle\int_{A^{k}}\mathbb{E}[\xi_{1}({\bf x})]p({\bf
x})(n\nu)^{k}(d{\bf x})$ $\displaystyle\leq(f_{\rm max}\theta
k^{d+1})^{k}(nr^{d})^{k}e^{-(\theta/3)f_{0}nr^{d}}(\frac{n^{k}}{k!})\int_{A^{k}}p({\bf
x})\nu^{k}(d{\bf x})$ $\displaystyle=(f_{\rm max}\theta
k^{d+1})^{k}(nr^{d})^{k}e^{-(\theta/3)f_{0}nr^{d}}I_{n,k}.$ (5.8)

Set $\gamma({\bf x},{\bf y})=\mathbbm{1}\\{r<\operatorname{dist}({\bf x},{\bf
y})\leq 2r\\}$. By the multivariate Mecke equation

$\displaystyle\mathbb{E}[\xi_{2}({\bf x})]$
$\displaystyle=\frac{n^{k}}{k!}\int_{A^{k}}h_{r}({\bf y})\gamma({\bf x},{\bf
y})e^{-n\nu(B_{r}({\bf y})\setminus B_{r}({\bf x}))}\nu^{k}(d{\bf y}),$

and therefore writing $B_{r}({\bf x},{\bf y})$ for $B_{r}({\bf x})\cup
B_{r}({\bf y})$, we have that

$\displaystyle\int_{A^{k}}\mathbb{E}[\xi_{2}({\bf x})]p({\bf
x})(n\nu)^{k}(d{\bf x})=\frac{n^{2k}}{k!}\int_{A^{k}}\int_{A^{k}}h_{r}({\bf
x})h_{r}({\bf y})\gamma({\bf x},{\bf y})e^{-n\nu(B_{r}({\bf x},{\bf
y}))}\nu^{k}(d{\bf y})\nu^{k}(d{\bf x}).$

By (4.1) this expression is equal to $k!J_{1,n}$, and therefore by Lemma 4.2
it is $O(e^{-c^{\prime}nr^{d}}I_{n,k})$ for some $c^{\prime}>0$.

Combining this with (5.8), and using (5.7), we obtain for suitable $c>0$ that

$\int_{A^{k}}|U_{{\bf x}}-V_{{\bf x}}|p({\bf x})(n\nu)^{k}(d{\bf
x})=O(e^{-cnr^{d}}I_{n,k}).$

Applying Lemma 5.3 with the present choice of $g$ (so that the $W$ of that
result is $S^{\prime}_{n,k}$) gives the desired bound in Poisson
approximation, completing the proof. ∎

###  5.2 Poisson approximation for $S_{n,k}$

For Poisson approximation in the binomial setting, i.e. for $S_{n,k}$, we use
the following result from [12, Theorem II.24.3] or [4, Theorem 1.B].

######  Lemma 5.5.

Let $n\in\mathbb{N}$. Suppose $Y_{1},\ldots,Y_{n}$ are Bernoulli random
variables on a common probability space. Set $W:=\sum_{i=1}^{n}Y_{i}$, and
$p_{i}:=\mathbb{E}[Y_{i}]$ for $i\in[n]$. Suppose for each $i\in[n]$ that
there exist coupled random variables $U_{i},V_{i}$ such that
$\mathscr{L}(U_{i})=\mathscr{L}(W)$ and
$\mathscr{L}(1+V_{i})=\mathscr{L}(W|Y_{i}=1)$. Then

$d_{\mathrm{TV}}(W,Z_{\mathbb{E}[W]})\leq(\min(1,1/\mathbb{E}[W]))\sum_{i=1}^{n}p_{i}\mathbb{E}[|U_{i}-V_{i}|].$

We use this to obtain the analogue of Proposition 5.4 in the binomial setting,
i.e. the second Poisson approximation result (5.2) in Theorem 5.1:

######  Proposition 5.6.

Suppose $d\geq 2$. Let $k\in\mathbb{N}$. There exist $c>0$,
$n_{0}\in(0,\infty)$ such that

$d_{\mathrm{TV}}(S_{n,k},Z_{\mathbb{E}[S_{n,k}]})\leq
e^{-cnr^{d}},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\forall\leavevmode\nobreak\ n\geq n_{0}.$

We shall prove this in stages. To apply Lemma 5.5 to $S_{n,k}$, we let $Y_{i}$
be the indicator of the event that $|{\cal C}_{r}(X_{i},{\cal X}_{n})|=k$ and
$X_{i}$ is the left-most point of ${\cal C}_{r}(X_{i},{\cal X}_{n})$ (we
called this $\xi_{i}$ at (4.5)). Then $S_{n,k}=\sum_{i=1}^{n}Y_{i}$.

We need to define $U_{i}$, $V_{i}$ for each $i\in[n]$ so that
$\mathscr{L}(U_{i})=\mathscr{L}(S_{n,k})$, and
$\mathscr{L}(1+V_{i})=\mathscr{L}(S_{n,k}|Y_{i}=1)$, and so that we can find a
good bound for $\mathbb{E}[|U_{i}-V_{i}|]$. We do this for $i=1$ as follows.
First define the event

$\mathscr{E}:=\\{Y_{1}=1\\}\cap\\{{\cal C}_{r}(X_{1},{\cal
X}_{n})=\\{X_{1},\ldots,X_{k}\\}\\}.$

Let $(\tilde{X}_{1},\ldots,\tilde{X}_{k})$ be a random vector in
$(\mathbb{R}^{d})^{k}$ with
$\mathscr{L}(\tilde{X}_{1},\ldots,\tilde{X}_{k})=\mathscr{L}((X_{1},\ldots,X_{k})|\mathscr{E})$.
Also let $(X_{i,j},i\in[n],j\in\mathbb{N})$ be an array of independent
$\nu$-distributed random variables, independent of
$(\tilde{X}_{1},\ldots,\tilde{X}_{k})$. Set ${\cal
X}_{n,1}=\\{X_{1,1},\ldots,X_{n,1}\\}$.

For $k<i\leq n$ set
$J_{i}=\min\\{j:X_{i,j}\notin\cup_{\ell=1}^{k}B_{r}(\tilde{X}_{\ell})\\}$ and
set $\tilde{X}_{i}:=X_{i,J_{i}}$. Then set ${\cal
X}_{n,2}:=\\{\tilde{X}_{1},\ldots,\tilde{X}_{n}\\}$.

In other words, we sample the random vector
$(\tilde{X}_{1},\ldots,\tilde{X}_{k})$ from the conditional distribution of
$(X_{1},\ldots,X_{k})$ given that $\mathscr{E}$ occurs, independently of
${\cal X}_{n,1}$. Given the outcome of $\tilde{X}_{1},\ldots,\tilde{X}_{k}$,
for $i\in[n]\setminus[k]$, if
$X_{i,1}\notin\cup_{\ell=1}^{k}B_{r}(\tilde{X}_{\ell})$ we take
$\tilde{X}_{i}=X_{i,1}$. Otherwise we re-sample a random vector with
distribution $\nu$ repeatedly until we get a value that is not in
$\cup_{\ell=1}^{k}B_{r}(\tilde{X}_{\ell})$, and call this $\tilde{X}_{i}$.
Thus, given the value of $(\tilde{X}_{1},\dots,\tilde{X}_{k})$, the
distribution of $\tilde{X}_{i}$ is given by the measure $\nu$ restricted to
$A\setminus\cup_{\ell=1}^{k}B_{r}(\tilde{X}_{\ell})$, normalised to a
probability measure.

Set $U_{1}:=K_{k,r}({\cal X}_{n,1})$, and $V_{1}:=K_{k,r}({\cal X}_{n,2})-1$.
Note that in this coupling we make no attempt to make a ‘good’ coupling of
$(\tilde{X}_{1},\ldots,\tilde{X}_{k})$ to $(X_{1,1},\ldots,X_{k,1})$. However,
for $k+1\leq i\leq n$ the variables $\tilde{X}_{i}$, are the same as $X_{i,1}$
except in those rare cases where $X_{i,1}$ lies in
$B_{r}((\tilde{X}_{1},\ldots,\tilde{X}_{k}))$. This is what makes the coupling
effective. Clearly $\mathscr{L}(U_{1})=\mathscr{L}(S_{n,k})$.

######  Lemma 5.7.

With $V_{1}$ as just defined,
$\mathscr{L}(1+V_{1})=\mathscr{L}(S_{n,k}|Y_{1}=1)$.

###### Proof.

Given $Y_{1}=1$, we have that ${\cal C}_{r}(X_{1},{\cal X}_{n})$ has $k$
vertices with $X_{1}$ the left-most of these, and by exchangeability we can
assume the other vertices of ${\cal C}_{r}(X_{1},{\cal X}_{n})$ are
$X_{2},\ldots,X_{k}$ without affecting the distribution of the point process
${\cal X}_{n}$. In other words, we have $\mathscr{L}({\cal
X}_{n}|Y_{1}=1)=\mathscr{L}({\cal X}_{n}|\mathscr{E}).$ Moreover, we claim
that

$\displaystyle\mathscr{L}((\tilde{X}_{1},\ldots,\tilde{X}_{n}))=\mathscr{L}((X_{1},\ldots,X_{n})|\mathscr{E}).$
(5.9)

This implies that
$\mathscr{L}(\\{\tilde{X}_{1},\ldots,\tilde{X}_{n}\\})=\mathscr{L}({\cal
X}_{n}|\mathscr{E})=\mathscr{L}({\cal X}_{n}|Y_{1}=1),$ and hence
$\mathscr{L}(1+V_{1})=\mathscr{L}(K_{k,r}(\\{\tilde{X}_{1},\ldots,\tilde{X}_{n}\\}))=\mathscr{L}(S_{n,k}|Y_{1}=1)$,
as required.

It remains to confirm the claim (5.9). The reader may think this is obvious;
we provide a sketch proof. For ${\bf
x}=(x_{1},\ldots,x_{n})\in(\mathbb{R}^{d})^{n}$, let us set ${\bf
x}_{1}^{k}:=(x_{1},\ldots,x_{k})$, ${\bf x}_{k+1}^{n}:=(x_{k+1},\ldots,x_{n})$
and $g_{r}({\bf x}_{1}^{k},{\bf
x}_{k+1}^{n}):=\prod_{\ell=k+1}^{n}\mathbbm{1}\\{x_{\ell}\notin B_{r}({\bf
x}_{1}^{k})\\}$. Then with $h_{r}^{*}$ defined just after (1.7),

$\displaystyle\mathbb{P}[(X_{1},\ldots,X_{n})\in d{\bf
x};\mathscr{E}]=h_{r}^{*}({\bf x}_{1}^{k})g_{r}({\bf x}_{1}^{k},{\bf
x}_{k+1}^{n})\nu^{n}(d{\bf x}),$ (5.10)

so that $\mathbb{P}(\mathscr{E})=\int_{A^{n}}h_{r}^{*}({\bf
x}_{1}^{k})g_{r}({\bf x}_{1}^{k},{\bf x}_{k+1}^{n})\nu^{n}(d{\bf x})$. For
${\bf x}_{1}^{k}\in(\mathbb{R}^{d})^{k}$, let us set $I({\bf
x}_{1}^{k}):=\int_{(\mathbb{R}^{d})^{n-k}}g_{r}({\bf x}_{1}^{k},{\bf
x}_{k+1}^{n})\nu^{n-k}(d{\bf x}_{k+1}^{n}).$ Then by (5.10),

$\displaystyle\mathbb{P}[(\tilde{X}_{1},\ldots,\tilde{X}_{k})\in d{\bf
x}_{1}^{k}]$ $\displaystyle=\mathbb{P}[(X_{1},\ldots,X_{k})\in d{\bf
x}_{1}^{k}|\mathscr{E}]=\frac{h^{*}_{r}({\bf x}_{1}^{k})I({\bf
x}_{1}^{k})\nu^{k}(d{\bf x}_{1}^{k})}{\int_{A^{n}}h_{r}^{*}({\bf
x}_{1}^{k})g_{r}({\bf x}_{1}^{k},{\bf x}_{k+1}^{n})\nu^{n}(d{\bf x})}.$

Then

$\displaystyle\mathbb{P}[(\tilde{X}_{1},\ldots,\tilde{X}_{n})\in d{\bf x}]$
$\displaystyle=\frac{g_{r}({\bf x}_{1}^{k},{\bf x}_{k+1}^{n})\nu^{n-k}(d{\bf
x}_{k+1}^{n})}{I({\bf
x}_{1}^{k})}\times\mathbb{P}[(\tilde{X}_{1},\ldots\tilde{X}_{k})\in d{\bf
x}_{1}^{k}]$ $\displaystyle=\frac{h^{*}_{r}({\bf x}_{1}^{k})g_{r}({\bf
x}_{1}^{k},{\bf x}_{k+1}^{n})\nu^{n}(d({\bf x}_{1}^{k},{\bf
x}_{k+1}^{n}))}{\int_{A^{n}}h_{r}^{*}({\bf x}_{1}^{k})g_{r}({\bf
x}_{1}^{k},{\bf x}_{k+1}^{n})\nu^{n}(d{\bf x})}$
$\displaystyle=\mathbb{P}[(X_{1},\ldots,X_{n})\in d{\bf x}|\mathscr{E}],$

where the last line comes from (5.10). Thus we have (5.9). ∎

###### Proof of Proposition 5.6.

We need to find a useful bound on $\mathbb{E}[|U_{1}-V_{1}|]$. Note that the
‘new’ point process
$\mathcal{X}_{n,2}=\\{\tilde{X}_{1},\ldots\tilde{X}_{n}\\}$ is obtained from
the ‘old’ point process ${\cal X}_{n,1}$ by replacing the points
$X_{1,1},\ldots,X_{k,1}$ with $\tilde{X}_{1},\ldots,\tilde{X}_{k}$ and also,
for those $i\in[n]\setminus[k]$ such that $J_{i}>1$, replacing the point
$X_{i,1}$ with $\tilde{X}_{i}$, leaving the other points unchanged.

We refer to vertices and components (here also called clusters) of $G({\cal
X}_{n,1},r)$ as being old while vertices and clusters of $G({\cal X}_{n,2},r)$
are new. We write $\tilde{{\cal C}}$ for
$\\{\tilde{X}_{1},\ldots,\tilde{X}_{k}\\}$. By construction $\tilde{{\cal C}}$
is a cluster of $G({\cal X}_{n,2},r)$.

The value of $|U_{1}-V_{1}|$ is bounded by the sum of the following variables
$N_{i},1\leq i\leq 6$.

$N_{1}$ is the number of old $k$-clusters involving $X_{1,1},\ldots,X_{k,1}$,
and $N_{2}$ is the number of new $k$-clusters within distance $r$ of one of
$X_{1,1},\ldots,X_{k,1}$ but not using any of the new vertices $\tilde{X}_{i}$
with $i>k,J_{i}>1$, and with no vertex in $B_{2r}(\tilde{{\cal C}})$. These
will be affected by removing $X_{i,1}$ for $1\leq i\leq k$.

$N_{3}$ is the number of old $k$-clusters intersecting $B_{r}(\tilde{X}_{i})$
for some $i\in[n]\setminus[k]$ with $J_{i}>1$, and not using $X_{i,1}$ (if
such a cluster does use $X_{i,1}$ it is included in $N_{5}$ below). $N_{4}$ is
the number of new $k$-clusters involving $\tilde{X}_{i}$ for some $i>k$ with
$J_{i}>1$, and having no vertex in $B_{2r}(\tilde{{\cal C}})$. These are
affected by the creation of new vertices at $\tilde{X}_{i}$ with
$i>k,J_{i}>1$.

$N_{5}$ is the number of old $k$-clusters having at least one vertex in
$B_{r}(\tilde{{\cal C}})$. These clusters are affected by the removal of old
vertices in $B_{r}(\tilde{{\cal C}})$.

$N_{6}$ is the number of new $k$-clusters having at least one vertex in
$B_{2r}(\tilde{{\cal C}})$, other than $\tilde{{\cal C}}$ itself. These could
be created from previously larger clusters due to the removal of old vertices
in $B_{r}(\tilde{{\cal C}})$.

We estimate $\mathbb{E}[N_{i}]$ for each $i\in[6]$, repeatedly using the fact
that $\nu(B_{s}(x))\geq(\theta/3)f_{0}s^{d}$ for all small enough $s>0$ and
all $x\in A$ by Lemma 3.4. We have for large enough $n$ that

$\displaystyle\mathbb{E}[N_{1}]$ $\displaystyle\leq
k\binom{n-1}{k-1}\int_{A^{k}}h_{r}({\bf x})(1-\nu(B_{r}({\bf
x})))^{n-k}\nu^{k}(d{\bf x})$ $\displaystyle\leq 2kn^{k-1}(f_{\rm
max}\theta((k-1)r)^{d})^{k-1}\exp(-f_{0}(\theta/3)nr^{d}),$

and writing $h_{r}(x,{\bf x})$ for $h_{r}((x,{\bf x}))$, we have

$\displaystyle\mathbb{E}[N_{2}]$ $\displaystyle\leq
k\binom{n-k}{k}\int_{A}\int_{A^{k}}h_{r}(x,{\bf x})(1-\nu(B_{r}({\bf
x})))^{n-2k}\nu^{k}(d{\bf x})\nu(dx)$ $\displaystyle\leq 2n^{k}(f_{\rm
max}\theta(kr)^{d})^{k}\exp(-f_{0}(\theta/3)nr^{d}).$

Using the fact that $\mathbb{P}[J_{i}>1]\leq kf_{\rm max}\theta r^{d}$ for
$i>k$, and the point process ${\cal X}_{n,1}\setminus\\{X_{i,1}\\}$ is
independent of the event $\\{J_{i}>1\\}$ and the random vector
$\tilde{X}_{i}$, we obtain that

$\displaystyle\mathbb{E}[N_{3}]$ $\displaystyle\leq(n-k)(kf_{\rm max}\theta
r^{d})\binom{n-1}{k}\sup_{x\in A}\int_{A^{k}}h_{r}(x,{\bf x})(1-\nu(B_{r}({\bf
x})))^{n-1-k}\nu^{k}(d{\bf x})$ $\displaystyle\leq
c(nr^{d})^{k+1}\exp(-f_{0}(\theta/3)nr^{d}).$

Using the same bound on $\mathbb{P}[J_{i}>1]$ and the fact that for
$i\in[n]\setminus[k]$ the distribution of ${\cal
X}_{n,2}\setminus\\{\tilde{X}_{1},\ldots,\tilde{X}_{k},\tilde{X}_{i}\\},$
given $(\tilde{X}_{1},\ldots,\tilde{X}_{k},\tilde{X}_{i})$ is that of a sample
of size $n-k-1$ from the restriction of $\nu$ to
$A\setminus\cup_{\ell=1}^{k}\tilde{X}_{\ell}$ normalized to be a probability
measure, we have that

$\displaystyle\mathbb{E}[N_{4}]$ $\displaystyle\leq(n-k)(kf_{\rm max}\theta
r^{d})\binom{n-k-1}{k-1}\sup_{x\in A}\left\\{(2f_{\rm
max}\theta(kr)^{d})^{k-1}(1-\nu(B_{r}(x)))^{n-2k}\right\\}$ $\displaystyle\leq
c(nr^{d})^{k}\exp(-f_{0}(\theta/3)nr^{d}).$

Next,

$\displaystyle\mathbb{E}[N_{5}]$ $\displaystyle\leq nkf_{\rm max}\theta
r^{d}\binom{n-1}{k-1}\sup_{x\in A}\int_{A^{k-1}}h_{r}(x,{\bf
x})(1-\nu(B_{r}(x,{\bf x})))^{n-k}\nu^{k-1}(d{\bf x})$ $\displaystyle\leq
c(nr^{d})^{k}\exp(-f_{0}(\theta/3)nr^{d}).$

We give an estimate for $\mathbb{E}[N_{6}]$ in Lemma 5.8 below. Combining this
with the earlier estimates for $N_{1},\ldots,N_{5}$, we obtain that there
exists $\varepsilon>0$ that

$\mathbb{E}[|U_{1}-V_{1}|]=O(\exp(-\varepsilon nr^{d})).$

By the exchangeability of $X_{1},\ldots,X_{n}$, we can construct $U_{i},V_{i}$
similarly for each $i\in[n]$, with the same bound for
$\mathbb{E}[|U_{i}-V_{i}|]$. Also we know $\mathbb{E}[S_{n,k}]\to\infty$ as
$n\to\infty$ by Proposition 3.2 and Lemma 3.1. Then by Lemma 5.5 (with the $W$
of that result equal to our $S_{n,k}$) we obtain for $n$ large enough that

$\displaystyle d_{\mathrm{TV}}(S_{n,k},Z_{\mathbb{E}[S_{n,k}]})$
$\displaystyle\leq(\mathbb{E}[S_{n,k}])^{-1}\sum_{i=1}^{n}\mathbb{E}[Y_{i}]\times
O(\exp(-n\varepsilon r^{d}))=O(\exp(-n\varepsilon r^{d})),$

as required. ∎

######  Lemma 5.8.

Suppose $d\geq 2$. Let $N_{6}$ be the number of $k$-clusters of $G({\cal
X}_{n,2},r)$ within distance $2r$ of
$\\{\tilde{X}_{1},\ldots,\tilde{X}_{k}\\}$, other than
$\\{\tilde{X}_{1},\ldots,\tilde{X}_{k}\\}$ itself. Then there exists a
constant $c>0$ such that $\mathbb{E}[N_{6}]=O(\exp(-cnr^{d}))$ as
$n\to\infty$.

It is harder to find a good upper bound for $\mathbb{E}[N_{6}]$ than for
$\mathbb{E}[N_{i}],1\leq i\leq 5$. The main problem is that for fairly large
$k$ (for example, $k=12$ for $d=2$) there can be a configuration of
$\\{\tilde{X}_{1},\ldots,\tilde{X}_{k}\\}$ such that the union of balls of
radius $r$ centred on these points surrounds a very small (but non-empty)
region. To deal with this, we verify that this eventuality is very unlikely
because of the compression phenomenon mentioned before: given small but fixed
$\delta_{1}>0$, a $k$-cluster is very likely to be compressed within a small
ball of radius $\delta_{1}r$, and if this happens the kind of possibility just
mentioned cannot happen. We can deal with the probability of non-compressed
$k$-clusters by other means.

The proof of Lemma 5.8 uses the following geometrical lemma. The lemma fails
when $d=1$, and is the reason for the restriction to $d\geq 2$ in the
statement of Proposition 5.6. It may be possible to prove Lemma 5.8, and hence
Proposition 5.6, by other means when $d=1$.

######  Lemma 5.9.

Suppose $d\geq 2$. There exists a constant $\delta_{1}>0$ such that we have
for all small enough $s>0$ that

$\displaystyle{\rm Vol}(B_{s}(y)\cap A\setminus
B_{(1+\delta_{1})s}(x))\geq\delta_{1}s^{d},\leavevmode\nobreak\
\leavevmode\nobreak\ \forall\leavevmode\nobreak\ x\in A,y\in A\setminus
B_{s}(x).$ (5.11)

###### Proof.

Suppose $\delta_{1}<1/4$. If $x\in A,y\in A^{(s)}\setminus B_{s}(x)$ then the
set $B_{s}(y)\setminus B_{(1+\delta_{1})s}(x)$ contains a ball of radius
$s/4$, and is contained in $A$, so that ${\rm Vol}(B_{s}(y)\cap A\setminus
B_{(1+\delta_{1})s}(x))\geq\theta(s/4)^{d}$.

.$y$$x$.$\partial A$ Figure 3: Illustration for the proof of Lemma 5.9. The
small circle represents $B_{\delta_{2}s}(z)$. The larger segment represents
$B^{*}(y,s,\delta_{2},e(y))$.

As discussed in the proof of Lemma 3.4, $\partial A$ is a $(d-1)$-dimensional
$C^{2}$ submanifold of $\mathbb{R}^{d}$. Let $\delta_{2}=0.01$. Using [15,
Lemma 5.5] and a compactness argument, as in the proof of [15, Lemma 5.7], we
can find $s_{0}>0$ such that for all $s\in(0,s_{0}]$ and all $y\in A\setminus
A^{(s)}$ we can find a unit vector $e(y)$ such that
$B^{*}(y;s,\delta_{2},e(y))\subset A$. The set $B^{*}(y;s,\eta,e)$ is as
defined at [15, P98], namely, it is the set of $y\in B(x,r)$ such that
$\langle(y-x),e\rangle>\eta r$, where $\langle\cdot,\cdot\rangle$ is the usual
Euclidean inner product.

Let $s\in(0,s_{0})$. Pick $y\in A\setminus A^{(s)}$ and let $e=e(y)$ be as
just described. By translating and rotating $A$ we can assume without loss of
generality that $y=o$ and $e=e_{d}:=(0,\ldots,0,1)$. The following argument is
illustrated in Figure 3.

Let $x\in A\setminus B_{s}(y)$. After a further rotation we can also assume
without loss of generality that $x=-ue_{1}+ve_{d}$ for some $u\geq 0$ and
$v\in\mathbb{R}$ with $u^{2}+v^{2}\geq s^{2}$, where $e_{1}:=(1,0,\ldots,0)$.
It follows from this that $\|se_{1}-x\|\geq\sqrt{2}s$.

Let $z=(1-7\delta_{2})se_{1}+2\delta_{2}se_{d}$. By the triangle inequality
$\|z-x\|\geq(\sqrt{2}-9\delta_{2})s\geq(1+3\delta_{2})s$. Hence
$B_{\delta_{2}s}(z)\subset\mathbb{R}^{d}\setminus B_{(1+\delta_{2})s}(x)$.
Moreover $B_{\delta_{2}s}(z)^{o}\subset B^{*}(y;s,\delta_{2},e_{d})\subset A$.
Therefore

$\displaystyle{\rm Vol}(B_{s}(y)\cap A\setminus
B_{(1+\delta_{2})s}(x))\geq{\rm
Vol}(B_{\delta_{2}s}(z)^{o})=\theta(\delta_{2}s)^{d}.$

Thus taking $\delta_{1}=\min(\delta_{2},\theta\delta_{2}^{d})$ we have (5.11).
∎

###### Proof of Lemma 5.8.

Choose $\delta_{1}\in(0,1/2)$ with the property in Lemma 5.9. Let ${\bf
x}=(x_{1},\ldots,x_{k})\in(\mathbb{R}^{d})^{k}$ with $x_{1}\prec x_{i}$ and
$\|x_{1}-x_{i}\|\leq\delta_{1}r$ for $2\leq i\leq k$ (here $\prec$ refers to
the lexicographic ordering). For $i\in[n]\setminus[k]$, let ${\cal
X}_{i,k,n}:=\\{\tilde{X}_{k+1},\ldots,\tilde{X}_{n}\\}\setminus\\{\tilde{X}_{i}\\}$.
Let

$\displaystyle N_{6}({\bf x}):=\sum_{i=k+1}^{n}\mathbbm{1}\\{\tilde{X}_{i}\in
B_{2r}({\bf x})\setminus B_{r}({\bf x}),{\cal
X}_{i,k,n}(B_{r}(\tilde{X}_{i})\setminus B_{(1+\delta_{1})r}(x_{1}))<k\\}.$

Then using the property from Lemma 5.9 (taking $y=\tilde{X}_{i}$ and
$x=x_{1}$), and then a Chernoff-type bound (for example, [15, Lemma 1.1]), we
have for large $n$ that

$\displaystyle\mathbb{E}[N_{6}({\bf x})]$ $\displaystyle\leq(n-k)2kf_{\rm
max}\theta(2r)^{d}\mathbb{P}[\mathrm{Bin}((n-k-1),f_{0}\delta_{1}r^{d})\leq
k-1]$ $\displaystyle\leq\exp(-f_{0}(\delta_{1}/2)nr^{d}).$

Let $\mathscr{M}$ be the event that
$\\{\tilde{X}_{1},\ldots,\tilde{X}_{k}\\}\subset
B_{\delta_{1}r}(\tilde{X}_{1})$, i.e. ‘compressed’. If $\mathscr{M}$ occurs
then $N_{6}\leq N_{6}((\tilde{X}_{1},\ldots,\tilde{X}_{k}))$, and thus we have

$\displaystyle\mathbb{E}[N_{6}|\mathscr{M}]\leq\exp(-f_{0}(\delta_{1}/2)nr^{d}).$
(5.12)

Also,

$\displaystyle\mathbb{P}[\mathscr{M}^{c}]$
$\displaystyle=\mathbb{P}[\cup_{i=2}^{k}\\{X_{i}\notin
B_{\delta_{1}r}(X_{1})\\}|\\{h_{r}^{*}(X_{1},\ldots,X_{k})=1\\}\cap\cap_{\ell=k+1}^{n}\\{X_{\ell}\notin\cup_{i=1}^{k}B_{r}(X_{i})\\}]$
$\displaystyle=\frac{\int_{A}\mathbb{P}[E_{x}]\nu(dx)}{\int_{A}\mathbb{P}[F_{x}]\nu(dx)}$
(5.13)

where we set

$\displaystyle F_{x}$
$\displaystyle:=\\{h_{r}^{*}(x,X_{2},\ldots,X_{k})=1\\}\cap\cap_{\ell=k+1}^{n}\\{X_{\ell}\notin
B_{r}((x,X_{2},\ldots,X_{k}))\\};$ $\displaystyle E_{x}$
$\displaystyle:=\\{\\{X_{2},\ldots,X_{k}\\}\setminus
B_{\delta_{1}r}(x)\neq\varnothing\\}\cap F_{x}.$

Set $b=\limsup_{n\to\infty}(\theta nr^{d}/\log n)$ and note that
$b(f_{0}-f_{1}/2)<1/d$ by (3.1). Take $\delta_{2}>0$ such that

$\displaystyle b(f_{0}-f_{1}/2)+bf_{0}\delta_{2}<1/d,$ (5.14)

and such that moreover for all $y\in\mathbb{R}^{d}\setminus B_{\delta_{1}}(o)$
we have ${\rm Vol}(B_{1}(y)\setminus B_{1}(o))\geq\delta_{2}\theta$, and also
$\delta_{2}<1/3$. Then for all small enough $s>0$ and all $x\in A^{(3s)},y\in
A\setminus B_{\delta_{1}s}(x)$ we have ${\rm Vol}(A\cap B_{s}(y)\setminus
B_{s}(x))>\delta_{2}\theta s^{d}$. Moreover,
$h_{r}^{*}(x,x_{2},\ldots,x_{k})=0$ unless $x_{2},\ldots,x_{k}$ all lie in
$B_{(k-1)r}(x)$, and hence for all large enough $n$ and all $x\in A^{(3r)}$ we
have

$\displaystyle\mathbb{P}[E_{x}]$
$\displaystyle\leq\int_{(B_{kr}(x))^{k-1}\setminus(B_{\delta_{1}r}(x))^{k-1}}(1-\nu(B_{r}(x,{\bf
x})))^{n-k}\nu^{k-1}(d{\bf x})$ $\displaystyle\leq
2\int_{(B_{kr}(x))^{k-1}\setminus(B_{\delta_{1}r}(x))^{k-1}}\exp(-n\nu(B_{r}(x,{\bf
x})))\nu^{k-1}(d{\bf x})$ $\displaystyle\leq
2\int_{(B_{kr}(x))^{k-1}\setminus(B_{\delta_{1}r}(x))^{k-1}}\exp(-n\nu(B_{r}(x))-f_{0}\theta\delta_{2}nr^{d})\nu^{k-1}(d{\bf
x})$ $\displaystyle\leq
cr^{d(k-1)}\exp(-n\nu(B_{r}(x))-f_{0}\theta\delta_{2}nr^{d}),$

for some constant $c$ (independent of $x$). Similarly using the simpler bound
$\nu(B_{r}(x,{\bf x}))\geq\nu(B_{r}({\bf x}))$ we obtain for $x\in A\setminus
A^{(3r)}$ that $\mathbb{P}[E_{x}]\leq cr^{d(k-1)}e^{-n\nu(B_{r}(x))}.$ Hence
by splitting the integral into regions $A^{(3r)}$ and $A\setminus A^{(3r)}$,
given $f_{1}^{-}<f_{1}$, and using Lemma 3.4 we obtain for some new constant
$c$ that for $n$ large,

$\displaystyle r^{d(1-k)}\int_{A}\mathbb{P}[E_{x}]\nu(dx)\leq
c\exp(-\theta(f_{0}+f_{0}\delta_{2})nr^{d})+cr\exp(-\theta(f_{1}^{-}/2)nr^{d}).$
(5.15)

On the other hand, given $\delta_{3}\in(0,\delta_{1})$, and any
$\varepsilon>0$, we have for large enough $n$ and all $x\in A^{(2r)}$, setting
$B_{s}^{+}(x)$ to be the right half of $B_{s}(x)$, that

$\displaystyle\mathbb{P}[F_{x}]$
$\displaystyle\geq\int_{(B^{+}_{\delta_{3}r}(x))^{k-1}}(1-\nu(B_{(1+\delta_{3})r}(x)))^{n-k}\nu^{k-1}(d{\bf
x})$
$\displaystyle\geq(f_{0}(\theta/2)\delta_{3}^{d}r^{d})^{k-1}\exp(-(1+\varepsilon)n\nu(B_{(1+\delta_{3})r}(x))).$

Choose $\delta_{3}$ so that $f_{\rm max}((1+\delta_{3})^{d}-1)\leq
f_{0}\delta_{2}/4$, and $\varepsilon$ so that $2^{d}\varepsilon f_{\rm
max}<f_{0}\delta_{2}/4$. Then

$\displaystyle(1+\varepsilon)\nu(B_{(1+\delta_{3})r}(x))$
$\displaystyle\leq\nu(B_{r}(x))+f_{\rm max}\theta
r^{d}((1+\delta_{3})^{d}-1))+\varepsilon f_{\rm max}\theta(2r)^{d}$
$\displaystyle\leq\nu(B_{r}(x))+\theta r^{d}f_{0}\delta_{2}/2,$

so that given $f_{0}^{+}>f_{0}$ there is a further constant $c^{\prime}>0$
such that for large $n$ (using the continuity of $f$ on $A$) we have

$\displaystyle r^{d(1-k)}\int_{A}\mathbb{P}[F_{x}]\nu(dx)\geq
c^{\prime}\exp(-(f_{0}^{+}+f_{0}\delta_{2}/2)\theta nr^{d}).$

Therefore by (5.13) and (5.15) there is a further constant $c^{\prime\prime}$
such that

$\displaystyle\mathbb{P}[\mathscr{M}^{c}]$ $\displaystyle\leq
c^{\prime\prime}\exp[(f_{0}^{+}+f_{0}\delta_{2}/2-f_{0}-f_{0}\delta_{2})\theta
nr^{d}]+c^{\prime\prime}r\exp[(f_{0}^{+}+f_{0}\delta_{2}/2-f_{1}^{-}/2)\theta
nr^{d}]$
$\displaystyle=c^{\prime\prime}\exp[(f_{0}^{+}-f_{0}-f_{0}\delta_{2}/2)\theta
nr^{d}]+c^{\prime\prime}r\exp[(f_{0}^{+}+f_{0}\delta_{2}/2-f_{1}^{-}/2)\theta
nr^{d}].$

Taking $f_{0}^{+}$ sufficiently close to $f_{0}$ and $f_{1}^{-}$ sufficiently
close to $f_{1}^{-}$, we have that the first term is
$O(\exp(-f_{0}(\delta_{2}/4)\theta nr^{d}))$, while taking
$b:=\limsup_{n\to\infty}((n\theta r^{d})/\log n)$, the second term is bounded
by $rn^{b(f_{0}-(f_{1}/2)+f_{0}\delta_{2})}$, and by (5.14) and (3.1), this is
$O(\exp(-cnr^{d}))$ for some $c>0$. Thus using (5.12) and the fact that
$N_{6}$ is bounded by a deterministic constant depending only on $d$ and $k$,
we have for some constant $c^{\prime}$ that

$\displaystyle\mathbb{E}[N_{6}]$
$\displaystyle=\mathbb{E}[N_{6}|\mathscr{M}]\mathbb{P}[\mathscr{M}]+\mathbb{E}[N_{6}|\mathscr{M}^{c}]\mathbb{P}[\mathscr{M}^{c}]$
$\displaystyle\leq\exp(-\delta_{1}(f_{0}/2)nr^{d})+c^{\prime}\exp(-cnr^{d}),$

which implies the result asserted. ∎

###  5.3 Normal approximation

We shall prove our central limit theorem for $S^{\prime}_{n,k}$ by expressing
it as a sum of variables having the structure of an $m$-dependent random
field, whose definition we now recall. Let $X=(X_{\alpha},\alpha\in{\cal V})$
be a collection of random variables indexed by a set ${\cal
V}\subset\mathbb{Z}^{d}$. Given $m>0$, we say $X$ is an $m$-dependent random
field if for any two subsets $A_{1},A_{2}$ of $\mathbb{Z}^{d}$ with
$\min_{\alpha\in A_{1},\beta\in A_{2}}\|\alpha-\beta\|_{\infty}>m$, the sigma-
algebras $\sigma\\{X_{\alpha},\alpha\in A_{1}\\}$, and
$\sigma\\{X_{\alpha},\alpha\in A_{2}\\}$, are mutually independent.

######  Lemma 5.10.

(see [7, Theorem 2.6]) Let $2<q\leq 3$. Let ${\cal V}\subset\mathbb{Z}^{d}$
and let $(W_{i},\ i\in{\cal V})$ be an $m$-dependent random field with
$\mathbb{E}[W_{i}]=0$ for each $i\in{\cal V}$. Let $W=\sum_{i\in{\cal
V}}W_{i}.$ Assume that $\mathbb{E}[W^{2}]=1$ and
$\mathbb{E}[|W_{i}|^{q}]<\infty$ for all $i\in{\cal V}$. Then

$\displaystyle d_{\mathrm{K}}(W,N(0,1))\leq 75(10m+1)^{(q-1)d}\sum_{i\in{\cal
V}}\mathbb{E}[|W_{i}|^{q}].$ (5.16)

We shall apply Lemma 5.10 to $S^{\prime}_{n,k}$ to prove (5.3) from Theorem
5.1. The claim is restated in the form of a proposition.

######  Proposition 5.11.

Set $b=\limsup_{n\to\infty}n\theta r^{d}/(\log n)$. Set
$\sigma=(\mathbb{V}\mathrm{ar}[S^{\prime}_{n,k}])^{1/2}$. Let $\varepsilon>0$.
Then as $n\to\infty$,

$\displaystyle
d_{\mathrm{K}}(\sigma^{-1}(S^{\prime}_{n,k}-I_{n,k}),N(0,1))=O(n^{\varepsilon+(bf_{0}-1)/2}).$
(5.17)

###### Proof.

Let $f_{0}^{-}<f_{0}$ and $f_{0}^{+}>f_{0}$, and $f_{1}^{-}<f_{1}^{*}<f_{1}$.
Fix $\delta\in(0,d^{-1/2})$, with $f_{0}(1-2d\delta)^{d}>f_{0}^{-}$ and also
$f_{1}^{*}(1-2d\delta)^{d}>f_{1}^{-}$. Given $n$, partition $\mathbb{R}^{d}$
into cubes of side length $\delta r=\delta r(n)$ centred on the points of
$\delta r\mathbb{Z}^{d}$ and indexed by $\mathbb{Z}^{d}$; for
$z\in\mathbb{Z}^{d}$ let $C_{z}$ be the cube in the partition that is centred
on $\delta rz$. Let ${\cal V}=\\{z\in\mathbb{Z}^{d}:C_{z}\cap
A\neq\varnothing\\}$. Then $|{\cal V}|=O(r^{-d})$ as $n\to\infty$.

For $z\in{\cal V}$, let $U_{z}$ be the number of components of order $k$ in
$G({\cal P}_{n},r)$ having their left-most vertex in $C_{z}$, set
$p_{z}:=\mathbb{E}[U_{z}]$, and let $W_{z}=\sigma^{-1}(U_{z}-p_{z})$. Then
$\sum_{z\in{\cal V}}U_{z}=S^{\prime}_{n,k}$ and $\sum_{z\in{\cal
V}}W_{z}=\sigma^{-1}(S^{\prime}_{n,k}-I_{n,k})$. Moreover, $(W_{z},z\in{\cal
V})$ is a centred $m$-dependent random field, where $m$ is independent of $n$.
Hence by Lemma 5.10 (taking $q=3$), there is a constant $c$ independent of $n$
such that

$\displaystyle
d_{\mathrm{K}}(\sigma^{-1}(S^{\prime}_{n,k}-I_{n,k}),N(0,1))\leq
c\sum_{z\in\nu}\mathbb{E}[|W_{z}|^{3}]=c\sigma^{-3}\sum_{z\in\nu}\mathbb{E}[|U_{z}-p_{z}|^{3}].$
(5.18)

Since $\delta<d^{-1/2}$, any two points of ${\cal P}_{n}$ in the same cube are
connected in $G({\cal P}_{n},r)$, and therefore $U_{z}$ is a Bernoulli random
variable with parameter $p_{z}$, for each $z\in{\cal V}$. Hence
$\mathbb{E}[|U_{z}-p_{z}|^{3}]=p_{z}(1-p_{z})^{3}+(1-p_{z})p_{z}^{3}\leq
p_{z}$.

Let ${\cal V}_{1}:=\\{z\in{\cal V}:\delta rz\in A^{(r)}\\}$ and ${\cal
V}_{2}:={\cal V}\setminus{\cal V}_{1}$.

Let $z\in{\cal V}$. If ${\cal P}_{n}(B_{r-d\delta r}(\delta rz))\geq k+1$,
then $U_{z}=0$. Therefore there exists $c>0$ such that for $z\in{\cal V}_{1}$,

$p_{z}\leq\mathbb{P}[{\cal P}_{n}(B_{r-d\delta r}(\delta rz))\leq k]\leq
c(nr^{d})^{k}\exp(-f_{0}\theta(1-d\delta)^{d}nr^{d}),$

so that by Proposition 4.1, there exists $c^{\prime}$ such that for $n$ large
the contribution of ${\cal V}_{1}$ to the right hand side of (5.18) is at most

$c^{\prime}r^{-d}\exp(-f_{0}\theta(1-2d\delta)^{d}nr^{d})I_{n,k}^{-3/2}\leq
c^{\prime}r^{-d}\exp(-f_{0}^{-}\theta nr^{d})I_{n,k}^{-3/2},$

and by Lemma 3.1, for $n$ large this is at most

$n^{-1/2}(nr^{d})^{-1}\exp(((3/2)f_{0}^{+}-f_{0}^{-})\theta nr^{d}).$

Set $b:=\limsup_{n\to\infty}n\theta r^{d}/(\log n)$. Then $b<1/f_{0}$ by
(3.1), and for any $\varepsilon>0$, provided $f_{0}^{+}$ and $f_{0}^{-}$ are
chosen close enough to $f_{0}$ the above is bounded by
$n^{\varepsilon+(bf_{0}-1)/2}$.

Now consider $z\in{\cal V}_{2}$. For such $z$, using Lemma 3.4 we have

$p_{z}\leq\mathbb{P}[{\cal P}_{n}(B_{r-d\delta r}(\delta rz))\leq k]\leq
c(nr^{d})^{k}\exp(-f_{1}^{*}(1-d\delta)^{d}(\theta/2)nr^{d}).$

Also we claim that $|{\cal V}_{2}|=O(r^{1-d})$. Indeed, using the first part
of Lemma 3.4, we can cover $\partial A$ by $O(r^{1-d})$ balls of radius $r$.
Taking balls of radius $3r$ with the same centres gives a collection of
$O(r^{1-d})$ balls such that each each point of ${\cal V}_{2}$ lies in at
least one of these balls. Since the number of points of ${\cal V}_{2}$
contained in any one of these balls is uniformly bounded, the claim follows.

Therefore there exists a constant $c^{\prime\prime}$ such that the
contribution of ${\cal V}_{2}$ to the right hand side of (5.18) is at most
$c^{\prime\prime}r^{1-d}\exp(-f_{1}^{-}(\theta/2)nr^{d})I_{n,k}^{-3/2},$ and
by Lemma 3.1, given $\varepsilon>0$, for $n$ large this is at most

$n^{-1/2}r(nr^{d})^{-1}\exp(((3/2)f_{0}^{+}-f_{1}^{-}/2)\theta
nr^{d})<n^{\varepsilon-(1/2)-(1/d)+(b/2)(3f_{0}-f_{1})}.$

Using (3.1) we have that $b(f_{0}-f_{1}/2)<1/d$ and therefore the exponent of
$n$ above is at most $\varepsilon-(1/2)+bf_{0}/2$, i.e.
$\varepsilon+(bf_{0}-1)/2$. Combining this with the contribution of ${\cal
V}_{1}$ and applying (5.18) yields (5.17). ∎

For a binomial counterpart of Proposition 5.11 using Wasserstein distance, we
use the following lemma, which is based on a result of Chatterjee [6], which
requires further notation.

Recall the definition of $\mathbf{N}(\mathbb{R}^{d})$ from Section 5.1. Given
$F:\mathbf{N}(\mathbb{R}^{d})\to\mathbb{R}$ and $x\in\mathbb{R}$, set
$D_{x}F({\cal X}):=F({\cal X}\cup\\{x\\})-F({\cal X})$, and set
$\|DF\|:=\sup_{x\in\mathbb{R}^{d},{\cal
X}\in\mathbf{N}(\mathbb{R}^{d})}|D_{x}F({\cal X})|$. Given such $F$ and given
$s\in(0,\infty)$, we say that the constant $s$ is a radius of stabilization
for $F$ if $D_{x}F({\cal X})$ is determined by ${\cal X}\cap B_{s}(x)$ for all
$x\in\mathbb{R}^{d},{\cal X}\in\mathbf{N}(\mathbb{R}^{d})$, i.e. $D_{x}F({\cal
X})=D_{x}F({\cal X}\cap B_{s}(x))$ for all $x,{\cal X}$ (this notion dates
back at least to [19]).

######  Lemma 5.12.

Let $n\in\mathbb{N}$, $s\in(0,\infty)$. Suppose
$F:\mathbf{N}(\mathbb{R}^{d})\to\mathbb{R}$ is measurable with $\|DF\|<\infty$
and $\sigma:=\sqrt{\mathbb{V}\mathrm{ar}[F({\cal X}_{n})]}\in(0,\infty)$, and
$s$ is a radius of stabilization for $F$. Then

$\displaystyle d_{\mathrm{W}}\left(\frac{F({\cal X}_{n})-\mathbb{E}F({\cal
X}_{n})}{\sigma},\mathcal{N}\right)\leq\frac{Cn^{1/2}}{\sigma^{2}}\|DF\|^{2}(\mathbb{E}[({\cal
X}_{n+4}(B_{s}(X_{1})))^{4}])^{1/4}+\frac{4n}{\sigma^{3}}\|DF\|^{3},$ (5.19)

where $C$ is a universal constant.

###### Proof.

We apply [6, Theorem 2.5]. As explained below, the graph $G({\cal X}_{n},s)$
is a symmetric interaction rule (in the sense of [6]) for $F$, and we can take
its symmetric extension $G^{\prime}$ to be $G({\cal X}_{n+4},s)$. The quantity
denoted $\Delta_{j}f(X)$ in [6, Theorem 2.5] has its absolute value bounded by
$2\|DF\|$.

Suppose ${\bf x}=(x_{1},\ldots,x_{n})\in(\mathbb{R}^{d})^{n}$ and ${\bf
x}^{\prime}=(x^{\prime}_{1},\ldots,x^{\prime}_{n})\in(\mathbb{R}^{d})^{n}$.
For $i,j\in\\{1,\ldots,n\\}$ with $i\neq j$, set ${\bf
x}^{i}=(x_{1},\ldots,x_{i-1},x^{\prime}_{i},x_{i+1},\ldots,x_{n})$ and ${\bf
x}^{ij}=({\bf x}^{i})^{j}$. As done elsewhere in this paper, we identify ${\bf
x}$ with the set $\\{x_{1},\ldots,x_{n}\\}$ (with any repeated entry in ${\bf
x}$ being included just once in $\\{x_{1},\ldots,x_{n}\\}$), and likewise for
${\bf x}^{i}$ and ${\bf x}^{ij}$.

By the stabilization condition $F({\bf x})-F({\bf x}^{j})$ is determined by
$x_{j},x^{\prime}_{j}$ and the sets ${\bf x}\cap B_{s}(x_{j})$ and ${\bf
x}\cap B_{s}(x^{\prime}_{j})$. Similarly, $F({\bf x}^{i})-F({\bf x}^{ij})$ is
determined by $x_{j},x^{\prime}_{j}$ and the sets ${\bf x}^{i}\cap
B_{s}(x_{j})$ and ${\bf x}^{i}\cap B_{s}(x^{\prime}_{j})$.

If $\|x_{i}-x_{j}\|$, $\|x^{\prime}_{i}-x_{j}\|$, $\|x_{i}-x^{\prime}_{j}\|$
and $\|x^{\prime}_{i}-x^{\prime}_{j}\|$ all exceed $s$ then ${\bf x}\cap
B_{s}(x_{j})={\bf x}^{i}\cap B_{s}(x_{j})$ and ${\bf x}\cap
B_{s}(x^{\prime}_{j})={\bf x}^{i}\cap B_{s}(x^{\prime}_{j})$, so that $F({\bf
x})-F({\bf x}^{j})=F({\bf x}^{i})-F({\bf x}^{ij})$, and this shows that
$G({\bf x},s)$ really is a symmetric interaction rule for $F$ in the sense of
[6], as claimed earlier. ∎

We can now provide the binomial counterpart for Proposition 5.11 using
Wasserstein distance. This gives us the penultimate assertion (5.4) of Theorem
5.1.

######  Proposition 5.13.

Set $\sigma=\sqrt{\mathbb{V}\mathrm{ar}[S_{n,k}]}$, and set
$b:=\limsup_{n\to\infty}n\theta r^{d}/(\log n)$. Then

$\displaystyle
d_{\mathrm{W}}(\sigma^{-1}(S_{n,k}-\mathbb{E}[S_{n,k}]),N(0,1))$
$\displaystyle=O\left(\frac{n}{\sigma^{3}}\right)$
$\displaystyle=O(n^{\varepsilon+(3bf_{0}-1)/2}).$ (5.20)

###### Proof.

Given $n$, we apply Lemma 5.12, taking $F({\cal X}):=K_{k,r}({\cal X})$, the
number of $k$-components in $G({\cal X},r)$ (with $r=r(n)$ as usual). Then
$\|DF\|$ is bounded above by a constant independent of $n$, since for all
$x\in\mathbb{R}^{d}$, $r>0$ and finite ${\cal X}\subset\mathbb{R}^{d}$ the
number of components of $G({\cal X},r)$ intersecting $B(x,r)$ is bounded by a
constant depending only on $d$ (and not on ${\cal X},x$ or $r$). Also
$\|DF\|\geq 1$. By Propositions 3.2 and 4.1, $\mathbb{E}[F({\cal X}_{n})]\sim
I_{n,k}$ and $\sigma^{2}\sim I_{n,k}$ as $n\to\infty$.

Clearly $s=(k+1)r$ is a radius of stabilization for $F$. Also ${\cal
X}_{n+4}(B_{(k+1)r}(X_{1}))$ is stochastically dominated by
$1+\mathrm{Bin}(n+4,f_{\rm max}\theta((k+1)r)^{d})$ and hence
$\mathbb{E}[{\cal X}_{n+4}(B_{(k+1)r}(X_{1}))^{4}]\leq c(nr^{d})^{4}$, for
some constant $c$. Therefore in the present instance, the first term in the
right hand side of (5.19) divided by the second term is
$O(n^{-1/2}\sigma(nr^{d}))=O(n^{-1/2}(nr^{d})I_{n}^{1/2})$. which tends to
zero because $I_{n}^{1/2}=O(n^{1/2}(nr^{d})^{(k-1)/2}e^{-cnr^{d}})$ for some
$c>0$, by (3.3) and (3.8). Then we obtain the first line of (5.20) from
(5.19).

For the second line of (5.20) we use Proposition 4.3, Lemma 3.1 and (1.1). ∎

###### Proof of Theorem 5.1.

We have already proved (5.1), (5.2), (5.3) and (5.4). We now prove the normal
approximation result (5.5), using the Poisson approximation result (5.2). By
the Berry-Esseen theorem
$d_{\mathrm{K}}(t^{-1/2}(Z_{t}-t),\mathcal{N})=O(t^{-1/2})$ as $t\to\infty$.
Hence, by the triangle inequality for $d_{\mathrm{K}}$, and the fact that
$d_{\mathrm{K}}(X,Y)\leq d_{\mathrm{TV}}(X,Y)$ for any $X,Y$, we have

$\displaystyle
d_{\mathrm{K}}((\mathbb{E}S_{n,k})^{-1/2}(S_{n,k}-\mathbb{E}S_{n,k}),\mathcal{N})\leq
d_{\mathrm{TV}}(S_{n,k},Z_{\mathbb{E}S_{n,k}})+O((\mathbb{E}S_{n,k})^{-1/2}).$
(5.21)

By (5.2) the first term in the right hand side of (5.21) is $O(e^{-cnr^{d}})$
for some $c>0$.

By Proposition 3.2 and Lemma 3.1,
$\mathbb{E}S_{n,k}=\Omega(ne^{-nf_{0}^{+}\theta r^{d}})$. Therefore
$(\mathbb{E}S_{n,k})^{-1/2}=o(n^{\varepsilon+(bf_{0}-1)/2})$. Note that (3.1)
implies $bf_{0}<1$. Moreover, using (3.1) and taking both $\varepsilon$ and
$c$ to be sufficiently small, we see that the second term in the right hand
side of (5.21) is also $O(e^{-cnr^{d}})$, and hence the left hand side of
(5.21) is $O(e^{-cnr^{d}})$ for some $c>0$. Thus

$\displaystyle
d_{\mathrm{K}}((\mathbb{V}\mathrm{ar}S_{n,k})^{-1/2}(S_{n,k}-\mathbb{E}S_{n,k}),(\mathbb{E}S_{n,k}/\mathbb{V}\mathrm{ar}S_{n,k})^{1/2}\mathcal{N})$
$\displaystyle=d_{\mathrm{K}}((\mathbb{E}S_{n,k})^{-1/2}(S_{n,k}-\mathbb{E}S_{n,k}),\mathcal{N})=O(e^{-cnr^{d}}).$

Now using the fact that
$\sup_{t\in[-1/2,1/2]\setminus\\{0\\}}t^{-1}d_{\mathrm{K}}((1+t)\mathcal{N},\mathcal{N})<\infty$,
and Proposition 4.3, and the triangle inequality for $d_{\mathrm{K}}$, we can
deduce (5.5).

The same argument works for $S^{\prime}_{n,k}$, for all $d\geq 1$. ∎

##  6 The sparse limiting regime

Fix $k\in\mathbb{N}$. In this section, instead of (3.1) we assume the ‘mildly
sparse’ limiting regime

$\displaystyle\lim_{n\to\infty}nr_{n}^{d}=0;\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\lim_{n\to\infty}n(nr_{n}^{d})^{k-1}=\infty.$ (6.1)

In Section 1.1, we mentioned how to obtain a CLT for $S_{n,k}$ from previously
known results in this regime under the extra condition that $n(nr^{d})^{k}\to
0$. We now describe, without giving full details, how we can adapt the methods
of this paper to derive limiting expressions for means and variances, and CLTs
both for $S_{n,k}$ and $S^{\prime}_{n,k}$, assuming only (6.1).

We assume $f_{\rm max}<\infty$ but now we do not need to make any other
assumptions on $f$ or on the geometry of the support $A$ of $f$. Defining
$I_{n,k}:=\mathbb{E}S^{\prime}_{n,k}$ as before, we now have

$\displaystyle I_{n,k}\sim
k!^{-1}n(nr^{d})^{k-1}\int_{\mathbb{R}^{d}}f(x)^{k}dx\int_{(\mathbb{R}^{d})^{k-1}}h_{1}((o,{\bf
x}))d{\bf x}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ {\rm
as}\leavevmode\nobreak\ n\to\infty.$ (6.2)

Moreover $\mathbb{E}[S_{n,k}]\sim I_{n,k}$ as $n\to\infty$. These can be
proved along the lines of [15, Propositions 3.1 and 3.2]. By (6.2), (6.1)
implies $I_{n.k}\to\infty$ as $n\to\infty$. Under (6.1), any factors of the
form $e^{-n\nu(B_{r}({\bf x}))}$ arising in moment estimates no longer tend to
zero, but remain bounded above by 1.

Next we have

$\mathbb{V}\mathrm{ar}[S^{\prime}_{n,k}]=I_{n,k}(1+O(nr^{d})^{k}).$

To see this, follow the proof of Proposition 4.1. In the sparse regime, it can
be seen directly from (4.1) and (4.2) that both $J_{1,n}$ and $J_{2,n}$ are
$O(n^{2k}r^{d(2k-1)})$, which is $O((nr^{d})^{k}I_{n,k})$.

Next we have

$\displaystyle d_{\mathrm{TV}}(S^{\prime}_{n,k},Z_{I_{n,k}})=O((nr^{d})^{k}).$
(6.3)

For this, we can follow the proof of Proposition 5.4. We now have
$\mathbb{E}[\xi_{1}({\bf x})]=O((nr^{d})^{k})$, uniformly over ${\bf x}$.
Likewise $\mathbb{E}[\xi_{2}({\bf x})]=O((nr^{d})^{k})$.

For $S_{n,k}$, we consider only the case $k\geq 2$ in the sparse limiting
regime, since isolated vertices are not rare events. We claim that if $k\geq
2$ then

$\displaystyle\mathbb{V}\mathrm{ar}[S_{n,k}]=\mathbb{E}[S_{n,k}](1+O(nr^{d})^{k-1}).$
(6.4)

This is proved by following the proof of Proposition 4.3. The expression at
(4.9) is $O(n^{2k-1}r^{d(2k-2)})$ which is $O(I_{n,k}(nr^{d})^{k-1})$. In the
penultimate line of (4.11) the last factor (in square brackets) now simplifies
to $O(n^{-1})$ so the expression in (4.11) is $O(n^{2k-3})$. Hence the first
term in the right hand side of (4.10), multiplied by $n^{2}$, is now
$O(n^{2k-1}r^{d(2k-2)})=O((nr^{d})^{k-1}I_{n,k})$. It can be seen directly
that the second and third terms in the right hand side of (4.10), multiplied
by $n^{2}$, are $O(n^{2k}r^{d(2k-1)})$ which is $O((nr^{d})^{k}I_{n,k})$.
Combining these estimates shows that
$\mathbb{V}\mathrm{ar}S_{n,k}-\mathbb{E}S_{n,k}=O((nr^{d})^{k-1}I_{n,k})=O((nr^{d})^{k-1}\mathbb{E}S_{n,k})$,
as claimed.

Next we claim that by following the proof of Proposition 5.6, one can show

$\displaystyle
d_{\mathrm{TV}}(S_{n,k},Z_{\mathbb{E}S_{n,k}})=O((nr^{d})^{k-1}).$ (6.5)

Indeed, for each $i\in[6]$ we have $\mathbb{E}[N_{i}]=O((nr^{d})^{j})$ with
$j=j(i)\in\\{k-1,k,k+1\\}$. For $N_{6}$ this can now be seen directly without
using the more involved proof of Lemma 5.8. In particular, the restriction to
$d\geq 2$ is not needed for (6.5).

By a similar argument to the proof of (5.5), using (6.5) and (6.4), we can
obtain that

$d_{\mathrm{K}}((\mathbb{V}\mathrm{ar}S_{n,k})^{-1/2}(S_{n,k}-\mathbb{E}S_{n,k}),\mathcal{N})=O(\max((nr^{d})^{k-1},(n(nr^{d})^{k-1})^{-1/2})).$

Using (6.3) instead of (6.5) we can similarly obtain that

$d_{\mathrm{K}}((\mathbb{V}\mathrm{ar}S^{\prime}_{n,k})^{-1/2}(S^{\prime}_{n,k}-\mathbb{E}S^{\prime}_{n,k}),\mathcal{N})=O(\max((nr^{d})^{k},(n(nr^{d})^{k-1})^{-1/2})).$

Acknowledgements. We thank Frankie Higgs and Oliver Penrose for some useful
discussions in relation to this paper.

## References

  * [1] Alexander, K.S. (1993) Finite clusters in continuous percolation: compression and sphericality. Probab. Theory Related Fields 97, 35–63.
  * [2] Azmoodeh, E., Peccati, G. and Yang, X. (2021) Malliavin-Stein method: a survey of recent developments. Mod. Stoch. Theory Appl. 8, 141–177.
  * [3] Baccelli, F. and Błaszczyszyn, B. (2009). Stochastic geometry and wireless networks I: Theory. Foundations and Trends in Networking 4, 1–312.
  * [4] Barbour, A.D., Holst, L. and Janson, S. (1992) Poisson Approximation. Oxford University Press, Oxford.
  * [5] Bobrowski, O. and Kahle, M. (2018) Topology of random geometric complexes: a survey. J. Appl. Comput. Topol. 1, 331–364.
  * [6] Chatterjee, S. (2008) A new method of normal approximation. Ann. Probab. 36, 1584–1610.
  * [7] Chen, L.H.Y. and Shao, Q.-M. (2004) Normal approximation under local dependence, Ann. Probab., 32, 1985–2028.
  * [8] Chen, Louis H. Y., Goldstein, L. and Shao, Q.-M. (2011) Normal Approximation by Stein’s Method. Springer, Heidelberg.
  * [9] Haan, S.W. and Zwanzig, R. (1977) Series expansions in a continuum percolation problem. J. Phys. A: Math. Gen. 10, 1547–1555.
  * [10] Lachièze-Rey, R. (2017) and Peccati, G. (2017) New Berry-Esseen bounds for functionals of binomial point processes. Ann. Appl. Probab. 27, 1992–2031.
  * [11] Last, G. and Penrose, M. (2018) Lectures on the Poisson Process. Cambridge University Press.
  * [12] Lindvall, T. (1992) Lectures on the Coupling Method. Dover, Mineola, New York.
  * [13] Meester, R. and Roy, R. (1996). Continuum Percolation. Cambridge University Press.
  * [14] Nourdin, I. and Peccati, G. (2012) Normal Approximations with Malliavin Calculus. From Stein’s method to Universality. Cambridge University Press, Cambridge.
  * [15] Penrose, M. (2003) Random Geometric Graphs. Oxford University Press, Oxford.
  * [16] Penrose, M.D. (1991) On a continuum percolation model. Adv. Appl. Probab. 23, 536–556.
  * [17] Penrose, M.D. (2018) Inhomogeneous random graphs, isolated vertices, and Poisson approximation. J. Appl. Probab. 55, 112–136.
  * [18] Penrose, M.D. (2023) Random Euclidean coverage from within. Probability Theory and Related Fields. https://doi.org/10.1007/s00440-022-01182-5. Also Arxiv:2101.06306v3.
  * [19] Penrose, M.D. and Yukich, J. E. (2001) Central limit theorems for some graphs in computational geometry. Ann. Appl. Probab. 11, 1005–1041.
  * [20] Quintanilla, J. and Torquato, S. (1996). Clustering properties of $d$-dimensional overlapping spheres. Phys. Review E 54, 5331–5339.
  * [21] Stein, C. (1986) Approximate Computation of Expectations. Institute of Mathematical Statistics, Hayward, CA.
  * [22] Torquato, S. (2002) Random Heterogeneous Materials. Springer, New York.