Limit search to available items
Book Cover
Author Weiss, Alan

Title Large Deviations for Performance Analysis : Queues, Communication and Computing
Published Milton : Routledge, 2019


Description 1 online resource (565 pages)
Series Routledge Revivals Ser
Routledge Revivals Ser
Contents 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
Notes 15.5. Justification-PP
Print version record
Subject Large deviations.
System analysis.
Systems Analysis
systems analysis.
Anick-Mitra-Sondhi Model.
Ballot Theorem.
Boundary Theory.
Branching Processes.
Coefficient Processes.
Contraction Principle.
Discrete-Space Markov Processes.
Empirical Distributions.
Empirical Measures.
Erlang's Model.
Exit Problem.
Exponential Approximations.
Finite Markov Processes.
Free M/M/1 Process.
Gar╠łtner-Ellis Theorem.
I.I.D. Random Variables.
I.I.D. Random Vectors.
Invariant Measures.
Kurtz's Theorem.
Large Deviations Principle.
Large Deviations.
Lower Bound.
Markov Process.
Markov Processes.
Metric Spaces.
Parallel Algorithms.
Probable Behavior.
Radon-Nikodym Derivatives.
Random Variables.
Rate Function.
Sanov's Theorem.
Simple Jump Processes.
Stochastic Processes.
Subadditivity Arguments.
Upper Bound.
Varadhan's Integral Lemma.
Large deviations
System analysis
Form Electronic book
Author Shwartz, Adam
ISBN 9780429846878