Abstract

We extend the well known large deviation upper bound for sums of independent, identically distributed random variables in Rd\mathbb{R}^d by weakening the requirement that the rate function have compact level sets (the classical Cramér condition). To do so we establish an apparently new theorem on approximation of closed convex sets by polytopes.

Author information

Contact details are reproduced from the original publication and may be historical.

Peter E. Ney

University of Wisconsin, Dept. of Mathematics, 480 Lincoln Drive, Madison, WI 53706, USA.

Stephen M. Robinson

University of Wisconsin, Dept. of Industrial Engineering, 1513 University Avenue, Madison, WI 53706-1572, USA.

Keywords

  • Large deviations
  • Cramér condition
  • rate function
  • polyhedral convex sets
  • polytopes

References

  1. H. Cramér: On a new limit theorem in the theory of probability, in Colloquium on the Theory of Probability, Hermann, Paris, 1937.Google Scholar
  2. A. Dembo, O. Zeitouni: Large Deviations Techniques and Applications, Jones and Bartlett, Boston, 1993.Google Scholar
  3. J. D. Deuschel, D. W. Stroock: Large Deviations, Academic Press, Boston, 1989.Google Scholar
  4. I. H. Dinwoodie: A note on the upper bound for i.i.d. large deviations, Annals of Probability 19, 1991, 1732–1736.https://doi.org/10.1214/aop/1176990231Google Scholar
  5. L. Hörmander: Sur la fonction d’appui des ensembles convexes dans un espace localement convexe, Arkiv för Matematik 3, 1955, 181–186.https://doi.org/10.1007/BF02589354Google Scholar
  6. H. Rådström: An embedding theorem for spaces of convex sets, Proc. Amer. Math. Soc. 3, 1952, 165–169.https://doi.org/10.1090/S0002-9939-1952-0045938-2Google Scholar
  7. S. M. Robinson: An embedding theorem for unbounded convex sets, Technical Summary Report 1321, Mathematics Research Center, University of Wisconsin–Madison, Madison, WI, 1973.Google Scholar
  8. S. M. Robinson: Some continuity properties of polyhedral multifunctions, Mathematical Programming Study 14, 1981, 206–214.https://doi.org/10.1007/BFb0120929Google Scholar
  9. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton, NJ, 1970.Google Scholar
  10. M. Slaby: On the upper bound for large deviations for sums of i.i.d. random vectors, Annals of Probability 16, 1988, 978–990.https://doi.org/10.1214/aop/1176991672Google Scholar
  11. S. R. S. Varadhan: Large Deviations and Applications, CBMS–NSF Regional Conference Series in Applied Mathematics No. 46, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1984.Google Scholar

Suggested citation

P. E. Ney, S. M. Robinson. “Polyhedral Approximation of Convex Sets with an Application to Large Deviation Probability Theory.” Journal of Convex Analysis 2 (1995), No. 1&2, 229–240. https://doi.org/10.68381/jca02015

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 1995. Rights now held by Banach Press LLC.