CONTENTS
CHAPTER 1. PRELIMINARIES
1.1 Probability = 1
1.2 Random Variables = 5
1.3 Expected Value = 7
1.4 Moment Generating, Characteristic Functions, and Laplace Transforms = 11
1.5 Conditional Expectation = 14
1.6 The Exponential Distribution, Lack of Memory, and Hazard Rate Functions = 23
1.7 Limit Theorems = 26
1.8 Stochastic Processes = 26
Problems = 27
Notes and References = 30
CHAPTER 2. THE POISSON PROCESS
2.1 The Poisson Process = 31
2.2 Interarrival and Waiting Time Distributions = 34
2.3 Conditional Distribution of the Arrival Times = 36
2.3.1 The M ／ G ／ I Busy Period = 41
2.4 Nonhomogeneous Poisson Process = 46
2.5 Compound Poisson Process = 48
2.6 Conditional Poisson Process = 49
Problems = 50
Notes and References = 54
CHAPTER 3. RENEWAL THEORY
3.1 Introduction and Preliminaries = 55
3.2 Distribution of N(t) = 56
3.3 Some Limit Theorems = 57
3.3.1 Wald's Equation = 59
3.3.2 Back to Renewal Theory = 60
3.4 The Key Renewal Theorem and Applications = 63
3.4.1 Alternating Renewal Processes = 66
3.4.2 Limiting Mean Excess and Expansion of m(t) = 70
3.4.3 Age-Dependent Branching Processes = 72
3.5 Delayed Renewal Processes = 74
3.6 Renewal Reward Processes = 77
3.6.1 A Queueing Application = 82
3.7 Regenerative Processes = 84
3.7.1 The Symmetric Random Walk and the Arc Sine Laws = 85
3.8 Stationary Point Processes = 90
Problems = 93
Notes and References = 98
CHAPTER 4. MARKOV CHAINS
4.1 Introduction and Examples = 100
4.2 Chapman-Kolmogorov Equations and Classification of States = 103
4.3 Limit Theorems = 107
4.4 Transitions Among Chasses and the Gambler's Ruin Problem = 114
4.5 Branching Processes = 116
4.6 Applications of Markov Chains = 118
4.6.1 A Markov Chain Model of Algorithmic Efficiency = 118
4.6.2 An Application to Runs-A Markov Chain with a Continuous State Space = 120
4.6.3 List Ordering Rules-Optimality of the Transposition Rule = 122
4.7 Time-Reversible Markov Chains = 126
4.8 Semi-Markov Processes = 130
Problems = 134
Notes and References = 140
CHAPTER 5. CONTINUOUS-TIME MARKOV CHAINS
5.1 Introduction = 141
5.2 Continuous-Time Markov Chains = 141
5.3 Birth and Death Processes = 143
5.4 The Kolmogorov Differential Equations = 147
5.5 Limiting Probabilities = 152
5.6 Time Reversibility = 156
5.6.1 Tandem Queues = 158
5.6.2 A Stochastic Population Model = 160
5.7 Applications of the Reversed Chain to Queueing Theory = 164
5.7.1 Network of Queues = 165
5.7.2 The Erlang Loss Formula = 168
5.7.3 The M ／ G ／ I Shared Processor System = 171
5.8 Uniformization = 174
Problems = 178
Notes and References = 182
CHAPTER 6. BROWNIAN MOTION AND OTHER MARKOV PROCESSES
6.1 Introduction and Preliminaries = 184
6.2 Hitting Times, Maximum Variable, and Arc Sine Laws = 190
6.3 Variations on Brownian Motion = 192
6.3.1 Brownian Motion Absorbed at a Value = 192
6.3.2 Brownian Motion Reflected at the Origin = 193
6.3.3 Geometric Brownian Motion = 193
6.3.4 Integrated Brownian Motion = 194
6.4 Brownian Motion with Drift = 196
6.5 Backward and Forward Diffusion Equations = 204
6.6 Applications of the Kolmogorov Equations to Obtaining Limiting Distributions = 205
6.6.1 Semi-Markov Processes = 205
6.6.2 The M ／ G ／ I Queue = 207
6.6.3 A Ruin Problem in Risk Theory = 211
6.7 A Markov Shot Noise Process = 212
6.8 Stationary Processes = 214
Problems = 217
Notes and References = 220
CHAPTER 7. RANDOM WALKS AND MARTINGALES
Introduction = 221
7.1 Duality in Random Walks = 222
7.1.1 Some Remarks Concerning Exchangeable Random Variables = 226
7.2 Martingales = 228
7.3 Back to Random Walks = 233
7.4 Applications to G ／ G ／ I Queues and Ruin Problems = 236
7.4.1 The G ／ G ／ I Queues = 236
7.4.2 A Ruin Problem = 238
7.5 Blackwell's Theorem on the Line = 239
7.6 More on Martingales = 242
Problems = 246
Notes and References = 249
CHAPTER 8. STOCHASTIC ORDER RELATIONS
Introduction = 251
8.1 Stochastically Larger = 251
8.2 Coupling = 255
8.2.1 Stochastic Monotonicity Properties of Birth and Death Processes = 257
8.2.2 Exponential Convergence in Markov Chains = 258
8.3 Hazard Rate Ordering and Applications to Counting Processes = 260
8.4 Likelihood Ratio Ordering = 266
8.5 Stochastically More Variable = 270
8.6 Applications of Variability Orderings = 273
8.6.1 Comparison of G ／ G ／ I Queues = 274
8.6.2 A Renewal Process Application = 275
8.6.3 A Branching Process Application = 277
Problems = 279
Notes and References = 283
ANSWERS AND SOLUTIONS TO SELECTED PROBLEMS = 285
INDEX = 307
