Introduction To Probability

Introduction to Probability

Charles M. Grinstead
Swarthmore College

J. Laurie Snell
Dartmouth College

To our wives and in memory of Reese T. Prosser

Contents
1 Discrete Probability Distributions 1.1 Simulation of Discrete Probabilities . . . . . . . . . . . . . . . . . . . 1.2 Discrete Probability Distributions . . . . . . . . . . . . . . . . . . . . 2 Continuous ProbabilityDensities 2.1 Simulation of Continuous Probabilities . . . . . . . . . . . . . . . . . 2.2 Continuous Density Functions . . . . . . . . . . . . . . . . . . . . . . 1 1 18 41 41 55

3 Combinatorics 75 3.1 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.2 Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.3 Card Shuffling . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 120 4 Conditional Probability 4.1 Discrete Conditional Probability . . . . . . . . . . . . . . . . . . . . 4.2 Continuous Conditional Probability . . . . . . . . . . . . . . . . . . . 4.3 Paradoxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 133 162 175

5 Distributions and Densities 183 5.1 Important Distributions . . . . . . .. . . . . . . . . . . . . . . . . . 183 5.2 Important Densities . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 6 Expected Value and Variance 225 6.1 Expected Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 6.2 Variance of Discrete Random Variables . . . . . . . . . . . . . . . . . 257 6.3 Continuous Random Variables . . . . . . . . . . . . . . . . . . . . . . 268 7Sums of Random Variables 285 7.1 Sums of Discrete Random Variables . . . . . . . . . . . . . . . . . . 285 7.2 Sums of Continuous Random Variables . . . . . . . . . . . . . . . . . 291 8 Law of Large Numbers 305 8.1 Discrete Random Variables . . . . . . . . . . . . . . . . . . . . . . . 305 8.2 Continuous Random Variables . . . . . . . . . . . . . . . . . . . . . . 316 v

vi

CONTENTS 325325 340 355

9 Central Limit Theorem 9.1 Bernoulli Trials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Discrete Independent Trials . . . . . . . . . . . . . . . . . . . . . . . 9.3 Continuous Independent Trials . . . . . . . . . . . . . . . . . . . . .

10 Generating Functions 365 10.1 Discrete Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . 365 10.2Branching Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 10.3 Continuous Densities . . . . . . . . . . . . . . . . . . . . . . . . . . . 394 11 Markov Chains 11.1 Introduction . . . . . . . . . . 11.2 Absorbing Markov Chains . . 11.3 Ergodic Markov Chains . . . 11.4 Fundamental Limit Theorem 11.5 Mean First Passage Time . . 405 405 415 433 447 452

. . . . .

. . . . .

. . . ..

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

12 Random Walks 471 12.1 Random Walks in Euclidean Space . . . . . . . . . . . . . . . . . . . 471 12.2 Gambler’s Ruin . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 486 12.3 Arc Sine Laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493 Appendices A Normal Distribution Table . . . . . . . . . . . . . . . . . . . . . . . . B Galton’s Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C Life Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Index 499 499 500 501 503Preface
Probability theory began in seventeenth century France when the two great French mathematicians, Blaise Pascal and Pierre de Fermat, corresponded over two problems from games of chance. Problems like those Pascal and Fermat solved continued to influence such early researchers as Huygens, Bernoulli, and DeMoivre in establishing a mathematical theory of probability. Today, probability theory is...