Subscribe to DSC Newsletter

From Algorithms to Z-Scores:Probabilistic and Statistical Modeling in Computer Science. By Norm Matloff, University of California, Davis. 

Click here to read the book (PDF document, 520 pages). I guess it will become a classic on the subject, for students learning traditional statistics.

Contents


1 Time Waste Versus Empowerment 1


2 Basic Probability Models 3

2.1 ALOHA Network Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 The Crucial Notion of a Repeatable Experiment . . . . . . . . . . . . . . . . . . . . 5
2.3 Our Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 “Mailing Tubes” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 Example: ALOHA Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.6 Bayes’ Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.7 ALOHA in the Notebook Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.8 A Note on Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.9 Solution Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.10 Example: Divisibility of Random Integers . . . . . . . . . . . . . . . . . . . . . . . . 18
2.11 Example: A Simple Board Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.12 Example: Bus Ridership . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.13 Random Graph Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.13.1 Example: Preferential Attachment Graph Model . . . . . . . . . . . . . . . . 23
2.14 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.14.1 Example: Rolling Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.14.2 First Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.14.3 Second Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.14.3.1 Simulation of Conditional Probability in Dice Problem . . . . . . . 27
2.14.4 Simulation of the ALOHA Example . . . . . . . . . . . . . . . . . . . . . . . 28
2.14.5 Example: Bus Ridership, cont’d. . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.14.6 Back to the Board Game Example . . . . . . . . . . . . . . . . . . . . . . . . 30
2.14.7 How Long Should We Run the Simulation? . . . . . . . . . . . . . . . . . . . 30
2.15 Combinatorics-Based Probability Computation . . . . . . . . . . . . . . . . . . . . . 30
2.15.1 Which Is More Likely in Five Cards, One King or Two Hearts? . . . . . . . . 31
2.15.2 Example: Random Groups of Students . . . . . . . . . . . . . . . . . . . . . . 32
2.15.3 Example: Lottery Tickets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.15.4 “Association Rules” in Data Mining . . . . . . . . . . . . . . . . . . . . . . . 33
2.15.5 Multinomial Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.15.6 Example: Probability of Getting Four Aces in a Bridge Hand . . . . . . . . . 34

3 Discrete Random Variables 39

3.1 Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Discrete Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3 Independent Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4 Example: The Monty Hall Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Expected Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5.1 Generality—Not Just for DiscreteRandom Variables . . . . . . . . . . . . . . 42
3.5.1.1 What Is It? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.5.3 Existence of the Expected Value . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.5.4 Computation and Properties of Expected Value . . . . . . . . . . . . . . . . . 43
3.5.5 “Mailing Tubes” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5.6 Casinos, Insurance Companies and “Sum Users,” Compared to Others . . . . 50
3.6 Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.6.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.6.2 More Practice with the Properties of Variance . . . . . . . . . . . . . . . . . 54
3.6.3 Central Importance of the Concept of Variance . . . . . . . . . . . . . . . . . 55
3.6.4 Intuition Regarding the Size of Var(X) . . . . . . . . . . . . . . . . . . . . . . 55
3.6.4.1 Chebychev’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.6.4.2 The Coefficient of Variation . . . . . . . . . . . . . . . . . . . . . . . 55
3.7 A Useful Fact . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.8 Covariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.9 Indicator Random Variables, and Their Means and Variances . . . . . . . . . . . . . 59
3.9.1 Example: Return Time for Library Books . . . . . . . . . . . . . . . . . . . . 60
3.9.2 Example: Indicator Variables in a Committee Problem . . . . . . . . . . . . . 62
3.9.3 Example: Spinner Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.10 Expected Value, Etc. in the ALOHA Example . . . . . . . . . . . . . . . . . . . . . 64
3.11 Example: Measurements at Different Ages . . . . . . . . . . . . . . . . . . . . . . . . 65
3.12 Example: Bus Ridership Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.13 Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.13.1 Example: Toss Coin Until First Head . . . . . . . . . . . . . . . . . . . . . . 67
3.13.2 Example: Sum of Two Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.13.3 Example: Watts-Strogatz Random Graph Model . . . . . . . . . . . . . . . . 67
3.13.3.1 The Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.13.3.2 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.14 Proof of Chebychev’s Inequality (optional section) . . . . . . . . . . . . . . . . . . . 69

4 Discrete Parametric Distribution Families 71

