xvi
Contents
CHAPTER 8
Discrete Probability
475
8.1 Ideas of Chance in Computer Science 475
8.11 Introductory Examples 476
8.1.2 Basic Definitions 478
8.1.3 Frequency Interpretation of Probability 480
8.1.4 Introductory Example Reconsidered 480
8.1.5 The Combinatorics of Uniform Probability Density 482
8.1.6 Set Theory and the Probability of Events 484
8.2 Exercises 488
8.3 Cross Product Sample Spaces 491
8.3.1 A Multiplication Principle 492
8.3.2 The Cross Product of Sample Spaces 495
8.3.3 Bernoulli Trial Processes 498
8.3.4 Events of Cross Product Form 500
8.3.5 Two Ways of Viewing Events 502
8.4 Exercises 505
8.5 Independent Events and Conditional Probability 507
8.5.1 Independent Events 507
8.5.2 Introduction to Conditional Probability 509
8.5.3 Exploring Conditional Probability 512
8.5.4 Using Bayes' Rule with the Theorem of Total Probability 514
8.6 Exercises 517
8.7 Discrete Random Variables 520
8.7.1 Distributions of a Random Variable 520
8.72 The Binomial Distribution 522
8.73 The Hypergeometric Distribution 522
8.74 Expectation of a Random Variable 524
8.75 The Sum of Random Variables 526
8.8 Exercises 529
8.9 Variance, Standard Deviation, and the Law of Averages 530
8.9.1 Variance and Standard Deviation 531
8.9.2 Independent Random Variables 533