Notebooks

Large Deviations

06 Mar 2024 15:16

$\newcommand{\Expect}[1]{\mathbb{E}\left[ #1 \right]}$

The limit theorems of probability theory --- the weak and strong laws of large numbers, the central limit theorem, etc. --- basically say that averages taken over large samples (of well-behaved independent, identically distributed random variables) converge on expectation values. (The strong law of large numbers asserts almost-sure convergence, the central limit theorem asserts a kind of convergence in distribution, etc.) These results say little or nothing about the rate of convergence, however, which is often important for many applications of probability theory, e.g., statistical mechanics. One way to address this is the theory of large deviations. (I believe the terminology that follows goes back to Varadhan in the 1970s, but that's just an impression, rather than research.)

Let me say things sloppily first, so the idea comes through, and then more precisely, so people who know the subject won't get too upset. Suppose $$X$$ is a random variable with expected value $$\Expect{X}$$, and we consider $$S_n \equiv \frac{1}{n}\sum_{i=1}^{n}{X_i}$$, the sample mean of $$n$$ independent, identically-distributed draws of $$X$$. $$S_n$$ obeys a large deviations principle if there is a non-negative function $$r$$, the rate function, such that $\Pr{\left(\left| \Expect{X} - S_n \right| \geq \epsilon\right)} \rightarrow e^{-nr(\epsilon)} ~.$ (The rate function has to obey some sensible but technical continuity conditions.) This is a large deviation result, because the difference between the empirical mean and the expectation is remaining constant as $$n$$ grows --- there has to be a larger and large conspiracy, as it were, among the samples to keep deviating from the expectation in the same way. Now, one reason what I've stated isn't really enough to satisfy a mathematician is that the right-hand side converges on zero, so the functional form of the probability could be anything which also converges on zero and that'd be satisfied, but we want to pick out exponential convergence. The usual way is to look at the limiting decay rate of the probability. Also, we want the probability that the difference between the empirical mean and the expectation falls into any arbitrary set. So one usually sees the LDP asserted in some form like, for any reasonable set $$A$$, $\lim_{n\rightarrow\infty}{-\frac{1}{n}\log{\mathrm{Pr}\left(\left| \Expect{X} - S_n \right| \in A\right)}} = \inf_{x\in A}{r(x)} ~.$
(Actually, to be completely honest, I really shouldn't be assuming that there is a limit to those probabilities. Instead I should connect the lim inf of that expression to the infimum of the rate function over the interior of $$A$$, and the lim sup to the infimum of the rate function over the closure of $$A$$.)

Similar large deviation principles can be stated for the empirical distribution, the empirical process, functionals of sample paths, etc., rather than just the empirical mean. There are tricks for relating LDPs on higher-level objects, like the empirical distribution over trajectories, to LDPs on lower-level objects, like empirical means. (These go under names like "the contraction principle".)

Since ergodic theory extends the probabilistic limit laws to stochastic processes, rather than just sequences of independent variables, it shouldn't be surprising that large deviation principles also hold for some stochastic processes. I am particularly interested in LDPs for Markov processes, and their applications. There are further important connections to information theory, since in an awful lot of situations, the large deviations rate function is the Kullback-Leibler divergence, a.k.a. the relative entropy.

Closely related, but strictly speaking distinct topics:

• Finite-sample deviation inequalities, such as the Bernstein, Chernoff and Hoeffding inequalities, which bound the probability of averages departing by more than a certain amount from expectation values at given finite sample sizes $$n$$;
• Concentration of measure, roughly speaking finite-$$n$$ upper bounds on deviation probabilities holding uniformly over large classes of functions. In contrast, large deviations principles give matching upper and lower bounds, but only for the exponential rate, and only asymptotically as $$n \rightarrow \infty$$.
Recommended, big picture:
• James Bucklew, Large Deviation Techniques in Decision, Simulation, and Estimation
• Thomas Cover and Joy Thomas, Elements of Information Theory [Very nice chapter on large deviations for IID sequences]
• Amir Dembo and Ofer Zeitouni, Large Deviations Techniques and Applications [Chapters 2, 4 and 5, and parts of chapter 6, are available in postscript format via Prof. Dembo's page for his course on large deviations]
• Frank den Hollander, Large Deviations [Nice, short introductory text for people with an applied probability background.]
• Richard S. Ellis
• "The Theory of Large Deviations: from Boltzmann's 1877 Calculation to Equilibrium Macrostates in 2D Turbulence", Physica D 133 (1999): 106--136
• Entropy, Large Deviations, and Statistical Mechanics
• M. I. Friedlin and A. D. Wentzell, Random Perturbations of Dynamical Systems
• Hugo Touchette, "The Large Deviations Approach to Statistical Mechanics", Physics Reports 478 (2009): 1--69, arxiv:0804.0327
• S. R. S. Varadhan, "Large Deviations", Annals of Probability 36 (2008): 397--419, arxiv:0804.2330
To read:
• Paul H. Algoet and Brian H. Marcus, "Large Deviation Theorems for Empirical Types of Markov Chains Constrained to Thin Sets," IEEE Transactions on Information Theory 38 (1992): 1276--1291
• Abdelhamid Amroun, "Equilibrium states for smooth maps", arxiv:1004.2577
• Alexei Andreanov, Giulio Biroli, Jean-Philippe Bouchaud, and Alexandre Lefèvre, "Field theories and exact stochastic equations for interacting particle systems", Physical Review E 74 (2006): 030101, cond-mat/0602307
• David Andrieux, "Equivalence classes for large deviations", arxiv:1208.5699
• Ellen Baake, Frank den Hollander and Natali Zint, "How T-Cells Use Large Deviations to Recognize Foreign Antigens", arxiv:q-bio.SC/0605016 [Presumably == the paper of the same title in Journal of Mathematical Biology 57 (2008): 841--861, but that orders the authors Zint, Baake and den Hollander.]
• J. Barral and P. Goncalves, "On the Estimation of the Large Deviations Spectrum", Journal of Statistical Physics 144 (2011): 1256--1283
• L. Bertini, A. De Sole, D. Gabrielli, G. Jona-Lasinio, C. Landim, "Large deviation approach to non equilibrium processes in stochastic lattice gases", arxiv:math/0602557
• Matthias Birkner, Andreas Greven and Frank den Hollander, "Quenched large deviation principle for words in a letter sequence", arxiv:0807.2611
• Igor Bjelakovic, Jean-Dominique Deuschel, Tyll Krueger, Ruedi Seiler, Rainer Siegmund-Schultze and Arleta Szkola
• Amarjit Budhiraja, Paul Dupuis, Markus Fischer, "Large deviation properties of weakly interacting processes via weak convergence methods", arxiv:1009.6030
• Amarjit Budhiraja, Paul Dupuis, Vasileios Maroulas, "Large deviations for infinite dimensional stochastic dynamical systems", Annals of Applied Probability 36 (2008): 1390--1420, arxiv:0808.3631
• Adrian A. Budini, "Large deviations of ergodic counting processes: a statistical mechanics approach", Physical Review E 84 (2011): 011141, arxiv:1112.2625
• Patrick Cattiaux and Nathael Gozlan, "Deviations bounds and conditional principles for thin sets", arxiv:math/0510257
• Raphaël Cerf and Pierre Petit, "Cramér's theorem for asymptotically decoupled fields", arxiv:1103.4415 [The English abstract is extremely interesting, but unfortunately this paper is in French, so my marking it "to read" is delusional aspirational.]
• Arijit Chakrabarty, "Central Limit Theorem and Large Deviations for truncated heavy-tailed random vectors", arxiv:1003.2159
• Hanshuang Chen, Feng Huang, Guofeng Li, Haifeng Zhang, "Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks", arxiv:1907.13330
• Jihyeok Choi and Sunder Sethuraman, "Large deviations for the degree structure in preferential attachment schemes", Annals of Applied Probability 23 (2013): 722--763
• Po-Ning Chen, "Generalization of Gartner-Ellis theorem", IEEE Transactions on Information Theory 46 (2000): 2752--2760
• Zhiyi Chi
• Alberto Chiarini, Markus Fischer, "On large deviations for small noise Ito processes", Advances in Applied Probability 46 (2014): 1126--147, arxiv:1212.3223
• Igor Chueshov and Annie Millet, "Stochastic 2D hydrodynamical type systems: Well posedness and large deviations", arxiv:0807.1810
• A. de Acosta, "A general nonconvex large deviation result II", Annals of Probability 32 (2004): 1873--1901, math.PR/0410101
• Zach Deitz and Sunder Sethuraman, "Large deviations for a class of nonhomgeneous Markov chains", math.PR/0404230
• Frank den Hollander, Julien Poisat, "Large deviation principles for words drawn from correlated letter sequences", arxiv:1303.5383
• B. Derrida, "Non equilibrium steady states: fluctuations and large deviations of the density and of the current", cond-mat/0703762
• B. Derrida, Joel L. Lebowitz and Eugene R. Speer, "Exact Large Deviation Functional for the Density Profile in a Stationary Nonequilibrium Open System," cond-mat/0105110
• Manh Hong Duong, Mark A. Peletier, Upanshu Sharma, "Coarse-graining and fluctuations: Two birds with one stone", arxiv:1404.1466
• Vlad Elgart and Alex Kamenev, "Rare Events Statistics in Reaction--Diffusion Systems", cond-mat/0404241 [i.e., large deviations]
• Andreas Engel, Remi Monasson and Alexander K. Hartmann, "On Large Deviation Properties of Erdos-Renyi Random Graphs", Journal of Statistical Physics 117 (2004): 387--426
• Mikhail Ermakov, "A moderate deviation principle for empirical bootstrap measure", arxiv:1206.1459
• Parisa Fatheddin, Jie Xiong, "Large Deviation Principle for Some Measure-Valued Processes", arxiv:1204.3501
• Mario Filiasi, Giacomo Livan, Matteo Marsili, Maria Peressi, Erik Vesselli, Elia Zarinelli, "On the concentration of large deviations for fat tailed distributions, with application to financial data", arxiv:1201.2817
• Hans Follmer and Steven Orey, "Large Deviations for the Empirical Field of a Gibbs Measure", Annals of Probability 16 (1988): 961--977
• Peipei Gao, Yong Liu, Yue Sun, Zuohuan Zheng, "Large deviations principle for stationary solutions of stochastic differential equations with multiplicative noise", arxiv:2206.02356
• Jorge Garcia, "A Large Deviation Principle for Stochastic Integrals", Journal of Theoretical Probability 21 (2008): 476--501
• Cristian Giardina, Jorge Kurchan, Luca Peliti, "Direct evaluation of large-deviation functions", cond-mat/0511248
• Yuri Golubev, Vladimir Spokoiny, "Exponential bounds for minimum contrast estimators", arxiv:0901.0655
• Nathael Gozlan and Christian Léonard
• Alice Guionnet, "Large deviations and stochastic calculus for large random matrices", Probability Surveys 1 (2004): 72--172 [Open access]
• O. V. Gulinskii and R. S. Liptser, "Example of Large Deviations for Stationary Processes", Theory of Probability and Applications 44 (1999): 211--225 [PDF]
• Te Sun Han, "An information-spectrum approach to large deviation theorems", cs.IT/0606104
• Rajat Subhra Hazra, Frank den Hollander, Maarten Markering, "Large deviation principle for the norm of the Laplacian matrix of inhomogeneous Erdos-Renyi random graphs", arxiv:2307.02324
• Henrik Hult and Gennady Samorodnitsky, "Large deviations for point processes based on stationary sequences with heavy tails", Journal of Applied Probability 47 (2010): 1--40
• Svante Janson, "Large deviations for sums of partly dependent random variables", Random Structures and Algorithms 24 (2004): 234--248 ["We use and extend a method by Hoeffding to obtain strong large deviation bounds for sums of dependent random variables with suitable dependency structure. The method is based on breaking up the sum into sums of independent variables. Applications are given to U-statistics, random strings and random graphs." Applied here only to Erdos-Renyi (IID) random graphs, but might be extendable to Markov random graphs...? PDF preprint]
• Giovanni Jona-Lasinio, "From fluctuations in hydrodynamics to nonequilibrium thermodynamics", arxiv:1003.4164
• Vladislav Kargin, "A Large Deviation Inequality for Vector Functions on Finite Reversible Markov Chains", math.PR/0508538
• Gerhard Keller, Equilibrium States in Ergodic Theory
• Michael Keyl, "Quantum state estimation and large deviations", quant-ph/0412053
• Yuri Kifer, "Large deviations and adiabatic transitions for dynamical systems and Markov processes in fully coupled averaging", arxiv:0710.2405
• Yuri Kifer, S. R. S. Varadhan, "Nonconventional Large Deviations Theorems", Probability Theory and Related Fields 158 (2014): 197--224, arxiv:1206.0156
• F. Klebaner and R. Liptser, "Large Deviations for Past-Dependent Recursions", math.PR/0603407 [Corrected version of Problems of Information Transmission 32 (1996): 23--34]
• Ioannis Kontoyiannis and S. P. Meyn
• Christian Kuehn, Martin G. Riedler, "Large Deviations for Nonlocal Stochastic Neural Fields", Journal of Mathematical Neuroscience 4 (2014): 1--33, arxiv:1302.5616
• D. Lacoste, A. W. C. Lau and K. Mallick, "Fluctuation theorem and large deviation function for a solvable model of a molecular motor", Physical Review E 78 (2008): 011915
• Vivien Lecomte, Cécile Appert-Rolland, and Frédéric van Wijland
• "Thermodynamic formalism for systems with Markov dynamics", cond-mat/0606211
• "Thermodynamic formalism and large deviation functions in continuous time Markov dynamics", cond-mat/0703435
• Raphael Lefevere, Mauro Mariani, Lorenzo Zambotti, "Large deviations for renewal processes", arxiv:1009.2659
• Christian Léonard , "Entropic Projections and Dominating Points", ESAIM: Probability and Statistics 14 (2010): 343--381, arxiv:0711.0206 ["Generalized entropic projections and dominating points are solutions to convex minimization problems related to conditional laws of large numbers"]
• Robert Sh. Liptser and Anatolii A. Pukhalskii, "Limit theorems on large deviations for semimartingales", math.PR/0510028 [But published in a journal in 1992]
• Fotis Loukissas, "Precise Large Deviations for Long-Tailed Distributions", Journal of Theoretical Probability 25 (2012): 913--924
• Yutao Ma, Ran Wang, Liming Wu, "Moderate Deviation Principle for dynamical systems with small random perturbation", arxiv:1107.3432
• Claudio Macci, "Large Deviations for Empirical Estimators of the Stationary Distribution of a Semi-Markov Process with Finite State Space", Communications in Statistics: Theory and Methods 37 (2008): 3077--3089
• Satya N. Majumdar and Alan J. Bray, "Large-Deviation Functions for Nonlinear Functionals of a Gaussian Stationary Markov Process", Physical Review E 65 (2002): 051112, cond-mat/0202138
• David McAllester, "A Statistical Mechanics Approach to Large Devations Theorems" [E-print available via CiteSeer --- published?]
• Kevin McGoff, Sayan Mukherjee, Andrew Nobel, "Gibbs posterior convergence and the thermodynamic formalism", arxiv:1901.08641
• Kevin McGoff, Sayan Mukherjee, Andrew Nobel, Natesh Pillai, "Consistency of maximum likelihood estimation for some dynamical systems", Annals of Statistics 43 (2015): 1--29, arxiv:1306.5603
• Thomas Mikosch, Olivier Wintenberger, "Precise large deviations for dependent regularly varying sequences", arxiv:1206.1395
• Abdelkader Mokkadem, Mariane Pelletier and Baba Thiam, "Large and moderate deviations principles for kernel estimators of the multivariate regression", math.ST/0703341
• K. Netocny and F. Redig, "Large deviations for quantum spin systems", Journal of Statistical Physics 117 (2004): 521--547, math-ph/0404018
• Ouassim Feliachi, Freddy Bouchet, "Dynamical large deviations for homogeneous systems with long range interactions and the Balescu--Guernsey--Lenard equation", arxiv:2105.05644
• Magda Peligrad, Hailin Sang, Yunda Zhong, Wei Biao Wu, "Exact Moderate and Large Deviations for Linear Processes", arxiv:1111.0537
• Huyen Pham, "Some applications and methods of large deviations in finance and insurance",math.PR/0702473
• Mark Pollicott and Richard Sharp, "Large Deviations, Fluctuations and Shrinking Intervals", Communications in Mathematical Physics 290 (2009): 321--334
• Anatoly Puhalskii, Large Deviations and Idempotent Probability
• Anatolii A. Puhalskii, "Stochastic processes in random graphs", math.PR/0402183 [Large deviations for Erdos-Renyi graphs. Memo to self: how much work would it be to extend this to Markovian graphs?]
• Hong Qian, "Relative Entropy: Free Energy Associated with Equilibrium Fluctuations and Nonequilibrium Deviations", Physical Review E 63 (2001): 042103, math-ph/0007010
• Olivier Rivoire, "The cavity method for large deviations", Journal of Statistical Mechanics: Theory and Experiment (2005): P07004, cond-mat/0506164 ["A method is introduced for studying large deviations in the context of statistical physics of disordered systems. The approach, based on an extension of the cavity method to atypical realizations of the quenched disorder, allows us to compute exponentially small probabilities (rate functions) over different classes of random graphs."]
• David Ruelle, Thermodynamic Formalism
• Shin-ichi Sasa, "Physics of Large Deviation", arxiv:1204.5584
• L. Saulis and V. A. Statulevicius, Limit Theorems for Large Deviations
• Carolyn Schroeder, "I-Projection and Conditional Limit Theorems for Discrete Parameter Markov Processes", Annals of Probability 21 (1993): 721--758
• Adam Shwartz, Large Deviations in Performance Modeling
• Joe Suzuki, "A Markov chain analysis of genetic algorithms: large deviation principle approach", Journal of Applied Probability 47 (2010): 967--975
• Hiroki Takahasi, "Level-2 Large Deviation Principle for Countable Markov Shifts Without Gibbs States", Journal of Statistical Physics 190 (2023): 120
• Hugo Touchette, Rosemary J. Harris, "Large deviation approach to nonequilibrium systems", arxiv:1110.5216
• José Trashorras, Olivier Wintenberger, "Large deviations for bootstrapped empirical measures", arxiv:1110.4620
• A. Vulpiani, F. Cecconi, M. Cencini, A. Puglisi and D. Vergni (eds.)m Large Deviations in Physics: The Legacy of the Law of Large Numbers
• Wei Wang, A. J. Roberts and Jinqiao Duan, "Large deviations for slow-fast stochastic partial differential equations", arxiv:1001.4826
• Lingjiong Zhu, "Process-Level Large Deviations for General Hawkes Processes", arxiv:1108.2431
To write:
• CRS, "Large Deviations in Exponential Families of Stochastic Automata"
• CRS, "Large Deviations for Markovian Compartment Models and Related Population Processes"

Previous versions: 2005-11-09 17:39 (but not the first version by any means)