# A Note on the Large Deviation Principle for Discrete Associated Random Variables

Authors: Przemysław Matuła; Maciej Ziemba
Journal: Journal of Probability
 (2015)

---

## Abstract

We present sufficient conditions under which the sequence of arithmetic meansS
n
/
n, where S
n
=
X
1
+
⋯
+
X
n, is the partial sum built on a stationary sequence {
X
n
}
n
≥
1 of associated integer-valued and uniformly bounded random variables, which satisfy the large deviation principle.


---

## Body

## 1. Introduction and the Notation

Let{
X
n
}
n
≥
1 be a strictly stationary sequence of square-integrable random variables (r.v.’s). Denote S
n
=
∑
i
=
1
n
X
i, μ
=
E
X
1, and σ
2
=
Var
⁡
X
1
+
2
∑
i
=
2
∞
Cov
(
X
1
,
X
i
). Consider a sequence satisfying the strong law of large numbers (SLLN) and the central limit theorem (CLT), that is, S
n
-
n
μ
/
σ
n
→
d
N
(
0,1
). SLLN asserts that the arithmetic mean S
n
/
n converges to μ almost surely when n
→
∞, whereas the CLT specifies the probability that S
n differs from μ
n by the quantity of order n. Such deviation is called normal. However, in the case of S
n and μ
n being distant by the quantity of order n, we deal with so-called large deviation events.It turns out that under certain condition on the tail distribution function ofX
i, for a
>
0, the probability P
(
S
n
≥
(
μ
+
a
)
n
) tends to zero with exponential rate; that is,
(1)
lim
⁡
n
→
∞
1
n
ln
⁡
P
S
n
n
≥
μ
+
a
=
-
I
(
a
)
<
0
,
n
⟶
∞
,
where I
(
a
) is called the rate function.In the i.i.d. case, the well-known Cramer theorem gives the explicit formula for the rate function (see, for example, [1]). Let us recall that if the moment generating function φ
(
t
)
=
E
e
t
X
1 is finite for all t
∈
R, then lim
⁡
n
→
∞
(
1
/
n
)
ln
⁡
P
S
n
≥
a
n
=
-
I
(
a
) for all a
>
μ, where
(2)
I
(
z
)
=
sup
⁡
t
∈
R
z
t
-
ln
⁡
φ
t
,
which means that I
(
z
) is the Fenchel-Legendre transform of the function ln
⁡
φ
(
t
).In general setting, we follow [1] to give the definition of the rate function as the function defined on a Polish space X, taking values in closed half line [
0
,
∞
] and satisfying three conditions:(i)
I is not identically infinite;
(ii)
I is lower semicontinuous;
(iii)
I
-
1
(
[
0
,
c
]
) is compact for all c
>
0.Let us further recall that it is said that the sequence of probability measures{
P
n
}
n
≥
1 satisfies the large deviation principle (LDP) with rate n and the rate function I, if(D1)
I is the rate function in the sense of the invoked definition;
(D2)
limsup
⁡
n
→
∞
(
1
/
n
)
ln
⁡
P
n
F
≤
-
inf
⁡
x
∈
F
I
x, for all closed F
⊂
R;
(D3)
liminf
⁡
n
→
∞
(
1
/
n
)
ln
⁡
P
n
G
≥
-
inf
⁡
x
∈
G
I
x, for all open G
⊂
R.It is also well known that the rate function corresponding to the sequence {
P
n
}
n
≥
1 is uniquely determined.The role of open and closed sets in the above definition is similar to the one they play in Portmanteau theorem stating equivalent conditions for the weak convergence of probability measures. In fact, LDP may be thought of as the analogue of the weak convergence but in the exponential scale. Bryc [2] proved that if the sequence of probability measures {
P
n
}
n
≥
1 is exponentially tight (see Appendix) and for all continuous and bounded functions F defined on the Polish space X (denoted by C
B
(
X
)) the limit
(3)
R
∋
Λ
(
F
)
∶
=
lim
⁡
n
→
∞
1
n
ln
⁡
∫
X
‍
e
n
F
(
x
)
P
n
(
d
x
)
exists, then {
P
n
}
n
≥
1 satisfies LDP with rate n and the rate function
(4)
I
x
=
sup
⁡
F
∈
C
B
X
F
x
-
Λ
F
,
x
∈
X
.This result explains the relation between the LDP and the concept of weak convergence of probability measures. Moreover, it appears very useful in proving the LDP, since it suffices to show existence ofΛ
(
F
) for sufficiently large subfamily of continuous and bounded functions.There is only a few results on LDP for dependent r.v.’s other than Markov processes. Bryc [3] and Bryc and Dembo [4] studied LDP for strongly mixing sequences of r.v.’s; Henriques and Oliveira [5, 6] dealt with stationary sequences of associated absolutely continuous r.v.’s. They assumed that the probability density function f
S
n
/
n of the random variable S
n
/
n satisfies the following condition:
(5)
f
S
n
/
n
x
≤
a
·
B
n
,
for
some
a
>
0
,
B
>
1
.Our goal is to extend the results of Henriques and Oliveira [5, 6] by proving the LDP for a stationary sequence {
X
n
}
n
≥
1 of integer-valued r.v.’s satisfying the following additional conditions:(A1)
X
i, i
≥
1, are associated;
(A2)
X
i, i
≥
1, are uniformly bounded; that is, there exists M
>
0 such that P
(
X
i
≤
M
)
=
1;
(A3)
u
(
n
)
∶
=
∑
j
=
n
+
1
∞
Cov
(
X
1
,
X
j
)
≤
a
0
·
exp
⁡
(
-
n
ln
⁡
1
+
b
n
) for some a
0
,
b
>
0.For the definition of associated r.v.’s and their properties we refer the reader to the monographs of Bulinski and Shashkin [7], Oliveira [6], and Rao [8].The paper is organized as follows. Section2 presents the LDP in question, its proof, and an example demonstrating the applicability of the result. For convenience while reading, we place the technical lemmas used in the proof in Section 3. At the end, in the Appendix, we recall the Gärtner-Ellis theorem and essential results of Varadhan [9] and Bryc [2] as well as two lemmas on convergence of real sequences. In the proofs we will follow the ideas of Henriques and Oliveira [5, 6].


