Poisson approximation and connectivity in a scale-free random connection model

El e c t ro nic J

ou o

f Pr

ob a bi l i t y

Electron. J. Probab.26(2021), article no. 86, 1–23.

ISSN:1083-6489 https://doi.org/10.1214/21-EJP651

Poisson approximation and connectivity in a scale-free random connection model

Srikanth K. Iyer

Sanjoy Kr Jhawar

Abstract

We study an inhomogeneous random connection model in the connectivity regime. The vertex set of the graph is a homogeneous Poisson point processPsof intensitys >0 on the unit cubeS= −¹₂,¹₂d

,d≥2. Each vertex is endowed with an independent random weight distributed asW, whereP(W > w) =w^−β1[1,∞)(w),β >0. Given the vertex set and the weights an edge exists betweenx, y ∈ Ps with probability

1−exp

−_(d(x,y)/r)^ηWxWyα

,independent of everything else, where η, α >0,d(·,·)is the toroidal metric onS andr >0is a scaling parameter. We derive conditions on α, βsuch that under the scalingrs(ξ)^d=_c¹

0s logs+ (k−1) log logs+ξ+ log _k!d^αβ , ξ∈R, the number of vertices of degreekconverges in total variation distance to a Poisson random variable with meane^−ξass→ ∞, wherec0is an explicitly specified constant that depends on α, β, dand η but not on k. In particular, for k = 0 we obtain the regime in which the number of isolated nodes stabilizes, a precursor to establishing a threshold for connectivity. We also derive a sufficient condition for the graph to be connected with high probability for larges. The Poisson approximation result is derived using the Stein’s method.

Keywords: scale-free networks; Poisson point process; inhomogeneous random connection model; Poisson convergence; Stein’s method; connectivity.

MSC2020 subject classifications:Primary 60D05; 60G70, Secondary 60G55; 05C80; 05C82.

Submitted to EJP on March 30, 2020, final version accepted on May 22, 2021.

SupersedesarXiv:2002.10128v4.

1 Introduction

Social, financial and other networks such as the internet and wireless networks have been objects of much interest among researchers and practitioners in various fields in recent years. This is largely due to following stylized features observed in empirical data

*SKI has been supported in part from SERB Matrics grant MTR/2018/000496 and DST-CAS. SKJ has been supported by DST-INSPIRE Fellowship.

†Department of Mathematics, Indian Institute of Science, Bangalore, India.

E-mail:srikiyer@gmail.com(Corresponding author).

‡Department of Mathematics, Indian Institute of Science, Bangalore, India.

E-mail:sanjayjhawar@iisc.ac.in.

(See [15], and Section 1.3, in [8]). Small world effect: Typically the number of ‘links’

required to connect two distant vertices is very small (see [20]). Clustering property:

Linked vertices have mutual connections.Heavy-tailed degree distribution: It has been observed that the degree distribution is heavy-tailed with tail parameter between1and 2(see [8]).

These real-life networks naturally possess long range connections among the vertices.

The homogeneous long range percolation model onZwas first introduced by Zhang in [21]. The model can be extended to a random graph with vertex setZ^{d. Vertices}x, y are connected by an edge with probability proportional toη|x−y|^−αas|x−y| → ∞for someη, α >0. Since nearby points are connected with higher probability, this form of connection probability leads to the graph having the clustering property. For certain range of values of the parameter αa small world effect has also been observed [4].

The continuum version of the above graph called the random connection model was introduced in [16]. Such models have found applications in the study of wireless commu- nication networks, models for spread of epidemic and interactions among molecules [9].

The vertex set of the graph is a homogeneous Poisson point processPλof intensityλ >0 inR^d.x, y∈ Pλare connected by an edge with probabilityg(x−y)whereg:R^d→[0,1]. It was shown that a non-trivial phase transition occurs if and only ifgis integrable [16].

This set-up where the expected degree is finite is referred to as the thermodynamic regime. Of interest are a non-trivial threshold for percolation, the degree distribution and the graph distance.

The random graph models described above do not exhibit a heavy-tailed degree distribution. To overcome this, Deijfen et. al. in [7] proposed an inhomogeneous version of this long-range percolation model on Z^d and called it the scale-free percolation model. The inhomogeneity was introduced by assigning independent and identically distributed weightsW_xat each vertexx∈Z^drepresenting the importance of a vertex.

Given any two pointsx, y∈Z^dand corresponding weightsW_x, W_y, the probability that there is an edge between these two points equals1−exp

−^ηW_|x−y|^xW_α^y

