Skip to content Skip to navigation

OpenStax-CNX

You are here: Home » Content » Maximum of a Sequence of Gaussian Random Variables

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Maximum of a Sequence of Gaussian Random Variables

Module by: Justin Romberg. E-mail the author

Summary: We derive an upper bound on the expected maximum of a sequence of Gaussian random variables, and argue that it is tight when they are independent.

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.

Figure 1: Two tail bounds for P|X|>uP|X|>u, which is shown in blue. Red: e-u2/2σ2e-u2/2σ2. Green: 2σ/(πu)e-u2/2σ22σ/(πu)e-u2/2σ2.
Figure 1 (gauss_tail_bounds.png)

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>u1PZ>u1, 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.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks