1

Threshold Phenomena for Interference with
Randomly Placed Sensors

arXiv:1611.06329v2 [] 4 May 2017

Rafał Kapelko
Abstract—This paper investigates the problem of efficient displacement of random sensors where good communication within the
network is provided, there is no interference between sensors and the movement cost is minimized in expectation.
Fix d ∈ N \ {0}. Assume n sensors are initially placed in the hyperoctant [0, ∞)d according to d identical and independent Poisson
processes each with arrival rate n1/d . Let 0 < s ≤ v be given real numbers. We are allowed to move the sensors, so that every two
consecutive sensors are placed at distance greater than or equal to s and less than or equal to v. When a sensor is displaced a
distance equal to m, the cost of movement is proportional to some (fixed) power a > 0 of the m distance travelled. We consider a−total
movement (see Definition 2) for one dimension and d−dimensional a−total movement (see Definition 3) for the higher dimension.
Motivation for using this extended cost metric arises from the fact that the parameter a in the exponents represents various conditions
on the barrier: lubrication, obstacles, etc. The main contribution of this paper can be summarized as follows.
1)

2)

If the sensors are displaced in the half-infinite interval [0, ∞), the tradeoffs between the interference distances s, v and the
expected minimum a−total movement are derived. We discover a sharp decline and a sharp increase in the expected minimum
1
a−total movement around the interference distance s, v equal to n
.
For the sensors in the hyperoctant [0, ∞)d (d > 1), the tradeoffs between the interference distances s, v and the expected
minimum d−dimensional a−total movement are obtained. We also discover a sharp decline and a sharp increase in the
1
expected minimum d−dimensional a−total movement around the interference distance s, v equal to 1/d
.
n

Index Terms—Interference, Analysis of algorithms, Random, Sensors, Poisson process

✦

1

I NTRODUCTION

Mobile sensors are being deployed for detecting and monitoring events which occur in many instances of every day life.
However, it is often their case that monitoring may not be as
effective due to external factors such as harsh environmental
conditions, sensor faults, geographic obstacles, etc. In such cases
sensor realignments may be required, e.g., sensors must be relocated from their initial positions to new positions so as to attain
the desired communication characteristics. The resulting problem
is assigning final positions to the sensors in order to minimize the
reallocation cost.
Fix d ∈ N \ {0}. The present paper is concerned with random
realignments of sensors in the hyperoctant. Assume that n sensors
are initially placed in the hyperoctant [0, ∞)d according to d
identical and independent Poisson processes each with arrival rate
n1/d . Given that the sensors are initially placed on the domain
at random according to some well-defined random process, we
are interested to ensure that by moving the sensors the following
scheduling requirement is satisfied.
Definition 1 ((s, v) − IP ). The (s, v)−interference problem
requires that every two consecutive sensors1 are placed at distance
greater than or equal to s and less than or equal to v for some
s, v such that 0 < s ≤ v.
It is very well known that proximity between sensors affects
•

R. Kapelko is with the Department of Computer Science, Faculty of
Fundamental Problems of Technology, Wrocław University of Science and
Technology, Poland.
E-mail: rafal.kapelko@pwr.edu.pl.

Manuscript received ???? ??, ????; revised ???? ??, ????.
1. The precise meaning of consecutive sensors in the higher dimension
(d > 1) will be explain further in Section 4.

transmission and reception signals and causes degradation of performance (see [6]). The closer the distance between neighbouirng
sensors, the higher the resulting interference. Additionally, to
ensure a good communication or connection of the whole network
the sensors can not be too far from each other.
Thus, in (s, v) − IP problem the goal is to ensure a good
communication of the whole network while at the same time the
neighbouring sensors are not too close.
The initial placement of the sensors does not guarantee (s, v)−
IP interference requirement since the sensors have been placed
randomly according to the arrival times of Poisson processes. To
attain the requirements that any pair of sensors are separated by a
distance of at least s and no two consecutive sensors are placed at
distance greater than v, the sensors have to move from their initial
location to new position.
For the case of the half-infinite interval [0, ∞) we define the
cost measure a−total movement as follows.
Definition 2 (a−total movement). Let a > 0 be a constant.
Suppose that the i−th sensor’s displacement is equal
P |m(i)|. The
a−total movement is defined as the sum Ma := ni=1 |m(i)|a .

Motivation for this extended cost metric arises from the fact
that the cost of individual sensor displacement may not be linear
in this displacement, but rather be dependent on some power
of the distance traversed. Moreover, the parameter a may well
represent various conditions on the barrier: obstacles, lubrication,
etc. Therefore, the a−total movement is a more realistic metric
than the one previously considered a = 1.
Let d be a natural number greater than 1. For the case
of the hyperoctant [0, ∞)d we define below the concept of
d−dimensional a−total movement which refers to a movement

2

of sensors only along the axes.
Definition 3 (d−dimensional a−total movement). Let a > 0
be a constant. Consider a sensor Si located in the position
(y1 (i), y2 (i), . . . , yd (i)), where y1 (i), y2 (i), . . . , yd (i) ∈ R+ .
We move the sensor Si to the position (y1 (i) + m1 (i), y2 (i) +
m2 (i), . . . , yd (i) + md (i)). Then the d−dimensional a−total
movement is defined as the double sum Md,a
:=
Pn Pd
a
|m
(i)|
.
j
j=1
i=1

The main question we study in this paper is the following. Assume that n sensors are initially placed in the hyperoctant [0, ∞)d
according to d identical and independent Poisson processes each
with arrival rate n1/d . What is the expected minimum a−total
movement on the line and d−dimensional a−total movement in
the higher dimension so as to solve the problem (s, v) − IP as a
function of the parameter s, v, n, a, d? Our goal is to investigate
tradeoffs arising among the parameters s, v, n, a, d.
Let us fix ǫ, τ > 0 arbitrary small constants independent
on the number of sensors. For the case of the half-infinitive
interval [0, ∞) we explain the threshold phenomena around the
interference distances s = v = n1 . We discover
•

•

a sharp decline in the expected minimal a−total movement
1
as s decreases from n1 to 1−ǫ
n and v increases from n to
1+τ
n ,
a sharp increase in the expected minimal a−total movement as s increases from n1 to 1+ǫ
n and v increases from
1+τ
1
n to n .

exact asymptotics) which explain the tradeoffs arising among the
parameters s, v, n, a, d.

1.2 Preliminaries and Model
In this subsection we recall some useful properties of the Poisson
process. Consider n sensors initially placed in the half-infinite
interval [0, ∞) according to Poisson process with arrival rate
n. Assume that, the i−th event represents the location of the
i−th sensor, for i = 1, 2, . . . , n. Let Xi be the arrival time of
the i−th event in this Poisson process, i.e., the position of the
i−th sensor in the interval [0, ∞). We know that the random
variable Xi obeys the Gamma distribution with parameters i, n. Its
(nt)i−1
probability density function is given by fi,n (t) = ne−nt (i−1)!
R∞
(nt)i−1
and Pr [Xi ≥ t] = t ne−nt (i−1)! . Moreover, the probability
density function of random variable Xj+l − Xj = Xl is given by
the formula
(nt)l−1
fl,n (t) = ne−nt
(1)
(l − 1)!
(see [9], [10], [16] for additional details on the Poisson process).
Notice that,
Z ∞
fl,n (t)dt = 1,
(2)
0