where η, α > 0 andP(Wx> w) =w^−β1_[1,∞)(w)for someβ >0. For the graph to be non-trivial (finite degrees) one must have min{α, αβ} > d. This model is studied in great detail in [5].

Whenαβ <2dthe degree distribution is heavy tailed. Surprisingly, under this condition the graph also shows an ultra small world effect, that is, the graph distance between two far away points grows doubly logarithmically in the Euclidean distance. A non-trivial phase transition occurs in the model ifαβ >2d. A non-trivial phase transition for the above model refers to the existence of a critical value ηc ∈ (0,∞)such that for any η < ηc all components in the graph are finite and for allη > ηc, there is, with probability one, an infinite component in the graph. In addition, ifα∈(d,2d)the graph displays a small-world effect. Thus this model is rich enough to exhibit all the stylized features of real-world networks. The continuity of the percolation function which was conjectured in [7] was proved in [5]. The above results onZ^dwere extended to the continuum in [6].

The graph in the thermodynamic regime is however far from being connected. To obtain connectivity, one needs to scale the connection function suitably. As is the case with the Erd˝os-Rényi random graph, though much harder to prove, the main obstacle to connectivity in certain random geometric graphs is the presence of isolated nodes (see Chapter 13, [17], [18]). A scaling in the connectivity regime under which the number of isolated vertices converges to a Poisson random variable for the random connection model is obtained in [14]. Suppose that the graph is connected with probability approach- ing one in the absence of isolated nodes. The Poisson convergence result then yields the asymptotic probability that the graph is connected. Such a result is available only in some restricted cases for the random connection model. The soft random geometric

graph was considered by Penrose in [18]. In this model each pair ofnpoints distributed uniformly in the unit square are connected with probabilitypprovided the inter-point distance between them is at mostr. Conditions for a Poisson approximation for the number of isolated nodes and the asymptotic probability of connectivity are derived for arbitrary sequences of parameters(pn, rn). The former result is extended to a larger class of connection functions in higher dimensions. A sufficient condition for the random connection model to be connected asymptotically with high probability is derived in [11].

Another model of interest with a different type of inhomogeneity is a general random connection model studied by Penrose in [19] in the connectivity regime. Non-uniformity in this graph comes from two sources: the vertices of the graph form a Poisson point process with intensity measure sµwhere µ is a probability measure ands > 0 is a parameter. Given a realization of the point process, vertices located atx, yare connected with probabilityφ_s(x, y), whereφ_s:X×X→[0,1]is a symmetric function. Of interest are the number of nodes of a certain degree and the number of components of a given size. It is shown that the number of vertices of a fixed degree converge (ass→ ∞) to a Poisson random variable when expected number of such vertices converge ass→ ∞. A key assumption under which the result is proved is that the connection function satisfies max_x,yφ_s(x, y)<1−for some >0, that is, it stays bounded away from one. Thus it does not include the simple Gilbert’s disk model where an edge exists between any pair of nodes that are within a specified distance from each other. That the above condition does not hold for our model complicates the computations.

We shall study, for the inhomogeneous random graph considered in [6], the asymp- totic behavior of the number of isolated nodes and vertices of arbitrary degree in the connectivity regime. As is often the case, it is convenient to study the connectivity problem on the unit cube. The vertex set is assumed to be distributed according a homogeneous Poisson point processPsof intensityson the unit cube. To avoid boundary effects, we equip the space with the toroidal metricd(·,·)(to be specified below). The connection function is given by

g(x, Wx;y, Wy) = 1−exp

− ηWxWy

(d(x, y))^α

, (1.1)

whereη, α >0andP(W_x> w) =w^−β1_[1,∞)(w)for someβ >0. To stabilize the expected number of isolated nodes or vertices of fixed degree we must scale the connection function by a parameter depending on the intensity that we denote byrs. The modified connection function will be denoted by

gs(x, Wx;y, Wy) = 1−exp



− ηWxWy

_d(x,y)

rs

^α



. (1.2)

We derive an explicit expression for the scaling parameterrsand show that the number of vertices of arbitrary degree converges to a Poisson random variable under certain condition on the parameters. The Poisson convergence results are proved using the Stein’s method and thus give a bound on the rate of convergence in the total variation distance. We adapt Theorem 3.1 from [19] to account for the inhomogeneity arising from the random weights associated with the vertices of the graph. Much of the effort in proving this result lies in overcoming the challenge posed by the fact that the connection function given by (1.2) can take values arbitrarily close to one and the presence of weights on the vertices. The connectivity problem for geometric random graphs is, in general hard. Having derived the Poisson convergence for the number of isolated nodes, one would like to show that the graph is connected with high probability whenever the isolated nodes vanish. We derive a sufficient condition for the graph to be connected with high probability under mild conditions on the parameters.

