Contents
Preface xi
1 Combinatorial Analysis 1
1.1 Introduction . . . .............................. 1
1.2 The Basic Principle of Counting . . . ................... 1
1.3 Permutations................................. 3
1.4 Combinations . . .............................. 5
1.5 Multinomial Coefficients . . . ....................... 9
1.6 The Number of Integer Solutions of Equations . ............ 12
Summary . .................................. 15
Problems ................................... 16
Theoretical Exercises . . . . . ....................... 18
Self-Test Problems and Exercises . . ................... 20
2 Axioms of Probability 22
2.1 Introduction . . . .............................. 22
2.2 Sample Space and Events.......................... 22
2.3 Axioms of Probability . . . . . ....................... 26
2.4 Some Simple Propositions . . ....................... 29
2.5 Sample Spaces Having Equally Likely Outcomes ............ 33
2.6 Probability as a Continuous Set Function . . . . . ............ 44
2.7 Probability as a Measure of Belief . . ................... 48
Summary . .................................. 49
Problems ................................... 50
Theoretical Exercises . . . . . ....................... 54
Self-Test Problems and Exercises . . ................... 56
3 Conditional Probability and Independence 58
3.1 Introduction . . . .............................. 58
3.2 Conditional Probabilities . . . ....................... 58
3.3 Bayes’s Formula . .............................. 65
3.4 IndependentEvents............................. 79
3.5 P (· |F ) Is a Probability . . . . . ....................... 93
Summary . .................................. 101
Problems ................................... 102
Theoretical Exercises . . . . . ....................... 110
Self-Test Problems and Exercises . . ................... 114
4 Random Variables 117
4.1 Random Variables .............................. 117
4.2 Discrete Random Variables . ....................... 123
4.3 Expected Value ............................... 125
4.4 Expectation of a Function of a Random Variable ............ 128
4.5 Variance . .................................. 132
4.6 The Bernoulli and Binomial Random Variables . ............ 134
4.6.1 Properties of Binomial Random Variables ............ 139
4.6.2 Computing the Binomial Distribution Function . . . . ..... 142
vii
viii Contents
4.7 The Poisson Random Variable ....................... 143
4.7.1 Computing the Poisson Distribution Function . . . . . ..... 154
4.8 Other Discrete Probability Distributions . . . . . ............ 155
4.8.1 The Geometric Random Variable . . . . . ............ 155
4.8.2 The Negative Binomial Random Variable ............ 157
4.8.3 The Hypergeometric Random Variable . ............ 160
4.8.4 TheZeta(orZipf)Distribution.................. 163
4.9 Expected Value of Sums of Random Variables . ............ 164
4.10 Properties of the Cumulative Distribution Function . . . . . ...... 168
Summary . .................................. 170
Problems ................................... 172
Theoretical Exercises . . . . . ....................... 179
Self-Test Problems and Exercises . . ................... 183
5 Continuous Random Variables 186
5.1 Introduction . . . .............................. 186
5.2 Expectation and Variance of Continuous Random Variables ..... 190
5.3 The Uniform Random Variable . . . ................... 194
5.4 Normal Random Variables . . ....................... 198
5.4.1 The Normal Approximation to the Binomial Distribution . . . 204
5.5 Exponential Random Variables . . . ................... 208
5.5.1 Hazard Rate Functions ....................... 212
5.6 Other Continuous Distributions . . . ................... 215
5.6.1 The Gamma Distribution ..................... 215
5.6.2 The Weibull Distribution ..................... 216
5.6.3 The Cauchy Distribution...................... 217
5.6.4 The Beta Distribution ....................... 218
5.7 The Distribution of a Function of a Random Variable . . . ...... 219
Summary . .................................. 222
Problems ................................... 224
Theoretical Exercises . . . . . ....................... 227
Self-Test Problems and Exercises . . ................... 229
6 Jointly Distributed Random Variables 232
6.1 Joint Distribution Functions ........................ 232
6.2 Independent Random Variables . . . ................... 240
6.3 Sums of Independent Random Variables . . . . . ............ 252
6.3.1 Identically Distributed Uniform Random Variables . ..... 252
6.3.2 Gamma Random Variables . ................... 254
6.3.3 Normal Random Variables . ................... 256
6.3.4 Poisson and Binomial Random Variables ............ 259
6.3.5 Geometric Random Variables ................... 260
6.4 Conditional Distributions: Discrete Case . . . . . ............ 263
6.5 Conditional Distributions: Continuous Case . . . ............ 266
6.6 Order Statistics ............................... 270
6.7 Joint Probability Distribution of Functions of Random Variables . . . 274
6.8 Exchangeable Random Variables . . ................... 282
Summary . .................................. 285
Problems ................................... 287
Theoretical Exercises . . . . . ....................... 291
Self-Test Problems and Exercises . . ................... 293
Contents ix
7 Properties of Expectation 297
7.1 Introduction . . . .............................. 297
7.2 Expectation of Sums of Random Variables . . . . ............ 298
7.2.1 Obtaining Bounds from Expectations
via the Probabilistic Method .................... 311
7.2.2 The Maximum–Minimums Identity . . . . ............ 313
7.3 Moments of the Number of Events that Occur . . ............ 315
7.4 Covariance, Variance of Sums, and Correlations . ............ 322
7.5 Conditional Expectation . . . ....................... 331
7.5.1 Definitions.............................. 331
7.5.2 Computing Expectations by Conditioning ............ 333
7.5.3 Computing Probabilities by Conditioning ............ 344
7.5.4 Conditional Variance . ....................... 347
7.6 Conditional Expectation and Prediction . . . . . ............ 349
7.7 Moment Generating Functions ....................... 354
7.7.1 Joint Moment Generating Functions . . . ............ 363
7.8 Additional Properties of Normal Random Variables . . . . ...... 365
7.8.1 The Multivariate Normal Distribution . . ............ 365
7.8.2 The Joint Distribution of the Sample Mean
and Sample Variance ........................ 367
7.9 General Definition of Expectation . . ................... 369
Summary . .................................. 370
Problems ................................... 373
Theoretical Exercises . . . . . ....................... 380
Self-Test Problems and Exercises . . ................... 384
8 Limit Theorems 388
8.1 Introduction . . . .............................. 388
8.2 Chebyshev’s Inequality and the Weak Law of Large
Numbers . .................................. 388
8.3 TheCentralLimitTheorem ........................ 391
8.4 The Strong Law of Large Numbers . ................... 400
8.5 Other Inequalities .............................. 403
8.6 Bounding the Error Probability When Approximating a Sum of
Independent Bernoulli Random Variables by a Poisson
Random Variable .............................. 410
Summary . .................................. 412
Problems ................................... 412
Theoretical Exercises . . . . . ....................... 414
Self-Test Problems and Exercises . . ................... 415
9 Additional Topics in Probability 417
9.1 The Poisson Process . . . . . . ....................... 417
9.2 Markov Chains................................ 419
9.3 Surprise, Uncertainty, and Entropy . ................... 425
9.4 Coding Theory and Entropy . ....................... 428
Summary . .................................. 434
Problems and Theoretical Exercises . ................... 435
Self-Test Problems and Exercises . . ................... 436
References .................................. 436
x Contents
10 Simulation 438
10.1 Introduction . . . .............................. 438
10.2 General Techniques for Simulating Continuous Random Variables . . 440
10.2.1 The Inverse Transformation Method . . . ............ 441
10.2.2 The Rejection Method ....................... 442
10.3 Simulating from Discrete Distributions . . . . . . ............ 447
10.4 Variance Reduction Techniques . . . ................... 449
10.4.1 Use of Antithetic Variables . ................... 450
10.4.2 Variance Reduction by Conditioning . . . ............ 451
10.4.3 Control Variates . . . ....................... 452
Summary . .................................. 453
Problems ................................... 453
Self-Test Problems and Exercises . . ................... 455
Reference .................................. 455
Answers to Selected Problems 457
Solutions to Self-Test Problems and Exercises 461
Index