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 Independent Events 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
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 The Zeta (or Zipf) 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
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 The Central Limit Theorem 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
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 521