2 The inhomogeneous random connection model

We now provide a precise definition of the model that is the object of our study.

We denote byS = −¹₂,¹₂d

the unit cube centered at the origin. To avoid “boundary effects” we equip S with the toroidal metric d(·,·) : S×S → R⁺∪ {0} defined by d(x, y) = inf{||x−y−z|| : z ∈ Z^d}, where || · || is the Euclidean norm. Let Ps be a Poisson point process with intensitys onS. Consider the random graph with vertex setPs. To each x ∈ Ps we associate independent random weights with probability distribution satisfying P(W > w) = w^−β1_[1,∞)(w), β >0. Given any two points inPs

along with their associated weights, the probability that there is an edge is a function of the distance between them as well as the weights. For fixedα, η >0, the probability that there is an edge between vertices (located at)x, y∈ Psis given by (1.2) independent of everything else. We denote the resulting random graph byG(P_s, r_s). The parameterη is not important for our results and can be set equal to one. For the model described earlier on the latticeZ^d, results in the thermodynamic regime such as phase transitions are stated in terms ofη. For the continuum model such results can be stated either in terms ofηor the intensity of the underlying Poisson process.

3 Statements of main results

LetDk=Dk,sbe the number of vertices of degreekinG(Ps, rs). We derive a scaling regime in whichE[Dk]converges under certain conditions on the parameters. In this regime we show thatDk converges in distribution to a Poisson random variable under some additional conditions on the parameters. For fixedξ ∈ R consider the scaling r_s≡r_s(ξ), defined by

r_s(ξ)^d= 1 c₀s

logs+ (k−1) log logs+ξ+ log αβ

k!d

, (3.1)

wherec₀=_αβ−d^θdαβη^dαΓ 1−_α^d

andθ_dis the volume ofd-dimensional unit ball. Forλ >0, letP o(λ)denote a Poisson random variable with meanλand−→^d denotes convergence in distribution.

Theorem 3.1.Consider the random graphG(Ps, r_s)with the connection functiong_sof the form (1.2). Supposeα > d,β >1and the scaling parameterr_sis as defined by (3.1).

Then for anyk≥0we have

E[Dk]→e^−ξass→ ∞. (3.2)

Note that we needmin{α, αβ}> dfor the vertices to have finite degrees. This holds since we also require that the weights have a finite mean(β >1). Our next result shows that under some additional conditions,D_k converges in distribution to a Poisson random variable. The conditionαβ >2din Theorem 3.2 is required for the degree distribution to have a finite variance [6].

Theorem 3.2.Consider the random graphG(Ps, rs)with the connection functiongsof the form (1.2). Supposeα > d,β >1and the scaling parameterr_sis as defined by (3.1).

If for anyk≥0,αβ >max{2d,(k+ 1)d,(2k+ 3)(α−d)}, then, Dk

−→d P o(e^−ξ)ass→ ∞. (3.3)

Consider now the problem of connectivity. For random geometric graphs, that is, when the connection function is the indicator function on the unit ball, it is known (see

13.37, [17]) that the graph is connected with high probability in the absence of isolated nodes. Such a result would imply that under the conditions of Theorem 3.2 withk= 0, G(Ps, rs)is connected with probability close toexp(−e^−ξ)for larges. Though such a result is out of our reach at the moment, the next result provides a sufficient condition for the graphG(Ps,·)to be connected with high probability. To state the result we need some notation. The idea is to choose the scaling parameter in such a way that there is a one hop path (a two path) from each vertex to every one of its neighbours within a distance that guarantees connectivity in the usual random geometric graph with high probability. LetE^W denote the expectation with respect to the weightW. LetB(x, r) be the unit ball of radiusrcentered atxwith respect to the Euclidean metric and the origin byO. Forγ >0, let

ˆ

rs(γ)^d :=γlogs

κs , where κ:=

Z

B(O,1)

E^Wz

1−exp

−ηWz

|z|^α

dz. (3.4) Note thatκ <∞ifβ >1andα > d. Letgˆs(x, Wx;y, Wy)be the connection probability between two pointsx, ywithrsreplaced byrˆs(γ)(≡rˆs)in (1.2). Denote the random graph with the connection functionˆg_sbyG(Ps,rˆ_s). Letθ_dbe the volume of thed-dimensional unit ball. Define the functions

T(γ) := 1−exp







−η 1 + κ

γθd

¹_d!^−α





