Main
Main
I Probability 1
1 Lecture 1 3
1.1 The Basics of Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Sample Space and Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Axioms of Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5.1 Definition of a Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5.2 Types of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.6 Example (Set Theory) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.6.1 Venn Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6.2 Set Containment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6.3 Probability Calculations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6.4 For both uniform and non-uniform sample space . . . . . . . . . . . . . . 7
2 Lecture 2 9
2.1 Combinatorics: The Art of Counting . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Permutations: When Order Matters . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Combinations: When Order Doesn’t Matter . . . . . . . . . . . . . . . . . 9
2.2 Solved Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Problem 1: Distributing Teachers to Schools . . . . . . . . . . . . . . . . 10
2.2.2 Problem 2: Distributing Indistinguishable Objects (Stars and Bars) . . . 12
2.3 The Multinomial Coefficient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 Lecture 3 15
3.1 Stars and Bars: Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1.1 Distributions into Non-Empty Boxes . . . . . . . . . . . . . . . . . . . . . 16
3.1.2 Distribution Allowing Empty Boxes . . . . . . . . . . . . . . . . . . . . . 17
3.1.3 Equation-Based Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4 Lecture 4 19
4.1 Sample Space and Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Probability Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 Axioms of Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4 Theorem I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.5 Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.6 Theorem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.7 Sum of First (n − 1) Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . . 25
4.8 General Formula for Binomial Coefficient . . . . . . . . . . . . . . . . . . . . . . 26
iii
iv CONTENTS
5 Lecture 5 27
5.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2 Conditional Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.3 Sample Space in a collection of all basic outcomes ω ∈ Ω of some experiment. . . 28
5.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.5 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
6 Lecture 7 33
6.1 Mutual Independence, Pairwise Independence, Conditional Independence . . . . 33
6.2 Example: Tossing a Fair Die . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
6.3 Conditional Probability and Intersection . . . . . . . . . . . . . . . . . . . . . . . 34
6.4 Axioms of Conditional Probability . . . . . . . . . . . . . . . . . . . . . . . . . . 34
6.5 Sample Space and Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.6 Independence of Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.7 Example: Drawing Balls without Replacement . . . . . . . . . . . . . . . . . . . 36
6.8 Conditional Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.9 Law of Total Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.10 Bayes’ Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.11 Example: Box and Balls Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.12 Disjoint Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.13 Unions of Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.14 Partitions of the Sample Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.15 Example: Tossing a Fair Coin Twice . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.16 Example: Mutually Independent Events . . . . . . . . . . . . . . . . . . . . . . . 39
7 Lecture 8 41
7.1 Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
7.1.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
7.1.2 Probability Mass Function (PMF) . . . . . . . . . . . . . . . . . . . . . . 41
7.1.3 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
7.1.4 Probability Mass Function (PMF) . . . . . . . . . . . . . . . . . . . . . . 42
7.2 Experiment: Waiting Time for First Head . . . . . . . . . . . . . . . . . . . . . . 42
7.2.1 Probability Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7.3 X is a Random Variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7.3.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
7.3.2 Properties of CDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
8 Lecture 9 45
8.1 Probability Example: Uniform over (0, 1) . . . . . . . . . . . . . . . . . . . . . . 45
8.1.1 Facts about the uniform distribution on (0, 1) . . . . . . . . . . . . . . . . 45
8.1.2 Probability of a single point . . . . . . . . . . . . . . . . . . . . . . . . . . 45
8.2 Continuous Random Variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
8.3 Discrete Random Variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
8.3.1 Expectation of a Discrete Random Variable . . . . . . . . . . . . . . . . . 46
8.4 Example: Tossing Coins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
8.4.1 Tossing 2 Coins: Number of Heads X . . . . . . . . . . . . . . . . . . . . 46
8.4.2 Tossing 10 Coins: Observed Sample . . . . . . . . . . . . . . . . . . . . . 47
8.5 Indicator Random Variable Example . . . . . . . . . . . . . . . . . . . . . . . . . 47
8.6 Expectation Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
8.6.1 Expectation of a Fair Die . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
8.6.2 Expectation of a Biased Coin (Two Tosses) . . . . . . . . . . . . . . . . . 47
CONTENTS v
9 Lecture 10 49
9.1 Random Variable in Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
9.2 Variance of RV X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
9.2.1 For function Y=[x+a] — a ∈ R . . . . . . . . . . . . . . . . . . . . . . . . 55
10 Lecture 11 57
10.0.1 Linearity of Expectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
10.1 Variance Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
10.2 Expectation and Variance of Linear Combinations . . . . . . . . . . . . . . . . . 58
10.2.1 Example: Toss a fair coin twice . . . . . . . . . . . . . . . . . . . . . . . . 59
10.3 Example: Picking Balls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
10.4 Example: Toss a Coin Once . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
10.5 Bernoulli Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
10.6 Example 2: Toss one biased coin n times . . . . . . . . . . . . . . . . . . . . . . . 60
10.6.1 Case n = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
11 Lecture 12 61
11.1 Families of Random Variables (RVs) — Bernoulli RV . . . . . . . . . . . . . . . . 61
11.1.1 1. Xi ∼ Bern(p) [One Trial, One Parameter] . . . . . . . . . . . . . . . . . 61
11.1.2 2. n sets of identical & mutually independent trials . . . . . . . . . . . . . 62
11.1.3 Binomial RV and PMF . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
11.1.4 3. Outcomes of n trials . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
11.1.5 4. Cumulative Distribution Function (CDF) for Binomial RV . . . . . . . 63
11.1.6 5. Probability Calculation for Different Paths . . . . . . . . . . . . . . . . 64
11.2 Multiplication of probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
11.2.1 7. Further Expansion and Multiplication of Probabilities . . . . . . . . . . 64
12 Lecture 13 67
12.1 The Binomial Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
12.1.1 Probability Mass Function (PMF) . . . . . . . . . . . . . . . . . . . . . . 67
12.1.2 The Bernoulli Distribution (n = 1) . . . . . . . . . . . . . . . . . . . . . . 67
12.1.3 Expected Value of a Bernoulli Random Variable . . . . . . . . . . . . . . 68
12.2 Binomial Probability Mass Function (PMF) . . . . . . . . . . . . . . . . . . . . . 68
12.2.1 Path Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
12.3 Tree Diagram for n = 2 Trials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
12.4 Probability of a Single Path (Sequence) . . . . . . . . . . . . . . . . . . . . . . . 69
12.5 Total Probability of y Successes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
12.5.1 Definition of the Event En,y . . . . . . . . . . . . . . . . . . . . . . . . . . 69
12.5.2 Calculating P (En,y ) using Disjoint Union . . . . . . . . . . . . . . . . . . 69
12.5.3 Final PMF Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
12.6 Example: Coin Toss 3 Times (n = 3) . . . . . . . . . . . . . . . . . . . . . . . . . 70
12.6.1 Outcomes and Probabilities for n = 3 . . . . . . . . . . . . . . . . . . . . 70
12.7 Expected Value of a Bernoulli Trial . . . . . . . . . . . . . . . . . . . . . . . . . . 70
12.8 Conditions for Binomial Distribution . . . . . . . . . . . . . . . . . . . . . . . . . 70
12.8.1 Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
12.8.2 Identically Distributed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
12.8.3 General Formulation and Paths . . . . . . . . . . . . . . . . . . . . . . . . 71
12.9 Scenario: Events are NOT i.i.d. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
13 Lecture 14 73
vi CONTENTS
14 Lecture 15 77
14.1 Probability Distributions and Memoryless Property . . . . . . . . . . . . . . . . . 77
14.1.1 Calculation of P [G > t] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
14.1.2 Image 1: Memoryless Property - Conditional Probability . . . . . . . . . . 78
14.1.3 Memoryless Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
14.1.4 Expected Value and Variance of Bernoulli RV . . . . . . . . . . . . . . . . 80
14.1.5 Random Variables and Expected Value Formula . . . . . . . . . . . . . . 80
14.1.6 Image 3: Law of Expectation (LOE) and Law of Variance (LOV) . . . . . 81
14.1.7 Covariance and Independence . . . . . . . . . . . . . . . . . . . . . . . . . 81
14.1.8 Image 0: Conditional Probability of Geometric RV (Shift) . . . . . . . . . 82
15 Lecture 16 83
15.1 Probability Measure and Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
15.1.1 Experiment and Sample Space . . . . . . . . . . . . . . . . . . . . . . . . 83
15.1.2 Probability Measure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
15.1.3 Axioms of Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
15.1.4 Countable Collection of Sets . . . . . . . . . . . . . . . . . . . . . . . . . 84
15.2 Concept of Random Variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
15.2.1 Discrete Random Variable . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
15.2.2 Continuous Random Variable . . . . . . . . . . . . . . . . . . . . . . . . . 84
15.3 Cumulative Distribution Function (CDF) . . . . . . . . . . . . . . . . . . . . . . 85
15.4 Joint Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
15.4.1 Example: Two Fair Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
15.5 Joint Distribution Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
15.6 Independent Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
15.7 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
15.8 i.i.d Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
15.9 Independent Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
15.10Expectation and Covariance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
15.11Continuous Random Variable X . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
16 Lecture 17 89
16.1 Derivation of Expected Value E[Y ] . . . . . . . . . . . . . . . . . . . . . . . . . . 89
16.1.1 Expansion of the Summation . . . . . . . . . . . . . . . . . . . . . . . . . 89
16.1.2 Formal Manipulation of the Term . . . . . . . . . . . . . . . . . . . . . . . 89
16.2 Completing the Derivation of E[Y ] . . . . . . . . . . . . . . . . . . . . . . . . . . 90
16.2.1 Algebraic Manipulation (from i = 1) . . . . . . . . . . . . . . . . . . . . . 90
16.2.2 Factoring out np . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
16.2.3 Change of Index and Variable Substitution . . . . . . . . . . . . . . . . . 90
16.2.4 Recognizing the Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . 91
16.2.5 Final Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
16.3 Derivation of E[Y (Y − 1)] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
16.3.1 Setup and Initial Summation . . . . . . . . . . . . . . . . . . . . . . . . . 91
16.3.2 Algebraic Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
16.3.3 Factoring out n(n − 1)p2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
16.3.4 Change of Index and Variable Substitution . . . . . . . . . . . . . . . . . 92
16.3.5 Recognizing the Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . 92
16.3.6 Final Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
16.4 Variance of the Binomial Distribution Y ∼ Bin(n, p) . . . . . . . . . . . . . . . . 93
16.4.1 Substitution of Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
16.5 Expected Value of the Poisson Distribution . . . . . . . . . . . . . . . . . . . . . 93
16.5.1 Derivation of E[X] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
CONTENTS vii
II Statistical Inference 99
36 Lectures 7 and 8: Likelihood Ratio Test and Large Sample Z Test 213
36.1 Simple and Composite Alternative Hypotheses . . . . . . . . . . . . . . . . . . . 213
36.2 Likelihood Ratio Test Statistic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
36.3 Level of Significance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
36.4 Further Remarks on Likelihood Ratio Test . . . . . . . . . . . . . . . . . . . . . . 214
36.5 Example Setup (i.i.d Sample) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
36.6 Likelihood Ratio in this Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
36.7 Likelihood Function and MLE (Detailed) . . . . . . . . . . . . . . . . . . . . . . 216
36.8 Derivation of Likelihood Ratio (Final Form) . . . . . . . . . . . . . . . . . . . . . 218
36.9 Likelihood Ratio and Rejection Region (Detailed) . . . . . . . . . . . . . . . . . . 219
36.10Recall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
36.11Final Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
41 Lectures 17 and 18: Markov Chains and Naive Bayes Classification 273
41.1 Introduction to Stochastic Processes . . . . . . . . . . . . . . . . . . . . . . . . . 273
41.2 Transition Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
41.2.1 Weather Prediction Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
41.2.2 Non-Markovian Counter-example . . . . . . . . . . . . . . . . . . . . . . . 274
41.2.3 Two-Step Transition Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 274
41.3 Gambler’s Ruin Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
xvi CONTENTS
Probability
1
Chapter 1
Lecture 1
Sample Space (S): This is the list of all possible outcomes that can happen. It’s like
the entire menu at a restaurant. We use curly braces {} to list the outcomes. The total
number of outcomes is called the size of the sample space, written as |S|.
Event (E): An event is a specific outcome or a set of outcomes that we are interested in.
It’s a subset of the sample space. This is like choosing what you want to eat from the
menu.
Example: Tossing Two Coins If we toss two different coins, say a penny and a nickel,
what are all the possible results? Let ’H’ stand for Heads and ’T’ for Tails.
The Sample Space is all possible combinations:
So, there’s a 75% chance of getting at least one head when you toss two coins.
3
4 CHAPTER 1. LECTURE 1
⇒ RANDOM experiment
RISK
⇓
SEVERAL OUTCOMES
W1 , W2 , . . . , Wn , . . .
Set of all possible outcomes
⇓
Sample Space of the Random experiment:
Ω = {W1 , W2 , . . . , Wn }
⇓
Events: Subset ⊆ Ω in the sample space
E1 ⊆ Ω, E2 ⊆ Ω
Example:
Outcome has at least one heads:
EH = {H1 H2 , H1 T2 , T1 H2 } ⊆ Ω
Coin Toss model is an important model in the Binomial model which we’ll be discussing
in the future.
When there is more than 1 outcome, then you’ll generate “Risk”.
0 ≤ P (E) ≤ 1 (4)
0 ≤ P (E) ≤ 1 (5)
This means that probabilities can never be negative and cannot exceed 1. - Example:
When tossing a coin, P (Head) = 0.5, which lies between 0 and 1.
P (Ω) = 1 (6)
This reflects the fact that something in the sample space must occur. - Example: For a
dice roll, Ω = {1, 2, 3, 4, 5, 6}, so
∞
X
⇒ P (E1 ∪ E2 ∪ . . . ∪ En ∪ . . .) = P (Ei ) (9)
i=1
Where:
Ek ∩ Ej = ∅ for k ̸= j (10)
Ek ⊆ Ω, Ej ⊆ Ω (11)
In words, the probability of the union of mutually exclusive events is the sum of their
probabilities.
- Example: In a dice roll, let E1 = {1} and E2 = {2}. Since E1 ∩ E2 = ∅, we have:
1 1 2
P (E1 ∪ E2 ) = P (E1 ) + P (E2 ) = 6 + 6 = 6 (12)
These three axioms form the basis of probability theory. All other results, such as conditional
probability, Bayes’ theorem, and distributions, can be derived from these axioms.
1.4 Example
Ω = {1, 2, 3, 4, 5, 6, 7, 8, 9} (13)
A = {1, 2, 3}, B = {3, 4, 5}, C = {7, 8} (14)
A ⊂ Ω, B ⊂ Ω, C⊂Ω (15)
|A| = 3, |B| = 3, |C| = 2 (16)
Complement of A:
Ac = {w ∈ Ω | w ∈
/ A} = {4, 5, 6, 7, 8, 9} (17)
Venn Diagram:
6 CHAPTER 1. LECTURE 1
B
1,2 A 3 4,5 C 7,8
A B
F ⊆E (26)
|E|
P (E) = (29)
|Ω|
Here, |E| is the number of favorable outcomes, and |Ω| is the total number of possible outcomes.
In a non-uniform sample space, outcomes may not be equally likely. In that case:
X
P (E) = P ({w}) (30)
w∈E
This allows us to calculate probabilities in both uniform (equal likelihood) and non-uniform
(unequal likelihood) cases.
8 CHAPTER 1. LECTURE 1
Chapter 2
Lecture 2
Derivation
Let’s say we want to pick and arrange 3 people (k = 3) from a group of 10 (n = 10).
9
10 CHAPTER 2. LECTURE 2
Analogy: The Pizza Toppings You’re ordering a pizza and can choose 3 toppings from
a list of 10. Does it matter if you choose ”pepperoni, mushrooms, and olives” versus ”olives,
pepperoni, and mushrooms”? No! The final pizza is the same.
The formula for calculating the number of combinations of selecting k items from a set of n
items is:
n n!
n Ck = = (34)
k k!(n − k)!
Derivation
The key idea is that a combination is just a permutation where we remove the overcounting
caused by order. For our 3 pizza toppings, there are 3! = 3 × 2 × 1 = 6 ways to arrange them.
A permutation counts all 6 of these as different, but a combination counts them as one.
So, to get the number of combinations, we take the number of permutations and divide by
the number of ways to arrange the selected items (k!).
n Pk n!/(n − k)! n!
n Ck = = = (35)
k! k! k!(n − k)!
Part (i): How many ways can this be done with no conditions?
This is a problem about choices. Let’s think from the perspective of each teacher.
3. Add back ways where at least TWO schools are empty: (We subtracted these
cases twice in the last step, so we add them back once).
Part (iii): How many ways to assign exactly 2 teachers to each school?
This question is about partitioning. We are splitting 8 distinct teachers into 4 distinct groups
(the schools), with each group having exactly 2 members. Here’s how we can count this:
For the third school, we have 4 teachers left. We choose 2. The number of ways is 4
2 .
For the fourth school, we have 2 teachers left. We choose 2. The number of ways is 2
2 .
To get the total number of ways, we multiply the possibilities for each step:
8 6 4 2
Total Ways = × × × (41)
2 2 2 2
8! 6! 4! 2!
= × × × (42)
2!6! 2!4! 2!2! 2!0!
12 CHAPTER 2. LECTURE 2
Notice that many terms cancel out (like the 6! and 4!):
8! 6! 4! 2!
= × × × (43)
2!6!
2!4! 2!2! 2!0!
We are left with (since 0! = 1):
8! 40320 40320
Total Ways = = = = 2520 (44)
2! · 2! · 2! · 2! 2·2·2·2 16
The Analogy Imagine the n objects are ”stars” (∗). To divide them into k groups, you need
k − 1 ”bars” (|).
n = 6 objects (stars) and k = 3 groups. We need k − 1 = 2 bars to divide them.
Consider this arrangement:
∗| ∗ ∗| ∗ ∗∗ (45)
This represents: Group 1 gets 1 star, Group 2 gets 2 stars, and Group 3 gets 3 stars. (1+2+3 =
6)
The Logic Since every group must have at least one object, we can imagine our 6 stars laid
out in a row with spaces between them:
∗ ∗ ∗ ∗ ∗ ∗ (46)
There are n − 1 = 5 possible spaces where we can place our bars. To create 3 groups, we need
to choose 2 of these spaces to place our bars. The number of ways to do this is:
n−1 6−1 5
= = (47)
k−1 3−1 2
5 5! 5×4
= = = 10 (48)
2 2!(5 − 2)! 2×1
There are 10 ways to do this.
General Formula The problem is equivalent to finding the number of positive integer solu-
tions to the equation:
x1 + x2 + · · · + xk = n, where xi ≥ 1 (49)
Let’s make a substitution to simplify the condition. Let yi = xi − 1. Since xi ≥ 1, we know
that yi ≥ 0. Substituting xi = yi + 1 into the equation:
(y1 + 1) + (y2 + 1) + · · · + (yk + 1) = n (50)
y1 + y2 + · · · + yk + k = n (51)
y1 + y2 + · · · + yk = n − k (52)
Now we are distributing n − k items into k groups where the groups are allowed to be empty
(yi ≥ 0). This is a standard stars and bars problem with n − k ”stars” and k − 1 ”bars”. The
total number of arrangements is:
(n − k) + (k − 1) n−1
= (53)
k−1 k−1
2.3. THE MULTINOMIAL COEFFICIENT 13
Example 2.3.1. Distribute 8 teachers among 4 schools with each school receiving 2 teachers.
The number of possible assignments is
8!
= 2520. (55)
2! 2! 2! 2!
14 CHAPTER 2. LECTURE 2
Chapter 3
Lecture 3
x1 + x2 + · · · + xr = n. (56)
⋆ ⋆ ⋆| ⋆ | ⋆ ⋆ (58)
Stars represent the items to be distributed. Bars act as dividers to separate the items into
distinct groups or bins. The number of ways to distribute n identical items into k distinct bins
is given by the formula:
n+k−1
(59)
k−1
This comes from choosing k − 1 positions for the bars among n + k − 1 total positions (stars
plus bars).
x1 + x2 + x3 = 6? (60)
⋆ ⋆ ⋆| ⋆ | ⋆ ⋆ (62)
⋆ ⋆ ⋆ — ⋆ — ⋆ ⋆
15
16 CHAPTER 3. LECTURE 3
y1 + y2 + · · · + yr = n − r. (63)
x1 + x2 + x3 = 6? (65)
x1 + x2 + x3 = 6. (67)
1. Place one item in each of the k boxes to satisfy the requirement that no box is empty.
This uses up k items.
2. Now, distribute the remaining n − k items into the k boxes with no restrictions (boxes
can receive zero or more items).
3. The number of ways to distribute n − k identical items into k distinct boxes is given by
the standard stars and bars formula:
(n − k) + k − 1 n−1
= (69)
k−1 k−1
This counts the number of non-negative integer solutions to y1 +y2 +· · ·+yk = n−k, where
yi represents the additional items in box i, and the total items in box i is xi = yi + 1 ≥ 1.
Conditions
This formula assumes n ≥ k, because you need at least k items to put one in each box.
If n < k, it’s impossible to have at least one item in each box, so the number of ways is 0.
3.1. STARS AND BARS: BASIC IDEA 17
y1 + y2 + · · · + yk = n − k. (70)
⋆ ⋆ ⋆ — ⋆ — ⋆ ⋆
⋆ ⋆ — ⋆ — ⋆
x + y = 5, x, y ∈ N. (75)
The solutions are (1, 4), (2, 3), (3, 2), (4, 1), so there are 4 solutions.
Example 3.1.7. Find the number of solutions to
x + y + z = 6, x, y, z ∈ N. (76)
Substitute x′ = x − 1, y ′ = y − 1, z ′ = z − 1. Then
x′ + y ′ + z ′ = 3. (77)
Lecture 4
Sample Space:
Set of all possible outcomes. It is denoted by Ω
w ∈ Ω (w is an element of Ω)
E is a subset of a sample space.
E⊆Ω
P : F → [0, 1] (79)
where F is the collection of events. For finite experiments, F can be taken as the power set 2Ω .
Remark 4.2.1. If Ω is finite and all outcomes are equally likely, then for any E ⊆ Ω,
|E|
P (E) = . (80)
|Ω|
2. P(Ω) = 1
19
20 CHAPTER 4. LECTURE 4
E ∩E
i j = ∅ i ̸= j
E1 ∩ E2 = ∅
E1 ∩ E3 = ∅
E2 ∩ E4 = ∅
then
∞ ∞
!
[ X
P Ei = P(Ei ) (81)
i=1 i=1
( ∞
S
i=1 Ei ) : It is a disjoint union. (A disjoint union is when you combine multiple sets,
and none of them share any elements. That means each item in the union comes from
exactly one set — no duplicates, no overlap.)
Set operation: S P
Arithmetic operation:
4.4 Theorem I
A⊆Ω (82)
c
P (A ) = 1 − P (A) (83)
Proof
Ω
Ac
A⊆Ω (84)
Ac ⊆ Ω (85)
c
A∩A =∅ (86)
A ∪ Ac = Ω (87)
Note:
4.5. THEOREM 2 21
4.5 Theorem 2
Let A ⊆ Ω, B ⊆ Ω.
Proof
Ω
A A∩B B
A = (A ∩ B c ) ∪ (A ∩ B) (93)
Also,
P (A ∩ B c ) = P (A) − P (A ∩ B) (95)
Note that:
A ∪ B = (A ∩ B c ) ∪ B (96)
P (A ∪ B) = P (A ∩ B c ) + P (B) (97)
Rearranging,
P (A ∩ B c ) = P (A ∪ B) − P (B) (98)
Each outcome:
ω1 = H1 ∈ Ω1 , ω2 = T1 ∈ Ω1 (102)
1
P ({H1 }) = P (EH1 ) = p = (106)
2
1
P ({T1 }) = P (ET1 ) = q = (107)
2
Eϕ = ϕ ⊆ Ω1 (109)
So,
P ({H1 , T1 }) = P ({H1 }) + P ({T1 }) (114)
X
P (E) = P ({ω}) (117)
ω∈E
4.6. THEOREM 3 23
Ω2 = {H1 H2 , H1 T2 , T1 H2 , T1 T2 } (118)
1
P ({H1 H2 }) = P ({H1 T2 }) = P ({T1 H2 }) = P ({T1 T2 }) = (119)
4
Let:
A = {H1 T2 , T1 H2 } (120)
Then:
1 1 1
P (A) = P ({H1 T2 }) + P ({T1 H2 }) = + = (121)
4 4 2
Also:
|A| = 2, |Ω2 | = 4 (122)
|A| 2 1
P (A) = = = (123)
|Ω2 | 4 2
Note: This only holds true for a uniform sample space where all the outcomes are equally
likely.
4.6 Theorem 3
Let E ⊆ Ω, then:
|E|
P (E) = (124)
|Ω|
For a uniform sample space.
In general (for any sample space):
X
P (E) = P ({ω}) [General] (125)
ω∈E
Since the sample space Ω is uniform, all outcomes ω ∈ Ω are equally likely:
1
P ({ωj }) = for all ωj ∈ Ω (127)
|Ω|
Let:
Ω = {ω1 , ω2 , . . . , ω|Ω| } (128)
Then:
1 = P (Ω) = P ({ω1 }) + P ({ω2 }) + . . . + P ({ω|Ω| }) (129)
Since all probabilities are equal:
1
1 = y + y + . . . + y = y · |Ω| ⇒ y = (131)
|Ω|
Thus:
1
P ({ωj }) = for all ωj ∈ Ω (132)
|Ω|
Let the event E = {ω1 , ω2 , . . . , ω|E| }. Then:
X X 1 1 1 1
P (E) = P ({ω}) = = + + ... + (133)
|Ω| |Ω| |Ω| |Ω|
ω∈E ω∈E
|E|
P (E) = (135)
|Ω|
E c = No student from North in placement cell (i.e., all 3 are from South) (138)
So,
c 30 50
|E | = , |Ω| = (139)
3 3
30
c |E c | 3
P (E ) = = 50 (140)
|Ω|
3
Hence,
30
c 3
P (E) = 1 − P (E ) = 1 − 50
(141)
3
50
− 30
3 3
P (E) = 50
(142)
3
4.7. SUM OF FIRST (n − 1) NATURAL NUMBERS 25
Then:
|E1 | |E2 | |E3 |
P (E) = P (E1 ) + P (E2 ) + P (E3 ) = + + (147)
|Ω| |Ω| |Ω|
Where:
20 30
|E1 | = (148)
1 2
20 30
|E2 | = (149)
2 1
20
|E3 | = (150)
3
50
|Ω| = (151)
3
Example: Handshakes
Problem: An MBA class has 50 students. How many handshakes occur if each student shakes
hands with every other student?
Let total students be n = 50.
n 50
Total handshakes = = (152)
2 2
n n! n(n − 1)(n − 2)! n(n − 1)
= = = (153)
2 2!(n − 2)! 2(n − 2)! 2
Note: This is not the same as the sum of the first n natural numbers:
n
Sn = 1 + 2 + 3 + . . . + (n − 1) ̸= (154)
2
But in fact,
n(n − 1)
Sn−1 = (155)
2
50
Graphical Insight into 2
50
= 49 + 48 + 47 + · · · + 2 + 1 + 0 (158)
2
This shows that choosing 2 people out of 50 can be visualized as summing all unique pairs:
- Person 1 shakes hands with 49 people - Person 2 shakes hands with 48 new people (excluding
the one already counted), and so on.
Hence,
X 49
50 50 · 49
= k= (159)
2 2
k=0
Lecture 5
5.1 Example
Roll a pair of fair dice. Find the probability that the second die shows a higher value than the
first die.
Direct counting
x
P (E2>1 ) = =? (163)
|Ω|
x
= (164)
36
6 2x
1= + (165)
36 36
2x 6
=1− (166)
36 36
2x 36 − 6
= (167)
36 36
2x 30
= (168)
36 36
30
2x = × 36 (169)
36
27
28 CHAPTER 5. LECTURE 5
2x = 30 (170)
30
x= (171)
2
x = 15 (172)
Ω
F ⊆ Ω and E ⊆ Ω
E F P (E ∩ F ) = ∅
P (E ∩ F )
P (E|F ) = conditional probability of E given F = (176)
P (F )
where P (F ) ̸= 0 and 0 < P (F ) ≤ 1 (177)
P(E) = P(E|Ω)
5.4. EXAMPLE 29
P(E ∩ F)
EE∩F F
5.4 Example
Toss a Fair Die
Ω = {1, 2, 3, 4, 5, 6} (181)
E = {4} (182)
F = {4, 5, 6} (183)
E 4 F
4 4,5,6
P (E ∩ F )
P (E|F ) = (184)
P (F )
1
P (E ∩ F ) = (186)
6
30 CHAPTER 5. LECTURE 5
3 1
P (F ) = = (187)
6 2
1 6 1
P (E|F ) = × = (188)
6 3 3
1 2 3 time
E1 occurs E2 E3
P (E ∩ F ) P (F ∩ E) P (E ∩ F )
P (E|F ) = and P (F |E) = = (189)
P (F ) P (E) P (E)
P (E1 ∩ E2 ) P (E3 ∩ F )
P (E
1)
(193)
P (E
1)
P (F )
(194)
P (E3 ∩ F )
P (E1 ∩ E2 ) (195)
(( (((
P (E1 ∩ E2 )
(
( (( (((
(196)
P (E3 ∩ F ) (197)
(198)
P (E1 ∩ E2 ∩ E3 ) (199)
5.5 Definition
Event E ⊆ Ω and F ⊆ Ω are independent events if:
0 < P (F ) ≤ 1
E F
0 < P (E) ≤ 1
E ∩ F = ∅ =⇒ P (E ∩ F ) = P (∅) = 0 (204)
LHS = P (E ∩ F ) = 0 (205)
RHS = P (E)P (F ) ̸= 0 (206)
LHS ̸= RHS (207)
1. 0 ≤ P (E) ≤ 1
2. P (Ω) = 1
PΩ (E ∩ F )
PF (E) = P (E|F ) = (209)
PΩ (F )
0 < PΩ (F ) ≤ 1 (210)
32 CHAPTER 5. LECTURE 5
Chapter 6
Lecture 7
Events
E1 = {1, 2, 3, 4} (212)
E2 = {4, 3, 6} (213)
E3 = {1, 2, 6} (214)
Example Calculation
Let us compute the probability of event {4}:
1
P ({4}) = (216)
6
4 3 2
P (E1 ) = , P (E2 ) = , P (E1 ∩ E2 ) = (217)
6 6 6
4 3 12 1
P (E1 ) · P (E2 ) = · = = (218)
6 6 36 3
2 1
P (E1 ∩ E2 ) = = (219)
6 3
Here, P (E1 ∩ E2 ) = P (E1 ) · P (E2 ).
33
34 CHAPTER 6. LECTURE 7
Now consider:
1 4 3 3 36 1
P (E1 ∩ E2 ∩ E3 ) = , P (E1 )P (E2 )P (E3 ) = · · = = (220)
6 6 6 6 216 6
So the events are mutually independent.
But:
1 1
P ({4}) = = ̸ (221)
6 3
So some conditional independence relations may not hold.
P (E ∩ F )
PF (E) = P (E | F ) = (222)
P (F )
Properties
1. 0 ≤ PF (E) ≤ 1
2. PF (Ω) = 1
E1 E2
P (E ∩ F )
PF (E) = (224)
P (F )
Axiom 1: Boundedness
For any event E ⊆ Ω,
0 ≤ PF (E) ≤ 1 (225)
Justification:
Since E ∩ F ⊆ F , we have:
0 ≤ P (E ∩ F ) ≤ P (F ) (226)
6.5. SAMPLE SPACE AND EVENTS 35
Axiom 2: Normalization
The conditional probability of the entire sample space Ω, given F , is 1:
P (Ω ∩ F ) P (F )
PF (Ω) = = =1 (229)
P (F ) P (F )
Conclusion: The conditional probability function PF satisfies all properties of a probability
measure on the reduced sample space F .
Ω
E1 F E2
(E1 ∩ F ) (E2 ∩ F )
Axiom 3: Additivity
If E1 ∩ E2 = ∅, then:
PF (E1 ∪ E2 ) = PF (E1 ) + PF (E2 ) (230)
Proof:
By the definition of conditional probability:
P ((E1 ∪ E2 ) ∩ F )
PF (E1 ∪ E2 ) = (231)
P (F )
Since E1 ∩ E2 = ∅, their intersections with F are also disjoint:
So:
P ((E1 ∪ E2 ) ∩ F ) = P (E1 ∩ F ) + P (E2 ∩ F ) (233)
Hence:
P (E1 ∩ F ) P (E2 ∩ F )
PF (E1 ∪ E2 ) = + = PF (E1 ) + PF (E2 ) (234)
P (F ) P (F )
Conclusion: The conditional probability measure PF satisfies all three axioms of a proba-
bility function on the sample space restricted to F .
P (E ∩ F ) = P (E) · P (F ). (235)
E E∩F F
5 5
P (White) = = 12 , P (Black) = = 12 . (238)
10 10
If a ball is drawn and not replaced, the probability for the second draw changes. For example,
if the first draw is white, then
4 5
P (Second White) = , P (Second Black) = . (239)
9 9
Thus, the two draws are not independent.
6.8. CONDITIONAL PROBABILITY 37
5W
5B
P (E ∩ F )
P (E|F ) = , P (F ) > 0. (240)
P (F )
F E∩F E
P (E|Fj ) P (Fj )
P (Fj |E) = Pn . (242)
i=1 P (E|Fi ) P (Fi )
Remark 6.10.1. Bayes’ theorem updates prior probabilities P (Fi ) into posterior probabilities
P (Fi |E) after observing evidence E.
Choose Box
1 1 1
3 3 3
4 2 3 3 2 4
6 6 6 6 6 6
E1 E2
E E∩F F
F1 F2 F3
Start
H T
HH HT TH TT
Lecture 8
X:Ω→R (252)
7.1.1 Example
Pick students at random from MBA class and measure their height.
7.1.3 Definition
A random variable (RV) is a function
X:Ω→R (257)
41
42 CHAPTER 7. LECTURE 8
That is:
P [X = xi ] = P (Ei ) (259)
Properties of PMF
1. p(x) ≥ 0 ∀x ∈ SX
P
2. x∈SX p(x) = 1
This means the first k − 1 tosses are Tails, and the k-th toss is a Head:
Let:
P (Tails) = q = (1 − p), P (Heads) = p (262)
Therefore:
P (Ek ) = q · q · · · · · q · p = q k−1 p, k ∈ {1, 2, 3, . . . } (263)
For a fair coin, p = q = 21 .
FX (x) = P (X ≤ x) (267)
7.3.1 Example
Toss a fair coin twice:
S = {H1 H2 , H1 T2 , T1 H2 , T1 T2 } (268)
Let X = Number of Heads.
X ∈ SX = {0, 1, 2} (269)
P (X = 0) = 41 , P (X = 1) = 12 , P (X = 2) = 1
4 (270)
So, the PMF of X is:
PX (x) = P (X = x) (271)
1. FX (x) is right-continuous.
3. limx→+∞ FX (x) = 1
Lecture 9
45
46 CHAPTER 8. LECTURE 9
Explanation: Continuous random variables do not have probabilities for single points. Prob-
abilities are assigned only to intervals. There is no probability mass function (PMF), only a
probability density function (PDF).
Interpretation: Expectation is the weighted average of all possible values, weighted by their
probabilities.
1 1 1
P (X = 0) = , P (X = 1) = , P (X = 2) = . (290)
4 2 4
Expectation:
1 1 1
E P [X] = 0 · +1· +2· =1 (291)
4 2 4
Case 2: Biased Coin (Q)
1 1 1
Q(X = 0) = , Q(X = 1) = , Q(X = 2) = . (292)
3 3 3
Expectation:
1 1 1
E Q [X] = 0 · +1· +2· =1 (293)
3 3 3
Observation: Different distributions can yield the same expected value.
8.5. INDICATOR RANDOM VARIABLE EXAMPLE 47
Lecture 10
PX (x) = P (X = x) (305)
Where,x ∈ SX
PX (x) = P (X ≤ x) (306)
X
E P [X] = xP [X = x] (308)
x∈SX
EX = [X = x] (309)
X
= xP [EX ] (310)
x∈SX
49
50 CHAPTER 9. LECTURE 10
Sample Space = Ω2
Ω2 = {H1 H2 = ω1 , H1 T2 = ω2 , T1 H2 = ω3 , T1 T2 = ω4 } (311)
X = 2, E2 = {H1 H2 , } (312)
X = 1, E1 = {H1 T2 , T1 H2 } (313)
X = 0, E0 = {T1 T2 } (314)
X
[Link][X] = P (ω) × ω (315)
ω∈Ω2
(Outcome Based)
In a fair coin toss every trial is mutually independent of each other and are statistically
identical.
X
E P [X] = P (ω) × ω = P (ω1 ) × (ω1 ) + P (ω2 ) × (ω2 ) + P (ω3 ) × (ω3 ) + P (ω4 ) × (ω4 ) (316)
ω∈Ω2
1 1 1 1
= ×2+ ×1+ ×1+ ×0 (317)
4 4 4 4
2 1 1
= + + =1 (318)
4 4 4
X X
2.E P [X] = xP (EX ) = xP (X = x) (319)
x∈SX x∈SX
( Event Based)
1
P (E2 ) = P {H1H 2} = (321)
4
2
P (E2 ) = P {H1 T2 , T1 H2 } = (322)
4
1
P (E0 ) = P {T1 T2 } = (323)
4
P 1 2 1
EX = 2( ) + 1( ) + 0( ) = 1 (324)
4 4 4
9.1. RANDOM VARIABLE IN FUNCTION 51
[ [
P (Ω2 ) = P (E0 ) P (E1 ) P (E2 ) (325)
Example:2
DAY 1 DAY 2 DAY 3 DAY 4 DAY 5 DAY 6 DAY 7 DAY 8 DAY 9 DAY 10
10 1 5 2 1 20 10 2 1 15
A person deposits coins of different sum with a banker for 10 days. The deposits made are
listed in the above [Link] the expectation of the event
1. Outcome Based:
X
P
EX = P (ω) × (ω) (326)
x∈§X
Ω = {10 = ω1 , 1 = ω2 , 5 = ω3 , 2 = ω4 , 1 = ω5 , 20 = ω6 , 10 = ω7 , 2 = ω8 , 1 = ω9 , 5 = ω1 0} (327)
1 1 1 1 1 1 1 1 1
= (10) + (1) + (5) + (2) + (1) + (20) + (5) + (10) + (2) + (1) (328)
10 10 10 10 10 1 10 10 10 10
57
= = 5.7 (329)
10
[Link] Based:
X
P
EX = xP (EX ) (330)
x∈SX
1 1 1 1 1 1 1 1 1 1
1( + + ) + 2( + ) + 5( + ) + 10( + ) + 20( ) (331)
10 10 10 10 10 10 1 10 10 10
3 + 4 + 10 + 20 + 20 57
= = = 5.7 (332)
10 10
Function: y = g(x)
Y = g(X) (334)
X
E(Y ) = E[g(x)] = g(x)P (X = x) (335)
x∈SX
X X X
yP (Y = y) = P (ω)y(ω) = g(x)P [X = x] (336)
y∈SY ω∈Ω x∈SX
52 CHAPTER 9. LECTURE 10
X X
P (ω)y(ω) = P (ω)g[X(x)] (337)
ω∈Ω ω∈ω
Ex = [X = x] = {ω ∈ Ω|X(ω) = x} (339)
Outcome Based:
X
EP [g(x)] = P (ω)g(X(ω) (342)
ω∈Ω
If g(x) = x = X
EP [X] = xP(X = x) (343)
x∈SX
X
EP [X] = P (ω) × ω (344)
ω∈Ω
Example:
PMF of RV X is given by :
SX = {5, 7} (345)
1
P (X = 5) = (346)
3
2
P (X = 7) = (347)
3
2/3
P (X = x)
1/3
0
5 7
x
9.1. RANDOM VARIABLE IN FUNCTION 53
1
P (X = 5) = P (6X = 30) = (348)
3
2
P (X = 7) = P (7X = 42) = (349)
3
2/3
P (y = 6x)
1/3
0
30 42
x
Probability (Height) of events does not change in scaling.
P (Y = y) = P (X = x) (353)
[Link] of RV X :
Y = X+9
PMF of X + 9: Y = h(x) = (x + 9)
1
P (X = 5) = P (X + 9 = 14) = (354)
3
2
P (X = 7) = P (X + 9 = 16) = (355)
3
2/3
1/3
0
14 16
x
1)
EP [S] = P [X = 3] = 1 (357)
y = ax + b (359)
Y = aX + b (361)
X
EP [Y ] = P (ω)y(ω) (362)
ω∈Ω
X
= P (ω)[a × (ω) + b] (363)
ω∈Ω
X X
a[ P (ω) × ω] + b( P (ω)) (364)
ω∈Ω ω∈Ω
X
= a × EP [X] + b(1), [ P (ω) = 1] (365)
ω∈Ω
Linearity of Expectation:
[EP [aX + b] = aEP [X] + b] (366)
Example:
SX = {−1, 1} (367)
−1
p(X = −1) = (368)
2
1
P (X = 1) = (369)
2
9.2. VARIANCE OF RV X 55
X
EP = xp(x) (370)
ω∈Ω
1 1
= −1( ) + 1( ) (371)
2 2
=0 (372)
9.2 Variance of RV X
Variance is given by: X
2
σX = varX = (x − µx )2 P (X = x) (373)
x∈SX
[E − E = 0] (386)
σy2 = σx+a
2
= σx2 = E[(x − µx )2 ] = σx2 (391)
56 CHAPTER 9. LECTURE 10
Chapter 10
Lecture 11
= E (X − µX )2 = E[X 2 ] − µ2X
(395)
X
E[g(X)] = g(x)P (X = x) (2nd moment of RV X) (396)
x∈SX
—
p q
σX = SD(X) = Var(X) = E[X 2 ] − µ2X (398)
—
Note:
The variance is invariant under shifting.
57
58 CHAPTER 10. LECTURE 11
=⇒ V (Y ) = a2 V (X) (403)
—
V (T ) = V (aX + bY + c) (407)
—
Let
D = aX + bY (408)
P (X = 0) = 14 , P (X = 1) = 12 , P (X = 2) = 1
4 (419)
SX = {0, 1, 2} (420)
100
2 100 · 99 99
P (Y = 0) = 200 = = . (423)
200 · 199
2
398
100
2 100 · 99 99
P (Y = 2) = 200 = = . (424)
200 · 199
2
398
99 99 200
P (Y = 1) = 1 − − = . (425)
398 398 398
Thus,
P (Y = 0) = 41 , P (Y = 1) = 12 , P (Y = 2) = 14 . (426)
(
1, with probability p = P (H),
X= (428)
0, with probability q = 1 − p = P (T ).
60 CHAPTER 10. LECTURE 11
Thus,
X ∼ Bernoulli(p). (431)
—
p = P (H), q = 1 − p = P (T ). (432)
Each toss is mutually independent:
Each toss does not statistically influence the other tosses. (433)
10.6.1 Case n = 2
Ω2 = {H1 H2 , H1 T2 , T1 H2 , T1 T2 } (434)
|Ω2 | = 22 = 4 (435)
In general, for n tosses:
Ωn = {H1 H2 . . . Hn , . . . , T1 T2 . . . Tn } (436)
|Ωn | = 2n (437)
Chapter 11
Lecture 12
Probability
p
q
x
0 1
p+q =1 (440)
X : Ω → {0, 1}
i
{H, T } = {E, E }c
p+q =1
P (X = x) = p qx 1−x
61
62 CHAPTER 11. LECTURE 12
If identical: pj = pk = p (443)
Sample space:
SYn = {0, 1, 2, . . . , n} (446)
Yn : Ωn → SYn (447)
Yn ∼ Binomial(n, p) (449)
n y n−y
P (Yn = y) = p q , y ∈ {0, 1, . . . , n} (455)
y
11.1. FAMILIES OF RANDOM VARIABLES (RVS) — BERNOULLI RV 63
Start
H1 T1
H2 T2 H2 T2
H1 H2 → 2 ⇒ p2 (456)
H1 T2 → 1 ⇒ pq (457)
T1 H2 → 1 ⇒ qp (458)
T1 T2 → 0 ⇒ q 2 (459)
H1 H2 H3 = p3
H1 H2 T3 = p2 q
H1 T2 H3 = p2 q
H1 T2 T3 = pq 2
(463)
T1 H2 H3 = p2 q
T1 H2 T3 = pq 2
T1 T2 H3 = q 2 p
T1 T2 T3 = q 3
This tree shows different possible sequences of trials, each with an associated probability.
k
X
FY (k) = P (Yn ≤ k) = P (Yn = y) (464)
y=0
64 CHAPTER 11. LECTURE 12
P (ω k ) = pq q n−q (465)
The number of paths that lead to a particular outcome is given by:
n
k= (466)
q
The probability of each path is the same, as shown by:
Lecture 13
If x = 0 (Failure): P (X = 0) = p q = q.
1
0 1
67
68 CHAPTER 12. LECTURE 13
Interpretation:
n
The term accounts for the fact that the final result of the path matters, not the
y
p H2 ) ⇒ P = p2
(H1 , H2=
H1
q
T2 (H1 , T2 )=⇒ P = pq
p
Start
p H2 (T1 , H2 )=⇒ P = qp
q
T1
q
T2 (T1 , T2 )=⇒ P = q 2
12.4. PROBABILITY OF A SINGLE PATH (SEQUENCE) 69
Since the probability of *every* single path ωpn,y with y successes is the same,
P (ωpn,y ) = py q n−y , we have:
Xk
y n−y
P (En,y ) = p q (495)
p=1
This is the Probability Mass Function (PMF) for the Binomial Random Variable Yn :
n y
P (Yn = y) = p (1 − p)n−y (499)
y
E[X] = 1 · p + 0 · q = p (502)
12.8.1 Independence
The trials must be Independent and Identically Distributed (i.i.d.).
Independence:The outcome of one trial does not affect the outcome of any other trial.
Incorrect Summation (Example of what NOT to do in Independent Events):
P (E1 ∩ E2 ∩ E3 ) ̸= P (E1 ) + P (E2 ) + P (E3 ) + . . . (503)
Each path gives a value of y that is possible (i.e., y is the number of successes in that
path).
Lecture 14
x n
lim 1+ → ex (507)
n→∞ n
x n
1− → e−x (508)
n
x n
ln = 1 − (509)
n
x
loge ln = n loge 1 − (510)
n
−x
= ∞ loge 1 + = ∞ loge (1) = ∞(0) (511)
n
x
= lim n loge 1 − (512)
n→∞ n
loge (1) 0
= = (513)
(1/n) 0
loge (1 − nλ )
⇒ lim loge ln = lim (514)
n→∞ n→∞ (1/n)
Apply L’Hopital’s Rule:
d λ . d
⇒ loge (1 − ) (1/n) (515)
dn n dn
λ
λ
n2 (1− n ) −λ
= lim 1 = lim (516)
n→∞ − 2 n→∞ (1 − λ )
n n
λ n
∴ lim 1 − = e−λ (518)
n→∞ n
X ∼ Geom(p) (519)
73
74 CHAPTER 13. LECTURE 14
X = Number of trials required until 1st success event occurs. Once the 1st success occurs, you stop.
(520)
P [X = n] = q n−1 p, n = 1, 2, 3, . . . (522)
Xj ∼ Bern(p) (523)
p→0, np→λ
(3) Bin(n, p) −−−−−−−→ Pois(λ)
e−λ λk
Z ∼ Pois(λ), P [Z = k] = , λ ≥ 0, k = 0, 1, 2, . . . (526)
k!
GR = Number of trials required until the Rth success event occurs. (527)
q − 1 R (q−R)
P [GR = q] = p q (529)
R−1
P [GR = q] = P [At (q−1)th trial we see (R−1) success events, and at the q th trial we see Rth trial]
(530)
X ∼ Bin(n, p) (532)
n k n−k
P [X = k] = p q , k = 0, 1, 2, . . . , n (533)
k
Recall:
a
b > 1 ⇒ a > b
a
a > 0, b > 0 ⇒ b > 1 if and only if a > b (534)
a
b <1⇒a<b
75
n − (R − 1) p
⇒ P [X = R] = P [X = R − 1] × × (535)
R q
(R − 1)!(n − R + 1)! p
= × (536)
R!(n − R)! q
P [X = R] (n − R + 1) p
= × (537)
P [X = R − 1] R q
Lecture 15
Memoryless Property (MP): Only geometric distribution has Ageless property / Anti-aging
property (in discrete case).
G ∼ Geom(p) (541)
P [G = k] = q (k−1) p (542)
[k = 1, 2, 3, . . .] (543)
q p q p q p
The coin does not give you preference [Ageless property of a coin - coin does not age].
Event [G > t]:
[G > t] = [G = t + 1] ∪ [G = t + 2] ∪ [G = t + 3] ∪ [G = t + 4] ∪ . . . (544)
A
P [G > t] =3 P [G = t + 1] + P [G = t + 2] + P [G = t + 3] + . . . (546)
∞
X
= P [G = t + k] (547)
k=1
77
78 CHAPTER 14. LECTURE 15
= q p q + q1 + q2 + . . .
t 0
(551)
∞
X 1 1
qj = = (552)
1−q p
j=0
1
= qtp · (553)
p
= qt (554)
P [G > t] = q t (555)
[Till time t the event E has not occurred].
Body
Tail
k
1 2 33
t= 4 5
If does not matter how much time have you waited. The coin won’t give you preference.
Waited extra ∆ units of time, but not arrived.
Using the general conditional probability formula:
q t+∆
= = q∆ (563)
qt
= P [G > ∆] (564)
t=0
P [G > (t + ∆) | G > t] =⇒ P [G > (0 + ∆) | G > 0]
0 1 2 (t − 1) t (t +(∆
1) − 1)∆ Priya
Past history
Waited t units of time, but not arrived.
t=0 ∆−1 ∆ Gowathi
∆
Sample space Ω = {G > 0}.
Distribution says probability is the same.
Application → Fusing of a bulb, Markov chain (Google search engine).
—
80 CHAPTER 14. LECTURE 15
Expectation E(Xj ):
1
X
= xP [Xj = x] (Event based) (569)
x=0
=0·q+1·p=p (570)
E(Xj ) = p (571)
Variance Var(Xj ):
Var(X) = E(X 2 ) − µ2 = E[(X − µ)2 ] (572)
(
12 = 1 w.p. p
Xj2 = (573)
02 = 0 w.p. q
E(Xj2 ) = 1 · p + 0 · q = p (574)
p
q
0 1
µj = p
—
X
= xP [X = x] (Event based) (577)
x∈SX
—
14.1. PROBABILITY DISTRIBUTIONS AND MEMORYLESS PROPERTY 81
Expectation E(Y ):
n
X X n k (n−k)
µY = E(Y ) = yP (Y = y) = k p q (579)
k
y∈SY k=0
LOE Pn Pn
Using LOE: E(Y ) = j=1 E(Xj ) = j=1 p
E(Y ) = p + p + · · · + p = np (580)
| {z }
n times
Variance Var(Y ):
n
LOV
X
Var(Y ) = Var(Xj ) only when they are Independent (581)
j=1
n
X
Var(Y ) = pq = npq (582)
j=1
q/p
Waited t units of time for event of occur and it has not occurred.
k starts from (t + 1)
t+1 t+2
Distribution remain the same. It only shifts.
Chapter 15
Lecture 16
F ⊆ P(Ω) (590)
where F is the set of events (measurable sets).
P : F → [0, 1] (592)
P (Ω) = 1 (593)
3. Countable Additivity: For a countable collection of disjoint sets {Ai } ⊆ F such that
Ai ∩ Aj = ∅, i ̸= j, (595)
we have !
[ X
P Ai = P (Ai ) (596)
i i
83
84 CHAPTER 15. LECTURE 16
A1 , A2 , A3 , . . . , AN , . . . (597)
Infinite: A , A , A , . . . , A , A , . . .
1 2 3 N N +1
X : Ω −→ R (598)
The PMF (Probability Mass Function) maps the random variable to the interval [0, 1]:
and Z ∞
p(x) dx = 1 (603)
−∞
fX (x)
x
P (X ≤ x)
(a)
P (X > x) = 1 − FX (x), since [X > x] = [X ≤ x]c (606)
(c)
lim FX (x) = 1 (608)
x→+∞
(d)
lim FX (x) = 0 (609)
x→−∞
P : R2 −→ [0, 1] (610)
such that
P (X = x, Y = y) = P (X = x ∩ Y = y) = P (x, y) (611)
The joint PMF satisfies: XX
P (x, y) = 1 (612)
x y
Marginal PMF of X:
X
PX (X = xi ) = PX,Y (xi , y) ⇒ Row Sum (615)
y∈SY
Marginal PMF of Y:
X
PY (Y = yj ) = PX,Y (x, yj ) ⇒ Column Sum (616)
x∈SX
Example:
1
PX,Y (2, 1) = (618)
36
1 1
PX (2) = , PY (1) = (619)
36 36
15.7 Example
Pick 2 balls with replacement from an urn containing 4 white and 6 black balls.
( (
1, if the first ball is white 1, if the second ball is white
X1 = X2 = (621)
0, if the first ball is black 0, if the second ball is black
X1 , X2 ∈ {0, 1} (622)
Joint Probability Table:
15.8. I.I.D RANDOM VARIABLES 87
and
n
Y
fX1 ,X2 ,...,Xn (x1 , x2 , . . . , xn ) = fXi (xi ) (624)
i=1
µ = E(X) (632)
σ 2 = V ar(X) (633)
p
σ = SD(X) = + V ar(X) (634)
88 CHAPTER 15. LECTURE 16
µ
Tail Tail
Bell
−σ +σ
x
" #
1 x−µ 2
1
PDF of X ⇒ fX (x) = √ exp − (635)
σ 2π 2 σ
Lecture 17
n
X
E[Y ] = i · P (Y = i) (637)
i=0
n
X n i n−i
= i· pq (638)
i
i=0
E[Y ] = 0 · P (Y = 0) + 1 · P (Y = 1) + 2 · P (Y = 2) + . . . + n · P (Y = n) (639)
n 0 n−0 n 1 n−1 n 2 n−2
=0· p q +1· p q +2· p q + ... (640)
0 1 2
n(n − 1) 2 n−2
= 0 + 1 · npq n−1 + 2 · p q + ... (641)
2
= 0 + npqn−1 + n(n − 1)p2 qn−2 + . . . (642)
n
X n!
E[Y ] = i· pi q n−i (643)
i!(n − i)!
i=0
Note on Simplification: Since the term for i = 0 is 0, the sum can start from i = 1. For
n·(n−1)!
i ≥ 1, we use the identity i · i!1 = (i−1)!
1
and n!
i! = i·(i−1)! .
89
90 CHAPTER 16. LECTURE 17
n
X n!
E[Y ] = i· pi q n−i (644)
i!(n − i)!
i=1
n
X n!
= pi q n−i (645)
(i − 1)!(n − i)!
i=1
n
X (n − 1)!
= np pi−1 q n−i (646)
(i − 1)!(n − i)!
i=1
The summation term is the sum of the PMF of a Bin(n − 1, p) distribution, which must equal
1.
n−1
X n − 1
pk q (n−1)−k = (p + q)n−1 = 1n−1 = 1 (648)
k
k=0
n
X n!
E[Y ] = pi q n−i (651)
(i − 1)!(n − i)!
i=1
m
X m!
E[Y ] = np pk q m−k (654)
k![m − k]!
k=0
m
X m
E[Y ] = np pk q m−k (655)
k
k=0
The sum of the probabilities for *any* distribution must equal 1. Specifically, by the Binomial
Theorem, the summation is the expansion of (p + q)m :
m
X m k m−k
p q = (p + q)m (656)
k
k=0
E[Y ] = np (660)
n
pi q n−i :
Substituting the PMF P (Y = i) = i
n
X n i n−i
E[Y (Y − 1)] = i(i − 1) pq (662)
i
i=0
92 CHAPTER 16. LECTURE 17
n
X n!
E[Y (Y − 1)] = i(i − 1) · pi q n−i (663)
i!(n − i)!
i=2
1 1
We use the identity i(i − 1) · i! = (i−2)! and i(i − 1) · n!/i! = n(n − 1)(n − 2)!/(i − 2)!:
n
X n!
E[Y (Y − 1)] = pi q n−i (664)
(i − 2)!(n − i)!
i=2
Now, let m = n − 2.
m
X m!
E[Y (Y − 1)] = n(n − 1)p2 pk q m−k (667)
k![m − k]!
k=0
Since p + q = 1:
E[Y (Y − 1)] = n(n − 1)p2 (p + q)m (669)
A common method for discrete distributions is to use the factorial moment E[Y (Y − 1)]:
E[Y ] = np
E[Y (Y − 1)] = n(n − 1)p 2
X ∼ Pois(λ) (681)
e−λ λi
P [X = i] = , for i = 0, 1, 2, . . . , ∞ (682)
i!
∞
X e−λ λi
= i· (685)
i!
i=1
Factor out the constant term e−λ and simplify the factorial term i/i! = 1/(i − 1)!:
∞
X λi
= e−λ (686)
(i − 1)!
i=1
∞
−λ
X λk
= λe (688)
k!
k=0
∞
X λk
= eλ (689)
k!
k=0
To simplify the calculation of E[X 2 ], we first calculate the second factorial moment
E[X(X − 1)]:
Var[X] = E[X(X − 1)] + E[X] − (E[X])2 (1) (695)
16.6. VARIANCE OF THE POISSON DISTRIBUTION 95
e−λ λi
Substituting the PMF P (X = i) = i! :
∞
X e−λ λi
E[X(X − 1)] = i(i − 1) · (697)
i!
i=0
The terms for i = 0 and i = 1 are zero, so we start the summation from i = 2.
∞
X e−λ λi
= i(i − 1) · (698)
i!
i=2
E[X] = λ
Var[X] = E[X(X − 1)] + E[X] − (E[X])2 (704)
= λ2 + λ − (λ)2 (705)
= λ2 + λ − λ2 (706)
The variance of a Poisson random variable is:
Var[X] = λ (707)
96 CHAPTER 16. LECTURE 17
Factorization
Factor out the constant term p:
∞
X
E[X] = p nq n−1 (711)
n=1
Final Result
Substitute the result of the summation back into the E[X] equation:
"∞ #
X
E[X] = p · nq n−1 (715)
n=1
16.8. NOTE ON VARIANCE CALCULATION 97
1
E[X] = p · (716)
(1 − q)2
Since 1 − q = p:
1
E[X] = p · (717)
p2
1
E[X] = (718)
p
Substituting the moments into the variance formula Var[X] = E[X 2 ] − (E[X])2 :
2
2−p 1
Var[X] = 2
− (721)
p p
2−p 1
= − 2 (722)
p2 p
(2 − p) − 1
= (723)
p2
1−p
= (724)
p2
q
Var[X] = (725)
p2
98 CHAPTER 16. LECTURE 17
Xn ∼ NB(r, p) (726)
Statistical Inference
99
Chapter 17
T ∼ Geom(p) (730)
P (T > i) = q × q × · · · × q = q i (732)
| {z }
i times
From this, we derive the Cumulative Distribution Function (CDF), FT (i), which represents
the probability that the event occurs on or before trial i:
101
102CHAPTER 17. LECTURE 2: THE GEOMETRIC AND EXPONENTIAL DISTRIBUTIONS
Shifting Property
j=1
i→i−j
P Pq P Pq
i
1 2 3 4 4
j= 5 6
i has gone to 5
λe−λx
fX (x) 1
0.5
Probability Area
0
0 1 2 3 4 5
x (time)
Definition 17.3.1. Similar to the discrete case, the future lifetime of the event depends only
on the current duration, not on how much time has already elapsed.
Proof Sketch: Using the definition of conditional probability for continuous variables:
Since survival past t + ∆ implies survival past t, the intersection simplifies to P (J > t + ∆).
Substituting the Tail Probability formula (e−λx ):
Notice that the result e−λ∆ is exactly equal to P (J > ∆). This confirms that the probability
depends only on the interval ∆, independent of the starting time t.
fJ (t)
Conditional Area
t
t t+∆
Figure 17.2: Visualizing the Shifting Property: The ratio of the blue area to the gray area is
constant and depends only on ∆.
18.1 Introduction
The exponential distribution is one of the most important continuous probability models,
commonly used to describe the waiting time between independent events that occur at a
constant average rate. If X is an exponentially distributed random variable with rate
parameter λ > 0, then its probability density function is
In this derivation, we compute the mean, second moment, variance, and standard deviation of
the exponential distribution step by step. These results are important because they highlight
the memoryless property of the exponential distribution and also connect it to the Poisson
process, where λ represents the rate of event occurrence.
105
106 CHAPTER 18. LECTURE 3: EXPONENTIAL DISTRIBUTION DERIVATIONS
Z ∞ ∞
1 1 1
e−λx dx = − e−λx =0− − = . (756)
0 λ 0 λ λ
1
E[X] = . (757)
λ
This matches the standard mean of an exponential distribution.
We will compute the expectation E[X] and the second moment E[X 2 ] with step-by-step
explanations.
Step 1: take constants outside the integral. Since λ is a constant (with respect to x),
we write Z ∞
E[X] = λ xe−λx dx. (760)
0
R∞
Step 2: use integration by parts. To evaluate 0 xe−λx dx we apply integration by parts:
choose u = x (so du = dx) and dv = e−λx dx (so v = − λ1 e−λx ). Integration by parts gives
Z ∞ ∞ Z ∞
−λx 1 −λx 1
xe dx = x − e − − e−λx dx. (761)
0 λ 0 0 λ
Because the exponential e−λx decays faster than the polynomial x grows, we have
limx→∞ xe−λx = 0. Therefore the boundary term equals 0 − 0 = 0.
18.3. DERIVATIONS OF E[X] AND E[X 2 ] FOR AN EXPONENTIAL DISTRIBUTION107
Hence Z ∞
1 1 1
xe−λx dx = · = 2. (765)
0 λ λ λ
Step 5: multiply back the constant λ. Recall E[X] = λ times that integral, so
1 1
E[X] = λ · = . (766)
λ2 λ
1
Result: E[X] = .
λ
R∞
Step 1: integration by parts (first application). To evaluate 0 x2 e−λx dx use
integration by parts with u = x2 (so du = 2x dx) and dv = e−λx dx (so v = − λ1 e−λx ). This
yields
Z ∞ ∞ Z ∞
x2
1
x2 e−λx dx = − e−λx − − 2xe−λx dx. (768)
0 λ 0 0 λ
Step 2: boundary term vanishes. As before, limx→∞ x2 e−λx = 0 and at x = 0 the term
is 0. So the boundary term is 0. Thus
Z ∞
2 ∞ −λx
Z
2 −λx
x e dx = xe dx. (769)
0 λ 0
Step 3:
Z ∞use the previously computed integral. From the computation of E[X] we
1
found xe−λx dx = 2 . Therefore
0 λ
Z ∞
2 1 2
x2 e−λx dx = · 2 = 3 . (770)
0 λ λ λ
Step 4: multiply back the factor λ. Recall E[X 2 ] = λ times the integral, hence
2 2
E[X 2 ] = λ · 3
= 2. (771)
λ λ
2
Result: E[X 2 ] = .
λ2
108 CHAPTER 18. LECTURE 3: EXPONENTIAL DISTRIBUTION DERIVATIONS
1
Result: Var(X) = .
λ2
Remarks: In the integrations above we repeatedly used the fact that for any positive integer
n, lim xn e−λx = 0 (exponential decay dominates any polynomial growth). This justifies
x→∞
discarding boundary terms that involve such expressions.
18.4.1 1. Mean of X
The expectation of an exponential random variable is
1
E[X] = . (774)
λ
K x
110 CHAPTER 18. LECTURE 3: EXPONENTIAL DISTRIBUTION DERIVATIONS
Chapter 19
Z ∼ D(0, 1) (783)
Z ←− X (784)
Calculating Variance σ 2 :
σ 2 = E(X 2 ) − µ2 (787)
2
= E(X ) − 4 (788)
1+4+9
= −4 (789)
3
14 2
= −4= (790)
3 3
111
112 CHAPTER 19. LECTURE 4: NORMALIZATION AND SAMPLE STATISTICS
19.1.3 Calculations for Set: − √ , √ , √
1 0 +1
2/3 2/3 2/3
− √1 + √0 + √1
2/3 2/3 2/3
µ= (791)
3
r
3 1
=0· =0 (792)
2 3
Calculating Variance σ 2 :
σ 2 = E(X 2 ) − µ2 (793)
2 2 2
√−1 + √0
+ √1
2/3 2/3 2/3
= − 02 (794)
3
1 1
2/3 + 0 + 2/3
= (795)
3
2×3
= =1 (796)
2×3
19.1.4 Calculations for Set: √1 , √2 , √3
2/3 2/3 2/3
σ 2 = E(X 2 ) − µ2 (797)
2 2 2
√ 1 2 3
+ √ + √ !2
2/3 2/3 2/3 2
= − p (798)
3 2/3
1 4 9
2/3 + 2/3 + 2/3 4
= − (799)
3 2/3
1+4+9
2/3 4×3
= − (800)
3 2
14 × 3
= −6 (801)
2×3×3
14
= −6=7−6=1 (802)
2
In this context, the parameter k signifies that we have waited k units of time and the event
has not yet occurred.
19.3. SAMPLE STATISTICS FOR n I.I.D. VARIABLES 113
X −µ
X ∼ D(µ, σ 2 ) =⇒ Z = ∼ D(0, 1) (804)
σ
Where the parameters are defined as:
µ = E(X)
σ = Var(X)
2
In step (805), we use the linearity of expectation. Since E(X) = µ, the numerator becomes
zero in (806).
1
Equations (807) through (809) confirm that the scaling factor σ correctly yields a unit
variance.
For independent variables, the variance of the sum is the sum of the variances:
n
X n
X
Var(Sn ) = Var(Xi ) = σ 2 = nσ 2 (812)
i=1 i=1
nσ 2 σ2
Sn 1
Var(X̄n ) = Var = 2 Var(Sn ) = 2 = (815)
n n n n
This result in (815) is a fundamental principle in statistics, showing that larger samples
provide more precise estimates of the mean.
Theoretical Definition
Given X ∼ D(µ, σ 2 ), we define the normalized variable Z as:
X − E(X) X −µ
Z= = (828)
SD(X) σ
By definition, Z will have a distribution D(0, 1).
Functions changing rapidly require a small window for analysis, whereas gradual changes allow
for a larger window.
This lead
R xus to the Fundamental Theorem of Calculus (FTC), stating that if
F (x) = a f (t) dt, then F ′ (x) = f (x).
118 CHAPTER 19. LECTURE 4: NORMALIZATION AND SAMPLE STATISTICS
Chapter 20
MX (t) = E etX ,
for those values of t for which the expectation exists. (833)
The term “moment generating” arises from the fact that the derivatives of the MGF evaluated
at t = 0 produce the moments of the random variable. In particular, the nth moment about
the origin is given by
(n)
E[X n ] = MX (0), (834)
f (x) = a0 + a1 x + a2 x2 + a3 x3 + · · · + an xn + · · · (835)
119
120CHAPTER 20. LECTURES 5 AND 6: MOMENT GENERATING FUNCTIONS AND LIMIT THEOREM
f (0) = a0 (836)
Hence,
a0 = f (0) (837)
Evaluating at x = 0,
f ′ (0) = a1 (839)
Thus,
a1 = f ′ (0) (840)
Evaluating at x = 0,
f ′′ (0) = 2a2 (842)
Hence,
f ′′ (0)
a2 = (843)
2!
Evaluating at x = 0,
f (n) (0) = n!an (845)
Therefore,
f (n) (0)
an = (846)
n!
∞
X f (n) (0)
f (x) = xn (848)
n!
n=0
MX (t) = E etX
(854)
tx t2 x2 t3 x3
etx = 1 + + + + ··· (858)
1! 2! 3!
122CHAPTER 20. LECTURES 5 AND 6: MOMENT GENERATING FUNCTIONS AND LIMIT THEOREM
t2 X 2 t3 X 3
tX
MX (t) = E 1 + + + + ··· (860)
1! 2! 3!
t t2 t3
MX (t) = 1 + E(X) + E(X 2 ) + E(X 3 ) + · · · (861)
1! 2! 3!
This can be written in summation form as
∞ n
X t
MX (t) = E(X n ) (862)
n!
n=0
20.4.4 Evaluation at t = 0
Setting t = 0, we obtain
′
MX (0) = E(X) (864)
More generally, the nth derivative of the MGF evaluated at t = 0 gives
(n)
MX (0) = E(X n ), n = 1, 2, 3, . . . (865)
20.4.5 Conclusion
Hence, the nth moment of a random variable X about the origin can be obtained by
differentiating its moment generating function n times and evaluating at t = 0.
where n is the number of independent Bernoulli trials and p is the probability of success in
each trial.
The moment generating function (MGF) of X is defined as
MX (t) = E etX .
(867)
20.5. MOMENT GENERATING FUNCTION OF THE BINOMIAL DISTRIBUTION 123
The MGF is useful for obtaining the moments of the binomial distribution. Differentiating the
MGF and evaluating at t = 0, we obtain the mean and variance:
′
E[X] = MX (0) = np, (871)
′′ ′
2
Var(X) = MX (0) − MX (0) = np(1 − p). (872)
Thus, the moment generating function provides a convenient method for deriving the
moments and studying the distributional properties of the binomial random variable.
First moment:
Given
MX (t) = (pet + 1 − p)n (875)
Differentiate:
′
MX (t) = n(pet + 1 − p)n−1 (pet ) (876)
Evaluate at t = 0:
′
E(X) = MX (0) = n(p + 1 − p)n−1 p = np (877)
Thus:
E(X) = np (878)
We have
MX (t) = (pet + 1 − p)n (879)
Differentiate again to compute E(X 2 ):
124CHAPTER 20. LECTURES 5 AND 6: MOMENT GENERATING FUNCTIONS AND LIMIT THEOREM
′
MX (t) = n(pet + 1 − p)n−1 (pet ) (880)
′′
(t) = n (n − 1)(pet + 1 − p)n−2 (pet )(pet ) + (pet + 1 − p)n−1 (pet )
MX (881)
Factor out (pet + 1 − p)n−2 :
′′
(t) = n(pet + 1 − p)n−2 (n − 1)p2 e2t + (pet + 1 − p)(pet )
MX (882)
Evaluate at t = 0:
′′
(0) = n(1) n−2 (n − 1)p2 + (1)(p)
MX (883)
Hence:
′′
E(X 2 ) = MX (0) = n(n − 1)p2 + np (884)
We know:
Var(X) = E(X 2 ) − [E(X)]2 (885)
Substituting:
P (X = 0) = q 2 , P (X = 1) = 2pq, P (X = 2) = p2 . (893)
Thus,
∞ 2 !
x−µ
Z
1 tx1
MX (t) = e √ exp − dx. (907)
−∞ σ 2π 2 σ
20.8.3 Substitution
Let
x−µ
Z= ⇒ x = µ + σZ, dx = σ dZ. (908)
σ
Then:
z2 1
= − z 2 − 2tσz
tσz − (913)
2 2
1 2
z − 2tσz + t2 σ 2 − t2 σ 2
=− (914)
2
1 t2 σ 2
= − (z − tσ)2 + . (915)
2 2
Thus,
Z ∞
2 σ 2 /2 1 2
E(etσZ ) = et √ e−(z−tσ) /2 dz. (916)
−∞ 2π
Since this integral equals 1,
2 σ 2 /2
E(etσZ ) = et . (917)
20.9. PROPERTIES OF THE MGF 127
t2 σ 2
MX (t) = exp tµ + (919)
2
Since X and Y are independent, etX and etY are also independent, so
′ d
MX (t) = MX (t) = MX (t)(σ 2 t + µ). (930)
dt
Thus,
′
E[X] = MX (0) = MX (0) · µ = µ. (931)
′′ ′
MX (t) = MX (t)(σ 2 ) + (σ 2 t + µ)MX (t). (933)
At t = 0:
′′ ′
MX (0) = MX (0)σ 2 + µ MX (0) = σ 2 + µ2 . (934)
Thus,
E[X 2 ] = σ 2 + µ2 . (935)
20.10.2 Variance
Var(X) = E[X 2 ] − (E[X])2 = (σ 2 + µ2 ) − µ2 = σ 2 . (936)
2
X ∼ N (µX , σX ), Y ∼ N (µY , σY2 ), (937)
and X and Y are independent random variables.
We want to determine the distribution of:
X + Y. (938)
1 2 2
MY (t) = exp µY t + σY t . (941)
2
Thus:
1 2 2 1 2 2
MX+Y (t) = exp µX t + σX t exp µY t + σY t . (942)
2 2
Combine exponents:
1 2
MX+Y (t) = exp (µX + µY )t + (σX + σY2 )t2 . (943)
2
µ = µX + µY , σ 2 = σX
2
+ σY2 . (944)
Therefore:
2
X + Y ∼ N (µX + µY , σX + σY2 ) (945)
n
1X
X̄n = Xi . (947)
n
i=1
X̄n −
→ µ. (949)
P
Consistency of estimator:
That is, the standardized sample mean converges in distribution to a standard normal random
variable.
Chapter 21
21.1 Introduction
In probability and statistics, a central objective is to understand the behavior of random
variables and functions of random variables. In real-world applications, data are collected in
the form of samples from a population, and statistical inference is used to draw conclusions
about unknown population parameters such as the mean and variance.
One of the most important theoretical results in statistics is the Central Limit Theorem
(CLT). The CLT explains why the normal distribution arises naturally in many statistical
problems, even when the underlying population distribution is not normal. It provides the
theoretical foundation for approximation methods, hypothesis testing, and confidence interval
estimation.
In this session, we study the Central Limit Theorem and analyze the asymptotic behavior of
the sample sum and the sample mean of independent and identically distributed random
variables.
131
132 CHAPTER 21. LECTURE 7: CENTRAL LIMIT THEOREM
21.3.1 CDF of ZX n
FZX (z) = P (ZX n ≤ z) −−−→ P (Z ≤ z) = FZ (z) (964)
n n→∞
For all z ∈ R:
⇒ P (a < ZX n < b) −−−→ P (a < Z < b) (965)
n→∞
For the standard normal distribution, the probability is calculated as the area under the curve:
Z z
1 2
P (Z ≤ z) = √ e−x /2 dx, Z ∼ N (0, 1). (966)
2π −∞
Z ∼ N (0, 1)
z
-1 0 1
X1 X2 Xn
ZX̄n = √ + √ + · · · + √ (971)
n n n
The MGF of ZX n is the product of the individual MGFs:
MZX (t) = MX1 /√n (t) · MX2 /√n (t) · · · MXn /√n (t). (972)
n
Since Xi are i.i.d., MXi /√n (t) = MX √t , yielding:
n
n
t
MZX (t) = MX √ (973)
n n
2
We want to show that this converges to et /2 as n → ∞. Taking the natural logarithm on both
sides:
t2
t
lim n log MX √ = (974)
n→∞ n 2
Let L(t) = loge MX (t) . The limit can be rewritten as:
L √tn
lim (975)
n→∞ 1/n
Since MX (0) = 1, we have L(0) = loge (1) = 0. Thus, as n → ∞, the limit approaches 00 ,
requiring L’Hospital’s Rule.
133
134 CHAPTER 22. LECTURE 8: ASYMPTOTIC BOUNDS AND INEQUALITIES
t2
t
n log MX √ −−−→ (982)
n n→∞ 2
2 /2
Which confirms the MGF converges to et , proving the Central Limit Theorem.
P(X > a)
−b a
x
E(X) µ
P(X > a) ≤ = , ∀ a > 0. (983)
a a
(Note: this may not be the tightest possible upper bound).
Proof via Indicator Variables:
Let I be an indicator variable representing the event of interest [X ≥ a]:
1, if X > a with probability P (X > a) = p
I= (984)
0, if X ≤ a with probability [1 − P (X > a)] = q
Case 2: X ≤ a ⇒ I = 0 ⇒ X ≥ 0 (True)
Taking the expectation on both sides:
P |X − µ| ≥ k = P (X − µ)2 ≥ k 2
(989)
Let Y = (X − µ)2 . Note that Y ≥ 0. We can apply Markov’s inequality to Y , letting the
threshold a = k 2 > 0:
E(Y )
P Y ≥ k2 ≤
(990)
k2
Since E(Y ) = E[(X − µ)2 ] = σ 2 , we arrive directly at Chebyshev’s Inequality:
σ2
P |X − µ| ≥ k ≤ 2 (991)
k
Visualizing the Bounds:
x ≤ (µ − k) x ≥ (µ + k)
x
µ−k k µ k µ+k
This calculates the total probability of a random variable X being less than or equal to
x by adding up all probability densities:
Z x
FX (x) = P (X ≤ x) = f (t) dt (996)
a
√
PDF of X: By FTC, we can find the PDF of X by differentiating the CDF:
d
f√X (x) = FX (x2 ) = fX (x2 ) · (2x) (1001)
dx
137
138 CHAPTER 23. LECTURE 11: TRANSFORMATIONS OF RANDOM VARIABLES
CDF of 2X:
PDF of 2X:
d d
f2X (x) = F2X (x) = FX (x/2) (1007)
dx dx
Using the chain rule:
d 1
f2X (x) = fX (x/2) · (x/2) = fX (x/2) (1008)
dx 2
Since fX (t) = 1 for 0 < t < 1, then f2X (x) = 1/2 for 0 < x < 2.
X ∼ N (µ, σ 2 ) (1010)
X−µ
Find the PDF of Z = σ , where µ is expectation, σ 2 is variance, and σ is standard deviation.
CDF of Z:
FZ (z) = P (Z ≤ z) (1011)
X −µ
=P ≤z (1012)
σ
= P [X ≤ µ + σz] (1013)
Z µ+σz
= fX (t) dt (1014)
−∞
d
fZ (z) = FZ (z) = fX (g(z)) · g ′ (z) (1016)
dz
d
g ′ (z) = (µ + σz) = σ (1017)
dz
Substituting g(z) into fX :
h i2
1 −1
(µ+σz)−µ
fX (g(z)) = √ e 2 σ
(1018)
σ 2π
1 1 2
= √ e− 2 z (1019)
σ 2π
Then, fZ (z) = σ · fX (g(z)):
1 1 2 1 1 2
fZ (z) = σ · √ e− 2 z = √ e− 2 z (1020)
σ 2π 2π
The result is the PDF of the standard normal distribution:
Z ∼ N (0, 1) (1021)
140 CHAPTER 23. LECTURE 11: TRANSFORMATIONS OF RANDOM VARIABLES
Chapter 24
y
y = f (x) curve
Z t=b
= f (t)dt
a
(x, y)
y area under curve x=b
Z x=b
= f (x)dx
a
x
a bx
interval on x-axis
In 3D space, where z = f (x, y), we look at a region in the xy-plane. The input is 2D, and the
output exists in 3D space (x, y, z).
f (x, y)
S : z = f (x, y)
c
d y
a
x R
b
(x, y)
141
142 CHAPTER 24. LECTURE 12: JOINTLY DISTRIBUTED RANDOM VARIABLES
1. f (x, y) ≥ 0 ∀(x, y) ∈ R2
R∞ R∞
2. −∞ −∞ f (x, y) dx dy = 1
∂2F
∂ ∂F
f (x, y) = = (1025)
∂x∂y ∂x ∂y
Y
c d
a
re
ct
an
g le
b
B = {a ≤ x < b, c ≤ y ≤ d}
X
Fact: The PDF of a continuous RV is unique. If X is a continuous RV, and it has a PDF
fX (x), this means:
Z
P [X ∈ A] = fX (x) dx for almost all sets A ⊆ R (1028)
A
For example:
Z b
P [X ∈ (a, b)] = fX (x) dx (1029)
a
(Note: If X is a discrete RV, then the PMF of X is unique.)
1. Numerator: Z 1/2 Z 2
6 2 xy 69
x + dy dx = (1048)
0 1/2 7 2 448
2. Denominator: Z 1/2 Z 2
6 2 xy 5
x + dy dx = (1049)
0 0 7 2 28
Final Result:
69/448 69
= (1050)
5/28 80
Chapter 25
145
146CHAPTER 25. LECTURES 9 AND 10: JOINT DISTRIBUTIONS AND CONDITIONAL EXPECTATION
Since E and E c are complementary events, we have P (E) = 1 − P (E c ). Observe that the
complement event can be rewritten in terms of deviation from the mean µX = 20:
19
P (0 ≤ X ≤ 40) ≥ (1060)
20
This bound illustrates the power of Chebyshev’s inequality when only limited information
about a random variable is available.
The joint PMF completely characterizes the probabilistic behavior of the pair (X, Y ). For any
real-valued function g(x, y), the expected value of g(X, Y ) is defined as:
XX
E[g(X, Y )] = g(x, y) pX,Y (x, y) (1062)
x y
Often, we are interested in the distribution of a single random variable obtained from the pair.
This leads to the concept of marginal distributions. The marginal PMF of X is obtained by
summing the joint PMF over all possible values of Y :
X
pX (x) = pX,Y (x, y) (1063)
y
Using the marginal PMF, expectations involving only X can be computed as:
X
E[g(X)] = g(x) pX (x) (1064)
x
This definition extends naturally from the discrete case by replacing summations with
integrals.
25.4. LINEARITY OF EXPECTATION 147
Hence proved.
150CHAPTER 25. LECTURES 9 AND 10: JOINT DISTRIBUTIONS AND CONDITIONAL EXPECTATION
Since all floors are statistically identical, the expectation is the same for any floor:
The first sum is the total probability of a Poisson distribution, which equals 1. For the second
sum, we factor out e−λ and recognize the Taylor series for an exponential function:
∞ 1 n
X λ(1 − )
E(X) = N − N e−λ N
n!
n=0
1
−λ
= N − Ne · eλ(1− N )
= N − N e−λ+λ−λ/N
= N − N e−λ/N (1103)
This calculates the total probability of a random variable X being less than or equal to
x by adding up all probability densities:
Z x
FX (x) = P (X ≤ x) = f (t) dt (1106)
a
√
PDF of X: By FTC, we can find the PDF of X by differentiating the CDF:
d
f√X (x) = FX (x2 ) = fX (x2 ) · (2x) (1111)
dx
153
154 CHAPTER 26. LECTURE 11: TRANSFORMATIONS OF RANDOM VARIABLES
CDF of 2X:
PDF of 2X:
d d
f2X (x) = F2X (x) = FX (x/2) (1117)
dx dx
Using the chain rule:
d 1
f2X (x) = fX (x/2) · (x/2) = fX (x/2) (1118)
dx 2
Since fX (t) = 1 for 0 < t < 1, then f2X (x) = 1/2 for 0 < x < 2.
X ∼ N (µ, σ 2 ) (1120)
X−µ
Find the PDF of Z = σ , where µ is expectation, σ 2 is variance, and σ is standard deviation.
CDF of Z:
FZ (z) = P (Z ≤ z) (1121)
X −µ
=P ≤z (1122)
σ
= P [X ≤ µ + σz] (1123)
Z µ+σz
= fX (t) dt (1124)
−∞
d
fZ (z) = FZ (z) = fX (g(z)) · g ′ (z) (1126)
dz
d
g ′ (z) = (µ + σz) = σ (1127)
dz
Substituting g(z) into fX :
h i2
1 −1
(µ+σz)−µ
fX (g(z)) = √ e 2 σ
(1128)
σ 2π
1 1 2
= √ e− 2 z (1129)
σ 2π
Then, fZ (z) = σ · fX (g(z)):
1 1 2 1 1 2
fZ (z) = σ · √ e− 2 z = √ e− 2 z (1130)
σ 2π 2π
The result is the PDF of the standard normal distribution:
Z ∼ N (0, 1) (1131)
156 CHAPTER 26. LECTURE 11: TRANSFORMATIONS OF RANDOM VARIABLES
Chapter 27
y
y = f (x) curve
Z t=b
= f (t)dt
a
(x, y)
y area under curve x=b
Z x=b
= f (x)dx
a
x
a bx
interval on x-axis
In 3D space, where z = f (x, y), we look at a region in the xy-plane. The input is 2D, and the
output exists in 3D space (x, y, z).
f (x, y)
S : z = f (x, y)
c
d y
a
x R
b
(x, y)
157
158 CHAPTER 27. LECTURE 12: JOINTLY DISTRIBUTED RANDOM VARIABLES
1. f (x, y) ≥ 0 ∀(x, y) ∈ R2
R∞ R∞
2. −∞ −∞ f (x, y) dx dy = 1
∂2F
∂ ∂F
f (x, y) = = (1135)
∂x∂y ∂x ∂y
Y
c d
a
re
ct
an
g le
b
B = {a ≤ x < b, c ≤ y ≤ d}
X
Fact: The PDF of a continuous RV is unique. If X is a continuous RV, and it has a PDF
fX (x), this means:
Z
P [X ∈ A] = fX (x) dx for almost all sets A ⊆ R (1138)
A
For example:
Z b
P [X ∈ (a, b)] = fX (x) dx (1139)
a
(Note: If X is a discrete RV, then the PMF of X is unique.)
1. Numerator: Z 1/2 Z 2
6 2 xy 69
x + dy dx = (1158)
0 1/2 7 2 448
2. Denominator: Z 1/2 Z 2
6 2 xy 5
x + dy dx = (1159)
0 0 7 2 28
Final Result:
69/448 69
= (1160)
5/28 80
Chapter 28
1.5
y
1 Support Region
0.5
0
0 0.2 0.4 0.6 0.8 1 1.2
x
161
162CHAPTER 28. LECTURE 13: CONDITIONAL PROBABILITY (CONTINUOUS CASE)
1.5
y 1
0.5
0
0 0.2 0.4 0.6 0.8 1 1.2
x
2
fX (x)
0
0 0.2 0.4 0.6 0.8 1
x
28.3.2 Expectation of X
The expected value is computed by integrating the product of x and its marginal density:
Z 1
E(X) = xfX (x) dx (1167)
0
6 1
Z
= x(2x2 + x) dx (1168)
7 0
6 1 1 5
= + = (1169)
7 2 3 7
Chapter 29
Discrete Case:
PX,Y (a, b) = PX (a)PY (b) (1172)
P (Z = r) = P (X + Y = r) (1173)
Xr
= P (X + Y = r | Y = y)P (Y = y) (1174)
y=0
r
X
= P (X = r − y) P (Y = y) (1175)
y=0
163
164 CHAPTER 29. LECTURE 14: INDEPENDENCE AND SUMS OF VARIABLES
(λ + β)r
P (Z = r) = e−(λ+β) (1179)
r!
Thus, Z ∼ Poisson(λ + β) .
FA (a) = 0 (1183)
29.3.3 Case 2: 0 ≤ a ≤ 1
The region is a triangle with vertices (0, 0), (a, 0), (0, a).
a Z a−x a
a2
Z Z
FA (a) = dy dx = (a − x) dx = (1184)
0 0 0 2
(2 − a)2
FA (a) = 1 − (1185)
2
29.3. SUM OF TWO UNIFORM RANDOM VARIABLES 165
0.8
fA (a)
0.6
0.4
0.2
0
0 0.5 1 1.5 2
a
166 CHAPTER 29. LECTURE 14: INDEPENDENCE AND SUMS OF VARIABLES
Chapter 30
fX (x; θ),
X1 , X2 , . . . , XN ∼ fX (x; θ).
(xn − µ)2
2 1
fXn (xn ; µ, σ ) = √ exp − .
2πσ 2 2σ 2
167
168 CHAPTER 30. LECTURES 15 AND 16: MAXIMUM LIKELIHOOD ESTIMATION
30.3.2 Log-Likelihood
The log-likelihood simplifies optimization:
N
X
log L(θ | x) = log fXn (xn ; θ).
n=1
As N increases, the estimate becomes more accurate due to the law of large numbers.
Xij ∼ Bernoulli(p).
The log-likelihood is
N X
X N
log L(p | X) = [xij log p + (1 − xij ) log(1 − p)] .
i=1 j=1
P
Let S = i,j xij . The MLE is
S
p̂ML = .
N2
Xn ∼ Poisson(λ).
Then
P (Yn = 1) = 1 − e−λ , P (Yn = 0) = e−λ .
30.7.1 Log-Likelihood
N h
X i
log L(λ | y) = yn log(1 − e−λ ) − λ(1 − yn ) .
n=1
P
Let S = yn . The MLE is
S
λ̂ML = − log 1 − .
N
Conceptual Diagram
θ fX (x; θ) X1 , . . . , XN
Estimator
Forward problem: θ → Xn
Inverse problem (estimation): Xn → θ
N
Y
L(θ | x) = f (xn ; θ).
n=1
Taking logarithms,
N
X
log L(θ | x) = log f (xn ; θ).
n=1
Step 1: Likelihood
N
Y
L(θ) = θxn (1 − θ)1−xn
n=1
Step 2: Log-Likelihood
N
X
log L(θ) = xn log θ + (1 − xn ) log(1 − θ)
n=1
Define
N
X
S= xn
n=1
Then
log L(θ) = S log θ + (N − S) log(1 − θ)
30.11. BERNOULLI LOG-LIKELIHOOD SHAPE (TIKZ PLOT) 171
Step 3: Optimization
d S N −S
log L(θ) = −
dθ θ 1−θ
Set derivative to zero:
S
θ̂ML =
N
−40
−60
log L(θ)
−80
−100
−120
0 0.2 0.4 0.6 0.8 1
θ
Log-Likelihood
N
1 X
log L(µ) = − 2 (xn − µ)2 + C
2σ
n=1
Derivative
N
d 1 X
log L(µ) = 2 (xn − µ)
dµ σ
n=1
Set to zero:
N N
X 1 X
(xn − µ) = 0 ⇒ µ̂ML = xn
N
n=1 n=1
Candidate PDF
Better Match
MLE selects the parameter whose PDF best aligns with the observed data.
30.14 Conclusion
Maximum Likelihood Estimation provides a principled and general framework for parameter
estimation. Many classical estimators such as the sample mean naturally arise as MLEs under
common distributional assumptions.
Chapter 31
173
174 CHAPTER 31. LECTURES 17 AND 18: LIMIT THEOREMS
Conceptual Meaning
M aggregates information from n random observations.
n
The central question of this chapter is: What happens to Mn as the sample size n becomes
large?
Interpretation
The expected value of the sample mean equals the population mean.
The sample mean is an unbiased estimator.
On average, sampling neither inflates nor deflates the true mean.
31.5 Variance of the Sample Mean
Variance measures the spread or uncertainty of a random variable.
n
!
1X
Var(Mn ) = Var Xi (1194)
n
i=1
Substituting Var(Xi ) = σ 2 :
1 2 σ2
Var(Mn ) = (nσ ) = (1196)
n2 n
31.6. WEAK LAW OF LARGE NUMBERS (WLLN) 175
Critical Insight
Var(Mn ) −−−→ 0 (1197)
n→∞
Interpretation
Deviations from µ larger than ϵ become increasingly rare.
Convergence is probabilistic, not deterministic.
There is no claim that M (ω) converges for every ω.
n
Var(Y )
P (|Y − E(Y )| ≥ ϵ) ≤ (1200)
ϵ2
Apply it to Y = Mn :
Var(Mn )
P (|Mn − µ| ≥ ϵ) ≤ (1201)
ϵ2
Substitute Var(Mn ) = σ 2 /n:
σ2
P (|Mn − µ| ≥ ϵ) ≤ (1202)
nϵ2
Taking limits:
lim P (|Mn − µ| ≥ ϵ) = 0 (1203)
n→∞
Thus:
P
Mn −
→µ (1204)
Meaning
The probability mass concentrates around µ.
Large deviations vanish asymptotically.
31.9 Strong Law of Large Numbers (SLLN)
a.s.
Mn −−→ µ (1206)
Interpretation
Convergence occurs for almost every outcome.
Only a probability-zero set fails to converge.
SLLN is stronger than WLLN: SLLN ⇒ WLLN.
31.10 Bernoulli Example
Let Xi be a Bernoulli trials where success is 1 and failure is 0:
(
1 with probability p
Xi = (1207)
0 with probability 1 − p
Then:
E(Xi ) = p, Var(Xi ) = p(1 − p) (1208)
Sample mean:
n
1X
Mn = Xi (1209)
n
i=1
Interpretation
M equals the proportion of successes.
n
Meaning
LLN explains convergence of averages.
CLT explains distribution of fluctuations.
Normality arises universally, regardless of the original distribution.
31.13 Final Summary
Averaging stabilizes randomness.
Variance shrinks at rate 1/n.
WLLN ensures probabilistic convergence.
SLLN ensures pathwise convergence.
CLT explains Gaussian fluctuations.
178 CHAPTER 31. LECTURES 17 AND 18: LIMIT THEOREMS
Chapter 32
x1 , x2 , . . . , xn . (1218)
179
180 CHAPTER 32. LECTURES 19 AND 20: SAMPLING DISTRIBUTIONS (χ2 , t, AND F )
Then
X ∼ χ2n . (1227)
area = α
x
χ2α,ν
32.4. STUDENT t DISTRIBUTION 181
α = P(Tn > tα,n ) = P(−Tn < −tα,n ) = P(Tn < −tα,n ). (1244)
Hence:
P(Tn > −tα,n ) = 1 − α. (1245)
So we identify the relationship:
−tα,n = t1−α,n . (1246)
32.4.6 Sketch
[Image comparing a standard normal distribution curve with a Student’s t-distribution curve
to show the heavier tails]
α α
t
−tα,n 0 tα,n
32.4.7 As n → ∞
d
Tn −
→ Z ∼ N (0, 1). (1247)
Also,
χ2n Z 2 + · · · + Zn2
= 1 −−−→ 1. (1248)
n n n→∞
32.5 F Distribution
32.5.1 Definition
Let χ2n and χ2m be independent chi-square r.v.s with degrees of freedom n and m respectively.
Define
χ2 /n
Fn,m = 2n . (1249)
χm /m
Then:
Fn,m ∼ F (n, m). (1250)
area = α
f
fα;n,m
Sample sizes: n1 from X and n2 from Y . Let sample variances be S12 and S22 .
32.6.3 F ratio
Then:
S12 /σ12
∼ F (n1 − 1, n2 − 1). (1259)
S22 /σ22
184 CHAPTER 32. LECTURES 19 AND 20: SAMPLING DISTRIBUTIONS (χ2 , t, AND F )
Part III
185
Chapter 33
Lecture 1
2. Mathematical Setup
Machine learning aims to learn an unknown functional relationship between inputs and
outputs:
Y = f (X)
where
X = (x1 , x2 , . . . , xn ) ∈ Rn
represents the input feature vector, and
Y ∈R or Y ∈ {0, 1}
The objective is to estimate a function fˆ(·) that performs well not only on training data but
also on unseen data. This property is known as generalization.
187
188CHAPTER 33. LECTURES 1 AND 2: FUNDAMENTALS OF MACHINE LEARNING AND HYPOTHES
L(y, ŷ)
Examples of loss functions:
Y = f (X)
Tasks:
Objectives:
Pattern discovery
Dimensionality reduction
Feature extraction
Techniques:
1. Clustering
2. Dimensionality Reduction:
Inner product:
⟨(1, 0), (0, 1)⟩ = 0
Since the vectors are orthogonal, the classes are linearly separable. Classification corresponds
to finding a decision boundary in feature space.
Lecture 2
H0 : µ = µ0
H1 : µ ̸= µ0
Types of alternatives:
Two-tailed: µ ̸= µ 0
Right-tailed: µ > µ 0
Left-tailed: µ < µ 0
5. Make a decision
190CHAPTER 33. LECTURES 1 AND 2: FUNDAMENTALS OF MACHINE LEARNING AND HYPOTHES
Probability Density
β α
µ0 t µ1
x
Explanation:
α = P (Reject H0 | H0 true)
β = P (Accept H0 | H0 false)
5. p-Value
The p-value is the probability of observing a test statistic as extreme as the sample value
assuming H0 is true.
Decision rule:
Reject H0 if p-value < α
Then,
X̄n − µ d
√ − → N (0, 1)
σ/ n
This holds regardless of the original distribution for large n.
X̄ − µ0
T = √ ∼ tn−1
s/ n
H0
H1
Density
Threshold
µ0 t µ1
x
Explanation:
34.1 Introduction
Statistical inference provides a principled framework for reasoning under uncertainty. In many
real-world problems, we observe data generated by random mechanisms and seek to make
decisions about unknown population parameters. Hypothesis testing is one of the central
tools in this framework, allowing us to formally assess whether observed data are consistent
with a proposed model.
Special attention is given to the interpretation of Type I error, Type II error, and power
of a test, highlighting their roles as long-run frequency properties rather than statements of
absolute certainty. Graphical illustrations are used throughout to reinforce geometric intuition
behind rejection regions and probability mass under competing distributions.
34.2.1 Objective
Given one observation x, decide whether to reject H0 . Since µ1 = 25 > 8, large values of X
favor H1 . This is a right-tailed test.
193
194CHAPTER 34. LECTURES 3 AND 4: HYPOTHESIS TESTING AND STATISTICAL DECISIONS
P (X > C | H0 ) = α (1266)
34.5.2 α = 0.05
z0.05 = 1.645 (1276)
C = 8 + 4(1.645) = 14.58 (1277)
34.5.3 α = 0.10
z0.10 = 1.282 (1278)
C = 8 + 4(1.282) = 13.13 (1279)
34.5.4 Observation
C0.01 > C0.05 > C0.10 (1280)
As α increases, rejection becomes easier.
34.6. DIAGRAM: 5% REJECTION REGION 195
Density 8
0
−5 0 5 10 15 20 25 30
x
Standardize:
15 − 8
Z= = 1.75 (1285)
4
From tables:
Φ(1.75) = 0.9599 (1287)
34.8.1 Interpretation
Reject H0 whenever:
α > 0.0401 (1289)
196CHAPTER 34. LECTURES 3 AND 4: HYPOTHESIS TESTING AND STATISTICAL DECISIONS
Density 8
0
−5 0 5 10 15 20 25 30
x
14.58 − 25
Z= = −2.605 (1292)
4
8
Density
0
−5 0 5 10 15 20 25 30 35 40
x
34.12. CONCEPTUAL SUMMARY 197
Power = 1 − β
Smaller α harder to reject
Greater separation of means higher power
Statistical inference controls error probabilistically — it never yields absolute certainty.
β = P (X ∈
/ R | H1 ) (1303)
34.15.3 Power
Power = 1 − β (1304)
Power measures the probability of correctly rejecting H0 when H1 is true.
If we fix
α = 0.01 (1306)
then by definition,
α = P (Reject H0 | H0 true) (1307)
Interpretation: If we repeat the experiment 1000 times while H0 is true,
Thus:
β = P (X ≤ C | µ = 25) (1311)
Under H1 :
X ∼ N (25, 16) (1312)
Standardize:
X − 25
Z= (1313)
4
Therefore,
C − 25
β=P Z≤ (1314)
4
34.18. GRAPHICAL ILLUSTRATION OF β AND POWER 199
Thus,
C − 25 17.32 − 25
= = −1.92 (1316)
4 4
Hence,
β = P (Z ≤ −1.92) (1317)
Thus,
Power = 1 − 0.0274 = 0.9726 (1320)
Interpretation: If the true mean is 25, the test correctly rejects H0 approximately 97% of the
time.
8
Density
0
−5 0 5 10 15 20 25 30 35 40
x
Interpretation:
R = {X > C} (1323)
X > C ⇒ Reject H0
X ≤ C ⇒ Accept H0 (1324)
C1 = 8 − 4zα/2 (1328)
C2 = 8 + 4zα/2 (1329)
Thus we reject if
|Z| > zα/2 (1330)
Accept Region
Reject H0 Reject H0
−zα/2 0 zα/2
The shaded regions represent the rejection regions, each having probability α/2.
To develop a procedure for determining whether the observed sample data are
consistent with the given null hypothesis.
If the observed sample mean x̄ lies far from µ0 (measured in standard error units), then the
probability of such an observation under H0 is small. If this probability is less than α, we
reject H0 .
34.23.8 Summary
Null Hypothesis: µ = 8
Alternative Hypothesis: µ ̸= 8
Distribution: X ∼ N (µ, σ )
2
This completes the theoretical and graphical explanation of the two-sided test for population
mean.
34.24. A NOTE ON HYPOTHESIS ”ACCEPTANCE” 203
b) Composite Hypothesis:
H0 : θ ≤ 1 (1347)
If (b) is true, it does not specify a single population distribution because θ can take any
value ≤ 1.
Accept H if (x , x , . . . , x ) ∈/ C.
0 1 2 n
1.96
1. x̄ > 1 + √
n
(Right tail)
1.96
2. x̄ < 1 − √
n
(Left tail)
f (x̄)
Acceptance (95%)
CL (2.5%) CR (2.5%) x̄
1 − 1.96
√ 1 1+ 1.96
√
n n
Conclusion: H0 is rejected if the resulting observed data are very unlikely (i.e., fall in the
shaded tails) when H0 is true.
Chapter 35
35.1 Introduction
In statistical inference we frequently wish to determine whether observed data are consistent
with a specified value of an unknown population parameter. This decision problem is
formalized through statistical hypothesis testing.
The goal is not to prove a hypothesis true, but rather to determine whether the data provide
sufficient evidence to reject it.
H0 : θ ∈ W
T = T (X1 , . . . , Xn ).
α = P (Reject H0 | H0 True)
β = P (Accept H0 | H0 False)
Remark 35.3.1. The function β(θ) describes the probability of accepting H0 for each possible
true parameter value.
205
206CHAPTER 35. LECTURES 5 AND 6: HYPOTHESIS TESTING FOR POPULATION MEAN
We test
H0 : µ = µ0 , HA : µ ̸= µ0 .
σ2
X̄ ∼ N µ, .
n
Z ∼ N (0, 1).
Interpretation
The value zα/2 satisfies
α
P (Z > zα/2 ) = .
2
Thus the probability of rejecting a true null hypothesis equals α.
Reject H0 Reject H0
z
35.7. ACCEPTANCE REGION 207
1−α
35.8 P-Value
Definition 35.8.1 (P-value). The p-value is the probability, under H0 , of observing a test
statistic at least as extreme as the observed value.
Decision rule:
Reject H0 if p-value < α.
35.9 Examples
Example 35.9.1. Test
H0 : µ = 168, HA : µ ̸= 168
with
n = 36, X̄ = 169.5, σ = 3.9.
Conclusion: Reject H0 .
Example 35.9.2.
n = 5, X̄ = 8.5, σ = 2, µ0 = 8.
Z = 0.559.
Definition 35.10.1 (Operating Characteristic Curve). The function β(µ) is called the OC
curve.
208CHAPTER 35. LECTURES 5 AND 6: HYPOTHESIS TESTING FOR POPULATION MEAN
β(µ)
Example:
H0 : θ = 75, Ha : θ ̸= 75.
H0 : µ1 = µ2 , Ha : µ1 > µ2 , Ha : µ1 < µ2 , Ha : µ1 ̸= µ2 .
Statistical testing is a decision rule based on the observed value of the test statistic.
Power = 1 − β.
Goal of testing:
Minimize α and β.
L(θ0 )
λ=
L(θ̂)
Remark 35.18.1. Among all tests with level α, the likelihood ratio test often has maximum
power.
α/2 α/2
2. Rejection Region (RR): If the test statistic falls here, we reject H0 and accept Ha .
35.25. LIKELIHOOD RATIO TEST (LRT) 211
Type I Error (α): Rejecting H 0 when it is actually true. α is called the Significance
Level.
Power of the Test (1 − β): The probability of correctly rejecting a false H . Goal:
0
Maximize (1 − β) for a fixed α.
Note: Type I error is considered more serious. We generally fix α to a very low
value (e.g., 0.05) and then try to minimize β.
L(θ0 )
λ=
L(θ̂)
Where L(θ0 ) is the likelihood under H0 , and θ̂ is the Maximum Likelihood Estimate
(MLE).
212CHAPTER 35. LECTURES 5 AND 6: HYPOTHESIS TESTING FOR POPULATION MEAN
Chapter 36
H a : θ = θa
This is called a simple alternative hypothesis since the parameter θ has only one
specified value θa .
H a : θ > θa
This is called a composite alternative hypothesis since many possible values of θ are
included.
Example
Hypothesis Structure
H0 : µ = 75 (simple) (3)
Ha : µ > 75 (composite) (4)
Remark: This is a case of simple vs composite testing.
Note: Mostly H0 is simple, but Ha can be either simple or composite.
L(θ0 )
λ= (1351)
L(θ̂)
where:
L(θ ) is the likelihood under the null hypothesis H
0 0 : θ = θ0
L(θ̂) is the likelihood evaluated at the MLE of θ
213
214CHAPTER 36. LECTURES 7 AND 8: LIKELIHOOD RATIO TEST AND LARGE SAMPLE Z TEST
Interpretation
If λ is small, then L(θ ) is small relative to the maximum likelihood.
0
H0 : θ = θ0 (6)
θ̂ : MLE of θ (7)
Thus:
α = P (λ ≤ λα ) (1352)
where λα is the critical value.
Thus, α represents the probability of rejecting H0 when it is true.
Decision Rule
λ ≤ λα ⇒ Reject H0 (1353)
Equivalently:
Final Interpretation:
Probability Interpretation
α = P λ ≤ λα (1358)
be a sample of size n.
Observed sample:
x = (x1 , x2 , . . . , xn ) (1361)
Population Assumption
i.e.,
X ∼ N (µ, 1) (1363)
or equivalently,
L(θ0 )
λ= (1366)
L(θ̂)
H0 : µ = 0 (1)
Ha : µ > 0 (2)
L(θ0 )
λ= (3)
L(θ̂M LE )
Likelihood under H0
L(θ0 ) = L(µ = 0) (4)
General Likelihood
L(µ, σ 2 ) = f (x1 , x2 , . . . , xn | µ, σ 2 ) (5)
n
xi −µ
2
Y 1 −1
= √ e 2 σ
(7)
i=1
σ 2π
Putting σ 2 = 1
n
Y 1 1 2
= √ e− 2 (xi −µ) (8)
i=1
2π
n
Y 1 1 2
L(µ) = √ e− 2 (xi −µ) (9)
i=1
2π
n
n Y
1 1 2
= √ e− 2 (xi −µ) (10)
2π i=1
n
1 1 Pn 2
= √ e− 2 i=1 (xi −µ) (11)
2π
Expanded Form
n n
1 − 21 [(x1 −µ)2 +(x2 −µ)2 +···+(xn −µ)2 ] 1 1 P
(xi )2 ]
L(µ) = √ e = √ e− 2 [ (12)
2π 2π
Under H0 (Numerator)
n
1 1 2 2 2
L(µ = 0) = √ e− 2 [x1 +x2 +···+xn ] (13)
2π
36.7. LIKELIHOOD FUNCTION AND MLE (DETAILED) 217
n
1 1 Pn 2
= √ e− 2 i=1 (xi −x̄) (15)
2π
MLE of µ
µ̂M LE = x̄ (16)
Rewriting Likelihood
n
1 1 Pn 2
L(µ) = √ e− 2 i=1 (xi −µ) (17)
2π
Log Likelihood
n
1 − 12
P
(xi −µ)2
= log √ e (19)
2π
n
1 1X
= n log √ − (xi − µ)2 (20)
2π 2
i=1
Derivative (Step-by-Step)
dℓ(µ) 1 X
=− ·2 (xi − µ)(−1) (21)
dµ 2
X
= (xi − µ) (22)
X X
= xi − µ (23)
X
= xi − nµ (24)
=0 (25)
µ̂M LE = x̄ (26)
218CHAPTER 36. LECTURES 7 AND 8: LIKELIHOOD RATIO TEST AND LARGE SAMPLE Z TEST
n
X n
X
= xi − µ (28)
i=1 i=1
n
X
= xi − nµ (29)
i=1
=0 (30)
n
X
xi = nµ (31)
i=1
n
1X
µ̂M LE = xi = x̄ (32)
n
i=1
Second Derivative
d2 ℓ(µ)
= −n < 0 (33)
dµ2
Let θ ≡ µ.
Likelihood Ratio
L(θ0 ) L(µ = 0)
λ= = (34)
L(θ̂M LE ) L(x̄)
Substitute Expressions
n
1 1 Pn
x2i
L(0) = √ e− 2 i=1 (35)
2π
n
1 1 Pn 2
L(x̄) = √ e− 2 i=1 (xi −x̄) (36)
2π
Form Ratio
1
x2i
P
e− 2
λ= 1 (37)
(xi −x̄)2
P
e− 2
36.9. LIKELIHOOD RATIO AND REJECTION REGION (DETAILED) 219
X X X
= x2i + x̄2 − 2x̄ xi (39)
X X
= x2i + nx̄2 − 2x̄ xi (40)
X
xi = nx̄ (41)
X
= x2i + nx̄2 − 2nx̄2 (42)
X
= x2i − nx̄2 (43)
Substitute Back
1
x2i
P
e− 2
λ= 1 (44)
x2i −nx̄2 )
P
e− 2 (
1 1
x2i x2i −nx̄2 )
P P
= e− 2 · e2( (45)
1 2
= e− 2 nx̄ (46)
Final Result
n 2
λ = e− 2 x̄ (47)
Decision Rule
If λ ≤ λα reject H0 with level of significance α (49)
Substitution
n 2
e− 2 x̄ ≤ λα (50)
Taking Log
n
− x̄2 ≤ ln(λα ) (51)
2
2
x̄2 ≥ − ln(λα ) (52)
n
220CHAPTER 36. LECTURES 7 AND 8: LIKELIHOOD RATIO TEST AND LARGE SAMPLE Z TEST
|x̄| ≥ χα (55)
If λ ≤ λα reject H0 (56)
2
x̄2 ≥ − ln(λα ) (57)
n
Let
2
χ2α = − ln(λα ) (58)
n
36.10 Recall
x2 ≥ y 2 (60)
Solve for x:
x2 − y 2 ≥ 0 (61)
(x − y)(x + y) ≥ 0 (62)
Case (1)
When both (x − y) ≥ 0 and (x + y) ≥ 0:
x≥y (63)
x ≥ −y (64)
Case (2)
When both (x − y) ≤ 0 and (x + y) ≤ 0:
x≤y (65)
x ≤ −y (66)
If x ≥ 0 and y ≥ 0, then x ≥ y
If x ≤ 0 and y ≤ 0, then −x ≥ −y
If x ≥ 0 and y ≤ 0, then x ≥ −y
If x ≤ 0 and y ≥ 0, then −x ≥ y
36.11. FINAL RESULT 221
Conclusion
|x| ≥ y (67)
Critical Quantity
2
χ2α = − ln(λα ) ≥ 0 (78)
n
Hence,
χ2α ≥ 0 (79)
Thus both χα and −χα satisfy the condition.
222CHAPTER 36. LECTURES 7 AND 8: LIKELIHOOD RATIO TEST AND LARGE SAMPLE Z TEST
Final Inequality
|x̄| ≥ χα or |x̄| ≥ −χα (80)
Sign-Based Breakdown
If x̄ > 0, then
x̄ ≥ χα (81)
If x̄ < 0, then
−x̄ ≥ χα ⇒ x̄ ≤ −χα (82)
Equivalent Form
x̄ ≥ χα or x̄ ≤ −χα (83)
H0 : µ = µ0 (48)
Ha : µ ̸= µ0 (49)
Area (1 − α)
Rejection Region Rejection Region
α/2 α/2
−zα/2 zα/2
α α
Size of Test = + =α (50)
2 2
Reject H0 with level α.
Acceptance Ha : µ ̸= 0
—
H0 : µ = µ0 (51)
Ha : µ < µ0 (52)
−zα
H0 : µ = µ0 (53)
Ha : µ > µ0 (54)
zα
H0 : µ = µ0 (56)
Ha : µ ̸= µ0 (57)
Area (1 − α)
Rejection Region Rejection Region
α/2 α/2
−zα/2 zα/2
α α
Size of Test = + =α (58)
2 2
given.
Reject H0 with level α
Acceptance Ha : µ ̸= 0
—
Large Sample
X̄ − µ
Z= √ ∼ N (0, 1) (60)
σ/ n
—
224CHAPTER 36. LECTURES 7 AND 8: LIKELIHOOD RATIO TEST AND LARGE SAMPLE Z TEST
Small Sample
n < 30 (61)
X̄ − µ0
t-statistic: T = √ (62)
S/ n
X̄ − µ
T = √ (63)
S/ n
under H0 : µ = µ0
—
Decision Rules
Right Tail
Left Tail
Two Tail
Example
H0 : µ = 1 (68)
Ha : µ > 1 (69)
dof = (n − 1) = 19 (70)
36.11. FINAL RESULT 225
α = 5% (72)
Test Statistic:
X̄ − µ0
T = √ (73)
s/ n
under H0
1.7 − 1
t= √ = 1.739 (74)
1.8/ 20
—
t Tables
dof α = 0.05
19 t0.05,19 = 1.729
—
Reject H0
α = 0.05
1.729
Reject H0 (77)
Large Sample
n > 30 (78)
σ12
X̄1 ∼ N µ1 , (81)
n1
σ22
X̄2 ∼ N µ2 , (82)
n2
2
σ2
σ1
[X̄1 − X̄2 ] ∼ N (µ1 − µ2 ), + 2 (83)
n1 n2
[X̄1 − X̄2 ] − D0
Z= q 2 (87)
S1 S22
n1 + n2
—
Decision Rule
−zα/2 zα/2
36.11. FINAL RESULT 227
H0 : (µ1 − µ2 ) = D0 (89)
Ha : (µ1 − µ2 ) < D0 (90)
−zα
—
Note: For small sample n < 30, use t-test instead of Z-statistic.
Pop 1 → n1 (92)
Pop 2 → n2 (93)
H0 : p = p0 (96)
Ha : p ̸= p0 (97)
p̂ − p0
Z= q under H0 (98)
pq
n
q0 = 1 − p 0 (99)
—
228CHAPTER 36. LECTURES 7 AND 8: LIKELIHOOD RATIO TEST AND LARGE SAMPLE Z TEST
n
σ2
1X
X̄ ∼ N µ, , X̄ = Xi (101)
n n
i=1
Xi ∼ Bern(p) (102)
X ∼ Bin(n, p) (103)
(
1 with probability p = P (H)
Xi = (104)
0 with probability q = 1 − p = P (T )
n
X
X= Xi = (X1 + X2 + · · · + Xn ) (105)
i=1
n
X 1X
p̂ = = Xi (106)
n n
i=1
n
1X 1
E(p̂) = E(Xi ) = (np) = p (107)
n n
i=1
n
1 X 1 pq
Var(p̂) = 2 Var(Xi ) = 2 (npq) = (108)
n n n
i=1
p̂n − p n→∞
q −−−→ Z ∼ N (0, 1) (109)
pq CLT
n
—
36.11. FINAL RESULT 229
D0 = 0 (110)
H0 : (p1 − p2 ) = D0 (111)
Ha : (p1 − p2 ) ̸= D0 (112)
Test statistic:
(p̂1 − p̂2 ) − D0
Z= q (113)
p̂1 q̂1 p̂2 q̂2
n1 + n2
This test is used to determine whether the difference between two population proportions (p1
and p2 ) is significantly different from a hypothesized value D0 .
H0 : p1 − p2 = D0
Ha : p1 − p2 ̸= D0
Since this is a large sample case, the sampling distribution of (p̂1 − p̂2 ) is approximately
normal.
231
232CHAPTER 37. LECTURES 9 AND 10: TWO-POPULATION INFERENCE AND ERROR PROBABILIT
(p̂1 − p̂2 )
Z=r
p̄q̄ n11 + n12
4. Decision Rule
Success-Failure Condition:
n1 p̂1 ≥ 10, n1 (1 − p̂1 ) ≥ 10
When testing for a hypothesized difference D0 (where D0 ̸= 0), we use individual sample
proportions (unpooled case):
(p̂1 − p̂2 ) − D0
Z= r
p̂1 q̂1 p̂2 q̂2
+
n1 n2
Variable Definitions:
p̂1 − p̂2
Z=s
1 1
p̂q̂ +
n1 n2
Success-Failure Condition:
n1 p̂1 ≥ 10, n1 q̂1 ≥ 10
(n − 1)s2
χ2 = ∼ χ2(n−1) d.o.f = (n − 1)
σ02
Note: The Chi-Square distribution is asymmetric (right-skewed) and defined only for
non-negative values.
One-Sided Tests
Area=α
Reject H0
χ2α
Right-Tailed Test
Area=α
χ21−α χ2(1−α)
From Table
Left-Tailed Test
Two-Sided Test
Ho Accept
Acceptance
Region
(1 − α)
Reject Area Reject H0
H0
χ21− α χ2α
2 2
Key Takeaways
Degrees of freedom = (n − 1)
Critical values must be looked up separately for each tail
236CHAPTER 37. LECTURES 9 AND 10: TWO-POPULATION INFERENCE AND ERROR PROBABILIT
Step 1: Hypotheses
Step 2: Assumptions
S12
F =
S22
Degrees of Freedom:
df1 = n1 − 1 (numerator), df2 = n2 − 1 (denominator)
Important Convention:
Larger Variance
F = ≥1
Smaller Variance
Right-Tailed Test:
Reject H0 if F > Fα, (n1 −1, n2 −1)
Left-Tailed Test:
Reject H0 if F < F1−α, (n1 −1, n2 −1)
Two-Tailed Test:
Reject H0 if F < F1−α/2, (n1 −1, n2 −1) or F > Fα/2, (n1 −1, n2 −1)
F ≥ 0 (always positive)
Right-skewed distribution
Depends on two degrees of freedom
Not symmetric (unlike Z and t)
Step 6: Mathematical Property
Reciprocal Property:
1
∼ F(n2 −1, n1 −1)
F
Key Insight
The F -test is based on the Likelihood Ratio Test (LRT) and is the most powerful test
for comparing variances of normal populations.
238CHAPTER 37. LECTURES 9 AND 10: TWO-POPULATION INFERENCE AND ERROR PROBABILIT
Date: 26/02/2026
Definition:
The p-value is the observed level of significance (α̂) computed from sample data.
Interpretation:
(
p-value < α ⇒ Reject H0
p-value ≥ α ⇒ Fail to Reject H0
Power of Test:
Power = 1 − β
Given:
X ∼ Exp(θ)
PDF: f (x) = θe −θx , x≥0
Hypotheses:
H0 : θ = 2, Ha : θ = 1
239
Critical Region: x ≥ 1
Step 1: Calculate α
α = P (X ≥ 1 | θ = 2)
Z ∞
= 2e−2x dx
1
∞
= −e−2x 1 = 0 − (−e−2 ) = e−2
∴ α = e−2 ≈ 0.1353
Step 2: Calculate β
β = P (X < 1 | θ = 1)
Z 1
= e−x dx
0
1
= −e−x 0 = (−e−1 ) − (−1) = 1 − e−1
∴ β = 1 − e−1 ≈ 0.6321
4. Key Takeaways
Given:
X ∼ Exp(θ)
PDF:
f (x) = θe−θx , x≥0
Hypotheses:
H0 : θ = 2, Ha : θ = 1
Critical Region:
C = {x ≥ 1}
240CHAPTER 37. LECTURES 9 AND 10: TWO-POPULATION INFERENCE AND ERROR PROBABILIT
α = P (Reject H0 | H0 true)
= P (X ≥ 1 | θ = 2)
Z ∞
= 2e−2x dx
1
∞
= −e−2x 1 = 0 − (−e−2 ) = e−2
∴ α = e−2 ≈ 0.1353
β = P (Accept H0 | Ha true)
= P (X < 1 | θ = 1)
Z 1
= e−x dx
0
1
= −e−x 0 = (−e−1 ) − (−1) = 1 − e−1
∴ β = 1 − e−1 ≈ 0.6321
Final Answer
(S 2 is an estimator of σ2)
Rejection Rule
Reject H0 if:
|T | > tα/2, n−1
p-value
p-value = P (|Tn−1 | > Tc )
Note
Normal distribution: N (0, 1)
t-distribution is symmetric
242CHAPTER 37. LECTURES 9 AND 10: TWO-POPULATION INFERENCE AND ERROR PROBABILIT
Power of Test
Power = (1 − β)
Example:
e−1 1
1− =
e e
X̄ − µ0
Z= √ ∼ N (0, 1)
σ/ n
Reject H0 if:
|Z| > zα/2
Case 2: σ Unknown
Use t-test:
X̄ − µ0
T = √ ∼ tn−1
S/ n
Reject H0 if:
|T | > tα/2, n−1
This is the same equation scaled by 2, so the system has infinitely many solutions.
Key Insight: The infinite solutions arise from the fact that there are infinitely many ways
to express x + y = 1 in R.
To see this, look at the system:
x+y =1 and x − y = 0
243
244CHAPTER 38. LECTURES 11 AND 12: LINEAR ALGEBRA FOUNDATION - SUBSPACES AND PROJ
x⃗c1 + y⃗c2 = ⃗b
1 1
For example, with ⃗c1 = and ⃗c2 = :
−1 −1
1 1 b
x +y = 1
−1 −1 b2
⃗x = ⃗xp + ⃗xh
n o
C(A) = ⃗b ∈ Rm ⃗b = A⃗x (Column Space, m × 1)
Intuitive descriptions:
C(A): Collection of all vectors that are linear combinations of the n columns of A
38.4. ORTHOGONALITY OF THE FUNDAMENTAL SUBSPACES 245
R(A): Collection of all vectors that are linear combinations of the n rows of A
N (A): Collection of all vectors that give linear dependencies among the n
columns of A
N (A T ):
Collection of all vectors that give linear dependencies among the n
columns of AT (i.e., rows of A)
Since ⃗x2 = 2⃗x1 , we have 2⃗x1 − ⃗x2 = ⃗0, confirming a linear dependency.
38.3.2 Rank
rank(A) = r implies there are r independent rows and r independent columns.
Dimension summary:
Subspace Dimension Lives in
C(A) r Rm
R(A) = C(AT ) r Rn
N (A) n−r Rn
N (AT ) m−r Rm
Proof sketch: Let ⃗y ∈ N (A) (i.e., A⃗y = ⃗0), and let ⃗xTi be the rows of A. Then:
y1 · ⃗xT1 ⃗b = 0
y2 · ⃗xT ⃗b = 0
2
..
.
yk · ⃗xTk ⃗b = 0
Summing:
y1 ⃗xT1 + y2 ⃗xT2 + y3 ⃗xT3 + · · · ⃗b = 0 ⃗aT ⃗b = 0
=⇒
a) If ⃗b ∈ C(A): ∞ solutions.
b) If ⃗b ∈
/ C(A): no solution.
38.6 Projections
38.6.1 2D Setup
Goal: Project ⃗b onto ⃗a (i.e., find p⃗ ∈ span{⃗a} closest to ⃗b).
From the diagram: ⃗b = ⃗e + p⃗, so p⃗ = ⃗b − ⃗e.
Orthogonality condition: ⃗a ⊥ ⃗e, which means ⃗aT ⃗e = 0:
⃗aT ⃗b
⃗aT (⃗b − x⃗a) = 0 =⇒ x= (a scalar)
⃗aT ⃗a
38.7. PROPERTIES OF THE PROJECTION MATRIX 247
The projection:
" #
⃗aT ⃗b ⃗a⃗aT ⃗
p⃗ = ⃗a · x = ⃗a T = T b
⃗a ⃗a ⃗a ⃗a
⃗a⃗aT
P =
⃗aT ⃗a
so that p⃗ = P⃗b.
Note the difference:
⃗a · ⃗a is a scalar (1 × n times n × 1)
T
⃗a · ⃗a is a matrix (n × 1 times 1 × n)
T
⃗a⃗aT
For P = :
⃗aT ⃗a
1. P is always a square matrix.
3. P T = P (Symmetric).
Proof of (5):
Let p⃗ = P⃗b. Then:
P p⃗ = P (P⃗b) = P 2⃗b
Long proof:
⃗a⃗aT ⃗a⃗aT ⃗a(⃗aT ⃗a)⃗aT ⃗a⃗aT
P2 = · = = =P ✓
⃗aT ⃗a ⃗aT ⃗a (⃗aT ⃗a)2 ⃗aT ⃗a
248CHAPTER 38. LECTURES 11 AND 12: LINEAR ALGEBRA FOUNDATION - SUBSPACES AND PROJ
38.7.1 Eigenvalues of P
From P ⃗x = λ⃗x, the two eigenvectors correspond to:
Expanding:
AT ⃗b − AT A⃗xp = ⃗0 =⇒ AT A⃗xp = AT ⃗b
Normal Equations:
⃗xp = (AT A)−1 AT ⃗b
P = A(AT A)−1 AT
This has the same form as the 1D case but generalised to matrices.
So the projection matrix becomes the identity matrix — every vector is already in
C(A) = Rn .
38.9. LINEAR REGRESSION (FINALLY!) 249
AT A⃗xp = AT ⃗b
ĉ
This gives the least squares solution ⃗xp = ˆ minimising ∥⃗b − A⃗x∥2 .
d
Summary: Regression is the projection of ⃗b onto the column space of A. The best-fit line
is b̂ = ĉ + dˆt, and the residual ⃗e = ⃗b − p⃗ is orthogonal to every column of A.
x1⃗a + x2⃗b = ⃗0 ⇐⇒ x1 = x2 = 0
24/03/26
Project : Project for human body (you)
→ Projection
2D
Given ⃗a and ⃗b
P⃗ =? (1368)
⃗b
⃗e = ⃗b − P⃗
⃗a
P⃗ ∈ C(A)
O
clp
⃗b ∈
/ C(A) (1369)
P⃗ ∈ C(A) (1370)
⃗a ∈ C(A) (1371)
251
252 CHAPTER 39. LECTURES 13 AND 14: PROJECTION AND REGRESSION
P⃗ = x⃗a (1373)
⃗a ⊥ ⃗e (1374)
⃗aT ⃗e = 0 (1375)
Ax = ⃗b (1376)
(m × n)(n × 1) = (m × 1) (1377)
N (A) = collection of ∞ vectors that gives linear dependencies among n columns of A (1381)
N (AT ) = collection of ∞ vectors that gives linear dependencies among m rows of A (1382)
⃗aT ⃗e = 0 (1383)
⃗aT ⃗b
x= (1386)
⃗aT ⃗a
" #
⃗
a T⃗
b
P⃗ = x⃗a = ⃗a T (1387)
⃗a ⃗a
T
⃗a⃗a
P = T ⃗b
⃗ (1388)
⃗a ⃗a
253
⃗a⃗aT
P = T projection matrix (1389)
⃗a ⃗a
Take an example
2
⃗a = (1390)
3
2
⃗aT ⃗a = 2 3 = 22 + 32 = 4 + 9 = 13 = |⃗a|2
(1391)
3
T 2 4 6
⃗a⃗a = 2 3 = (1392)
3 6 9
(2 × 1)(1 × 2) = 2 × 2 (1393)
→ Properties of P matrix
1. Square matrix
3. P T = P i.e symmetric
5. Projection property: P 2 = P
⃗a⃗aT
1 4 6
P = T = (1395)
⃗a ⃗a 13 6 9
T
⃗a⃗aT (⃗a⃗aT )T
T
P = = (1396)
⃗aT ⃗a (⃗aT ⃗a)T
⃗a⃗aT
= =P (1397)
⃗aT ⃗a
P⃗ = P⃗b (1398)
P⃗b = P⃗ (1399)
P⃗ = P 2⃗b (1401)
⇒ P = P2 (1402)
OR
254 CHAPTER 39. LECTURES 13 AND 14: PROJECTION AND REGRESSION
⃗a⃗aT
P = (1403)
⃗aT ⃗a
⃗a⃗aT ⃗a⃗aT
2
P = PP = (1404)
⃗aT ⃗a ⃗aT ⃗a
⃗a(⃗aT ⃗a)⃗aT
= (1405)
(⃗aT ⃗a)(⃗aT ⃗a)
(scalar)
⃗a⃗aT
= =P (1406)
⃗aT ⃗a
→ What is the eigen values and eigen vectors of P ?
P ⃗x = λ⃗x (1407)
The direction does not change, is the beauty of eigen vector.
eg:
Case I
y
⃗b
x
⃗a
P⃗b = ⃗0 (1408)
= 0⃗b (1409)
λ=0 (1410)
⃗b ⊥ ⃗a (1411)
eigen vector / value for λ = 0
Case II
⃗b = P⃗b (1412)
255
λ=1 (1414)
⃗b is along ⃗a (1415)
⃗a
⃗b
→ A⃗x = ⃗b
⃗b ∈
/ C(A) (1416)
(m × n)(n × 1) = (m × 1) (1417)
Project ⃗b onto C(A)
This is your model & data
⃗b ∈
/ C(A) (1419)
Data
You want to solve for A⃗x = ⃗b
You cannot solve for ⃗x
That’s why you have to go for regression
⃗b ∈
/ C(A)
⃗e
C(A)
p⃗ ∈ C(A)
⃗eT p⃗ = 0 (1423)
⃗e is the error vector
256 CHAPTER 39. LECTURES 13 AND 14: PROJECTION AND REGRESSION
What is p⃗ now?
Given A, ⃗b
p⃗ = A⃗xp (1424)
⃗xp you have to calculate.
If ⃗e ∈ N (AT ), then what is the property of vector.
AT ⃗e = ⃗0n (1425)
(m × n)T (m × 1) = (n × 1) (1426)
⇒ AT A⃗xp = AT ⃗b (1429)
So, now p⃗ is
p⃗ = P⃗b (1433)
Compare
C(A) = Rn (1438)
If take the vector which is not in column-space, it project that vector on column space.
P = PT, P2 = P (1440)
→ Example
3 points (1, 1), (2, 2), (3, 2)
(b, t) : Blood pressure
(3, 3)
(2, 2)
(3, 2)
(1, 1)
b=t (1441)
b = C + Dt (1442)
b ̸= t (1447)
inconsistent data
A⃗x = ⃗b (1448)
⃗b ∈
/ C(A) (1449)
258 CHAPTER 39. LECTURES 13 AND 14: PROJECTION AND REGRESSION
1 1 1
c ⃗b = 2
A = 1 2 , ⃗x = , (1450)
d
1 3 2
5 2 −1
1
P = 2 2 2 (3 × 3) (1452)
6
−1 2 5
A⃗xp = p⃗ (1453)
⃗xp =? (1454)
AT ⃗e = ⃗0 (1455)
AT ⃗b = AT A⃗xp (1457)
2
c
⃗xp = = 31 (1459)
d 2
7
1
p⃗ = P⃗b = 10 (3 × 1) (1460)
6
13
−1
1
⃗e = ⃗b − p⃗ = 2 (1461)
6
−1
⃗eT p⃗ = ⃗e · p⃗ = 0 ⇒ ⃗e ⊥ p⃗ (1462)
Now solve
A⃗xp = p⃗ (1463)
1 1 7/6
1 2 ⃗xp = 10/6 (3 × 2)(2 × 1) = (3 × 1) (1464)
1 3 13/6
You should do by Row reduction method.
1 1 7/6
1 2 10/6 (1465)
1 3 13/6
259
R3 → R3 − R1 (1466)
1 1 7/6
1 2 10/6 (1467)
0 2 6/6
R2 → R2 − R1 (1468)
1 1 7/6
0 1 3/6 (1469)
0 2 6/6
R3 → R3 − 2R2 (1470)
1 1 7/6
0 1 3/6 (1471)
0 0 0
x + y = 7/6 (1472)
7 1
x= − (1474)
6 2
4 2
x= = (1475)
6 3
Normal eqn
AT A⃗xp = AT ⃗b (1476)
A⃗xp = p⃗ (1477)
A⃗xE = ⃗b × (1478)
2 1
b = c + Dt = + t (1481)
3 2
260 CHAPTER 39. LECTURES 13 AND 14: PROJECTION AND REGRESSION
2.16
1.66 b3
p3
1.16 pb22
0.66 b1
p1
1 2 3
t bL
0 0.66 = 23
7
1 6 = 1.16 (1482)
5
2 3 = 1.66
13
3 6 = 2.16
−1
1
⃗e = 2 = −1e1 + 2e2 − 1e3 (1483)
6
−1
⃗e = ⃗b − p⃗ (1484)
7/6 1.16
p⃗ = 10/6 = 1.67 (1485)
13/6 2.16
Chapter 40
The score function for a single observation is the derivative of the log-likelihood with
respect to θ:
∂ log f (x1 ; θ)
W =
∂θ
261
262CHAPTER 40. LECTURES 15 AND 16: FISHER INFORMATION, MLE, AND REGRESSION
[k ′ (θ)]2
Var(Y ) ≥ (1491)
n I(θ)
where k ′ (θ) = dk/dθ and I(θ) is the Fisher information per observation.
40.3. UNBIASED ESTIMATORS AND EFFICIENCY 263
Cov(Y, Z) k ′ (θ)
ρ= p =p (1492)
Var(Y ) · Var(Z) Var(Y ) · n I(θ)
Since ρ2 ≤ 1:
[k ′ (θ)]2 [k ′ (θ)]2
≤ 1 =⇒ Var(Y ) ≥ .
Var(Y ) · n I(θ) n I(θ)
n
1X
θ̂ = X̄ = Xi (1494)
n
i=1
nσ 2 σ2
Var X̄ = 2 = (1496)
n n
264CHAPTER 40. LECTURES 15 AND 16: FISHER INFORMATION, MLE, AND REGRESSION
1 (x − µ)2
ℓ(µ) = − log(2πσ 2 ) −
2 2σ 2
CRLB σ 2 /n
Efficiency of X̄ = = 2 =1 (1497)
Var X̄ σ /n
X̄ is the Best Unbiased Estimator (BLUE) for µ, since it achieves the CRLB with
efficiency = 1.
with:
h i
E y (j) | ⃗x(j) ; θ⃗ = θ⃗⊤ ⃗x(j) (1503)
Var y (j) | ⃗x(j) ; θ⃗ = σ 2 (1504)
⃗ m m
∂J(θ) X (j) X (j)
= θ⃗⊤ ⃗x(j) − y (j) xi = hθ⃗ (⃗x(j) ) − y (j) xi (1513)
∂θi
j=1 j=1
40.7. BATCH GRADIENT DESCENT FOR LINEAR REGRESSION 267
where A is the design matrix, ⃗b is the output vector, and ⃗xp is the least-squares solution.
SSE to minimise:
First-order conditions:
∂ SSE
=0: 2(C + D − 1) · 1 + 2(C + 2D − 2) · 1 + 2(C + 3D − 2) · 1 = 0
∂C
which gives the system:
3 6 C 5
= ⇐⇒ A⊤ A ⃗xp = A⊤⃗b
6 14 D 11
Repeat {
for j = 1 to m:
for all i:
(k+1) (k) (j)
←− θi − α hθ⃗ (⃗x(j) ) − y (j) xi
θi
}
SGD is faster and often better than batch GD because it updates parameters after each
training example rather than after a full pass over the data.
Parameter vector: θ⃗ = (θ , θ , . . . , θ )
0 1 n
⊤
1 1
g(z) = 1+e−z
g(z)
0.5
0
−6 −4 −2 0 2 4 6
z = θ⃗⊤ ⃗x
40.8. LOGISTIC REGRESSION — BINARY CLASSIFICATION 269
⃗ = h⃗ (⃗x)
P [Y = 1 | ⃗x; θ] (1522)
θ
⃗ = 1 − h⃗ (⃗x)
P [Y = 0 | ⃗x; θ] (1523)
θ
So:
Y | ⃗x; θ⃗ ∼ Bernoulli hθ⃗ (⃗x)
The log-likelihood:
m n
X o
⃗ = log L(θ)
⃗ = y (j) log hθ⃗ (⃗x(j) ) + (1 − y (j) ) log 1 − hθ⃗ (⃗x(j) )
ℓ(θ) (1525)
j=1
⃗ m
∂ℓ(θ) X (j)
= y (j) − hθ⃗ (⃗x(j) ) xi (1526)
∂θi
j=1
Proof. For a single observation, let h = hθ⃗ (⃗x) = g(z), z = θ⃗⊤ ⃗x.
Step 1. Differentiate ℓ:
" #
∂ℓ X y (j) ∂h 1 − y (j) ∂h
= ·
(j) ) ∂θ
− ·
(j) ) ∂θ
∂θi
j
h ⃗
θ
(⃗
x i 1 − hθ⃗ (⃗
x i
(j)
Step 2. Use ∂g/∂θi = g(z)(1 − g(z)) xi :
∂h (j)
= hθ⃗ (⃗x(j) ) [1 − hθ⃗ (⃗x(j) )] xi
∂θi
Step 3. Substituting and simplifying:
" #
∂ℓ X y (j) (j) 1 − y (j) (j)
= · h(1 − h) xi − · h(1 − h) xi
∂θi h 1−h
j
X (j)
= y (j) (1 − h) − (1 − y (j) )h xi
j
X (j)
= y (j) − hθ⃗ (⃗x(j) ) xi
j
270CHAPTER 40. LECTURES 15 AND 16: FISHER INFORMATION, MLE, AND REGRESSION
Substituting (1526):
m
(k+1) (k) (j)
X (j)
θi ←− θi +α y − hθ⃗ (⃗x(j) ) xi (1528)
j=1
The update rules have the same form! The only differences are:
1
where hθ⃗ (⃗x(j) ) = (sigmoid)
e−θ⃗⊤ ⃗x
(j)
1+
m
(k+1) (k) (j)
X
hθ⃗ (⃗x(j) ) − y (j) xi
θi ←− θi −α (1530)
j=1
For linear regression (same form but hθ⃗ (⃗x(j) ) = θ⃗⊤ ⃗x(j) ):
m
(k+1) (k) (j)
X
θ⃗⊤ ⃗x(j) − y (j) xi
θi ←− θi −α (1531)
j=1
40.9. SUMMARY OF KEY FORMULAE 271
Repeat {
for j = 1 to m {
(k+1) (k) (j)
− α hθ⃗ (⃗x(j) ) − y (j) xi
for all i: θi ←− θi
}
}
[k ′ (θ)]2
CRLB: Var θ̂ ≥
n I(θ)
CRLB
Efficiency: ≤1
eff(θ̂) =
Var θ̂
P
MLE score equation: i ∂ log f (xi ; θ)/∂θ = 0
m
⃗ = 1 X ⃗⊤ (j)
Linear regression cost: J(θ) [θ ⃗x − y (j) ]2
2
j=1
(j) ) (j)
− y (j) ]xi
P
Gradient: ∂J/∂θi = j [hθ⃗ (⃗
x
1
Sigmoid: g(z) = , g ′ (z) = g(z)[1 − g(z)]
1 + e−z
Logistic log-likelihood: ℓ = j {y (j) log h + (1 − y (j) ) log(1 − h)}
P
(j)
Logistic gradient: ∂ℓ/∂θi = j [y (j) − hθ⃗ (⃗x(j) )]xi
P
(j)
Batch GD (linear): θi ← θi − α j [h(⃗x(j) ) − y (j) ]xi
P
(j)
SGD (logistic): θi ← θi − α[hθ⃗ (⃗x(j) ) − y (j) ]xi
Normal equation: A⊤ A ⃗xp = A⊤⃗b
272CHAPTER 40. LECTURES 15 AND 16: FISHER INFORMATION, MLE, AND REGRESSION
Notation Reference
Symbol Meaning
273
274CHAPTER 41. LECTURES 17 AND 18: MARKOV CHAINS AND NAIVE BAYES CLASSIFICATION
p 01 = P (Xn+1 = 1 | Xn = 0) = 1 − α
p 10 = P (Xn+1 = 0 | Xn = 1) = β
p 11 = P (Xn+1 = 1 | Xn = 1) = 1 − β
Transition Matrix:
α 1−α
P = (1535)
β 1−β
p 00 =1
p NN =1
Transition Matrix:
1 0 0 ··· 0 0
1 − p 0 p ··· 0 0
P = 0
1−p 0 ··· 0 0 (1539)
.. .. .. . . .. ..
. . . . . .
0 0 0 ··· 0 1
276CHAPTER 41. LECTURES 17 AND 18: MARKOV CHAINS AND NAIVE BAYES CLASSIFICATION
Chapter 42
42.1.1 Notation
Y ∈ {0, 1}: email label (0 = good/ham, 1 = spam).
A fixed dictionary (vocabulary) of n words: V = {w , w , . . . , w }.
1 2 n
277
278 CHAPTER 42. NAIVE BAYES CLASSIFIER
Symbol Meaning
Xn Random variable (state) at time n
pij Transition probability from state i to state j
P Transition probability matrix (rows sum to 1)
P (k) = P k k-step transition matrix
N Target fortune in Gambler’s Ruin
p Win probability per game in Gambler’s Ruin
Y Email class label (0 = ham, 1 = spam)
⃗ (j)
X Feature vector (word indicator) for email j
(j)
Xi 1 if word wi present in email j; 0 otherwise
n Vocabulary size (number of words)
V Vocabulary set {w1 , . . . , wn }
P (Y = y) Prior probability of class y
P (X⃗ = ⃗x | Y = y) Likelihood of email given class y
280 CHAPTER 42. NAIVE BAYES CLASSIFIER
Chapter 43
281
282CHAPTER 43. LECTURES 19 AND 20: ASYMPTOTIC DYNAMICS OF MARKOV CHAINS
fi = 1 (1548)
An equivalent characterization, and one that connects the recurrence condition to the spectral
properties of the transition matrix, is given by the divergence of the series of n-step return
probabilities:
∞
(n)
X
Pii = ∞ (1549)
n=1
The equivalence of these two conditions is a classical result in the theory of Markov chains.
P (n)
The divergence of n Pii signifies not merely that the process returns to state i, but that it
returns infinitely often with probability one—a much stronger statement about the chain’s
long-run behavior.
fi < 1 (1550)
and equivalently:
∞
(n)
X
Pii <∞ (1551)
n=1
The convergence of this sum reflects the fact that the process can only visit state i a finite
expected number of times. As time progresses, the probability of finding the chain in a
transient state diminishes to zero: the chain eventually “escapes” such states permanently.
This behavior stands in stark contrast to recurrent states, to which the chain perpetually
returns.
Positive recurrence is the “well-behaved” form of recurrence. States with this property not
only guarantee a return, but do so on a timescale that is, on average, bounded. In finite state
Markov chains, every recurrent state is in fact positive recurrent, making this distinction most
relevant in chains with infinite state spaces.
43.5. PERIODICITY AND APERIODICITY 283
E[Ti ] = ∞ (1553)
Null recurrent states represent an edge case in which the chain is guaranteed to return, but
the average waiting time grows without bound. Such states arise naturally in random walks
on infinite lattices, but they do not occur in finite state Markov chains.
43.7 Irreducibility
A Markov chain is said to be irreducible if all of its states belong to a single communicating
class:
All states belong to a single communicating class. (1554)
Equivalently, every state is accessible from every other state. Irreducibility is a global
structural property: it prevents the chain from becoming “trapped” in a subset of the state
space. In an irreducible chain, properties such as recurrence, transience, and periodicity are
shared by all states, because they are class properties.
284CHAPTER 43. LECTURES 19 AND 20: ASYMPTOTIC DYNAMICS OF MARKOV CHAINS
To illustrate, consider a Markov chain with state space {0, 1, 2, 3} and transition matrix:
0 12 1
0 2
1 0 0 0
P =
0
(1555)
1 0 0
0 1 0 0
One may verify that all four states communicate with one another—each is accessible from
every other via some finite sequence of transitions—and hence all states {0, 1, 2, 3} belong to a
single communicating class. The chain is therefore irreducible.
(n)
lim Pij (1556)
n→∞
(n)
lim Pij = πj (1557)
n→∞
The independence from the initial state i is the hallmark of ergodic behavior. No matter
where the chain begins, after a long time it “forgets” its origins and settles into a distribution
determined solely by the structure of the transition matrix. The collection {πj } defines the
limiting distribution of the chain.
The balance equations can be written compactly in matrix form as π = πP , where π is treated
as a row vector. The interpretation is immediate: if the distribution of the chain at time n is
π, then its distribution at time n + 1 is also π. A chain started in its stationary distribution
remains there forever.
For an ergodic chain, the stationary distribution is unique, strictly positive at every state, and
coincides with the limiting distribution.
43.10. MEAN RECURRENCE TIME 285
43.13 Conclusion
The theory of Markov chains presented here traces a coherent path from the structural notion
of accessibility and communication, through the classification of states, to the dynamical
condition of ergodicity that underpins long-run convergence. The stationary distribution,
characterized by the balance equations π = πP , serves as the centerpiece of this theory: it is
simultaneously the unique invariant measure of the chain, the long-run frequency distribution
of state visits, and the reciprocal of the mean recurrence times.
43.13. CONCLUSION 287
partStochasatic Processes
288CHAPTER 43. LECTURES 19 AND 20: ASYMPTOTIC DYNAMICS OF MARKOV CHAINS
Chapter 44
where:
X:Ω→R (1570)
generates
sample space −−−−−→ Real number (1571)
”An RV is a bridge between numbers and things which are not numbers
(outcomes).”
44.1.3 Randomness
The randomness of the process at any time n comes from the outcome ω:
Ω = {H1 H2 , H1 T2 , T1 H2 , T1 T2 } (1573)
| {z } | {z } | {z } | {z }
ω1 ω2 ω3 ω4
289
290CHAPTER 44. LECTURES 1 AND 2: INTRODUCTION TO STOCHASTIC PROCESSES
ω2 → Realization ω2
ω1
t
0
X(ω ) = 2,
1 Y (ω1 ) = 0
X(ω ) = 1,
2 Y (ω2 ) = 1
X(ω ) = 1,
3 Y (ω3 ) = 1
X(ω ) = 0,
4 Y (ω4 ) = 2
Note: X(ω) ̸= Y (ω) for all ω ∈ Ω2 , even though they share the same Ω.
t = 0, S 0 = 12 (Initial Info)
States
of SP (y)
48 ⋆ (Path or Trajectory 1) (ω1 )
24 ⋆
12⋆
6
3 (ω4 ) ⇒ Trajectory
0 1 2 Time (x)
0
9 AM 9:23 9:33 9:35 Continuous Time
one Realization of SP.
I [X = x , X = x , X = x , X
3 0 0 1 1 2 2 3 = x3 ] represents the observed partial path of the
stochastic process.
292CHAPTER 44. LECTURES 1 AND 2: INTRODUCTION TO STOCHASTIC PROCESSES
ω1
ω2
ω3
ω4
Fixed X0 ω5
0 1 2 3 4 5
x1 x2 x3
observe
Example:
E1 = [X = 1] = {ω2 } ∪ {ω3 } = {ω2 , ω3 } (1575)
where SY is the State Space of the process. The value of the process at time n is:
1. P : F → [0, 1]
2. P (Ω) = 1
P
3. For mutually exclusive events E1 , E2 , . . . , P (∪Ei ) = P (Ei ).
44.2. LECTURE 2: PROBABILITY AND STATE SPACES 293
1
2
x
0 1 1
2
A B
Ω
294CHAPTER 44. LECTURES 1 AND 2: INTRODUCTION TO STOCHASTIC PROCESSES
45.2.1 Parameters
45.2.2 Assumptions
The model assumes that in each individual slot, either 1 or 0 customers arrive. This binary
outcome is analogous to tossing a coin for each slot, where an arrival is a ”head” and no
arrival is a ”tail.”
S ∼ Bin(n, p)
295
296CHAPTER 45. LECTURES 3 AND 4: BERNOULLI PROCESSES AND ARRIVAL TIMES
Expected Value
The expected value represents the average number of customers we expect to see in a window
of size n.
E[S] = np (1589)
Variance
The variance measures the spread or uncertainty regarding the number of arrivals around the
mean.
Var[S] = np(1 − p) (1590)
p = P (Job arrival/Success)
1 − p = P (No job/Failure)
45.7. THE GEOMETRIC DISTRIBUTION 297
T1 ∼ geom(p)
1
E[T1 ] = (1592)
p
1−p
Var(T1 ) = (1593)
p2
Memoryless Property: A critical consequence of the independence of trials is the
memoryless property, meaning the probability of a success in the next trial does not depend
on how many failures have already occurred.
(L + 1) ∈ {1, 2, 3, . . . } =⇒ L ∈ {0, 1, 2, . . . }
In your analysis, you noted a distinction regarding the independence of these strings.
Specifically, if the starting point of the string is not independent of the last success, the
standard geometric assumptions may not apply directly to L + 1 in certain contexts.
1. Exactly (k − 1) successes must have occurred in the previous (t − 1) trials. This part
follows a Binomial Distribution: Bin(t − 1, p).
Wk = T1 + T2 + · · · + Tk (1596)
Since each Ti ∼ geom(p), the total waiting time Wk is simply the sum of k i.i.d. Geometric
random variables.
W 1 = T1 ∼ geom(p) when k = 1.
k
X
Wk = Ti (1597)
i=1
Since each Ti ∼ geom(p), Wk represents the sum of k i.i.d. geometric random variables.
Expected Value:
k k
" #
X X k
E[Wk ] = E Ti = E[Ti ] = (1598)
p
i=1 i=1
Variance: " k # k
X X k(1 − p)
Var[Wk ] = Var Ti = Var(Ti ) = (1599)
p2
i=1 i=1
1 1
Server R (pq) 0 0 0 0 0 0
q 1 1 1 1
Time
pM W = p + q − pq (1602)
Equation 1602 confirms the previous result using a more efficient probabilistic approach.
λ (Rate): Represents the average number of events per unit time. It has units of . 1
Time
f (t): This is the density, not a probability. The probability is found by integrating this
T
function over an interval.
Expectation: " k
# k k
X X X 1 k
E[Wk ] = E Ti = E[Ti ] = = (1607)
p p
i=1 i=1 i=1
Variance: " k # k
X X k(1 − p)
Var(Wk ) = Var Ti = Var(Ti ) = (1608)
p2
i=1 i=1
kq
Note: If we denote q = 1 − p, the variance can be written concisely as p2
.
303
304CHAPTER 46. LECTURES 5 AND 6: GEOMETRIC AND EXPONENTIAL DISTRIBUTIONS
Server R: pq
split prob q
Bern(p) Split
split prob 1 − q
Server B: p(1 − q)
Bern(p)
Bern(q)
Merged: p + q − pq
Conversely, the probability that the event takes longer than t is:
f (t) = λe−λt
By independence:
P (T > t) = P (T1 > t)P (T2 > t) = e−λ1 t · e−λ2 t = e−(λ1 +λ2 )t (1620)
T2
T2 = T1
T1 < T2
T2 < T1
T1
λ2 h2
P (T < h) ≈ 1 − 1 − λh + = λh + o(h) (1626)
2
Where o(h) represents terms that go to zero faster than h. For very small h, the probability of
an event occurring scales linearly with h.
Since h2 is vastly smaller than h as h → 0, we say this joint probability is o(h). This means
the probability of two independent exponential events occurring in the same infinitesimally
small window is effectively zero.
Counting Process
Stochastic Process N (t) ≥ 0
N (t) is a counting process that counts number of events that have occurred by time t.
Illustration:
N (s) = 3
continuous time
e1 e2 e3 s N (t) = 5
s = 7.6 t = 9.9
excluding s
=5−3 (1633)
=2 (1634)
Example 1:
Example 2:
N (t) = # of economic crisis since 1947
count N (t)
jump
jump
jump
t continuous time
t1 t2 t3
N (ω) = Nt (1639)
46.6. SMALL INTERVAL APPROXIMATIONS 309
Independent Increments
Number of events in disjoint time intervals are independent.
Consider times s1 < t1 < s2 < t2 · · · are time intervals,
[s1 , t1 ] [s2 , t2 ]
continuous time t
s1 t1 s2 t2
N (t1 ) − N (s1 ) N (t2 ) − N (s2 )
N (s2 ) − N (t1 )
Note: Independent increments does not mean that N (t) is independent of N (s), since
N (t) ≥ N (s).
N (s) N (t)
s t
Stationary Increments
The probability distribution of the number of events depends only on the length of the time
interval and not on the location of that interval.
Consider time intervals [0, t] and [s, s + t]:
N (t) N (s) N (s + t)
0 t s s+t
Bernoulli Process
Discrete time is divided into time slots. A Bernoulli trial (coin toss) occurs in each time slot.
X1 X2 X3 ··· Xi
Discrete time
Time slot Time slot Time slot Time slot
n=1 n=2 n=3 ··· n=i
Xi ∼ i.i.d (1643)
(
1 w.p. p
Xi = (1644)
0 w.p. 1 − p
Xi ∼ Bern(p) (1645)
The continuous time version of the Bernoulli process is the Poisson process.
n→∞
Discrete continuous time
Poisson Process
Continuous version of the Bernoulli Process.
Single probability experiment with ∞ stages.
Bernoulli Process: Discrete time in time slots. Number of arrivals of events in n time slots or
trials. Distribution (pmf) is Binomial.
A1 A2 A3 · · · Ak
0 T1 T2 T3 ···
Tk
T1 = 4 T2 = 5 T3 = 6
Time of 1st arrival, inter-arrival time between 1st & 2nd arrival
46.6. SMALL INTERVAL APPROXIMATIONS 311
Ti ∼ Geom(p) i.i.d
Bernoulli Process: B1 , B2 , . . .
(
1 w.p. p
Bi = and Bi is i.i.d
0 w.p. (1 − p)
T
start observing BP from time T
Xi ∼ Bern(p)
Events can occur anywhere in continuous time. The Poisson process is the continuous time
version of the Bernoulli process.
continuous time
0
τ τ
Properties of P (k, τ ):
1. Normalisation: X
P (k, τ ) = 1 for fixed τ (1647)
k
2. Time Homogeneity: P (k, τ ) depends only on the length τ of the time interval and not
on its location. (Analogous to the same success probability p across all time slots in the
Bernoulli process.)
Small interval probabilities. For a very small time interval δ, with λ denoting the rate
(intensity) of the arrival process:
1 − λδ,
if k = 0 (zero arrivals)
P (k, δ) = λδ, if k = 1 (one arrival) (1648)
0, if k > 1 (two or more arrivals)
P (1, δ)
lim =λ (intensity of process) (1649)
δ→0 δ
E N (0, δ) = 1 · (λδ) + 0 · (1 − λδ) + 0 = λδ (1650)
1 w.p. λδ
N (0, δ) = 0 w.p. (1 − λδ) (1651)
2, 3, 4, . . . w.p. 0
Observation: An interval of large length τ can be subdivided into n small intervals of length
δ, where nδ = τ .
δ δ δ ··· δ δ
τ τ
nδ = τ, n= , δ= (1653)
δ n
Derivation of the Poisson PMF. In the Bernoulli process with n time slots each of success
probability p = λτ /n:
k
λτ n−k
n λτ
P [k arrivals in n time slots] = 1− (1655)
k n n
As n → ∞ (with np = λτ held fixed), expanding:
k
λτ (n−k)
n! λτ
1−
k!(n − k)! n n
n − k + 1 (λτ )k λτ n λτ −k
n n−1
= · ··· · · 1− · 1−
n n n k! n n
The bracketed term → 1 and (1 − λτ /n)−k → 1 as n → ∞. For the exponential term, let
x = limn→∞ (1 − λτ /n)n :
46.6. SMALL INTERVAL APPROXIMATIONS 313
ln 1 − λτ
λτ n L’H −λτ n→∞
ln x = lim n ln 1 − = lim 1 = λτ
−−−→ −λτ
n→∞ n n→∞
n 1− n
n
λτ
⇒ 1− −→ e−λτ
n
Therefore:
(λτ )k e−λτ
P (k, τ ) = , k = 0, 1, 2, . . . (1656)
k!
Nτ ∼ Pois(λτ ), Nt ∼ Pois(λt)
E(Nt ) = λt = Var(Nt )
X ∼ Bin(n, p) Nτ ∼ Pois(λτ )
E(X) = np → λτ E(Nτ ) = λτ
Var(X) = np(1 − p) → λτ Var(Nτ ) = λτ
Example. You receive emails according to a Poisson process at rate λ = 5 msgs/hr. You
check your email every 30 minutes (τ = 12 hr), so λτ = 2.5.
(λτ )0 e−λτ
P [no new msgs] = P (0, τ ) = = e−2.5 ≈ 0.08
0!
(λτ )1 e−λτ
P [exactly 1 new email in 30 min] = P (1, 12 ) = = 2.5 e−2.5 ≈ 0.205
1!
314CHAPTER 46. LECTURES 5 AND 6: GEOMETRIC AND EXPONENTIAL DISTRIBUTIONS
Chapter 47
Independently
At a constant average rate
It is often called the “law of rare events”.
e−λ λx
P (X = x) = , x = 0, 1, 2, . . .
x!
where:
4. The probability of more than one event in a very small interval is negligible
315
316 CHAPTER 47. LECTURE 9: POISSON DISTRIBUTION DERIVATION
n→∞
p→0
np = λ (finite)
47.1.5 Cumulative Probability
x
X e−λ λk
P (X ≤ x) =
k!
k=0
47.1.6 Applications
Number of calls received at a call center per minute
Number of defects in a manufactured product
Number of accidents at a traffic signal
Number of customers arriving at a store
Let,
p = λδ = P (1 arrival in δ)
As δ → 0, n → ∞ such that nδ = τ (fixed).
Binomial Setup:
k
λτ n−k
n λτ
P (k arrivals in n time slots) = 1−
k n n
Rearranging:
λτ n
1 n(n − 1) · · · (n − k + 1) k
P = (λτ ) 1 −
k! nk n
47.1. POISSON DISTRIBUTION 317
As n → ∞:
n(n − 1) · · · (n − k + 1)
→1
nk
and
λτ n
1− → e−λτ
n
e−λτ (λτ )k
P (k) = , k = 0, 1, 2, . . .
k!
Let: k = number of arrivals in a time interval of length τ
Limit Derivation:
λτ
lim n ln 1 −
n→∞ n
Using log approximation:
ln(1 − x) ≈ −x as x → 0
λτ λτ
⇒ lim n ln 1 − = lim n −
n→∞ n n→∞ n
= −λτ
λτ
⇒ exp lim n ln 1 − = e−λτ
n→∞ n
Nτ ∼ Pois(λτ )
Probability Mass Function (PMF):
e−λτ (λτ )k
P (Nτ = k) = , k = 0, 1, 2, . . .
k!
Nt ∼ Pois(λt)
Mean and Variance:
E(Nt ) = λt
Var(Nt ) = λt
X ∼ Bin(n, p)
For large n and small p:
np = λτ
⇒ Bin(n, p) → Pois(λτ )
Final Insight:
The Poisson distribution arises as a limiting case of the Binomial distribution when:
n→∞
p→0
np = constant
Poisson Process Applications
Events such as email arrivals, calls, and accidents can be modeled using a Poisson process.
Variance Relationship:
Var(X) = np(1 − p)
As n → ∞ and p → 0:
np = λτ
⇒ Var(Nτ ) = λτ
Time interval:
1
t = 30 minutes = hour
2
1
λt = 5 × = 2.5
2
e−λt (λt)0
P (X = 0) =
0!
= e−2.5
47.1. POISSON DISTRIBUTION 319
≈ 0.082
e−λt (λt)1
P (X = 1) =
1!
= (2.5)e−2.5
= 2.5 × 0.082
≈ 0.205
Final Results:
0 −→ Y1 −→ Y2 −→ · · · −→ Yk
Interarrival Times:
T1 , T2 , . . . , Tk
Yk = T1 + T2 + · · · + Tk
Assumption:
Ti ∼ Exp(λ), Ti are i.i.d.
Nt ∼ Pois(λt)
PDF of Yk :
fYk (t) δ ≈ P (t ≤ Yk ≤ t + δ)
This represents the probability that the k th arrival occurs in a small interval (t, t + δ).
Interpretation:
For Yk to lie in (t, t + δ):
P (a ≤ X ≤ a + ∆) ≈ fX (a) ∆
Graphical Representation:
fX (x)
x
ab
Key Insight:
k
X
Yk = Ti
i=1
Ti ∼ Exponential(λ)
⇒ Yk ∼ Gamma(k, λ)
Final Summary:
N ∼ Pois(λt)
t
0 −→ Y1 −→ Y2 −→ · · · −→ Yk
Interarrival Times:
T1 , T2 , . . . , Tk
Y1 = T1 , Y2 = T1 + T2 , ..., Yk = T1 + T2 + · · · + Tk
k
X
Yk = Ti
i=1
Ti ∼ Exp(λ)
Nt ∼ Pois(λt)
PDF of Yk :
fYk (t) =?
fYk (t) δ ≈ P (t ≤ Yk ≤ t + δ)
Interpretation:
For Yk to lie in (t, t + δ):
P (a ≤ X ≤ a + ∆) ≈ fX (a) ∆
Key Result:
k
X
Yk = Ti
i=1
Ti ∼ Exp(λ)
⇒ Yk ∼ Gamma(k, λ)
Summary:
N ∼ Pois(λt)
t
= P (N (t) = k − 1) · (λδ)
e−λt (λt)k−1
P (N (t) = k − 1) =
(k − 1)!
Substitute:
e−λt (λt)k−1
fYk (t) δ = λδ ·
(k − 1)!
Divide by δ:
λk tk−1 e−λt
fYk (t) = , t≥0
(k − 1)!
47.1. POISSON DISTRIBUTION 323
Yk ∼ Erlang(λ, k)
λk tk−1 e−λt
fYk (t) = , k = 1, 2, 3, . . .
(k − 1)!
Special Case:
For k = 1:
Y1 ∼ Exponential(λ)
As n → ∞, total time t = nδ
Nt ∼ Poisson(λt)
Comparison Table
Key Relations
N ∼ Poisson(λt)
t
Interarrival time:
Y1 ∼ Exponential(λ)
Given: λ = 1
Consider the time interval split:
[0, 5] = [0, 2] ∪ [2, 5]
Number of arrivals:
N[0,2] ∼ Poisson(2)
N[2,5] ∼ Poisson(3)
e−λt (λt)k
P (Nt = k) =
k!
So,
e−2 2k
P (N[0,2] = k) =
k!
e−3 3k
P (N[2,5] = k) =
k!
E[N[0,2] ] = 2, E[N[2,5] ] = 3
N[0,5] ∼ Poisson(5)
Independence Property:
For disjoint intervals,
N[0,2] and N[2,5] are independent
Define:
P = P1 + P2
k
X e−λ1 t (λ1 t)i e−λ2 t (λ2 t)k−i
= ·
i! (k − i)!
i=0
k
X (λ1 t)i (λ2 t)k−i
= e−(λ1 +λ2 )t
i!(k − i)!
i=0
Using MGF:
MGF of Poisson(λt):
MP (t) = exp λt(es − 1)
Conclusion:
P1 + P2 ∼ Poisson((λ1 + λ2 )t)
General Result:
If
Pi ∼ Poisson(λi t), i = 1, 2, . . . , n
then
n n
! !
X X
Pi ∼ Poisson λi t
i=1 i=1
t
P ∼ Pois(λ) (Σ) λ1 + λ2 e[(λ1 +λ2 )(e −1)]
y
x+y =1
⇒ pz = px ∗ py ↗ convolution
Convolution
Binomial Theorem
X λ(k−y) λy
= 1 2
· e−(λ1 +λ2 )
y
(k − y)! y!
X ∼ Pois(λ1 ), Y ∼ Pois(λ2 )
47.1. POISSON DISTRIBUTION 327
X k! λ(k−y) λy
(λ1 + λ2 )k = 1 2
y
(k − y)! y!
k ⩾ y, 0⩽k
(k − y)! y! λ1 + λ2 → p
λ2 ⩾ q
X n! p(n−y) q y
(p + q)n =
y
y! (n − y)!
By Binomial Theorem
X k! λ(k−y) λy 1 (λ1 + λ2 )k
1 2
· −→
y
(k − y)! y! k! k!
328 CHAPTER 47. LECTURE 9: POISSON DISTRIBUTION DERIVATION
Chapter 48
Lecture 11 and 12
Xn ∈ S = {0, 1, 2, . . . , i, i + 1, . . . }
an SP Xn is a DTMC if
⃗ Markov
P Xn+1 = j | Xn = i, X = ⃗x −−−−→ P [Xn+1 = j | Xn = i] = pn,ij ∀i, j ∈ S
| {z } | {z } | n−1 {z n−1}
Future Present Past History
Typically in a DTMC time doesn’t exist outside any of these time intervals, (it is not
measured).
⊛ Also, How you get to a certain state Xn = i, does not matter. Only the present state
determines the outcome of the future state.
329
330 CHAPTER 48. LECTURE 11 AND 12
States
j
n
n n+1
0.2
0.8 H A 0.7
0.3
HH 0.6 0.4
AH 0.4 0.6
HA 0.7 0.3
AA 0.95 0.05
State Diagram:
331
0.85
HA AA 0.15
0.1
0.9 0.6
0.4
AH HH 0.25
0.75
Transition Matrix P :
0.25 0.75 0 0 HH
0 0 0.6 0.4 AH
P =
0.1 0.9 0 0 HA
0 0 0.85 0.15 AA
Matrix Properties:
−2 −1 0 1 2
Diagram
332 CHAPTER 48. LECTURE 11 AND 12
p p p p p
... i−1 i i+1 i+2 ...
q q q q q
If p < 1/2
If p > 1/2 If p = 1/2, moves about zero.
0 n n
0
0 n
1 1
p p p p p p p
0 1 2 ... i i+1 ... J −1 J
q = (1 − p)q = (1 − p) q = (1 − p)
q = (1 − p) q = (1 − p)
Gambler Gambler
Gets Wins
Ruined
States = (J + 1)
0 and J are called absorbing states as they enter these states and stay there forever.
P00 = 1
Xn = State of gamblers at time n
Pi,i+1 = p
∀i ∈ {1, 2, 3, . . . , J − 1} Xn ∈ S
Pi,i−1 = q
n = 0, 1, 2, . . .
PJJ = 1
333
Gambler’s Ruin
→ You place Rs b bets
P (Ei ) =? ⇒ P (Xn = J | X0 = i) =?
Probability Foundations:
According to Law of Total Prob:
P (A) = P (A ∩ B) + P (A ∩ B c )
P (B) = P (B | A) × P (A)
P (A ∩ B | F ) = P (A | B, F )P (B | F )
334 CHAPTER 48. LECTURE 11 AND 12
P (Xn = J | X0 = i)
P (Xn = J ∩ X0 = i) = P Xn = J ∩ (X1 = 1 ∪ X1 = 2 · · · ∪ Xn = i)
P (A ∩ B | F ) = P (A | B, F )P (B | F )
P (B | F ) = P (B, A | F ) + P (B, Ac | F )
P (Ei ) = P [Xn = J, X1 = i + 1 | X0 = i]
+ P [Xn = J, X1 = i − 1 | X0 = i]
Substituting back:
+ P [Xn = J | X1 = i − 1] × P [X1 = i − 1 | X0 = i]
| {z }
=q
i = 0 ⇒ δ0 = P [Xn = J | X0 = 0] = 0
i = J ⇒ δJ = P [Xn = J | X0 = J] = 1
335
Derivation:
Since p + q = 1, we can rewrite δi as δi (p + q):
⇒ δi (p + q) = pδi+1 + qδi−1
δi p + δi q = pδi+1 + qδi−1
p(δi+1 − δi ) = q(δi − δi−1 )
q
⇒ (δi+1 − δi ) = (δi − δi−1 )
p
⇒ (δi+1 − δi ) = α(δi − δi−1 )
i = 1 ⇒ (δ2 − δ1 ) = α(δ1 − δ0 )
i = 2 ⇒ (δ3 − δ2 ) = α(δ2 − δ1 ) ⇒ α2 (δ1 − δ0 )
⇒ α + α2 + α3 + · · · + αJ−1 (δ1 − δ0 )
For upto i − 1:
⇒ α + α2 + α3 + α4 + · · · + αi−1 (δ1 − δ0 )
⇒ δi − δ1 = α + α2 + α3 + · · · + αi−1 (δ1 − δ0 )
Since δ0 = 0, we can rewrite this by moving δ1 to the RHS (effectively adding 1 to the
bracketed series):
δi = 1 + α + α2 + · · · + αi−1 (δ1 − 0)
δi = 1 + α + α2 + · · · + αi−1 δ1
1 − αi
1 + α + α2 + · · · + αi−1 =
1−α
1 − αi
⇒ δi = δ1
1−α
336 CHAPTER 48. LECTURE 11 AND 12
1 − αJ
1−α
δJ = 1 = δ1 ⇒ δ1 =
1−α 1 − αJ
1 − αi
1−α
δi = × for α = q/p ̸= 1
1−α 1 − αJ
1−αi
δi = 1−αJ
When α = 1:
This implies q = p = 1/2 (a fair game with equal odds).
δi = 1 + 1 + 12 + · · · + 1i−1 δ1
δi = iδ1
F
Applying boundary condition δJ = 1:
δJ = 1 ⇒ Jδ1 = 1 ⇒ δ1 = 1/J
δi = iδ1 ⇒ δi = i(1/J)
HW:
Perform Gambler’s Ruin without
formula in Python for:
α = 1, α < 1, α > 1
Favour Gambler
When α < 1 ⇒ q < p ⇒ P (lose) < P (win)
1 − αi J→∞⇒αJ →0
δi = −−−−−−−−−→ (1 − αi )
1 − αJ Since α<1
Result → 1
337
αi − 1 J→∞ αi J→∞
δi = −−−−→ −−−→ 0
αJ − 1 αJ ≫1 αJ
Result → 0
Regular Gamblers lose w.p 1 (win w.p 0)
To Xn+1
P11 P12 . . . P1m
P (n) = P21 P22 . . . P2m
From Xn ..
.. .. ..
. . . .
Pi1 Pi2 . . . Pim
338 CHAPTER 48. LECTURE 11 AND 12
Chapter 49
49.1 Introduction
Stochastic processes serve as the mathematical foundation for modeling systems that evolve
over time under uncertainty, a concept central to modern financial econometrics and risk
management. This section explores two fundamental pillars of probability theory: the Poisson
Process and Discrete-Time Markov Chains (DTMC).The Poisson Process provides a bridge
between discrete event counts and continuous time. By assuming that inter-arrival times
follow an Exponential Distribution, we leverage the memoryless property, ensuring that the
probability of a future event is independent of the time elapsed since the last occurrence. As
we aggregate these waiting times, we transition from the simple Exponential PDF to the
Erlang (or Gamma) Distribution, which describes the time required for a specific number of
arrivals (r) to occur. This relationship is rigorously proven through the link between the
Poisson Cumulative Distribution Function and the survival probability of arrival
[Link] from counting processes to state-based evolution, we introduce the Markov
Property. Here, the ”memoryless” concept is applied to sequences of random variables where
the future state depends solely on the present, rendered independent of the historical path.
Whether analyzing arrival rates in a queue or the shifting states of a financial market, these
models provide the analytical rigor necessary to quantify randomness in complex,
time-dependent systems.
t is continuous time
0 1 2 3
w2
339
340 CHAPTER 49. LECTURE 13 AND 14: POISSON PROCESS PROPERTIES
wi ∼ Exp(λ) i.i.d. i = 1, 2, 3, . . .
Memoryless Property: The process looks the same no matter when we start waiting.
t1 t2
N (I) = 2
w1
× × × × t
0 1 2 3
(t2 − t1 ) =I length(I)
Counting Variable (N (I)): Instead of looking at when things happen, we look at how
many things happen in a fixed window I. This is a discrete random variable.
This means that knowing how many events occurred in the interval (t1 , t2 ) provides zero
information about how many will occur in the future interval (t3 , t4 ).
w1
Nt3 = 0
× continuous time
t3
Tr = (w1 + w2 + · · · + wr ) (1659)
We know that wi ∼ Exp(λ) i.i.d. for i = 1, 2, . . . , r. The PDF of Tr is given by the Erlang or
Gamma Distribution:
λr tr−1 e−λt
fTr (t) = (1660)
(r − 1)!
Survival Probability
The probability that the r-th event occurs after time t (the Survival Probability) is equivalent
to saying there have been fewer than r events by time t:
r−1
X
P [Tr > t] = P [Nt ≤ (r − 1)] = P [Nt = k] (1661)
k=0
342 CHAPTER 49. LECTURE 13 AND 14: POISSON PROCESS PROPERTIES
Case II: The (r − 1)th event occurs before t, but the rth hasn’t.
If the (r − 1)th person arrived already, but we are still waiting for the rth arrival, then
at time t, exactly (r − 1) people have arrived.
In this scenario: Nt = (r − 1)
Conclusion: The event [Tr > t] is logically equivalent to the union of these cases:
(r − 1)th rth
× × Time
0 t Tr
2. Probability Summation
Since Nt is a Poisson Random Variable with mean λt, the probability of the count being less
than or equal to r − 1 is the sum of the individual probabilities for k = 0, 1, . . . , r − 1:
r−1 −λt
X e (λt)k
P (Tr > t) = P (Nt ≤ r − 1) = (1662)
k!
k=0
3. PDF Derivation: The Probability Density Function fTr (t) is the derivative of the
CDF:
r−1 −λt
" #
d d X e (λt)k
fTr (t) = FTr (t) = 1− (1663)
dt dt k!
k=0
This derivation proves that the sum of r i.i.d. exponential variables (the time Tr ) follows an
Erlang distribution, which can be expressed via the Poisson CDF.
49.1. INTRODUCTION 343
Explanation: By shifting the second index from k to p, we align the terms so they can be
compared directly.
344 CHAPTER 49. LECTURE 13 AND 14: POISSON PROCESS PROPERTIES
Mathematical Logic
Every term from z0 to zr−2 in the first bracket is subtracted by the corresponding term
in the second bracket. This is known as a telescoping sum. Only the term for k = r − 1
survives.
Summary: This proves that the time until the rth arrival in a Poisson Process with rate λ
follows the Erlang Distribution with parameters (r, λ).
Case 1: N t = 0 and N (t, t + h) = r. (Zero arrivals before t, all r arrivals happen in h).
...
Case r: N t = r − 1 and N (t, t + h) = 1. (The r − 1 event occurred before t, and exactly
the rth event occurs in h).
Nt = k N (t, t + h) = r − k
×
0 t th
r eventt + h
t h
49.1. INTRODUCTION 345
Nt = r − 1 N (t, t + h) = 1
2. Probability Calculation
Using the Independent Increments property:
P [N = (r − 1)] =
t
e−λt (λt)r−1
(r−1)!
If r is an integer, then Γ(r) = (r − 1)!. This allows us to write the Gamma PDF (which is the
Erlang PDF for integer r) as:
Time Index: n = 0, 1, 2, . . .
State Space (S): A discrete set of states S = {0, 1, 2, . . . , i, i + 1, . . . }.
Random State (X ): The state of the system at time n.
n
Xn ∈ S = {0, 1, 2, . . . , i, i + 1, . . . }
X0 , X1 , X2 , . . . , Xn , . . .
DTMC Definition:
Xn is a DTMC if:
Interpretation:
Future → X n+1
Present → X n
347
348 CHAPTER 50. DISCRETE TIME MARKOV CHAINS (DTMC)
xn+1 = j
xn = i
x2
Past history x1
x0
present future
Discrete Time
0 1 2 3 5 6 7
Transition is happening here
n n+1
P (Xn+1 = H | Xn = H) = 0.8
Tomorrow depends only on today.
Important Note:
Rows = present state
Columns = next state
Two different distributions possible
Higher Order Model Idea
Suppose tomorrow depends on today and yesterday.
Then not a Markov chain.
We expand state:
Recurrence vs Transience
Infinite states.
State space:
S = {0, 1, 2, . . . , J}, |S| = J + 1
p00 = 1, pJJ = 1
pi,i+1 = p, pi,i−1 = q
pij = 0 otherwise
Game Description
Bet Rs b.
Win ⇒ gain Rs b
Lose ⇒ lose Rs b
Initial wealth = Rs ib
Bias factor:
q P (lose)
α= =
p P (win)
reach 0 (ruin)
reach J (target wealth)
351
Probability of Winning
Let:
Ei = {reach J before 0}
si = P (Ei ) = P (Xn = J | X0 = i)
Using Law of Total Probability:
si = P (Ei |X1 = i + 1)P (X1 = i + 1|X0 = i) + P (Ei |X1 = i − 1)P (X1 = i − 1|X0 = i)
Using Markov property:
si = psi+1 + qsi−1
352 CHAPTER 50. DISCRETE TIME MARKOV CHAINS (DTMC)
Recurrence Relation
si = psi+1 + qsi−1
Let:
q
α=
p
(s2 − s1 ) = α(s1 − s0 )
(s3 − s2 ) = α2 (s1 − s0 )
Summation
si − s0 = (1 + α + α2 + · · · + αi−1 )(s1 − s0 )
Geometric series:
1 − αi
si = (s1 − s0 )
1−α
Boundary conditions:
s0 = 0, sJ = 1
1 − αJ
1= (s1 )
1−α
1−α
s1 =
1 − αJ
Final:
1 − αi
si =
1 − αJ
Special Cases
Case 1: α = 1
si = is1
1
1 = Js1 ⇒ s1 =
J
i
si =
J
Case 2: α < 1
50.1. INTRODUCTION TO DTMC 353
1 − αi
si =
1 − αJ
As J → ∞:
si → 1 − α i
If i → ∞, si → 1
Case 3: α > 1
αi − 1
si =
αJ − 1
As J → ∞:
si → 0
Winning probability → 0
sasi Gokul.P
April 2026
S = {1, 2, 3, . . . , n}
Detailed Explanation:
1 = Sunny
2 = Rainy
3 = Cloudy
At any time n, the system takes one value from S.
This represents the probability of moving from state i to state j in one step.
For a fixed current state i, there are multiple possible next states.
Each possible movement has an associated probability.
Important Understanding:
Fundamental Property:
n
X
Pij = 1
j=1
Why?
k) × P (k j)
m
(2)
X
Pij = P (i
k=1
Deep Meaning:
Transient
May not return.
Positive Recurrent
Returns quickly (finite time).
Null Recurrent
Returns slowly (infinite expected time).
Problem
Given Markov Chain:
1 0.3
0.2
R3 T1 0.2 R1
0.2
T2 0.2 R2
0.4
Transient state
P (Xn = R3 | X0 = R3 ) = 1
= P ∪n≥1 {Xn = i} | X0 = i
If i is recurrent ⇒ fi = 1
If i is transient fi < 1 ⇒ (1 − fi ) > 0 probability of escaping
⇒ I want show R1 is recurrent ⇒ fR1 = 1
First you have to define an event:
We are starting at X0 = R1
359
360 CHAPTER 51. LECTURE 18: MARKOV CHAINS IN MATRIX FORM
fi = P (return)
∞
X
fi = P (Xn+1 = R1 , Xn ̸= R1 , . . . , X2 ̸= R1 , X1 ̸= R1 | X0 = R1 )
n=0
∞
X
= 0.3 + (0.7)(0.4)n−1 (0.6)
n=1
∞
X
= 0.3 + (0.7)(0.6) (0.4)n−1
n=1
= 0.3 + 0.7
= 1.00
⇒ fR1 = 1
⇒ Now what about fT1 ?
n=0: P (X1 = T1 | X0 = T1 ) = 0
∞
X
= (0.6)(0.6)
n=1
= 0.36
= 0.64
⇒ Transient states
i↔j
Two way communication
i→j and j → i
One way communication
(n)
(i → j) : pij > 0 for some n
(m)
(j → i) : pji > 0 for some m
Two way communication is an equivalence relation on a set of states S.
It has following properties:
(i) Reflexive:
(0)
i ↔ i since pii = 1
(ii) Symmetric:
If i ↔ j then j ↔ i
(n) (m)
i ↔ j ⇒ pij > 0 and pji > 0
(m) (n)
⇒ pji > 0 and pij > 0
(iii) Transitive: for i, j, k ∈ S
If i ↔ j and j ↔ k then i ↔ k
i → j, j→k
(n) (m)
⇒ pij > 0, pjk > 0
Take t = n + m
362 CHAPTER 51. LECTURE 18: MARKOV CHAINS IN MATRIX FORM
(n+m)
⇒ pik >0
Similarly,
k → j, j→i
(m) (n)
⇒ pkj > 0, pji > 0
Take t = n + m
(n+m) (m) (n)
X
pki = pkj pji
j∈S
(n+m)
⇒ pki >0
∴ i↔k
As we did before
S = {T1 , T2 , R1 , R2 , R3 }
= I(X1 = i | X0 = i) + I(X2 = i | X0 = i) + · · ·
( (n)
1 if Xn = i w.p. pii
I(Xn = i | X0 = i) = (n)
0 if Xn ̸= i w.p. 1 − pii
P (Ni = n) = fin (1 − fi )
(Geometric)
fi < 1 ⇒ i is transient
Geometric distribution:
P (Y = k) = (1 − p)k−1 p
1
E(Y ) =
p
363
Ni ∼ geom(1 − fi )
1
E[Ni ] =
1 − fi
If i is recurrent ⇒ fi = 1
1 1
E[Ni ] = = =∞
1−1 0
Ni ∼ geom(1 − fi )
1
E[Ni ] = , fi < 1
1 − fi
Now from this definition,
∞
X
Ni = I(Xn = i | X0 = i)
n=1
∞
" #
X
E[Ni ] = E I(Xn = i | X0 = i)
n=1
∞
X
= E[I(Xn = i | X0 = i)]
n=1
∞
X
= P (Xn = i | X0 = i)
n=1
∞
(n)
X
= pii
n=1
∞
1 X (n)
⇒ E[Ni ] = = pii
1 − fi
n=1
If i is transient:
1
E[Ni ] = <∞
1 − fi
∞
(n)
X
⇒ pii < ∞
n=1
If i is recurrent:
∞
(n)
X
E[Ni ] = pii = ∞
n=1
Theorem
If state i is recurrent and i ↔ j then state j is recurrent.
Proof:
364 CHAPTER 51. LECTURE 18: MARKOV CHAINS IN MATRIX FORM
i ↔ j ⇒ i → j and j → i
(n) (m)
pij > 0 and pji > 0 for some n, m
Then for any n > 0 we have
To show j ∈ S is recurrent:
∞
(t)
X
pjj = ∞
t=1
l steps
n steps m steps
j i j
Choose t ∈ (l + n + m)
∞
(l+n+m) (n) (l) (m)
X
pjj ≥ pji pii pij
n=1
∞
" #
(n) (n) (m)
X
= pji pii pij
n=1
= ∞ since i is recurrent
⇒∞
n = 0, 1, 2, . . .
defines the full stochastic process: the current state depends on all past states.
365
A stochastic process {Xn } is called a Markov Chain if it satisfies the Markov Property:
That is,
P (Xn+1 = j | Xn = i, Xn−1 , . . . , X0 ) = P (Xn+1 = j | Xn = i).
future 0 future 1
present 0 0.5 0.5
P =
present 1 0.5 0.5
Problem Statement
Suppose it rains today and will rain tomorrow with probability α. If it does not rain
today, it will rain tomorrow with probability β.
Let Xn denote whether it rains on the n-th day:
(
0 rains on day n
Xn =
1 does not rain on day n
State 0 State 1
α 1−β
Rain No Rain
State Meaning
0 1 2 3
0 0.7 0 0.3 0
1 0.5 0 0.5 0
P =
2 0 0.4 0 0.6
3 0 0.2 0 0.8
0 1 2 3
0 0.43 0.12 0.21 0.18
1 0.35 0.20 0.15 0.30
P (2) = P2 =
2 0.20 0.12 0.20 0.48
3 0.10 0.16 0.10 0.64
Answer: Given it rained on Monday and Tuesday, we start in state 0. The probability
of raining on Thursday (two steps later, state 0) is:
(2)
P00 = 0.43
51.1. NUMERICAL 2 — GAMBLER’S RUIN PROBLEM 367
For (P 2 )00 :
p00 = 1, pN N = 1.
Setup
Each feature:
(
(j) 1 if word i (wi ) is present in email j
Xi =
0 if word i (wi ) is absent from email j
h i
⃗ (j) = ⃗x(j) = ?
P Y = y (j) X
i.e., given the word-vector of email j, what is the probability it belongs to class y?
⃗ = ⃗x]
P [Y = y | X Posterior
⃗ = ⃗x | Y = y]
P [X Likelihood
P [Y = y] Prior
⃗ = ⃗x]
P [X Normalisation (evidence)
generates
Y −−−−−→ X1 , X2 , . . . , Xn
51.2.6 ⃗
Distribution of X
Since each Xi ∈ {0, 1}, the vector ⃗x takes values in {0, 1}n . There are 2n possible email
vectors.
2 (2n − 1) + 1
Why Naive Bayes reduces this. By the conditional independence assumption, the
number of parameters reduces to:
2n
|{z} + |{z}
1 = 2n + 1
class-conditional prior
Dataset Setup
e0 0 0 0 —
e1 1 0 0 —
e2 0 1 0 —
e3 1 1 0 —
e4 0 0 1 —
e5 0 1 1 —
e6 1 1 1 —
e7 1 1 1 —
Training Data
From the notes, the training set contains 5 spam emails:
g1 0 0 1 spam
g2 0 0 1 spam
g3 0 0 0 spam
g4 0 1 1 spam
g5 0 0 1 spam
And the good (ham) emails have the class-conditional probabilities as listed in Section 4.7.
e0 1/5 0
e1 0 1/5
e2 3/5 0
e3 0 2/5
e4 1/5 0
e5 0 0
Expanding:
⃗ = ⃗x∗ | Y = y] P [Y = y]
ŷ = arg max P [X
y
51.3. QUICK REFERENCE — NOTATION TABLE 371
2(2n − 1) + 1 2n n→∞
≈ −−−→ ∞
2n + 1 n
Symbol Meaning