Stochastic-process limits. An introduction to stochastic-process limits and their application to queues.

*(English)*Zbl 0993.60001
Springer Series in Operations Research. New York, NY: Springer. xxiii, 602 p. (2002).

From the author’s preface: This book is about stochastic-process limits, i.e., limits in which a sequence of stochastic processes converges to another stochastic process. Since the converging stochastic processes are constructed from initial stochastic processes by appropriately scaling time and space, the stochastic-process limits provide a macroscopic view of uncertainty. The stochastic-process limits are interesting and important because they generate simple approximations for complicated stochastic processes and because they help to explain the statistical regularity associated with a macroscopic view of uncertainty. This book emphasizes the continuous-mapping approach to obtain new stochastic-process limits from previously established stochastic-process limits. The continuous-mapping approach is applied to obtain stochastic-process limits for queues, i.e., probability models of waiting lines or service systems. These limits for queues are called heavy-traffic limits because they involve a sequence of models in which the offered loads are allowed to increase towards the critical value for stability. These heavy-traffic limits generate simple approximations for complicated queueing processes under normal loading and reveal the impact of variability upon queueing performance. By focusing on the application of stochastic-process limits to queues, this book also provides an introduction to heavy-traffic stochastic-process limits for queues.

The book has fifteen chapters, which can be grouped roughly into four parts, ordered according to increasing difficulty. The level of difficulty is far from uniform: The first part is intended to be accessible with less background. It would be helpful to know something about probability and queues. The first part, containing the first five chapters, provides an informal introduction to stochastic-process limits and their application to queues. The first part provides a broad overview, mostly without proofs, intending to complement and supplement other books. Chapter 1 uses simulation to help the reader directly experience with statistical regularity associated with stochastic-process limits. Chapter 2 discusses applications of the random walks simulated in Chapter 1. Chapter 3 introduces the mathematical framework for stochastic-process limits. Chapter 4 provides an overview of stochastic-process limits, presenting Donsker’s theorem and some of its generalizations. Chapter 5 provides an introduction to heavy-traffic stochastic-process limits for queues.

The second part, containing Chapters 6–10, shows how the unmatched jumps can arise and expands the treatment of queueing models. Chapter 6 uses simulation to demonstrate that there should indeed be unmatched jumps in the limit process in several examples. Chapter 7 continues the overview of stochastic-process limits begun in Chapter 4. The remaining chapters in the second part apply the stochastic-process limits, with the continuous-mapping approach, to obtain more heavy-traffic limits for queues.

The third part, containing Chapters 11–14, is devoted to the technical foundations needed to establish stochastic-process limits with unmatched jumps in the limit process. The earlier queueing chapters draw on the third part to a large extent. The queueing chapters are presented first to provide motivation for the technical foundations. The third part begins with Chapter 11, which provides more details on the mathematical framework for stochastic-process limits, expanding upon the brief introduction in Chapter 3. Chapter 12 focuses on the function space \(D\) of right-continuous \(\mathbb R^k\)-valued functions with left limits, endowed with one of the nonstandard Skorokhod M topologies (\(\text{M}_1\) or \(\text{M}_2\)). As a basis for applying the continuous-mapping approach to establish new stochastic-process limits in this context, Chapter 13 shows that commonly used functions from \(D\) or \(D\times D\) to \(D\) preserve convergence with M (and \(\text{J}_1\)) topologies. The third part concludes with Chapter 14, which establishes heavy-traffic limits for networks of queues.

The fourth part, containing Chapter 15, is more exploratory. It initiates new directions for research. Chapter 15 introduces the new spaces larger than \(D\) that can be used to express stochastic-process limits for scaled stochastic processes with even greater fluctuations. The fourth part is most difficult, not because what appears is so abstruse, but because so little appears of what originally was intended: Most of the theory is yet to be developed.

To avoid excessive length, material was deleted from the book and placed in an Internet Supplement, which can be found via the Springer web site http://www.springer-ny.com/whittThe first choice for cutting was the more technical material. Thus, the Internet Supplement contains many proofs for theorems in the book. The Internet Supplement also contains related supplementary material. Finally, the Internet Supplement provides a place to correct errors found after the book has been published.

The book has fifteen chapters, which can be grouped roughly into four parts, ordered according to increasing difficulty. The level of difficulty is far from uniform: The first part is intended to be accessible with less background. It would be helpful to know something about probability and queues. The first part, containing the first five chapters, provides an informal introduction to stochastic-process limits and their application to queues. The first part provides a broad overview, mostly without proofs, intending to complement and supplement other books. Chapter 1 uses simulation to help the reader directly experience with statistical regularity associated with stochastic-process limits. Chapter 2 discusses applications of the random walks simulated in Chapter 1. Chapter 3 introduces the mathematical framework for stochastic-process limits. Chapter 4 provides an overview of stochastic-process limits, presenting Donsker’s theorem and some of its generalizations. Chapter 5 provides an introduction to heavy-traffic stochastic-process limits for queues.

The second part, containing Chapters 6–10, shows how the unmatched jumps can arise and expands the treatment of queueing models. Chapter 6 uses simulation to demonstrate that there should indeed be unmatched jumps in the limit process in several examples. Chapter 7 continues the overview of stochastic-process limits begun in Chapter 4. The remaining chapters in the second part apply the stochastic-process limits, with the continuous-mapping approach, to obtain more heavy-traffic limits for queues.

The third part, containing Chapters 11–14, is devoted to the technical foundations needed to establish stochastic-process limits with unmatched jumps in the limit process. The earlier queueing chapters draw on the third part to a large extent. The queueing chapters are presented first to provide motivation for the technical foundations. The third part begins with Chapter 11, which provides more details on the mathematical framework for stochastic-process limits, expanding upon the brief introduction in Chapter 3. Chapter 12 focuses on the function space \(D\) of right-continuous \(\mathbb R^k\)-valued functions with left limits, endowed with one of the nonstandard Skorokhod M topologies (\(\text{M}_1\) or \(\text{M}_2\)). As a basis for applying the continuous-mapping approach to establish new stochastic-process limits in this context, Chapter 13 shows that commonly used functions from \(D\) or \(D\times D\) to \(D\) preserve convergence with M (and \(\text{J}_1\)) topologies. The third part concludes with Chapter 14, which establishes heavy-traffic limits for networks of queues.

The fourth part, containing Chapter 15, is more exploratory. It initiates new directions for research. Chapter 15 introduces the new spaces larger than \(D\) that can be used to express stochastic-process limits for scaled stochastic processes with even greater fluctuations. The fourth part is most difficult, not because what appears is so abstruse, but because so little appears of what originally was intended: Most of the theory is yet to be developed.

To avoid excessive length, material was deleted from the book and placed in an Internet Supplement, which can be found via the Springer web site http://www.springer-ny.com/whittThe first choice for cutting was the more technical material. Thus, the Internet Supplement contains many proofs for theorems in the book. The Internet Supplement also contains related supplementary material. Finally, the Internet Supplement provides a place to correct errors found after the book has been published.

Reviewer: V.Schmidt (Ulm)