Introduction to Probability for Computing

Author: Prof. Mor Harchol-Balter

Published: 2024

Publisher: Cambridge University Press (CUP)

ISBN: 978-1-009-30907-3

Buy it via Amazon.com

Buy it via Cambridge University Press

Instructors can get a free Examination Copy from CUP.

Additional book resources (slides, figures, etc.) available from CUP.

Book contains 400 exercises as well as numerous examples.

Endorsements:

Probability theory has become indispensable in computer science. It is at the core of machine learning and statistics, where one often needs to make decisions under stochastic uncertainty. It is also integral to computer science theory, where most algorithms today are randomized algorithms, involving random coin flips. It is a central part of performance modeling in computer networks and systems, where probability is used to predict delays, schedule jobs and resources, and provision capacity.

This book gives an introduction to probability as it is used in computer science theory and practice, drawing on applications and current research developments as motivation and context. This is not a typical counting and combinatorics book, but rather it is a book centered on distributions and how to work with them. Every topic is driven by what computer science students need to know. For example, the book covers distributions that come up in computer science, such as heavy-tailed distributions. There is a large emphasis on variability and higher moments, which are very important in empirical computing distributions. Computer systems modeling and simulation are also discussed, as well as statistical inference for estimating parameters of distributions. Much attention is devoted to tail bounds, such as Chernoff bounds. Chernoff bounds are used for confidence intervals and also play a big role in the analysis of randomized algorithms, which themselves comprise a large part of the book. Finally, the book covers Markov chains, as well as a bit of queueing theory, both with an emphasis on their use in computer systems analysis.

0 Preface pdf

Part I: Fundamentals and Probability on Events

1 Before We Start ... Some Mathematical Basics pdf
1.1 Review of Simple Series
1.2 Review of Double Integrals and Sums
1.3 Fundamental Theorem of Calculus
1.4 Review of Taylor Series and Other Limits
1.5 A Little Combinatorics
1.6 Review of Asymptotic Notation
1.7 Exercises
2 Probability on Events pdf
2.1 Sample Space and Events
2.2 Probability Defined on Events
2.3 Conditional Probabilities on Events
2.4 Independent Events
2.5 Law of Total Probability
2.6 Bayes' Law
2.7 Exercises

Part II: Discrete Random Variables

3 Common Discrete Random Variables   pdf
3.1 Random Variables
3.2 Common Discrete Random Variables
3.2.1 The Bernoulli Random Variable
3.2.2 The Binomial Random Variable
3.2.3 The Geometric Random Variable
3.2.4 The Poisson Random Variable
3.3 Multiple Random Variables and Joint Probabilities
3.4 Exercises
4 Expectation   pdf
4.1 Expectation of a Discrete Random Variable
4.2 Linearity of Expectation
4.3 Conditional Expectation
4.4 Computing Expectations via Conditioning
4.5 Simpson's Paradox
4.6 Exercises
5 Variance, Higher Moments, and Random Sums   pdf
5.1 Higher Moments
5.2 Variance
5.3 Alternative Definitions of Variance
5.4 Properties of Variance
5.5 Summary Table for Discrete Distributions
5.6 Covariance
5.7 Central Moments
5.8 Sum of a Random Number of Random Variables
5.9 Tails
5.9.1 Simple Tail Bounds
5.9.2 Stochastic Dominance
5.10 Jensen's Inequality
5.11 Inspection Paradox
5.12 Exercises
6 z-Transforms   pdf
6.1 Motivating Examples
6.2 The Transform as an Onion
6.3 Creating the Transform: Onion Building
6.4 Getting Moments: Onion Peeling
6.5 Linearity of Transforms
6.6 Conditioning
6.7 Using z-Transforms to Solve Recurrence Relations
6.8 Exercises

Part III: Continuous Random Variables

