Eaton's inequality: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 10:33, 19 September 2021

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.^[1]

Statement of the inequality

Let {X_i} be a set of real independent random variables, each with an expected value of zero and bounded above 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

\sum _{i=1}^{n}a_{i}^{2}=1.

Eaton showed that

P\left(\left|\sum _{i=1}^{n}a_{i}X_{i}\right|\geq k\right)\leq 2\inf _{0\leq c\leq k}\int _{c}^{\infty }\left({\frac {z-c}{k-c}}\right)^{3}\phi (z)\,dz=2B_{E}(k),

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

A related bound is Edelman's^{[citation needed]}

P\left(\left|\sum _{i=1}^{n}a_{i}X_{i}\right|\geq k\right)\leq 2\left(1-\Phi \left[k-{\frac {1.5}{k}}\right]\right)=2B_{Ed}(k),

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

Pinelis has shown that Eaton's bound can be sharpened:^[2]

B_{EP}=\min\{1,k^{-2},2B_{E}\}

A set of critical values for Eaton's bound have been determined.^[3]

Related inequalities

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

\sum _{i=1}^{n}b_{i}^{2}=1.

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

a_{i}b_{i}+\cdots +a_{n}b_{n}

will converge if and only if

\sum _{i=1}^{n}b_{i}^{2}

is finite.

Then

Ef(a_{i}b_{i}+\cdots +a_{n}b_{n})\leq Ef(Z)

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

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

Ef(a_{i}b_{i}+\cdots +a_{n}b_{n})\leq \inf \left[{\frac {E(e^{\lambda Z})}{e^{\lambda x}}}\right]=e^{-x^{2}/2}

where inf is the infimum.^[6]

Let

S_{n}=a_{i}b_{i}+\cdots +a_{n}b_{n}

Then^[7]

P(S_{n}\geq x)\leq {\frac {2e^{3}}{9}}P(Z\geq x)

The constant in the last inequality is approximately 4.4634.

An alternative bound is also known:^[8]

P(S_{n}\geq x)\leq 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^[9]

P(|\mu -\sigma |)\leq 0.5\,

^{[clarification needed]}

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

References

^ Eaton, Morris L. (1974) "A probability inequality for linear combinations of bounded random variables." Annals of Statistics 2(3) 609–614
^ Pinelis, I. (1994) "Extremal probabilistic problems and Hotelling's T² test under a symmetry condition." Annals of Statistics 22(1), 357–368
^ Dufour, J-M; Hallin, M (1993) "Improved Eaton bounds for linear combinations of bounded random variables, with statistical applications", Journal of the American Statistical Association, 88(243) 1026–1033
^ Whittle P (1960) Bounds for the moments of linear and quadratic forms in independent variables. Teor Verojatnost i Primenen 5: 331–335 MR0133849
^ Haagerup U (1982) The best constants in the Khinchine inequality. Studia Math 70: 231–283 MR0654838
^ Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J Amer Statist Assoc 58: 13–30 MR144363
^ Pinelis I (1994) Optimum bounds for the distributions of martingales in Banach spaces. Ann Probab 22(4):1679–1706
^ de la Pena, VH, Lai TL, Shao Q (2009) Self normalized processes. Springer-Verlag, New York
^ van Zuijlen Martien CA (2011) On a conjecture concerning the sum of independent Rademacher random variables. https://arxiv.org/abs/1112.4988

[Eaton1974-1] Eaton, Morris L. (1974) "A probability inequality for linear combinations of bounded random variables." Annals of Statistics 2(3) 609–614

[Pinelis1994-2] Pinelis, I. (1994) "Extremal probabilistic problems and Hotelling's T² test under a symmetry condition." Annals of Statistics 22(1), 357–368

[Dufour1993-3] Dufour, J-M; Hallin, M (1993) "Improved Eaton bounds for linear combinations of bounded random variables, with statistical applications", Journal of the American Statistical Association, 88(243) 1026–1033

