Adventures in Stochastic Processes

Table of Contents......Page 6
Preface......Page 10
1.1 Non-negative integer valued random variables......Page 14
1.2 Convolution......Page 18
1.3 Generating functions......Page 20
1.3.1 Differentiation of generating functions......Page 22
1.3.2 Generating functions and moments......Page 23
1.3.3 Generating functions and convolution......Page 25
1.3.4 Generating functions, compounding and random sums......Page 28
1.4 The simple branching process......Page 31
1.5 Limit distributions and the continuity theorem......Page 40
1.5.1 The law of rare events......Page 43
1.6 The simple random walk......Page 46
1.7 The distribution of a process*......Page 53
1.8 Stopping times*......Page 57
1.8.1 Wald\'s identity......Page 60
1.8.2 Splitting an iid sequence at a stopping time*......Page 61
Exercises for Chapter 1......Page 64
2 Markov Chains......Page 73
2.1 Construction and first properties......Page 74
2.2 Examples......Page 79
2.3 Higher order transition probabilities......Page 85
2.4 Decomposition of the state space......Page 90
2.5 The dissection principle......Page 94
2.6 Transience and recurrence......Page 98
2.7 Periodicity......Page 104
2.8 Solidarity properties......Page 105
2.9 Examples......Page 107
2.10 Canonical decomposition......Page 111
2.11 Absorption probabilities......Page 115
2.12 Invariant measures and stationary distributions......Page 129
2.12.1 Time averages......Page 135
2.13 Limit distributions......Page 139
2.13.1 More on null recurrence and transience*......Page 147
2.14 Computation of the stationary distribution......Page 150
2.15 Classification techniques......Page 155
Exercises for Chapter 2......Page 160
3.1 Basics......Page 187
3.2.1 Integration......Page 189
3.2.2 Convolution......Page 191
3.2.3 Laplace transforms......Page 194
3.3 Counting renewals......Page 198
3.4 Renewal reward processes......Page 205
3.5 The renewal equation......Page 210
3.5.1 Risk processes*......Page 218
3.6 The Poisson process as a renewal process......Page 224
3.7 Informal discussion of renewal limit theorems; regenerative processes......Page 225
3.7.1 An informal discussion of regenerative processes......Page 228
3.8 Discrete renewal theory......Page 234
3.9 Stationary renewal processes*......Page 237
3.10 Blackwell and key renewal theorems*......Page 243
3.10.1 Direct Riemann integrability*......Page 244
3.10.2 Equivalent forms of the renewal theorems*......Page 250
3.10.3 Proof of the renewal theorem*......Page 256
3.11 Improper renewal equations......Page 266
3.12.1 Definitions and examples*......Page 272
3.12.2 The renewal equation and Smith\'s theorem*......Page 276
3.12.3 Queueing examples......Page 282
Exercises for Chapter 3......Page 293
4.1 Basics......Page 313
4.2 The Poisson process......Page 316
4.3 Transforming Poisson processes......Page 321
4.3.1 Max-stable and stable random variables*......Page 326
4.4 More transformation theory; marking and thinning......Page 329
4.5 The order statistic property......Page 334
4.6 Variants of the Poisson process......Page 340
4.7 Technical basics*......Page 346
4.7.1 The Laplace functional*......Page 349
4.8 More on the Poisson process*......Page 350
4.9 A general construction of the Poisson process; a simple derivation of the order statistic property*......Page 354
4.10 More transformation theory; location dependent thinning*......Page 356
4.11 Records*......Page 359
Exercises for Chapter 4......Page 362
5.1 Definitions and construction......Page 380
5.2 Stability and explosions......Page 388
5.2.1 The Markov property*......Page 390
5.3.1 More detail on dissection*......Page 393
5.4 The backward equation and the generator matrix......Page 395
5.5 Stationary and limiting distributions......Page 405
5.5.1 More on invariant measures*......Page 411
5.6 Laplace transform methods......Page 415
5.7 Calculations and examples......Page 419
5.7.1 Queueing networks......Page 428
5.8 Time dependent solutions*......Page 439
5.9 Reversibility......Page 444
5.10 Uniformizability......Page 449
5.11 The linear birth process as a point process......Page 452
Exercises for Chapter 5......Page 459
6.1 Introduction......Page 495
6.2 Preliminaries......Page 500
6.3 Construction of Brownian motion*......Page 502
6.4 Simple properties of standard Brownian motion......Page 507
6.5 The reflection principle and the distribution of the maximum......Page 510
6.6 The strong independent increment property and reflection*......Page 517
6.7 Escape from a strip......Page 521
6.8 Brownian motion with drift......Page 524
6.9 Heavy traffic approximations in queueing theory......Page 527
6.10 The Brownian bridge and the Kolmogorov-Smirnov statistic......Page 537
6.11 Path properties*......Page 552
6.12 Quadratic variation......Page 555
6.13 Khintchine\'s law of the iterated logarithm for Brownian motion*......Page 559
Exercises for Chapter 6......Page 564
7 The General Random Walk*......Page 571
7.1 Stopping times......Page 572
7.2 Global properties......Page 574
7.3 Prelude to Wiener-Hopf: Probabilistic interpretations of transforms......Page 577
7.4 Dual pairs of stopping times......Page 581
7.5 Wiener-Hopf decompositions......Page 586
7.6 Consequences of the Wiener-Hopf factorization......Page 594
7.7 The maximum of a random walk......Page 600
7.8 Random walks and the G/G/1 queue......Page 604
7.8.1 Exponential right tail......Page 608
7.8.2 Application to G/M/1 queueing model......Page 612
7.8.3 Exponential left tail......Page 615
7.8.4 The M/G/1 queue......Page 618
7.8.5 Queue lengths......Page 620
References......Page 626
Index......Page 630