4.1 The Case of Importance to Us: Parameteric Families of pmfs . . . . . . . . . . . . . 72
4.2 The Geometric Family of Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.2.1 R Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.2.2 Example: a Parking Space Problem . . . . . . . . . . . . . . . . . . . . . . . 76
4.3 The Binomial Family of Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.3.1 R Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.2 Example: Parking Space Model . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4 The Negative Binomial Family of Distributions . . . . . . . . . . . . . . . . . . . . . 80
4.4.1 R Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.4.2 Example: Backup Batteries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.5 The Poisson Family of Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.5.1 R Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.6 The Power Law Family of Distributions . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.6.1 The Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.6.2 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.7 Recognizing Some Parametric Distributions When You See Them . . . . . . . . . . . 84
4.8 Example: a Coin Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.9 Example: Tossing a Set of Four Coins . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.10 Example: the ALOHA Example Again . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4.11 Example: the Bus Ridership Problem Again . . . . . . . . . . . . . . . . . . . . . . . 88
4.12 Example: Flipping Coins with Bonuses . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.13 Example: Analysis of Social Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.14 Multivariate Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.15 Iterated Expectations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.15.1 Conditional Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.15.2 The Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.15.3 Example: Coin and Die Game . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.15.4 Example: Flipping Coins with Bonuses . . . . . . . . . . . . . . . . . . . . . 93

5 Pause to Reflect 99

5.1 A Cautionary Tale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.1.1 Trick Coins, Tricky Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.1.2 Intuition in Retrospect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.1.3 Implications for Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.2 What About “Iterated Variance”? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.3 Why Not Just Do All Analysis by Simulation? . . . . . . . . . . . . . . . . . . . . . 101
5.4 Reconciliation of Math and Intuition (optional section) . . . . . . . . . . . . . . . . . 102

6 Introduction to Discrete Markov Chains 109

6.1 Matrix Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.2 Example: Die Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.3 Long-Run State Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.3.1 Stationary Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.3.2 Calculation of π . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.3.2.1 Example: π in Die Game . . . . . . . . . . . . . . . . . . . . . . . . 114
6.3.2.2 Another Way to Find π . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.4 Example: 3-Heads-in-a-Row Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.4.1 Markov Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.4.2 Back to the word “Stationary” . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.5 A Modified Notebook Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.5.1 A Markov-Chain Notebook . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.5.2 Example: 3-Heads-in-a-Row Game . . . . . . . . . . . . . . . . . . . . . . . . 118
6.6 Simulation of Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.7 Example: ALOHA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.8 Example: Bus Ridership Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.9 Example: an Inventory Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.10 Expected Hitting Times . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

7 Continuous Probability Models 125

7.1 Running Example: a Random Dart . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.2 Individual Values Now Have Probability Zero . . . . . . . . . . . . . . . . . . . . . . 126
7.3 But Now We Have a Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
7.3.1 Our Way Out of the Problem: Cumulative Distribution Functions . . . . . . 127
7.3.2 Density Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
7.3.3 Properties of Densities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.3.4 Intuitive Meaning of Densities . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
7.3.5 Expected Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
7.4 A First Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.5 The Notion of Support in the Continuous Case . . . . . . . . . . . . . . . . . . . . . 135
7.6 Famous Parametric Families of Continuous Distributions . . . . . . . . . . . . . . . . 135
7.6.1 The Uniform Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.6.1.1 Density and Properties . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.6.1.2 R Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.6.1.3 Example: Modeling of Disk Performance . . . . . . . . . . . . . . . 136
7.6.1.4 Example: Modeling of Denial-of-Service Attack . . . . . . . . . . . . 137
7.6.2 The Normal (Gaussian) Family of Continuous Distributions . . . . . . . . . . 137
7.6.2.1 Density and Properties . . . . . . . . . . . . . . . . . . . . . . . . . 137
7.6.3 The Exponential Family of Distributions . . . . . . . . . . . . . . . . . . . . . 138
7.6.3.1 Density and Properties . . . . . . . . . . . . . . . . . . . . . . . . . 138
7.6.3.2 R Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
7.6.3.3 Example: Refunds on Failed Components . . . . . . . . . . . . . . . 139
7.6.3.4 Example: Garage Parking Fees . . . . . . . . . . . . . . . . . . . . . 139
7.6.3.5 Importance in Modeling . . . . . . . . . . . . . . . . . . . . . . . . . 140
7.6.4 The Gamma Family of Distributions . . . . . . . . . . . . . . . . . . . . . . . 140
7.6.4.1 Density and Properties . . . . . . . . . . . . . . . . . . . . . . . . . 140
7.6.4.2 Example: Network Buffer . . . . . . . . . . . . . . . . . . . . . . . . 141
7.6.4.3 Importance in Modeling . . . . . . . . . . . . . . . . . . . . . . . . . 142
7.6.5 The Beta Family of Distributions . . . . . . . . . . . . . . . . . . . . . . . . . 142
7.6.5.1 Density Etc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
7.6.5.2 Importance in Modeling . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.7 Choosing a Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.8 Finding the Density of a Function of a Random Variable . . . . . . . . . . . . . . . . 147
7.9 Quantile Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
7.10 Using cdf Functions to Find Probabilities . . . . . . . . . . . . . . . . . . . . . . . . 149
7.11 A General Method for Simulating a Random Variable . . . . . . . . . . . . . . . . . 149
7.12 Example: Writing a Set of R Functions for a Certain Power Family . . . . . . . . . . 150
7.13 Multivariate Densities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.14 Iterated Expectations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
7.14.1 The Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
7.14.2 Example: Another Coin Game . . . . . . . . . . . . . . . . . . . . . . . . . . 152
7.15 Continuous Random Variables Are “Useful Unicorns” . . . . . . . . . . . . . . . . . 153

