| |
| |
| Preface | |
| |
| |
| |
| Introduction to Probability Theory | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Sample Space and Events | |
| |
| |
| |
| Probabilities Defined on Events | |
| |
| |
| |
| Conditional Probabilities | |
| |
| |
| |
| Independent Events | |
| |
| |
| |
| Bayes' Formula | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| Random Variables | |
| |
| |
| |
| Random Variables | |
| |
| |
| |
| Discrete Random Variables | |
| |
| |
| |
| The Bernoulli Random Variable | |
| |
| |
| |
| The Binomial Random Variable | |
| |
| |
| |
| The Geometric Random Variable | |
| |
| |
| |
| The Poisson Random Variable | |
| |
| |
| |
| Continuous Random Variables | |
| |
| |
| |
| The Uniform Random Variable | |
| |
| |
| |
| Exponential Random Variables | |
| |
| |
| |
| Gamma Random Variables | |
| |
| |
| |
| Normal Random Variables | |
| |
| |
| |
| Expectation of a Random Variable | |
| |
| |
| |
| The Discrete Case | |
| |
| |
| |
| The Continuous Case | |
| |
| |
| |
| Expectation of a Function of a Random Variable | |
| |
| |
| |
| Jointly Distributed Random Variables | |
| |
| |
| |
| Joint Distribution Functions | |
| |
| |
| |
| Independent Random Variables | |
| |
| |
| |
| Covariance and Variance of Sums of Random Variables | |
| |
| |
| |
| Joint Probability Distribution of Functions of Random Variables | |
| |
| |
| |
| Moment Generating Functions | |
| |
| |
| |
| The Joint Distribution of the Sample Mean and Sample Variance from a Normal Population | |
| |
| |
| |
| The Distribution of the Number of Events that Occur | |
| |
| |
| |
| Limit Theorems | |
| |
| |
| |
| Stochastic Processes | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| Conditional Probability and Conditional Expectation | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| The Discrete Case | |
| |
| |
| |
| The Continuous Case | |
| |
| |
| |
| Computing Expectations by Conditioning | |
| |
| |
| |
| Computing Variances by Conditioning | |
| |
| |
| |
| Computing Probabilities by Conditioning | |
| |
| |
| |
| Some Applications | |
| |
| |
| |
| A List Model | |
| |
| |
| |
| A Random Graph | |
| |
| |
| |
| Uniform Priors, Polya's Urn Model, and Bose-Einstein Statistics | |
| |
| |
| |
| Mean Time for Patterns | |
| |
| |
| |
| The k-Record Values of Discrete Random Variables | |
| |
| |
| |
| Left Skip Free Random Walks | |
| |
| |
| |
| An Identity for Compound Random Variables | |
| |
| |
| |
| Poisson Compounding Distribution | |
| |
| |
| |
| Binomial Compounding Distribution | |
| |
| |
| |
| A Compounding Distribution Related to the Negative Binomial | |
| |
| |
| Exercises | |
| |
| |
| |
| Markov Chains | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Chapman-Kolmogorov Equations | |
| |
| |
| |
| Classification of States | |
| |
| |
| |
| Limiting Probabilities | |
| |
| |
| |
| Some Applications | |
| |
| |
| |
| The Gambler's Ruin Problem | |
| |
| |
| |
| A Model for Algorithmic Efficiency | |
| |
| |
| |
| Using a Random Walk to Analyze a Probabilistic Algorithm for the Satisfiability Problem | |
| |
| |
| |
| Mean Time Spent in Transient States | |
| |
| |
| |
| Branching Processes | |
| |
| |
| |
| Time Reversible Markov Chains | |
| |
| |
| |
| Markov Chain Monte Carlo Methods | |
| |
| |
| |
| Markov Decision Processes | |
| |
| |
| |
| Hidden Markov Chains | |
| |
| |
| |
| Predicting the States | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| The Exponential Distribution and the Poisson Process | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| The Exponential Distribution | |
| |
| |
| |
| Definition | |
| |
| |
| |
| Properties of the Exponential Distribution | |
| |
| |
| |
| Further Properties of the Exponential Distribution | |
| |
| |
| |
| Convolutions of Exponential Random Variables | |
| |
| |
| |
| The Poisson Process | |
| |
| |
| |
| Counting Processes | |
| |
| |
| |
| Definition of the Poisson Process | |
| |
| |
| |
| Interarrival and Waiting Time Distributions | |
| |
| |
| |
| Further Properties of Poisson Processes | |
| |
| |
| |
| Conditional Distribution of the Arrival Times | |
| |
| |
| |
| Estimating Software Reliability | |
| |
| |
| |
| Generalizations of the Poisson Process | |
| |
| |
| |
| Nonhomogeneous Poisson Process | |
| |
| |
| |
| Compound Poisson Process | |
| |
| |
| |
| Conditional or Mixed Poisson Processes | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| Continuous-Time Markov Chains | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Continuous-Time Markov Chains | |
| |
| |
| |
| Birth and Death Processes | |
| |
| |
| |
| The Transition Probability Function P<sub>ij</sub>(t) | |
| |
| |
| |
| Limiting Probabilities | |
| |
| |
| |
| Time Reversibility | |
| |
| |
| |
| Uniformization | |
| |
| |
| |
| Computing the Transition Probabilities | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| Renewal Theory and Its Applications | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Distribution of N(t) | |
| |
| |
| |
| Limit Theorems and Their Applications | |
| |
| |
| |
| Renewal Reward Processes | |
| |
| |
| |
| Regenerative Processes | |
| |
| |
| |
| Alternating Renewal Processes | |
| |
| |
| |
| Semi-Markov Processes | |
| |
| |
| |
| The Inspection Paradox | |
| |
| |
| |
| Computing the Renewal Function | |
| |
| |
| |
| Applications to Patterns | |
| |
| |
| |
| Patterns of Discrete Random Variables | |
| |
| |
| |
| The Expected Time to a Maximal Run of Distinct Values | |
| |
| |
| |
| Increasing Runs of Continuous Random Variables | |
| |
| |
| |
| The Insurance Ruin Problem | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| Queueing Theory | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Preliminaries | |
| |
| |
| |
| Cost Equations | |
| |
| |
| |
| Steady-State Probabilities | |
| |
| |
| |
| Exponential Models | |
| |
| |
| |
| A Single-Server Exponential Queueing System | |
| |
| |
| |
| A Single-Server Exponential Queueing System Having Finite Capacity | |
| |
| |
| |
| Birth and Death Queueing Models | |
| |
| |
| |
| A Shoe Shine Shop | |
| |
| |
| |
| A Queueing System with Bulk Service | |
| |
| |
| |
| Network of Queues | |
| |
| |
| |
| Open Systems | |
| |
| |
| |
| Closed Systems | |
| |
| |
| |
| The System M/G/1 | |
| |
| |
| |
| Preliminaries: Work and Another Cost Identity | |
| |
| |
| |
| Application of Work to M/G/1 | |
| |
| |
| |
| Busy Periods | |
| |
| |
| |
| Variations on the M/G/1 | |
| |
| |
| |
| The M/G/1 with Random-Sized Batch Arrivals | |
| |
| |
| |
| Priority Queues | |
| |
| |
| |
| An M/G/1 Optimization Example | |
| |
| |
| |
| The M/G/1 Queue with Server Breakdown | |
| |
| |
| |
| The Model G/M/1 | |
| |
| |
| |
| The G/M/1 Busy and Idle Periods | |
| |
| |
| |
| A Finite Source Model | |
| |
| |
| |
| Multiserver Queues | |
| |
| |
| |
| Erlang's Loss System | |
| |
| |
| |
| The M/M/k Queue | |
| |
| |
| |
| The G/M/k Queue | |
| |
| |
| |
| The M/G/k Queue | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| Reliability Theory | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Structure Functions | |
| |
| |
| |
| Minimal Path and Minimal Cut Sets | |
| |
| |
| |
| Reliability of Systems of Independent Components | |
| |
| |
| |
| Bounds on the Reliability Function | |
| |
| |
| |
| Method of Inclusion and Exclusion | |
| |
| |
| |
| Second Method for Obtaining Bounds on r(p) | |
| |
| |
| |
| System Life as a Function of Component Lives | |
| |
| |
| |
| Expected System Lifetime | |
| |
| |
| |
| An Upper Bound on the Expected Life of a Parallel System | |
| |
| |
| |
| Systems with Repair | |
| |
| |
| |
| A Series Model with Suspended Animation | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| Brownian Motion and Stationary Processes | |
| |
| |
| |
| Brownian Motion | |
| |
| |
| |
| Hitting Times, Maximum Variable, and the Gambler's Ruin Problem | |
| |
| |
| |
| Variations on Brownian Motion | |
| |
| |
| |
| Brownian Motion with Drift | |
| |
| |
| |
| Geometric Brownian Motion | |
| |
| |
| |
| Pricing Stock Options | |
| |
| |
| |
| An Example in Options Pricing | |
| |
| |
| |
| The Arbitrage Theorem | |
| |
| |
| |
| The Black-Scholes Option Pricing Formula | |
| |
| |
| |
| White Noise | |
| |
| |
| |
| Gaussian Processes | |
| |
| |
| |
| Stationary and Weakly Stationary Processes | |
| |
| |
| |
| Harmonic Analysis of Weakly Stationary Processes | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| Simulation | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| General Techniques for Simulating Continuous Random Variables | |
| |
| |
| |
| The Inverse Transformation Method | |
| |
| |
| |
| The Rejection Method | |
| |
| |
| |
| The Hazard Rate Method | |
| |
| |
| |
| Special Techniques for Simulating Continuous Random Variables | |
| |
| |
| |
| The Normal Distribution | |
| |
| |
| |
| The Gamma Distribution | |
| |
| |
| |
| The Chi-Squared Distribution | |
| |
| |
| |
| The Beta (n, m) Distribution | |
| |
| |
| |
| The Exponential Distribution-The Von Neumann Algorithm | |
| |
| |
| |
| Simulating from Discrete Distributions | |
| |
| |
| |
| The Alias Method | |
| |
| |
| |
| Stochastic Processes | |
| |
| |
| |
| Simulating a Nonhomogeneous Poisson Process | |
| |
| |
| |
| Simulating a Two-Dimensional Poisson Process | |
| |
| |
| |
| Variance Reduction Techniques | |
| |
| |
| |
| Use of Antithetic Variables | |
| |
| |
| |
| Variance Reduction by Conditioning | |
| |
| |
| |
| Control Variates | |
| |
| |
| |
| Importance Sampling | |
| |
| |
| |
| Determining the Number of Runs | |
| |
| |
| |
| Generating from the Stationary Distribution of a Markov Chain | |
| |
| |
| |
| Coupling from the Past | |
| |
| |
| |
| Another Approach | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| Appendix: Solutions to Starred Exercises | |
| |
| |
| Index | |