List of Contents

1 Events and their probabilities 1

• 1.1 Introduction 1
• 1.2 Events as sets 1
• 1.3 Probability 4
• 1.4 Conditional probability 8
• 1.5 Independence 13
• 1.6 Completeness and product spaces 14
• 1.7 Worked examples 16
• 1.8 Problems 21

2 Random variables and their distributions 26

• 2.1 Random variables 26
• 2.2 The law of averages 30
• 2.3 Discrete and continuous variables 33
• 2.4 Worked examples 35
• 2.5 Random vectors 38
• 2.6 Monte Carlo simulation 41
• 2.7 Problems 43

3 Discrete random variables 46

• 3.1 Probability mass functions 46
• 3.2 Independence 48
• 3.3 Expectation 50
• 3.4 Indicators and matching 56
• 3.5 Examples of discrete variables 60
• 3.6 Dependence 62
• 3.7 Conditional distributions and conditional expectation 67
• 3.8 Sums of random variables 70
• 3.9 Simple random walk 71
• 3.10 Random walk: counting sample paths 75
• 3.11 Problems 83

4 Continuous random variables 89

• 4.1 Probability density functions 89
• 4.2 Independence 91
• 4.3 Expectation 93
• 4.4 Examples of continuous variables 95
• 4.5 Dependence 98
• 4.6 Conditional distributions and conditional expectation 104
• 4.7 Functions of random variables 107
• 4.8 Sums of random variables 113
• 4.9 Multivariate normal distribution 115
• 4.10 Distributions arising from the normal distribution 119
• 4.11 Sampling from a distribution 122
• 4.12 Coupling and Poisson approximation 127
• 4.13 Geometrical probability 133
• 4.14 Problems 140

5 Generating functions and their applications 148

• 5.1 Generating functions 148
• 5.2 Some applications 156
• 5.3 Random walk 162
• 5.4 Branching processes 171
• 5.5 Age-dependent branching processes 175
• 5.6 Expectation revisited 178
• 5.7 Characteristic functions 181
• 5.8 Examples of characteristic functions 186
• 5.9 Inversion and continuity theorems 189
• 5.10 Two limit theorems 193
• 5.11 Large deviations 201
• 5.12 Problems 206

6 Markov chains 213

• 6.1 Markov processes 213
• 6.2 Classification of states 220
• 6.3 Classification of chains 223
• 6.4 Stationary distributions and the limit theorem 227
• 6.5 Reversibility 237
• 6.6 Chains with finitely many states 240
• 6.7 Branching processes revisited 243
• 6.8 Birth processes and the Poisson process 246
• 6.9 Continuous-time Markov chains 256
• 6.10 Uniform semigroups 266
• 6.11 Birth--death processes and imbedding 268
• 6.12 Special processes 274
• 6.13 Spatial Poisson processes 281
• 6.14 Markov chain Monte Carlo 291
• 6.15 Problems 296

7 Convergence of random variables 305

• 7.1 Introduction 305
• 7.2 Modes of convergence 308
• 7.3 Some ancillary results 318
• 7.4 Laws of large numbers 325
• 7.5 The strong law 329
• 7.6 The law of the iterated logarithm 332
• 7.7 Martingales 333
• 7.8 Martingale convergence theorem 338
• 7.9 Prediction and conditional expectation 343
• 7.10 Uniform integrability 350
• 7.11 Problems 354

8 Random processes 360

• 8.1 Introduction 360
• 8.2 Stationary processes 361
• 8.3 Renewal processes 365
• 8.4 Queues 367
• 8.5 The Wiener process 370
• 8.6 Existence of processes 371
• 8.7 Problems 373

9 Stationary processes 375

• 9.1 Introduction 375
• 9.2 Linear prediction 377
• 9.3 Autocovariances and spectra 380
• 9.4 Stochastic integration and the spectral representation 387
• 9.5 The ergodic theorem 393
• 9.6 Gaussian processes 405
• 9.7 Problems 409

10 Renewals 412

• 10.1 The renewal equation 412
• 10.2 Limit theorems 417
• 10.3 Excess life 421
• 10.4 Applications 423
• 10.5 Renewal--reward processes 431
• 10.6 Problems 437

11 Queues 440

• 11.1 Single-server queues 440
• 11.2 M/M/1 442
• 11.3 M/G/1 445
• 11.4 G/M/1 451
• 11.5 G/G/1 455
• 11.6 Heavy traffic 462
• 11.7 Networks of queues 462
• 11.8 Problems 468

12 Martingales 471

• 12.1 Introduction 471
• 12.2 Martingale differences and Hoeffding's inequality 476
• 12.3 Crossings and convergence 481
• 12.4 Stopping times 487
• 12.5 Optional stopping 491
• 12.6 The maximal inequality 496
• 12.7 Backward martingales and continuous-time martingales 499
• 12.8 Some examples 503
• 12.9 Problems 508

13 Diffusion processes 513

• 13.1 Introduction 513
• 13.2 Brownian motion 514
• 13.3 Diffusion processes 516
• 13.4 First passage times 525
• 13.5 Barriers 530
• 13.6 Excursions and the Brownian bridge 534
• 13.7 Stochastic calculus 537
• 13.8 The It\^o integral 539
• 13.9 It\^o's formula 544
• 13.10 Option pricing 547
• 13.11 Passage probabilities and potentials 554
• 13.12 Problems 561

Appendix I. Foundations and notation 564

Appendix II. Further reading 569

Appendix III. History and varieties of probability 571

Appendix IV. John Arbuthnot's Preface to Of the laws of chance (1692) 573

Appendix V. Table of distributions 576

Appendix VI. Chronology 578

Bibliography 580

Notation 583

Index 585