Preface to the Second Edition ................................... v
Preface ....................................................... vii
1 Basic Notions of Probability Theory .......................... 1
1.1 Introduction ............................................ 1
1.2 Probability and Expectation ............................. 1
1.3 Conditional Probability ................................. 6
1.4 Independence ............................................ 8
1.5 Distributions, Densities, and Moments ................... 9
1.6 Convolution ............................................ 13
1.7 Random Vectors ......................................... 14
1.8 Multivariate Normal Random Vectors ..................... 17
1.9 Problems ............................................... 20
2 Calculation of Expectations ................................. 25
2.1 Introduction ........................................... 25
2.2 Indicator Random Variables and Symmetry ................ 25
2.3 Conditioning ........................................... 29
2.4 Moment Transforms ...................................... 31
2.5 Tail Probability Methods ............................... 36
2.6 Moments of Reciprocals and Ratios ...................... 38
2.7 Reduction of Degree .................................... 40
2.8 Spherical Surface Measure .............................. 42
2.9 Dirichlet Distribution ................................. 44
2.10 Problems ............................................... 46
3 Convexity, Optimization, and Inequalities ................... 55
3.1 Introduction ........................................... 55
3.2 Convex Functions ....................................... 56
3.3 Minimization of Convex Functions ....................... 61
3.4 The MM Algorithm ....................................... 63
3.5 Moment Inequalities .................................... 66
3.6 Problems ............................................... 70
4 Combinatorics ............................................... 75
4.1 Introduction ........................................... 75
4.2 Bijections ............................................. 75
4.3 Inclusion-Exclusion .................................... 78
4.4 Applications to Order Statistics ....................... 83
4.5 Catalan Numbers ........................................ 84
4.6 Stirling Numbers ....................................... 86
4.7 Application to an Urn Model ............................ 89
4.8 Application to Faà di Bruno's Formula .................. 91
4.9 Pigeonhole Principle ................................... 93
4.10 Problems ............................................... 94
5 Combinatorial Optimization ................................. 103
5.1 Introduction .......................................... 103
5.2 Quick Sort ............................................ 104
5.3 Data Compression and Huffman Coding ................... 106
5.4 Graph Coloring ........................................ 108
5.5 Point Sets with Only Acute Angles ..................... 112
5.6 Sperner's Theorem ..................................... 113
5.7 Subadditivity and Expectations ........................ 114
5.8 Problems .............................................. 118
6 Poisson Processes .......................................... 123
6.1 Introduction .......................................... 123
6.2 The Poisson Distribution .............................. 124
6.3 Characterization and Construction ..................... 124
6.4 One-Dimensional Processes ............................. 127
6.5 Transmission Tomography ............................... 131
6.6 Mathematical Applications ............................. 134
6.7 Transformations ....................................... 136
6.8 Marking and Coloring .................................. 138
6.9 Campbell's Moment Formulas ............................ 139
6.10 Problems .............................................. 142
7 Discrete-Time Markov Chains ................................ 151
7.1 Introduction .......................................... 151
7.2 Definitions and Elementary Theory ..................... 151
7.3 Examples .............................................. 155
7.4 Coupling .............................................. 158
7.5 Convergence Rates for Reversible Chains ............... 163
7.6 Hitting Probabilities and Hitting Times ............... 165
7.7 Markov Chain Monte Carlo .............................. 168
7.7.1 The Hastings-Metropolis Algorithm .............. 168
7.7.2 Gibbs Sampling ................................. 170
7.7.3 Convergence of the Independence Sampler ........ 171
7.8 Simulated Annealing ................................... 173
7.9 Problems .............................................. 174
8 Continuous-Time Markov Chains .............................. 187
8.1 Introduction .......................................... 187
8.2 Finite-Time Transition Probabilities .................. 187
8.3 Derivation of the Backward Equations .................. 189
8.4 Equilibrium Distributions and Reversibility ........... 190
8.5 Examples .............................................. 193
8.6 Calculation of Matrix Exponentials .................... 197
8.7 Kendall's Birth-Death-Immigration Process ............. 200
8.8 Solution of Kendall's Equation ........................ 203
8.9 Problems .............................................. 206
9 Branching Processes ........................................ 217
9.1 Introduction .......................................... 217
9.2 Examples of Branching Processes ....................... 218
9.3 Elementary Theory ..................................... 219
9.4 Extinction ............................................ 221
9.5 Immigration ........................................... 225
9.6 Multitype Branching Processes ......................... 229
9.7 Viral Reproduction in HIV ............................. 231
9.8 Basic Reproduction Numbers ............................ 232
9.9 Problems .............................................. 235
10 Martingales ................................................ 247
10.1 Introduction .......................................... 247
10.2 Definition and Examples ............................... 247
10.3 Martingale Convergence ................................ 251
10.4 Optional Stopping ..................................... 255
10.5 Large Deviation Bounds ................................ 260
10.6 Problems .............................................. 264
11 Diffusion Processes ........................................ 269
11.1 Introduction .......................................... 269
11.2 Basic Definitions and Properties ...................... 270
11.3 Examples Involving Brownian Motion .................... 272
11.4 Other Examples of Diffusion Processes ................. 276
11.5 Process Moments ....................................... 280
11.6 First Passage Problems ................................ 282
11.7 The Reflection Principle .............................. 287
11.8 Equilibrium Distributions ............................. 289
11.9 Problems .............................................. 291
12 Asymptotic Methods ......................................... 297
12.1 Introduction .......................................... 297
12.2 Asymptotic Expansions ................................. 298
12.2.1 Order Relations ................................ 298
12.2.2 Finite Taylor Expansions ....................... 299
12.2.3 Exploitation of Nearby Exact Results ........... 301
12.2.4 Expansions via Integration by Parts ............ 302
12.3 Laplace's Method ...................................... 304
12.3.1 Stirling's Formula ............................. 306
12.3.2 Watson's Lemma ................................. 307
12.4 Euler-Maclaurin Summation Formula ..................... 308
12.5 Asymptotics and Generating Functions .................. 311
12.6 Stochastic Forms of Convergence ....................... 314
12.7 Problems .............................................. 318
13 Numerical Methods .......................................... 327
13.1 Introduction .......................................... 327
13.2 Computation of Equilibrium Distributions .............. 328
13.3 Applications of the Finite Fourier Transform .......... 331
13.4 Counting Jumps in a Markov Chain ...................... 336
13.5 Stochastic Simulation and Intensity Leaping ........... 339
13.6 A Numerical Method for Diffusion Processes ............ 343
13.7 Application to the Wright-Fisher Process .............. 347
13.8 Problems .............................................. 350
14 Poisson Approximation ...................................... 355
14.1 Introduction .......................................... 355
14.2 Applications of the Coupling Method ................... 356
14.3 Applications of the Neighborhood Method ............... 360
14.4 Proof of the Chen-Stein Estimates ..................... 363
14.5 Problems .............................................. 368
15 Number Theory .............................................. 373
15.1 Introduction .......................................... 373
15.2 Zipf's Distribution and Euler's Theorem ............... 374
15.3 Dirichlet Products and Möbius Inversion ............... 378
15.4 Averages of Arithmetic Functions ...................... 382
15.5 The Prime Number Theorem .............................. 386
15.6 Problems .............................................. 391
Appendix: Mathematical Review ................................. 395
A.l Elementary Number Theory ............................... 395
A.2 Nonnegative Matrices ................................... 397
A.3 The Finite Fourier Transform ........................... 401
A.4 The Fourier Transform .................................. 403
A.5 Fourier Series ......................................... 406
A.6 Laplace's Method and Watson's Lemma .................... 410
A.7 A Tauberian Theorem .................................... 412
References ................................................. 415
Index ...................................................... 429
|
