Introduction to Probability for Computing

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