8 The Normal Family of Distributions 155

8.1 Density and Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
8.1.1 Closure Under Affine Transformation . . . . . . . . . . . . . . . . . . . . . . . 156
8.1.2 Closure Under Independent Summation . . . . . . . . . . . . . . . . . . . . . 157
8.2 The Standard Normal Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
8.3 Evaluating Normal cdfs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
8.4 Example: Network Intrusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
8.5 Example: Class Enrollment Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
viii CONTENTS
8.6 More on the Jill Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.7 Example: River Levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
8.8 Example: Upper Tail of a Light Bulb Distribution . . . . . . . . . . . . . . . . . . . 162
8.9 The Central Limit Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
8.10 Example: Cumulative Roundoff Error . . . . . . . . . . . . . . . . . . . . . . . . . . 163
8.11 Example: R Evaluation of a Central Limit Theorem Approximation . . . . . . . . . 164
8.12 Example: Bug Counts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
8.13 Example: Coin Tosses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
8.14 Example: Normal Approximation to Gamma Family . . . . . . . . . . . . . . . . . . 166
8.15 Example: Museum Demonstration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
8.16 Importance in Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
8.17 The Chi-Squared Family of Distributions . . . . . . . . . . . . . . . . . . . . . . . . 167
8.17.1 Density and Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
8.17.2 Example: Error in Pin Placement . . . . . . . . . . . . . . . . . . . . . . . . 168
8.17.3 Example: Generating Normal Random Numbers . . . . . . . . . . . . . . . . 169
8.17.4 Importance in Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8.17.5 Relation to Gamma Family . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8.18 The Multivariate Normal Family . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8.19 Optional Topic: Precise Statement of the CLT . . . . . . . . . . . . . . . . . . . . . 171
8.19.1 Convergence in Distribution, and the Precisely-Stated CLT . . . . . . . . . . 171

9 The Exponential Distributions 175

9.1 Connection to the Poisson Distribution Family . . . . . . . . . . . . . . . . . . . . . 175
9.2 Memoryless Property of Exponential Distributions . . . . . . . . . . . . . . . . . . . 177
9.2.1 Derivation and Intuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
9.2.2 Uniquely Memoryless . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
9.2.3 Example: “Nonmemoryless” Light Bulbs . . . . . . . . . . . . . . . . . . . . . 179
9.3 Example: Minima of Independent Exponentially Distributed Random Variables . . . 179
9.3.1 Example: Computer Worm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
9.3.2 Example: Electronic Components . . . . . . . . . . . . . . . . . . . . . . . . . 183
9.4 A Cautionary Tale: the Bus Paradox . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
9.4.1 Length-Biased Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
9.4.2 Probability Mass Functions and Densities in Length-Biased Sampling . . . . 185

10 Stop and Review: Probability Structures 187

11 Introduction to Continuous-Time Markov Chains 193

11.1 Continuous-Time Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
11.2 Holding-Time Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
11.2.1 The Notion of “Rates” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
11.3 Stationary Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
11.3.1 Intuitive Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
11.3.2 Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
11.4 Example: Machine Repair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
11.5 Example: Migration in a Social Network . . . . . . . . . . . . . . . . . . . . . . . . . 198
11.6 Birth/Death Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
11.7 Cell Communications Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
11.7.1 Stationary Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
11.7.2 Going Beyond Finding the π . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

12 Covariance and Random Vectors 203

