Large deviations for the volume
of hyperbolic $k$-nearest neighbor balls

Large deviations theory is one of the most classical subfields of probability theory with a wide range of applications in information theory, statistical physics, and rare-event simulation [8]. While the most refined results are available in the study of sequences of random variables and of time-dependent stochastic processes, the understanding of large deviations in spatial random systems is still in its infancy. Even the most basic statistics such as the edge counts in a random geometric graph can give rise to surprising and highly non-trivial condensation effects on the level of large deviations [6].

One of the earliest achievements in this context is [13], which proves a large deviation principle (LDP) for statistics of a homogeneous Poisson point process in ${\mathbb{R}}^{d}$ under rather restrictive boundedness and locality assumptions. Later, these conditions could be relaxed substantially so as to allow for statistics with bounded exponential moments and stabilizing score functions [25, 26]. While the main focus there was on scalar and measure-valued LDPs in the thermodynamic regime, very recently also geometric statistics in the sparse and dense regimes of the Poisson point process were considered [16, 17].

All of the aforementioned results have in common that they deal with random geometric systems in Euclidean space. However, during the last years the hyperbolic space has received substantial attention in the context of complex networks [11]. Moreover, there has been vigorous activity to understand the asymptotic behavior of geometric functionals of random set systems in hyperbolic space as well. While there has been substantial progress for central and non-central limit theorems and Poisson approximation results [1, 2, 3, 10, 12, 14, 15, 18, 21, 22], large deviation principles have not been considered so far. By investigating the volume of $k$-nearest neighbor (kNN) balls in hyperbolic space in the present work, we provide a first step in this direction and complement the recent findings [21] about their extremal behavior.

The general proof strategy is to extend and to develop further the ideas of [16] on a coarse graining scheme to introduce a blocked point process. Inside each block, a Poisson approximation theorem in the spirit of [21] is used to replace the original functional by a Poisson point process for which the LDP is given by Sanov’s theorem. However, the intricate geometry of the hyperbolic space makes it far more challenging to implement the blocking argument in comparison to the Euclidean setting considered in [16]. For instance, in the Euclidean setting the kissing number is finite so that in a box of side length of order $r>0$ only a uniformly bounded number of points with a nearest neighbor radius exceeding $r$ can be placed. In contrast, in hyperbolic space, this number grows exponentially in $r$; see [9]. Moreover, in the half-space model of hyperbolic space, the Poisson intensity is inhomogeneous in the vertical direction when considered in Euclidean terms, while in the ${\mathbb{R}}^{d}$-setting there is homogeneity in all directions. We deal with these problems by deriving more refined exponential moment bounds and analyzing the point configuration in vertical layers that individually can be considered approximately homogeneous.

We believe that the techniques developed in the present article open the door to the investigation of further LDPs in hyperbolic space. In particular, we think of extending the results for the Euclidean component counts from [17] in the sparse regime. Here, we note that while the study of component counts is restricted to trees in the dense regime [22] such constraints are no longer present in the sparse regime.

The rest of the manuscript is organized as follows. In Section 2, we properly introduce the considered model and state the LDP for the volumes of large kNN balls. Next, in Section 3, we give a proof outline, where we reduce the assertion to two key auxiliary results, namely Propositions 3.1 and 3.2. These results are proven separately in Sections 4 and 5, respectively.

By the hyperbolic space $\mathbb{H}^{d}$ of dimension $d\geq 2$ we mean the unique simply connected, $d$-dimensional Riemannian manifold of constant sectional curvature $-1$, cf. [5, 24]. There are several models to represent $\mathbb{H}^{d}$ in the $d$-dimensional Euclidean space ${\mathbb{R}}^{d}$. To carry out our computations, we will work in this paper with the so-called half-space model, but we emphasize that all results we derive are actually model independent; for background material on half-space model of hyperbolic space we refer to [24, Chapter 4.6]. In the half-space model, we identify $\mathbb{H}^{d}$ with the product space $\mathbb{H}^{d}={\mathbb{R}}^{d-1}\times(0,\infty)$. The Riemannian metric is then determined by

and we denote by $\mathsf{dist}_{\mathsf{hyp}}(z_{1},z_{2})$ the hyperbolic distance of two points $z_{1}=(x_{1},y_{1}),z_{2}=(x_{2},y_{2})\in\mathbb{H}^{d}$, which in terms of the Euclidean distance $\mathsf{dist}_{\mathsf{euc}}(z_{1},z_{2})$ between $z_{1}$ and $z_{2}$ is given by

see [24, Theorem 4.6.1]. According to [24, Theorem 4.6.7], the hyperbolic volume measure $V_{\mathsf{hyp}}$ on $\mathbb{H}^{d}$ has density

