See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/305483738
Joint large deviation result for empirical measures of the coloured random
geometric graphs
Article  in  SpringerPlus · December 2016
DOI: 10.1186/s40064-016-2718-z
CITATIONS READS
2 57
1 author:
Kwabena Doku-Amponsah
University of Ghana
41 PUBLICATIONS   59 CITATIONS   
SEE PROFILE
Some of the authors of this publication are also working on these related projects:
Joint Large deviation Principles for d-regular random graphs View project
All content following this page was uploaded by Kwabena Doku-Amponsah on 23 July 2016.
The user has requested enhancement of the downloaded file.
Doku‑Amponsah  SpringerPlus  (2016) 5:1140 
DOI 10.1186/s40064‑016‑2718‑z
RESEARCH Open Access
Joint large deviation result for empirical 
measures of the coloured random  
geometric graphs
Kwabena Doku‑Amponsah* 
*Correspondence:  
kdoku‑amponsah@ug.edu.gh Abstract 
Statistics Department, We prove joint large deviation principle for the  empirical pair measure and empirical 
University of Ghana,  
Box LG 115, Legon, Ghana locality measure of the near intermediate coloured random geometric graph models on 
n points picked uniformly in a d‑dimensional torus of a unit circumference. From this 
result we obtain large deviation principles for the number of edges per vertex, the degree 
distribution and the proportion of isolated vertices  for the near intermediate random 
geometric graph models.
Keywords: Random geometric graph, Erdős–Rényi graph, Coloured random 
geometric graph, Typed graph, Joint large deviation principle, Empirical pair measure, 
Empirical measure, Degree distribution, Entropy, Relative entropy, Isolated vertices
Mathematics Subject Classification: 60F10, 05C80, 68P30
Background
In this article we study the coloured geometric random graph CGRG, where n points or 
vertices or nodes are picked uniformly at random in [0, 1]d , colours or spins are assigned 
independently from a finite alphabet  and any two points with colours a1, a2 ∈  dis-
tance at most rn(a1, a2) apart are connected. This random graph models, which has the 
geometric random graph (see Penrose 2003) as special case, has been suggested by Can-
nings and Penman (2003) as a possible extension to the coloured random graph studied 
in Biggins and Penman (2009), Doku-Amponsah and Mörters (2010), Doku-Amponsah 
(2006), Bordenave and Caputo (2015), Mukherjee (2014) and Doku-Amponsah (2014).
The connectivity radius rn plays similar role as the connection probability pn in the 
coloured random graph model. Several large deviation results about the coloured ran-
dom graphs and hence Erdős–Rényi graph have been established recently. See O’Connell 
(1998), Biggins and Penman (2009), Doku-Amponsah and Mörters (2010), Doku-
Amponsah (2006, 2014), Bordenave and Caputo (2015), Mukherjee (2014).
Until recently few or no large deviation result about the CGRG have been found. 
Doku-Amponsah (2015) proved joint large deviation principle for empirical pair meas-
ure and the empirical locality measure of the CGRG, where n points are uniformly cho-
sen in [0, 1]d, colours or spins are assigned by drawing without replacement from the 
© 2016 The Author(s). This article is distributed under the terms of the Creative Commons Attribution 4.0 International License 
(http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, 
provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and 
indicate if changes were made.
Doku‑Amponsah S pringerPlus ( 2016)5 :1140 Page 2 of 16
pool of, say, nνn(a1) colours, and nωn(a1, a2) edges, a1, a2 ∈ , are randomly inserted 
among the points for some colour law νn: � → [0, 1] and edge law ωn: � ×� → [0,∞).
This article presents a full joint large deviation principle (LDP) for the empirical pair 
measure and the empirical locality measure of the CGRG. Refer to (Doku-Amponsah 
and Mörters) for similar result for the coloured random graphs. From this large devia-
tion results we obtain LDPs for graph quantities such as number of edges per vertex, the 
degree distribution and the proportion of isolated vertices of geometric random graphs in 
the intermediate case. Our results are similar to those in O’Connell (1998), Biggins and 
Penman (2009), Doku-Amponsah and Mörters (2010), Doku-Amponsah (2006, (2014), 
Bordenave and Caputo (2015) and Mukherjee (2014) for the Erdö–Renyi graph except 
that the rate functions of the LDPs in our current setting is bigger as a result of the effect 
of the geometric in the model.
As a first step in the proof of our main result, we obtain a joint LDP for the empiri-
cal colour measure and empirical pair measures for the CGRG, see Theorem  4, by 
the exponential change-of-measure techniques and coupling argument. See example 
Doku-Amponsah and Mörters (2010) or Doku-Amponsah (2006). In the next step, we 
use Biggins (2004,  Theorem  5(b)) to mix Theorem  4 and the result (Doku-Amponsah 
2015,  Theorem  2.1) to obtain the full joint LDP for empirical pair measure and the 
empirical locality measure of CGRG model. Refer to Doku-Amponsah and Mörters 
(2010) or Doku-Amponsah (2006) for further illustration of this method.
Our main motivation for studying this model are in two folds.
Independence testing  Consider CGRG which is a model for Wireless Sensor Network 
as a very big dataset comprising the typed sites and the bonds between sites. One inter-
esting question to ask is how many bits will be required to code the n sites and the bonds 
between sites with high probability? Then, an asymptotic equipartition property (AEP) 
for the WSN will answer this question and our LDP for the empirical measures of the 
CGRG will play a crucial in the prove of the AEP. Further, we can test whether a received 
codeword yn of WSN is jointly typical with a candidate sent codeword xn of WSN. The 
probability that two independent sequences (xn, yn) (xn being a codeword other than 
what was sent when yn was received) actually appear as dependent is bounded asymptot-
ically as 2−nI , where the AEP is used to obtain the bound. See Doku-Amponsah (2016) 
for more on this application.
Hypothesis testing  One of the standard problems in statistics is to decide between two 
alternative explanations for the data are observed. For example, a transmitter will send 
an information on the WSN bits by bits in communication systems. There are two pos-
sible cases for each transmission: one is that bit 0 of WSN data is sent (noted as event 
H0 ) and the other is that bit 1 of WSN data is sent (noted as event H1). In the receiver 
side, the bit y is to be received as either 0 or 1. Based on the y bit of WSN data received, 
we can make a hypothesis whether the event H0 happens (bit 0 was sent at the transmit-
ter) or the event H1 happens (i.e. bit 1 was sent at the transmitter). Of course, we may 
make mis-judgement, such as we decode that bit 0 was sent but actually bit 1 was sent. 
We need to make the probability of error in hypothesis testing as low as possible and the 
LDPs for CGRG models can help us specify the probability of error.
Doku‑Amponsah  SpringerPlus  (2016) 5:1140 Page 3 of 16
In the remainder of the paper we state and prove our LDP results. In “Statement of 
the results” section we state our LDPs, Theorem 1, Corollary 2, Corollary 3, Theorem 4, 
and Corollary 5. In “Proof of Theorem 1” section we present the proof of Theorem 4. 
In “Proof of Theorem  1” section we combine Theorem  2.1 and Doku-Amponsah 
(2014,  Theorem  2.1) to obtain the Theorem  1, using the setup and result of Biggins 
(2004) to ‘mix’ the LDPs. The paper concludes with the proofs of Corollaries 2, 3 and 5 
which are given in “Proof of Corollaries 2, 3, and 5” section.
Statement of the results
The joint LDP for empirical pair measure and empirical locality measure of CGRG
In this subsection we shall look at a more general model of random geometric graphs, 
the CGCG in which the connectivity radius depends on the type or colour or symbol or 
spin of the nodes. The empirical pair measure and the empirical locality measure are our 
main object of study.
Given a probability measure ν on  and a function rn: � ×� → (0, 1] we may define 
the randomly coloured random geometric graph or simply coloured random geometric 
graph G with n vertices as follows: Pick vertices x1, . . . , xn at random independently 
according to the uniform distribution on [0, 1]d , d ∈ N. Assign to each vertex xj colour 
σ(xj) independently according to the colour law ν. Given the colours, we join any two 
vertices xi, xj,(i �= j) by an edge independently of everything else, if
[ ]
�xi − xj� ≤ rn σ(xi), σ(xj) .
In this article we shall refer to rn(a, b), for a, b ∈  as a connection radius, and always 
consider
G = (((σ (xi), σ(xj)): i, j = 1, 2, 3, . . . , n),E)
under the joint law of graph and colour. We interpret G as coloured GRG with verti-
ces x1, . . . , xn chosen at random uniformly and independently from the vertices space 
[0, 1]2. For the purposes of this study we restrict ourselves to the near intermediate cases. 
i.e. the connection radius rn satisfies the condition nrdn (a, b) → Cd(a, b) for all a, b ∈ , 
where C 2d : � → [0,∞) is a symmetric function, which is not identically equal to zero.
For any finite or countable set  we denote by P(�) the space of probability measures, 
and by P̃(�) the space of finite measures on , both endowed with the weak topology. 
By convention we write N = {0, 1, 2, . . .}.
We associate with any coloured graph G a probability measure, the empirical colour 
measure L1 ∈ P(�), by
n
1 ∑
L1G(a) := δσ(xj)(a), for a1 ∈ �,n
j=1
and a symmetric finite measure, the empirical pair measure L2X ∈ P̃∗(�2), by
∑
L2
1
G(a, b) := [δ
2
(σ (xi),σ(xj)) + δ((σ (xj),σ(xi))](a, b), for (a, b) ∈ � .n
(i,j)∈E
Doku‑Amponsah S pringerPlus  (2016)5 :1140 Page 4 of 16
Note that the total mass the empirical pair measure is 2|E| / n. Finally we define a further 
probability measure, the empirical neighbourhood measure MG ∈ P(� × N), by
n
1 ∑
MG(a, ℓ) := δ(σ(xi),L(xj))(a, ℓ), for (a, ℓ) ∈ � × N,n
j=1
while L(x ) = (lxjj (b), b ∈ �) and lxj (b) is the number of vertices of colour b connected 
to vertex xj.
For any η ∈ P(� × �N )we denote by η1 the -marginal of η and for every 
(b, a) ∈ � ×�, let η2 be the law of the pair (a,  l(b)) under the measure η. Define the 
measure (finite), �η(·, ℓ), l(·)� ∈ P̃(� ×�) by
∑
H2(η)(b, a) := η2(a, l(b))l(b), for a, b ∈ �
l(b)∈N
and write H1(η) = η1. We define the function H: P(� × �N ) → P(�)× P̃(� ×�) by 
H(η) = (H1(η),H2(η)) and note that H(MG) = (L1G ,L2G). Observe that H1 is a continu-
ous function but H2 is discontinuous in the weak topology. In particular, in the summa-
∑
tion l(b)∈ η2(a, l(b))l(b) the function l(b) may be unbounded and so the functional N
η → H2(η) would not be continuous in the weak topology. We call a pair of measures 
(ω, η) ∈ P̃(� ×�)× P(� × �N ) sub-consistent if
H2(η)(b, a) ≤ ω(b, a), for all a, b ∈ �, (1)
and consistent if equality holds in (1). For a measure ω ∈ P̃ (�2∗ ) and a measure 
ρ ∈ P(�), we recall from (Doku-Amponsah and Mörters 2010) the rate function
H1(ω � ρ) := H(ω �Cdρ ⊗ ρ)+ �Cdρ ⊗ ρ� − �ω�,
where the measure Cdρ ⊗ ρ ∈ P̃(� ×�) is defined by Cdρ ⊗ ρ(a, b) = Cd(a, b)ρ(a)ρ(b) 
for a, b ∈ . It is not hard to see that H1(ω � ρ) ≥ 0 and equality holds if and only if 
ω = Cdρ ⊗ ρ.
For every (ω, η) ∈ P̃∗(� ×�)× P(� × N) define a probability measure 
(ω,η)
Qpoi  on 
 × N by
( )
∏
(ω,η) −
ω(a,b) 1 ω(a, b ℓ(b))
Qpoi (a, ℓ) := η1(a) e
η1(a) , for a ∈ �, ℓ ∈ N.
ℓ(b)! η1(a)
b∈�
We assume d ∈ N and write

πd/2

� � if d ≥ 2
(d+2)
�(d) = Ŵ 2

1 if d = 1,
where Ŵ is the gamma function. We now state the principal theorem in this section the 
LDP for the empirical pair measure and the empirical locality measure.
Theorem  1 Suppose that G is a CRGG with colour law ν and connection radii 
rn:  × → [0, 1] satisfying nrdn (a, b) → Cd(a, b) for some symmetric function 
Doku‑Amponsah  SpringerPlus  (2016)5 :1140 Page 5 of 16
C: � ×� → [0,∞) not identical to zero. Then, as n → ∞, the pair (L2G , MG) satisfies an 
LDP in P̃∗(� ×�)× P(� × N) with good rate function
{
(ω,η)
H(η �Q )+H(η � ν)+ 1H (ω�η ) if (ω, η) consistent and η = ω ,
J (ω, η) = poi 1 2 2 1 1 2
∞ otherwise.
H2(ω�η1) = H1(ω � η1)− �ω� log�(d)+ (�(d)− 1)�Cdη1 ⊗ η1�.
Remark 1 Note that the first three terms of the rate function is the same as the rate 
function of Doku-Amponsah and Mörters (2010, Theorem 2.1). Additionally, the extra 
term 12 (−�ω� log�(d)+ (�(d)− 1)�Cdη1 ⊗ η1�) is positive and is as a result of the 
geometric [0, 1]d we have incorporated in the model. Moreover, on typical CGRG we 
have, η1 = ν, ω = �(d)C η1 ⊗ η1 and
ℓ(b)
∏
η(a, ℓ) = ν(a) e−�(d)C (a,b)ν(b)
(�(d)Cd(a, b)ν(b))d , for all (a, ℓ) ∈ � × N.
ℓ(b)!
b∈�
Hence, for some ε we P{|MG − η� ≥ ε} → 0 as n → ∞.
We write
c 1
1(δ) := (�(d)− 1) − �δ� log�(d)
2 2
Corollary 2 Suppose D is the degree distribution of the random graph G(n, rn), where 
the connectivity radius rn ∈ (0, 1] satisfies nrdn → c ∈ (0,∞). Then, as n → ∞, D satisfies 
an LDP in the space P(N ∪ {0}) with good rate function
{
[ ( ) ]
H d � q + 1 � � log �δ�( ) 1 c
2(δ) =
�δ� 2 δ c − 2 �δ� + 2 + 1(δ), if �δ� < ∞,
∞ if �δ� = ∞, (2)
∑
where qk is a poisson distribution with parameter k,  and �δ� := ∞m=0mδ(m).
This rate function 2 compares very well with the rate function of Doku-Amponsah 
and Mörters (2010, Corollary 2.2) with the extra term 1 accounting for the geometric 
effect on the CGRG model.
Next we give a similar result as in O’Connell (1998), the LDP for the proportion of iso-
lated vertices of the RGG.
[ ( ) ]
1 (�(d)− 1)c(1− y))
ξ1(y) = (�(d)− 1)cy(1− y/2)+ (1− y) log −
�(d) 2
Corollary 3 Suppose D is the degree distribution of the random graph G(n, rn), where 
the connectivity radius rn ∈ (0, 1] satisfies nrdn → c ∈ (0,∞). Then, as n → ∞, the pro-
portion of isolated vertices, D(0) satisfies an LDP in [0, 1] with good rate function
[ ]
( c ) (a− c(1− y))2
ξ2(y) = y log y+ cy(1− y/2)− (1− y) log − + ξ1(y),
a 2c(1− y)
where a = a(y, d) is the unique positive solution of 1− e−a = �(d)ca (1− y).
Doku‑Amponsah S pringerPlus ( 2016) 5:1140 Page 6 of 16
From Corollary 3 we deduce that on a typical random geometric graphs the number of 
isolated vertices will grow like ne−�(d)c. Thus, as n → ∞, the number of isolated verti-
ces in the geometric random graphs converges to ne−�(d)c in probability. Again, the rate 
function ξ2 above compares very well with the result of O’Connell (1998) with the extra 
term ξ1 accounting for the influence of the geometric plane [0, 1]d on the model.
The joint LDP for the empirical colour measure and empirical pair measure of CGRG
Theorem  4 Suppose that G is a CGRG with colour law ν and connection radii 
r 2n:  → [0, 1] satisfying nrdn (a, b) → Cd(a, b) for some symmetric function 
Cd : �
2 → [0,∞) not identical to zero. Then, as n → ∞, the pair (L1X ,L
2
X ) satisfies an 
LDP in P(�)× P̃∗(�2) with good rate function
1
I(η1,ω) = H(η1 � ν)+ H2(ω � η1), (3)
2
where the measure Cη1 ⊗ η1 ∈ P̃∗(� ×�) is defined by Cη1 ⊗ η1(a, b) =
Cd(a, b)η1(a)η1(b) for a, b ∈ .
Further, we state a corollary of Theorem 4 below.
Corollary 5 Suppose that Gis a CGRG graph with colour law ν and connection 
radii rn: 2 → [0, 1] satisfying nrdn (a, b) → Cd(a, b) for some symmetric function 
Cd : �
2 → [0,∞) not identical to zero. Then, as n → ∞, the number of edges per vertex 
|E| / n of Gsatisfies an LDP in [0,∞) with good rate function
{ }
ζ(x) = x log x − x + inf ψ(y)− x log(y)+ y ,
y>0
where ψ(y) = inf H(η1 � ν) over all probability vectors η1 with 1 T2�(d)η1 Cη1 = y.
Remark 2 By taking Cd(a, b) = c one will obtain ψ(y) = 0 for y = �(d)2 c, and ψ(y) = ∞ 
otherwise, which establishes that |E| / n obeys an LDP in [0,∞) with good rate function
{ ( ) }
1 1
ζ(x) = x log x − x + inf ψ(y)− x log y + y ,
y>0 2 2
where �(d)c = y.
Proof of Theorem 4
Change‑of‑measure
For any two points U1 and U2 uniformly and independently chosen from the space [0, 1]d 
write
F(t) := P{�U1 − U2� ≤ t}.
Further, given a function f̃ :  → R and a symmetric function g̃ : 2 → R, we define the 
constant U  by
f̃
∑
U = log ef̃ (a)ν(a),
f̃
a∈�
Doku‑Amponsah  SpringerPlus ( 2016)5 :1140 Page 7 of 16
and the function h̃ : 2n → R by
[ ]
( )−n
h̃n(a, b) = log 1− F(rn(a, b))+ F(rn(a, b))e
g̃(a,b) , (4)
for a, b ∈ . We use f̃  and g̃ to define (for sufficiently large n) a new coloured random 
graph as follows:
•  To the n points x1, x2, . . . , xn picked independently and uniformly in [0, 1]d we assign 
colours from  independently and identically according to the colour law ν̃ defined 
by 
f̃ (a)−B
ν̃(a) = e f̃ ν(a).
•  Given any two points xu, xv , with xu carrying colour a and xv carrying colour b, we 
connect vertex xu to vertex xv with probability 
F(r (a, b))eg̃(a,b)n
F(r̃n(a, b)) = .
1− F(rn(a, b))+ F(r g̃(a,b)n(a, b))e
We denote the transformed law by P̃. We observe that ν̃ is a probability meas-
ure and that P̃ is absolutely continuous with respect to P as, for any coloured graph 
G = ((σ (xj): j = 1, 2, 3, . . . , n),E),
dP̃ ∏ ν̃(σ (x )) ∏u F(r̃n(σ (xu), σ(xv))) ∏ 1− F(r̃n(σ (xu), σ(xv)))
(G) =
dP ν(σ (xu)) F(rn(σ (xu), σ(xv))) 1− F(rn(σ (xu), σ(xv)))u∈V (u,v)∈E (u,v)�∈E
∏ ν̃(σ (xu)) ∏ F(r̃n(σ (xu), σ(xv))) n− nF(rn(σ (xu), σ(xv)))
= ×
ν(σ (x )) F(r (σ (x ), σ(x ))) n− nF(r̃ (σ (x ), σ(x )))
u∈V u n u v n u v(u,v)∈E
∏ n− nF(r̃n(σ (xu), σ(xv)))
×
n− nF(rn(σ (xu), σ(xv)))
(u,v)∈E
∏ ∏ ∏
f̃ (σ (x ))−U
= e u f̃ eg̃(σ (xu),σ(xv))
1
e n h̃n(σ (xu),σ(xv))
u∈V (u,v)∈E (u,v)∈E
( 〈 〉 〈 〉 〈 〉)
〈 〉
1 1 1 1= exp n LG , f̃ − U + n L
2 , g̃ + n L1 1 1
f̃ G G
⊗ LG , h̃n − L�, h̃n ,2 2 2
(5)
where
1 1
∑
L� = δ(σ(xu),σ(x )).n u
u∈V
∑ ∑
We write �g ,ω� := a,b∈� g(a, b)ω(a, b) for ω ∈ P̃(�2), and �f , ρ� := a∈� f (a)ρ(a) for 
ρ ∈ P(�), and note that
F(rn(a, b)) = �(d)r
d
n (a, b), for all a, b ∈ �
2.
Doku‑Amponsah  SpringerPlus ( 2016)5 :1140 Page 8 of 16
i.e. the volume of a d-dimensional (hyper)sphere with radius r(a,  b) satisfying 
nrdn (a, b) → Cd(a, b).
The following lemmas will be useful in the proofs of main Lemmas.
Lemma 1 (Euler’s lemma) If nrdn (a, b) → Cd(a, b) for every a, b ∈ , then
lim [1+ αF(rn(a, b))]
n = eα�(d)Cd(a,b), for all a, b ∈ � and α ∈ R. (6)
n→∞
Proof Observe that, for any ε > 0 and for large n we have
[ ] [ ]
α�(d n n)Cd(a, b)− ε α�(d)Cd(a, b)+ ε
1+ ≤ [1+ αF(rn(a, b))]
n ≤ 1+ ,
n n
by the point-wise convergence. Hence by the sandwich theorem and Euler’s formula we 
get (6).  
We write
{ }
P(n)(ω) := 1P LG = ω .
Lemma 2 The family of measures (Pn: n ∈ N) is exponentially tight on P(�).
Proof We use coupling argument, see the proof of Doku-Amponsah and Mörters 
(2010, Lemma 5.1) to show that, for every θ > 0, there exists N ∈ N such that
1
lim sup P{|E| > nN } ≤ −θ .
n→∞ n
To begin, let c(d) > maxa,b∈� Cd(a, b) > 0 and nrdn (c) → c(d). Using similar coupling 
arguments as in see the proof of Doku-Amponsah and Mörters (2010, Lemma 5.1), we 
can define, for all sufficiently large n,  a coloured random graph X̃ with vertices x1, . . . , xn 
chosen uniformly from the vertices space [0, 1]d , colour law η and connectivity probabil-
{ }
ity pn = P �xi − xj� ≤ rn(c) = �(d)rdn , for all i �= j such that any edge present in G is 
also present in X̃ . Let |Ẽ| be the number of edges of X̃ . Using the binomial formula and 
Euler’s formula, we have that
n(n−1)
2 ( )
[ ]
∑
−nl |Ẽ| −nl k n(n− 1)/2 k n(n−1)/2−k
P{|Ẽ| ≥ nl} ≤ e E e = e e (pn) (1− pn)
k
k=0
= e−nl(1− p + ep )n(n−1)/2 ≤ e−nlenc�(d)(e−1+o(1))n n ,
where we used npn = �(d)nrdn → �(d)c in the last step. Now given θ > 0 choose 
N ∈ N such that N > θ +�(d)c(e − 1) and observe that, for sufficiently large n, 
P{|E| ≥ nN } ≤ P{|Ẽ| ≥ nN } ≤ e−nθ ,
which implies the statement.  
Proof of the upper bound in Theorem 4
We denote by C1 the space of functions on  and by C2 the space of symmetric functions 
on 2, and define
Doku‑Amponsah S pringerPlus ( 2016) 5:1140 Page 9 of 16
�
�
� �
Î(η1,ω) = sup f (a)− Uf η1(a)
f ∈C1 a∈�
g∈C2

1 � �(d ) �
+ g(a, b)ω(a, b)+ (1− eg(a,b))Cd(a, b)η1(a)η1(b)
2 2 
a,b∈� a,b∈�
for (η1,ω) ∈ P(�)× P 2∗(� )
Lemma 3 For each closed set G ⊂ P(�)× P̃∗(�2), we have
1 {( ) }
lim sup log L1 ,L2P G G ∈ F ≤ − inf Î(η1,ω).
n→∞ n (η1,ω)∈F
Proof First let f̃ ∈ C1 and g̃ ∈ C2 be arbitrary. Define β̃: �2 → R by
β̃(a, b) = �(d)(1− eg̃(a,b))Cd(a, b).
Observe that, by Lemma 1, β̃(a, b) = limn→∞ h̃n(a, b) for all a, b ∈ , recalling the defi-
nition of h̃n from (4). Hence, by (5), for sufficiently large n,
{ }
∫
1 1 2 1 1 1
emaxa∈� |β̃(a,a)| �
1L1 , h̃n� n�L ,f̃−U �+n� L ,g̃�+n� L ⊗L ,h̃ �≥ e 2 � dP̃ = E e G f̃ 2 G 2 G G n ,
∑
where L1� =
1
n u∈V δ(σ(xu),σ(xu)) and therefore,
〈 〉 〈 〉 〈 〉
{ }
1 n 1 ,f̃−U +n 1 1L L2 ,g̃ +n 1 1
lim sup logE e G f̃ 2 G 2
L ⊗L ,h̃
G G n ≤ 0. (7)
n→∞ n
Given ε > 0 let Îε(η1,ω) = min{Î(η1,ω), ε−1} − ε. Suppose that (η1,ω) ∈ G and observe 
that Î(η1,ω) > Îε(η1,ω). We now fix f̃ ∈ C1 and g̃ ∈ C2 such that
1 1
�f̃ −U , η1� + �g̃ ,ω� + �β̃ , η1 ⊗ η1� ≥ Îε(η1,ω).f̃ 2 2
As  is finite, there exist open neighbourhoods B1η  and B2ω of η1 1,ω such that
{ }
1 1
inf �f̃ − U , η1� + �g̃ , ω̃� + �β̃ , ηf̃ 1 ⊗ η1� ≥ Îε(η1,ω)− ε.
η̃ 11∈Bη 2 21
ω̃∈B2ω
Using Chebyshev’s inequality and (7) we have that
1 {( ) }
lim sup log L1P G ,L
2
G ∈ B
1
η × B
2
n 1 ωn→∞
〈 〉 〈 〉 〈 〉
{ }
1 n L1 ,f̃−U +n 1L2 ,g̃ +n 1L1 ⊗L1 ,h̃n
≤ lim sup logE e G f̃ 2 G 2 G G − Î (8)ε(η1,ω)+ ε
n→∞ n
≤ −Îε(η1,ω)+ ε.
Now we use Lemma 2 with θ = ε−1, to choose N (ε) ∈ N such that
1
lim sup log P{|E| > nN (ε)} ≤ −ε−1. (9)
n→∞ n
Doku‑Amponsah  SpringerPlus  (2016) 5:1140 Page 10 of 16
For this N (ε), define the set KN (ε) by
{ }
K 2N (ε) = (η1,ω) ∈ P(�)× P̃∗(� ): �ω� ≤ 2N (ε) ,
and recall that �L2G� = 2|E|/n. The set KN (ε) ∩ F  is compact and therefore may be cov-
ered by finitely many sets B1 2η × B , r = 1, . . . ,m with (η ,ω ) ∈ F  for r = 1, . . . ,m. 1,r ωr 1,r r
Consequently,
m
{( ) } {( ) } {( ) }
∑
L1 ,L2 ∈ F ≤ L1 ,L2 1P G G P G G ∈ Bη × B
2
ω + L
1
P G ,L
2
G �∈ K .1,r r N (ε)
r=1
We may now use (8) and (9) to obtain, for all sufficiently small ε > 0,
( )
1 {( ) } 1 {( ) }m
lim sup log 1 2P LG ,LG ∈ F ≤ max lim sup log
1
P LG ,
2 1 2 −1
LG ∈ Bη × B1,r ω ∨ (−ε)r
n→∞ n r=1 n→∞ n
( )
≤ − inf −1Îε(η1,ω)+ ε ∨ (−ε) .
(η1,ω)∈G
Taking ε ↓ 0 we get the desired statement.  
Next, we express the rate function in term of relative entropies, see for example 
Dembo and Zeitouni (1998, 2.15), and consequently show that it is a good rate function. 
Recall the definition of the function I from Theorem 4.
Lemma 4 (i) Î(η1,ω) = I(η1,ω), for any (η1,ω) ∈ P(�)× P̃∗(�2),
(ii) I is a good rate function and
(iii) H2(ω � η1) ≥ 0 with equality if and only if ω = �(d)Cdη1 ⊗ η1.
Proof (i) Suppose that ω �≪ �(d)Cdη1 ⊗ η1. Then, there exists a0, b0 ∈  with 
Cη1 ⊗ η1(a0, b0) = 0 and ω(a 20, b0) > 0. Define ĝ :  → R by
[ ]
ĝ(a, b) = log K (1(a ,b )(a, b)+ 1 (a, b))+ 1 , for a, b ∈ � and K > 0.0 0 (b0,a0)
For this choice of ĝ and f = 0 we have
∑ ∑ ∑
( ) 1 �(d)
f (a)−Uf η1(a)+ ĝ(a, b)ω(a, b)+ (1− e
ĝ(a,b))Cd(a, b)η1(a)η1(b)
2 2
a∈� a,b∈� a,b∈�
�(d)
≥ log(K + 1)ω(a0, b0) → ∞, for K ↑ ∞.
2
Now suppose that ω ≪ Cη1 ⊗ η1. We have
� � � �
� �
Î(η1,ω) = sup f (a)− log e
f (a)ν(a) η1(a)
f ∈C1 a∈� a∈�
�(d) �
+ Cd(a, b)η1(a)η1(b)
2
a,b∈�
 
1  � �
+ sup g(a, b)ω(a, b)−�(d) eg(a,b)Cd(a, b)η1(a)η1(b) .
2 g∈C  2 a,b∈� a,b∈�
By the variational characterization of relative entropy, the first term equals H(η1 ‖ ν). By 
the substitution g Cdη1⊗ηh = �(d)e 1 the last term equals
ω
Doku‑Amponsah S pringerPlus ( 2016) 5:1140 Page 11 of 16
[ ( ) ]
∑ ω(a, b)
sup log h(a, b) − h(a, b) ω(a, b)
h∈C �(d)Cd(a, b)η1(a)η1(b)2
h≥0 a,b∈�
( )
∑ ∑
( ) ω(a, b)
= sup log h(a, b)− h(a, b) ω(a, b)+ log ω(a, b)
h∈C �(d)Cd(a, b)η1(a)η1(b)2
≥0 a,b∈� a,b∈�h
= −�ω� +H(ω ��(d)Cdη1 ⊗ η1),
where we have used supx>0 log x − x = −1 in the last step. This yields that 
Î(η1,ω) = I(η1,ω).
(ii) Recall from (3) and the definition of H2 that I(η1,ω) = H(ω � ν)+ 
1
H(ω ��(d)Cdη1 ⊗ η +
�(d)
1) �Cdη1 ⊗ η1� −
1 �ω� . All summands are continuous in 
2 2 2
η1,ω and thus I is a rate function. Moreover, for all α < ∞, the level sets {I ≤ α} are con-
tained in the bounded set {(η1,ω) ∈ P(�)× P̃ (�2∗ ): H2(ω � η1) ≤ α} and are therefore 
compact. Consequently, I is a good rate function.
(iii) Consider the nonnegative function ξ(x) = x log x − x + 1, for x > 0, ξ(0) = 1, 
which has its only root in x = 1. Note that
{ ∫
ξ ◦ g d(�(d)Cdω ⊗ ω) if g :=
dω ≥ 0 exists,
H (ω � η ) = d(�(d)C2 1 dη1⊗η1) (10)
∞ otherwise.
( )
Hence H2(ω � η1) ≥ 0, and if ω = �(d)Cdη1 ⊗ η1, then ξ dω = ξ(1) = 0d  (�(d)Cdη1⊗η1)
and so H2(�(d)Cdη1 ⊗ η1 �ω) = 0. Conversely, if H2(ω �ω) = 0, then ω(a, b) > 0 
implies Cdη1 ⊗ η1(a, b) > 0, which then implies ξ ◦ g(a, b) = 0 and further g(a, b) = 1. 
Hence ω = �(d)Cdη1 ⊗ η1, which completes the proof of (iii).  
Proof of the lower bound in Theorem 4
We obtain the lower bound of Theorem 4 from the upper bound as follows:
Lemma 5 For every open set O ⊂ P(�)× P̃ (�2∗ ), we have
1 {( ) }
lim inf log P L1 ,L2 ∈ O ≥ − inf I(η1,ω).
n→∞ n G G (η1,ω)∈O
Proof Suppose (η1,ω) ∈ O, with ω ≪ �(d)Cdη1 ⊗ η1. Define f̃ω: � → R by
{
log η1(a) , if η (a) > 0,
f̃ω(a) = ν(a)
1
0, otherwise.
and g̃ω: �2 → R by
{
log ω(a,b), , if ω(a, b) > 0,g̃ �(d)C (a b)η (a)η (b)ω(a, b) = d 1 1
0, otherwise.
In addition, we let β̃ω(a, b) = �(d)Cd(a, b)(1− eg̃ω(a,b)) and note that 
β̃ω(a, b) = limn→∞ h̃ω,n(a, b), for all a, b ∈  where
[ ]
( )−n
h̃ω,n(a, b) = log 1− F(rn(a, b))+ F(rn(a, b))e
g̃ω(a,b) .
Doku‑Amponsah  SpringerPlus ( 2016)5 :1140 Page 12 of 16
Choose B1η ,B2ω open neighbourhoods of η1,ω, such that B1 ,×B2η ω ⊂ O and for all 1 1
(ω̃, ω̃) ∈ B1 2η × B1 ω
1 1 1 1
�f̃ω, η1� + �g̃ω,ω� + �β̃ω, η1 ⊗ η1� − ε ≤ �f̃ω, η̃1� + �g̃ω, ω̃� + �β̃ω, η̃1 ⊗ η̃1�.
2 2 2 2
We now use P̃, the probability measure obtained by transforming P using the functions 
f̃ω, g̃ω. Note that the colour law in the transformed measure is now η1, and the connec-
tivity radii r̃n(a, b) satisfy
n r̃dn (a, b) → ω(a, b)/(η1(a)η1(b)) =: C̃d(a, b), as n → ∞.
Using (5), we obtain
� �
�� � �
1 , 2
dP
P LG LG ∈ O ≥ Ẽ (G)
� �
1 � �
L1 ,L2 ∈B1 ×B2dP̃ G G η1 ω
 
 
� � �
= e−f̃ω(σ(xu)) e−g̃ω(σ(xu),σ(xv))
1
e− n h̃ω,n(σ (xu),σ(xv))Ẽ � �1 � �
L1 ,L2 ∈B1η ×B
2
 G G 1 ω u∈V (u,v)∈E (u,v)∈E
� � � �
� �
� � � �
−n L1 ,f̃ −n 1 L2 ,g̃ −n 1 L1 ⊗L1 ,g̃ + 1 L1
G ω 2 G ω 2 G G ω 2 � ,h̃ω,n= Ẽ e × � �1 � �
L1 ,L2 ∈B1 2
G G η ×B1 ω
� �
1 1 �� � �
≥ exp −n�f̃ 1 2 1 2ω ,ω� − n �g̃ω ,ω� − n �β̃ω , η1 ⊗ η1� +m− nε × P̃ L
2 2 G
,LG ∈ Bη × B1 ω ,
where m := 0 ∧mina∈� β̃(a, a). Therefore, by (6), we have
1 {( ) }
lim inf log 1 2P LG ,L ∈ On→∞ n G
1 1 1 {( ) }
≥ −�f̃ω ,ω� − �g̃ω ,ω� − �β̃ω , η1 ⊗ η1� − ε + lim inf log
1 , 2P̃ LG LG ∈ B
1 2
2 2 n→∞ n η
× B
1 ω
.
The result follows once we prove that
1 {( ) }
lim inf log L1 ,L2 ∈ B1P̃ × B2 = 0. (11)
n→∞ n G G η1 ω
We use the upper bound (but now with the law P replaced by P̃) to prove (11). Then we 
obtain
1 {( ) ( )c}
lim sup log 1 2 1 2P̃ LG ,LG ∈ Bη × Bω ≤ − inf Ĩ(ρ̃, ω̃),
n→∞ n (ρ̃,ω̃)∈F̃
where F̃ = (B1 × B2 )cη ω  and Ĩ(ρ̃, ω̃) := H(ω̃ �ω)+
1
2H2(ω̃ � ρ̃). It therefore suffices to 1
show that the infimum is positive. Suppose for contradiction that there exists a sequence 
(ρ̃n, ω̃n) ∈ F̃  with Ĩ(ρ̃n, ω̃n) ↓ 0. Then, because Ĩ is a good rate function and its level sets 
are compact, and by lower semi-continuity of the mapping (ρ̃, ω̃) �→ Ĩ(ρ̃, ω̃) , we can con-
struct a limit point (ρ̃, ω̃) ∈ F̃  with Ĩ(ρ̃, ω̃) = 0. By Lemma 4 this implies H(ρ̃ � η1) = 0 
and H2(ω̃ � η1) = 0, hence ρ̃ = η1, and ω̃ = C̃dη1 ⊗ η1 = ω contradicting (ρ̃, ω̃) ∈ F̃ .  
Proof of Theorem 1
For any n ∈ N we define
Doku‑Amponsah S pringerPlus ( 2016) 5:1140 Page 13 of 16
{ }
Pn(�) := ρ ∈ P(�): nρ(a) ∈ N for all a ∈ � ,
{ }
n
P̃n(� ×�) := ω ∈ P̃∗(� ×�): ω(a, b) ∈ N for all a, b ∈ � .
1+ 1{a = b}
We denote by �n := Pn(�)× P̃n(� ×�) and � := P(�)× P̃∗(� ×�). With
∣
(n) { }
P(ρ ,ω )(ηn) := P MG = η
∣
n H(MG) = (ρn,ωn) ,n n
{( ) }
P(n)(ρn,ωn) := P L
1
G ,L
2
G = (ρn,ωn)
the joint distribution of L1G ,L2G and MG is the mixture of 
(n)
P(ρ ,ω ) with P
(n)(ρn,ωn) n n
defined as
n (n)dP̃ (ρn,ωn, ηn) := dP (η ) dP
(n)
(ρ ,ω ) n (ρn,ωn). (12)n n
Biggins (2004, Theorem 5(b)) gives criteria for the validity of large deviation principles 
for the mixtures and for the goodness of the rate function if individual large deviation 
principles are known. The following three lemmas ensure validity of these conditions.
We recall from Lemma 6 that the family of measures (Pn: n ∈ N) is exponentially tight 
on 
Lemma 6 (Doku-Amponsah and Mörters 2010) The family of measures (P̃n: n ∈ N) is 
exponentially tight on �× P(� × N).
Define the function
J̃ : �× P(� × N) → [0,∞], J̃ ((η1,ω), η) = J̃(η1,ω)(η),
where
{
( )
(ω,η)
H η �Qpoi if (ω, η) is consistent and η1 = ωJ̃(η1,ω)(η) =
2 (13)
∞ otherwise.
Lemma 7 (Doku-Amponsah and Mörters 2010) J̃  is lower semi-continuous.
By Biggins (2004,  Theorem  5(b)) the two previous lemmas and the large deviation 
principles we have established Theorem 2.2 and Doku-Amponsah (2015, Theorem 2.1) 
ensure that under (P̃n) the random variables (ρn,ωn, ηn) satisfy a large deviation princi-
ple on P(�)× P̃∗(� ×�)× P(� × N) with good rate function
{ ( )
1 (ω,η)
H(η1 � ν)+ H2(ω ��)+H η �Q , if (ω, η) is consistent and η1 = ω2,
Ĵ (η 2 poi1,ω, η) =
∞, otherwise.
By projection onto the last two components we obtain the large deviation prin-
ciple as stated in Theorem  1 from the contraction principle, see e.g. Dembo et  al. 
(2005, Theorem 4.2.1).
Doku‑Amponsah  SpringerPlus ( 2016) 5:1140 Page 14 of 16
Proof of Corollaries 2, 3, and 5
We derive the theorems from Theorem  1 by applying the contraction principle, see 
e.g.  Dembo and Zeitouni (1998,  Theorem  4.2.1). In fact Theorem  1 and the contrac-
tion principle imply a large deviation principle for D. It just remains to simplify the rate 
functions.
Proof of Theorem 2
Note that, in the case of an uncoloured RGG graphs, the function C degenerates to a 
constant  c, L2G = |E|/n ∈ [0,∞) and MG = D ∈ P(N ∪ {0}). Theorem  1 and the con-
traction principle imply a large deviation principle for D with good rate function
2(δ) = inf{J (x, δ): x ≥ 0}
{ }
1 1 1 1
= inf H(δ � qx)+ x log x − x log�(d)c + �(d)c − x: �δ� ≤ x ,
2 2 2 2
which is to be understood as infinity if 〈d〉 is infinite. We denote by x (δ) the expression 
inside the infimum. For any ε > 0, we have
�δ�+ε �δ�
2 (δ)− 2 (δ)
( )
ε �δ� − ε �δ� ε �δ� ε �δ� − ε −ε ε �δ�
= + log + log ≥ + + log > 0,
2 2 �δ� + ε 2 �(d)c 2 2 �δ� 2 �(d)c
so that the minimum is attained at x = �(d)�δ�.
Proof of Corollary 3
Corollary 3 follows from Theorem 2 and the contraction principle applied to the con-
tinuous linear map G: P(N ∪ {0}) → [0, 1] defined by G(δ) = δ(0). Thus, Theorem  2 
implies the large deviation principle for G(D) = W  with the good rate function 
ξ2(y) = inf{2(δ): δ(0) = y, �δ� < ∞}. We recall the definition of x2 and observe that 
ξ2(y) can be expressed as
{ }
∞
1 b2 ∑ δ(k)
ξ2(y) = inf inf c + y log y+ + δ(k) log − b(1− y) .
b≥0 d∈P(N∪{0}) 2 2�(d)c qb(k)
δ(0)=y,�(d)c�δ�=b2 k=1
Now, using Jensen’s inequality, we have that
∞
∑ δ(k) (1− y)
δ(k) log ≥ (1− y) log ,
q k −b (14)b( ) (1− e )
k=1
with equality if (1−y)δ(k) = −b qb(k), for all k ∈ N. Therefore, we have the inequality(1−e )
inf{2(δ): δ(0)
{ }
1 b2 (1− y)
= y, �δ� < ∞} ≥ inf c + y log y+ + (1− y) log − b(1− y): b ≥ 0 .
2 2�(d)c (1− e−b)
Let y ∈ [0, 1]. Then, the equation a(1− e−a) = �(d)c(1− y) has a unique 
positive solution. Elementary calculus shows that the global minimum of 
Doku‑Amponsah S pringerPlus  (2016) 5:1140 Page 15 of 16
2 (1−y)
b �→ 12�(d)c + y log y+
b
2 + (1− y) log −b − b(1− y) on (0,∞) is attained at �(d)c (1−e )
the value b = a, where a is the positive solution of our equation. We obtain the form of ξ 
in Corollary 3 by observing that
( )
a(y)2 + (�(d)c)2 − 2�(d)ca(y) 1− y �(d)cy( ) 1 ( )2
= 2− y + a(y)−�(d)c(1− y) .
2�(d)c 2 2�(d)c
Proof of Corollary 5
We define the continuous linear map W : P(�)× P̃ (�2∗ ) → [0,∞) by W (η1,ω) = 12�ω�, 
and infer from Theorem 4 and the contraction principle that W (L1G ,L2G) = |E|/n satis-
fies a large deviation principle in [0,∞) with the good rate function
{ }
ζ(y) = inf I(η1,ω): W (η1,ω) = y .
To obtain the form of the rate in the corollary, the infimum is reformulated as uncon-
strained optimization problem (by normalising ω)
{ }
�(d)
inf H(η1 � ν)+ yH(ω ��(d)Cη1 ⊗ η1)+ y log 2y+ �Cω ⊗ ω� − y . (15)
ω∈P∗(�2) 2
η1∈P(�)
By Jensen’s inequality H(ω ��(d)Cη1 ⊗ η1) ≥ − log ��(d)Cη1 ⊗ η1�, with equality if 
= Cηω 1⊗η1�C ⊗ � , and hence, by symmetry of C we haveη1 η1
{ }
�(d)
min H(η1 � ν)+ yH(ω ��(d)Cη1 ⊗ η1)+ y log 2y+ �Cη1 ⊗ η1� − y
ω∈P (�2∗ ) 2
�(d)
= H(η1 � ν)− y log ��(d)Cη1 ⊗ η1� + y log 2y+ �Cη1 ⊗ η1� − y.
2
The form given in Corollary 5 follows by defining
1 ∑
y = �(d) Cd(a, b)η1(a)η1(b).
2
a,b∈�
Conclusion
In this work, we have proved joint large deviation principle for the empirical pair meas-
ure and empirical locality measure of the near intermediate CGRG models. From this 
result we have obtained asymptotic results about useful graph quantities such as num-
ber of edges per vertex, the degree distribution and the proportion of isolated vertices 
for the near intermediate CGRG models. The rate functions of all these large deviation 
principles compared very well with the rate functions of the results for coloured random 
graph models by Doku-Amponsah and Mörters (2010), with some extra terms account-
ing for the geometric effect in the CGRG models. An important future research direc-
tion is to formulate and prove an Asymptotic Equipartition Property for Networked 
Data Structures Modelled as the CGRG, and then a possible Coding or Approximate 
Pattern Matching Algorithms for such Networks. One could also investigate the Statisti-
cal Mechanics on the CGRG.
Doku‑Amponsah  SpringerPlus  (2016)5 :1140 Page 16 of 16
Acknowledgements
This extension has been mentioned in the author’s PhD Thesis at University of Bath.
Competing interests
The author declares that he has no competing interests.
Received: 16 January 2016   Accepted: 29 June 2016
References
Biggins JD (2004) Large deviations for mixtures. Electron Commun Probab 9:60–71
Bordenave C, Caputo P (2015) Large deviations of empirical neighbor‑hood distribution in sparse random graphs. Probab 
Theory Relat Fields 163(1–2):149–222
Biggins JD, Penman DB (2009) Large deviations in randomly coloured random graphs. Electron Comm Probab 
14:290–301
Cannings C, Penman DB (2003) Handbook of statistics 21. Stochastic processes: modelling and simulation. In: Shanbhag 
DN, Rao CR (eds) Models of random graphs and their applications. Elsevier, Amsterdam, pp 51–91
Dembo A, Zeitouni O (1998) Large deviations techniques and applications. Springer, New York
Dembo A, Mörters P, Sheffield S (2005) Large deviations of Markov chains indexed by random trees. Ann Inst Henri 
Poincaré Probab Stat 41:971–996
Doku‑Amponsah K (2006) Large deviations and basic information theory for hierarchical and networked data structures. 
PhD thesis, Bath
Doku‑Amponsah K (2014) Exponential approximation, method of types for empirical neighbourhood measures of 
random graphs by random allocation. Int J Stat Probab 3(2):110–120
Doku‑Amponsah K (2015) Large deviation result for the empirical locality measure of typed random geometric graphs. 
Int J Stat Prob 4(1):94–99
Doku‑Amponsah K (2016) Large deviation, Basic information theory for wireless sensor networks. Presented at College of 
Basic and Applied Sciences, Science Development Platform 2016, University of Ghana. arxiv:1512.08050
Doku‑Amponsah K, Mörters P (2010) Large deviation principles for empirical measures of coloured random graphs. Ann 
Appl Probab 20(6):1989–2021. doi:10.1214/09‑AAP47
Mukherjee S (2014) Large deviation for the empirical degree distribution of an Erdos–Renyi graph. arxiv:1310.4160
O’Connell N (1998) Some large deviation results for sparse random graphs. Probab Theory Relat Fields 110:277–285
Penrose MD (2003) Random geometric graphs. Oxford University Press, Oxford
View publication stats