Modeling and Analysis of Stochastic Systems

Preface

Probabilistic methodology has now become a routine part of graduate education in Operations Research, Computer Science, Business and Public Policy and Engineering. The following three aspects of the methodology are most vital for the students in these disciplines:

  1. Modeling a “real-life” situation with stochastic elements
  2. Analysis of the resulting stochastic model
  3. Implementation of the results of the analysis.

Of course, if the results of step 2 show that the model does not “fit” the “real-life” situation then one needs to modify the model and repeat steps 1 and 2 until a satisfactory solution emerges. Then one proceeds to step 3. As the title suggests, this book emphasizes the first two aspects. The organization and treatment of the topics in the book is dictated by the emphasis on modeling and analysis.

Based on my teaching experience over a dozen years, I have come to the conclusion that it is better (from the students’ point of view) to introduce Markov chains before renewal theory. This way students can immediately start building interesting stochastic models from diverse areas such as manufacturing, genetics, communications, biology, inventory systems, queueing systems, etc. This gives them a feel for the modeling aspect of the subject early in the course. Furthermore, the analysis of Markov chain models uses tools of matrix algebra. The students feel comfortable with these tools since they can use matrix-oriented computer packages to do numerical experimentation. Nothing gives them confidence in the subject better than seeing the analysis produce actual numbers that quantify their intuition.

After they have developed familiarity with Markov chains they are ready for renewal theory. They can now appreciate it because they have seen a lot of models where renewal, renewal-reward, or regenerative processes appear. Also, they are more willing to use the transform tools, which are less familiar to many students. Even here, my personal experience is that Markov regenerative processes offer better computational tools than renewal or regenerative processes.

I am aware that this sequence is contrary to the current approach which starts with renewal theory. Although this approach is intellectually appealing, I have found that it confuses and frustrates students and it does not give them a feel for the modeling aspect of the subject early on.

The emphasis on the analysis of the stochastic models requires careful development of the major useful classes of stochastic processes: discrete and continuous-time Markov chains, renewal processes, regenerative processes, and Markov regenerative processes. This development follows a common pattern: how to compute the transient distribution, the stationary distribution, expected total costs or rewards, and the first passage times. The treatment of the theory of these processes is aimed towards the development of tools of actually “solving” or “analyzing” the stochastic models. Thus, after we express the transient behavior of a discrete-time Markov chain in terms of the powers of its transition probability matrix, we discuss several methods of computing these powers numerically or algebraically. When their long-range behavior is expressed in terms of simultaneous linear equations, a detailed discussion follows on how to solve these. In continuous-time Markov chains the transient behavior is expressed in terms of simultaneous linear differential equations. This is followed by methods of solving these systems. In case of renewal theory, the key tool is the renewal type equation. After developing it, we discuss several methods of solving it. The same theme continues throughout the book at all levels. Thus the book discusses general (analytical and computational) methods of analyzing stochastic models.

The third aspect, namely the implementation, involves actually using the results of steps 1 and 2 to manage the “real-life” situation that we started with. This requires knowledge of statistics (for data collection to estimate the parameters of the model) and organizational science (how to persuade the members of a group to follow a new solution, and how to set up an organizational structure to facilitate it) and hence is beyond the scope of this book, although, admittedly, it is a very important part of the process.

The book is designed for a two-semester graduate course in Stochastic Models for the students of Operations Research, Computer Science, Business and Public Policy analysis, Engineering, etc. Portions of the first six chapters can be covered in the first semester and the last four in the second semester. It is also possible to pick and choose the material from the nine chapters to construct a one-semester senior-level or graduate course. The book assumes that the students have had a course in probability theory (measure theoretic probability is not needed), a course in advanced calculus (familiarity with differential and difference equations, transforms, etc.), a course in matrix algebra, and a general level of mathematical maturity. The appendix contains a brief review of relevant topics in probability.

The best way to learn the material in this book is by solving problems given in exercises. There are several examples included in the text to illustrate the concepts as well as computational tools. Each chapter also has a large number of exercises collected at the end. Where applicable, the exercises have been separated into three classes: modeling, computational and conceptual. Modeling exercises do not involve analysis, but may involve computations to obtain the parameters of the model. A computational exercise may ask for numerical or algebraic answers. Some computational exercises involve model building as well as analysis. A conceptual exercise generally involves proving some theorems, or fine tuning the understanding of the concepts introduced in the chapter, or it may introduce new concepts. Computational exercises are not necessarily easy and conceptual ones are not necessarily hard. The reader may categorize a particular exercise differently. I have found it useful to assign a model building exercise as well as its analysis exercise during my teaching. The students especially should be encouraged to use computers to obtain the solutions numerically.

It is my belief that a student, after mastering the material in this book, will be well equipped to build and analyze useful stochastic models of situations that he or she will face in his or her area of interest.