[Whittle1960-4] Whittle P (1960) Bounds for the moments of linear and quadratic forms in independent variables. Teor Verojatnost i Primenen 5: 331–335 MR0133849

[Haagerup1982-5] Haagerup U (1982) The best constants in the Khinchine inequality. Studia Math 70: 231–283 MR0654838

[Hoeffding1963-6] Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J Amer Statist Assoc 58: 13–30 MR144363

[Pinelis1994a-7] Pinelis I (1994) Optimum bounds for the distributions of martingales in Banach spaces. Ann Probab 22(4):1679–1706

[delaPena2009-8] Pena, VH, Lai TL, Shao Q (2009) Self normalized processes. Springer-Verlag, New York

[vanZuijlen2011-9] van Zuijlen Martien CA (2011) On a conjecture concerning the sum of independent Rademacher random variables. https://arxiv.org/abs/1112.4988

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Line 1: / Line 1: @@
-Eaton's inequality is a bound on the maximal values of a linear combination of bounded random variables.
+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.<ref name=Eaton1974>Eaton, Morris L. (1974) "A probability inequality for linear combinations of bounded random variables." ''Annals of Statistics'' 2(3) 609–614</ref>
-==History==
-This inequality was described in 1974 by Eaton.<ref name=Eaton1974>Eaton ML (1974) A probability inequality for linear combinations of bounded random variables. Ann Statist 2(3) 609-614 </ref>
 ==Statement of the inequality==
-Let ''X''<sub>i</sub> be a set of real independent random variables each with a [[mean]] of [[zero]] and bounded by 1 ( | ''X''<sub>i</sub> | ≤ 1). Let 1 ≤ ''i'' ≤ ''n''. The variates do not have to be identically or symmetrically distributed. Let ''a''<sub>i</sub> be a set of ''n'' fixed real numbers with
+Let {''X''<sub>i</sub>} be a set of real independent random variables, each with an [[expected value]] of zero and bounded above by 1 ( |''X''<sub>''i''</sub> | ≤ 1, for 1 ≤ ''i'' ≤ ''n''). The variates do not have to be identically or symmetrically distributed. Let {''a''<sub>''i''</sub>} be a set of ''n'' fixed real numbers with
-<math> \sum_{ i = 1 }^n a_i^2 = 1 </math>
+: <math> \sum_{ i = 1 }^n a_i^2 = 1 .</math>
 Eaton showed that
