Large Deviations for Performance Analysis

by Shwartz, Adam; Weiss, Alan

• ISBN13: 9780412063114
• ISBN10: 0412063115
• Format: Hardcover
• Copyright: 1995-05-01
• Publisher: Chapman & Hall

Summary

This book consists of two synergistic parts. The first half develops the theory of large deviations from the beginning (iid random variables) through recent results on the theory for processes with boundaries, keeping to a very narrow path: continuous-time, discrete-state processes. By developing only what is needed for the applications, the theory is kept to a manageable level, both in terms of length and in terms of difficulty. Within its scope, the treatment is detailed, comprehensive and self-contained. As the book shows, there are sufficiently many interesting applications of jump Markov processes to warrant a special treatment. The second half is a collection of applications developed at Bell Laboratories. The applications cover large areas of the theory of communication networks: circuit-switched transmission, packet transmission, multiple access channels, and the M/M/1 queue. Aspects of parallel computation are covered as well: basics of job allocation, rollback-based parallel simulation,assorted priority queueing models that might be used in performance models of various computer architectures, and asymptotic coupling of processors. These applications are thoroughly analyzed using the tools developed in the first half of the book.Features: A transient analysis of the M/M/1 queue; a new analysis of an Aloha model using Markov modulated theory; new results for Erlang's model; new results for the AMS model; analysis of "serve the longer queue", "join the shorter queue" and other simple priority queues; and a simple analysis of the Flatto-Hahn-Wright model of processor-sharing.

Table of Contents

