CHAPTER 1．PRELIMINARIES：DISCRETE INDEX SETS AND/OR DISCRETE STATE SPACES 1
1.1．Non-negative integer valued random variables 1
1.2．Convolution 5
1.3．Generating functions 7
1.3.1．Differentiation of generating functions 9
1.3.2．Generating functions and moments 10
1.3.3．Generating functions and convolution 12
1.3.4．Generating functions,compounding and random sums 15
1.4．The simple branching process 18
1.5．Limit distributions and the continuity theorem 27
1.5.1．The law of rare events 30
1.6．The simple random walk 33
1.7．The distribution of a process 40
1.8．Stopping times 44
1.8.1．Wald's identity 47
1.8.2．Splitting an iid sequence at a stopping time 48
Exercises for Chapter 1 51
CHAPTER 2．MARKOV CHAINS 61
2.1．Construction and first properties 61
2.2．Examples 66
2.3．Higher order transition probabilities 72
2.4．Decomposition of the state space 77
2.5．The dissection principle 81
2.6．Transience and recurrence 85
2.7．Periodicity 91
2.8．Solidarity properties 92
2.9．Examples 94
2.10．Canonical decomposition 98
2.11．Absorption probabilities 102
2.12．Invariant measures and stationary distributions 116
2.12.1．Time averages 122
2.13．Limit distributions 126
2.13.1 More on null recurrence and transience 134
2.14．Computation of the stationary distribution 137
2.15．Classification techniques 142
Exercises for Chapter 2 147
CHAPTER 3．RENEWAL THEORY 174
3.1．Basics 174
3.2．Analytic interlude 176
3.2.1．Integration 176
3.2.2．Convolution 178
3.2.3．Laplace transforms 181
3.3．Counting renewals 185
3.4．Renewal reward processes 192
3.5．The renewal equation 197
3.5.1．Risk processes 205
3.6．The Poisson process as a renewal process 211
3.7．Informal discussion of renewal limit theorems;regenerative processes 212
3.7.1 An informal discussion of regenerative processes 215
3.8．Discrete renewal theory 221
3.9．Stationary renewal processes 224
3.10．Blackwell and key renewal theorems 230
3.10.1．Direct Riemann integrability 231
3.10.2．Equivalent forms of the renewal theorems 237
3.10.3．Proof of the renewal theorem 243
3.11．Improper renewal equations 253
3.12．More regenerative processes 259
3.12.1．Definitions and examples 259
3.12.2．The renewal equation and Smith's theorem 263
3.12.3．Queueing examples 269
Exercises for Chapter 3 280
CHAPTER 4．POINT PROCESSES 300
4.1．Basics 300
4.2．The Poisson process 303
4.3．Transforming Poisson processes 308
4.3.1．Max-stable and stable random variables 313
4.4．More transformation theory;marking and thinning 316
4.5．The order statistic property 321
4.6．Variants of the Poisson process 327
4.7．Technical basics 333
4.7.1．The Laplace functional 336
4.8．More on the Poisson process 337
4.9．A general construction of the Poisson process;a simple derivation of the order statistic property 341
4.10．More transformation theory;location dependent thinning 343
4.11．Records 346
Exercises for Chapter 4 349
CHAPTER 5．CONTINUOUS TIME MARKOV CHAINS 367
5.1．Definitions and construction 367
5.2．Stability and explosions 375
5.2.1．The Markov property 377
5.3．Dissection 380
5.3.1．More detail on dissection 380
5.4．The backward equation and the generator matrix 382
5.5．Stationary and limiting distributions 392
5.5.1．More on invariant measures 398
5.6．Laplace transform methods 402
5.7．Calculations and examples 406
5.7.1．Queueing networks 415
5.8．Time dependent solutions 426
5.9．Reversibility 431
5.10．Uniformizability 436
5.11．The linear birth process as a point process 439
Exercises for Chapter 5 446
CHAPTER 6．BROWNIAN MOTION 482
6.1．Introduction 482
6.2．Preliminaries 487
6.3．Construction of Brownian motion 489
6.4．Simple properties of standard Brownian motion 494
6.5．The reflection principle and the distribution of the maximum 497
6.6．The strong independent increment property and reflection 504
6.7．Escape from a strip 508
6.8．Brownian motion with drift 511
6.9．Heavy traffic approximations in queueing theory 514
6.10．The Brownian bridge and the Kolmogorov-Smirnov statistic 524
6.11．Path properties 539
6.12．Quadratic variation 542
6.13．Khintchine's law of the iterated logarithm for Brownian motion 546
Exercises for Chapter 6 551
CHAPTER 7．THE GENERAL RANDOM WALK 559
7.1．Stopping times 559
7.2．Global properties 561
7.3．Prelude to Wiener-Hopf：Probabilistic interpretations of transforms 564
7.4．Dual pairs of stopping times 568
7.5．Wiener-Hopf decompositions 573
7.6．Consequences of the Wiener-Hopf factorization 581
7.7．The maximum of a random walk 587
7.8．Random walks and the G/G/1 queue 591
7.8.1．Exponential right tail 595
7.8.2．Application to G/M/1 queueing model 599
7.8.3．Exponential left tail 602
7.8.4．The M/G/1 queue 605
7.8.5．Queue lengths 607
References 613
Index 617