Cover; Title Page; Copyright Page; Table of Contents; 0: What this Book Is, and What It Is Not; 0.1. What to Do with this Book; 0.2. About the Format of the Book; 0.3. Acknowledgments; 1: Large Deviations of Random Variables; 1.1. Heuristics and Motivation; 1.2. I.I.D. Random Variables; 1.3. Examples-I.I.D. Random Variables; 1.4. I.I.D. Random Vectors; 1.5. End Notes; 2: General Principles; 2.1. The Large Deviations Principle; 2.2. Varadhan's Integral Lemma; 2.3. The Contraction Principle; 2.4. Empirical Measures: Sanov's Theorem; 3: Random Walks, Branching Processes; 3.1. The Ballot Theorem
3.2. Branching Random Walks4: Poisson and Related Processes; 4.1. The One-Dimensional Case; 4.2. Jump Markov Processes; 4.3. Martingales and Markov Processes; 5: Large Deviations for Processes; 5.1. Kurtz's Theorem; 5.2. Properties of the Rate Function; 5.3. The Lower Bound; 5.4. The Upper Bound: Orientation; 5.5. Proof of the Upper Bound; 6: Freidlin-Wentzell Theory; 6.1. The Exit Problem; 6.2. Beyond the Exit Problem; 6.3. Discontinuities; 6.4. Convergence of Invariant Measures; 7: Applications and Extensions; 7.1. Empirical Distributions of Finite Markov Processes
7.2. Simple Jump Processes7.3. The Free M/M/1 Process; 7.4. Meaning of the Twisted Distribution; 7.5. End Notes; 8: Boundary Theory; 8.1. The Rate Functions; 8.2. Properties of the Rate Function; 8.3. Proof of the Upper Bound; 8.4. Constant Coefficient Processes; 8.5. The Lower Bound; 8.6. End Notes; Applications; 9: Allocating Independent Subtasks; 9.1. Useful Notions; 9.2. Analysis; 9.3. End Notes; 10: Parallel Algorithms: Rollback; 10.1. Rollback Algorithms; 10.2. Analysis of a Rollback Tree; 11: The M/M/1 Queue; 11.1. The Model; 11.2. Heuristic Calculations; 11.3. Most Probable Behavior
11.4. Reflection Map11.5. The Exit Problem and Steady State; 11.6. The Probability of Hitting a Point; 11.7. Transient Behavior; 11.8. Approach to Steady State; 11.9. Further Extensions; 11.10. End Notes; 12: Erlang's Model; 12.1. Scaling and Preliminary Calculations; 12.2. Starting with an Empty System; 12.3. Starting with a Full System in Light Traffic; 12.4. Justification; 12.5. Erlang's Model: General Starting Point; 12.6. Large Deviations Theory; 12.7. Extensions to Erlang's Model; 12.8. Transient Behavior of Trunk Reservation; 12.9. End Notes; 13: The Anick-Mitra-Sondhi Model
13.1. The Simple Source Model13.2. Buffer Statistics; 13.3. Small Buffer; 13.4. Large Buffer; 13.5. Consequences of the Solution; 13.6. Justification; 13.7. Control Schemes; 13.8. Multiple Classes; 13.9. End Notes; 14: Aloha; 14.1. The I.D. Model and Heuristics; 14.2. Related Models; 14.3. Basic Analysis; 14.4. Large Deviations of Aloha; 14.5. Justification; 14.6. A Paradox-Resolved; 14.7. Slotted Aloha Models; 14.8. End Notes; 15: Priority Queues; 15.1. Preemptive Priority Queue; 15.2. Most Probable Behavior-PP; 15.3. The Variational Problem-PP; 15.4. Probabilistic Questions-PP
