# On the One Dimensional Poisson Random Geometric Graph

Authors: L. Decreusefond; E. Ferraz
Journal: Journal of Probability and Statistics
 (2011)

---

## Abstract

Given a Poisson process on a bounded interval, its random geometric graph is the graph whose vertices are the points of the Poisson process, and edges exist between two points if and only if their distance is less than a fixed given threshold. We compute explicitly the distribution of the number of connected components of this graph. The proof relies on inverting some Laplace transforms.


---

## Body

## 1. Motivation

As technology goes on [1–3], one can expect a wide expansion of the so-called sensor networks. Such networks represent the next evolutionary step in building, utilities, industry, home, agriculture, defense, and many other contexts [4].These networks are built upon a multitude of small and cheap sensors which are devices with limited transmission capabilities. Each sensor monitors a region around itself by measuring some environmental quantities (e.g., temperature, humidity), detecting intrusion and so forth, and broadcasts its collected information to other sensors or to a central node. The question of whether information can be shared among the whole network is then of crucial importance. Mathematically speaking, sensors can be abstracted as points inR2, R3, or a manifold. The region a sensor monitors is represented by a circle centered at the location of the sensor. In what follows, it is assumed that the broadcast radius, that is, the distance at which a sensor can communicate with another sensor, is equal to the monitoring radius. Two questions are then of interest: can any two sensors communicate using others as hopping relays and is the whole region covered by all the sensors? The recent works of Ghrist and his collaborators [5, 6] show how, in any dimension, algebraic topology can be used to answer these questions. Their method consists in building the so-called simplicial complex associated to the configuration of points and the radius of communication. Then, simple algebraic computations yield the Betti numbers: the first Betti number, usually denoted as β0, is the number of connected components; the second number β1 is the number of coverage holes. Thus, we have a satisfactory deployment whenever β0=1 and β1=0. Trying to pursue their work for random settings, we quickly realized that the dimension of the ambient space played a key role. We then first began by the analysis of dimension 1, which appeared to be the simplest situation. In this case, there is no need of algebraic topology so we will not go further in the description of this line of thought even if it was our first motivation.In dimension 1, the only question of interest is that of the connexity but it can take different forms. Imagine we are given[0,1] as a domain in which n points {x1,…,xn} are drawn. For a radius r, one can wonder whether [0,1]⊂∪i=1,…,n[xi-r,xi+r], or one can investigate whether [xi-r,xi+r]∩[xi+1-r,xi+1+r]≠∅ for all i=1,…,n-1. The second situation is less restrictive since we do not impose that the frontier of the interval is to be covered. Depending on the application, we have in mind, both questions are sensible. A slightly different but somehow close problem is that of the circle: consider now that the points are dispatched along a circle of unit perimeter C1 and ask again whether C1⊂∪i=1,…,nB(xi,r) where B(x,r) is the 2-dimensional ball of center x and radius r. Several years ago, this problem has been thoroughly analyzed ([7] and references therein) for a fixed number of i.i.d. arcs over the circle. A closed form formula can be given for the probability of coverage as a function of the number and of the common law of the arcs length. Some variations of this problem have been investigated since then, see, for instance, [8]. More recently, in [9], algorithms are devised to determine whether a domain can be protected from intrusion by a “belt” of sensors (namely, a ring or the border of a rectangle). There is no performance analysis in this work which is focused on algorithmic solutions for this special problem of coverage. Still motivated by applications to sensor networks, [10] considers the situation where sensors are actually placed in a plan, have a fixed radius of observation, and analyse the connectivity of the trace of the covered region over a line. Some recent results of Kahle [11, 12] are actually hardly linked to our results: the motivation is the same, studying the Betti numbers of some random simplicial complexes, but the results are only asymptotic and valid in dimension greater than 2.Our main result is the distribution of the number of connected components for a Poisson distribution of sensors in a bounded interval. We could not use the method of [7] since the number of gaps does not determine the connectivity of the domain. For instance, one may have only one gap at the “beginning” which means that all the points are pairwise within the threshold distance and, thus, that the network is connected, or one may have only one gap in the “middle” which means that there is a true hole of connectivity.Actually, our method is very much related to the queueing theory. Indeed, clusters, that is, sequence of neighboring points, are the strict analogous of busy periods—see Section2. As will appear below, our analysis turns down to be that of an M/D/1/1 queue with a preemption: when a customer arrives during a service, it preempts the server, and, since there is no buffer, the customer who was in service is removed from the queuing system. This analogy led us to use standard tools of queueing theory: Laplace transform and renewal processes—see, for instance, [13, 14]. This works perfectly, and, with a bit of calculus, we can compute all the characteristics we are interested in. It is worthwhile to note that a queueing model (namely the M/G/∞) also appears in [10].The paper is organized as follows: Section2 presents the model and defines the relevant quantities to be calculated. The calculations and analytical results are presented in Section 3. For our situation, we find results analogous to that of [7]. In Section 4, two other scenarios are presented, considering the number of incomplete clusters and clusters placed in a circle. In Section 5, numerical examples are presented and analyzed.