7 Continuous Random Variables: Single Distribution   pdf
7.1 Probability Density Functions
7.2 Common Continuous Distributions
7.3 Expectation, Variance, and Higher Moments
7.4 Computing Probabilities by Conditioning on a R.V.
7.5 Conditional Expectation and the Conditional Density
7.6 Exercises
8 Continuous Random Variables: Joint Distributions   pdf
8.1 Joint Densities
8.2 Probability Involving Multiple Random Variables
8.3 Pop Quiz
8.4 Conditional Expectation for Multiple Random Variables
8.5 Linearity and Other Properties
8.6 Exercises
9 Normal Distribution    pdf
9.1 Definition
9.2 Linear Transformation Property
9.3 The Cumulative Distribution Function
9.4 Central Limit Theorem
9.5 Exercises
10 Heavy Tails: The Distributions of Computing    pdf
10.1 Tales of Tails
10.2 Increasing versus Decreasing Failure Rate
10.3 UNIX Process Lifetime Measurements
10.4 Properties of the Pareto Distribution
10.5 The Bounded-Pareto Distribution
10.6 Heavy Tails
10.7 The Benefits of Active Process Migration
10.8 From the 1990s to the 2020s
10.9 Pareto Distributions Are Everywhere
10.10 Summary Table for Continuous Distributions
10.11 Exercises
11 Laplace Transforms    pdf
11.1 Motivating Example
11.2 The Transform as an Onion
11.3 Creating the Transform: Onion Building
11.4 Getting Moments: Onion Peeling
11.5 Linearity of Transforms
11.6 Conditioning
11.7 Combining Laplace and z-Transforms
11.8 One Final Result on Transforms
11.9 Exercises

Part IV: Computer Systems Modeling and Simulation

12 The Poisson Process    pdf
12.1 Review of the Exponential Distribution
12.2 Relating the Exponential Distribution to the Geometric
12.3 More Properties of the Exponential
12.4 The Celebrated Poisson Process
12.5 Number of Poisson Arrivals during a Random Time
12.6 Merging Independent Poisson Processes
12.7 Poisson Splitting
12.8 Uniformity
12.9 Exercises
13 Generating Random Variables for Simulation    pdf
13.1 Inverse Transform Method
13.1.1 The Continuous Case
13.1.2 The Discrete Case
13.2 Accept-Reject Method
13.2.1 Discrete Case
13.2.2 Continuous Case
13.2.3 A Harder Problem
13.3 Readings
13.4 Exercises
14 Event-Driven Simulation    pdf
14.1 Some Queueing Definitions
14.2 How to Run a Simulation
14.3 How to Get Performance Metrics from Your Simulation
14.4 More Complex Examples
14.5 Exercises

Part IV: Computer Systems Modeling and Simulation

15 Estimators for Mean and Variance    pdf
15.1 Point Estimation
15.2 Sample Mean
15.3 Desirable Properties of a Point Estimator
15.4 An Estimator for Variance
15.4.1 Estimating the Variance when the Mean is Known
15.4.2 Estimating the Variance when the Mean is Unknown
15.5 Estimators Based on the Sample Mean
15.6 Exercises
15.7 Acknowledgment
16 Classical Statistical Inference   pdf
16.1 Towards More General Estimators
16.2 Maximum Likelihood Estimation
16.3 More Examples of ML Estimators
16.4 Log Likelihood
16.5 MLE with Data Modeled by Continuous Random Variables
16.6 When Estimating More than One Parameter
16.7 Linear Regression
16.8 Exercises
16.9 Acknowledgment
17 Bayesian Statistical Inference    pdf
17.1 A Motivating Example
17.2 The MAP Estimator
17.3 More Examples of MAP Estimators
17.4 Minimum Mean Square Error Estimator
17.5 Measuring Accuracy in Bayesian Estimators
17.6 Exercises
17.7 Acknowledgment

Part VI: Tail Bounds and Applications

18 Tail Bounds   pdf
18.1 Markov's Inequality
18.2 Chebyshev's Inequality
18.3 Chernoff Bound
18.4 Chernoff Bound for Poisson Tail
18.5 Chernoff Bound for Binomial
18.6 Comparing the Different Bounds and Approximations
18.7 Proof of Chernoff Bound for Binomial: Theorem 18.4
18.8 A (Sometimes) Stronger Chernoff Bound for Binomial
18.9 Other Tail Bounds
18.10 Appendix: Proof of Lemma 18.5
18.11 Exercises
19 Applications of Tail Bounds: Confidence Intervals and Balls and Bins    pdf
19.1 Interval Estimation
19.2 Exact Confidence Intervals
19.2.1 Using Chernoff Bounds to Get Exact Confidence Intervals
19.2.2 Using Chebyshev Bounds to Get Exact Confidence Intervals
19.2.3 Using Tail Bounds to Get Exact Confidence Intervals in General Settings
19.3 Approximate Confidence Intervals
19.4 Balls and Bins
19.5 Remarks on Balls and Bins
19.6 Exercises
20 Hashing Algorithms   pdf
20.1 What is Hashing?
20.2 Simple Uniform Hashing Assumption
20.3 Bucket Hashing with Separate Chaining
20.4 Linear Probing and Open Addressing
20.5 Cryptographic Signature Hashing
20.6 Remarks
20.7 Exercises