0. What this Book Is and What It Is Not	1	(8)
0.1. What to Do with this Book	5	(1)
0.2. About the Format of the Book	5	(1)
0.3. Acknowledgments	6	(3)
1. Large Deviations of Random Variables	9	(20)
1.1. Heuristics and Motivation	9	(5)
1.2. I.I.D. Random Variables	14	(5)
1.3. Examples--I.I.D. Random Variables	19	(4)
1.4. I.I.D. Random Vectors	23	(2)
1.5. End Notes	25	(4)
2. General Principles	29	(16)
2.1. The Large Deviations Principle	29	(4)
2.2. Varadhan's Integral Lemma	33	(3)
2.3. The Contraction Principle	36	(1)
2.4. Empirical Measures: Sanov's Theorem	37	(8)
3. Random Walks, Branching Processes	45	(8)
3.1. The Ballot Theorem	46	(2)
3.2. Branching Random Walks	48	(5)
4. Poisson and Related Processes	53	(16)
4.1. The One-Dimensional Case	53	(3)
4.2. Jump Markov Processes	56	(5)
4.3. Martingales and Markov Processes	61	(8)
5. Large Deviations for Processes	69	(60)
5.1. Kurtz's Theorem	75	(10)
5.2. Properties of the Rate Function	85	(20)
5.3. The Lower Bound	105	(9)
5.4. The Upper Bound: Orientation	114	(3)
5.5. Proof of the Upper Bound	117	(12)
6. Freidlin-Wentzell Theory	129	(40)
6.1. The Exit Problem	132	(25)
6.2. Beyond the Exit Problem	157	(3)
6.3. Discontinuities	160	(4)
6.4. Convergence of Invariant Measures	164	(5)
7. Applications and Extensions	169	(22)
7.1. Empirical Distributions of Finite Markov Processes	169	(6)
7.2. Simple Jump Processes	175	(4)
7.3. The Free M/M/1 Process	179	(4)
7.4. Meaning of the Twisted Distribution	183	(6)
7.5. End Notes	189	(2)
8. Boundary Theory	191	(52)
8.1. The Rate Functions	195	(6)
8.2. Properties of the Rate Function	201	(14)
8.3. Proof of the Upper Bound	215	(5)
8.4. Constant Coefficient Processes	220	(10)
8.5. The Lower Bound	230	(12)
8.6. End Notes	242	(1)
Applications	243	(2)
9. Allocating Independent Subtasks	245	(10)
9.1. Useful Notions	246	(3)
9.2. Analysis	249	(4)
9.3. End Notes	253	(2)
10. Parallel Algorithms: Rollback	255	(6)
10.1. Rollback Algorithms	255	(3)
10.2. Analysis of a Rollback Tree	258	(3)
11. The M/M/1 Queue	261	(28)
11.1. The Model	261	(1)
11.2. Heuristic Calculations	262	(5)
11.3. Most Probable Behavior	267	(5)
11.4. Reflection Map	272	(2)
11.5. The Exit Problem and Steady State	274	(3)
11.6. The Probability of Hitting a Point	277	(2)
11.7. Transient Behavior	279	(2)
11.8. Approach to Steady State	281	(2)
11.9. Further Extensions	283	(3)
11.10. End Notes	286	(3)
12. Erlang's Model	289	(36)
12.1. Scaling and Preliminary Calculations	290	(2)
12.2. Starting with an Empty System	292	(8)
12.3. Starting with a Full System in Light Traffic	300	(2)
12.4. Justification	302	(3)
12.5. Erlang's Model: General Starting Point	305	(3)
12.6. Large Deviations Theory	308	(5)
12.7. Extensions to Erlang's Model	313	(5)
12.8. Transient Behavior of Trunk Reservation	318	(5)
12.9. End Notes	323	(2)
13. The Anick-Mitra-Sondhi Model	325	(62)
13.1. The Simple Source Model	328	(2)
13.2. Buffer Statistics	330	(11)
13.3. Small Buffer	341	(4)
13.4. Large Buffer	345	(3)
13.5. Consequences of the Solution	348	(2)
13.6. Justification	350	(11)
13.7. Control Schemes	361	(17)
13.8. Multiple Classes	378	(8)
13.9. End Notes	386	(1)
14. Aloha	387	(32)
14.1. The I.D. Model and Heuristics	387	(7)
14.2. Related Models	394	(3)
14.3. Basic Analysis	397	(1)
14.4. Large Deviations of Aloha	398	(2)
14.5. Justification	400	(5)
14.6. A Paradox--Resolved	405	(4)
14.7. Slotted Aloha Models	409	(8)
14.8. End Notes	417	(2)
15. Priority Queues	419	(40)
15.1. Preemptive Priority Queue	421	(1)
15.2. Most Probable Behavior--PP	422	(1)
15.3. The Variational Problem--PP	423	(13)
15.4. Probabilistic Questions--PP	436	(2)
15.5. Justification--PP	438	(5)
15.6. Serve the Longest Queue	443	(1)
15.7. Most Probable Behavior--SL	444	(1)
15.8. The Main Result--SL	445	(1)
15.9. Justification--SL	446	(8)
15.10. Join the Shortest Queue	454	(4)
15.11. End Notes	458	(1)
16. The Flatto-Hahn-Wright model	459	(12)
16.1. Most Probable Behavior	462	(1)
16.2. Formal Large Deviations Calculations	463	(4)
16.3. Justification of the Calculation	467	(3)
16.4. End Notes	470	(1)
A. Analysis and Probability	471	(28)
A.1. Topology, Metric Spaces, and Functions	471	(11)
A.2. Ordinary Differential Equations	482	(1)
A.3. Probability and Integration	483	(10)
A.4. Radon-Nikodym Derivatives	493	(2)
A.5. Stochastic Processes	495	(4)
B. Discrete-Space Markov Processes	499	(16)
B.1. Generators and Transition Semigroups	499	(2)
B.2. The Markov Process	501	(2)
B.3. Birth-Death Processes	503	(2)
B.4. Martingales	505	(10)
C. Calculus of Variations	515	(12)
C.1. Heuristics of the Calculus of Variations	515	(3)
C.2. Calculus of Variations and Large Deviations	518	(2)
C.3. One-Dimensional Tricks	520	(5)
C.4. Results from the Calculus of Variations	525	(2)
D. Large Deviations Techniques	527	(12)
D.1. The Gartner-Ellis Theorem	527	(6)
D.2. Subadditivity Arguments	533	(1)
D.3. Exponential Approximations	533	(1)
D.4. Level II	534	(5)
References	539	(12)
Index	551