## Book Description

Probability, Markov Chains, Queues, and Simulation provides a modern and authoritative treatment of the mathematical processes that underlie performance modeling. The detailed explanations of mathematical derivations and numerous illustrative examples make this textbook readily accessible to graduate and advanced undergraduate students taking courses in which stochastic processes play a fundamental role. The textbook is relevant to a wide variety of fields, including computer science, engineering, operations research, statistics, and mathematics.

The textbook looks at the fundamentals of probability theory, from the basic concepts of set-based probability, through probability distributions, to bounds, limit theorems, and the laws of large numbers. Discrete and continuous-time Markov chains are analyzed from a theoretical and computational point of view. Topics include the Chapman-Kolmogorov equations; irreducibility; the potential, fundamental, and reachability matrices; random walk problems; reversibility; renewal processes; and the numerical computation of stationary and transient distributions. The M/M/1 queue and its extensions to more general birth-death processes are analyzed in detail, as are queues with phase-type arrival and service processes. The M/G/1 and G/M/1 queues are solved using embedded Markov chains; the busy period, residual service time, and priority scheduling are treated. Open and closed queueing networks are analyzed. The final part of the book addresses the mathematical basis of simulation.

Each chapter of the textbook concludes with an extensive set of exercises. An instructor's solution manual, in which all exercises are completely worked out, is also available (to professors only).

• Numerous examples illuminate the mathematical theories

• Carefully detailed explanations of mathematical derivations guarantee a valuable pedagogical approach

• Each chapter concludes with an extensive set of exercises

1. Cover
2. Half title
3. Title
5. Dedication
6. Contents
7. Preface and Acknowledgments
8. I Probability
1. 1 Probability
2. 2 Combinatorics—The Art of Counting
3. 3 Random Variables and Distribution Functions
4. 4 Joint and Conditional Distributions
5. 5 Expectations and More
6. 6 Discrete Distribution Functions
7. 7 Continuous Distribution Functions
1. 7.1 The Uniform Distribution
2. 7.2 The Exponential Distribution
3. 7.3 The Normal or Gaussian Distribution
4. 7.4 The Gamma Distribution
5. 7.5 Reliability Modeling and the Weibull Distribution
6. 7.6 Phase-Type Distributions
7. 7.7 Exercises
8. 8 Bounds and Limit Theorems
9. II Markov Chains
1. 9 Discrete- and Continuous-Time Markov Chains
1. 9.1 Stochastic Processes and Markov Chains
2. 9.2 Discrete-Time Markov Chains: Definitions
3. 9.3 The Chapman-Kolmogorov Equations
4. 9.4 Classification of States
5. 9.5 Irreducibility
6. 9.6 The Potential, Fundamental, and Reachability Matrices
7. 9.7 Random Walk Problems
8. 9.8 Probability Distributions
9. 9.9 Reversibility
10. 9.10 Continuous-Time Markov Chains
11. 9.11 Semi-Markov Processes
12. 9.12 Renewal Processes
13. 9.13 Exercises
2. 10 Numerical Solution of Markov Chains
1. 10.1 Introduction
2. 10.2 Direct Methods for Stationary Distributions
3. 10.3 Basic Iterative Methods for Stationary Distributions
4. 10.4 Block Iterative Methods
5. 10.5 Decomposition and Aggregation Methods
6. 10.6 The Matrix Geometric/Analytic Methods for Structured Markov Chains
7. 10.7 Transient Distributions
8. 10.8 Exercises
10. III Queueing Models
1. 11 Elementary Queueing Theory
1. 11.1 Introduction and Basic Definitions
2. 11.2 Birth-Death Processes: The M/M/1 Queue
3. 11.3 General Birth-Death Processes
4. 11.4 Multiserver Systems
5. 11.5 Finite-Capacity Systems—The M/M/1/K Queue
6. 11.6 Multiserver, Finite-Capacity Systems—The M/M/c/K Queue
7. 11.7 Finite-Source Systems—The M/M/c//M Queue
8. 11.8 State-Dependent Service
9. 11.9 Exercises
2. 12 Queues with Phase-Type Laws: Neuts’ Matrix-Geometric Method
3. 13 The z-Transform Approach to Solving Markovian Queues
1. 13.1 The z-Transform
2. 13.2 The Inversion Process
3. 13.3 Solving Markovian Queues using z-Transforms
4. 13.4 Exercises
4. 14 The M/G/1 and G/M/1 Queues
1. 14.1 Introduction to the M/G/1 Queue
2. 14.2 Solution via an Embedded Markov Chain
3. 14.3 Performance Measures for the M/G/1 Queue
4. 14.4 The M/G/1 Residual Time: Remaining Service Time
5. 14.5 The M/G/1 Busy Period
6. 14.6 Priority Scheduling
7. 14.7 The M/G/1/K Queue
8. 14.8 The G/M/1 Queue
9. 14.9 The G/M/1/K Queue
10. 14.10 Exercises
5. 15 Queueing Networks
1. 15.1 Introduction
2. 15.2 Open Queueing Networks
3. 15.3 Closed Queueing Networks
4. 15.4 Mean Value Analysis for Closed Queueing Networks
5. 15.5 The Flow-Equivalent Server Method
6. 15.6 Multiclass Queueing Networks and the BCMP Theorem
7. 15.7 Java Code
8. 15.8 Exercises
11. IV Simulation
1. 16 Some Probabilistic and Deterministic Applications of Random Numbers
2. 17 Uniformly Distributed “Random” Numbers
1. 17.1 Linear Recurrence Methods
2. 17.2 Validating Sequences of Random Numbers
3. 17.3 Exercises
3. 18 Nonuniformly Distributed “Random” Numbers
1. 18.1 The Inverse Transformation Method
2. 18.2 Discrete Random Variates by Mimicry
3. 18.3 The Accept-Reject Method
4. 18.4 The Composition Method
5. 18.5 Normally Distributed Random Numbers
6. 18.6 The Ziggurat Method
7. 18.7 Exercises
4. 19 Implementing Discrete-Event Simulations
1. 19.1 The Structure of a Simulation Model
2. 19.2 Some Common Simulation Examples
3. 19.3 Programming Projects
5. 20 Simulation Measurements and Accuracy
1. 20.1 Sampling
2. 20.2 Simulation and the Independence Criteria
3. 20.3 Variance Reduction Methods
4. 20.4 Exercises
12. Appendix A: The Greek Alphabet
13. Appendix B: Elements of Linear Algebra
1. B.1 Vectors and Matrices
2. B.2 Arithmetic on Matrices
3. B.3 Vector and Matrix Norms
4. B.4 Vector Spaces
5. B.5 Determinants
6. B.6 Systems of Linear Equations
7. B.7 Eigenvalues and Eigenvectors
8. B.8 Eigenproperties of Decomposable, Nearly Decomposable, and Cyclic Stochastic Matrices
14. Bibliography
15. Index

## Product Information

• Title: Probability, Markov Chains, Queues, and Simulation
• Author(s): William J. Stewart
• Release date: July 2009
• Publisher(s): Princeton University Press
• ISBN: 9781400832811