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.
Table of Contents
- 0 Preface and Contents 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 V: Statistical Inference
- 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
Back to Mor's Home Page .