Eaton's inequality - Alchetron, The Free Social Encyclopedia

In probability theory, Eaton's inequality is a bound on the largest values of a linear combination of bounded random variables. This inequality was described in 1974 by Morris L. Eaton.

Statement of the inequality

Let X_i be a set of real independent random variables, each with a expected value of zero and bounded by 1 ( | X_i | ≤ 1, for 1 ≤ i ≤ n). The variates do not have to be identically or symmetrically distributed. Let a_i be a set of n fixed real numbers with

∑ i = 1 n a i 2 = 1.

Eaton showed that

P ( | ∑ i = 1 n a i X i | ≥ k ) ≤ 2 inf 0 ≤ c ≤ k ∫ c ∞ ( z − c k − c ) 3 ϕ ( z ) d z = 2 B E ( k ) ,

where φ(x) is the probability density function of the standard normal distribution.

A related bound is Edelman's

P ( | ∑ i = 1 n a i X i | ≥ k ) ≤ 2 ( 1 − Φ [ k − 1.5 k ] ) = 2 B E d ( k ) ,

where Φ(x) is cumulative distribution function of the standard normal distribution.

Pinelis has shown that Eaton's bound can be sharpened:

B E P = min { 1 , k − 2 , 2 B E }

A set of critical values for Eaton's bound have been determined.

Let a_i be a set of independent Rademacher random variables – P( a_i = 1 ) = P( a_i = −1 ) = 1/2. Let Z be a normally distributed variate with a mean 0 and variance of 1. Let b_i be a set of n fixed real numbers such that

∑ i = 1 n b i 2 = 1.

This last condition is required by the Riesz–Fischer theorem which states that

a i b i + ⋯ + a n b n

will converge if and only if

∑ i = 1 n b i 2

is finite.

Then

E f ( a i b i + ⋯ + a n b n ) ≤ E f ( Z )

for f(x) = | x |^p. The case for p ≥ 3 was proved by Whittle and p ≥ 2 was proved by Haagerup.

If f(x) = e^λx with λ ≥ 0 then

E f ( a i b i + ⋯ + a n b n ) ≤ inf [ E ( e λ Z ) e λ x ] = e − x 2 / 2

where inf is the infimum.

Let

S n = a i b i + ⋯ + a n b n

Then

P ( S n ≥ x ) ≤ 2 e 3 9 P ( Z ≥ x )

The constant in the last inequality is approximately 4.4634.

An alternative bound is also known:

P ( S n ≥ x ) ≤ e − x 2 / 2

This last bound is related to the Hoeffding's inequality.

In the uniform case where all the b_i = n^−1/2 the maximum value of S_n is n^1/2. In this case van Zuijlen has shown that

P ( | μ − σ | ) ≤ 0.5

where μ is the mean and σ is the standard deviation of the sum.

References

Eaton's inequality Wikipedia

(Text) CC BY-SA

Contents

Statement of the inequality

Related inequalities

References