12.1 Measuring Co-variation of Random Variables . . . . . . . . . . . . . . . . . . . . . . 203
12.1.1 Covariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
12.1.2 Example: Variance of Sum of Nonindependent Variables . . . . . . . . . . . . 205
12.1.3 Example: the Committee Example Again . . . . . . . . . . . . . . . . . . . . 205
12.2 Correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
12.2.1 Example: a Catchup Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
12.3 Sets of Independent Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . 207
12.3.1 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
12.3.1.1 Expected Values Factor . . . . . . . . . . . . . . . . . . . . . . . . . 208
12.3.1.2 Covariance Is 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
12.3.1.3 Variances Add . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
12.3.2 Examples Involving Sets of Independent Random Variables . . . . . . . . . . 209
12.3.2.1 Example: Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
12.3.2.2 Example: Variance of a Product . . . . . . . . . . . . . . . . . . . . 210
12.3.2.3 Example: Ratio of Independent Geometric Random Variables . . . 210
12.4 Matrix Formulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
12.4.1 Properties of Mean Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
12.4.2 Covariance Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
12.4.3 Covariance Matrices Linear Combinations of Random Vectors . . . . . . . . . 213
12.4.4 Example: (X,S) Dice Example Again . . . . . . . . . . . . . . . . . . . . . . . 214
12.4.5 Example: Easy Sum Again . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
12.5 The Multivariate Normal Family of Distributions . . . . . . . . . . . . . . . . . . . . 215
12.5.1 R Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
12.5.2 Special Case: New Variable Is a Single Linear Combination of a Random Vector216
12.6 Indicator Random Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
12.7 Example: Dice Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
12.7.1 Correlation Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
12.7.2 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

13 Multivariate PMFs and Densities 223

13.1 Multivariate Probability Mass Functions . . . . . . . . . . . . . . . . . . . . . . . . . 223
13.2 Multivariate Densities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
13.2.1 Motivation and Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
13.2.2 Use of Multivariate Densities in Finding Probabilities and Expected Values . 226
13.2.3 Example: a Triangular Distribution . . . . . . . . . . . . . . . . . . . . . . . 227
13.2.4 Example: Train Rendezvouz . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
13.3 More on Sets of Independent Random Variables . . . . . . . . . . . . . . . . . . . . . 231
13.3.1 Probability Mass Functions and Densities Factor in the Independent Case . . 231
13.3.2 Convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
13.3.3 Example: Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
13.3.4 Example: Analysis of Seek Time . . . . . . . . . . . . . . . . . . . . . . . . . 233
13.3.5 Example: Backup Battery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
13.3.6 Example: Minima of Uniformly Distributed Random Variables . . . . . . . . 235
13.3.7 Example: Ethernet Again . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
13.4 Example: Finding the Distribution of the Sum of Nonindependent Random Variables 236
13.5 Parametric Families of Multivariate Distributions . . . . . . . . . . . . . . . . . . . . 236
13.5.1 The Multinomial Family of Distributions . . . . . . . . . . . . . . . . . . . . 237
13.5.1.1 Probability Mass Function . . . . . . . . . . . . . . . . . . . . . . . 237
13.5.1.2 Example: Component Lifetimes . . . . . . . . . . . . . . . . . . . . 238
13.5.1.3 Mean Vectors and Covariance Matrices in the Multinomial Family . 239
13.5.1.4 Application: Text Mining . . . . . . . . . . . . . . . . . . . . . . . . 242
13.5.2 The Multivariate Normal Family of Distributions . . . . . . . . . . . . . . . 242
13.5.2.1 Densities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
13.5.2.2 Geometric Interpretation . . . . . . . . . . . . . . . . . . . . . . . . 243
13.5.2.3 Properties of Multivariate Normal Distributions . . . . . . . . . . . 246
13.5.2.4 The Multivariate Central Limit Theorem . . . . . . . . . . . . . . . 247
13.5.2.5 Example: Finishing the Loose Ends from the Dice Game . . . . . . 248
13.5.2.6 Application: Data Mining . . . . . . . . . . . . . . . . . . . . . . . . 248

14 Transform Methods 255

14.1 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
14.2 Moment Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
14.3 Transforms of Sums of Independent Random Variables . . . . . . . . . . . . . . . . . 257
14.4 Example: Network Packets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
14.4.1 Poisson Generating Function . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
14.4.2 Sums of Independent Poisson Random Variables Are Poisson Distributed . . 258
14.5 Other Uses of Transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259

15 Statistics: Prologue 261