## 2. Problem Formulation

LetL>0, we assume that we are given a Poisson process, denoted by N, of intensity λ on [0,L]. Let (Xi,i≥1) be the atoms of N. We, thus, know that the random variables, ΔXi=Xi+1-Xi are i.i.d. and exponentially distributed. We fix ϵ>0. Two points, located, respectively, at x and y, are said to be directly connected whenever |x-y|≤ϵ. For i<j, two points of N, say Xi and Xj, are indirectly connected if Xl and Xl+1 are directly connected for any l=i,…,j-1. A set of points directly or indirectly connected is called a cluster, a complete cluster is a cluster which begins and ends within [0,L]. The connectivity of the whole network is measured by the number of clusters.The number of points in the interval[0,x] is denoted by Nx=∑n=0∞1{Xn≤x}. The random variable Ai given by
(2.1)Ai={X1ifi=1,inf⁡{Xj:Xj>Ai-1,Xj-Xj-1>ϵ}ifi>1,
represents the beginning of the ith cluster, denoted by Ci. In the same way, the end of this same cluster, Ei, is defined by
(2.2)Ei=inf⁡{Xj+ϵ:Xj>Ai,Xj+1-Xj>ϵ}.
So, the ith cluster, Ci, has a number of points given by NEi-NAi. We define the length Bi of Ci as Ei-Ai. The intercluster size, Di, is the distance between the end of Ci and the beginning of Ci+1, which means that Di=Ai+1-Ei, and ΔAi is the distance between the first points of two consecutive clusters Ci, given by ΔAi=Ai+1-Ai=Bi+Di.Remark 2.1.
With this set of assumptions and definitions, we can see our problem as anM/D/1/1 preemptive queue, see Figure 1. In this nonconservative system, the service time is deterministic and given by ϵ. When a customer arrives during a service, the served customer is removed from the system and replaced by the arriving customer. Within this framework, a cluster corresponds to what is called a busy period, the intercluster size is an idle time, and Ai+Di is the length of the ith cycle.Figure 1
Queueing representation of the model. A down arrow denotes that useri starts his service. An up arrow indicates that user i leaves the system without having finished the service. A double up arrow illustrates that the service of user i finishes. Beginning and end of the ith busy period, respectively, Ai and Ei, are also shown.The number of complete clusters in[0,L] corresponds to the number of connected components β0(L) (since, in dimension 1, it coincides with the Euler characteristics of the union of intervals, see [5]) of the network. The distance between the beginning of the first cluster and the beginning of the (i+1)th one is defined as Ui=∑k=1iΔAk. We also define ΔX0=D0=X1. Figure 2 illustrates these definitions.Figure 2
Definitions of the relevant quantities of the network. Distance between points, distance between clusters, clusters size, interclusters size, beginning and ends of clusters.For the sake of completeness, we recall the essentials of Markov’s process theory needed to go along, for further details we refer, for instance, to [13, 14]. In what follows, for a process X, (ℱtX,t≥0) is the filtration generated by the sample-paths of X:
(2.3)FtX=σ{X(s),s≥t}.Definition 2.2.
A process(X(t),t≥0) with values in a denumerable space E is said to be Markov whenever
(2.4)E[F(X(t+s))∣FtX]=E[F(X(t+s))∣X(t)],
for any bounded function F from E to R, any t≥0 and s≥0.
Equivalently, a processX is Markov if and only if, given the present (i.e., given X(t)), the past (i.e., the sample-path of X before time t) and the future (i.e., the sample-path of X after time t) of the process are independent.Definition 2.3.
A random variableτ with values in R+∪{+∞} is an ℱX-stopping time whenever, for any t≥0, the event {τ≤t} belongs to ℱtX.The point is that (2.4) still holds when t is replaced by a stopping time τ: given X(τ), the past and the future of X are independent. X is then said to be strong Markov. This property always holds for the Markov processes with values in a denumerable space but is not necessarily true for the Markov processes with values in an arbitrary space.From now on, the Markov process under consideration isN, the Poisson process of intensity λ over [0,L].Lemma 2.4.
For anyi≥1, Ai and Ei are stopping times.Proof.
Let us consider the filtrationℱtN=σ{Na,a≤t}. For i=1, we have
(2.5){A1≤t}⟺{X1≤t}⟺{Nt≥1}∈FtN.
Thus,A1 is a stopping time. For A2, we have
(2.6){A2>t}⟺⋃n≥1{Nt=n,⋃j=1n{ΔXj≥ϵ,⋃k=j+1n{ΔXk≤ϵ}}}∈FtN,
so A2 is also a stopping time. We proceed along the same line for others Ai and as well for Ei to prove that they are stopping times.SinceN is a (strong) Markov’s process, the next corollary is immediate.Corollary 2.5.
The set{Bi,Di,i≥1} is a set of independent random variables. Moreover, Di is distributed as an exponential random variable with mean 1/λ, and the random variables {Bi,i≥1} are i.i.d.


## 3. Calculations

Theorem 3.1.
The Laplace transform of the distribution ofBi is given by
(3.1)E[e-sBi]=λ+sλ+se(λ+s)ϵ⋅Proof.
SinceΔXj is an exponentially distributed random variable,
(3.2)E[e-sΔXj1{ΔXj≤ϵ}]=∫0ϵe-stλe-λtdt=λs+λ(1-e-(s+λ)ϵ).
Hence, the Laplace transform of the distribution ofB1 is given by
(3.3)E[e-sB1]=∑n=1∞E[e-sB1,NE1=n]=∑n=1∞E[e-s(∑j=1n-1ΔXj+ϵ)1{ΔXn>ϵ}∏j=1n-11{ΔXj≤ϵ}]=∑n=1∞(E[e-sΔX11{ΔX1≤ϵ}])n-1E[e-sΔXn1{ΔXn>ϵ}]e-sϵ=∑n=0∞(λs+λ(1-e-(s+λ)ϵ))ne-sλe-sϵ=λ+sseλϵesϵ+λ.
Using Corollary2.5, we have 𝔼[e-sB1]=𝔼[e-sBi], which concludes the proof.From this result, we can immediately calculate the Laplace transform of the distribution ofΔAi. Since ΔAi=Bi+Di, we have 𝔼[e-sΔAi]=𝔼[e-s(Bi+Di)], and using Corollary 2.5:
(3.4)E[e-sΔAi]=E[e-sBi]E[e-sDi]=λλ+se(λ+s)ϵ⋅Corollary 3.2.
The Laplace transform of the distribution ofUn, for n≥0, is given by
(3.5)E[e-sUn]=λn(λ+se(λ+s)ϵ)n⋅Proof.
We use Corollary2.5 and Theorem 3.1 to calculate the Laplace transform of the distribution of Un since Un=∑i=1n(Bi+Di):
(3.6)E[e-sUn]=∏i=1nE[e-sBi]E[e-sDi]=(λ+sλ+se(λ+s)ϵ)n(λλ+s)n,
hence, the result.Let us define the functionpn as
(3.7)pn:x∈R+⟼pn(x)=Pr(β0(x)=n),
that is, pn(x) is the probability of having n clusters in the interval [0,x]. Since, for all x∈R+, 0≤pn(x)≤1, the Laplace transform of pn with respect to x,
(3.8)L{pn}(s)=∫0∞e-sxpn(x)dx,
is well defined.Theorem 3.3.
For anyn≥0, the Laplace transform of pn is given by
(3.9)L{pn}(s)=λne(λ+s)ϵ(se(λ+s)ϵ+λ)n⋅Proof.
We note that; see Figure3,
(3.10){β0(x)≥n}⟺{{ΔX0+Un-1+Bn≤L}ifn≥1,{ΔX0<∞}ifn=0.
Hence,(3.11)Pr(β0(x)=0)=1-Pr(ΔX0+B1≤x),(3.12)Pr(β0(x)=n)=Pr(ΔX0+Un-1+Bn≤x)-Pr(ΔX0+Un+Bn+1≤x).
Let
(3.13)Yn={ΔX0+Un-1+Bn,ifn≥1,0,ifn=0,
then we have
(3.14)L{Pr(Yn≤⋅)}(s)=∫0∞Pr(Yn≤x)e-sxdx=∫0∞∫0xdPYn(y)e-sxdx=1sE[e-sYn]=1sE[e-sΔX0]E[e-sUn-1]E[e-sBn]=1sλn(eλϵsesϵ+λ)n,
for n≥1, where we used Corollary 2.5 in the third line. For n=0, the Laplace transform is trivial and given by ℒ{Pr(Y0≤·)}(s)=1/s. Substituting (3.14) in the Laplace transform of both sides of (3.12) yields
(3.15)L{pn}(s)=L{Pr(Yn≤⋅)}(s)-L{Pr(Yn+1≤⋅)}(s)=eϵλeϵsλn(eϵλseϵs+λ)n+1,n≥0.
The proof is, thus, complete.Figure 3
Illustration of the condition equivalent toβ0≥n.Lemma 3.4.
Letm be an positive integer. For any x>0, when ϵ→0, 𝔼[β0m]→𝔼[NLm].Proof.
Since there is almost surely a finite number of points in[0,x], for almost all sample-paths, there exists η>0 such that ΔXj≥η for any j=1,…,Nx. Hence, for ϵ<η, β0(x)=Nx. This implies that β0(x) tends almost surely to Nx as ϵ goes to 0. Moreover, it is immediate by the very definition of β0(x) that β0(x)≤Nx. Since, for any m, 𝔼[Nxm] is finite, the proof follows by dominated convergence.LetLit(z), z,t∈R, z<1, be the polylogarithm function with parameter t, defined by
(3.16)Lit(z)=∑k=1∞zkkt⋅
For m a positive integer, consider the function of x(3.17)Mβ0m:x⟼E[β0m(x)]=∑i=0∞impi(x).
Its Laplace transform is given by
(3.18)L{Mβ0m}(s)=∫0∞E[β0(x)m]e-sLdx.Corollary 3.5.
Letα be defined as follows:
(3.19)α=eϵλλseϵs.
The Laplace transform of the mth moment of β0(L) is
(3.20)L{Mβ0m}(s)=αs(α+1)Li-m(1α+1),
which converges, provided that α>0.Proof.
Applying the Laplace transform of both sides of (3.17), we get
(3.21)L{Mβ0m}(s)=∑i=1∞imL{pi}(s)=((eϵλ/λ)eϵs)((eϵλ/λ)seϵs+1)∑i=1∞im((eϵλ/λ)seϵs+1)i=αs(α+1)Li-m(1α+1),
concluding the proof.We define{mk} as the Stirling number of second kind [15]; that is, {mk} is the number of ways to partition a set of m objects into k groups. They are intimately related to polylogarithm by the following identity (see [16]) valid for any positive integer m,
(3.22)Li-m(z)=∑k=0m(-1)m+kk!{m+1k+1}(1-z)k+1⋅Corollary 3.6.
Themth moment of the number of clusters on the interval [0,L] is given by
(3.23)Mβ0m(L)=∑k=1m{mk}(Lϵ-k)k(λϵe-ϵλ)k1{L/ϵ>k}.Proof.
Using (3.22) in the result of Corollary 3.5, we get
(3.24)L{Mβ0m}(s)=αs∑k=0m(-1)m+kk!{m+1k+1}(1+α)kαk+1(α+1)=1s∑k=0mck,m1αk,
where the coefficients ck,m are integers given by
(3.25)ck,m=∑j=km(-1)jj!{m+1j+1}(jk).
Using the following identity of the Stirling numbers [17],
(3.26)∑j=0m(-1)jj!{m+1j+1}=0,
we find that c0,m=0 for m a positive integer. So, we can write the Laplace transform of the moments as
(3.27)L{Mβ0m}(s)=∑k=1mck,m(λe-ϵλ)ksk+1eksϵ,
and apply the inverse of the Laplace transform in both sides of (3.12) to obtain
(3.28)Mβ0m(L)=L-1{∑k=1mck,m(λe-ϵλ)ksk+1eksϵ}(L)=∑k=1mck,m(λe-ϵλ)kL-1{1sk+1eksϵ}(L)=∑k=1mck,mk!(L-kϵ)k(λe-ϵλ)k1{L>kϵ}.
According to Lemma 3.4, when ϵ→0, we obtain
(3.29)Mβ0m(L)=E[NLm]=∑k=1mck,mk!(Lλ)k1{L>0}.
Hence, for any λ>0,
(3.30)∑k=1mck,mk!(Lλ)k1{L>0}=∑k=1m{mk}(Lλ)k1{L>0},
which shows that
(3.31)ck,m={mk}k!.
Thus, we have proved (3.23) for any positive integer m.Theorem 3.7.
For anyn, L, λ, and ϵ, we have
(3.32)Pr(β0(L)=n)=1n!∑i=0⌊L/ϵ⌋-n(-1)ii!((L-(n+i)ϵ)λe-λϵ)n+i.Proof.
Sinceβ0(L)≤NL and since 𝔼[esNL] is finite for any s∈R, we have, for any s≥0,
(3.33)E[e-sβ0(L)]=∑k=0∞(-1)kskk!E[β0k(L)].
Rearranging the terms of the right-hand side, and substituting Mβ0m(L), by the result of (3.23), we obtain
(3.34)E[e-sβ0(L)]=∑k=0∞((L-kϵ)k(λe-λϵ)k1{L>kϵ}∑j=k∞(-s)jj!{jk})⋅
Furthermore, it is known (see [17]) that
(3.35)∑j=k∞xjj!{jk}=1k!(ex-1)k.
Hence,
(3.36)E[e-sβ0(L)]=∑k=0∞(L-kϵ)k(λe-λϵ)k1{L>kϵ}(e-s-1)kk!⋅
By inverting the Laplace transforms, we get
(3.37)∑k=0∞∑i=k∞(-1)ii!(in)δ(k-n)(kϵ-L)k(λe-λϵ)k1{L>kϵ},
where δa is the Dirac measure at point a. After some simple algebra, we find the expression of the probability that an interval contains n complete clusters:
(3.38)Pr(β0(L)=n)=pn(L)=1n!∑i=0⌊L/ϵ⌋-n(-1)ii!([L-(n+i)ϵ]λe-λϵ)n+i,
concluding the proof.Lemma 3.8.
Forx≥0, pn(x) has the three following properties.(i)
pn(x) is differentiable.(ii)
limx→∞pn(x)=0.(iii)
limx→∞dpn(x)/dx=0.Proof.
Letj be a nonnegative integer. The function is obviously differentiable when x/ϵ≠j. Besides, we have
(3.39)lim⁡x→ϵj+pn(x)-lim⁡x→ϵj-pn(x)=lim⁡x→ϵj+(-1)jj!((x-(n+j)ϵ)1a)n+j⋅
Since the right-hand term function of x is zero as well as its derivative for all j, the function is also derivable when x/ϵ=j, which proves (i). Items (ii) and (iii) are direct consequences of the Final Value theorem in the Laplace transform of pn and its derivative.The expression ofpn gives us a Laplace pair between the x and s domains:
(3.40)1{x≥0}n!∑i=0⌊x/ϵ⌋-n(-1)ii!((x-(n+i)ϵ)1a)n+i⟺Laeϵs(aseϵs+1)n+1⋅
We can use this relation to find the distributions of Bi and Un.Theorem 3.9.
The probability density functions ofBi and Un, denoted, respectively, by fBi(x) and fUn(x), are given:
(3.41)fBi(x)=[λe-ϵλp0(x-ϵ)+e-ϵλddxp0(x-ϵ)]1{x>ϵ},(3.42)fUn(x)=λe-ϵλpn-1(x-ϵ)1{x>ϵ},
where the expressions of p0(x-ϵ) and (d/dx)p0(x-ϵ) are straightforwardly obtained from (3.32).Proof.
According to Theorem3.1,
(3.43)E[e-sBi]=1λ(λ+s)(eλϵ/λ)sesϵ+1=λe-ϵλeϵλλeϵs(eϵλ/λ)seϵs+1e-ϵs+e-ϵλseϵλλeϵs(eϵλ/λ)seϵs+1e-ϵs=λe-ϵλe-ϵsL{p0(⋅)}(s)+e-ϵλe-ϵssL{p0(⋅)}(s).
Here, using the inverse Laplace transform established in (3.40) and remembering that p0(x-)=0, we get an analytical expression for fBi(x), proving (3.41).
Proceeding in a similar fashion, we can find the distribution ofUn by inverting its Laplace transform given by Corollary 3.2 as follows:
(3.44)E[e-sUn]=1((eλϵ/λ)sesϵ+1)n=λe-ϵλeϵλλeϵs((eϵλ/λ)seϵs+1)ne-ϵs=λe-ϵλe-ϵsL{pn-1(⋅)}(s).
We, thus, have (3.42).We can also obtain the probability that the segment[0,L] is completely covered by the sensors. To do this, we remember that the first point (if there is one) is capable to cover the interval [X1-ϵ,X1+ϵ].Theorem 3.10.
LetRm,n(x) be defined as follows:
(3.45)Rm,n(x)=∑i=m⌊x/ϵ⌋-1[(e-λϵ)i+n∑j=0i+n(λ[(1-i)ϵ-x])jj!]⋅
Then,
(3.46)Pr([0,L]iscovered)=R0,1(L)-e-λϵR0,1(L-ϵ)-e-λϵR1,0(L)+e-2λϵR1,0(L-ϵ).Proof.
The condition of total coverage is the same as(3.47){∀x∈[0,L],∃Xi∈[0,L]∣x∈[X1-ϵ,X1+ϵ]},
which means that
(3.48){[0,L]iscovered}⟺{B1≥L-X1}∩{X1≤ϵ}.
Hence,
(3.49)Pr([0,L]iscovered)=∫0ϵPr(B1≥L-X1∣X1=x)dPX1(x),
and since B1 and X1 are independent
(3.50)Pr([0,L]iscovered)=∫0ϵ∫L-x∞fB1(u)λe-xλdudx.
The result then follows from Lemma 3.8 and some tedious but straightforward algebra.


## 4. Other Scenarios

The method can be used to calculatepn for other definitions of the number of clusters. We consider two other definitions: the number of incomplete clusters and the number of clusters in a circle.


### 4.1. Number of Incomplete Clusters

The major difference with Section3 is that a cluster is now taken into account as soon as one of the point of the cluster is inside the interval [0,L]. So, for instance, in Figure 3, we count actually n+1 incomplete clusters. We define β0′(L) as the number of incomplete clusters on an interval [0,L].Theorem 4.1.
LetG(k) be defined as
(4.1)G(k)=(-1)k(e-kλϵ∑j=0k[λ(kϵ-L)]jj!-e-λL)1{T>kϵ},
for k∈ℕ+ and G(-1)=e-λL. Then,
(4.2)Pr(β0′(L)=n)=∑i=n⌊L/ϵ⌋+1(-1)i+n(in)(G(i-1)+G(i)),forn≥0.Proof.
The condition ofβ0′(L)≥n is now given by
(4.3){β0′≥n}⟺{{ΔX0+Un-1≤L}ifn≥1,{ΔX0<∞}ifn=0.
We define Yn as
(4.4)Yn={ΔX0+Un-1ifn≥1,0ifn=0.
Repeating the same calculations, we find the Laplace transform of Pr(β0′(·)=n):
(4.5)L{Pr(β0′(⋅)=n)}(s)={λs+λeϵλλeϵs((eϵλ/λ)seϵs+1)nifn≥1,1λ+sifn=0.
With this expression, following the lines of Lemma 3.4, we obtain
(4.6)L{E[β0′(⋅)m]}(s)=∑k=1m+1{m+1k}(k-1)!1skλλ+s(λe-λϵesϵ)k-1.
Then, we write
(4.7)λλ+s1sk=(-1)kλk-11λ+s+∑i=1k1si(-1λ)k-i,
to find an expression with a well-known Laplace transform inverse, and, after inverting it, we obtain
(4.8)E[β0′m]=∑k=0m{m+1k+1}k!G(k).
Expanding the Laplace transform of the distribution of β0′(L) in a Taylor series and rearranging terms, we get
(4.9)E[e-sβ0′(L)]=1+G(0)∑j=1∞(-s)jj!{j1}+(∑k=1∞G(k)∑j=k∞(-s)jj!{j+1k+1}).
Now, we use another recurrence that the Stirling numbers obey [17],
(4.10){j+1k+1}={jk}+(k+1){jk+1},
to get
(4.11)∑j=k∞xjj!{j+1k+1}=∑j=k∞xjj!({jk}+(k+1){jk+1})=1k!(ex-1)k+1k!(ex-1)k+1.
Hence,
(4.12)E[e-sβ0′(L)]=1+∑k=1∞(G(k-1)+G(k))(e-s-1)k.
Inverting this expression for any nonnegative integer n, we have the searched distribution.


### 4.2. Number of Clusters in a Circle

We investigate now the case where the points of the process are deployed over a circumference, and we want to count the number of complete clusters, which corresponds to calculate the Euler's Characteristic of the total coverage, so we call this quantityχ. Without loss of generality, we can choose an arbitrary point to be the origin.Theorem 4.2.
The distribution of the Euler's Characteristic,χ(L), when the points are deployed over a circumference of length L is given by
(4.13)Pr(χ(L)=n)=e-λL1{n=0}+(1-e-λL)λe-ϵλn!×∑i=0⌊L/ϵ⌋-n[(-1)ii!([L-(n+i)ϵ]λe-ϵλ)n+i-1(L+(n+i)(1λ-ϵ))]forn≥0.Proof.
If there is no points on the circle,χ(L)=0. Otherwise, if there is at least one point, we choose the origin at this point, and we have equivalence between the events:
(4.14){χ(L)≥n}⟺{{Un-1+Bn≤L}∩{NL>0}ifn≥1,{ΔX0<∞}ifn=0.
In Figure 4, we present an example of this equivalence.
We can defineYn as
(4.15)Yn={Un-1+Bnifn≥1,0ifn=0,
to find the Laplace transform or Pr(χ(L)=n):
(4.16)L{Pr(χ(⋅)=n)}(s)=(1-e-λL)λ+sλeϵλλeϵs((eϵλ/λ)seϵs+1)n⋅
The number of clusters is almost surely equal to the number of points when ϵ→0, so
(4.17)E[χ(L)m]=(1-e-λL)λe-ϵλ∑k=1m[{mk}([L-kϵ]λe-ϵλ)k-1(L+k(1λ-ϵ))1{L>kϵ}].
Expanding the Laplace transform in a Taylor series and rearranging terms, as we did previously, yields
(4.18)E[e-sχ(L)]=(1-e-λL)λe-ϵλ∑k=0∞[([L-kϵ]λe-ϵλ)k-1(L+k(1λ-ϵ))1{L>kϵ}∑j=k∞(-s)jj!{jk}].
Since
(4.19)∑j=k∞(-s)jj!{jk}=(e-s-1)kk!,
we can directly invert this Laplace transform, add the case where there are no points for χ(L)=0, and the theorem is proved.Figure 4
Illustration of the condition equivalent toχ(L)≥n. Since the coverage of the last point on [0,L] overlaps the cluster with a point in zero, they are actually contained in the same cluster.


## 4.1. Number of Incomplete Clusters

The major difference with Section3 is that a cluster is now taken into account as soon as one of the point of the cluster is inside the interval [0,L]. So, for instance, in Figure 3, we count actually n+1 incomplete clusters. We define β0′(L) as the number of incomplete clusters on an interval [0,L].Theorem 4.1.
LetG(k) be defined as
(4.1)G(k)=(-1)k(e-kλϵ∑j=0k[λ(kϵ-L)]jj!-e-λL)1{T>kϵ},
for k∈ℕ+ and G(-1)=e-λL. Then,
(4.2)Pr(β0′(L)=n)=∑i=n⌊L/ϵ⌋+1(-1)i+n(in)(G(i-1)+G(i)),forn≥0.Proof.
The condition ofβ0′(L)≥n is now given by
(4.3){β0′≥n}⟺{{ΔX0+Un-1≤L}ifn≥1,{ΔX0<∞}ifn=0.
We define Yn as
(4.4)Yn={ΔX0+Un-1ifn≥1,0ifn=0.
Repeating the same calculations, we find the Laplace transform of Pr(β0′(·)=n):
(4.5)L{Pr(β0′(⋅)=n)}(s)={λs+λeϵλλeϵs((eϵλ/λ)seϵs+1)nifn≥1,1λ+sifn=0.
With this expression, following the lines of Lemma 3.4, we obtain
(4.6)L{E[β0′(⋅)m]}(s)=∑k=1m+1{m+1k}(k-1)!1skλλ+s(λe-λϵesϵ)k-1.
Then, we write
(4.7)λλ+s1sk=(-1)kλk-11λ+s+∑i=1k1si(-1λ)k-i,
to find an expression with a well-known Laplace transform inverse, and, after inverting it, we obtain
(4.8)E[β0′m]=∑k=0m{m+1k+1}k!G(k).
Expanding the Laplace transform of the distribution of β0′(L) in a Taylor series and rearranging terms, we get
(4.9)E[e-sβ0′(L)]=1+G(0)∑j=1∞(-s)jj!{j1}+(∑k=1∞G(k)∑j=k∞(-s)jj!{j+1k+1}).
Now, we use another recurrence that the Stirling numbers obey [17],
(4.10){j+1k+1}={jk}+(k+1){jk+1},
to get
(4.11)∑j=k∞xjj!{j+1k+1}=∑j=k∞xjj!({jk}+(k+1){jk+1})=1k!(ex-1)k+1k!(ex-1)k+1.
Hence,
(4.12)E[e-sβ0′(L)]=1+∑k=1∞(G(k-1)+G(k))(e-s-1)k.
Inverting this expression for any nonnegative integer n, we have the searched distribution.


## 4.2. Number of Clusters in a Circle

We investigate now the case where the points of the process are deployed over a circumference, and we want to count the number of complete clusters, which corresponds to calculate the Euler's Characteristic of the total coverage, so we call this quantityχ. Without loss of generality, we can choose an arbitrary point to be the origin.Theorem 4.2.
The distribution of the Euler's Characteristic,χ(L), when the points are deployed over a circumference of length L is given by
(4.13)Pr(χ(L)=n)=e-λL1{n=0}+(1-e-λL)λe-ϵλn!×∑i=0⌊L/ϵ⌋-n[(-1)ii!([L-(n+i)ϵ]λe-ϵλ)n+i-1(L+(n+i)(1λ-ϵ))]forn≥0.Proof.
If there is no points on the circle,χ(L)=0. Otherwise, if there is at least one point, we choose the origin at this point, and we have equivalence between the events:
(4.14){χ(L)≥n}⟺{{Un-1+Bn≤L}∩{NL>0}ifn≥1,{ΔX0<∞}ifn=0.
In Figure 4, we present an example of this equivalence.
We can defineYn as
(4.15)Yn={Un-1+Bnifn≥1,0ifn=0,
to find the Laplace transform or Pr(χ(L)=n):
(4.16)L{Pr(χ(⋅)=n)}(s)=(1-e-λL)λ+sλeϵλλeϵs((eϵλ/λ)seϵs+1)n⋅
The number of clusters is almost surely equal to the number of points when ϵ→0, so
(4.17)E[χ(L)m]=(1-e-λL)λe-ϵλ∑k=1m[{mk}([L-kϵ]λe-ϵλ)k-1(L+k(1λ-ϵ))1{L>kϵ}].
Expanding the Laplace transform in a Taylor series and rearranging terms, as we did previously, yields
(4.18)E[e-sχ(L)]=(1-e-λL)λe-ϵλ∑k=0∞[([L-kϵ]λe-ϵλ)k-1(L+k(1λ-ϵ))1{L>kϵ}∑j=k∞(-s)jj!{jk}].
Since
(4.19)∑j=k∞(-s)jj!{jk}=(e-s-1)kk!,
we can directly invert this Laplace transform, add the case where there are no points for χ(L)=0, and the theorem is proved.Figure 4
Illustration of the condition equivalent toχ(L)≥n. Since the coverage of the last point on [0,L] overlaps the cluster with a point in zero, they are actually contained in the same cluster.


## 5. Examples

We consider some examples to illustrate the results of the paper. Here, the behavior of the mean and the variance ofβ0(L) as well as Pr(β0(L)=n) are presented.From (3.23), we have that 𝔼[β0(L)] is given by
(5.1)E[β0(L)]=(L-ϵ)λe-ϵλ1{L>ϵ}.
This expression agrees with the intuition in that there are three typical regions given a fixed ϵ. When λ is much smaller than 1/ϵ, the number of clusters is approximatively the number of sensors, since the connections with few sensors will unlikely happen, which can be seen from the fact that 𝔼[β0(L)]→Lλ when λ→0. As we increase λ, the mean number of direct connections overcomes the mean number of sensors, and, at some value of λ, we expect that 𝔼[β0(L)] decreases, when adding a point is likely to connect disconnected clusters. We remark that the maximum occurs exactly for ϵ=1/λ, that is, when the mean distance between two sensors equals the threshold distance for them to be connected. At this maximum, 𝔼[β0(L)] takes the value of (L/ϵ-1)e-1. Finally, when λ is too large, all sensors tend to be connected, and there is only one cluster which even goes beyond L, so there are no complete clusters into the interval [0,L]. This is trivial when we make λ→∞ in the last equation. Figure 5 shows this behavior when L=4 and ϵ=1.Figure 5
Variation of the mean number of clusters in function ofλ when L=4 and ϵ=1.The variance can be obtained also by (3.23) as follows:
(5.2)Var⁡(β0(L))=(L-ϵ)λe-ϵλ1{L>ϵ}+(L-2ϵ)λ2e-2ϵλ1{L>2ϵ}-(L-ϵ)2λ2e-2ϵλ1{L>ϵ},
and, under the condition that L>2ϵ(5.3)Var⁡(β0(L))=(L-ϵ)λe-ϵλ+ϵ(3ϵ-2L)λ2e-2ϵλ.Figure6 shows a plot of Var(β0(L)) in function of λ for L=4 and ϵ=1. We can expect that, when λ is small compared to ϵ, the plot should be approximatively linear, since there would not be too much connections in the network, and the variance of the number of clusters should be close to the variance of the number of sensors given by λL. Since β0(L) tends almost surely to 0 when λ goes to infinity, Var(β0(L)) should also tend to 0 in this case. Those two properties are observed in the plot. Besides, we find the critical points of this function, and again, λ=1/ϵ is one of them, and at this value Var(β0(L))=(L/ϵ)e-1+(3-2L/ϵ)e-1. The other two are the ones satisfying the transcendent equation:
(5.4)λe-λϵ=L-ϵ2ϵ(2L-3ϵ)⋅
By using the second derivative, we realize that 1/ϵ is actually a minimum. Besides, if L≤2ϵ, there is just one critical point, a maximum, at λ=1/ϵ.Figure 6
Behavior of the variance of the number of clusters in function ofλ when L=4 and ϵ=1.The last example in the section is performed with the result obtained in Theorem3.7. We consider again L=4 and ϵ=1 to obtain the following distributions:
(5.5)Pr(β0(L)=0)=1-3λe-λ+2λ2e-2λ-1/6λ3e-3λ,Pr(β0(L)=1)=3λe-λ-4λ2e-2λ+1/2λ3e-3λ,Pr(β0(L)=2)=2λ2e-2λ-1/2λ3e-3λ,Pr(β0(L)=3)=1/6λ3e-3λ,Pr(β0(L)>3)=0.
Those expressions are simple, and they have at most four terms, since L=4ϵ. We plot these functions in Figure 7. The critical points on those plots at λ=1/ϵ are confirmed for the fact that, in function of λ for every n, Pr(χ(L)=n) can be represented as a sum:
(5.6)∑i=0jqi,j(λe-λϵ)i,
where the coefficients qi,j are constant in relation to λ. However, (λe-λϵ)i has a critical point at λ=1/ϵ for all i>0, so this should be also a critical point of Pr(χ(L)=n). If λ is small, we should expect that Pr(χ(L)=0) is close to one, since it is likely to N have no points. For this reason, in this region, Pr(χ(L)=n) for n>0 is small. When λ is large, we expect to have very large clusters, likely to be larger than L, so it is unlikely to have a complete cluster in the interval, and, again, Pr(χ(L)=0) approaches to the unity, while Pr(χ(L)=n) for n>0 become again small.Figure 7
Probabilities of connectiveness,Pr(β0(L)=n), for n=0,1,2,3, in function of λ when L=4 and ϵ=1.



---

*Source: 350382-2011-10-11.xml*