From Algorithms to Z-Scores: Probabilistic and Statistical Modeling in Computer Science

Time Waste Versus Empowerment......Page 27
ALOHA Network Example......Page 29
The Crucial Notion of a Repeatable Experiment......Page 31
Our Definitions......Page 32
Basic Probability Computations: ALOHA Network Example......Page 36
Bayes\' Rule......Page 39
ALOHA in the Notebook Context......Page 40
Solution Strategies......Page 41
Example: Divisibility of Random Integers......Page 43
Example: A Simple Board Game......Page 44
Example: Bus Ridership......Page 45
Example: Rolling Dice......Page 47
Improving the Code......Page 48
Simulation of the ALOHA Example......Page 50
Back to the Board Game Example......Page 51
Which Is More Likely in Five Cards, One King or Two Hearts?......Page 52
``Association Rules\'\' in Data Mining......Page 54
Multinomial Coefficients......Page 55
Example: Probability of Getting Four Aces in a Bridge Hand......Page 56
Discrete Random Variables......Page 61
Generality—Not Just for Discrete Random Variables......Page 62
Computation and Properties of Expected Value......Page 63
``Mailing Tubes\'\'......Page 68
Casinos, Insurance Companies and ``Sum Users,\'\' Compared to Others......Page 69
Definition......Page 70
Intuition Regarding the Size of Var(X)......Page 73
The Coefficient of Variation......Page 74
Covariance......Page 75
Indicator Random Variables, and Their Means and Variances......Page 76
A Combinatorial Example......Page 77
Expected Value, Etc. in the ALOHA Example......Page 79
Distributions......Page 80
Example: Watts-Strogatz Random Graph Model......Page 81
Parameteric Families of Functions......Page 82
The Case of Importance to Us: Parameteric Families of pmfs......Page 83
The Geometric Family of Distributions......Page 84
R Functions......Page 86
Example: a Parking Space Problem......Page 87
The Binomial Family of Distributions......Page 89
Example: Flipping Coins with Bonuses......Page 90
Example: Analysis of Social Networks......Page 91
The Negative Binomial Family of Distributions......Page 92
The Poisson Family of Distributions......Page 93
R Functions......Page 94
The Power Law Family of Distributions......Page 95
Example: a Coin Game......Page 96
Example: the ALOHA Example Again......Page 98
Example: the Bus Ridership Problem Again......Page 99
Multivariate Distributions......Page 100
Trick Coins, Tricky Example......Page 101
Intuition in Retrospect......Page 102
Why Not Just Do All Analysis by Simulation?......Page 103
Proof of Chebychev\'s Inequality......Page 104
Reconciliation of Math and Intuition (optional section)......Page 105
Example: Die Game......Page 111
Long-Run State Probabilities......Page 112
Example: 3-Heads-in-a-Row Game......Page 113
Example: ALOHA......Page 114
Example: Bus Ridership Problem......Page 116
An Inventory Model......Page 117
A Random Dart......Page 119
But Equation (5.2) Presents a Problem......Page 120
Motivation, Definition and Interpretation......Page 124
Properties of Densities......Page 127
A First Example......Page 128
Density and Properties......Page 129
Example: Modeling of Disk Performance......Page 130
Density and Properties......Page 131
Example: Network Intrusion......Page 133
Example: River Levels......Page 135
The Central Limit Theorem......Page 136
Example: Bug Counts......Page 137
Example: Coin Tosses......Page 138
Optional topic: Formal Statement of the CLT......Page 139
Density and Properties......Page 140
Example: Error in Pin Placement......Page 141
R Functions......Page 142
Example: Garage Parking Fees......Page 143
Connection to the Poisson Distribution Family......Page 144
Density and Properties......Page 146
Example: Network Buffer......Page 147
The Beta Family of Distributions......Page 148
Choosing a Model......Page 150
``Hybrid\'\' Continuous/Discrete Distributions......Page 151
Stop and Review: Probability Structures......Page 155
Covariance......Page 159
Example: the Committee Example Again......Page 161
Correlation......Page 162
Sets of Independent Random Variables......Page 163
Covariance Is 0......Page 164
Example: Dice......Page 165
Example: Ratio of Independent Geometric Random Variables......Page 166
Matrix Formulations......Page 167
Covariance Matrices......Page 168
Example: (X,S) Dice Example Again......Page 169
Example: Dice Game......Page 170
Correlation Matrices......Page 173
Multivariate Probability Mass Functions......Page 177
Use of Multivariate Densities in Finding Probabilities and Expected Values......Page 180
Example: a Triangular Distribution......Page 181
Example: Train Rendezvouz......Page 184
Convolution......Page 185
Example: Ethernet......Page 186
Example: Analysis of Seek Time......Page 187
Example: Backup Battery......Page 188
Example: Minima of Independent Exponentially Distributed Random Variables......Page 189
Example: Computer Worm......Page 191
Example: Ethernet Again......Page 192
Parametric Families of Multivariate Distributions......Page 193
Probability Mass Function......Page 194
Example: Component Lifetimes......Page 195
Mean Vectors and Covariance Matrices in the Multinomial Family......Page 196
Densities......Page 199
Geometric Interpretation......Page 200
Properties of Multivariate Normal Distributions......Page 203
The Multivariate Central Limit Theorem......Page 204
Application: Data Mining......Page 205
Derivation and Intuition......Page 211
Example: ``Nonmemoryless\'\' Light Bulbs......Page 213
Holding-Time Distribution......Page 214
Intuitive Derivation......Page 215
Computation......Page 216
Example: Machine Repair......Page 217
Example: Migration in a Social Network......Page 218
Introduction to Confidence Intervals......Page 221
Random Samples......Page 222
The Sample Mean—a Random Variable......Page 223
Sample Means Are Approximately Normal–No Matter What the Population Distribution Is......Page 224
The Sample Variance—Another Random Variable......Page 225
The ``Margin of Error\'\' and Confidence Intervals......Page 226
Confidence Intervals for Means......Page 227
Example: Simulation Output......Page 228
A Weight Survey in Davis......Page 229
One More Point About Interpretation......Page 230
General Formation of Confidence Intervals from Approximately Normal Estimators......Page 231
Example: Standard Errors of Combined Estimators......Page 232
Derivation......Page 233
Simulation Example Again......Page 234
Interpretation......Page 235
Planning Ahead......Page 236
Independent Samples......Page 237
Dependent Samples......Page 239
Example: Machine Classification of Forest Covers......Page 241
And What About the Student-t Distribution?......Page 242
Example: Amazon Links......Page 243
Example: Master\'s Degrees in CS/EE......Page 244
One More Time: Why Do We Use Confidence Intervals?......Page 245
Introduction to Significance Tests......Page 249
The Basics......Page 250
General Testing Based on Normally Distributed Estimators......Page 251
The Notion of ``p-Values\'\'......Page 252
Exact Tests......Page 253
Example: Improved Light Bulbs......Page 254
Example: Test Based on Range Data......Page 255
R Computation......Page 256
Example: Improved Light Bulbs......Page 257
History of Significance Testing, and Where We Are Today......Page 258
The Basic Fallacy......Page 259
What to Do Instead......Page 260
Decide on the Basis of ``the Preponderance of Evidence\'\'......Page 261
Example: Assessing Your Candidate\'s Chances for Election......Page 262
Example: Guessing the Number of Raffle Tickets Sold......Page 265
Method of Moments......Page 266
Method of Maximum Likelihood......Page 267
Method of Moments......Page 268
R\'s mle() Function......Page 269
More Examples......Page 271
What About Confidence Intervals?......Page 273
Why Divide by n-1 in s2?......Page 274
Tradeoff Between Variance and Bias......Page 277
More on the Issue of Independence/Nonindependence of Samples......Page 278
Basic Ideas in Density Estimation......Page 281
Histograms......Page 282
Kernel-Based Density Estimation......Page 284
Bayesian Methods......Page 286
How It Works......Page 288
Empirical Bayes Methods......Page 289
Arguments Against Use of Subjective Priors......Page 290
What Would You Do? A Possible Resolution......Page 291
Simultaneous Inference Methods......Page 295
The Bonferonni Method......Page 296
Scheffe\'s Method......Page 297
Example......Page 298
Other Methods for Simultaneous Inference......Page 299
Introduction to Model Building......Page 301
Estimated Mean......Page 302
The Bias/Variance Tradeoff......Page 303
Implications......Page 305
The Chi-Square Goodness of Fit Test......Page 306
Kolmogorov-Smirnov Confidence Bands......Page 307
Bias Vs. Variance—Again......Page 308
Robustness......Page 309
Real Populations and Conceptual Populations......Page 310
The Goals: Prediction and Understanding......Page 313
Example Applications: Software Engineering, Networks, Text Mining......Page 314
Adjusting for Covariates......Page 315
Example: Marble Problem......Page 316
Estimating That Relationship from Sample Data......Page 317
Example: Baseball Data......Page 320
Multiple Regression: More Than One Predictor Variable......Page 322
Example: Baseball Data (cont\'d.)......Page 323
Interaction Terms......Page 324
Meaning of ``Linear\'\'......Page 325
Point Estimates and Matrix Formulation......Page 326
Approximate Confidence Intervals......Page 328
Example: Baseball Data (cont\'d.)......Page 330
Example: Baseball Data (cont\'d.)......Page 331
What Does It All Mean?—Effects of Adding Predictors......Page 333
Model Selection......Page 335
The Overfitting Problem in Regression......Page 336
Methods for Predictor Variable Selection......Page 337
What About the Assumptions?......Page 339
Regression Diagnostics......Page 340
Example: Prediction of Network RTT......Page 341
Example: OOP Study......Page 342
Slutsky\'s Theorem......Page 347
Why It\'s Valid to Substitute s for......Page 348
The Theorem......Page 349
Example: Square Root Transformation......Page 352
Example: Confidence Interval for 2......Page 353
Example: Confidence Interval for a Measurement of Prediction Ability......Page 356
Basic Methodology......Page 357
Computation in R......Page 358
General Applicability......Page 359
Why It Works......Page 360
Nonlinear Parametric Regression Models......Page 361
Classification = Regression......Page 362
Optimality of the Regression Function for 0-1-Valued Y (optional section)......Page 363
Logistic Regression: a Common Parametric Model for the Regression Function in Classification Problems......Page 364
The Logistic Model: Motivations......Page 365
Example: Forest Cover Data......Page 367
What If Y Doesn\'t Have a Marginal Distribution?......Page 368
Methods Based on Estimating mY;X(t)......Page 369
Nearest-Neighbor Methods......Page 370
Kernel-Based Methods......Page 372
The Naive Bayes Method......Page 373
Support Vector Machines (SVMs)......Page 374
CART......Page 375
Comparison of Methods......Page 377
Symmetric Relations Among Several Variables......Page 378
How to Calculate Them......Page 379
Log-Linear Models......Page 381
The Data......Page 382
The Models......Page 383
Parameter Estimation......Page 384
Simpson\'s (Non-)Paradox......Page 385
Basic Concepts......Page 389
A Cautionary Tale: the Bus Paradox......Page 391
Length-Biased Sampling......Page 392
Probability Mass Functions and Densities in Length-Biased Sampling......Page 393
Renewal Theory......Page 394
Intuitive Derivation of Residual Life for the Continuous Case......Page 395
Age Distribution......Page 396
Example: Disk File Model......Page 398
Example: Memory Paging Model......Page 399
Conditional Pmfs and Densities......Page 403
Conditional Expected Value As a Random Variable......Page 404
Famous Formula: Theorem of Total Expectation......Page 405
Example: Trapped Miner......Page 406
Example: Analysis of Hash Tables......Page 408
Simulation of Random Vectors......Page 410
Mixture Models......Page 411
Transform Methods......Page 413
Generating Functions......Page 414
Moment Generating Functions......Page 415
Sums of Independent Poisson Random Variables Are Poisson Distributed......Page 416
Random Number of Bits in Packets on One Link......Page 417
Other Uses of Transforms......Page 418
Vector Space Interpretations (for the mathematically adventurous only)......Page 419
Conditional Expectation As a Projection......Page 420
Proof of the Law of Total Expectation......Page 422
Example: Finite Random Walk......Page 427
Long-Run Distribution......Page 428
Derivation of the Balance Equations......Page 429
Solving the Balance Equations......Page 430
Periodic Chains......Page 431
Description......Page 432
Initial Analysis......Page 433
Going Beyond Finding......Page 434
The Model......Page 436
Going Beyond Finding......Page 438
Example: Slotted ALOHA......Page 439
Going Beyond Finding......Page 440
Simulation of Markov Chains......Page 442
Continuous-Time Markov Chains......Page 444
Continuous-Time Birth/Death Processes......Page 445
Some Mathematical Conditions......Page 446
Example: Random Walks......Page 447
Finding Hitting and Recurrence Times......Page 448
Example: Tree-Searching......Page 450
Introduction......Page 455
Steady-State Probabilities......Page 456
Distribution of Residence Time/Little\'s Rule......Page 457
M/M/c......Page 460
M/M/2 with Heterogeneous Servers......Page 461
Cell Communications Model......Page 463
Stationary Distribution......Page 464
Nonexponential Service Times......Page 465
Markov Property......Page 467
Reversible Markov Chains......Page 468
Making New Reversible Chains from Old Ones......Page 469
Example: Queues with a Common Waiting Area......Page 470
Closed-Form Expression for  for Any Reversible Markov Chain......Page 471
Tandem Queues......Page 472
Jackson Networks......Page 473
Open Networks......Page 474
Closed Networks......Page 475
Terminology and Notation......Page 477
Matrix Addition and Multiplication......Page 478
Linear Independence......Page 479
Eigenvalues and Eigenvectors......Page 480
Correspondences......Page 483
First Sample Programming Session......Page 484
Second Sample Programming Session......Page 488
Third Sample Programming Session......Page 490
The Reduce() Function......Page 491
S3 Classes......Page 492
Handy Utilities......Page 493
Graphics......Page 495
Complex Numbers......Page 496
Installation and Use......Page 499
Basic Structures......Page 500
Example: Simple Line Graphs......Page 501
Example: Census Data......Page 503
What\'s Going on Inside......Page 510
For Further Information......Page 513