1 Introduction to Probability Theory 1 1.1　Introduction　1 1.2　Sample Space and Events　1 1.3　Probabilities Defined on Events　3 1.4　Conditional Probabilities　6 1.5　Independent Events　9 1.6　Bayes’ Formula　11 1.7　Probability Is a Continuous Event Function　14 Exercises　15 References　21 2　Random Variables　23 2.1　Random Variables　23 2.2　Discrete Random Variables　27 2.2.1　The Bernoulli Random Variable　28 2.2.2　The Binomial Random Variable　28 2.2.3　The Geometric Random Variable　30 2.2.4　The Poisson Random Variable　31 2.3　Continuous Random Variables　32 2.3.1　The Uniform Random Variable　33 2.3.2　Exponential Random Variables　35 2.3.3　Gamma Random Variables　35 2.3.4　Normal Random Variables　35 2.4　Expectation of a Random Variable　37 2.4.1　The Discrete Case　37 2.4.2　The Continuous Case　39 2.4.3　Expectation of a Function of a Random Variable　41 2.5　Jointly Distributed Random Variables　44 2.5.1　Joint Distribution Functions　44 2.5.2　Independent Random Variables　49 2.5.3　Covariance and Variance of Sums of Random Variables 50 Properties of Covariance　52 2.5.4　Joint Probability Distribution of Functions of Random Variables　59 2.6　Moment Generating Functions　62 2.6.1　The Joint Distribution of the Sample Mean and Sample Variance from a Normal Population　70 2.7　Limit Theorems　73 2.8　Proof of the Strong Law of Large Numbers　79 2.9　Stochastic Processes　84 Exercises　86 References　99 3　Conditional Probability and Conditional Expectation　101 3.1　Introduction　101 3.2　The Discrete Case　101 3.3　The Continuous Case　104 3.4　Computing Expectations by Conditioning　108 3.4.1　Computing Variances by Conditioning　120 3.5　Computing Probabilities by Conditioning　124 3.6　Some Applications　143 3.6.1　A List Model　143 3.6.2　A Random Graph　145 3.6.3　Uniform Priors, Polya’s Urn Model, and Bose–Einstein Statistics　152 3.6.4　Mean Time for Patterns　156 3.6.5　The k-Record Values of Discrete Random Variables　159 3.6.6　Left Skip Free Random Walks　162 3.7　An Identity for Compound Random Variables　168 3.7.1　Poisson Compounding Distribution　171 3.7.2　Binomial Compounding Distribution　172 3.7.3　A Compounding Distribution Related to the Negative Binomial　173 Exercises　174 4　Markov Chains　193 4.1　Introduction　193 4.2　Chapman–Kolmogorov Equations　197 4.3　Classification of States　205 4.4　Long-Run Proportions and Limiting Probabilities　215 4.4.1　Limiting Probabilities　232 4.5　Some Applications　233 4.5.1　The Gambler’s Ruin Problem　233 4.5.2　A Model for Algorithmic Efficiency　237 4.5.3　Using a Random Walk to Analyze a Probabilistic Algorithm for the Satisfiability Problem　239 4.6　Mean Time Spent in Transient States　245 4.7　Branching Processes 2475.2.2 Properties of the Exponential Distribution　295 4.8　Time Reversible Markov Chains　251 4.9　Markov Chain Monte Carlo Methods　261 4.10　Markov Decision Processes　265 4.11　Hidden Markov Chains　269 4.11.1　Predicting the States　273 Exercises　275 References　291 5　The Exponential Distribution and the Poisson Process　293 5.1　Introduction　293 5.2　The Exponential Distribution　293 5.2.1　Definition　293 5.2.2　Properties of the Exponential Distribution　295 5.2.3　Further Properties of the Exponential Distribution　302 5.2.4　Convolutions of Exponential Random Variables　309 5.2.5　The Dirichlet Distribution　313 5.3　The Poisson Process　314 5.3.1　Counting Processes　314 5.3.2　Definition of the Poisson Process　316 5.3.3　Further Properties of Poisson Processes　320 5.3.4　Conditional Distribution of the Arrival Times　326 5.3.5　Estimating Software Reliability　336 5.4　Generalizations of the Poisson Process　339 5.4.1　Nonhomogeneous Poisson Process　339 5.4.2　Compound Poisson Process　346 Examples　of Compound Poisson Processes　346 5.4.3　Conditional or Mixed Poisson Processes　351 5.5　Random Intensity Functions and Hawkes Processes　353 Exercises　357 References　374 6　Continuous-Time Markov Chains　375 6.1　Introduction　375 6.2　Continuous-Time Markov Chains　375 6.3　Birth and Death Processes　377 6.4　The Transition Probability Function Pi j (t)　384 6.5　Limiting Probabilities　394 6.6　Time Reversibility　401 6.7　The Reversed Chain　409 6.8　Uniformization　414 6.9　Computing the Transition Probabilities　418 Exercises　420 References　429 7　Renewal Theory and Its Applications　431 7.1　Introduction　431 7.2　Distribution of N (t)　432 7.3　Limit Theorems and Their Applications　436 7.4　Renewal Reward Processes　450 7.5　Regenerative Processes　461 7.5.1　Alternating Renewal Processes　464 7.6　Semi-Markov Processes　470 7.7　The Inspection Paradox　473 7.8　Computing the Renewal Function　476 7.9　Applications to Patterns　479 7.9.1　Patterns of Discrete Random Variables　479 7.9.2　The Expected Time to a Maximal Run of Distinct Values　486 7.9.3　Increasing Runs of Continuous Random Variables　488 7.10　The Insurance Ruin Problem　489 Exercises　495 References　506 8　Queueing Theory　507 8.1　Introduction　507 8.2　Preliminaries　508 8.2.1　Cost Equations　508 8.2.2　Steady-State Probabilities　509 8.3　Exponential Models　512 8.3.1　A Single-Server Exponential Queueing System　512 8.3.2　A Single-Server Exponential Queueing System Having Finite Capacity　522 8.3.3　Birth and Death Queueing Models　527 8.3.4　A Shoe Shine Shop　534 8.3.5　Queueing Systems with Bulk Service　536 8.4　Network of Queues　540 8.4.1　Open Systems　540 8.4.2　Closed Systems　544 8.5　The System M/G/1　549 8.5.1　Preliminaries: Work and Another Cost Identity　549 8.5.2　Application of Work to M/G/1　550 8.5.3　Busy Periods　552 8.6　Variations on the M/G/1　554 8.6.1　The M/G/1 with Random-Sized Batch Arrivals　554 8.6.2　Priority Queues　555 8.6.3　An M/G/1 Optimization Example　558 8.6.4　The M/G/1 Queue with Server Breakdown　562 8.7　The Model G/M/1　565 8.7.1　The G/M/1 Busy and Idle Periods　569 8.8　A Finite Source Model　570 8.9　Multiserver Queues　573 8.9.1　Erlang’s Loss System　574 8.9.2　The M/M/k Queue　575 8.9.3　The G/M/k Queue　575 8.9.4　The M/G/k Queue　577 Exercises　578 9　Reliability Theory　591 9.1　Introduction　591 9.2　Structure Functions　591 9.2.1　Minimal Path and Minimal Cut Sets　594 9.3　Reliability of Systems of Independent Components　597 9.4　Bounds on the Reliability Function　601 9.4.1　Method of Inclusion and Exclusion　602 9.4.2　Second Method for Obtaining Bounds on r(p)　610 9.5　System Life as a Function of Component Lives　613 9.6　Expected System Lifetime　620 9.6.1　An Upper Bound on the Expected Life of a Parallel System　623 9.7　Systems with Repair　625 9.7.1　A Series Model with Suspended Animation　630 Exercises　632 References　638 10　Brownian Motion and Stationary Processes　639 10.1　Brownian Motion　639 10.2　Hitting Times, Maximum Variable, and the Gambler’s Ruin Problem　643 10.3　Variations on Brownian Motion　644 10.3.1　Brownian Motion with Drift　644 10.3.2　Geometric Brownian Motion　644 10.4　Pricing Stock Options　646 10.4.1　An Example in Options Pricing　646 10.4.2　The Arbitrage Theorem　648 10.4.3　The Black–Scholes Option Pricing Formula　651 10.5　The Maximum of Brownian Motion with Drift　656 10.6　White Noise　661 10.7　Gaussian Processes　663 10.8　Stationary and Weakly Stationary Processes　665 10.9　Harmonic Analysis of Weakly Stationary Processes　670 Exercises　672 References　677 11　Simulation　679 11.1　Introduction　679 11.2　General Techniques for Simulating Continuous Random Variables　683 11.2.1　The Inverse Transformation Method　683 11.2.2　The Rejection Method　684 11.2.3　The Hazard Rate Method　688 11.3　Special Techniques for Simulating Continuous Random Variables　691 11.3.1　The Normal Distribution　691 11.3.2　The Gamma Distribution　694 11.3.3　The Chi-Squared Distribution　695 11.3.4　The Beta (n, m) Distribution　695 11.3.5　The Exponential Distribution—The Von Neumann Algorithm　696 11.4　Simulating from Discrete Distributions　698 11.4.1　The Alias Method　701 11.5　Stochastic Processes　705 11.5.1　Simulating a Nonhomogeneous Poisson Process　706 11.5.2　Simulating a Two-Dimensional Poisson Process　712 11.6　Variance Reduction Techniques　715 11.6.1　Use of Antithetic Variables　716 11.6.2　Variance Reduction by Conditioning　719 11.6.3　Control Variates　723 11.6.4　Importance Sampling　725 11.7　Determining the Number of Runs　730 11.8　Generating from the Stationary Distribution of a Markov Chain　731 11.8.1　Coupling from the Past　731 11.8.2　Another Approach　733 Exercises　734 References　741 12　Coupling　743 12.1　A Brief Introduction　743 12.2　Coupling and Stochastic Order Relations　743 12.3　Stochastic Ordering of Stochastic Processes　746 12.4　Maximum Couplings, Total Variation Distance, and the Coupling Identity　749 12.5　Applications of the Coupling Identity　752 12.5.1　Applications to Markov Chains　752 12.6　Coupling and Stochastic Optimization　758 12.7　Chen–Stein Poisson Approximation Bounds　762 Exercises　769 Solutions　to Starred Exercises　773 Index　817