and Q(γ) :=γT(γ). (3.5) Observe thatQ(0) = 0, Q(∞) =∞andQ⁰(γ)>0so thatρsatisfyingQ(ρ) = 1is uniquely defined.

Theorem 3.3.LetQbe as defined in (3.5) andρsatisfyQ(ρ) = 1. Supposeα > d,β >1. Then for the sequence of graphsG(P_s,ˆr_s(γ))

P(G(Ps,rˆs(γ))is connected)→1, (3.6) ass→ ∞, for allγ > ρ.

4 Proofs

In all the proofs c, c0, c1, c2,· · · and C, C0, C1, C2,· · · will denote constants whose values will change from place to place. Let d1 be the toroidal metric onAs := r⁻¹_s S defined as

d₁(x, y) := inf

z∈rs⁻¹Z^d

||x−y−z||, x, y ∈A_s. (4.1) In the proofs we often make the change of variable from r_s⁻¹x to x and r⁻¹_s y to y and hence shall refer to this as the standard change of variables. Such a change of variables transforms the connection function given by (1.2) to1−exp

−_(d^ηWxWy

1(x,y))^α

which is independent ofsand hence we shall denote it by˜g(x, Wx;y, Wy).

4.1 Proof of Theorem 3.1

Fixξ∈R^{and let}rsbe as defined in (3.1). By the Campbell-Mecke formula we have E[Dk] = E

"

X

X∈Ps

1_{{deg(X)=kinG(P}

s,rs)}

#

=sP^o(deg(O) =kinG(Ps, rs))

= sE^W0

"

1 k!

s

Z

S

E^Wx[gs(O, W0;x, Wx)]dx k

×exp

−s Z

S

E^Wx[gs(O, W0;x, Wx)]dx

. (4.2)

By the standard change of variables we obtain E[D_k] = sE^W0

"

1 k!

sr_s^d

Z

As

E^Wx[˜g(W₀;x, W_x)]dx ^k

×exp

−sr^d_s Z

A_s

E^Wx[˜g(W0;x, Wx)]dx

, (4.3)

where we have writtenE^Wx[˜g(W0;x, Wx)]forE^Wx[˜g(O, W0;x, Wx)]. We shall compute upper and lower bounds for the expression on the right in (4.3). LetD1:=B O,¹₂

. We start with the following trivial inequalities.

Z

r⁻¹_s D₁

E^Wx[˜g(W₀;x, W_x)]dx≤ Z

A_s

E^Wx[˜g(W₀;x, W_x)]dx≤ Z

R^d

E^Wx[˜g(W₀;x, W_x)]dx. (4.4) Consider the upper bound in (4.4). Using the probability density function of the weights and the fact thatd1(O, x) =|x|we obtain

Z

R^d

E^Wx[˜g(W0;x, Wx)]dx= Z

R^d

Z ∞ 1

1−exp

−ηW0w

|x|^α

β w^−β−1dw dx.

Switching to hyper-spherical coordinates then applying the Fubini’s theorem and subse- quently making the change of variablest=r^−αin the above equation yields

Z

R^d

E^Wx[˜g(W0;x, Wx)]dx = Cd

Z ∞ 0

Z ∞ 1

r^d−1

1−exp

−ηW₀w r^α

β w^−β−1dw dθ dr

= Cdβ α

Z ∞ 1

Z ∞ 0

t^−αd−1 1−e^−ηW0wt

w^−β−1dt dw, (4.5)

whereC_d= 2π

d−2

Q

i=1

Rπ

0 sin^d−1−iφ_idφ_i= ^2π

d 2

Γ(^d2). Using integration by parts the inner integral in (4.5) can be evaluated to yield

Z ∞ 0

t^−dα−1 1−e^−ηW0wt

dt = −α

d 1−e^−ηW0wt t^−αd

∞

0

+α

d(ηW0w) Z ∞

0

t^−αde^−ηW0wtdt

= α

d(ηW0w)^αd Z ∞

0

u^−dαe^−udu

= α

d(ηW0w)^αdΓ

1− d α

, (4.6)

where we have used the assumption thatα > d. Substituting from (4.6) in (4.5) we obtain Z

R^d

E^Wx[˜g(W₀;x, W_x)]dx= C_dβ

d (ηW₀)^αdΓ

1− d α

Z ∞ 1

w^αd−β−1=c₀W₀^αd, (4.7) where we have used the fact that αβ > d and have setc0 = _αβ−d^θdαβη^αdΓ 1−_α^d

since θd= ^C_d^d. We now bound the integral on the left in (4.4) from below. Proceeding as above and using (4.7) we obtain

Z

r_s⁻¹D₁

E^Wx[˜g(W0;x, Wx)]dx=c0W

