Probability Lifesaver

Steven J. Miller is associate professor of mathematics at Williams College. He is the coauthor of An Invitation to Modern Number Theory (Princeton) and The Mathematics of Encryption: An Elementary Introduction and the editor of Benford's Law: Theory and Applications (Princeton).

"I recommend the book to everyone who is studying and fascinated by statistics."---Singalakha Menziwa, Mathemafrica

• Note to ReadersHow to Use This BookI General Theory1 Introduction1.1 Birthday Problem1.1.1 Stating the Problem1.1.2 Solving the Problem1.1.3 Generalizing the Problem and Solution: Efficiencies1.1.4 Numerical Test1.2 From Shooting Hoops to the Geometric Series1.2.1 The Problem and Its Solution1.2.2 Related Problems1.2.3 General Problem Solving Tips1.3 Gambling1.3.1 The 2008 Super Bowl Wager1.3.2 Expected Returns1.3.3 The Value of Hedging1.3.4 Consequences1.4 Summary1.5 Exercises2 Basic Probability Laws2.1 Paradoxes2.2 Set Theory Review2.2.1 Coding Digression2.2.2 Sizes of Infinity and Probabilities2.2.3 Open and Closed Sets2.3 Outcome Spaces, Events, and the Axioms of Probability2.4 Axioms of Probability2.5 Basic Probability Rules2.5.1 Law of Total Probability2.5.2 Probabilities of Unions2.5.3 Probabilities of Inclusions2.6 Probability Spaces and σ-algebras2.7 Appendix: Experimentally Finding Formulas2.7.1 Product Rule for Derivatives2.7.2 Probability of a Union2.8 Summary2.9 Exercises3 Counting I: Cards3.1 Factorials and Binomial Coefficients3.1.1 The Factorial Function3.1.2 Binomial Coefficients3.1.3 Summary3.2 Poker3.2.1 Rules3.2.2 Nothing3.2.3 Pair3.2.4 Two Pair3.2.5 Three of a Kind3.2.6 Straights, Flushes, and Straight Flushes3.2.7 Full House and Four of a Kind3.2.8 Practice Poker Hand: I3.2.9 Practice Poker Hand: II3.3 Solitaire3.3.1 Klondike3.3.2 Aces Up3.3.3 FreeCell3.4 Bridge3.4.1 Tic-tac-toe3.4.2 Number of Bridge Deals3.4.3 Trump Splits3.5 Appendix: Coding to Compute Probabilities3.5.1 Trump Split and Code3.5.2 Poker Hand Codes3.6 Summary3.7 Exercises4 Conditional Probability, Independence, and Bayes’ Theorem4.1 Conditional Probabilities4.1.1 Guessing the Conditional Probability Formula4.1.2 Expected Counts Approach4.1.3 Venn Diagram Approach4.1.4 The Monty Hall Problem4.2 The General Multiplication Rule4.2.1 Statement4.2.2 Poker Example4.2.3 Hat Problem and Error Correcting Codes4.2.4 Advanced Remark: Definition of Conditional Probability4.3 Independence4.4 Bayes’ Theorem4.5 Partitions and the Law of Total Probability4.6 Bayes’ Theorem Revisited4.7 Summary4.8 Exercises5 Counting II: Inclusion-Exclusion5.1 Factorial and Binomial Problems5.1.1 “How many” versus “What’s the probability”5.1.2 Choosing Groups5.1.3 Circular Orderings5.1.4 Choosing Ensembles5.2 The Method of Inclusion-Exclusion5.2.1 Special Cases of the Inclusion-Exclusion Principle5.2.2 Statement of the Inclusion-Exclusion Principle5.2.3 Justification of the Inclusion-Exclusion Formula5.2.4 Using Inclusion-Exclusion: Suited Hand5.2.5 The At Least to Exactly Method5.3 Derangements5.3.1 Counting Derangements5.3.2 The Probability of a Derangement5.3.3 Coding Derangement Experiments5.3.4 Applications of Derangements5.4 Summary5.5 Exercises6 Counting III: Advanced Combinatorics6.1 Basic Counting6.1.1 Enumerating Cases: I6.1.2 Enumerating Cases: II6.1.3 Sampling With and Without Replacement6.2 Word Orderings6.2.1 Counting Orderings6.2.2 Multinomial Coefficients6.3 Partitions6.3.1 The Cookie Problem6.3.2 Lotteries6.3.3 Additional Partitions6.4 Summary6.5 ExercisesII Introduction to Random Variables7 Introduction to Discrete Random Variables7.1 Discrete Random Variables: Definition7.2 Discrete Random Variables: PDFs7.3 Discrete Random Variables: CDFs7.4 Summary7.5 Exercises8 Introduction to Continuous Random Variables8.1 Fundamental Theorem of Calculus8.2 PDFs and CDFs: Definitions8.3 PDFs and CDFs: Examples8.4 Probabilities of Singleton Events8.5 Summary8.6 Exercises9 Tools: Expectation9.1 Calculus Motivation9.2 Expected Values and Moments9.3 Mean and Variance9.4 Joint Distributions9.5 Linearity of Expectation9.6 Properties of the Mean and the Variance9.7 Skewness and Kurtosis9.8 Covariances9.9 Summary9.10 Exercises10 Tools: Convolutions and Changing Variables10.1 Convolutions: Definitions and Properties10.2 Convolutions: Die Example10.2.1 Theoretical Calculation10.2.2 Convolution Code10.3 Convolutions of Several Variables10.4 Change of Variable Formula: Statement10.5 Change of Variables Formula: Proof10.6 Appendix: Products and Quotients of Random Variables10.6.1 Density of a Product10.6.2 Density of a Quotient10.6.3 Example: Quotient of Exponentials10.7 Summary10.8 Exercises11 Tools: Differentiating Identities11.1 Geometric Series Example11.2 Method of Differentiating Identities11.3 Applications to Binomial Random Variables11.4 Applications to Normal Random Variables11.5 Applications to Exponential Random Variables11.6 Summary11.7 ExercisesIII Special Distributions12 Discrete Distributions12.1 The Bernoulli Distribution12.2 The Binomial Distribution12.3 The Multinomial Distribution12.4 The Geometric Distribution12.5 The Negative Binomial Distribution12.6 The Poisson Distribution12.7 The Discrete Uniform Distribution12.8 Exercises13 Continuous Random Variables: Uniform and Exponential13.1 The Uniform Distribution13.1.1 Mean and Variance13.1.2 Sums of Uniform Random Variables13.1.3 Examples13.1.4 Generating Random Numbers Uniformly13.2 The Exponential Distribution13.2.1 Mean and Variance13.2.2 Sums of Exponential Random Variables13.2.3 Examples and Applications of Exponential Random Variables13.2.4 Generating Random Numbers from Exponential Distributions13.3 Exercises14 Continuous Random Variables: The Normal Distribution14.1 Determining the Normalization Constant14.2 Mean and Variance14.3 Sums of Normal Random Variables14.3.1 Case 1: μX = μY = 0 and 2/x = 2/y = 114.3.2 Case 2: General μX, μY and 2/x, 2/y14.3.3 Sums of Two Normals: Faster Algebra14.4 Generating Random Numbers from Normal Distributions14.5 Examples and the Central Limit Theorem14.6 Exercises15 The Gamma Function and Related Distributions15.1 Existence of Γ (s)15.2 The Functional Equation of Γ (s)15.3 The Factorial Function and Γ (s)15.4 Special Values of Γ (s)15.5 The Beta Function and the Gamma Function15.5.1 Proof of the Fundamental Relation15.5.2 The Fundamental Relation and Γ(1/2)15.6 The Normal Distribution and the Gamma Function15.7 Families of Random Variables15.8 Appendix: Cosecant Identity Proofs15.8.1 The Cosecant Identity: First Proof15.8.2 The Cosecant Identity: Second Proof15.8.3 The Cosecant Identity: Special Case s = 1/215.9 Cauchy Distribution15.10 Exercises16 The Chi-square Distribution16.1 Origin of the Chi-square Distribution16.2 Mean and Variance of X ∼ χ2(1)16.3 Chi-square Distributions and Sums of Normal Random Variables16.3.1 Sums of Squares by Direct Integration16.3.2 Sums of Squares by the Change of Variables Theorem16.3.3 Sums of Squares by Convolution16.3.4 Sums of Chi-square Random Variables16.4 Summary16.5 ExercisesIV Limit Theorems17 Inequalities and Laws of Large Numbers17.1 Inequalities17.2 Markov’s Inequality17.3 Chebyshev’s Inequality17.3.1 Statement17.3.2 Proof17.3.3 Normal and Uniform Examples17.3.4 Exponential Example17.4 The Boole and Bonferroni Inequalities17.5 Types of Convergence17.5.1 Convergence in Distribution17.5.2 Convergence in Probability17.5.3 Almost Sure and Sure Convergence17.6 Weak and Strong Laws of Large Numbers17.7 Exercises18 Stirling’s Formula18.1 Stirling’s Formula and Probabilities18.2 Stirling’s Formula and Convergence of Series18.3 From Stirling to the Central Limit Theorem18.4 Integral Test and the Poor Man’s Stirling18.5 Elementary Approaches towards Stirling’s Formula18.5.1 Dyadic Decompositions18.5.2 Lower Bounds towards Stirling: I18.5.3 Lower Bounds toward Stirling II18.5.4 Lower Bounds towards Stirling: III18.6 Stationary Phase and Stirling18.7 The Central Limit Theorem and Stirling18.8 Exercises19 Generating Functions and Convolutions19.1 Motivation19.2 Definition19.3 Uniqueness and Convergence of Generating Functions19.4 Convolutions I: Discrete Random Variables19.5 Convolutions II: Continuous Random Variables19.6 Definition and Properties of Moment Generating Functions19.7 Applications of Moment Generating Functions19.8 Exercises20 Proof of the Central Limit Theorem20.1 Key Ideas of the Proof20.2 Statement of the Central Limit Theorem20.3 Means, Variances, and Standard Deviations20.4 Standardization20.5 Needed Moment Generating Function Results20.6 Special Case: Sums of Poisson Random Variables20.7 Proof of the CLT for General Sums via MGF20.8 Using the Central Limit Theorem20.9 The Central Limit Theorem and Monte Carlo Integration20.10 Summary20.11 Exercises21 Fourier Analysis and the Central Limit Theorem21.1 Integral Transforms21.2 Convolutions and Probability Theory21.3 Proof of the Central Limit Theorem21.4 Summary21.5 ExercisesV Additional Topics22 Hypothesis Testing22.1 Z-tests22.1.1 Null and Alternative Hypotheses22.1.2 Significance Levels22.1.3 Test Statistics22.1.4 One-sided versus Two-sided Tests22.2 On p-values22.2.1 Extraordinary Claims and p-values22.2.2 Large p-values22.2.3 Misconceptions about p-values22.3 On t-tests22.3.1 Estimating the Sample Variance22.3.2 From z-tests to t-tests22.4 Problems with Hypothesis Testing22.4.1 Type I Errors22.4.2 Type II Errors22.4.3 Error Rates and the Justice System22.4.4 Power22.4.5 Effect Size22.5 Chi-square Distributions, Goodness of Fit22.5.1 Chi-square Distributions and Tests of Variance22.5.2 Chi-square Distributions and t-distributions22.5.3 Goodness of Fit for List Data22.6 Two Sample Tests22.6.1 Two-sample z-test: Known Variances22.6.2 Two-sample t-test: Unknown but Same Variances22.6.3 Unknown and Different Variances22.7 Summary22.8 Exercises23 Difference Equations, Markov Processes, and Probability23.1 From the Fibonacci Numbers to Roulette23.1.1 The Double-plus-one Strategy23.1.2 A Quick Review of the Fibonacci Numbers23.1.3 Recurrence Relations and Probability23.1.4 Discussion and Generalizations23.1.5 Code for Roulette Problem23.2 General Theory of Recurrence Relations23.2.1 Notation23.2.2 The Characteristic Equation23.2.3 The Initial Conditions23.2.4 Proof that Distinct Roots Imply Invertibility23.3 Markov Processes23.3.1 Recurrence Relations and Population Dynamics23.3.2 General Markov Processes23.4 Summary23.5 Exercises24 The Method of Least Squares24.1 Description of the Problem24.2 Probability and Statistics Review24.3 The Method of Least Squares24.4 Exercises25 Two Famous Problems and Some Coding25.1 The Marriage/Secretary Problem25.1.1 Assumptions and Strategy25.1.2 Probability of Success25.1.3 Coding the Secretary Problem25.2 Monty Hall Problem25.2.1 A Simple Solution25.2.2 An Extreme Case25.2.3 Coding the Monty Hall Problem25.3 Two Random Programs25.3.1 Sampling with and without Replacement25.3.2 Expectation25.4 ExercisesAppendix A Proof TechniquesA.1 How to Read a ProofA.2 Proofs by InductionA.2.1 Sums of IntegersA.2.2 DivisibilityA.2.3 The Binomial TheoremA.2.4 Fibonacci Numbers Modulo 2A.2.5 False Proofs by InductionA.3 Proof by GroupingA.4 Proof by Exploiting SymmetriesA.5 Proof by Brute ForceA.6 Proof by Comparison or StoryA.7 Proof by ContradictionA.8 Proof by Exhaustion (or Divide and Conquer)A.9 Proof by CounterexampleA.10 Proof by Generalizing ExampleA.11 Dirichlet’s Pigeon-Hole PrincipleA.12 Proof by Adding Zero or Multiplying by OneAppendix B Analysis ResultsB.1 The Intermediate and Mean Value TheoremsB.2 Interchanging Limits, Derivatives, and IntegralsB.2.1 Interchanging Orders: TheoremsB.2.2 Interchanging Orders: ExamplesB.3 Convergence Tests for SeriesB.4 Big-Oh NotationB.5 The Exponential FunctionB.6 Proof of the Cauchy-Schwarz InequalityB.7 ExercisesAppendix C Countable and Uncountable SetsC.1 Sizes of SetsC.2 Countable SetsC.3 Uncountable SetsC.4 Length of the RationalsC.5 Length of the Cantor SetC.6 ExercisesAppendix D Complex Analysis and the Central Limit TheoremD.1 Warnings from Real AnalysisD.2 Complex Analysis and Topology DefinitionsD.3 Complex Analysis and Moment Generating FunctionsD.4 ExercisesBibliographyIndex