Part VII: Randomized Algorithms

21 Las Vegas Randomized Algorithms    pdf
21.1 Randomized versus Deterministic Algorithms
21.2 Las Vegas versus Monte Carlo
21.3 Review of Deterministic Quicksort
21.4 Randomized Quicksort
21.5 Randomized Selection and Median-Finding
21.6 Exercises
22 Monte Carlo Randomized Algorithms    pdf
22.1 Randomized Matrix-Multiplication Checking
22.2 Randomized Polynomial Checking
22.3 Randomized Min-Cut
22.4 Related Readings
22.5 Exercises
23 Primality Testing      pdf
23.1 Naive Algorithms
23.2 Fermat's Little Theorem
23.3 Fermat Primality Test
23.4 Miller-Rabin Primality Test
23.4.1 A New Witness of Compositeness
23.4.2 Logic Behind the Miller-Rabin Test
23.4.3 Miller-Rabin Primality Test
23.5 Readings
23.6 Appendix: Proof of Theorem 23.9
23.7 Exercises

Part VIII: Discrete-Time Markov Chains

24 Discrete-Time Markov Chains: Finite-State    pdf
24.1 Our First Discrete-Time Markov Chain
24.2 Formal Definition of a DTMC
24.3 Examples of Finite-State DTMCs
24.3.1 Repair Facility Problem
24.3.2 Umbrella Problem
24.3.3 Program Analysis Problem
24.4 Powers of P: n-Step Transition Probabilities
24.5 Limiting Probabilities
24.6 Stationary Equations
24.7 The Stationary Distribution Equals the Limiting Distribution
24.8 Examples of Solving Stationary Equations
24.9 Exercises
25 Ergodicity for Finite-State Discrete-Time Markov Chains    pdf
25.1 Some Examples on Whether the Limiting Distribution Exists
25.2 Aperiodicity
25.3 Irreducibility
25.4 Aperiodicity plus Irreducibility Implies Limiting Distribution
25.5 Mean Time Between Visits to a State
25.6 Long-Run Time Averages
25.6.1 Strong Law of Large Numbers
25.6.2 A Bit of Renewal Theory
25.6.3 Equality of the Time Average and Ensemble Average
25.7 Summary of Results for Ergodic Finite-State DTMCs
25.8 What If My DTMC Is Irreducible but Periodic?
25.9 When the DTMC Is Not Irreducible
25.10 An Application: PageRank
25.10.1 Problems with Real Web Graphs
25.10.2 Google's Solution to Dead Ends and Spider Traps
25.10.3 Evaluation of the PageRank Algorithm and Practical Considerations
25.11 From Stationary Equations to Time-Reversibility Equations
25.12 Exercises
26 Discrete-Time Markov Chains: Infinite-State    pdf
26.1 Stationary = Limiting
26.2 Solving Stationary Equations in Infinite-State DTMCs
26.3 A Harder Example of Solving Stationary Equations in Infinite-State DTMCs
26.4 Ergodicity Questions
26.5 Recurrent versus Transient: Will the Fish Return to Shore?
26.6 Infinite Random Walk Example
26.7 Back to the Three Chains and the Ergodicity Question
26.8 Why Recurrence Is Not Enough
26.9 Ergodicity for Infinite-State Chains
26.10 Exercises
27 A Little Bit of Queueing Theory   pdf
27.1 What Is Queueing Theory?
27.2 A Single-Server Queue
27.3 Kendall Notation
27.4 Common Performance Metrics
27.5 Another Metric: Throughput
27.5.1 Throughput for M/G/k
27.5.2 Throughput for Network of Queues with Probabilistic Routing
27.5.3 Throughput for Network of Queues with Deterministic Routing
27.5.4 Throughput for Finite Buffer
27.6 Utilization
27.7 Introduction to Little's Law
27.8 Intuitions for Little's Law
27.9 Statement of Little's Law
27.10 Proof of Little's Law
27.11 Important Corollaries of Little's Law
27.12 Exercises
References and Index   pdf

The content above has been sourced from the book page of Professor Mor Harchol-Balter.
I highly recommend accessing her personal website for additional high-quality learning resources.
Please note that I do not own the copyright to the content presented here.

Search This Blog

Academic Resource Forum