d α

0 −CdβI2, (4.8) where by a use of the Fubini’s theorem we can write

I₂= Z ∞

1

Z ∞

1 2rs

h1−exp

−ηW₀w r^α

ir^d−1w^−β−1dr dw. (4.9)

To compute the inner integral on the right hand side in (4.9) we make the change of variablet=r^−αand use the assumption thatα > d. This yields

1 α

Z (2r_s)^α 0

1−e^−ηW0wt

t^−dα−1dt

= −1

d 1−e^−ηW0wt t^−dα

(2r_s)^α

0

+1

d(ηW₀w)

Z (2rs)^α 0

t^−dαe^−ηW0wtdt

≤ 1

d(ηW0w)

Z (2r_s)^α 0

t^−αddt = c1W0wr^α−d_s , (4.10) wherec1= ^αη2_d(α−d)^α−d. From (4.9), (4.10) and the fact thatβ >1we obtain

I2≤ Z ∞

1

c1βW0r^α−d_s w^−β=c2W0r^α−d_s , (4.11) wherec₂= _β−1^βc1. From (4.8), (4.11) and the fact that˜g >0we obtain

Z

rs⁻¹D1

E^Wx[˜g(W0;x, Wx)]dx≥0∨ c0W

d α

0 −c3W0r^α−d_s

, (4.12)

where c3 =Cdβc2. Forw ≥1, letΛs(w) := 0∨

c0w^dα−c3wr_s^α−d

. Substituting from (4.7) and (4.12) in (4.4) we obtain

Λ_s(W₀)≤ Z

A_s

E^Wx[˜g(W₀;x, W_x)]dx≤c₀W₀^αd. (4.13) It follows from (4.3) and (4.13) that

s k!E^W0

sr_s^dΛs(W0)^k

e^−c0srsdW

d α 0

≤E[Dk]≤ s k!E^W0

c0sr^d_sW

d α

0

^k

e^{−srdsΛs(W0)}

. (4.14) The next step is to prove that both the upper and lower bounds in (4.14) converge toe^−ξ ass→ ∞. For later use we shall state the convergence of the lower and upper bounds in somewhat greater generality as separate lemmas.

Theorem 3.1 follows from (4.14) and Lemmas 4.1–4.3 stated below. For the case k= 0we use the first assertion in Lemma 4.1 and Lemma 4.2 withj= 1. Fork≥1we use the second assertion in Lemma 4.1 and Lemma 4.3 withj= 1andm=k.

Lemma 4.1. (i) Letrsbe as defined in (3.1) withk= 0.

s→∞lim sE^W0h exp

−c0sr_s^dW₀^dαi

=e^−ξ. (4.15)

(ii) Letrsbe as defined in (3.1). Supposeα > dandk≥1, then

s→∞lim s k!E^W0h

sr^d_sΛ_s(W₀)^k exp

−c0sr_s^dW₀^dαi

=e^−ξ. (4.16) Lemma 4.2.Letrsbe as defined in (3.1) withk= 0. Supposej ≥1,α > dandαβ > jd, then ass→ ∞

s^jE^W0h

e^{−jsrdsΛs(W0)}i

=1 j

αβ d

−j+1

e^−jξ(logs)^j−1+o(1). (4.17)

Lemma 4.3.Letr_sbe as defined in (3.1) withk≥1. Supposeα > d,j≥1andm≥1, then ass→ ∞

s k!

^j E^W0

c₀sr^d_sW₀^αdjm

e^{−jsrdsΛs(W0)}

=1 j

αβ d

−j+1

e^−jξ(logs)^j−1+o(1). (4.18)

The following observations will be invoked several times in the proofs.

c0sr_s^d = logs+ (k−1) log logs+ξ+ log αβ

k!d

, c0sr_s^d0

:= d

ds c0sr^d_s

=s⁻¹(1 +o(1)). (4.19)

Proof of Lemma 4.1(i).Using the density ofW0we obtain sE^W0h

exp

−c0sr^d_sW₀^αdi

= s Z ∞

1

exp

−c0sr^d_sw^dα

βw^−β−1dw

= αβ

d s c0sr_s^dαβd

Z ∞ c0sr_s^d

e^−tt^−αβd−1dt

= αβ d

R∞

c0sr_s^de^−tt^−αβd−1dt s⁻¹(c0sr^d_s)⁻

αβ d

. (4.20)

Sincesr^d_s→ ∞ass→ ∞we can apply to L’Hospital’s rule to conclude that the limit of the last expression in (4.20) equals the limit of the ratio

αβ d