## 2. Main Result

Theorem 1.
Let{
X
n
}
n
≥
1 be a strictly stationary sequence of integer-valued r.v.’s satisfying conditions (A1), (A2), and (A3). Then the sequence of probability measures {
P
n
(
·
)
=
P
S
n
/
n
∈
·
}
n
≥
1 satisfies the large deviation principle with rate n and the rate function Λ
*
(
x
) being Fenchel-Legendre transform of the function
(6)
Λ
(
t
)
=
lim
⁡
n
→
∞
1
n
ln
⁡
E
e
t
S
n
,
which means that
(7)
Λ
*
x
=
sup
⁡
t
∈
R
x
t
-
Λ
t
,
x
∈
R
.Proof.
The main tool in proving LDP for dependent r.v.’s is the Gärtner-Ellis theorem (see Appendix) which states that it is enough to verify the existence of limit (6) together with the differentiability of Λ to have LDP.
To be more precise, in order to obtain the upper bound (A.1), we need to prove that limit (6) exists, which is shown in Lemma 3 (see Section 3). Actually, we prove even more—the finiteness of (6) for all t
∈
R.
With a view to getting the lower bound (A.2), we first need to verify the existence of a more general limit
(8)
Λ
(
G
)
=
lim
⁡
n
→
∞
1
n
ln
⁡
E
e
n
G
S
n
/
n
for any real continuous, concave, and bounded from above function G (the class of such functions will be denoted by C
C
B
A
(
R
)). It is presented in Lemma 4, Section 3. In fact, these are continuous and bounded functions (
C
B
(
R
)
) which is required in limit (A.5). Nevertheless, in order to claim the sole existence of this limit, it suffices to consider the subfamily C
C
B
A
(
R
), since it is well separated (see Definition B.7 and Theorem B.8 in [6]).
Further, from (A2), it is easy to see that the distributions ofS
n
/
n are exponentially tight (see Appendix).
As a result, by LemmaA.4, we can claim that the LDP holds with rate n and the rate function
(9)
I
(
x
)
=
sup
⁡
F
∈
C
B
R
F
x
-
Λ
F
.
However, to make sure that I is the Fenchel-Legendre transform of Λ
(
t
) defined by (6), we are still in need of showing convexity of I (see Lemma A.2). To this end, somewhat unobvious implication is inevitable. If x
1
,
x
2
∈
R are such that, for all δ
>
0, liminf
⁡
n
→
∞
(
1
/
n
)
ln
⁡
P
S
n
/
n
-
x
i
<
δ
>
-
∞ for i
∈
{
1,2
}, then
(10)
inf
⁡
δ
>
0
liminf
⁡
n
→
∞
1
n
ln
⁡
P
S
2
n
/
2
n
-
x
1