15.1 Sampling Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
15.1.1 Random Samples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
15.2 The Sample Mean—a Random Variable . . . . . . . . . . . . . . . . . . . . . . . . . 263
15.2.1 Toy Population Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
15.2.2 Expected and Variance of X . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
15.2.3 Toy Population Example Again . . . . . . . . . . . . . . . . . . . . . . . . . . 265
15.2.4 Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
15.3 Sample Means Are Approximately Normal—No Matter What the Population Distribution
Is . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
15.3.1 The Sample Variance—Another Random Variable . . . . . . . . . . . . . . . 267
15.3.1.1 Intuitive Estimation of σ
15.3.1.2 Easier Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
15.3.1.3 To Divide by n or n-1? . . . . . . . . . . . . . . . . . . . . . . . . . 268
15.4 Observational Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
15.5 A Good Time to Stop and Review! . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

16 Introduction to Confidence Intervals 271

16.1 The “Margin of Error” and Confidence Intervals . . . . . . . . . . . . . . . . . . . . 271
16.2 Confidence Intervals for Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
16.2.1 Basic Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
16.2.2 Example: Simulation Output . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
16.3 Meaning of Confidence Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
16.3.1 A Weight Survey in Davis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
16.3.2 More About Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
16.4 Confidence Intervals for Proportions . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
16.4.1 Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
16.4.2 That n vs. n-1 Thing Again . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
16.4.3 Simulation Example Again . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
16.4.4 Example: Davis Weights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
16.4.5 Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
16.4.6 (Non-)Effect of the Population Size . . . . . . . . . . . . . . . . . . . . . . . . 280
16.4.7 Inferring the Number Polled . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
16.4.8 Planning Ahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
16.5 General Formation of Confidence Intervals from Approximately Normal Estimators . 281
16.5.1 The Notion of a Standard Error . . . . . . . . . . . . . . . . . . . . . . . . . 281
16.5.2 Forming General Confidence Intervals . . . . . . . . . . . . . . . . . . . . . . 282
16.5.3 Standard Errors of Combined Estimators . . . . . . . . . . . . . . . . . . . . 283
16.6 Confidence Intervals for Differences of Means or Proportions . . . . . . . . . . . . . . 284
16.6.1 Independent Samples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
16.6.2 Example: Network Security Application . . . . . . . . . . . . . . . . . . . . . 285
16.6.3 Dependent Samples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
16.6.4 Example: Machine Classification of Forest Covers . . . . . . . . . . . . . . . . 287
16.7 And What About the Student-t Distribution? . . . . . . . . . . . . . . . . . . . . . . 288
16.8 R Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
16.9 Example: Pro Baseball Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
16.9.1 R Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
16.9.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
16.10Example: UCI Bank Marketing Dataset . . . . . . . . . . . . . . . . . . . . . . . . . 293
16.11Example: Amazon Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
16.12Example: Master’s Degrees in CS/EE . . . . . . . . . . . . . . . . . . . . . . . . . . 295
16.13Other Confidence Levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
16.14One More Time: Why Do We Use Confidence Intervals? . . . . . . . . . . . . . . . . 296

17 Introduction to Significance Tests 299

17.1 The Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
17.2 General Testing Based on Normally Distributed Estimators . . . . . . . . . . . . . . 301
17.3 Example: Network Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
17.4 The Notion of “p-Values” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
17.5 Example: Bank Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
17.6 One-Sided HA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
17.7 Exact Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
17.7.1 Example: Test for Biased Coin . . . . . . . . . . . . . . . . . . . . . . . . . . 304
17.7.2 Example: Improved Light Bulbs . . . . . . . . . . . . . . . . . . . . . . . . . 305
17.7.3 Example: Test Based on Range Data . . . . . . . . . . . . . . . . . . . . . . . 306
17.7.4 Exact Tests under a Normal Distribution Assumption . . . . . . . . . . . . . 307
17.8 Don’t Speak of “the Probability That H0 Is True” . . . . . . . . . . . . . . . . . . . 307
17.9 R Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
17.10The Power of a Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
17.10.1 Example: Coin Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
17.10.2 Example: Improved Light Bulbs . . . . . . . . . . . . . . . . . . . . . . . . . 309
17.11What’s Wrong with Significance Testing—and What to Do Instead . . . . . . . . . . 309
17.11.1 History of Significance Testing, and Where We Are Today . . . . . . . . . . . 310
17.11.2 The Basic Fallacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
17.11.3 You Be the Judge! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
17.11.4What to Do Instead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
17.11.5 Decide on the Basis of “the Preponderance of Evidence” . . . . . . . . . . . . 313
17.11.6 Example: the Forest Cover Data . . . . . . . . . . . . . . . . . . . . . . . . . 314
17.11.7 Example: Assessing Your Candidate’s Chances for Election . . . . . . . . . . 314

18 General Statistical Estimation and Inference 315

