Large deviation estimates have proved to be the crucial tool required to handle many questions in statistics, engineering, statistial mechanics, and applied probability. Amir Dembo and Ofer Zeitouni, two of the leading researchers in the field, provide an introduction to the theory of large deviations and applications at a level suitable for graduate students. The mathematics is rigorous and the applications come from a wide range of areas, including electrical engineering and DNA sequences. The second edition, printed in 1998, included new material on concentration inequalities and the metric and weak convergence approaches to large deviations. General statements and applications were sharpened, new exercises added, and the bibliography updated. The present soft cover edition is a corrected printing of the 1998 edition.
Author(s): Amir Dembo, Ofer Zeitouni
Edition: 2nd ed. 1998. 2nd printing
Publisher: Springer
Year: 2009
Language: English
Pages: 415
Cover......Page 1
Stochastic Modelling and Applied Probability 38......Page 2
Large Deviations Techniques and Applications (Second edition)......Page 4
9783642033100......Page 5
Preface to the Second Edition......Page 8
Preface to the First Edition......Page 10
Contents......Page 14
1.1 Rare Events and Large Deviations......Page 18
1.2 The Large Deviation Principle......Page 21
1.3 Historical Notes and References......Page 26
2.1 Combinatorial Techniques for Finite Alphabets......Page 28
2.1.1 The Method of Types and Sanov's Theorem......Page 29
2.1.2 Cramér's Theorem for Finite Alphabets in IR......Page 35
2.1.3 Large Deviations for Sampling Without Replacement......Page 37
2.2.1 Cramér's Theorem in IR......Page 43
2.2.2 Cramér's Theorem in IR^d......Page 53
2.3 The Gärtner--Ellis Theorem......Page 60
2.4.1 Inequalities for Bounded Martingale Differences......Page 72
2.4.2 Talagrand's Concentration Inequalities......Page 77
2.5 Historical Notes and References......Page 85
3. Applications - The Finite Dimensional Case......Page 88
3.1 Large Deviations for Finite State Markov Chains......Page 89
3.1.1 LDP for Additive Functionals of Markov Chains......Page 90
3.1.2 Sanov's Theorem for the Empirical Measure of Markov Chains......Page 93
3.1.3 Sanov's Theorem for the Pair Empirical Measure of Markov Chains......Page 95
3.2 Long Rare Segments in Random Walks......Page 99
3.3 The Gibbs Conditioning Principle for Finite Alphabets......Page 104
3.4 The Hypothesis Testing Problem......Page 107
3.5 Generalized Likelihood Ratio Test for Finite Alphabets......Page 113
3.6 Rate Distortion Theory......Page 118
3.7 Moderate Deviations and Exact Asymptotics in IR^d......Page 125
3.8 Historical Notes and References......Page 130
4. General Principles......Page 132
4.1 Existence of an LDP and Related Properties......Page 133
4.1.1 Properties of the LDP......Page 134
4.1.2 The Existence of an LDP......Page 137
4.2.1 Contraction Principles......Page 143
4.2.2 Exponential Approximations......Page 147
4.3 Varadhan's Integral Lemma......Page 154
4.4 Bryc's Inverse Varadhan Lemma......Page 158
4.5 LDP in Topological Vector Spaces......Page 165
4.5.1 A General Upper Bound......Page 166
4.5.2 Convexity Considerations......Page 168
4.5.3 Abstract Gärtner--Ellis Theorem......Page 174
4.6 Large Deviations for Projective Limits......Page 178
4.7 The LDP and Weak Convergence in Metric Spaces......Page 185
4.8 Historical Notes and References......Page 190
5. Sample Path Large Deviations......Page 192
5.1 Sample Path Large Deviations for Random Walks......Page 193
5.2 Brownian Motion Sample Path Large Deviations......Page 202
5.3 Multivariate Random Walk and Brownian Sheet......Page 205
5.4 Performance Analysis of DMPSK Modulation......Page 210
5.5 Large Exceedances in IR^d......Page 217
5.6 The Freidlin--Wentzell Theory......Page 229
5.7 The Problem of Diffusion Exit from a Domain......Page 237
5.8.1 An Angular Tracking Loop Analysis......Page 255
5.8.2 The Analysis of Range Tracking Loops......Page 259
5.9 Historical Notes and References......Page 265
6.1 Cramér's Theorem in Polish Spaces......Page 268
6.2 Sanov's Theorem......Page 277
6.3 LDP for the Empirical Measure---The Uniform Markov Case......Page 289
6.4 Mixing Conditions and LDP......Page 295
6.4.1 LDP for the Empirical Mean in IR^d......Page 296
6.4.2 Empirical Measure LDP for Mixing Processes......Page 302
6.5.1 LDP for Occupation Times......Page 306
6.5.2 LDP for the k-Empirical Measures......Page 312
6.5.3 Process Level LDP for Markov Chains......Page 315
6.6 A Weak Convergence Approach to Large Deviations......Page 319
6.7 Historical Notes and References......Page 323
7.1.1 A General Statement of Test Optimality......Page 328
7.1.2 Independent and Identically Distributed Observations......Page 334
7.2 Sampling Without Replacement......Page 335
7.3 The Gibbs Conditioning Principle......Page 340
7.3.1 The Non-Interacting Case......Page 344
7.3.2 The Interacting Case......Page 347
7.3.3 Refinements of the Gibbs Conditioning Principle......Page 352
7.4 Historical Notes and References......Page 355
A. Convex Analysis Considerations in IR^d......Page 358
B.1 Generalities......Page 360
B.2 Topological Vector Spaces and Weak Topologies......Page 363
B.3 Banach and Polish Spaces......Page 364
B.4 Mazur's Theorem......Page 366
C.1 Additive Set Functions......Page 367
C.2 Integration and Spaces of Functions......Page 369
D.1 Generalities......Page 371
D.2 Weak Topology......Page 372
D.3 Product Space and Relative Entropy Decompositions......Page 374
E. Stochastic Analysis......Page 376
Bibliography......Page 380
General Conventions......Page 402
Glossary......Page 404
Index......Page 408