-<math> P( | \sum_{ i = 1 }^n a_i X_i | \ge k ) \le 2 \inf_{ 0 \le c \le k } \int_c^\infty ( \frac{ z - c }{ k - c } )^3 \phi( z ) dz = 2 B_E( k )</math>
+: <math> P\left( \left| \sum_{ i = 1 }^n a_i X_i \right| \ge k \right) \le 2 \inf_{ 0 \le c \le k } \int_c^\infty \left( \frac{ z - c }{ k - c } \right)^3 \phi( z ) \, dz = 2 B_E( k ) ,</math>
-where ''φ''( x ) is the normal probability density.
+where ''φ''(''x'') is the [[probability density function]] of the [[standard normal distribution]].
-A related bound is Edelman's
+A related bound is Edelman's{{cn|date=April 2013}}
-<math> P( | \sum_{ i = 1 }^n a_i X_i | \ge k ) \le 2 ( 1 - \Phi[ k - \frac{ 1.5 }{ k } ] ) </math>
+: <math> P\left( \left| \sum_{ i = 1 }^n a_i X_i \right| \ge k \right) \le 2 \left( 1 - \Phi\left[ k - \frac{ 1.5 }{ k } \right] \right) = 2 B_{ Ed }( k ) , </math>
-where ''Φ''( x ) is the normal probability distribution.
+where Φ(''x'') is [[cumulative distribution function]] of the standard normal distribution.
+Pinelis has shown that Eaton's bound can be sharpened:<ref name=Pinelis1994>Pinelis, I. (1994) "Extremal probabilistic problems and Hotelling's ''T''<sup>2</sup> test under a symmetry condition." ''Annals of Statistics'' 22(1), 357–368</ref>
+: <math> B_{ EP } = \min\{ 1, k^{ -2 }, 2 B_E \} </math>
+A set of critical values for Eaton's bound have been determined.<ref name=Dufour1993>Dufour, J-M; Hallin, M (1993) "Improved Eaton bounds for linear combinations of bounded random variables, with statistical applications", ''Journal of the American Statistical Association'', 88(243) 1026–1033</ref>
+==Related inequalities==
+Let {''a''<sub>i</sub>} be a set of independent [[Rademacher distribution|Rademacher random variables]] – ''P''( ''a''<sub>''i''</sub> = 1 ) = ''P''( ''a''<sub>''i''</sub> = −1 ) = 1/2. Let ''Z'' be a normally distributed variate with a [[mean]] 0 and [[variance]] of 1. Let {''b''<sub>''i''</sub>} be a set of ''n'' fixed real numbers such that
+: <math> \sum_{ i = 1 }^n b_i^2 = 1 .</math>
+This last condition is required by the [[Riesz–Fischer theorem]] which states that
+:<math> a_i b_i + \cdots + a_n b_n </math>
+will converge if and only if
+: <math> \sum_{ i = 1 }^n b_i^2 </math>
+is finite.
+Then
+: <math> E f( a_i b_i + \cdots + a_n b_n ) \le E f( Z ) </math>
+for ''f''(x) = | x |<sup>p</sup>. The case for ''p'' ≥ 3 was proved by Whittle<ref name=Whittle1960>Whittle P (1960) Bounds for the moments of linear and quadratic forms in independent variables. Teor Verojatnost i Primenen 5: 331–335 MR0133849</ref> and ''p'' ≥ 2 was proved by Haagerup.<ref name=Haagerup1982>Haagerup U (1982) The best constants in the Khinchine inequality. Studia Math 70: 231–283 MR0654838</ref>
+If ''f''(x) = ''e''<sup>λx</sup> with ''λ'' ≥ 0 then
+:<math> E f( a_i b_i + \cdots + a_n b_n ) \le \inf \left[ \frac{ E ( e^{ \lambda Z  } ) }{ e^{ \lambda x } } \right] = e^{ -x^2 / 2 } </math>
+where ''inf'' is the [[infimum]].<ref name=Hoeffding1963>Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J Amer Statist Assoc 58: 13–30 MR144363</ref>
+Let
+:<math> S_n =  a_i b_i + \cdots + a_n b_n </math>
+Then<ref name=Pinelis1994a>Pinelis I (1994) Optimum bounds for the distributions of martingales in Banach spaces. Ann Probab 22(4):1679–1706</ref>
+:<math> P( S_n \ge x ) \le \frac{ 2e^3 }{ 9 } P( Z \ge x ) </math>
+The constant in the last inequality is approximately 4.4634.
+An alternative bound is also known:<ref name=delaPena2009>de la Pena, VH, Lai TL, Shao Q (2009) Self normalized processes. Springer-Verlag, New York</ref>
+:<math> P( S_n \ge x ) \le e^{ -x^2 / 2 } </math>
+This last bound is related to the [[Hoeffding's inequality]].
+In the uniform case where all the ''b''<sub>''i''</sub> = ''n''<sup>−1/2</sup> the maximum value of ''S''<sub>''n''</sub> is ''n''<sup>1/2</sup>. In this case van Zuijlen has shown that<ref name=vanZuijlen2011>van Zuijlen  Martien CA (2011) On a conjecture concerning the sum of independent Rademacher random variables. https://arxiv.org/abs/1112.4988</ref>
+: <math> P( | \mu - \sigma | ) \le 0.5 \, </math>{{clarification needed|date=April 2013}}
+where ''μ'' is the [[mean]] and ''σ'' is the [[standard deviation]] of the sum.
 ==References==
 {{reflist}}
+[[Category:Probabilistic inequalities]]
+[[Category:Statistical inequalities]]