Let X∼ Normal (0,σ2)X∼ Normal (0,σ2) be a Gaussian random variable. There is no closedform 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 mediumsized 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 XiXi being above some fixed uu is less than the sum of the probabilities of each of the XiXi 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 XiXi 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 1p1p. Then in a sequence of length nn the expected number of locations where XiXi 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.