| |

| |

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 | |