Probability, Markov Chains, Queues, and Simulation

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

Table of Contents

  1. Cover
  2. Half title
  3. Title
  4. Copyright
  5. Dedication
  6. Contents
  7. Preface and Acknowledgments
  8. I Probability
    1. 1 Probability
      1. 1.1 Trials, Sample Spaces, and Events
      2. 1.2 Probability Axioms and Probability Space
      3. 1.3 Conditional Probability
      4. 1.4 Independent Events
      5. 1.5 Law of Total Probability
      6. 1.6 Bayes’ Rule
      7. 1.7 Exercises
    2. 2 Combinatorics—The Art of Counting
      1. 2.1 Permutations
      2. 2.2 Permutations with Replacements
      3. 2.3 Permutations without Replacement
      4. 2.4 Combinations without Replacement
      5. 2.5 Combinations with Replacements
      6. 2.6 Bernoulli (Independent) Trials
      7. 2.7 Exercises
    3. 3 Random Variables and Distribution Functions
      1. 3.1 Discrete and Continuous Random Variables
      2. 3.2 The Probability Mass Function for a Discrete Random Variable
      3. 3.3 The Cumulative Distribution Function
      4. 3.4 The Probability Density Function for a Continuous Random Variable
      5. 3.5 Functions of a Random Variable
      6. 3.6 Conditioned Random Variables
      7. 3.7 Exercises
    4. 4 Joint and Conditional Distributions
      1. 4.1 Joint Distributions
      2. 4.2 Joint Cumulative Distribution Functions
      3. 4.3 Joint Probability Mass Functions
      4. 4.4 Joint Probability Density Functions
      5. 4.5 Conditional Distributions
      6. 4.6 Convolutions and the Sum of Two Random Variables
      7. 4.7 Exercises
    5. 5 Expectations and More
      1. 5.1 Definitions
      2. 5.2 Expectation of Functions and Joint Random Variables
      3. 5.3 Probability Generating Functions for Discrete Random Variables
      4. 5.4 Moment Generating Functions
      5. 5.5 Maxima and Minima of Independent Random Variables
      6. 5.6 Exercises
    6. 6 Discrete Distribution Functions
      1. 6.1 The Discrete Uniform Distribution
      2. 6.2 The Bernoulli Distribution
      3. 6.3 The Binomial Distribution
      4. 6.4 Geometric and Negative Binomial Distributions
      5. 6.5 The Poisson Distribution
      6. 6.6 The Hypergeometric Distribution
      7. 6.7 The Multinomial Distribution
      8. 6.8 Exercises
    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
        1. 7.6.1 The Erlang-2 Distribution
        2. 7.6.2 The Erlang-r Distribution
        3. 7.6.3 The Hypoexponential Distribution
        4. 7.6.4 The Hyperexponential Distribution
        5. 7.6.5 The Coxian Distribution
        6. 7.6.6 General Phase-Type Distributions
        7. 7.6.7 Fitting Phase-Type Distributions to Means and Variances
      7. 7.7 Exercises
    8. 8 Bounds and Limit Theorems
      1. 8.1 The Markov Inequality
      2. 8.2 The Chebychev Inequality
      3. 8.3 The Chernoff Bound
      4. 8.4 The Laws of Large Numbers
      5. 8.5 The Central Limit Theorem
      6. 8.6 Exercises
  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
        1. 9.6.1 Potential and Fundamental Matrices and Mean Time to Absorption
        2. 9.6.2 The Reachability Matrix and Absorption Probabilities
      7. 9.7 Random Walk Problems
      8. 9.8 Probability Distributions
      9. 9.9 Reversibility
      10. 9.10 Continuous-Time Markov Chains
        1. 9.10.1 Transition Probabilities and Transition Rates
        2. 9.10.2 The Chapman-Kolmogorov Equations
        3. 9.10.3 The Embedded Markov Chain and State Properties
        4. 9.10.4 Probability Distributions
        5. 9.10.5 Reversibility
      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
        1. 10.1.1 Setting the Stage
        2. 10.1.2 Stochastic Matrices
        3. 10.1.3 The Effect of Discretization
      2. 10.2 Direct Methods for Stationary Distributions
        1. 10.2.1 Iterative versus Direct Solution Methods
        2. 10.2.2 Gaussian Elimination and LU Factorizations
      3. 10.3 Basic Iterative Methods for Stationary Distributions
        1. 10.3.1 The Power Method
        2. 10.3.2 The Iterative Methods of Jacobi and Gauss–Seidel
        3. 10.3.3 The Method of Successive Overrelaxation
        4. 10.3.4 Data Structures for Large Sparse Matrices
        5. 10.3.5 Initial Approximations, Normalization, and Convergence
      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
        1. 10.6.1 The Quasi-Birth-Death Case
        2. 10.6.2 Block Lower Hessenberg Markov Chains
        3. 10.6.3 Block Upper Hessenberg Markov Chains
      7. 10.7 Transient Distributions
        1. 10.7.1 Matrix Scaling and Powering Methods for Small State Spaces
        2. 10.7.2 The Uniformization Method for Large State Spaces
        3. 10.7.3 Ordinary Differential Equation Solvers
      8. 10.8 Exercises
  10. III Queueing Models
    1. 11 Elementary Queueing Theory
      1. 11.1 Introduction and Basic Definitions
        1. 11.1.1 Arrivals and Service
        2. 11.1.2 Scheduling Disciplines
        3. 11.1.3 Kendall’s Notation
        4. 11.1.4 Graphical Representations of Queues
        5. 11.1.5 Performance Measures—Measures of Effectiveness
        6. 11.1.6 Little’s Law
      2. 11.2 Birth-Death Processes: The M/M/1 Queue
        1. 11.2.1 Description and Steady-State Solution
        2. 11.2.2 Performance Measures
        3. 11.2.3 Transient Behavior
      3. 11.3 General Birth-Death Processes
        1. 11.3.1 Derivation of the State Equations
        2. 11.3.2 Steady-State Solution
      4. 11.4 Multiserver Systems
        1. 11.4.1 The M/M/c Queue
        2. 11.4.2 The M/M/∞ Queue
      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
      1. 12.1 The Erlang-r Service Model—The M/Er/1 Queue
      2. 12.2 The Erlang-r Arrival Model—The Er/M/1 Queue
      3. 12.3 The M/H2/1 and H2/M/1 Queues
      4. 12.4 Automating the Analysis of Single-Server Phase-Type Queues
      5. 12.5 The H2/E3/1 Queue and General Ph/Ph/1 Queues
      6. 12.6 Stability Results for Ph/Ph/1 Queues
      7. 12.7 Performance Measures for Ph/Ph/1 Queues
      8. 12.8 Matlab code for Ph/Ph/1 Queues
      9. 12.9 Exercises
    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
        1. 13.3.1 The z-Transform Procedure
        2. 13.3.2 The M/M/1 Queue Solved using z-Transforms
        3. 13.3.3 The M/M/1 Queue with Arrivals in Pairs
        4. 13.3.4 The M/Er/1 Queue Solved using z-Transforms
        5. 13.3.5 The Er/M/1 Queue Solved using z-Transforms
        6. 13.3.6 Bulk Queueing Systems
      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
        1. 14.3.1 The Pollaczek-Khintchine Mean Value Formula
        2. 14.3.2 The Pollaczek-Khintchine Transform Equations
      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
        1. 14.6.1 M/M/1: Priority Queue with Two Customer Classes
        2. 14.6.2 M/G/1: Nonpreemptive Priority Scheduling
        3. 14.6.3 M/G/1: Preempt-Resume Priority Scheduling
        4. 14.6.4 A Conservation Law and SPTF 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
        1. 15.1.1 Basic Definitions
        2. 15.1.2 The Departure Process—Burke’s Theorem
        3. 15.1.3 Two M/M/1 Queues in Tandem
      2. 15.2 Open Queueing Networks
        1. 15.2.1 Feedforward Networks
        2. 15.2.2 Jackson Networks
        3. 15.2.3 Performance Measures for Jackson Networks
      3. 15.3 Closed Queueing Networks
        1. 15.3.1 Definitions
        2. 15.3.2 Computation of the Normalization Constant: Buzen’s Algorithm
        3. 15.3.3 Performance Measures
      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
        1. 15.6.1 Product-Form Queueing Networks
        2. 15.6.2 The BCMP Theorem for Open, Closed, and Mixed Queueing Networks
      7. 15.7 Java Code
      8. 15.8 Exercises
  11. IV Simulation
    1. 16 Some Probabilistic and Deterministic Applications of Random Numbers
      1. 16.1 Simulating Basic Probability Scenarios
      2. 16.2 Simulating Conditional Probabilities, Means, and Variances
      3. 16.3 The Computation of Definite Integrals
      4. 16.4 Exercises
    2. 17 Uniformly Distributed “Random” Numbers
      1. 17.1 Linear Recurrence Methods
      2. 17.2 Validating Sequences of Random Numbers
        1. 17.2.1 The Chi-Square “Goodness-of-Fit” Test
        2. 17.2.2 The Kolmogorov-Smirnov Test
        3. 17.2.3 “Run” Tests
        4. 17.2.4 The “Gap” Test
        5. 17.2.5 The “Poker” Test
        6. 17.2.6 Statistical Test Suites
      3. 17.3 Exercises
    3. 18 Nonuniformly Distributed “Random” Numbers
      1. 18.1 The Inverse Transformation Method
        1. 18.1.1 The Continuous Uniform Distribution
        2. 18.1.2 “Wedge-Shaped” Density Functions
        3. 18.1.3 “Triangular” Density Functions
        4. 18.1.4 The Exponential Distribution
        5. 18.1.5 The Bernoulli Distribution
        6. 18.1.6 An Arbitrary Discrete Distribution
      2. 18.2 Discrete Random Variates by Mimicry
        1. 18.2.1 The Binomial Distribution
        2. 18.2.2 The Geometric Distribution
        3. 18.2.3 The Poisson Distribution
      3. 18.3 The Accept-Reject Method
        1. 18.3.1 The Lognormal Distribution
      4. 18.4 The Composition Method
        1. 18.4.1 The Erlang-r Distribution
        2. 18.4.2 The Hyperexponential Distribution
        3. 18.4.3 Partitioning of the Density Function
      5. 18.5 Normally Distributed Random Numbers
        1. 18.5.1 Normal Variates via the Central Limit Theorem
        2. 18.5.2 Normal Variates via Accept-Reject and Exponential Bounding Function
        3. 18.5.3 Normal Variates via Polar Coordinates
        4. 18.5.4 Normal Variates via Partitioning of the Density Function
      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
        1. 19.2.1 Simulating the M/M/1 Queue and Some Extensions
        2. 19.2.2 Simulating Closed Networks of Queues
        3. 19.2.3 The Machine Repairman Problem
        4. 19.2.4 Simulating an Inventory Problem
      3. 19.3 Programming Projects
    5. 20 Simulation Measurements and Accuracy
      1. 20.1 Sampling
        1. 20.1.1 Point Estimators
        2. 20.1.2 Interval Estimators/Confidence Intervals
      2. 20.2 Simulation and the Independence Criteria
      3. 20.3 Variance Reduction Methods
        1. 20.3.1 Antithetic Variables
        2. 20.3.2 Control Variables
      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
      1. B.6.1 Gaussian Elimination and LU Decompositions
    7. B.7 Eigenvalues and Eigenvectors
    8. B.8 Eigenproperties of Decomposable, Nearly Decomposable, and Cyclic Stochastic Matrices
      1. B.8.1 Normal Form
      2. B.8.2 Eigenvalues of Decomposable Stochastic Matrices
      3. B.8.3 Eigenvectors of Decomposable Stochastic Matrices
      4. B.8.4 Nearly Decomposable Stochastic Matrices
      5. B.8.5 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