Barry L. Nelson - Stochastic Modeling: Analysis and Simulation

Stochastic Modeling

Analysis & Simulation

Barry L. Nelson

Northwestern University

DOVER PUBLICATIONS, INC.
Mineola, New York

Copyright

Copyright 1995 by Barry L. Nelson

All rights reserved.

Bibliographical Note

This Dover edition, first published in 2010, is an unabridged republication of the 2002 Dover edition of the work originally published in 1995 by McGraw- Hill, Inc., New York. Readers of this book who would like to receive the solutions to the exercises may request them from the publisher at the following e-mail address: editors@doverpublications.com.

Library of Congress Cataloging-in-Publication Data

Nelson, Barry L.

Stochastic modeling: analysis & simulation / Barry L. Nelson. Dover ed.

p. cm.

Originally published: New York : McGraw-Hill, 1995.

Includes bibliographical references and index.

ISBN-13: 9780-48647770-1

ISBN-10: 0486-477703

1. Stochastic processes. I. Title.

QA274.N46 2010

519.2/3 22

2009048553

Manufactured in the United States by Courier Corporation
47770301
http://www.doverpublications.com

ABOUT THE AUTHOR

Barry L. Nelson is the James N. and Margie M. Krebs Professor in the Department of Industrial Engineering and Management Sciences at Northwestern University, and is Director of the Master of Engineering Management Program there. His teaching and research centers on the design and analysis of computer simulation experiments with applications in manufacturing, services and transportation. His work has been consistently funded by the National Science Foundation, and he has published numerous papers and two books. Dr. Nelson received his B.S. in Mathematics from DePauw University, and his M.S. and Ph.D. in Industrial Engineering from Purdue University. He has served the profession as the Simulation Area Editor of Operations Research and President of the INFORMS (then TIMS) College on Simulation. He has held many positions for the annual Winter Simulation Conference, including Program Chair in 1997, and is currently a member of its Board of Directors representing INFORMS.

To Jeanne for now
To Kyle for the future

CONTENTS

PREFACE

A student who had taken my simulation course called me from work. The students engineering group thought it had a problem for which simulation might be the solution. It was trying to estimate the expected lead time to produce a particular product, and the group had some data on this lead time, but not much. The student wondered if the group could fit a distribution to the data, simulate a larger sample of lead times, and obtain a better estimate of the expected lead time from this larger sample.

To the beginner it may not be obvious what is wrong here. A short answer is that the proposed simulation merely represents what was already observed, so it cannot add anything beyond what was observed. Was the confusion due to poor training of the student? I conjecture (in self-defense), no. In fact, the student understood several important concepts: Real phenomena that are subject to uncertainty (the lead times) can be modeled using the language of probability (a probability distribution). The probability model can be parameterized or fit using real data. Given a probability model, simulation is one way to analyze it (generate samples from the probability model). And the more data you generate, the better your estimates of performance measures (such as the expected lead time) will be. The confusion arose in how these concepts fit together.

I do not think that this confusion is surprising. We tend to expect either too much or too little from first courses in stochastic modeling and simulation. We expect too much when we start with the difficult language and notation of probability and expect students to have any intuition about the kinds of physical processes it describes. We expect too little when we teach a collection of formulas without the mathematical structure that supports them. Sometimes students are misled when we fail to make the important distinction between probability models and the mathematical, simulation, and numerical tools that are available to analyze them. And the dual role of statistics, to parameterize stochastic models and to analyze them when we simulate, is rarely clear.

In this book I attempt to provide a unified presentation of stochastic modeling, analysis and simulation that encompasses all of these aspects. The unifying principle is the discrete-event-sample-path view of stochastic processes, which is the basis for discrete-event simulation, but can also be exploited to make sense of many mathematically tractable processes. A primary goal is to use simulation to help the student develop intuition that will serve as a faithful guide when the mathematics gets tough. Another goal is to ensure that the student has nothing to relearn when progressing to the next level of mathematical rigor in a second course. In other words, I have tried to be correct without being formal. I take as my starting point the cumulative distribution function of a random variable and do not describe the underlying probability space, although one is certainly implied by the way we generate sample paths.

A course from this book should precede, or be the first part of, a course in simulation modeling and analysis that emphasizes the particulars of a simulation language and how to model complex systems. This allows the student to develop some intuition about simulation from simulating the simple processes in this book and also to gain an understanding of the supporting probability structure that is hidden by most simulation languages. The simple Markovian processes emphasized here also provide approximating models for more complex systems, allowing students to obtain rough-cut estimates prior to simulating.

I presume linear algebra, calculus, computer programming and an introductory course in probability and statistics (that typically emphasizes statistics) as prerequisites. The concepts of random variables, probability distributions and sample statistics need to be familiar, but not necessarily comfortable. The only stochastic process about which I assume any knowledge is a sequence of independent and identically distributed random variables. Modeling and analysis tools are introduced as needed, with no extras just for completeness.

The book is designed to be read in chapter sequence, and there are many backward references from later chapters to earlier chapters. However, it is possible to omit certain sections within chapters, especially the more difficult derivations (a euphemism for proofs) that are collected in their own skipable sections, and the Fine Points at the end of most chapters. The chapters are structured around miniature cases that are introduced at the beginning and carried throughout to illustrate key points.

All of the book can be covered in a semester course (45 class hours), with the possible exception of the last chapter, , Topics in Simulation of Stochastic Processes. For those who have the misfortune, as I have, of cramming the material into a one-quarter course (30 class hours), I offer three compromises:

If fundamentals are more important than the particular application of queueing, then cover portions of . These chapters contain simulation, arrival- counting processes, discrete-time Markov chains and continuous-time Markov processes.

to make this possible.

An alternative that puts more of a burden on the instructor, but works well, is to cover if a little in-class support is provided.

In any case it is important not to spend too much time on the probability and statistics review material in . This is prerequisite material given a slightly different slant to match the perspective of the book, and I wrote it assuming students would be required to read it without much in-class discussion. If time is critical, then the random variate generation section, Section 3.3, can also be treated lightly, but it should not be skipped entirely. And no matter what path you follow through the book, I recommend finishing the course with Section 9.2, Rough-Cut Modeling, because quick-and-dirty analysis is one of the most important uses of Markovian models.