+

x
2
/
2
<
δ
P
S
n
/
n

-

x
1
<
δ
/
2
P
S
n
/
n
-
x
2
<
δ
/
2
≥
0
.
It is shown in Lemma 6.
We are already in a position to prove the convexity ofI, proceeding exactly like in the proof of Theorem 3.20 in [6]. According to Theorem B.2 in [6], the rate function I may be presented in the following form:
(11)
I
x
=
-
inf
⁡
δ
>
0
,
y
:
|
y
-
x
|
<
δ
liminf
⁡
n
→
∞
1
n
ln
⁡
P
S
n
n
-
y
<
δ
=
-
inf
⁡
δ
>
0
,
y
:
|
y
-
x
|
<
δ
limsup
⁡
n
→
∞
1
n
ln
⁡
P
S
n
n
-
y
<
δ
.
Since for y
∈
(
x
-
δ
,
x
+
δ
) there exists δ
′ such that (
x
-
δ
′
,
x
+
δ
′
) is immersed in (
y
-
δ
,
y
+
δ
), it is enough to write
(12)
I
x
=
-
inf
⁡
δ
>
0
liminf
⁡
n
→
∞
1
n
ln
⁡
P
S
n
n
-
x
<
δ
=
-
inf
⁡
δ
>
0
limsup
⁡
n
→
∞
1
n
ln
⁡
P
S
n
n
-
x
<
δ
.
Let us now take x
1
,
x
2
∈
R such that I
(
x
1
)
,
I
(
x
2
)
<
∞. As the assumption of Lemma 6 is satisfied, we have
(13)
inf
⁡
δ
>
0
liminf
⁡
n
→
∞
1
n
ln
⁡
P
S
2
n
/
2
n
-
x
1

+

x
2
/
2
<
δ
P
S
n
/
n

-

x
1
<
δ
/
2
P
S
n
/
n
-
x
2
<
δ
/
2
≥
0
.
Hence,
(14)
-
I
x
1
+
x
2
2
=
inf
⁡
δ
>
0
limsup
⁡
n
→
∞
1
n
ln
⁡
P
S
n
n
-
x
1
+
x
2
2
<
δ
≥
inf
⁡
δ
>
0
liminf
⁡
n
→
∞
1
2
n
ln
⁡
⁡
P
S
2
n
2
n
-
x
1
+
x
2
2
<
δ
×
P
S
n
n
-
x
2
<
δ
2
-
1
×
P
S
n
n
-
x
1
<
δ
2
×
P
S
n
n
-
x
2
<
δ
2
-
1
+
inf
⁡
δ
>
0
liminf
⁡
n
→
∞
1
2
n
ln
⁡
P
S
n
n
-
x
1
<
δ
2
+
inf
⁡
δ
>
0
liminf
⁡
n
→
∞
1
2
n
ln
⁡
P
S
n
n
-
x
2
<
δ
2
≥
-
1
2
I
(
x
1
)
-
1
2
I
(
x
2
)
,
which means that I is midconvex (called by some authorsJensen-convex orJ-convex). The function I is measurable; thus according to Sierpiński Theorem (see [10], Theorem 9.4.2. and Theorem 5.3.5), it is convex and the proof is completed.Finally, let us present an example of a sequence satisfying the assumptions of our theorem; for this sequence obviously the results of [5] do not apply.Example 2.
LetY
n
n
≥
1 be a Gaussian sequence with the squared exponential covariance function; that is,
(15)
Cov
Y
i
,
Y
j
=
exp
⁡
-
i
-
j
2
.
This sequence is stationary and associated (positively correlated Gaussian). Define a sequence X
n
n
≥
1 as follows:
(16)
X
n
=
I
(
Y
n
≤
x
)
,
where x
∈
R is an arbitrary number. The r.v.’s X
n
n
≥
1 inherit the properties of association and stationarity from the sequence Y
n
n
≥
1 (we applied the same nonincreasing indicator function to the r.v.’s X
n which are associated). Furthermore, for n
≥
1, from the covariance inequality for Gaussian r.v.’s (see [11]) we have
(17)
0
<
Cov
X
1
,
X
n
+
1
=
P
Y
1
≤
x
,
Y
n
+
1
≤
x
-
P
Y
1
≤
x
P
Y
n
+
1
≤
x
≤
4
f
Y
1
∞
2
Cov
Y
1
,
Y
n
+
1
=
4
f
Y
1
∞
2
exp
⁡
-
n
2
.
Therefore
(18)
u
(
n
)
=
∑
j
=
n
+
1
∞
‍
Cov
X
1
,
X
j
≤
const
·
exp
⁡
(
-
n
2
)
and the binary sequence X
n
n
≥
1 is stationary and fulfills assumptions (A1), (A2), and (A3).