18.1 General Methods of Parametric Estimation . . . . . . . . . . . . . . . . . . . . . . . 315
18.1.1 Example: Guessing the Number of Raffle Tickets Sold . . . . . . . . . . . . . 315
18.1.2 Method of Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
18.1.2.1 Example: Lottery Model . . . . . . . . . . . . . . . . . . . . . . . . 316
18.1.2.2 General Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
18.1.3 Method of Maximum Likelihood . . . . . . . . . . . . . . . . . . . . . . . . . 317
18.1.3.1 Example: Raffle Model . . . . . . . . . . . . . . . . . . . . . . . . . 317
18.1.3.2 General Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
18.1.4 Example: Estimation of the Parameters of a Gamma Distribution . . . . . . 319
18.1.4.1 Method of Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
18.1.4.2 MLEs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
18.1.5 R’s mle() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
18.1.6 R’s gmm() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
18.1.6.1 Example: Bodyfat Data . . . . . . . . . . . . . . . . . . . . . . . . . 323
18.1.7 More Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
18.1.8 Asymptotic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
18.1.8.1 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
18.1.8.2 Approximate Confidence Intervals . . . . . . . . . . . . . . . . . . . 328
18.2 Bias and Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
18.2.1 Bias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
18.2.2 Why Divide by n-1 in s
18.2.2.1 But in This Book, We Divide by n, not n-1 Anyway . . . . . . . . . 332
18.2.3 Example of Bias Calculation: Max from U(0,c) . . . . . . . . . . . . . . . . . 333
18.2.4 Example of Bias Calculation: Gamma Family . . . . . . . . . . . . . . . . . . 334
18.2.5 Tradeoff Between Variance and Bias . . . . . . . . . . . . . . . . . . . . . . . 334
18.3 Simultaneous Inference Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
18.3.1 The Bonferonni Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
18.3.2 Scheffe’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
18.3.3 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
18.3.4 Other Methods for Simultaneous Inference . . . . . . . . . . . . . . . . . . . . 339
18.4 Bayesian Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
18.4.1 How It Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
18.4.1.1 Empirical Bayes Methods . . . . . . . . . . . . . . . . . . . . . . . . 342
18.4.2 Extent of Usage of Subjective Priors . . . . . . . . . . . . . . . . . . . . . . . 342
18.4.3 Arguments Against Use of Subjective Priors . . . . . . . . . . . . . . . . . . . 343
18.4.4 What Would You Do? A Possible Resolution . . . . . . . . . . . . . . . . . . 344
18.4.5 The Markov Chain Monte Carlo Method . . . . . . . . . . . . . . . . . . . . . 345
18.4.6 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345

19 Mixture Models 349

19.1 The Old Trick Coin Example, Updated . . . . . . . . . . . . . . . . . . . . . . . . . . 349
19.2 General Mixture Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
19.3 Generating Random Variates from a Mixture Distribution . . . . . . . . . . . . . . . 351
19.4 A Useful Tool: the Law of Total Expectation . . . . . . . . . . . . . . . . . . . . . . 351
19.4.1 Conditional Expected Value As a Random Variable . . . . . . . . . . . . . . 352
19.4.2 Famous Formula: Theorem of Total Expectation . . . . . . . . . . . . . . . . 353
19.4.3 Properties of Conditional Expectation and Variance . . . . . . . . . . . . . . 353
19.4.4 Example: More on Flipping Coins with Bonuses . . . . . . . . . . . . . . . . 354
19.4.5 Example: Trapped Miner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
19.4.6 Example: Analysis of Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . 357
19.4.7 What About the Variance? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
19.5 The EM Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
19.5.1 Overall Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
19.5.2 The mixtools Package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
19.5.3 Example: Old Faithful Geyser . . . . . . . . . . . . . . . . . . . . . . . . . . 361
19.6 Mean and Variance of Random Variables Having Mixture Distributions . . . . . . . 363
19.7 Example: Two Kinds of Batteries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
19.8 Example: Overdispersion Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
19.9 Example: Hidden Markov Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
19.10Vector Space Interpretations (for the mathematically adventurous only) . . . . . . . 367
19.10.1 Properties of Correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
19.10.2 Conditional Expectation As a Projection . . . . . . . . . . . . . . . . . . . . 368
19.11Proof of the Law of Total Expectation . . . . . . . . . . . . . . . . . . . . . . . . . . 370

20 Histograms and Beyond: Nonparametric Density Estimation 375

