Fax 800 374 3401
Telephone 44 1462 488900, Fax 44 1462 483011
Telephone 61 3 9210 7777, Fax 61 3 9210 7778
The new edition (early 1997) incorporates a number of corrections. Unfortunately, Chapman Hall also raised the price (several times). If you have the first edition, feel free to download PostScript files that contain all the changes. Here are the changes and new PS files.
The book is designed to be an introduction to the theory, and a compelling collection of real engineering applications, for advanced undergraduate and graduate students in engineering and applied mathematics. The book is also a reference resource for mathematicians, researchers, and engineers. The book is self-contained, with detailed appendices to cover all the major tools used in the book, and over 60 figures.
We have an errata page with all errata which are incorporated into the second printing. We shall create an errata page for the second printing as soon as errors are found... .
is a member of the technical staff at Bell Laboratories,
1. Large Deviations of Random Variables
2. General Principles
3. Random Walks, branching processes
4. Poisson and Related Processes
5. Large Deviations for Processes
6. Freidlin-Wentzell Theory
7. Applications and Extensions
8. Boundary Theory
9. Allocating Independent Subtasks
10. Parallel Algorithms: Rollback
11. The M/M/1 Queue
12. Erlang's Model
13. The Anick-Mitra-Sondhi Model
15. Priority Queues
16. The Flatto-Hahn-Wright model
A. Analysis and Probability
B. Discrete-Space Markov Processes
C. Calculus of Variations
D. Large Deviations Techniques
This book consists of two synergistic parts.
The first half is the theory of large deviations developed from the beginning (i.i.d. 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 we need for the applications we present, we to keep the theory to a manageable level, both in terms of length and in terms of difficulty. Since our scope is limited to a class of relatively simple processes, the theory is accessible, and less demanding mathematically, than more general treatments. Within our scope, our treatment is detailed, comprehensive and self-contained. As the book shows, there are sufficienty many interesting applications of jump Markov processes to warrant a special treatment. After all, we live in continuous time, and the events that occur in digital equipment are discrete.
We firmly believe that the large deviations of processes should be taught first for jump Markov processes: more difficult processes can be studied once the foundations and the intuition are established. Diffusions are complicated objects, and the student does not need the extra burden of a subtle process to hinder the understanding of large deviations. Discrete time presents another unnecessarily difficult process, because the jumps are usually more general than those of the processes we consider.
The second half of the book is a collection of applications developed at AT&T Bell Laboratories. Our applications cover large areas of the theory of communication networks: circuit-switched transmission (Chapter 12), packet transmission (Chapter 13), multiple access channels (Chapter 14), and the M/M/1 queue (Chapter 11). We cover aspects of parallel computation in a much more spotty fashion: basics of job allocation (Chapter 9), rollback-based parallel simulation (Chapter 10), assorted priority queuing models (Chapter 15) that may be used in performance models of various computer architectures, and asymptotic coupling of processors (Chapter 16).
This book can be used as a basis for two types of one-semester courses. The first is an introduction to the theory of large deviations, through jump Markov processes. This course should cover most of Chapters 1, 2, 5, 6, possibly the advanced material in Chapter 8, and Appendix A. Such a course would prepare the student to read the more mathematical theory, and to fully appreciate the applications worked out in the rest of the book. It would be wise (in our opinion) to sprinkle such a theory-oriented course with some of the applications.
The second course is application-oriented. Such a course should probably start with Chapter 1 (at least Sections 1 through 3), so that some flavor of the theory is provided. Many results can then be stated without proof, with or without intuitive explanations. Some basic tools from the calculus of variations, at least as summarized in Appendix C, should be covered. Then applications can be presented.