An asymptotically Gaussian bound on the Rademacher tails

Iosif Pinelis (Michigan Technological University)

Abstract


An explicit upper bound on the tail probabilities for the normalized Rademacher sums is given. This bound, which is best possible in a certain sense, is asymptotically equivalent to the corresponding tail probability of the standard normal distribution, thus affirming a longstanding conjecture by Efron. Applications to sums of general centered uniformly bounded independent random variables and to the Student test are presented.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-22

Publication Date: May 15, 2012

DOI: 10.1214/EJP.v17-2026

References

  • Antonov, Sergei N.; Kruglov, Victor M. Sharpened versions of a Kolmogorov's inequality. Statist. Probab. Lett. 80 (2010), no. 3-4, 155--160. MR2575440
  • Ben-Tal, A.; Nemirovski, A.; Roos, C. Robust solutions of uncertain quadratic and conic quadratic problems. SIAM J. Optim. 13 (2002), no. 2, 535--560 (electronic). MR1951034
  • Ben-Tal, Aharon; Nemirovski, Arkadi. On safe tractable approximations of chance-constrained linear matrix inequalities. Math. Oper. Res. 34 (2009), no. 1, 1--25. MR2542986
  • George Bennett, phProbability inequalities for the sum of independent random variables, J. Amer. Statist. Assoc. 57 (1962), no. 297, 33--45.
  • Bentkus, V. An inequality for large deviation probabilities of sums of bounded i.i.d. random variables. Liet. Mat. Rink. 41 (2001), no. 2, 144--153; translation in Lithuanian Math. J. 41 (2001), no. 2, 112--119 MR1851123
  • Bentkus, V. A remark on the inequalities of Bernstein, Prokhorov, Bennett, Hoeffding, and Talagrand. (Russian) Liet. Mat. Rink. 42 (2002), no. 3, 332--342; translation in Lithuanian Math. J. 42 (2002), no. 3, 262--269 MR1947624
  • Bentkus, V. An inequality for tail probabilities of martingales with differences bounded from one side. J. Theoret. Probab. 16 (2003), no. 1, 161--173. MR1956826
  • V. Bentkus and D. Dzindzalieta, phA tight Gaussian bound for weighted sums of Rademacher random variables (preprint).
  • Bentkus, Vidmantas. On Hoeffding's inequalities. Ann. Probab. 32 (2004), no. 2, 1650--1673. MR2060313
  • Bentkus, Vidmantas. On measure concentration for separately Lipschitz functions in product spaces. Israel J. Math. 158 (2007), 1--17. MR2342455
  • Bobkov, Sergey G.; Götze, Friedrich; Houdré, Christian. On Gaussian and Bernoulli covariance representations. Bernoulli 7 (2001), no. 3, 439--451. MR1836739
  • Boucheron, Stéphane; Bousquet, Olivier; Lugosi, Gábor; Massart, Pascal. Moment inequalities for functions of independent random variables. Ann. Probab. 33 (2005), no. 2, 514--560. MR2123200
  • Burkholder, D. L. Independent sequences with the Stein property. Ann. Math. Statist. 39 1968 1282--1288. MR0228045
  • Collins, George E. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Quantifier elimination and cylindrical algebraic decomposition (Linz, 1993), 85--121, Texts Monogr. Symbol. Comput., Springer, Vienna, 1998. MR1634190
  • Dembo, Amir; Zeitouni, Ofer. Large deviations techniques and applications. Second edition. Applications of Mathematics (New York), 38. Springer-Verlag, New York, 1998. xvi+396 pp. ISBN: 0-387-98406-2 MR1619036
  • Derinkuyu, Kürşad; Pınar, Mustafa Ç. On the S-procedure and some variants. Math. Methods Oper. Res. 64 (2006), no. 1, 55--77. MR2264772
  • Derinkuyu, Kürşad; Pınar, Mustafa Ç.; Camcı, Ahmet. An improved probability bound for the approximate S-Lemma. Oper. Res. Lett. 35 (2007), no. 6, 743--746. MR2361043
  • Eaton, M. L.; Efron, Bradley. Hotelling's $T^{2}$ test under symmetry conditions. J. Amer. Statist. Assoc. 65 1970 702--711. MR0269021
  • Eaton, Morris L. A note on symmetric Bernoulli random variables. Ann. Math. Statist. 41 1970 1223--1226. MR0268930
  • bysame, phA probability inequality for linear combinations of bounded random variables, Ann. Statist. 2 (1974), 609--613.
  • D. Edelman, phPrivate communication, 1994.
  • Efron, Bradley. Student's $t$-test under symmetry conditions. J. Amer. Statist. Assoc. 64 1969 1278--1302. MR0251826
  • Giné, Evarist; Götze, Friedrich; Mason, David M. When is the Student $t$-statistic asymptotically standard normal? Ann. Probab. 25 (1997), no. 3, 1514--1531. MR1457629
  • Graversen, S. E.; Peškir, G. Extremal problems in the maximal inequalities of Khintchine. Math. Proc. Cambridge Philos. Soc. 123 (1998), no. 1, 169--177. MR1474873
  • Hall, Richard L.; Kanter, Marek; Perlman, Michael D. Inequalities for the probability content of a rotated square and related convolutions. Ann. Probab. 8 (1980), no. 4, 802--813. MR0577317
  • Hiriart-Urruty, Jean-Baptiste. A new series of conjectures and open questions in optimization and matrix analysis. ESAIM Control Optim. Calc. Var. 15 (2009), no. 2, 454--470. MR2513094
  • Pawel Hitczenko and Stanislaw Kwapie'n, phOn the Rademacher series, Probability in Banach spaces, 9 (Sandjberg, 1993), Progr. Probab., vol. 35, Birkhäuser Boston, Boston, MA, 1994, pp. 31--36. MR1308508 (95k:60046)
  • bysame, phOn the Rademacher series, Probability in Banach spaces, 9 (Sandjberg, 1993), Progr. Probab., vol. 35, Birkhäuser Boston, Boston, MA, 1994, pp. 31--36. MRMR1308508 (95k:60046)
  • Hitczenko, Paweł; Montgomery-Smith, Stephen. Measuring the magnitude of sums of independent random variables. Ann. Probab. 29 (2001), no. 1, 447--466. MR1825159
  • Hoeffding, Wassily. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 1963 13--30. MR0144363
  • Hoffmann-Jørgensen, Jørgen. Sums of independent Banach space valued random variables. Studia Math. 52 (1974), 159--186. MR0356155
  • Holzman, Ron; Kleitman, Daniel J. On the product of sign vectors and unit vectors. Combinatorica 12 (1992), no. 3, 303--316. MR1195893
  • Karlin, Samuel; Studden, William J. Tchebycheff systems: With applications in analysis and statistics. Pure and Applied Mathematics, Vol. XV Interscience Publishers John Wiley & Sons, New York-London-Sydney 1966 xviii+586 pp. MR0204922
  • Klass, Michael J.; Nowicki, Krzysztof. An improvement of Hoffmann-Jørgensen's inequality. Ann. Probab. 28 (2000), no. 2, 851--862. MR1782275
  • Klass, Michael J.; Nowicki, Krzysztof. Uniformly accurate quantile bounds via the truncated moment generating function: the symmetric case. Electron. J. Probab. 12 (2007), no. 47, 1276--1298 (electronic). MR2346512
  • Klass, Michael J.; Nowicki, Krzysztof. Uniformly accurate quantile bounds for sums of arbitrary independent random variables. J. Theoret. Probab. 23 (2010), no. 4, 1068--1091. MR2735737
  • König, H.; Kwapień, S. Best Khintchine type inequalities for sums of independent, rotationally invariant random vectors. Positivity 5 (2001), no. 2, 115--152. MR1825172
  • Kreĭn, M. G.; Nudelʹman, A. A. The Markov moment problem and extremal problems. Ideas and problems of P. L. Čebyšev and A. A. Markov and their further development. Translated from the Russian by D. Louvish. Translations of Mathematical Monographs, Vol. 50. American Mathematical Society, Providence, R.I., 1977. v+417 pp. ISBN: 0-8218-4500-4 MR0458081
  • Lasserre, Jean Bernard. Moments, positive polynomials and their applications. Imperial College Press Optimization Series, 1. Imperial College Press, London, 2010. xxii+361 pp. ISBN: 978-1-84816-445-1; 1-84816-445-9 MR2589247
  • Latała, R.; Oleszkiewicz, K. Between Sobolev and Poincaré. Geometric aspects of functional analysis, 147--168, Lecture Notes in Math., 1745, Springer, Berlin, 2000. MR1796718
  • Latała, Rafał. Estimation of moments of sums of independent real random variables. Ann. Probab. 25 (1997), no. 3, 1502--1513. MR1457628
  • Latała, Rafał. Estimates of moments and tails of Gaussian chaoses. Ann. Probab. 34 (2006), no. 6, 2315--2331. MR2294983
  • Latała, Rafał; Oleszkiewicz, Krzysztof. On the best constant in the Khinchin-Kahane inequality. Studia Math. 109 (1994), no. 1, 101--104. MR1267715
  • Ledoux, Michel. On Talagrand's deviation inequalities for product measures. ESAIM Probab. Statist. 1 (1995/97), 63--87 (electronic). MR1399224
  • Ledoux, Michel. The concentration of measure phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI, 2001. x+181 pp. ISBN: 0-8218-2864-9 MR1849347
  • Łojasiewicz, S. Sur les ensembles semi-analytiques. (French) Actes du Congrès International des Mathématiciens (Nice, 1970), Tome 2, pp. 237--241. Gauthier-Villars, Paris, 1971. MR0425152
  • Marshall, Murray. Positive polynomials and sums of squares. Mathematical Surveys and Monographs, 146. American Mathematical Society, Providence, RI, 2008. xii+187 pp. ISBN: 978-0-8218-4402-1; 0-8218-4402-4 MR2383959
  • Montgomery-Smith, S. J. The distribution of Rademacher sums. Proc. Amer. Math. Soc. 109 (1990), no. 2, 517--522. MR1013975
  • Mossel, Elchanan; O'Donnell, Ryan; Oleszkiewicz, Krzysztof. Noise stability of functions with low influences: invariance and optimality. Ann. of Math. (2) 171 (2010), no. 1, 295--341. MR2630040
  • A. V. Nagaev, phProbabilities of large deviations of sums of independent random variables (Doctor of Science Thesis, Tashkent 1970).
  • Oleszkiewicz, Krzysztof. On the Stein property of Rademacher sequences. Probab. Math. Statist. 16 (1996), no. 1, 127--130. MR1407938
  • bysame, phOn a nonsymmetric version of the Khinchine-Kahane inequality, Stochastic inequalities and applications, Progr. Probab., vol. 56, Birkhäuser, Basel, 2003, pp. 157--168. MR2073432 (2005f:60049)
  • Peshkir, G.; Shiryaev, A. N. Khinchin inequalities and a martingale extension of the sphere of their action. (Russian) Uspekhi Mat. Nauk 50 (1995), no. 5(305), 3--62; translation in Russian Math. Surveys 50 (1995), no. 5, 849--904 MR1365047
  • Petrov, V. V. Sums of independent random variables. Translated from the Russian by A. A. Brown. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 82. Springer-Verlag, New York-Heidelberg, 1975. x+346 pp. MR0388499
  • I. Pinelis, phAn asymptotically Gaussian bound on the Rademacher tails, preprint, version~1, rlhttp://arxiv.org/pdf/1007.2137v1.pdf.
  • bysame, phAn asymptotically Gaussian bound on the Rademacher tails, preprint, version~3, rlhttp://arxiv.org/pdf/1007.2137v3.pdf.
  • bysame, phOn the Bennett-Hoeffding inequality (preprint), arXiv:0902.4058v1 [math.PR].
  • bysame, phOn the extreme points of moments sets, preprint, rlhttp://arxiv.org/find/all/1/au:+pinelis/0/1/0/all/0/1.
  • bysame, phOn the supremum of the tails of normalized sums of independent Rademacher random variables, preprint, rlhttp://arxiv.org/find/all/1/au:+pinelis/0/1/0/all/0/1.
  • bysame, phTchebycheff systems and extremal problems for generalized moments: a brief survey, preprint, rlhttp://arxiv.org/find/all/1/au:+pinelis/0/1/0/all/0/1.
  • bysame, phExponential deficiency of convolutions of densities, published online, DOI 10.1051/ps/2010010, ESAIM: Probability and Statistics (2011).
  • I. Pinelis and R. Molzon, phBerry-Esséen bounds for general nonlinear statistics, with applications to Pearson's and non-central Student's and Hotelling's (preprint), arXiv:0906.0177v1 [math.ST].
  • Pinelis, I. F. A problem of large deviations in a space of trajectories. (Russian) Teor. Veroyatnost. i Primenen. 26 (1981), no. 1, 73--87. MR0605637
  • Pinelis, I. F. Asymptotic equivalence of the probabilities of large deviations for sums and maximum of independent random variables. (Russian) Limit theorems of probability theory, 144--173, 176, Trudy Inst. Mat., 5, "Nauka'' Sibirsk. Otdel., Novosibirsk, 1985. MR0821760
  • Pinelis, Iosif. Extremal probabilistic problems and Hotelling's $T^ 2$ test under a symmetry condition. Ann. Statist. 22 (1994), no. 1, 357--368. MR1272088
  • Pinelis, Iosif. Optimal tail comparison based on comparison of moments. High dimensional probability (Oberwolfach, 1996), 297--314, Progr. Probab., 43, Birkhäuser, Basel, 1998. MR1652335
  • Pinelis, Iosif. Fractional sums and integrals of $r$-concave tails and applications to comparison probability inequalities. Advances in stochastic inequalities (Atlanta, GA, 1997), 149--168, Contemp. Math., 234, Amer. Math. Soc., Providence, RI, 1999. MR1694770
  • bysame, phOn exact maximal Khinchine inequalities, High dimensional probability, II (Seattle, WA, 1999), Progr. Probab., vol. 47, Birkhäuser Boston, Boston, MA, 2000, pp. 49--63. MRMR1857314 (2002i:60038)
  • Pinelis, Iosif. Exact asymptotics for large deviation probabilities, with applications. Modeling uncertainty, 57--93, Internat. Ser. Oper. Res. Management Sci., 46, Kluwer Acad. Publ., Boston, MA, 2002. MR1893275
  • Pinelis, Iosif. L'Hospital type rules for monotonicity: applications to probability inequalities for sums of bounded random variables. JIPAM. J. Inequal. Pure Appl. Math. 3 (2002), no. 1, Article 7, 9 pp. (electronic). MR1888922
  • Pinelis, Iosif. Monotonicity properties of the relative error of a Padé approximation for Mills' ratio. JIPAM. J. Inequal. Pure Appl. Math. 3 (2002), no. 2, Article 20, 8 pp. (electronic). MR1906389
  • Pinelis, Iosif. Spherically symmetric functions with a convex second derivative and applications to extremal probabilistic problems. Math. Inequal. Appl. 5 (2002), no. 1, 7--26. MR1880267
  • Pinelis, Iosif. Dimensionality reduction in extremal problems for moments of linear combinations of vectors with random coefficients. Stochastic inequalities and applications, 169--185, Progr. Probab., 56, Birkhäuser, Basel, 2003. MR2073433
  • Pinelis, Iosif. Binomial upper bounds on generalized moments and tail probabilities of (super)martingales with differences bounded from above. High dimensional probability, 33--52, IMS Lecture Notes Monogr. Ser., 51, Inst. Math. Statist., Beachwood, OH, 2006. MR2387759
  • Pinelis, Iosif. On L'Hospital-type rules for monotonicity. JIPAM. J. Inequal. Pure Appl. Math. 7 (2006), no. 2, Article 40, 19 pp. (electronic). MR2221321
  • Pinelis, Iosif. On normal domination of (super)martingales. Electron. J. Probab. 11 (2006), no. 39, 1049--1070. MR2268536
  • Pinelis, Iosif. Exact inequalities for sums of asymmetric random variables, with applications. Probab. Theory Related Fields 139 (2007), no. 3-4, 605--635. MR2322709
  • Pinelis, Iosif. Toward the best constant factor for the Rademacher-Gaussian tail comparison. ESAIM Probab. Stat. 11 (2007), 412--426. MR2339301
  • Pinelis, Iosif. On inequalities for sums of bounded random variables. J. Math. Inequal. 2 (2008), no. 1, 1--7. MR2453629
  • S. Portnoy, phPrivate communication, 1991.
  • Raič, Martin. CLT-related large deviation bounds based on Stein's method. Adv. in Appl. Probab. 39 (2007), no. 3, 731--752. MR2357379
  • Shaked, Moshe; Shanthikumar, J. George. Stochastic orders. Springer Series in Statistics. Springer, New York, 2007. xvi+473 pp. ISBN: 978-0-387-32915-4; 0-387-32915-3 MR2265633
  • Shevtsova, I. G. Refinement of estimates for the rate of convergence in Lyapunov's theorem. (Russian) Dokl. Akad. Nauk 435 (2010), no. 1, 26--28; translation in Dokl. Math. 82 (2010), no. 3, 862--864 MR2790498
  • Talagrand, Michel. The missing factor in Hoeffding's inequalities. Ann. Inst. H. Poincaré Probab. Statist. 31 (1995), no. 4, 689--702. MR1355613
  • Tarski, Alfred. A Decision Method for Elementary Algebra and Geometry. RAND Corporation, Santa Monica, Calif., 1948. iii+60 pp. MR0028796
  • Joel~A. Tropp, phUser-friendly tail bounds for sums of random matrices (preprint), arXiv:1004.4389v7 [math.PR].
  • I. Tyurin, phNew estimates of the convergence rate in the Lyapunov theorem (preprint, arXiv:0912.0726v1 [math.PR]).
  • van de Geer, Sara A. On non-asymptotic bounds for estimation in generalized linear models with highly correlated design. Asymptotics: particles, processes and inverse problems, 121--134, IMS Lecture Notes Monogr. Ser., 55, Inst. Math. Statist., Beachwood, OH, 2007. MR2459935
  • Veraar, Mark. A note on optimal probability lower bounds for centered random variables. Colloq. Math. 113 (2008), no. 2, 231--240. MR2425084
  • Veraar, Mark. On Khintchine inequalities with a weight. Proc. Amer. Math. Soc. 138 (2010), no. 11, 4119--4121. MR2679633
  • Vinogradov, Vladimir. Refined large deviation limit theorems. Pitman Research Notes in Mathematics Series, 315. Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1994. xii+212 pp. ISBN: 0-582-25499-X MR1312369
  • A. V. Zhubr, phOn one extremal problem for N-cube, To appear, 2012.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.