Page 1 of 630
Introduction to Probability
Second Edition
Joseph K. Blitzstein and Jessica Hwang
Harvard University and Stanford University
c 2019 by Taylor & Francis Group, LLC
print copies available at https://www.crcpress.com
supplementary materials available at https://stat110.net
Page 2 of 630
To our mothers, Steffi and Min
v
Page 3 of 630
Page 4 of 630
Contents
1 Probability and counting 1
1.1 Why study probability? . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Sample spaces and Pebble World . . . . . . . . . . . . . . . . . . . . 3
1.3 Naive definition of probability . . . . . . . . . . . . . . . . . . . . . 6
1.4 How to count . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Story proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6 Non-naive definition of probability . . . . . . . . . . . . . . . . . . . 21
1.7 Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.8 R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2 Conditional probability 45
2.1 The importance of thinking conditionally . . . . . . . . . . . . . . . 45
2.2 Definition and intuition . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3 Bayes’ rule and the law of total probability . . . . . . . . . . . . . . 52
2.4 Conditional probabilities are probabilities . . . . . . . . . . . . . . . 59
2.5 Independence of events . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.6 Coherency of Bayes’ rule . . . . . . . . . . . . . . . . . . . . . . . . 67
2.7 Conditioning as a problem-solving tool . . . . . . . . . . . . . . . . 68
2.8 Pitfalls and paradoxes . . . . . . . . . . . . . . . . . . . . . . . . . . 74
2.9 Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.10 R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3 Random variables and their distributions 103
3.1 Random variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.2 Distributions and probability mass functions . . . . . . . . . . . . . 106
3.3 Bernoulli and Binomial . . . . . . . . . . . . . . . . . . . . . . . . . 112
3.4 Hypergeometric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
3.5 Discrete Uniform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
3.6 Cumulative distribution functions . . . . . . . . . . . . . . . . . . . 120
3.7 Functions of random variables . . . . . . . . . . . . . . . . . . . . . 123
3.8 Independence of r.v.s . . . . . . . . . . . . . . . . . . . . . . . . . . 129
3.9 Connections between Binomial and Hypergeometric . . . . . . . . . 133
3.10 Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
3.11 R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
3.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
vii
Page 5 of 630
viii Contents
4 Expectation 149
4.1 Definition of expectation . . . . . . . . . . . . . . . . . . . . . . . . 149
4.2 Linearity of expectation . . . . . . . . . . . . . . . . . . . . . . . . . 152
4.3 Geometric and Negative Binomial . . . . . . . . . . . . . . . . . . . 157
4.4 Indicator r.v.s and the fundamental bridge . . . . . . . . . . . . . . 164
4.5 Law of the unconscious statistician (LOTUS) . . . . . . . . . . . . . 170
4.6 Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
4.7 Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
4.8 Connections between Poisson and Binomial . . . . . . . . . . . . . . 181
4.9 *Using probability and expectation to prove existence . . . . . . . . 184
4.10 Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
4.11 R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
5 Continuous random variables 213
5.1 Probability density functions . . . . . . . . . . . . . . . . . . . . . . 213
5.2 Uniform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
5.3 Universality of the Uniform . . . . . . . . . . . . . . . . . . . . . . . 224
5.4 Normal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
5.5 Exponential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
5.6 Poisson processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
5.7 Symmetry of i.i.d. continuous r.v.s . . . . . . . . . . . . . . . . . . . 248
5.8 Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
5.9 R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
5.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
6 Moments 267
6.1 Summaries of a distribution . . . . . . . . . . . . . . . . . . . . . . 267
6.2 Interpreting moments . . . . . . . . . . . . . . . . . . . . . . . . . . 272
6.3 Sample moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
6.4 Moment generating functions . . . . . . . . . . . . . . . . . . . . . . 279
6.5 Generating moments with MGFs . . . . . . . . . . . . . . . . . . . . 283
6.6 Sums of independent r.v.s via MGFs . . . . . . . . . . . . . . . . . . 286
6.7 *Probability generating functions . . . . . . . . . . . . . . . . . . . 287
6.8 Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
6.9 R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
6.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
7 Joint distributions 303
7.1 Joint, marginal, and conditional . . . . . . . . . . . . . . . . . . . . 304
7.2 2D LOTUS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
7.3 Covariance and correlation . . . . . . . . . . . . . . . . . . . . . . . 326
7.4 Multinomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
7.5 Multivariate Normal . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
7.6 Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
Page 6 of 630
Contents ix
7.7 R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
7.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
8 Transformations 367
8.1 Change of variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
8.2 Convolutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
8.3 Beta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
8.4 Gamma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
8.5 Beta-Gamma connections . . . . . . . . . . . . . . . . . . . . . . . . 396
8.6 Order statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
8.7 Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
8.8 R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
8.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
9 Conditional expectation 415
9.1 Conditional expectation given an event . . . . . . . . . . . . . . . . 415
9.2 Conditional expectation given an r.v. . . . . . . . . . . . . . . . . . 424
9.3 Properties of conditional expectation . . . . . . . . . . . . . . . . . 426
9.4 *Geometric interpretation of conditional expectation . . . . . . . . . 431
9.5 Conditional variance . . . . . . . . . . . . . . . . . . . . . . . . . . . 432
9.6 Adam and Eve examples . . . . . . . . . . . . . . . . . . . . . . . . 436
9.7 Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
9.8 R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441
9.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
10 Inequalities and limit theorems 457
10.1 Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458
10.2 Law of large numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 467
10.3 Central limit theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 471
10.4 Chi-Square and Student-t . . . . . . . . . . . . . . . . . . . . . . . . 477
10.5 Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
10.6 R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
10.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
11 Markov chains 497
11.1 Markov property and transition matrix . . . . . . . . . . . . . . . . 497
11.2 Classification of states . . . . . . . . . . . . . . . . . . . . . . . . . . 502
11.3 Stationary distribution . . . . . . . . . . . . . . . . . . . . . . . . . 506
11.4 Reversibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
11.5 Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
11.6 R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521
11.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524
12 Markov chain Monte Carlo 535
12.1 Metropolis-Hastings . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
12.2 Gibbs sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548
Page 7 of 630
x Contents
12.3 Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554
12.4 R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555
12.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
13 Poisson processes 559
13.1 Poisson processes in one dimension . . . . . . . . . . . . . . . . . . 559
13.2 Conditioning, superposition, and thinning . . . . . . . . . . . . . . . 561
13.3 Poisson processes in multiple dimensions . . . . . . . . . . . . . . . 573
13.4 Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575
13.5 R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575
13.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577
A Math 581
A.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581
A.2 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585
A.3 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590
A.4 Difference equations . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
A.5 Differential equations . . . . . . . . . . . . . . . . . . . . . . . . . . 593
A.6 Partial derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594
A.7 Multiple integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594
A.8 Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596
A.9 Pattern recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . 599
A.10 Common sense and checking answers . . . . . . . . . . . . . . . . . 599
B R 601
B.1 Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
B.2 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602
B.3 Math . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602
B.4 Sampling and simulation . . . . . . . . . . . . . . . . . . . . . . . . 603
B.5 Plotting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603
B.6 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603
B.7 Summary statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
B.8 Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
C Table of distributions 605
References 607
Index 609