Generalization of Gartner-Ellis theorem

Po-Ning Chen*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


A generalization of the Gartner-Ellis Theorem for arbitrary random sequences is established. It is shown that the conventional formula of the large deviation rate function, based on the moment generating function techniques, fails to describe the general (possibly nonconvex) large deviation rate for an arbitrary random sequence. An (nonconvex) extension formula obtained by twisting the conventional large deviation rate function around a continuous functional is therefore proposed. As a result, a new Gartner-Ellis upper bound is proved. It is demonstrated by an example that a tight upper bound on the large deviation rate of an arbitrary random sequence can be obtained by choosing the right continuous functional, even if the true large deviation rate is not convex. Also proved is a parallel extension of the Gartner-Ellis lower bound with the introduction of a new notion of Gartner-Ellis set within which the upper bound coincides with the lower bound (for countably many points).

Original languageEnglish
Pages (from-to)2752-2760
Number of pages9
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - Nov 2000


  • Arbitrary random sequence
  • Exponent
  • Gartner-ellis theorem
  • Information spectrum
  • Large deviations

Cite this