Z

d

For the case of the hyperoctant [0, ∞) the threshold phenomena
1
around the interference distances s = v = n1/d
is discovered for
the expected minimal d−dimensional a−total movement.
1.1 Related Work
Interference has been the subject of extensive interest in research
community in the last decade. Some papers study interference in
relation to network performance degradation [6], [8]. Moscibroda
et al. [14] consider the average interference problem while maintaining the desired network properties such as connectivity, multicast trees or point-to-point connections, while in [1] the authors
propose connectivity preserving and spanner constructions which
are interference optimal. The interference minimization in wireless
ad-hoc networks in a plane was studied in [7]. Further, [12],
[13] investigates the problem of optimally determining sourcedestination connectivity in random networks. The asymptotic
analysis of interference problem on the line using queueing theory
was provided in [11].
More importantly, our work is related to the paper [2] where
the authors consider the expected minimum total displacement
required so that every pair of sensors are in their final positions
at distance greater or equal to s for n sensors placed uniformly
according to Poisson process.
Compared to the minimum distance between two sensors, the
(s, v) − IP scheduling requirement not only avoids interference,
but also ensures good connectivity and is more reasonable when
considering interference. Our analysis also generalizes the result
of the paper [2] from a = 1 to all exponents a > 0 for more
realistic expected minimum a−total movement on the line and
d−dimensional a−total movement in the higher dimension. It is
worth mentioning that some asymptotic bounds in [2] are onesided. We give full asymptotic results (lower and upper bound,

∞

tfl,n (t)dt =

0

l
,
n

(3)

where l, n are positive integers ( see [4, Chapter 15]).
Finally, we derive the following definite integral
Z

∞
z

∞
l−1+b
X (nt)j
(l
−
1
+
b)!

e−nt
tb fl,n (t)dt = −
(l − 1)!nb
j!
j=0


z

=

(l − 1 + b)! −nz
e
(l − 1)!nb

l−1+b
X
j=0

j

(nz)
.
j!

(4)

where l, n, b are positive integers.

1.3 Outline and Results of the Paper
Throughout this paper ǫ, τ > 0 are arbitrary small constants
independent on n.
Fix d ∈ N \ {0}. Assume n sensors are initially placed in
the hyperoctant [0, ∞)d according to d identical and independent
Poisson processes each with arrival rate n1/d . We want to have the
sensors moving from their current random locations to positions
to ensure (s, v) − IP interference requirement.
For the case of one dimension we derive tradeoffs between
the expected minimum a−total movement and the interferences
distances s, v. Table 1 summarizes the results proved in Section
3.2
2. We recall the following asymptotic notation: (i) f (n) = O(g(n)) if
there exists a constant c1 > 0 and integer N such that |f (n)| ≤ C1 |g(n)| for
all n > N, (ii) f (n) = Ω(g(n)) if there exists a constant c2 > 0 and integer
N such that |f (n)| ≥ C2 |g(n)| for all n > N, (iii) f (n) = Θ(g(n)) if and
only if f (n) = O(g(n)) and f (n) = Ω(g(n)).

3

TABLE 1
The expected minimum a−total movement of n sensors in the
half-infinite interval [0, ∞) as a function of the interference distances
s, v.

Interference
distances
s, v
s = 1−ǫ
n
v = 1+τ
n
0 < ǫ, τ
1
n
1
n
1+ǫ
n
1+τ
n

s=
v=

s=
v=
0<ǫ≤τ

Expected minimum
a−total movement
O n1−a





a
Θ n1− 2 , a ≥ 1,


a
O n1− 2 , a ∈ (0, 1)
Θ (n) , a ≥ 1,
O (n) , a ∈ (0, 1)

Algorithm

I1 n,

1−ǫ 1+τ
, n
n

M V1 n,

M V1 n,

1
n





1+ǫ
n



Let us consider case a = 2. We prove the following results.
•
•

•

For interference distances s = v = n1 the expected
minimal 2−total movement is in Θ(1).
1
1+τ
1
If s = 1−ǫ
n is below n and v =
n is above n , the
expected
 minimal 2−total movement declines sharply to
O n1 .
1+τ
If both interference distances s = 1+ǫ
n and v =
n
are above n1 , the expected minimal 2−total movement
increses sharply to Θ(n).

Similar sharp decline and increase hold for all exponent a > 0.
Thus, our investigations explain the threshold phenomena around
the interference distances equal to n1 as this affects the expected
minimum a−total movement of the sensors to fulfill (s, v) − IP
interference requirement.
For the sensors placed in the higher dimension (d > 1) we
obtain tradeoffs between d−dimensional a−total movement and
the interferences distances s, v. Table 2 summarizes the results
obtained in Section 4.
TABLE 2
The expected minimum d−dimensional a−total movement of n
sensors in the hyperoctant [0, ∞)d as a function of the interference
distances s, v.

•

1+ǫ
√
n

1+τ
√
n

If both interference distances s =
and v =
are
1
above √n , the expected minimal 2−dimensional 2−total
movement increases sharply to Θ(n).

Similar sharp decrease and increase hold in all dimensions
(d ∈ N \ {1}) and for all exponents a > 0. Hence, our
investigations explain the threshold phenomena around the in1
terference distances equal to n1/d
as this affects the expected
minimum d−dimensional a−total movement of the sensors to
fulfill (s, v) − IP interference requirement.
Here is an outline of the paper. In Section 2 we provide several
combinatorical facts that will be used in the sequel. In Section 3
we investigate sensors on the line. We show
 that the expected
a−total movement of algorithm M V1 n, n1 is
 a
a!
a
 n1− 2 + O n− 2 ,
a
a
22 2 + 1 !
when a is an even natural number. Further, we analyze the expected minimal a−total movement near the interference distances
s = v = n1 . In Section 4 we investigate sensors in the higher
dimensions.

2

BASIC FACTS AND N OTATIONS

In this section we recall some known facts about special functions
and special numbers which will be useful in the analysis in the
next sections. We also prove Lemma 4 which will be helpful in
the analysis of Algorithm 1.
We will use the following notations for the rising factorial [5]
(
1
for k = 0
k
n =
n(n + 1) . . . (n + k − 1) for k ≥ 1.
n
Let k be the Stirling numbers of the first, which are defined for
all integer numbers such that 0 ≤ k ≤ n.
The Stirling numbers of the first kind arise as coefficients of
the rising factorial (see [5, Identity 6.11])
" #
X m
m
x =
(5)
xl2 .
l
2
l
2

n
k

Interference
distances
s, v
s = 1−ǫ
n1/d
v = 1+τ
n
0 < ǫ, τ
s=
v=

1
n1/d
1
n1/d
1+ǫ
n1/d
1+τ
n1/d

s=
v=
0<ǫ≤τ

Expected minimum
d−dimensional
a−total movement


a
O n1− d

Algorithm

Id n,

1−ǫ
, 1+τ
n1/d n1/d



a
Θ n1− 2d , a ≥ 1,


a
O n1− 2d , a ∈ (0, 1)


M Vd n,

1
n1/d



Θ (n) , a ≥ 1,
O (n) , a ∈ (0, 1)


M Vd n,

1+ǫ
n1/d





•

Let us recall the definition of a finite difference of a function f

∆f (x) = f (x + 1) − f (x).

Let us consider cases d = 2 and a = 2. We prove the
following results.
•

be the Eulerian numbers of the second kind, which
Let
are defined for all integer numbers such that 0 ≤ k ≤ n. The
following two identities for Eulerian numbers of the second kind
are known (see Identities (6.42), and (6.44) in [5]):
X DD m EE
(2m)! 1
=
,
(6)
l
(m)! 2m
l
"
#
!
X DD p EE m + l
m
=
.
(7)
m−p
l
2p
l

√1
n

the expected
For interference distances s = v =
√
minimal 2−dimensional 2−total movement is in Θ ( n) .
√
√
If s = 1−ǫ
is below √1n and v = 1+τ
is above √1n ,
n
n
the expected minimal 2−dimensional 2−total movement
declines sharply to O (1) .

Then, high-order differences are defined by iteration

∆a f (x) = ∆∆a−1 f (x).
It is easy to prove by induction the following formula (see also [5,
Identity 5.40])
!
X a
a
(−1)a−j f (x + j).
(8)
∆ f (x) =
j
j

4

A crucial observation is the following identity, which will be
useful in the asymptotic analysis of Algorithm 1 when interference
distances s, v are equal to n1 .
Lemma 4. Assume that a is an even positive number. Then
!
"
# 
0
X a
if 2l1 < a
j
(−1)j
=
a!
if
2l1 = a.
a
 a !2 2
j
j − l1
(2)
j
 x 
Proof. Choosing f (x) = x−l
in (8) we see that
1
"
#
!
"
#
X a
x
x+j
a
a−j
∆
=
(−1)
x − l1
j
x + j − l1
j
x=0
x=0
!
"
#
X a
j
=
(−1)j
.
j
j − l1
j

Let f be non-negative integer. Then
n
X
i=2

3

This is enough to prove Lemma 4.

We will also use many times Jensen’s inequality for expectactions. If f is a convex function, then
(9)

provided the expectations exists (see [16, Proposition 3.1.2]).
The following inequality for the general random variable will
be useful in the threshold tight bounds when interference distances
are greater or equal to n1 .
If Z is the random variable such that E[|Z|] < ∞ and q ∈ R,
then
|E[Z] − q| ≤ E[|Z − q|] ≤ E[|Z|] + |q|.
(10)
Notice that the left side of Inequality (10) is the special case of
Jensen’s inequality for X := Z −q and f (x) = |x|. The right side
of Inequality (10) follows from the triangle inequality |Z − q| ≤
|Z| + |q| and the monotonicity of the expected value.
We will also use the following notation

|x|+ = max{x, 0}
for positive parts of x ∈ R.
The Euler Gamma function (see [15])
Z ∞
Γ(z) =
tz−1 e−t dt

(11)

(12)

0

is defined for z > 0. Notice that Γ(z) satisfies the following
functional equations

Γ(z + 1) = Γ(z)z.
Moreover, for n natural number we have

Γ(n + 1) = n!.

(i − 1)f =

f
X
1
cl n l ,
nf +1 +
f +1
l=0

(15)

where cl are some constants independent on n (see [5, Formula
(6.78)]).

Applying equations
(6), (7) and the following identity
(

0
if
2l1 < a
x+l
∆a 2l1
=
, we easily derive
x=0
1 if 2l1 = a
!
"
#
X  l1 
x
a x+l
a
∆
∆
=
l
2l1
x − l1
l
x=0
x=0

0
if
2l1 < a
DD a EE
= P
a!
2
= a a2 if 2l1 = a.
 l
l
( 2 )!2

f (E[X]) ≤ E [f (X)]

We will also use the following forms of Stirling’s formula (see
[3, page 54])
√
√
1
1
1
1
2πN N + 2 e−N + 12N +1 < N ! < 2πN N + 2 e−N + 12N . (14)

(13)

S ENSORS ON THE L INE

Let us recall that ǫ, τ > 0 are arbitrary small constants independent on n. In this section we analyze (s, v) − IP interference
problem when the sensors are placed in the half-infinite interval
[0, ∞) according to Poisson process with arrival rate n.
3.1 Analysis of Algorithm 1
In this subsection we present algorithm M V1 (n, s) (see Algorithm
1). We show
 that the expected a−total movement of algorithm
M V1 n, n1 is

2

a
2

 a
a!
a
 n1− 2 + O n− 2 ,
+1 !

a
2

when a is an even positive number.
We prove that the expected a−total movement of algorithm
M V1 n, 1+ǫ
is Θ(n), when a is an even positive number or
n
a = 1 and ǫ > 0.
Algorithm 1 M V1 (n, s) Moving sensors in the [0, ∞); s > 0.
Require: The initial location X1 ≤ X2 ≤ · · · ≤ Xn of the n
sensors in the [0, ∞) according to Poisson process with arrival
rate n.
Ensure: The final positions of the sensors such that each pair of
consecutive sensors is separated by the distance equal to s.
1: for i = 2 to n do
2:
move the sensor Xi at the position X1 + (i − 1)s;
3: end for
We prove the following theorem.
Theorem 5. Fix ǫ1 ≥ 0 independent on n. Let a be an even
natural number.
 The expected a−total movement of algorithm
1
is respectively
M V1 n, 1+ǫ
n

a
a
 a a!
when ǫ1 = 0,
n1− 2 + O n− 2
a
2
2 ( 2 +1)!
Θ (n)
when ǫ1 > 0.
Proof. Let Xi be the arrival time of the ith event in a Poisson
process with arrival rate n. We know that the random variable
Xi − X1 = Xi−1 obeys the Gamma distribution with density

fi−1,n (t) = ne−nt

(nt)i−2
(i − 2)!

for i = 2, 3, . . . , n. (see equation (1) for j = 1, l = i − 1).
(a)
Assume that, a is even natural number. Let Di be the expected

5
(1)
Di

distance to the power a between Xi − X1 and the i−th sensor
position, ti−1 = (1 + ǫ1 ) i−1
n , hence given by
Z ∞
(a)
Di =
|t − ti−1 |a fi−1,n (t)dt
0
Z ∞
(ti−1 − t)a fi−1,n (t)dt.
=

be the expected distance between Xi − X1 and
Proof. Let
the i−th sensor position, ti−1 = (1 + ǫ) i−1
n for i = 2, 3, . . . , n,
hence given by
Z ∞
(1)
|t − ti−1 |fi−1,n (t)dt.
Di =

Let j ∈ {0, . . . , a}. Applying Identity (5) we deduce that

This completes the proof of Theorem 6.

0

Let us recall that E [Xi − X1 ] = i−1
n (see (3) for l = i − 1).
Applying Inequality (10) for Z = Xi − X1 , q = ti−1 and ǫ > 0
Observe that
!

Z ∞
we have
X a 
i − 1 a−j
i−1
i−1
(a)
j
(1)
(−1)
tj fi−1,n (t)dt.
(1 + ǫ1 )
Di =
ǫ
≤ Di ≤ (2 + ǫ)
.
n
j
n
n
0
j
Pn
(n−1)n
, we have
Since i=2 (i − 1) =
Using the integral Identities (2) and (3) we see that
2
!
n
X (1)
1 X a
(i + j − 2)!
(a)
(16)
Di = Θ(n)
Di = a
(1 + ǫ1 )a−j (−1)j (i − 1)a−j
.
n j
(i − 2)!
j
i=2
0

(i + j − 2)!
(i − 1)a−j
= (i − 1)a−j (i − 1)j
(i − 2)!
"
#
X
j
(i − 1)a−l1 .
=
j
−
l
1
l
1

Hence
(a)
Di

"
!
#
1 XX a
j
= a
(1 + ǫ1 )a−j (−1)j (i − 1)a−l1
.
j − l1
j
n j l
1

Changing the summation we get
(a)
Di

!
"
#
X a
j
1 X
a−j
j
a−l1
(1 + ǫ1 ) (−1)
(i − 1)
.
= a
j
j − l1
n l
j
1

Now, we will estimate separately when ǫ1 = 0 and when ǫ1 > 0.
Case ǫ1 = 0.
Applying Lemma 4 we get
a
1 X
a!
1
(a)
C1,a−l1 · (i − 1)a−l1 ,
Di = a a  a · (i − 1) 2 + a
n 2 !2 2
n 2l >a

3.2 Expected Minimum a−total Movement for s = v =
1
n

In this subsection we look at the expected minimum a−total
movement when the interference distances
 s and v are equal to
1
1− a
2
.
We
prove
the
upper
bound
O
n
on the expected a−total
n
movement, when a > 0 (see Theorem 7). Our
Theorem 8 and
a
Theorem 9 give the lower bound Ω n1− 2 on the expected
a−total movement, when a ≥ 1.
We begin with a theorem which indicates how to apply the
results of Theorem 5 to the upper bound on the expected a−total
movement, when a > 0.
Theorem 7. Let a >
movement of
 0. The expected a−total
a
algorithm M V1 n, n1 is respectively O n1− 2 .
(a)

Proof. Assume that a > 0. Let Di be the expected distance to
the power a between Xi − X1 and the ith sensor position. Let
b be the even natural number such that b − a > 0. Then we use
b
discrete Hölder inequality with parameters ab and b−a
and get

1

where C1,a−l1 depends only on a and l1 . Using Identity (15) we
conclude that the expected
 sum of displacements to the power a
of algorithm M V1 n, n1 is
n
X
i=2

(a)

Di

=

2

a
2

a
a!
 n1− 2 + O n− 2 .
a
2 +1 !




a

This is enough to prove the case
 ǫ1 = 0.

Pwhen
Case ǫ1 > 0. Observe that j aj (−1)j (1+ǫ1 )a−j jj = ǫa1 .
Therefore
1 X
ǫa
(a)
C2,a−l1 · (i − 1)a−l1 ,
Di = 1a · (i − 1)a + a
n
n l >0
1

where C2,a−l1 depends only on a and l1 . Again, applying Identity
(15) we conclude that the expected sum
 of displacements to the
1
power a of algorithm M V1 n, 1+ǫ
is Θ(n). This is enough
n
to prove the case when ǫ1 > 0 which completes the proof of
Theorem 5.

n
X
i=2

(a)

Di

≤
=

n 
b
X
(a) a
Di
i=2

n 
b
X
(a) a
Di
i=2

! ab
! ab

n
X
i=2

1

! b−a
b

(n − 1)

b−a
b

.

(17)
b

Next we use Jensen’s inequality (see (9)) for f (x) = x a and
(a)
E[X] = Di and get

b
(a) a
(b)
Di
≤ Di .
(18)

Combining together (17), (18) and Theorem 5 we deduce that
 ab
 
n


X
b−a
a
1
(a)
Di ≤ Θ
(n − 1) b = Θ n1− 2 .
b
n 2 −1
i=2

This is enough to prove the upper bound which finishes the proof
of Theorem 7.

We also prove the following tight bound for 1−total movement
of Algorithm 1 when s = 1+ǫ
n and ǫ > 0.

We now prove the desired lower bound for expected 1−total
movement.

Theorem 6. Let ǫ > 0 be a constant independent on n. Then

is
the expected 1−total movement of algorithm M V1 n, 1+ǫ
n
respectively Θ(n).

Theorem
 8. Any sensor’s displacement algorithm which solves
1 1
,
n n −
√IP problem requires expected 1−total movement of at
least Ω ( n) .

6

Proof. Before providing the proof of the theorem we make two
important observations.
Let X1 < X2 < · · · < Xn be the initial positions of the
sensors. Recall that by the monotonicity lemma no sensor Xi is
ever placed before sensor Xj , for all i < j.
We assume that the final position of the first sensor is the
nonnegative random variable Z with E[Z] < ∞.
We are now ready to prove the theorem. Let Xi be the arrival
times of the i−th event in Poisson process with arrival rate. Let
1
ai = ni − 2n
, for i = 1, 2, . . . , n be the anchor points. The
following result was proved in [2, Lemma 1]
n
X
i=1

E [|Xi − ai |] = C1

√ 
√ 
n +o n ,

(19)

where C1 is some constant independent on n. There are two cases
to consider.
Case 1. The algorithm moves the sensor Xi to the position
Z + bi , where bi = n1 (i − 1), for i = 1, 2, . . . n and E[Z] >
C1
1√
2 n.
Combining together Inequality (10) for Z := Xi − Z , q = bi
Equation (3) for l = i and the triangle inequality we get
n
X
i=1

E [|Xi − Z − bi |] ≥

n
X
i=1

E[Z] −

This is enough to prove the first case.
Case 2. The algorithm moves the sensor Xi to the position
Z + bi , where bi = n1 (i − 1), for i = 1, 2, . . . n and E[Z] ≤
C1
1√
2 n.
i
n

be the expected distance
Proof. Assume that a > 1. Let
to the power a of i−th sensor for i = 1, 2, . . . , n. Then we use
a
discrete Hölder inequality with parameters a and a−1
and get
n
X

(1)
Ei

n 

X
(1) a
Ei

≤

i=1

i=1

n 

X
(1) a
Ei

=

i=1

! a1
! a1

n
X

1

i=1

n

a−1
a

! a−1
a

.

(20)

Next we use Jensen’s inequality (see (9)) for f (x) = xa and
(1)
E[X] = Ei and get


(1) a
(a)
Ei
≤ Ei .
(21)
Combining together (20), (21) and Theorem 8 we deduce that
!a
n
n
X
X
√ a −a+1
(a)
(1)
n
Ei ≥
Ei
n−a+1 = Ω n
i=1

i=1



a
= Ω n1− 2 .

This is enough to prove the lower bound and completes the proof
of Theorem 9.
3.3 Expected Minimum a−total Movement for
v

1
n


n 
X
√ 
1
1 C1
√ −
≥
=Θ n .
2
n
n
i=1

Let us recall that ai =
triangle inequality

(a)
Ei

1
− 2n
, for i = 1, 2, . . . , n. Using the

|Xi − ai | ≤ |Xi − (Z + bi )| + |(Z + bi ) − ai |

1
n

<s≤

In this subsection we study the expected minimum a−total
movement when the interference distances s and v are greater
than n1 . We give the upper bound O(n) on the expected a−total
movement, when a > 0 (see Theorem 10) and the lower bound
Ω(n) on the expected a−total movement, when a ≥ 1 (see
Theorem 11 and Theorem 12).
We begin with a theorem which indicates how to apply the
results of Theorem 5 to the upper bound on the expected a−total
movement, when a > 0.
Theorem 10. Let ǫ > 0 be a constant independent on n. Let a >
0. The expected a−total movement of algorithm M V1 n, 1+ǫ
is
n
in O(n).
(a)

we get
n
X
i=1

E [|Xi − (Z + bi )|] ≥

n
X
i=1

E [|Xi − ai |]−

n
X
i=1

E Z−

1
.
2n

C1
and
Combining together Equation (19), assumption E[Z] ≤ 12 √
n


1
1
the triangle inequality E Z − 2n ≤ E[Z] + 2n we have
n
X
i=1

E [|Xi − (Z + bi )|] ∈ Ω(n).

This is enough to prove the second case and sufficient to complete
the proof of Theorem 8.

Proof. Let Di be the expected distance to the power a between
Xi − X1 and the ith sensor position. Let b be the even natural
number such that b − a > 0. Then we proceed as in the upper
bound treatment from the proof of Theorem 7 and get
n
X

(a)
Di

i=2

≤

n 
b
X
(a) a
Di
i=2



(a)

Di

 ab

! ab

(n − 1)

b−a
b

(b)

≤ Di

(22)

(23)

Combining together (22), (23) and Theorem 5 we deduce that
n
X
i=2

(a)

Di

a

≤ (Θ(n)) b (n − 1)

b−a
b

= Θ(n).

This is sufficient to complete the proof of Theorem 10.
We now apply Theorem 8 in order to derive the lower bound
on the expected a−total movement when a > 1.

We can now prove the desired lower bound for expected
1−total movement.

Theorem 9. Let a > 1. Then any sensor’s displacement algorithm
which solves n1 , n1 − IP problem
requires expected a−total
a
movement of at least Ω n1− 2 .

Theorem 11. Fix τ ≥ ǫ > 0 independent on n. Then
 any sensor’s
1+τ
displacement algorithm which solves 1+ǫ
− IP problem
,
n
n
requires expected 1−total movement of at least Ω(n).

7

Proof. The proof of the theorem is analogous to the proof of
Theorem 8.
Fix τ ≥ ǫ > 0 independent on n. Let Xi be the arrival
times of the i−th event in Poisson process with arrival rate. We
assume that the algorithm moves the sensor Xi to the position
i
bi = Z + 1+∆
n (i − 1) provided ǫ ≤ ∆i ≤ τ for i = 1, 2, . . . , n,
where Z is the nonnegative random variable with E[Z] < ∞.
It is sufficient to show that
n
X
i=1

E [|Xi − bi |] ∈ Ω(n).

Applying Inequality (10) for Z := Xi −Z −∆i i−1
n , q =
and Equation (3) for l = i we get



n
X
1 + ∆i
E Xi − Z +
(i − 1)
n
i=1

i−1
n

n
X
E[∆i ]
1 + E[∆i ]
i + E[Z] −
n
n
i=1


n
X E[∆i ]
1 + E[∆i ]
≥
i + E[Z] −
n
n
i=1


n
X ǫ
1+τ
= Θ(n)
i + E[Z] −
≥
n
n
i=1

≥

This completes the proof of Theorem 11.
We now apply Theorem 11 in order to derive the lower bound
on the expected a−total movement when a > 1.
Theorem 12. Fix τ ≥ ǫ > 0 independent on n. Let a > 1. Then

1+τ
−
any sensor’s displacement algorithm which solves 1+ǫ
n , n
IP problem requires expected a−total movement of at least Ω(n).

Algorithm 2 I1 (n, s, v) Moving sensors in the [0, ∞); 0 < s <
v.
Require: The initial location X1 ≤ X2 ≤ · · · ≤ Xn of the n
sensors in the [0, ∞) according to Poisson process with arrival
rate n.
Ensure: The final positions of the sensors such that
∀i=2,3...,n v ≥ Xi − Xi−1 ≥ s (so as that the distance
between consecutive sensors is less or equal v and greater or
equal to s).
1: for i = 2 to n do
2:
if Xi − Xi−1 < s then
3:
move left-to-right the sensor Xi at the new position s +
Xi−1 ;
4:
else if Xi − Xi−1 > v then
5:
move right-to-left the sensor Xi at the new position v +
Xi−1 ;
6:
else
7:
do nothing;
8:
end if
9: end for
Lemma 13. Fix ǫ > 0 independent on n. Let a > 0 and let
s = 1−ǫ
n . Assume that random variable Xl obeys the Gamma
distribution with parameters l, n. Then
n
X

n 
E (|sl − Xl |+ )a = O(n1−a ).
l
l=1
Proof. See Appendix for the proof.

Lemma 14. Fix τ > 0 independent on n. Let a > 0 and let
v = 1+τ
n . Assume that random variable Xl obeys the Gamma
distribution with parameters l, n. Then
n
X
n

(a)

Proof. Assume that a > 1. Let Ei be the expected distance to
the power a of i−th sensor for i = 1, 2, . . . , n. As in the proof of
Theorem 9 we get two inequalities:
n
X

(1)

Ei

i=1

≤

n 

X
(1) a
Ei
i=1

! a1



(1) a
(a)
Ei
≤ Ei .

n

a−1
a

,

(24)

(25)

Combining together (24), (25) and Theorem 11 we deduce that
!a
n
n
X
X
(a)
(1)
a
n−a+1 = (Ω(n)) n−a+1 = Ω(n).
Ei ≥
Ei
i=1

i=1

This is enough to prove the lower bound and completes the proof
of Theorem 12.
3.4 Expected Minimum a−total Movement for s <
and v > n1

1
n

In this subsection we give algorithm I1 (n, s, v) (see Algorithm
2) to solve (s, v) − IP interference problem. Let ǫ, τ > 0
be constants independent on n. Let a > 0. We show
 that
1+τ
is in
,
expected a−total movement of algorithm I1 n, 1−ǫ
n
n
O n1−a .
We begin with the following two lemmas which will be helpful
in the proof of Theorem 15.

l=1

l



E (|Xl − vl|+ )a = O(n1−a ).

Proof. See Appendix for the proof.

We can now prove the desired result.
Theorem 15. Fix ǫ, τ > 0 independent on n. Let a > 0.
 The
1+τ
is in
,
expected a−total movement of algorithm I1 n, 1−ǫ
n
n
O n1−a .
1+τ
Proof. Let s = 1−ǫ
n , v = n , where ǫ and τ are arbitrary small
constants independent on n.
Firstly, we consider the following scenario.
•
•
•

Algorithm 2 leaves the sensors X1 , X2 , . . . , Xi at the
same positions.
Algorithm 2 moves the sensors Xi+1 , Xi+2 , . . . Xi+q at
the new locations.
Algorithm 2 leaves the sensors Xi+q+1 , Xi+q+2 , . . . , Xn
at the same positions.

Let q = q1 + q2 + · · · + qk for some q1 , q2 , . . . , qk ∈ N+ . Define
(
0 if i = 0
Si =
q1 + q2 + · · · + qi if i ∈ {1, 2, . . . , k − 1}.
Consider an integer configuration (q1 , q2 , . . . , qk ) as specified
above.
•

For each i ∈ {0, 1, . . . , k − 1} Algorithm 2 moves the
sensors XSi +1 , XSi +2 , . . . , XSi +qi+1 in the one chosen
direction left to right or right to left.

8
•

For each i ∈ {0, 1, . . . , k − 2} the movement direction of sensors XSi +1 , XSi +2 , . . . , XSi +qi+1
is opposite to the movement direction of sensors
XSi+1 +1 , XSi+1 +2 , . . . , XSi+1 +qi+2 .

Let T (q1 , q2 , . . . , qk ) be the movement to the power a of the sensors Xi+1 , Xi+2 , . . . Xi+q and let T (qk ) be the displacement to
the power a of the sensors XSk−1 +1 , XSk−1 +2 , . . . , XSk−1 +qk .
There are two cases to consider.
Case 1. The sensor XSk−1 moves left to right to the new
position Y and the sensors XSk−1 +1 , XSk−1 +2 , . . . , XSk−1 +qk
move right to left.
Observe that
qk 

X
+ a
XSk−1 +l − (Y + vl)
.
T (qk ) =
l=1

Since XSk−1 < Y we upper bound the displacement T (qk ) as
follows
qk 
X
 + a
XSk−1 +l − XSk−1 + vl
.
T (qk ) ≤
l=1

Using Identity Xi+l − Xi = Xl for i := Sk−1 (see (1)) we get

T (qk ) ≤

qk
X
l=1

(|Xl − vl|+ )a .

(26)

Case 2. The sensor XSk−1 moves right to left to the new
position Z and the sensors XSk−1 +1 , XSk−1 +2 , . . . , XSk−1 +qk
move left to right.
Observe that
qk 

X
+ a
.
Z + sl − XSk−1 +l
T (qk ) =

Observe that the displacements E [(|sl − Xl |+ )a ] and |Xl −
vl|+ )a can appear in the Algorithm 2 at most nl times. Therefore

Ta ≤

n
X
n
l=1

l

(|sl − Xl |+ )a +

n
X
n
l=1

l

(|Xl − vl|+ )a

Passing to the expectations we have

E [Ta ] ≤

n

 X

n 
E (|sl − Xl |+ )a +
E (|Xl − vl|+ )a
l
l
l=1

n
X
n
l=1

1+τ
Finally, using Lemma 13 for s = 1−ǫ
n and
 Lemma 14 for v = n
1−a
we conclude that E [Ta ] = O n
. This is enough to prove
Theorem 15.

4

S ENSORS IN THE H IGHER D IMENSION .

Fix d ∈ N \ {0}. Let us recall that ǫ, τ > 0 are arbitrary small
constants independent on n.
We consider n sensors that are placed in the hyperoctant
[0, ∞)d according to d identical and independent Poisson pro(d)
(2)
(1)
cesses Xi , Xi , . . . , Xi , for i = 1, 2, . . . , n1/d each with
1/d
arrival rate n . The position of a sensor in the R+ is de(d)
(2)
(1)
termined by the d coordinates (Xi1 , Xi2 , . . . , Xid ), where
1 ≤ i1 , i2 , . . . , id ≤ n1/d .
Hence, we have initially n(d−1)/d rows and n(d−1)/d columns
such that each column and each row has n1/d sensors. Figure 4
illustrates our random displacement of sensors in two dimensions.
(2)

s

s

s

s

(2)

s

s

s

s

(2)

s

s

s

s

(2)

s

s

s

s

X4

X3

l=1

Since Z < XSk−1 we upper bound the displacement T (qk ) as
follows
qk 

X
+ a
.
XSk−1 + sl − XSk−1 +l
T (qk ) =

X2

l=1

X1

Using Identity Xi+l − Xi = Xl for i := Sk−1 (see (1)) we get

T (qk ) ≤

qk
X
l=1

(|sl − Xl |+ )a .

(27)

Combining together inequalities (26) and (27) we have

T (q1 , q2 , . . . , qk ) ≤T (q1 , q2 , . . . , qk−1 ) +
+

qk
X
l=1

qk
X
(|Xl − vl|+ )a
l=1

(|sl − Xl |+ )a .

Hence, by induction we get

(1)

≤

j=1 l=1

(|Xl − vl| ) +

qj
k X
X
j=1 l=1

+ a

(|sl − Xl | ) .

Next we make an important observation that extends our estimation to general scenario of Algorithm 2. Let Ta be the a−total
displacement of Algorithm 2.

(1)

X4

We reallocate the sensors so as:
(a)
(b)
(c)

+ a

(1)

X3

Fig. 1. The mobile sensors located in the quadrant [0, ∞)2 according to
2 identical and independent Poisson processes.

T (q1 ,q2 , . . . , qk )
qj
k X
X

(1)

X1 X2

the sensors move only along the axes,
we have finally n(d−1)/d rows and n(d−1)/d columns
such that each column and each row has n1/d sensors,
in each column and in each row the sensors satisfy
(s, v) − IP interference requirement.

In order to fulfill the requirements (a), (b), (c) two algorithms
are presented. Namely,
•

1
1
for the case of s = n1/d
, v = n1/d
we show that the
expected d−dimensional
a−
total
movement
of algorithm

a 
1
is in O n1− 2d (see proof of Theorem
M Vd n, n1/d
17),

9
•

1−ǫ
,
n1/d

1+τ
n1/d

v =
we prove that the
for the case of s =
expected d−dimensional
a−
total
movement
of algorithm


1+τ
1− a
d
Id n, n1−ǫ
(see
Theorem
19).
,
is
in
O
n
1/d n1/d

Algorithm 3 M Vd (n, s) Moving sensors in the [0, ∞)d , d ≥ 2,
s > 0.
(1)

(2)

(d)

Require: The initial location (Xi1 , Xi2 , . . . , Xid ) of the n
sensors in the [0, ∞)d , 1 ≤ i1 , i2 , . . . , id ≤ n1/d .
Ensure: The final positions of the sensors such that in each
column and in each row the consecutive sensors are separated
by the distance equal to s.
move the sensor at
1: ∀1 ≤ i ,i ,...,i ≤ n1/d
1 2
d
(1)

(d)

(2)

the location (Xi1 , Xi2 , . . . , Xid ) to the
(d)
(2)
(1)
(X1+(i1 −1)s , X1+(i2 −1)s , . . . , X1+(id −1)s );

position

Algorithm 4 Id (n, s, v) Moving sensors in the [0, ∞)d , d ≥ 2,
0 < s < v.
(1)

(2)

(d)

Require: The initial location (Xi1 , Xi2 , . . . , Xid ) of the n
sensors in the [0, ∞)d , 1 ≤ i1 , i2 , . . . , id ≤ n1/d .
Ensure: The final positions of the sensors such that in each
column and in each row the sensors satisfy (s, v) − IP
interference requirement.
1: For each column and row in the [0, ∞)d apply algorithm
I1 (n1/d , s, v);
We call a move of a sensor a sliding move if the final position
of the sensor is either in the same row or column as its initial
position.
In this section, we restrict the movement of sensors to a sliding
movement. The claim is justified in Lemma 16 whose simple proof
is omitted. Such a reduction of the movement is indeed crucial and
reduces the displacement of sensors in the higher dimension to the
displacement of sensors in the half-infinite interval [0, ∞).
Lemma 16. The optimal reallocation of sensors which ensures
the requirements (a), (b), (c) is a sliding movement.
We now embark to extend the results from Section 3 to the high
dimensions. We can prove the following sequences of Theorem.
The next theorem clarifies how the interference distances s =
1
1
, v = n1/d
affect the expected minimum d−dimensional
n1/d
a−total movement.
Theorem 17. Let a > 0 be a constant. Assume that n sensors
are placed in the [0, ∞)d according to d independent identical
Poisson processes, each with arrival rate n1/d and the reallocation of sensors ensures the requirements (a), (b), (c). If the
1
1
interference distances s = n1/d
, v = n1/d
then the expected
minimal d−dimensional a−total movement is in
(
a 
Θ n1− 2d
if a ≥ 1,
a 
1− 2d
O n
if a ∈ (0, 1).

Proof. First of all, we discuss the proof of the upper bound. By
Theorem 7 applied to n := n1/d and for n(d−1)/d columns and
n(d−1)/d rows we have that the expected
 d−dimensional a−total
1
movement of algorithm M Vd n, n1/d
is



1− a2 
a
2n(d−1)/d O n1/d
= O n1− 2d , when a > 0.

Next we prove the lower bound. Since the movement of sensors
along the axes is a sliding move to attain the interference distances
1
1
s = n1/d
, v = n1/d
in the [0, ∞)d the sensors have to attain the
1
1
interference distances s = n1/d
, v = n1/d
in each column and
each row. By Theorem 8 and Theorem 9 applied to n := n1/d and
for n(d−1)/d columns and n(d−1)/d rows we have the following
lower bound



1− a2 
a
2n(d−1)/d Ω n1/d
= Ω n1− 2d , when a ≥ 1.
This is sufficient to complete the proof of Theorem 17.

We now analyze the expected minimum d−dimensional
a−total movement when the interference distances s and v are
1
.
greater than n1/d
Theorem 18. Fix τ ≥ ǫ > 0 independent on n. Let a > 0
be a constant. Assume that n sensors are placed in the [0, ∞)d
according to d independent identical Poisson processes, each with
arrival rate n1/d and the reallocation of sensors ensures the
requirements (a), (b), (c). If the interference distances are equal to
1+τ
s = n1+ǫ
1/d , v = n1/d , then the expected d−dimensional a−total
movement is in
(
Θ(n) if a ≥ 1,
O(n) if a ∈ (0, 1).
Proof. Fix τ ≥ ǫ > 0 independent on n. The proof is analogous
to the proof of Theorem 17. By Theorem 10 applied to n :=
n1/d and for n(d−1)/d columns and n(d−1)/d rows and have the
expected a−total movement of algorithm M Vd n, n1+ǫ
is
1/d


2n(d−1)/d O n1/d = O(n), when a > 0.
This completes the prove of upper bound.
By Theorem 11 and Theorem 12 applied to n := n1/d and for
(d−1)/d
n
columns and n(d−1)/d rows we have that the following
lower bound


2n(d−1)/d Ω n1/d = Ω (n) , when a ≥ 1.
This is enough to prove Theorem 18.

The next theorem provides the expected minimum
1
1
d−dimensional a−total movement for s < n1/d
and v > n1/d
.
Theorem 19. Fix ǫ, τ > 0 independent on n. Let a > 0 be
a constant. Assume that n sensors are placed in the [0, ∞)d
according to d independent identical Poisson processes, each with
arrival rate n1/d and the reallocation of sensors ensures the
requirements (a), (b), (c). The expected d−dimensional a−total
a
1+τ
movement of algorithm Id n, n1−ǫ
is in O n1− d .
1/d , n1/d
Proof. Fix ǫ, τ > 0 independent on n. By Theorem 15 applied to
n := n1/d and for n(d−1)/d columns and n(d−1)/d rows we have
the following upper bound


1−a 

a
2n(d−1)/d O n1/d
= O n1− d , when a > 0

which proves the theorem.

5

C ONCLUSION

In this paper we obtained tradeoffs between interference distances s, v and the expected minimum (a−total
movement)/(d−dimensional a−total movement) of n random
sensors.

10

R EFERENCES
[1]

[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]

[13]
[14]
[15]
[16]

Wattenhofer R. Burkhart, M. and A. Zollinger. Does topology control
reduce interference? In Proceedings of the 5th ACM International
Symposium on Mobile Ad Hoc Networking and Computing, pages 9–19.
ACM, 2004.
Kranakis E. and Shaikhet G. Displacing random sensors to avoid
interference. In COCOON, volume 8591 of LNCS, pages 501–512.
Springer, 2014.
W. Feller. An Introduction to Probability Theory and its Applications,
volume 1. John Wiley, NY, 1968.
Evans M. Hastings N. Peacock B. Forbes, C. Statistical Distributions.
John Wiley & Sons, 2011.
R. Graham, D. Knuth, and O. Patashnik. Concrete Mathematics A
Foundation for Computer Science. Addison-Wesley, Reading, MA, 1994.
P. Gupta and P.R. Kumar. The capacity of wireless networks. IEEE
Transactions on Information Theory, 46(2), 2000.
M. Halldórsson and T. Tokuyama. Minimizing interference of a wireless
ad-hoc network in a plane. Theoretical Computer Science, 402(1), 2008.
Padhye J. Padmanabhan V.N. Jain, K. and L. Qiu. Impact of interference
on multi-hop wireless network performance. Wireless Networks, 11(4),
2005.
J.F.C. Kingman. Poisson Process, volume 3. Oxford University Press,
1992.
E. Kranakis. On the event distance of poisson processes with applications
to sensors. Discrete Applied Mathematics, 179:152 – 162, 2014.
E. Kranakis and G. Shaikhet. Sensor allocation problems on the real line.
Journal of Applied Probability, 53(3):667–687, 2016.
Wang X. L. Fu, L. and P.R. Kumar. Optimal determination of sourcedestination connectivity in random graphs. In Proceedings of the 15th
ACM International Symposium on Mobile Ad Hoc Networking and
Computing, pages 205–214. ACM, 2014.
Wang X. L. Fu, L. and P.R. Kumar. Are we connected? optimal
determination of source-destination connectivity in random networks.
IEEE/ACM Transactions on Networking, PP(99):1–14, 2016.
T. Moscibroda and R. Wattenhofer. Minimizing interference in ad hoc
and sensor networks. In Proceedings of the 2005 Joint Workshop on
Foundations of Mobile Computing, pages 24–33. ACM, 2005.
NIST Digital Library of Mathematical Functions. http://dlmf.nist.gov/5.
S. M. Ross. Probability Models for Computer Science. Academic press,
2002.

11

A PPENDIX
Proof. (Lemma 13) First of all observe that
h
i Z sl
+ a
E (|sl − Xl | ) =
(sl − t)a fl,n (t)dt
0
Z sl
≤ (sl)a
fl,n (t)dt,

Applying Identity (4) for z = rl and b = ⌈a⌉ we have
Z
(28)

∞

t

⌈a⌉

rl

(l − 1 + ⌈a⌉)! −nrl
fl,n (t)dt =
e
(l − 1)!n⌈a⌉

0

0

(l−1)!

e

(30)

Applying Stirling’s formula (14) for N = l we get
1
ll
≤ el l 2 .
(l − 1)!

(31)

Using (31) with assumption s = 1−ǫ
n in Inequality (30) we imply
(

Z sln
sne l 21
l
if l ≥ 1ǫ
xl−1
esn
(32)
dx ≤ snl
e−x
(l−1)l−1
(l − 1)!
if l < 1ǫ .
0
el−1 (l−1)!
Putting together (28), (29) and (32) we have
n
X
n
l=1

l



E (|sl − Xl |+ )a

≤n

1−a



a

(ns)



n 
X
nse l

ens

l≥ 1ǫ

+ n1−a (ns)a+1

l
X
(nrl)j
(nrl)l
≤ (l + 1)
.
j!
(l)!
j=0

l




X la (l − 1)l−1
.
el−1 (l − 1)!
1

l< ǫ

l≥ ǫ

l< ǫ

l

j=l+1

l⌈a⌉−1 (nrl)l
(nrl)j
≤ (⌈a⌉ − 1) (nr)⌈a⌉−1
.
j!
l + 1 (l)!

(38)

From Stirling’s formula (14) for N = l we get

ll
el
(39)
≤ 1 ≤ el .
l!
l2
Putting all together (35–39) we have
h
⌈a⌉ i
1  nre l
E |Xl − vl|+
≤ f (l) ⌈a⌉
,
(40)
enr
n
where
!
⌈a⌉−1
(l − 1 + ⌈a⌉)!
⌈a⌉−1 l
.
f (l) = (l + 1) + (⌈a⌉ − 1)(nr)
l+1
(l − 1)!
Since rn = 1 + τ is some constant independent on n we derive


f (l) = Θ lmax(⌈a⌉+1,2⌈a⌉−2) .
(41)
⌈a⌉
a

and

(42)

Together (40) and (42) imply that

E

(34)




E (|sl − Xl |+ )a = O n1−a .

This is enough to prove Lemma 13.

Proof. (Lemma 14) Let ⌈a⌉ be the smallest integer greater or
equal to a. Observe that

⌈a⌉  Z ∞
+
E |Xl − vl|
(t − rl)⌈a⌉ fl,n (t)dt
=
rl
Z ∞
≤
t⌈a⌉ fl,n (t)dt.
(35)
rl

X

(33)

Finally, putting together (33) and (34) we get
n
X
n

l+⌈a⌉−1

a
h
a i  
⌈a⌉  ⌈a⌉
+
+
.
E |Xl − vl|
≤ E |Xl − vl|

a− 12 

(37)

Observe that

Next we apply Jensen’s inequality (see (9)) for f (x) = x

⌈a⌉
+
X = |Xl − vl|
and get

Combining assumption sn < 1 with the elementary inequality
xe < ex when x < 1 we deduce that nse
ens < 1. Hence
n


X nse l
X la (l − 1)l−1
a− 12
a+1
= O(1).
l
(ns)a
+
(ns)
ens
el−1 (l − 1)!
1
1

l=1

Hence

−x l−1

Observe that, the function g(x) = e x
is monotonically
increasing over the interval [0, l−1] and monotonically decreasing
over the interval [l − 1, ∞]. Therefore, we easily derive the
following inequality
Z sln
xl−1
xl−1
dx ≤ sln max e−x
e−x
(l − 1)!
x∈[0,sln]
(l − 1)!
0


l
l
l
 sn
if sln ≤ l − 1
esn
(l−1)!
= snl
l−1
(l−1)
 l−1
if sln > l − 1.

j=0

(nrl)j
.
j!
(36)

(nrl)j
(nrl)j+1
≤
, when j ≤ l − 1.
j!
(j + 1)!

l−1

. The substitution tn = x yields
Z sln
xl−1
fl,n (t)dt =
e−x
dx.
(29)
(l − 1)!
0

X

Using assumption rn > 1 we can easily derive

ne−nt (nt)
(l−1)!

where fl,n (t) =
Z sl

l−1+⌈a⌉


a l
h
a i
a
1  nre  ⌈a⌉
+
|Xl − vl|
.
≤ f (l) ⌈a⌉ a
n
enr

(43)

Combining assumption rn > 1 with the elementary inequality
xe < ex , when x > 1 we deduce that
nre
< 1.
(44)
enr
From (41) and (44) we have
a

n
a l
X
f (l) ⌈a⌉  nre  ⌈a⌉
= O(1).
(45)
l
enr
l=1
Finally, putting together (43) and (45) we get
n
X
n
l=1

l




E (|Xl − vl|+ )a = O n1−a .

This is enough to prove Lemma 14.