## 3. Auxiliary Results

Lemma 3.
Let{
X
n
}
n
≥
1 be the sequence as in Theorem 1. Then limit (6) exists and is finite for all t
∈
R.Proof.
The proof is nearly rewritten from Theorem 3.16 in [6]. For n
,
m
∈
N, t
∈
R, by assumption (A1), we have Cov
e
t
S
n
,
e
t
(
S
n
+
m
-
S
n
)
≥
0. Since the sequence of r.v.’s X
i, i
∈
N, is stationary, we obtain ln
⁡
E
e
t
S
n
+
m
≥
ln
⁡
E
e
t
S
n
+
ln
⁡
E
e
t
S
m. Denoting h
(
n
)
=
-
ln
⁡
E
e
t
S
n, by Lemma A.5 we get the existence of (6). It remains to verify its finiteness for all t
∈
R. By assumption (A2), we have
(19)
e
-
t
n
M
≤
E
e
t
S
n
≤
e
t
n
M
for
t
>
0
,
e
t
n
M
≤
E
e
t
S
n
≤
e
-
t
n
M
for
t
<
0
.
Thus, for arbitrarily chosen t
∈
R, lim
⁡
n
→
∞
(
1
/
n
)
ln
⁡
E
e
t
S
n is finite.Lemma 4.
Let{
X
n
}
n
≥
1 be the sequence as in Theorem 1. Then, for every real continuous, concave, and bounded from above function G
:
R
→
R, the limit Λ
(
G
)
=
lim
⁡
n
→
∞
(
1
/
n
)
ln
⁡
E
e
n
G
S
n
/
n exists.Proof.
Except for the steps where discreteness of r.v.’s in question is involved, the proof goes along exactly like in Theorem 3.18 in [6].
Without loss of generality, we may and do assume that-
∞
<
-
B
≤
G
(
x
)
≤
0 for x
∈
[
-
M
,
M
] and for some B
>
0. Since G is continuous and concave, it is a Lipschitz function with constant L, for example. By assumption (A2), we get that for n
,
m
,
l
∈
N
(20)
1
n
+
m
S
n
+
m
-
S
n
+
S
n
+
m
+
l
-
S
n
+
l
≤
2
l
M
n
+
m
,
almost
surely
.
Thus, since G is Lipschitz,
(21)
G
1
n
+
m
S
n
+
m
-
G
1
n
+
m
S
n
+
S
n
+
m
+
l
-
S
n
+
l
≥
-
2
l
L
M
n
+
m
.
By assumed concavity of G, this implies that
(22)
G
1
n
+
m
S
n
+
m
≥
n
n
+
m
G
S
n
n
+
m
n
+
m
G
S
n
+
m
+
l
-
S
n
+
l
m
-
2
l
L
M
n
+
m
,
which is equivalent to
(23)
ln
⁡
E
e
n
+
m
G
(
S
n
+
m
/
(
n
+
m
)
)
≥
ln
⁡
E
e
n
G
S
n
/
n
e
m
G
(
(
S
n
+
m
+
l
-
S
n
+
l
)
/
m
)
-
2
l
L
M
.
When we denote h
(
n
)
∶
=
-
ln
⁡
E
e
n
G
(
S
n
/
n
), the above inequality takes the following form:
(24)
h
(
n
+
m
)
≤
2
l
L
M
-
ln
⁡
E
e
n
G
(
S
n
/
n
)
e
m
G
(
(
S
n
+
m
+
l
-
S
n
+
l
)
/
m
)
.
We will now aim at finding the bound for the second term at the r.h.s. of inequality (24).
Let us now define, forx
∈
[
-
M
,
M
] and n
∈
N, the sequence of continuous functions F
n
:
R
→
R in the following way:
(25)
F
n
x
=
e
n
G
(
x
)
,
for
x
=
k
n
,
where
k
∈
Z
linear
,
otherwise
.
Each F
n is thus a polyline with vertices having first coordinate of the form k
/
n, k
∈
Z
, and second coordinate in the interval (
0,1
]. Now, since G is nonpositive and Lipschitz with constant L, we have
(26)
e
n
G
(
x
)
-
e
n
G
(
y
)
≤
n
L
x
-
y
for
x
,
y
∈
[
-
M
,
M
]
,
so F
n is absolutely continuous (since it is Lipschitz continuous) and almost everywhere differentiable with |
F
n
′
(
x
)
|
≤
L
n.
We will now make use of the Newman identity (see [12]) which allows us to express the covariance of two absolutely continuous functions of arbitrary r.v.’s via the covariance of the indicators of these r.v.’s. Let us recall that if g
1 and g
2 are absolutely continuous functions and X, Y are random variables, such that g
1
(
X
) and g
2
(
Y
) are square-integrable, then
(27)
Cov
g
1
X
,
g
2
Y
=
∫
-
∞
+
∞
‍
∫
-
∞
+
∞
‍
g
1
′
t
g
2
′
s
Cov
I
X
≤
t
,
I
Y
≤
s
d
t
d
s
.
In light of the above identity, we can write
(28)
Cov
e
n
G
(
S
n
/
n
)
,
e
m
G
(
(
S
n
+
m
+
l
-
S
n
+
l
)
/
m
)
=
∫
-
M
M
‍
∫
-
M
M
‍
e
n
G
x
n
G
′
m
G
y
m
G
′
y
×
Cov
I
S
n
n
≤
x
,
I
S
n
+
m
+
l
-
S
n
+
l
m
≤
y
d
x
d
y
≤
L
2
Cov
(
S
n
,
S
n
+
m
+
l
-
S
n
+
l
)
,
where the last inequality is a consequence of nonpositivity of G and application of the well-known Hoeffding identity stating that
(29)
Cov
X
,
Y
=
∫
‍
∫
R
2
‍
P
(
X
≤
x
,
Y
≤
y
)
-
P
X
≤
x
P
Y
≤
y
d
x
d
y
.
By the assumption of stationarity of {
X
n
}
n
∈
N, we can bound the above expression in the following way:
(30)
L
2
Cov
S
n
,
S
n
+
m
+
l
-
S
n
+
l
≤
L
2
n
+
m
∑
i
=
l
l
+
m
‍
Cov
X
1
,
X
1
+
i
=
L
2
(
n
+
m
)
u
(
l
)
.
Hence, we get
(31)
E
e
n
G
(
S
n
/
n
)
e
m
G
(
(
S
n
+
m
+
l
-
S
n
+
l
)
/
m
)
≥
E
e
n
G
(
S
n
/
n
)
E
e
m
G
(
(
S
n
+
m
+
l
-
S
n
+
l
)
/
m
)
-
L
2
(
n
+
m
)
u
(
l
)
,
which, on the basis of uniform boundedness of X
i, i
∈
N, yields
(32)
E
e
n
G
(
S
n
/
n
)
e
m
G
(
(
S
n
+
m
+
l
-
S
n
+
l
)
/
m
)
E
e
n
G
(
S
n
/
n
)
E
e
m
G
(
(
S
n
+
m
+
l
-
S
n
+
l
)
/
m
)
≥
1
-
L
2
(
n
+
m
)
u
(
l
)
e
(
n
+
m
)
B
.
Let us now define the following quantity: θ
(
l
,
n
)
∶
=
1
-
L
2
n
u
(
l
)
e
n
B, and restate (32):
(33)
ln
⁡
E
e
n
G
(
S
n
/
n
)
e
m
G
(
(
S
n
+
m
+
l
-
S
n
+
l
)
/
m
)
≥
-
h
(
n
)
-
h
(
m
)
+
ln
⁡
max
⁡
0
,
θ
l
,
n
+
m
.
Going back to inequality (24), we obtain
(34)
h
n
+
m
≤
2
l
L
M
+
h
n
+
h
m
-
ln
⁡
max
⁡
0
,
θ
l
,
n
+
m
.
Choose δ
∈
(
0
,
b
), where b is the constant taken from assumption (A3). By Lemma A.6,
(35)
θ
n
ln
⁡
1
+
δ
n
,
n
⟶
1
,
n
⟶
∞
.
Therefore it is easy to show that putting l
=
(
n
+
m
)
/
ln
⁡
1
+
δ
(
n
+
m
), for sufficiently large n
+
m, we have
(36)
ln
⁡
max
⁡
0
,
θ
l
,
n
+
m
≥
-
l
.
As a result, from inequality (34), we arrive at
(37)
h
n
+
m
≤
2
l
L
M
+
h
n
+
h
m
+
l
=
h
(
n
)
+
h
(
m
)
+
(
2
l
L
M
+
1
)
n
+
m
ln
⁡
1
+
δ
(
n
+
m
)
,
and by Lemma A.5 we conclude that the limit lim
⁡
n
→
∞
(
h
n
/
n
) exists and the proof is completed.Lemma 5.
LetX and Y be integer-valued, associated, square-integrable r.v.’s; then
(38)
P
(
a
1
≤
X
≤
a
2
,
b
1
≤
Y
≤
b
2
)
-
P
(
a
1
≤
X
≤
a
2
)
P
(
b
1
≤
Y
≤
b
2
)
≤
4
Cov
(
X
,
Y
)
,
for any a
1
<
a
2 and b
1
<
b
2.Proof.
The proof follows from the covariance inequality(39)
sup
⁡
x
,
y
∈
R
P
X
≤
x
,
Y
≤
y
-
P
X
≤
x
P
Y
≤
y
≤
Cov
(
X
,
Y
)
obtained in [13] for integer-valued associated r.v.’s X, Y.Lemma 6.
Let{
X
n
}
n
≥
1 be the sequence as in Theorem 1. Let also x
1
,
x
2
∈
R be such that, for all δ
>
0,
(40)
liminf
⁡
n
→
∞
1
n
ln
⁡
P
S
n
n
-
x
i
<
δ
>
-
∞
f
o
r
i
∈
{
1,2
}
.
Then,
(41)
inf
⁡
δ
>
0
liminf
⁡
n
→
∞
1
n
ln
⁡
P
S
2
n
/
2
n
-
x
1
+
x
2
/
2
<
δ
P
S
n
/
n
-
x
1
<
δ
/
2
P
S
n
/
n
-
x
2
<
δ
/
2
≥
0
.Proof.
Again, apart from the calculations we conduct with remark that the r.v.’s are integer-valued, the proof goes like in Theorem 3.19 in [6].
From assumption (40) we know that there exist c
i
>
0, i
∈
{
1,2
}, such that, for sufficiently large n, (
1
/
n
)
ln
⁡
P
S
n
/
n
-
x
i
<
δ
>
-
c
i; thus, for some c
>
0,
(42)
P
S
n
n
-
x
1
<
δ
P
S
n
n
-
x
2
<
δ
≥
e
-
n
c
.
Now, for n
,
l
∈
N, by Lemma 5 and by stationarity of r.v’s, we can write
(43)
P
S
n
n
-
x
1
<
δ
2
,
S
2
n
+
l
-
S
n
+
l
n
-
x
2
<
δ
2
-
P
S
n
n
-
x
1
<
δ
2
P
S
n
n
-
x
2
<
δ
2
≤
4
Cov
(
S
n
,
S
2
n
+
l
-
S
n
+
l
)
≤
4
n
u
(
l
)
.
Hence and in light of inequality (42), we get
(44)
P
S
n
/
n
-
x
1
<
δ
/
2
,
S
2
n
+
l
-
S
n
+
l
/
n
-
x
2
<
δ
/
2
P
S
n
/
n
-
x
1
<
δ
/
2
P
S
n
/
n
-
x
2
<
δ
/
2
≥
1
-
4
n
u
(
l
)
e
n
c
.
Next, on the basis of (A2) we see that
(45)
S
2
n
2
n
-
x
1
+
x
2
2
≤
1
2
S
n
n
-
x
1
+
S
2
n
+
l
-
S
n
+
l
n
-
x
2
+
l
M
n
,
which yields that
(46)
P
S
2
n
2
n
-
x
1
+
x
2
2
<
δ
≥
P
1
2
S
n
n
-
x
1
+
S
2
n
+
l
-
S
n
+
l
n
-
x
2
<
δ
-
l
M
n
.
By triangle inequality, this implies
(47)
P
S
2
n
2
n
-
x
1
+
x
2
2
<
δ
≥
P
S
n
n
-
x
1
<
δ
-
l
M
n
,
S
2
n
+
l
-
S
n
+
l
n
-
x
2
<
δ
-
l
M
n
.
Putting l
=
δ
n
/
2
M in the above inequality and plugging it in inequality (44), we arrive at
(48)
P
S
2
n
/
2
n
-
x
1
+
x
2
/
2
<
δ
P
S
n
/
n
-
x
1
<
δ
/
2
P
S
n
/
n
-
x
2
<
δ
/
2
≥
1
-
4
n
u
δ
n
2
M
e
n
c
.
If we finally put δ
=
2
M
/
ln
⁡
1
+
k
n, where 0
<
k
<
b, then by Lemma A.6 we get the thesis.



---

*Source: 430837-2015-01-06.xml*