20.1 Example: Baseball Player Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
20.2 Basic Ideas in Density Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
20.3 Histograms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
20.4 Kernel-Based Density Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
20.5 Example: Baseball Player Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
20.6 More on Density Estimation in ggplot2 . . . . . . . . . . . . . . . . . . . . . . . . . . 379
20.7 Bias, Variance and Aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
20.7.1 Bias vs. Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
20.7.2 Aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
20.8 Nearest-Neighbor Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
20.9 Estimating a cdf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
20.10Hazard Function Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
20.11For Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386

21 Introduction to Model Building 387

21.1 “Desperate for Data” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
21.1.1 Known Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
21.1.2 Estimated Mean . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
21.1.3 The Bias/Variance Tradeoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
21.1.4 Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
21.2 Assessing “Goodness of Fit” of a Model . . . . . . . . . . . . . . . . . . . . . . . . . 392
21.2.1 The Chi-Square Goodness of Fit Test . . . . . . . . . . . . . . . . . . . . . . 392
21.2.2 Kolmogorov-Smirnov Confidence Bands . . . . . . . . . . . . . . . . . . . . . 393
21.2.3 Less Formal Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
21.3 Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
21.4 Real Populations and Conceptual Populations . . . . . . . . . . . . . . . . . . . . . . 397

22 Linear Regression 399

22.1 The Goals: Prediction and Description . . . . . . . . . . . . . . . . . . . . . . . . . . 399
22.2 Example Applications: Software Engineering, Networks, Text Mining . . . . . . . . . 400
22.3 Adjusting for Covariates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
22.4 What Does “Relationship” Really Mean? . . . . . . . . . . . . . . . . . . . . . . . . 402
22.4.1 Precise Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
22.4.2 (Rather Artificial) Example: Marble Problem . . . . . . . . . . . . . . . . . . 403
22.5 Estimating That Relationship from Sample Data . . . . . . . . . . . . . . . . . . . . 404
22.5.1 Parametric Models for the Regression Function m() . . . . . . . . . . . . . . 404
22.5.2 Estimation in Parametric Regression Models . . . . . . . . . . . . . . . . . . 405
22.5.3 More on Parametric vs. Nonparametric Models . . . . . . . . . . . . . . . . . 406
22.6 Example: Baseball Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
22.6.1 R Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
22.6.2 A Look through the Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
22.7 Multiple Regression: More Than One Predictor Variable . . . . . . . . . . . . . . . . 410
22.8 Example: Baseball Data (cont’d.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
22.9 Interaction Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
22.10Parametric Estimation of Linear Regression Functions . . . . . . . . . . . . . . . . . 413
22.10.1Meaning of “Linear” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
22.10.2 Random-X and Fixed-X Regression . . . . . . . . . . . . . . . . . . . . . . . 414
22.10.3 Point Estimates and Matrix Formulation . . . . . . . . . . . . . . . . . . . . 414
22.10.4 Approximate Confidence Intervals . . . . . . . . . . . . . . . . . . . . . . . . 416
22.11Example: Baseball Data (cont’d.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
22.12Dummy Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
22.13Example: Baseball Data (cont’d.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
22.14What Does It All Mean?—Effects of Adding Predictors . . . . . . . . . . . . . . . . 422
22.15Model Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
22.15.1 The Overfitting Problem in Regression . . . . . . . . . . . . . . . . . . . . . . 425
22.15.2 Relation to the Bias-vs.-Variance Tradefoff . . . . . . . . . . . . . . . . . . . 426
22.15.3Multicollinearity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
22.15.4Methods for Predictor Variable Selection . . . . . . . . . . . . . . . . . . . . 427
22.15.4.1 Hypothesis Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . 427
22.15.4.2 Confidence Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
22.15.4.3 Predictive Ability Indicators . . . . . . . . . . . . . . . . . . . . . . 428
22.15.4.4 The LASSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
22.15.5 Rough Rules of Thumb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
22.16Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
22.16.1 Height/Weight Age Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
22.16.2 R’s predict() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
22.17Example: Turkish Teaching Evaluation Data . . . . . . . . . . . . . . . . . . . . . . 431
22.17.1 The Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
22.17.2 Data Prep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432
22.17.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
22.18What About the Assumptions? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
22.18.1 Exact Confidence Intervals and Tests . . . . . . . . . . . . . . . . . . . . . . . 436
22.18.2 Is the Homoscedasticity Assumption Important? . . . . . . . . . . . . . . . . 436
22.18.3 Regression Diagnostics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
22.19Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
22.19.1 Example: Prediction of Network RTT . . . . . . . . . . . . . . . . . . . . . . 437
22.19.2 Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
22.19.3 Example: OOP Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438

23 Classification 443

23.1 Classification = Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
23.1.1 What Happens with Regression in the Case Y = 0,1? . . . . . . . . . . . . . 444
23.2 Logistic Regression: a Common Parametric Model for the Regression Function in
Classification Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
23.2.1 The Logistic Model: Motivations . . . . . . . . . . . . . . . . . . . . . . . . . 445
23.2.2 Esimation and Inference for Logit Coefficients . . . . . . . . . . . . . . . . . . 447
23.3 Example: Forest Cover Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
23.3.0.1 R Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
23.3.1 Analysis of the Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
23.4 The Multiclass Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
23.4.1 One vs. All Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
23.4.2 Issues of Data Balance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452
23.4.2.1 Statement of the Problem . . . . . . . . . . . . . . . . . . . . . . . . 452
23.4.2.2 Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
23.5 Model Selection in Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
23.6 Optimality of the Regression Function for 0-1-Valued Y (optional section) . . . . . . 454

24 Nonparametric Estimation of Regression and Classification Functions 457

24.1 Methods Based on Estimating mY ;X(t) . . . . . . . . . . . . . . . . . . . . . . . . . . 457
24.1.1 Nearest-Neighbor Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458
24.1.2 Kernel-Based Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
24.1.3 The Naive Bayes Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
24.2 Methods Based on Estimating Classification Boundaries . . . . . . . . . . . . . . . . 462
24.2.1 Support Vector Machines (SVMs) . . . . . . . . . . . . . . . . . . . . . . . . 462
24.2.2 CART . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
24.3 Comparison of Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465

25 Relations Among Variables 467

25.1 Principal Components Analysis (PCA) . . . . . . . . . . . . . . . . . . . . . . . . . . 467
25.1.1 How to Calculate Them . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468
25.1.2 Example: Forest Cover Data . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
25.1.3 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
25.1.4 Scope of Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
25.1.5 Example: Turkish Teaching Evaluation Data . . . . . . . . . . . . . . . . . . 471
25.2 Log-Linear Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
25.2.1 The Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
25.2.2 The Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
25.2.3 The Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
25.2.4 Interpretation of Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
25.2.5 Parameter Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
25.2.6 Example: Hair, Eye Color . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
25.2.6.1 The loglin() Function . . . . . . . . . . . . . . . . . . . . . . . . . . 478
25.2.7 Hair/Eye Color Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
25.2.8 Obtaining Standard Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
25.3 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
25.3.1 K-Means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
25.3.1.1 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
25.3.1.2 Example: the Baseball Player Data . . . . . . . . . . . . . . . . . . 483
25.3.2 Mixture Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
25.3.3 Spectral Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
25.3.4 Other R Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
25.3.5 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
25.4 Simpson’s (Non-)Paradox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
25.4.1 Example: UC Berkeley Graduate Admission Data . . . . . . . . . . . . . . . 486
25.4.1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
25.4.1.2 Log-Linear Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
25.4.2 Toward Making It Simpson’s NON-Paradox . . . . . . . . . . . . . . . . . . . 489

A R Quick Start 491

A.1 Correspondences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491
A.2 Starting R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
A.3 First Sample Programming Session . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
A.4 Second Sample Programming Session . . . . . . . . . . . . . . . . . . . . . . . . . . . 496
A.5 Third Sample Programming Session . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
A.6 Default Argument Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499
A.7 The R List Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499
A.7.1 The Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499
A.7.2 The Reduce() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
A.7.3 S3 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
A.7.4 Handy Utilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
A.8 Data Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
A.9 Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
A.10 Packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
A.11 Other Sources for Learning R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
A.12 Online Help . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
A.13 Debugging in R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
A.14 Complex Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508
A.15 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508

B Review of Matrix Algebra 509

B.1 Terminology and Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509
B.1.1 Matrix Addition and Multiplication . . . . . . . . . . . . . . . . . . . . . . . 510
B.2 Matrix Transpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
B.3 Linear Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
B.4 Determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
B.5 Matrix Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
B.6 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
B.7 Matrix Algebra in R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514

C Introduction to the ggplot2 Graphics Package 517

C.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
C.2 Installation and Use . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
C.3 Basic Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
C.4 Example: Simple Line Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
C.5 Example: Census Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521
C.6 Function Plots, Density Estimates and Smoothing . . . . . . . . . . . . . . . . . . . 528
C.7 What’s Going on Inside . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529
C.8 For Further Information . . .

DSC Resources

Additional Reading

Follow us on Twitter: @DataScienceCtrl | @AnalyticBridge

Views: 864

On Data Science Central

© 2019   AnalyticBridge.com is a subsidiary and dedicated channel of Data Science Central LLC   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service