−e^−c0srds(c0sr^d_s)^−αβd−1 c0sr_s^d0

−s⁻²(c0sr^d_s)^−αβd −^αβ_d s⁻¹(c0sr_s^d)^−αβd−1(c0sr^d_s)⁰

= αβ d

s²e^−c0srsd c0sr^d_s⁰ (c₀sr^d_s) +s^αβ_d (c₀sr^d_s)⁰. Lemma 4.1(i) now follows from (4.19) withk= 0.

Proof of Lemma 4.1(ii).Substituting for the density ofW0,the expression in the limits on the left of (4.16) equals

s k!

Z ∞ 1

sr_s^d

0∨

c0w^αd −c3wr^α−d_s ^k exp

−c0sr^d_sw^αd

βw^−β−1dw

= s k!

Z Cr^−α_s 1

c₀sr^d_sw^αd −c₃swr^α_sk

exp

−c₀sr^d_sw^αd

βw^−β−1dw, (4.21) whereC=

c0

c3

_α−d^α

. By the change of variablet=c0sr^d_sw^αd the right hand side in (4.21) equals

αβ

k!ds c0sr^d_s^αβd

Z c₄s c0sr^d_s

t−c3c⁻

α d

0

t^αd s^αd−1

^k

e^−tt^−αβd−1dt

= αβ k!d

Rc₄s c0sr^d_s

t−c₅ ^t

αd

s^αd−1

k

e^−tt^−αβd−1dt s⁻¹(c0sr^d_s)^−αβd

, (4.22)

wherec4=c

α α−d

0 c⁻

d α−d

3 andc5=c3c⁻₀^αd. Again we can apply L’Hospital’s rule to conclude that the limit of the ratio on the right in (4.22) equals the limit of

αβ k!d

c4s−c5c

α d

4s^k

e^−c4s(c4s)^{−αβd −1}c4

−s⁻²(c0sr^d_s)^−αβd −^αβ_d s⁻¹(c0sr_s^d)^−αβd−1(c0sr^d_s)⁰

−αβ k!d

c₀sr_s^d−c₃sr^α_s^k

e^−c0srds(c₀sr_s^d)^−αβd−1 c₀sr^d_s0

−s⁻²(c0sr_s^d)^−αβd −^αβ_d s⁻¹(c0sr^d_s)^−αβd−1(c0sr_s^d)⁰

(4.23)

The first term in (4.23) is zero sincec₄−c₅c₄^αd = 0. The second term in (4.23) simplifies to αβ

k!d

s² c0sr^d_s−c3sr_s^αk

e^−c0srds c0sr_s^d0 (c₀sr^d_s) +s^αβ_d (c₀sr_s^d)⁰ = αβ

k!d

s² c0sr_s^dk

e^−c0srsd c0sr^d_s⁰ (c₀sr_s^d) +s^αβ_d (c₀sr^d_s)⁰

1−c3

c₀r^α−d_s ^k

. Lemma 4.1(ii) now follows from (4.19) and observing thatα > dandrs→0.

Proof of Lemma 4.2. Note that {c₀W₀^dα −c₃W₀r^α−d_s ≥ 0} = {W₀ ≤ Cr^−α_s } where C=_c

0

c3

α−d^α

. The left hand side of (4.17) equals s^jE^W0h

exp

−jc0sr^d_sW₀^αd +jc₃W₀sr^α_s

;W₀≤Cr^−α_s i

+s^jP W₀> Cr^−α_s

= s^j Z Cr^−α_s

1

exp

−jc₀sr^d_sw^αd +jc₃sr^α_sw

βw^−β−1dw+s^jC^−βr^αβ_s . (4.24) The second term in (4.24) converges to zero by (3.1) sinceαβ > jd. By the change of variablet=jc₀sr_s^dw^αd the first term on the right in (4.24) equals

αβ

d s^j jc₀sr^d_s^αβd

Z c4s jc₀sr^d_s

e^−t+c5t

α ds^−αd+1

t^−αβd−1dt

= αβ d

Rc₄s

jc₀sr^d_se^−t+c5t

α ds^−αd+1

t^−αβd−1dt s^−j(jc0sr^d_s)⁻

αβ d

, (4.25)

wherec₄=jc₀C^αd andc₅=jc₃(jc₀)^−αd. By the L’Hospital’s rule the limit of the expression on the right in (4.25) equals the limit of

αβ d

e^{−c4s+c5(c4s)}

α ds^−αd+1

(c₄s)^−αβd−1c₄

−js^−j−1(jc0sr^d_s)^−αβd −^αβ_d s^−j(jc0sr_s^d)^{−αβd −1}(jc0sr^d_s)⁰