with respect to the Lebesgue measure on ${\mathbb{R}}^{d-1}\times(0,\infty)$ and we will use the notation

for the hyperbolic volume of a measurable set $B\subseteq\mathbb{H}^{d}$. In contrast, we shall write $|\,\cdot\,|_{\mathsf{leb}}$ for the Lebesgue measure of the appropriate dimension, which will always be clear from the context. In addition, we denote for $r>0$ and $x\in\mathbb{H}^{d}$ by $B_{r}(x)\mathrel{\mathop{\mathchar 58\relax}}=\{z\in\mathbb{H}^{d}\mathrel{\mathop{\mathchar 58\relax}}\mathsf{dist}_{\mathsf{hyp}}(x,z)\leq r\}$ the hyperbolic ball of radius $r$ centered at $x$. Its hyperbolic volume satisfies

independently of $x$, with $\beta_{d}\mathrel{\mathop{\mathchar 58\relax}}=2\pi^{d/2}/\Gamma({d\over 2})$ being the surface content of the $(d-1)$-dimensional Euclidean unit sphere; see [24, page 79]. In particular, $|B_{r}(x)|_{\mathsf{hyp}}$ grows like a constant multiple of $e^{r(d-1)}$, as $r\uparrow\infty$.

Henceforth, we let $\mathcal{P}=\sum_{i\geq 1}\delta_{X_{i}}$ be the random counting measure distributed as a Poisson point process with the hyperbolic volume measure as its intensity measure. We note that such $\mathcal{P}$ is stationary in the sense that its distribution is invariant with respect to the full group of hyperbolic isometries. In particular, $\mathcal{P}(B)$ is the number of points of $\mathcal{P}$ falling into a measurable set $B\subseteq\mathbb{H}^{d}$. In this paper, we write $\mathcal{P}_{B}$ or sometimes $\mathcal{P}\cap B$ for the restriction of the measure $\mathcal{P}$ to $B$. In what follows, we shall restrict $\mathcal{P}$ to the family of sampling windows

whose hyperbolic volume is given by $|W_{\lambda}|_{\mathsf{hyp}}=\int_{e^{-\lambda}}^{\infty}y^{-d}\,\operatorname{d\!}y={1\over d-1}e^{(d-1)\lambda}$.

For $k\geq 1$ we study the asymptotics of large $k$-nearest neighbor (kNN) balls centered in $W_{\lambda}$. To make this precise, we define the point process

where

and $(v_{\lambda})_{\lambda>0}$ is a threshold sequence satisfying

In particular, the expected number of exceedances in the window $W_{\lambda}$ is of order $u_{\lambda}\mathrel{\mathop{\mathchar 58\relax}}=|W_{\lambda}|_{\mathsf{hyp}}e^{-v_{\lambda}}v_{\lambda}^{k-1}$.

Our main result is a large deviation principle (LDP) for the volumes of large kNN balls. We recall that a family of random variables $(X_{\lambda})_{\lambda>0}$, defined on some probability space $(\Omega,\mathcal{F},\mathbb{P})$ and taking values in a Polish space ${\mathcal{X}}$, satisfies an LDP with speed $s_{\lambda}\uparrow\infty$ and rate function $\mathcal{I}\mathrel{\mathop{\mathchar 58\relax}}{\mathcal{X}}\to[0,\infty]$, provided that $\mathcal{I}$ is lower semicontinuous and if for each measurable set $B\subseteq{\mathcal{X}}$ one has that

where $B^{\circ}$ and $\bar{B}$ stand for the interior and the closure of $B$, respectively. To present our main result, we fix $s_{0}\in{\mathbb{R}}$ and introduce the space $E_{0}\mathrel{\mathop{\mathchar 58\relax}}=[s_{0},\infty)$ as well as the measure $\tau_{k}$ on $E_{0}$ which has Lebesgue density $e^{-u}/(k-1)!$, $u>s_{0}$. By $\mathcal{M}(E_{0})$ we denote the space of finite measures on $E_{0}$, which supplied with the weak topology becomes a Polish space [7, Proposition A2.5.III]. For $\rho\in\mathcal{M}(E_{0})$ we let

be the relative entropy entropy of $\rho$ with respect to $\tau_{k}$, where $\rho\ll\tau_{k}$ indicates that $\rho$ is absolutely continuous with respect to $\tau_{k}$ and $\frac{\operatorname{d\!}\rho}{\operatorname{d\!}\tau_{k}}$ denotes the corresponding Radon-Nikodym derivative; see [13, Equation (2.10)]. We are now prepared to present the main result of this paper.

