Let X∼ Normal (0,σ2)X∼ Normal (0,σ2) be a Gaussian random variable. There is no closed-form expression tail probability
P
|
X
|
>
u
=
2
π
σ
∫
u
∞
e
-
t
2
/
2
σ
2
d
t
,
P
|
X
|
>
u
=
2
π
σ
∫
u
∞
e
-
t
2
/
2
σ
2
d
t
,
(1)but it can be bounded very accurately, especially for moderately large uu. There are two standard bounds, one of which is good for small uu, the other for medium-sized uu and larger:
P
|
X
|
>
u
≤
min
2
π
σ
u
e
-
u
2
/
2
σ
2
,
e
-
u
2
/
2
σ
2
.
P
|
X
|
>
u
≤
min
2
π
σ
u
e
-
u
2
/
2
σ
2
,
e
-
u
2
/
2
σ
2
.
(2)
These bounds are illustrated in Figure 1.
Now let X1,...,XnX1,...,Xn be a sequence of (not necessarily independent) Gaussian random variables with Xi∼ Normal (0,σ2)Xi∼ Normal (0,σ2). Define the random variable ZZ to be
Z
=
max
0
≤
i
≤
n
|
X
i
|
.
Z
=
max
0
≤
i
≤
n
|
X
i
|
.
(3)We will be concerned with estimating the size of ZZ. We will ultimately compute the expectation E[Z]E[Z], but will do so by first calculating a simple tail bound.
Since ZZ is positive, we can get at E[Z]E[Z] through its tail bound in the following manner. Using fZ(z)fZ(z) to denote the probability density function of ZZ, we have
E
[
Z
]
=
∫
z
=
0
∞
z
f
Z
(
z
)
d
z
=
∫
z
=
0
∞
∫
u
=
0
∞
1
u
≤
z
d
u
f
Z
(
z
)
d
z
=
∫
u
=
0
∞
∫
z
=
0
∞
1
u
≤
z
f
Z
(
z
)
d
z
d
u
=
∫
u
=
0
∞
P
Z
>
u
d
u
.
E
[
Z
]
=
∫
z
=
0
∞
z
f
Z
(
z
)
d
z
=
∫
z
=
0
∞
∫
u
=
0
∞
1
u
≤
z
d
u
f
Z
(
z
)
d
z
=
∫
u
=
0
∞
∫
z
=
0
∞
1
u
≤
z
f
Z
(
z
)
d
z
d
u
=
∫
u
=
0
∞
P
Z
>
u
d
u
.
(4)
Since the probability of at least one of the |Xi||Xi| being above some fixed uu is less than the sum of the probabilities of each of the |Xi||Xi| being above uu (this is the union bound, or Boole's inequality), we have
P
Z
>
u
≤
n
·
P
|
X
i
|
>
u
≤
n
·
e
-
u
2
/
2
σ
2
.
P
Z
>
u
≤
n
·
P
|
X
i
|
>
u
≤
n
·
e
-
u
2
/
2
σ
2
.
(5)
Of course, we always have PZ>u≤1PZ>u≤1, which is a better bound than the above when u≤σ2lognu≤σ2logn. Thus
∫
P
Z
>
u
d
u
≤
σ
2
log
n
+
n
∫
σ
2
log
n
∞
e
-
u
2
/
2
σ
2
d
u
≤
σ
2
log
n
+
σ
2
log
n
,
∫
P
Z
>
u
d
u
≤
σ
2
log
n
+
n
∫
σ
2
log
n
∞
e
-
u
2
/
2
σ
2
d
u
≤
σ
2
log
n
+
σ
2
log
n
,
(6)
where we have again used Equation 2 on the second term. So we see that
E
max
1
≤
i
≤
n
|
X
i
|
≤
σ
2
log
n
+
o
(
1
)
≤
σ
2
log
n
+
1
,
E
max
1
≤
i
≤
n
|
X
i
|
≤
σ
2
log
n
+
o
(
1
)
≤
σ
2
log
n
+
1
,
(7)and that this upper bound →σ2logn→σ2logn as nn gets large.
When the XiXi are independent, then Equation 7 is a very good bound. We can see this by considering a lower bound for the tail of a single Gaussian random variable XX:
P
|
X
|
>
u
≥
1
-
1
u
2
2
u
π
σ
e
-
u
2
/
2
σ
2
.
P
|
X
|
>
u
≥
1
-
1
u
2
2
u
π
σ
e
-
u
2
/
2
σ
2
.
(8)Now set a threshold λλ just below σ2lognσ2logn, say
λ
=
1
-
δ
σ
2
log
n
for
some
δ
<
1
.
λ
=
1
-
δ
σ
2
log
n
for
some
δ
<
1
.
(9)We now consider a sequence of independent XiXi, and show that we expect many of them to be larger than λλ. Since the XiXi are independent, we can correspond the events that the |Xi||Xi| exceed λλ with a sequence of independent Bernoulli random variable which take a value of 1 with probability p=P{|Xi|>λ}p=P{|Xi|>λ} and a value of zero with probability 1-p1-p. Then in a sequence of length nn the expected number of locations where |Xi||Xi| exceeds λλ is simply npnp:
E
#
{
i
:
|
X
i
|
>
λ
}
=
n
P
|
X
i
|
>
λ
≥
n
1
-
1
2
(
1
-
δ
)
σ
2
log
n
2
σ
2
2
π
(
1
-
δ
)
log
n
e
-
(
1
-
δ
)
log
n
=
1
-
1
2
(
1
-
δ
)
σ
2
log
n
2
σ
2
2
π
(
1
-
δ
)
log
n
n
-
δ
=
O
n
-
δ
log
n
→
∞
as
n
gets
large
.
E
#
{
i
:
|
X
i
|
>
λ
}
=
n
P
|
X
i
|
>
λ
≥
n
1
-
1
2
(
1
-
δ
)
σ
2
log
n
2
σ
2
2
π
(
1
-
δ
)
log
n
e
-
(
1
-
δ
)
log
n
=
1
-
1
2
(
1
-
δ
)
σ
2
log
n
2
σ
2
2
π
(
1
-
δ
)
log
n
n
-
δ
=
O
n
-
δ
log
n
→
∞
as
n
gets
large
.
(10)
So for any λλ smaller than σ2lognσ2logn, the number of XiXi which exceed λλ grows without bound as nn gets large, suggesting that Equation 7 is tight.
When the XiXi are not independent, Equation 7 can be far too pessimistic. Fortunately, there are other tools from probability theory (namely the Dudley inequality) that can take derive a tighter bound on the maximum by taking systematic advantage of the correlation structure.