−αβ d

e^−jc0srds(jc0sr^d_s)^−αβd−1 jc0sr_s^d0

e^c5(jc0)

α dsr^α_s

−js^−j−1(jc₀sr_s^d)^−αβd −^αβ_d s^−j(jc₀sr^d_s)^−αβd−1(jc₀sr_s^d)⁰

=C1

e^−c4s+c5c

α d

4 ss^−αβd+j(jc0sr_s^d)^αβd+1 j(jc₀sr^d_s) +s^αβ_d (jc₀sr_s^d)⁰ +αβ

d

s^j+1e^−jc0srds jc0sr^d_s⁰ e^c5(jc0)

α dsr_s^α

j(jc₀sr_s^d) +s^αβ_d (jc₀sr^d_s)⁰ , (4.26) whereC1is a constant. Sincec4−c5c

α d

4 = 0, the first term on the right in (4.26) simplifies to

C1

s^−αβd+j(jc0sr^d_s)^{αβd +1}

j(jc0sr_s^d) +s^αβ_d (jc0sr^d_s)⁰ →0ass→ ∞,

by (4.19) and the assumption thatαβ > jd. Lemma 4.2 now follows by using (4.19) in the second term on the right in (4.26) and the assumption thatα > d.

Proof of Lemma 4.3.By the observation at the beginning of the proof of Lemma 4.2, the left hand side of (4.18) equals

s k!

jZ Cr_s^−α 1

c₀sr_s^dw^dαjm

e^−jc0srdsw

d

α+jc₃sr_s^αwβw^−β−1dw +s

k!

jZ ∞ Crs^−α

c0sr^d_sw^dαjm

βw^−β−1dw. (4.27)

By changing the variablet=c0sr^d_sw^αd in the second term in (4.27) we obtain αβ

d(k!)^j s^j c0sr_s^dαβd

Z ∞ c0Cα^ds

t^{jm−αβd−1}dt= αβ (k!)^jd

R∞

c4st^{jm−αβd−1}dt s^−j (c₀sr^d_s)^−αβd

, (4.28)

wherec₄=c₀C^αd. To apply the L’Hospital’s rule differentiate the numerator and denomi- nator of the expression on the right in (4.28) to obtain

αβ d(k!)^j

−(c4s)^{jm−αβd−1}c4

−js^−j−1(c₀sr_s^d)^−αβd −^αβ_d s^−j(c₀sr^d_s)^−αβd−1(c₀sr_s^d)⁰

=c^jm−

αβ d

4

αβ d(k!)^j

s^jm−αβd+j(c0sr_s^d)^αβd+1

j(c₀sr^d_s) +s^αβ_d (c₀sr^d_s)⁰. (4.29) By making the same change of variablet=c₀sr_s^dw^dα in the first term in (4.27) we obtain

αβ

d(k!)^js^j c0sr_s^dαβd

Z c4s c0sr^d_s

e^−jt+c5jt

α ds^−αd+1

t^{jm−αβd−1}dt

= αβ d(k!)^j

Rc₄s

c0sr_s^de^−jt+c5jt

α ds^−αd+1

t^{jm−αβd−1}dt s^−j(c0sr_s^d)⁻

αβ d

, (4.30)

wherec₅=c₃c⁻₀^αd. Differentiating the numerator and denominator of the expression on the right in (4.30) we obtain

αβ d(k!)^j

e^{−c4js+c5j(c4s)}

α ds^−αd+1

(c₄s)^{jm−αβd−1}c₄−e^{−jc0srds+jc5c}

α

0dsr^α_s(c₀sr_s^d)^{jm−αβd −1} c₀sr^d_s0

−js^−j−1(c0sr^d_s)^−αβd −^αβ_d s^−j(c0sr_s^d)^{−αβd −1}(c0sr^d_s)⁰

. The above term equals to the sum of

− αβ d(k!)^jc^jm−

αβ d

4

e^−c4js+c5c

α d

4 jss^{jm−αβd +j}(c0sr^d_s)^αβd+1 j(c0sr_s^d) +s^αβ_d (c0sr^d_s)⁰

=− αβ d(k!)^j c^jm−

αβ d

4

s^jm−αβd+j(c0sr_s^d)^αβd+1

j(c₀sr_s^d) +s^αβ_d (c₀sr^d_s)⁰, (4.31) sincec4−c5c

α d

4 = 0and αβ d(k!)^j

s^j+1e^−jc0srds(c0sr^d_s)^jm c0sr^d_s0

j(c0sr^d_s) +s^αβ_d (c0sr^d_s)⁰ e^jc5c