As highlighted in Section 1, Theorem 2.1 can be seen as the hyperbolic counterpart of [16, Theorem 2.1], which concerns large deviations of the empirical measure of recentered and rescaled kNN balls in Euclidean space. On a formal level, in the hyperbolic setting, we found it more convenient to consider a scaling where the expected number of Poisson points in the window grows exponentially in $\lambda$, whereas in [16] the corresponding scaling is linear in parameter $n$. After this rescaling, our condition on the growth of $v_{\lambda}$ corresponds precisely to the growth of $a_{n}$ in [16, Equation (2.1)]. Moreover, in the Euclidean setting the dense scaling in [16] can be equivalently transformed to the regime of growing windows considered here. However, we stress that the regimes of dense points and growing windows are no longer equivalent in hyperbolic setting, and only the growing-window asymptotics reflects the negative curvature effects from the hyperbolic space.

While the previous paragraph illustrates that there is a formal correspondence between Theorem 2.1 and the Euclidean analog [16, Theorem 2.1], the hyperbolic geometry creates substantial complications, which require us to develop novel methodological tools. First, while both Theorem 2.1 and [16, Theorem 2.1] rely on a Poisson approximation result for large kNN balls, such a result is substantially harder to establish in hyperbolic geometry. We therefore adapt the arguments of a very recent work [21]. Moreover, when establishing a central uniform integrability property, [16] relies crucially on a kissing-number argument. More precisely, while in Euclidean space, the number of non-intersecting balls of radius $r$ that can be put into a box of side length of order $r$ is uniformly bounded independently of $r$, such a property does not hold in hyperbolic space. Therefore, we need to develop delicate exponential moment bound that ensure uniform integrability despite a potentially unbounded number of balls.

In addition, simple point processes $\omega=\sum_{k\geq 1}\delta_{z_{k}}$ with $z_{k}\in\mathbb{H}^{d}$ will be identified with locally finite point configurations $\{z_{k}\mathrel{\mathop{\mathchar 58\relax}}k\geq 1\}$. Moreover, by abuse of notation, we write $z\in\omega$ if $z$ is an atom of the counting measure $\omega$. The intensity measure of $\omega$ is denoted by $\mathbb{E}[\omega]$.

In this paper we will denote by $C>0$ a generic constant whose value might change from occurrence to occurrence. If several such constants are needed at the same time, we denote them by $C_{0},C_{1},\ldots$

Finally, since the parameters $k$ and $s_{0}$ are fixed in the rest of the manuscript, we omit them from the notation.

To prove Theorem 2.1, we partition $[0,1]^{d-1}$ into $u_{\lambda}$ congruent blocks $S_{1},\dots,S_{u_{\lambda}}$ and set $Q_{m}\mathrel{\mathop{\mathchar 58\relax}}=S_{m}\times[e^{-\lambda},\infty)$. We note that $u_{\lambda}$ is not necessarily an integer. However, to keep notation simple we do not write rounding symbols. The key step in the proof of Theorem 2.1 is to relate the empirical measure $\xi_{\lambda}/u_{\lambda}$ with the following separated point process:

Here, for a locally finite counting measure $\omega$ on $\mathbb{H}^{d}$ we put $f(x,\omega)\mathrel{\mathop{\mathchar 58\relax}}=|B_{R_{k}(x,\omega)}|_{\mathsf{hyp}}-v_{\lambda}$ with $R_{k}(x,\omega)\mathrel{\mathop{\mathchar 58\relax}}=\inf\{r\geq 0\mathrel{\mathop{\mathchar 58\relax}}\omega(B_{r}(x))\geq k+1\}$ and let $Q^{-}_{m}\subseteq Q_{m}$ be an ‘internal region’ that we will define precisely in (3.1) below. The idea behind introducing these internal regions is that we want large kNN balls to occur independently for distinct regions. In other words, this step will remove the dependence of kNN radii exceeding the threshold $r_{\lambda}(u)$, which is defined such that $|B_{r_{\lambda}(u)}|_{\mathsf{hyp}}=u+v_{\lambda}$.

Having introduced the process $\eta_{\lambda}$, the proof of Theorem 2.1 can be split up into two steps regarding exponential equivalence (with respect to the total variation distance) in the sense of [8, Definition 4.2.10]:

1. (1)

   show that the family of random measures $\eta_{\lambda}/u_{\lambda}$ is exponentially equivalent to $\zeta_{\lambda}/u_{\lambda}$, where for each $\lambda>0$, $\zeta_{\lambda}$ is a Poisson point process on $E_{0}$ whose intensity measure has density $u_{\lambda}\tau_{k}$ with respect to the Lebesgue measure;

2. (2)

   show that the family of random measures $\eta_{\lambda}/u_{\lambda}$ is exponentially equivalent to $\xi_{\lambda}/u_{\lambda}$.

