STOCHASTIC MODELS
Edited by D.P. Heyman and M.J. Sobel
PREFACE
One of the central problems in operations research and management science is how to quantify the effects of uncertainty about the future. This, the second volume in a series of handbooks, is devoted to models where chance events play a major role. The thirteen chapters survey topics in applied probability that have been particularly useful in operations research and management science. Each chapter was written by an expert (both in the subject matter and in its exposition), and most are meant to be accessible at an introductory level. By this we mean a calculus-based probability course and the rudiments of matrix algebra.
Stochastic models are concerned with phenomena that vary as time advances, and where the variation has a significant chance component. Examples in operations research and management science are legion. Two examples from everyday life are the number of books on a library shelf and the availability of the local copying machine. More intricate examples from commercial activities are the stocks in the warehouse of a food chain and the availability of a dialtone on your telephone.
The chapters fall into four groups. The first four cover the fundamentals of stochastic processes, and lay the foundation for the following chapters. The next three chapters are concerned with methods of getting numbers. This includes numerical solution of models, parameter estimation for models, and simulation of models. Chapters 8 and 9 describe the fundamentals of dynamic optimization. The last four chapters are concerned with the most important structured models in operations research and management science; queues, queueing networks, inventories. and reliability.
The first chapter, by Richard Serfozo, is about point processes. Point processes on the line describe the times at which events take place. For example, the arrival epochs of customers to a queue, the demand epochs in an inventory system, or the failure times of a piece of equipment. When another attribute is added to the description of a point, e.g. a priority value, a point process in two dimensions is formed. Considering several attributes leads to point processes in several dimensions. Thus, point processes have intrinsic interest, and are among the fundamental building blocks of many stochastic models. Chapter 1 starts with several examples, and then Section 2 covers the Poisson and related processes. This includes superposition, thinning and translating Poisson processes, and compound-Poisson, Cox, negative-binomial, and cluster processes. Section 3 covers renewal theory. The emphasis is on the major limit theorems which describe the long-run behavior of these processes.
Section 4 is concerned with stationary processes. The intensity function and Palm probabilities are primary topics. The next section describes point processes in terms of martingales. (Martingales are the primary subject of Chapter 3) Among the applications of this point of view is a way to see if a complicated process is close to being a Poisson process. The final section describes theorems about sums of point processes that converge to a Poisson process.
Markov processes enjoy the property that no matter what the past was, the current state is,,~ll that is needed to predict the future. This allows flexibility in modeling and produces tractable models. This class of processes is the subject of Chapter 2, by Alan Karr. Section 1 shows how Markov processes are related to other types of stochastic processes. Section 2 covers the main features of discrete Markov chains and Section 3 does the same for continuous-time Markov chains. Diffusion processes, the topic of Chapter 4, are Markov processes, so it is not out of place to treat them in this chapter. Section 4 gives a way to reconstruct the sample path of a partially observable diffusion process. The final section concerns Markov random fields, which are processes with a multidimensional index set. Instead of the random variables having a time index, they have a space index.
Martingales were orginally used to study gambling strategies, but they have become a fundamental tool in the theory of stochastic processes and have been used in many applied models. Chapter 3, by Howard Taylor, covers martingales and random walks. Section 1 gives definitions and examples. The optional stopping and sampling theorems, and the martingale convergence theorem are described in Section 2. These theorems are used in three examples in the next section. Section 4 introduces continuous-time martingales, which are the basis for stochastic integral equations. This section gives a non-technical introduction to these topics. The final section gives some highlights from the theory of random walks.
Sometimes it is very difficult to obtain an exact solution of a stochastic process model and one resorts to bounds and approximations. Diffusion approximations are an important class of methods and in Chapter 4 Peter Glynn gives an overview of the applications of diffusion approximations to operations research models. Sections 2 and 3 describe the basic elements of the theory of weak convergence that underlies the method of diffusion approximation. Then Section 4 discusses the most basic diffusion approximation, namely that sums of random variables can be approximated by Brownian motion. Section 5 uses the correspondence between random walks and the single-server queue to develop the theory of weak convergence for such queues. Most of the rest of the chapter describes applications of the theory of weak convergence to models of networks of queues.
Even when explicit formulas for the quantities of interest are obtained, it is not always straightforward to do numerical evaluations. In Chapter 5, Winfried Grassmann describes computational methods that are used for stochastic models. The first section gives some examples where 'obvious' ways to evaluate probabilities from formulas are not suitable for numerical computations, and presents the basic elements of rounding-error analysis for floating-point arithmetic done on a digital computer. Section 2 is devoted to Markov processes. Algorithms for the transient and steady-state probabilities of discrete-time and continuous-time Markov chains, and for the steady-state probabilities of semi-Markov processes are given. Phase-type distributions, which are used extensively in algorithmic work, are introduced. Sections 3 and 4 expand the material in Section 2. Section 3 covers ways to generate and store transition matrices, iterative methods (Jacobi and Gauss-Seidel), and aggregationdisaggregation methods that can handle very large problems. Section 4 considers Markov chains where the rows of the transition matrix repeat. This structure appears in many queueing models, and several ways of exploiting it are described. These include the classical method based on Rouch6's theorem, Wiener-Hopf factorization, the matrix methods pioneered by M. Neuts, and state reduction.
Chapter 6, by John Lehoczky, discusses many of the statistical methods that are used in fitting stochastic models to real data. The chapter starts with a review of classical parametric statistical inference, including point, Bayesian, and maximum-likelihood estimation. The method of moments, the jackknife procedure, and confidence intervals are also discussed. Section 3 covers hypothesis testing. These ideas are applied to stochastic processes in Section 4. Procedures for estimating the transition probabilities for discrete and continuous-time Markov chains, and birth-and-death processes are given. The sequential-probability-ratio test for choosing the sample size dynamically is covered in Section 5. Estimation for models where one stochastic process generates the parameters of another stochastic process is the subject of the last section.
Although simulation is often viewed as a method of last resort, it is probably used more often than any other method for analyzing stochastic models. Chapter 7, by Bruce Schmeiser, discusses the issues that arise in each step of a simulation experiment. The first is to select a source of randomness. This is discussed in Section 2, which emphasizes methods for generating pseudorandom numbers. The second step, random-variate generation, concerns transforming the source of randomness into the input random variables of the simulation. This is described in Section 3. Section 4, on input modeling, covers the process of determining a model for the input random variables. After the sample paths are generated, the output is used to estimate performance measures. Section 5 presents methods for obtaining point estimates, and Section 6 presents methods for estimating the variance of these point estimates. The final section covers variance reduction techniques, which attempt to improve the quality of the point estimates.
Chapters 8 and 9 discuss the optimization of stochastic dynamic models, that is controlled stochastic processes. The models are discrete in time in Chapter 8 and continuous in time in Chapter 9. In Chapter 8, Markov decision processes (MDP's), Martin Puterman presents a synthesis of the qualitative theory of MDP's with the properties of algorithms to compute optimal decision rules.
Each of these topics merits a separate chapter and the size of Chapter 8 is double that of the others. It begins with a definition of the generic MDP and examples that illustrate the notation. Section 4 presents the basic results for finite-horizon models and highlights dynamic programming recursions. The next four sections concern models with infinitely long planning horizons. Section 5 discusses the foundations of infinite-horizon models with criteria of expected total reward, expected discounted reward, and gain-rate (long-run average reward per unit time). The discounted criterion is examined in detail in Section 6. The theory in this case is reasonably complete and the algorithms converge geometrically fast. The expected total reward and the gain-rate criteria are discussed in Sections 7 and 8, respectively. Both criteria generate rich mathematical theories and the gain-rate criterion invites secondary criteria to resolve ties. The chapter ends with an extension of many of the chapter's results to continuous-time models in which the underlying stochastic processes are semi-Markov or Markov renewal processes.
Chapter 10, by Raymond Rishel, concerns the optimal control of continuoustime Markov processes. It begins with four prototype examples that illustrate different operations research/ management science situations and control problems for different types of Markov processes. Then dynamic programming sufficiency conditions for optimality are discussed in general and applied to the four examples. These examples indicate the current status of the feasibility of determining optimal controls for different kinds of continuous-time Markov control problems. The concluding section discusses the linear-quadratic-Gaussian control problem that has been applied so widely.
Queueing theory may be the oldest problem-area in operations research, having started in 1917 with Erlang's work at the Copenhagen Telephone Company. Chapter 10, by Robert Cooper, surveys this subject. Research in queueing theory can be divided into two large categories; general theorems that apply to a broad class of queueing models, and specific formulas for a particular model. The former concern basic properties, such as the existence of long-run averages, while the latter provide a way of calculating a long-run average for a particular set of assumptions about the nature of the queue. Chapter 10 starts with a discussion of some of the basic theorems, including the famous 'Little's law'. Section 3 describes some of the important performance measures for queues. The exponential distribution is ubiquitous in queueing theory, and Section 4 explains why. The emphasis turns to formulas for performance measures in Section 5, with a discussion of queues that can be described by a birth-and-death process. The next section extends these ideas to multi-dimensional birth-and-death processes. Sections 8 and 9 describe the embedded Markov chain methods for two classes of models. The final section mentions some advanced topics of current research.
The emphasis in Chapter 10 is on a solitary queueing system. Chapter 11, by Jean Walrand, is concerned with the concepts and methods that are used to study networks of queues. These models have been widely applied in computer performance evaluation, and in the analysis of communication systems and flexible manufacturing systems. The added richness of the network setting raises new questions and produces a greater need for algorithmic solutions. A simple network with two service centers is described in Section 2. This is used to illustrate the general properties that are considered in the succeeding sections; product-form, time reversal, parameter optimization, and the need for algorithmic methods. Section 3 presents results for product-form networks; i.e. those networks in which the steady-state probabilities for the joint occupancies of all the queues factor into a product, with each term in the product giving the queue-size probability for a queue in isolation. Product form greatly simplifies computations, so these networks have been of particular interest. Approximations and bounds for nonproduct-form networks are given in Section 4. Section 5 concerns optimization problems. For example, how should jobs be routed and how should a fixed amount of storage space be allocated among several service centers?
Inventory theory is the most highly developed family of optimized structured operations research/ management science models. Evan Porteus begins his description of this area with terminology and a brief treatment of the EOQ (economic order quantity) model that has influenced the development of the theory. Section 3 treats variants of the 'newsvendor' model, namely singleperiod inventory models that balance the costs of excess supply against the costs of unsatisfied demand. Dynamic versions of the newsvendor model often yield an optimal base stock inventory level; these models are examined in Section 4. Augmenting these dynamic models with convex costs, such as smoothing costs, is discussed in Section 5. Inserting a setup cost or other concave element in a dynamic model often leads to the optimality of an (s, S) policy as discussed in Section 6. The chapter ends with an indication of the rich variety of other kinds of models that have been treated in stochastic inventory theory.
Queueing theory is more descriptive than normative, inventory theory is the reverse, and reliability-maintainability strikes a happy medium. In Chapter 13, Moshe Shaked and George Shanthikumar describe the operating characteristics of stochastic reliability models and the kinds of policies that optimize such models. They begin with a description of reliability systems whose details range from course (little detail) to fine (much detail) and they list the most important measures of effectiveness in such systems. Section 5 concerns various notions of aging, particularly monotone hazard rates and Section 6 shows how a model's notion of aging influences an optimal replacement policy. Section 6 concerns systems with multiple components and shows that the hazard rate can be used to describe the probabilistic dependence of lives of different components. The basic tool is the multivariate conditional hazard rate function. The ideas in Section 7 are applied in Section 8 to the analysis of systems with repairable components. Section 9 discusses various extensions of statistical notions of aging to systems with multiple components having 'interdependent lifetimes. The last section describes two areas of statistical inference in reliability theory.
D.P. Heyman and MJ. Sobel
Complete chapters on ScienceDirect
[Description and order information]