α d 0 sr^α_s

= αβ

d(k!)^j

s^j+1e^−jc0srsd(c₀sr_s^d)^jm c₀sr^d_s0

j(c0sr_s^d) +s^αβ_d (c0sr^d_s)⁰ e^jc5c

α d

0 sr^α_s. (4.32) Adding (4.29) to the last expressions in (4.31) and (4.32) and observing that the expres- sion on the right in (4.29) cancels with the term on the right in (4.31) we obtain by the L’Hospital’s rule that the limit of the expression on the left in (4.18) equals the limit of

αβ d(k!)^j

s^j+1exp −jc0sr^d_s

(c0sr^d_s)^jm c0sr_s^d0

j(c₀sr_s^d) +s^αβ_d (c₀sr^d_s)⁰ e^jc5c

α

0dsr_s^α. (4.33)

Lemma 4.3 now follows by using (4.19) and the assumption thatα > din (4.33).

4.2 Stein’s method for poisson convergence

To prove the Poisson convergence results stated in Theorem 3.2 we adapt Theorem 3.1 from [19]. The proof of the later result which uses the Stein’s method needs to be modified to account for the inhomogeneity arising from the random weights associated with the vertices of the graph.

LetP˜sbe aW-marking ofPs. That is, supposePs=PN_s

i=1δ_Xn whereN_sis a Poisson random variable with meansandX₁, X₂, . . .is a sequence of independent uniformly dis- tributed random variables taking values inS. ThenP˜s=PNs

i=1δ_(Xn,Wn)whereW1, W2, . . . is a sequence of independent random variables with probability distribution satisfying P(W > w) =w^−β1_[1,∞)(w)for someβ >0and independent of the random variableNs

and the sequence{Xn}n≥1. We write Dk =Dk( ˜Ps) = X

y∈P_s

f(y, Wy,P˜s\ {(y, Wy)}), (4.34)

wheref(y, Wy,P˜s\ {(y, Wy)})equals one if the degree ofyequalskin the graphG(Ps∪ {y}, rs)and zero otherwise. We shall abbreviatef(y, Wy,P˜s\ {(y, Wy)})tof(y,Ps\ {y}). Note thatf(y,Ps\ {y}) =f(y,Ps). We use the former notation to avoid confusion while applying the Campbell-Mecke formula. Setp˜_s(x, W_x) =E

f(x,P_s) W_x

,x∈S. Since the underlying point process is homogeneous and the metric is toroidal,p˜depends ons, Wx

and not onx. Hence we shall writep˜s(Wx)instead ofp˜s(x, Wx). By the Campbell-Mecke formulaν :=E[Dk]satisfies

ν=E



 X

y∈Ps

f(y, Wy,P˜s\ {(y, Wy)})



=s Z

S

E^Wx[˜ps(x, Wx)]dx=s E^Wo[˜ps(Wo)]. (4.35)

LetdT V denote the total variation distance,Zν be a Poisson random variable with mean νandFD_k, FZ_ν denote the distribution functions ofDk, Zνrespectively. For any function φ:N∪ {0} →R^{, let}∆φ(i) =φ(i+ 1)−φ(i)and|| · ||∞denote thesupnorm.

Theorem 4.4.Suppose that for almost everyx∈Swe can find a random variableVx= V_x(W_x)coupled withD_k such that conditional onW_xand the event{f(x,Ps\ {x}) = 1}, 1 +Vxhas the same distribution asDk

{(x, Wx)} ∪P˜s

. Then

dT V (FD_k, FZν)≤(1∧ν⁻¹)s Z

S

E^Wx E

|Dk−Vx| Wx

p˜s(Wx)

dx. (4.36)

Proof of Theorem 4.4. Letφ : N∪ {0} → R be a bounded function. By using the definition ofDkand the Campbell-Mecke formula we have

E[Dkφ(Dk)] = E

"

X

x∈Ps

f(x,Ps\ {x})φ(Dk( ˜Ps))

#

= s

Z

S

E^Wxh Eh

f(x,P_s)φ

D_k({(x, W_x)} ∪P˜_s) W_xii

dx

= s

Z

S

E^Wxh Eh

φ

D_k({(x, W_x)} ∪P˜_s)

{f(x,P_s) = 1}, W_xi

˜ p_s(W_x)i

dx

= s

Z

S

E^Wx E

φ(V_x+ 1) W_x

˜ p_s(W_x)

dx. (4.37)

From (4.35) we have

E[νφ(Dk+ 1)] = s Z

S

E^Wx[φ(Dk+ 1)˜ps(Wx)]dx. (4.38)