Preface xiii
Acknowledgments xvii
Introduction xix
1 First Principles 1
1.1 Random Experiment, Sample Space, Event 1
1.2 What Is a Probability? 3
1.3 Probability Function 4
1.4 Properties of Probabilities 7
1.5 Equally Likely Outcomes 11
1.6 Counting I 12
1.6.1 Permutations 13
1.7 Counting II 16
1.7.1 Combinations and Binomial Coefficients 17
1.8 Problem-Solving Strategies: Complements and
Inclusion¢"Exclusion 26
1.9 A First Look at Simulation 29
1.10 Summary 34
Exercises 36
2 Conditional Probability and Independence 45
2.1 Conditional Probability 45
2.2 New Information Changes the Sample Space 50
2.3 Finding P (A and B) 51
2.3.1 Birthday Problem 56
2.4 Conditioning and the Law of Total Probability 60
2.5 Bayes Formula and Inverting a Conditional Probability 67
2.6 Independence and Dependence 72
2.7 Product Spaces 80
2.8 Summary 82
Exercises 83
3 Introduction to Discrete Random Variables 93
3.1 Random Variables 93
3.2 Independent Random Variables 97
3.3 Bernoulli Sequences 99
3.4 Binomial Distribution 101
3.5 Poisson Distribution 108
3.5.1 Poisson Approximation of Binomial Distribution 113
3.5.2 Poisson as Limit of Binomial Probabilitie; 115
3.6 Summary 116
Exercises 118
4 Expectation and More with Discrete Random Variables 125
4.1 Expectation 127
4.2 Functions of Random Variables 130
4.3 Joint Distributions 134
4.4 Independent Random Variables 139
4.4.1 Sums of Independent Random Variables 142
4.5 Linearity of Expectation 144
4.6 Variance and Standard Deviation 149
4.7 Covariance and Correlation 158
4.8 Conditional Distribution 165
4.8.1 Introduction to Conditional Expectation 168
4.9 Properties of Covariance and Correlation 171
4.10 Expectation of a Function of a Random Variable 173
4.11 Summary 174
Exercises 176
5 More Discrete Distributions and Their Relationships 185
5.1 Geometric Distribution 185
5.1.1 Memorylessness 188
5.1.2 Coupon Collecting and Tiger Counting 189
5.2 Moment-Generating Functions 193
5.3 Negative Binomial¢"Up from the Geometric 196
5.4 Hypergeometric¢"Sampling Without Replacement 202
5.5 From Binomial to Multinomial 207
5.6 Benford¢s Law 213
5.7 Summary 216
Exercises 218
6 Continuous Probability 227
6.1 Probability Density Function 229
6.2 Cumulative Distribution Function 233
6.3 Expectation and Variance 237
6.4 Uniform Distribution 239
6.5 Exponential Distribution 242
6.5.1 Memorylessness 243
6.6 Joint Distributions 247
6.7 Independence 256
6.7.1 Accept¢"Reject Method 258
6.8 Covariance, Correlation 262
6.9 Summary 264
Exercises 266
7 Continuous Distributions 273
7.1 Normal Distribution 273
7.1.1 Standard Normal Distribution 276
7.1.2 Normal Approximation of Binomial Distribution 278
7.1.3 Quantiles 282
7.1.4 Sums of Independent Normals 285
7.2 Gamma Distribution 288
7.2.1 Probability as a Technique of Integration 292
7.3 Poisson Process 294
7.4 Beta Distribution 302
7.5 Pareto Distribution 305
7.6 Summary 308
Exercises 311
8 Densities of Functions of Random Variables 319
8.1 Densities via CDFs 320
8.1.1 Simulating a Continuous Random Variable 326
8.1.2 Method of Transformations 329
8.2 Maximums, Minimums, and Order Statistics 330
8.3 Convolution 335
8.4 Geometric Probability 338
8.5 Transformations of Two Random Variables 344
8.6 Summary 348
Exercises 349
9 Conditional Distribution, Expectation, and Variance 357
Introduction 357
9.1 Conditional Distributions 358
9.2 Discrete and Continuous: Mixing it Up 364
9.3 Conditional Expectation 369
9.3.1 From Function to Random Variable 371
9.3.2 Random Sum of Random Variables 378
9.4 Computing Probabilities by Conditioning 378
9.5 Conditional Variance 382
9.6 Bivariate Normal Distribution 387
9.7 Summary 396
Exercises 398
10 LIMITS 407
10.1 Weak Law of Large Numbers 409
10.1.1 Markov and Chebyshev Inequalities 411
10.2 Strong Law of Large Numbers 415
10.3 Method of Moments 421
10.4 Monte Carlo Integration 424
10.5 Central Limit Theorem 428
10.5.1 Central Limit Theorem and Monte Carlo 436
10.6 A Proof of the Central Limit Theorem 437
10.7 Summary 439
Exercises 440
11 Beyond Random Walks and Markov Chains 447
11.1 Random Walk on Graphs 447
11.1.1 Long-Term Behavior 451
11.2 Random Walks on Weighted Graphs and Markov Chains 455
11.2.1 Stationary Distribution 458
11.3 From Markov Chain to Markov Chain Monte Carlo 462
11.4 Summary 474
Exercises 476
Appendix A Probability Distributions in R 481
Appendix B Summary of Probability Distributions 483
Appendix C Mathematical Reminders 487
Appendix D Working with Joint Distributions 489
Solutions 497
References 511
Index 515