The main task is to prove Propositions 3.1 and 3.2, which are the hyperbolic analogs of [16, Proposition 4.3] and [16, Propositions 4.4–4.6]. Before doing so in Sections 4 and 5, we briefly explain how to deduce Theorem 2.1 from these two results.

We conclude the present overview section, with a precise definition of the internal regions $Q^{-}_{m}$. To that end, we let $(w_{\lambda})_{\lambda>0}$ be a diverging sequence with $w_{\lambda}\in o(v_{\lambda})$. Now, for each $y\geq e^{-\lambda}$, we define

where $S^{-}_{m,y}\mathrel{\mathop{\mathchar 58\relax}}=\{x\in S_{m}\colon\mathsf{dist}_{\mathsf{euc}}(x,\partial S_{m})\geq x_{\lambda}(y)\}\subseteq{\mathbb{R}}^{d-1}$ with $x_{\lambda}(y)\mathrel{\mathop{\mathchar 58\relax}}=ye^{r_{\lambda}(w_{\lambda})}$, $\mathsf{dist}_{\mathsf{euc}}$ refers to the Euclidean distance in ${\mathbb{R}}^{d-1}$ and $\partial S_{m}$ stands for the boundary of the set $S_{m}$. The desired properties of the internal regions $Q^{-}_{m}$ are described in the following proposition.

To prove Proposition 3.3, we rely on the following distance formula taken from [10, Proposition 2.1]. We also recall that we identify points $z\in\mathbb{H}^{d}$ with pairs $z=(x,y)$ in the product space ${\mathbb{R}}^{d-1}\times(0,\infty)$.

We now prove Proposition 3.3. For the proof, we note that

for suitable constants $-\infty<C_{1}<C_{2}<\infty$; see Equation (4.1) in [21].

In this section, we prove Proposition 3.1, that is, the exponential equivalence of the empirical measures $\eta_{\lambda}/u_{\lambda}$ and a family of empirical measures of suitable Poisson point processes. We recall that $\eta_{\lambda}$ is composed of its constituents $\eta^{(m)}_{\lambda}$ in the individual boxes. The first step of the proof is therefore to proceed as in [16, Proposition 4.1] and establish a Poisson approximation result individually for each $\eta^{(m)}_{\lambda}$. We do this by showing the stronger assertion that for each $m\geq 1$ the Kantorovich-Rubinstein distance $\mathsf{dist}_{\mathsf{KR}}(\mathcal{L}(\eta^{(m)}_{\lambda}),\mathcal{L}(\zeta^{(m)}_{\lambda}))$ between the law $\mathcal{L}(\eta^{(m)}_{\lambda})$ of $\eta^{(m)}_{\lambda}$ and that of $\zeta^{(m)}_{\lambda}$ tends to zero, as $\lambda\uparrow\infty$. Here, we recall that for two point processes $\omega_{1},\omega_{2}$ on $\mathbb{H}^{d}$,

where the supremum runs over all measurable Lipschitz-$1$ functions on the space of point processes on the space $E_{0}$ with respect to the total variation distance $\mathsf{dist}_{\mathsf{TV}}$. For two measures $\mu_{1},\mu_{2}$ on $E_{0}$ the latter is given by

To prepare the proof, some elements of which are similar to the main computations in [21], we recall that for $\omega\subseteq\mathbb{H}^{d}$ locally finite, we put $f(x,\omega)\mathrel{\mathop{\mathchar 58\relax}}=|B_{R_{k}(x,\omega)}|_{\mathsf{hyp}}-v_{\lambda}$. We also define $g(x,\omega)\mathrel{\mathop{\mathchar 58\relax}}={\mathbbm{1}}\{f(x,\omega)>s_{0}\}$ and $\mathcal{S}(x,\omega)=B_{R_{k}(x,\omega)}(x)$. Then, $f$ and $g$ are localized to $\mathcal{S}$ in the sense of [4]. Namely, for every $x\in\omega$ and all $S\supseteq\mathcal{S}(x,\omega)$, we have that $g(x,\omega)=g(x,\omega\cap S),\text{ and }f(x,\omega)=f(x,\omega\cap S)\text{ if }g(x,\omega)=1.$ Moreover, $\mathcal{S}(x,\omega)$ is a so-called stopping set, in the sense that if $B_{R_{k}(x,\omega)}(x)\subseteq S$, then $B_{R_{k}(x,\omega\cap S)}(x)\subseteq S$ for every compact set $S\subseteq\mathbb{H}^{d}$. First, we set $S_{x}\mathrel{\mathop{\mathchar 58\relax}}=B_{r_{\lambda}(w_{\lambda})}(x)$. Henceforth, we put