EECS126 Notes

Lecturers: Kannan Ramchandran and Abhay Parekh

Scribe: Michael Whitmeyer

Jan 2020 - May 2020 (with some examples from Fall 2018)

1
Contents
1 Lecture 1: Overview and beginning of CS70 Review 4
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Conditional Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Lecture 2: Independence, Bayes Rule, Discrete Random Variables 6

2.1 Bayes Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Discrete Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Lecture 3: Expectation, Uniform, Geometric, Binomial and Poisson Distributions 9

3.1 Expectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Some Popular Discrete Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Lecture 4: (Co)variance, Correlation, Conditional / Iterated Expectation, Law of Total Variance 14

4.1 Geometric RV and Properties, Poisson RV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Conditioning of RVs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

5 Lecture 5: Iterated Expectation, Continuous Probability, Uniform, Exponential Distributions 19

5.1 Iterated Expectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2 Continuous Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

6 Lecture 6: Normal Distribution, Continuous Analogs, Derived Distributions 24

6.1 Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.2 Normal Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.3 Continuous Analogs of Discrete RVs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

7 Lecture 7: Order Statistics, Convolution, Moment Generating Functions 28

7.1 Conditional Variance and Law of Total Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
7.2 Order Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
7.3 Convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
7.4 Moment Generating Functions (MGFs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

8 Lecture 8: MGFs, Bounds/Concentration Inequalities (Markov, Chebyshev, Chernoff) 32

8.1 Properties of MGFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
8.2 Limiting Behavior of RV’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

9 Lecture 9: Convergence, Weak and Strong Law of Large Numbers, Central Limit Theorem 38
9.1 Recap of Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

10 Lecture 10: Information Theory 41

10.1 Proof of CLT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
10.2 Intro to Info Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

11 Lecture 11: Info Theory, Binary Erasure Channel 44

11.1 Capacity of BEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

12 Lecture 12: Wrapup of Info Theory 48

12.1 Huffman Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

13 Lecture 13: Markov Chains 51

14 Lecture 14: More Markov Chains 56

14.1 First-step equation modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
14.2 Reversibility of MCs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

2
15 Lecture 15: Wrapup (reversible) Markov Chains, and beginning Poisson Processes 60
15.1 Reversible MCs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
15.2 Poisson Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

16 Lecture 16: Properties of Poisson Processes 63

16.1 Merging and Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
16.2 Erlang Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

17 Lecture 17: CTMCs 66

17.1 Random Incidence Paradox (RIP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
17.2 Continuous-Time Markov Chains (CTMCs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

18 Lecture 18: More on CTMCs 68

18.1 Hitting Times . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
18.2 Simulating a CTMC with a DTMC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

19 Lecture 19: Random Graphs 73

19.1 recap of CTMCs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
19.2 Random Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

20 Lecture 20: Wrapup of Random Graphs and Starting Statistical Inference 77

20.1 Statistical Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

21 Lecture 21: Wrapup of MLE/MAP and Hypothesis Testing/Neyman-Pearson 79

21.1 Wrapup of MLE/MAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
21.2 Hypothesis Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

22 Lecture 22: Wrapup of Hypothesis Testing and Beginning of LLSE 84

22.1 Proof of Neyman-Pearson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
22.2 Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

23 Lecture 23: Geometry of RV’s: LLSE and MMSE 86

23.1 Hilbert Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
23.2 Properties of LLSE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

24 Lecture 24: MMSE and Jointly Gaussian Random Variables 90

24.1 Recap of LLSE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
24.2 MMSE Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
24.3 Jointly Gaussian RVs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

25 Lecture 25: Jointly Gaussian Random Variables and Scalar Kalman Filter 95
25.1 Jointly Gaussian RVs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
25.2 Kalman Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

26 Lecture 26: Kalman Filter 100

26.1 Orthogonal Updates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
26.2 Scalar Derivation of Kalman filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

27 Extra Content: Hidden Markov Models 105

28 Extra Content: Expectation Maximization 107

3
1 Lecture 1: Overview and beginning of CS70 Review
1.1 Motivation
1. Uncertainty is all around us!
2. This course is about formalizing how to predict things.
3. Actually has origins in gambling
4. First need to develop model (requires understanding of the problem as an experiment), and then need
to solve (using combinatorics, calculus, common sense, etc). As engineers, we need to do both, but
often it is (perhaps unexpectedly) the modelling that is more difficult than the solving.
5. Last but certainly not least (for many of you), foundational for ML/AI.

1.2 Content

Definition 1.1. A Sample Space Ω of an experiment is the set of all outcomes of the experiment.
The outcomes must be mutually exclusive (ME) and collectively exhaustive (CE)

Example 1.2. Toss two fair coins. Then we have Ω = {HH, HT, T H, T T }. Can check that these
outcomes are mutually exclusive and collectively exhaustive.

Definition 1.3. An Event is simply an allowable subset of Ω.

Example 1.4. In Ex 1.2 an event would be getting at least 1 Head

Definition 1.5. A Probability Space (Ω, F, P ) is a mathematical construct that allows us to model
these ”experiments”. Here F denotes the set of all possible events, where each event is a set containing
0 or more base outcomes (for discrete Ω this is simply the power set of Ω). And P : F 7→ [0, 1] is a
function assigning probabilities to each event.

All of Probability Theory rests on just 3 (2.5?) axioms (Kolmogorov):

1. Pr(A) ≥ 0 for all A ⊆ Ω
2. Pr(Ω) = 1
3. Pr(A1 ∪ A2 ∪ ...) = Pr(A1 ) + Pr(A2 ) + . . . for all disjoint A1 , A2 , . . . . This can be finite or we can
take n → ∞ and this becomes countable additivity.
We immediately have the following fundamental facts:
1. Pr(Ac ) = 1 − Pr(A)
2. Pr(A ∪ B) = Pr(A) + Pr(B) − Pr(A ∩ B)
Sn Pn
3. Union bound: Pr ( i=1 Ai ) ≤ i=1 Pr(Ai )
4. Inclusion-Exclusion:
n
!
[ X X X
Pr Ai = Pr(Ai ) − Pr(Ai ∩ Aj ) + Pr(Ai ∩ Aj ∩ Ak ) − . . .
i=1 i<j i<j<k
P
In the discrete setting, just from the axioms, we have that Pr(A) = ω∈A Pr(ω). If our sample space is
uniform, then we have that Pr(A) = |A| |Ω|

4
1.3 Conditional Probability

Definition 1.6. In general, we use the notation Pr(A|B) = the probability that event A has occurred
given that we know that B has occurred.

Proposition 1.7 (Bayes Rule).

Pr(A ∩ B)
Pr(A|B) =
Pr(B)
”B is the new Ω”

Example 1.8. We roll two six sided die, and observe that the sum of the two die is 11. What is is
the probability that the first die was a 6? Here let A = event of a 6 on the first die and B = event
of sum being 11.
Pr(A ∩ B) Pr({6, 5}) 1
Pr(A|B) = = =
Pr(B) Pr({6, 5}) + Pr({5, 6}) 2

Bayes Rule directly extends to the Product Rule, which says that

Pr(A1 ∩ A2 ∩ ... ∩ An ) = Pr(A1 ) Pr(A2 |A1 ) Pr(A3 |A1 ∩ A2 ) · · · Pr(An |A1 ∩ ... ∩ An−1 )

We also can develop the Law of Total Probability, which says that for mutually exclusive and collec-
tively exhaustive events A1 , ..., An , we have that
n
X
Pr(B) = Pr(A1 ∩ B) + ... + Pr(An ∩ B) = Pr(Ai ) Pr(B|Ai )
i=1

This can be easily visualized via the following picture:

In the picture, we partition the sample space indicated by the whole box into the mutually exclusive and
collectively exhaustive events A1 , A2 , A3 , A4 , A5 . Conditioned on each of these, there is some probability
that B occurs, and so we can find the total probability that B occurs by considering each case separately.

5
2 Lecture 2: Independence, Bayes Rule, Discrete Random Variables
We will begin with a cool example.

Example 2.1 (Birthday Paradox). Want to estimate Pr(at least two people in a group of size n share
the same birthday). First we note that |Ω| = k n = 365n . The problem is that this event is a bit
complicated. So we will consider the complement: Ac = “no two people share a birthday” Then,
since the distributions are uniform, we have

|Ac | 365 × 364 × · · · × (365 − n + 1)

Pr(Ac ) = =
|Ω| 365n
1 2 n−1
= 1(1 − )(1 − ) · · · (1 − )
k k k
≈ e−1/k e−2/k · · · e−(n−1)/k
1
= e− k (1+···+n−1)
2
≈ e−n /k
.

So then we have that 2

Pr(A) = 1 − Pr(Ac ) ≈ 1 − e−n /k
.
It turns out, for k = 365 and n = 23, we get a roughly 50% chance of two people having the same
birthday!

2.1 Bayes Theorem

Bayes Theorem was motivated by disease testing.

Example 2.2 (False Positive Quiz). We are testing for a rare disease, and our test has the following
properties:
• If person has disease, we detect with 0.95 probability.
• If person doesn’t have the disease, test is negative wp 0.95

• Random person has disease wp 0.001

Let A be the event that the person has the disease, and B be the event that the person tests
positive. We would like to calculate Pr(A|B). We have via Bayes Theorem that

Pr(B|A) Pr(A)
Pr(A|B) =
Pr(B|A) Pr(A) + Pr(B|Ac ) Pr(Ac )
(0.95)(0.001)
= = 0.0187
(0.95)(0.001) + (0.999)(0.05)

Most doctors, when asked, said this probability was 95%. The main contributing factor here is
the fact that the prior Pr(A) = 0.001 is so small. If we change the scenario and have Pr(A) = 0.01,
then our new probability Pr(A|B) = 0.16, so we should be more worried. Note that the doctor would
actually be correct if the disease were present in 1/2 of the population.

Definition 2.3. Two events are Independent if the occurrence of one provides no information about
the occurrence of the other. i.e.
Pr(A|B) = Pr(A)

6
 which is equivalent to saying
Pr(A ∩ B) = Pr(A)P r(B)
Extending this, a collection of events S are independent if
\ Y
Pr( Ai ) = Pr(Ai )
i∈S i∈S

Remark 2.4. Pairwise independence does not imply joint independence.

Remark 2.5. Being disjoint does not imply independence, nor does the implication hold in the other
direction. If A, B are disjoint, then Pr(A ∩ B) = 0, and independence tells us that Pr(A ∩ B) =
Pr(A) Pr(B), which would tell us for two events to be both disjoint and independent, at least one
of the two events must have zero probability of occurring. Note that this tells us that base outcomes
of our probability space, which are all disjoint by definition, and all have nonzero probability by
definition, must not be independent.

Definition 2.6. Conditional Independence is when Pr(A ∩ B|C) = Pr(A|C) Pr(B|C). Then we
say that A and B are “conditionally independent given C”.

Example 2.7. Say we have two coins, one with tails on both sides, one with heads on both sides. We
pick one up at random, and we flip it twice. We also let Hi be the event that that ith flip is a heads.
Note immediately that H1 and H2 are decidedly not independent. Now we denote A as the event of
us picking the two-headed coin. Then we have that Pr(H1 ∩ H2 |A) = Pr(H1 |A) Pr(H2 |A ∩ H1 ) =
Pr(H1 |A) Pr(H2 |A). So this is an example of events that are conditionally independent but not
themselves independent.

Exercise 2.8. Construct an example of RVs that are independent, but not conditionally independent.

Example 2.9. I roll two fair die. What is the probability I see a 6 before I see a 7? Let’s use
independence to attack this problem.
Lets condition on the first roll. Let S be the event that the first roll of the two die is a 6, and T
be the event that the first roll is a 7. Let E be the event we are looking for, that we see a 6 before
we see a 7. Then we have

Pr(E) = Pr(E|S)P r(S) + Pr(E|T )P r(T ) + Pr(E|(S ∪ T )c ) Pr((S ∪ T )c )

= 1 × 5/36 + 0 × 6/36 + Pr(E) × 25/36
=⇒ Pr(E) = 5/11

2.2 Discrete Random Variables

Definition 2.10. Random Variables associate a real number with each possible outcome. They are
inherently a function f : Ω → R.

7
 Why is this useful? If we are stuck with only events, we have no numbers to work with, we can’t calculate
means and variances and we cannot do statistics. Heads and tails only gets us so far, but if we assign the
value 0 or 1 now we can do math.

Example 2.11 (Some random variables). 1. The RV X has value i if the throw of a die is i.

2. X 2 is a perfectly valid random variable.

Consider rolling two four-sided dice. Then Mk is the event that the min is k, whereas we can say M
is the random variable that is equal to the value of the minimum of the two die. By enumerating all the
possible values of the two die roll (which are all equal probability), we can see that M = 1 wp 7/16, M = 2
wp 5/16, M = 3 wp 3/16, and M = 4 wp 1/16. This mapping from values of a RV to probabilities for
discrete random variables is known as a probability mass function or PMF, and in a way it defines the
random variable.

There are nigh on an uncountable number of notations you will see for PMFs, but I’ll just briefly go over
the one’s you’ll see in these notes. We let the PMF of a RV X be PX , and we say PX (x) = Pr({X = x}),
often simply denoted Pr(X = x). We also have to have (in order for our PMF to be valid), that
X X
PX (x) = 1, P (X ∈ S) = PX (x)
x x∈S

Example 2.12 (chess). Imagine Vishy Anand is playing Kasparov in chess (when they are at the
height of their power). They play 10 games, and for each individual game, the probability Anand
wins is 0.3, the probability that Kasparov wins is 0.4, and then probability that they draw is 0.3. The
first to win a game wins the match, and if there are ten consecutive draws then the match is drawn.
Question: what is the PMF of the duration of the match L? We have that
(
0.39 l = 10
PL (l) =
0.3l−1 · 0.7 1 ≤ l ≤ 9

Question: What is the probability that Anand wins the match?

9
X
Pr(A wins the match) = (0.3)l (0.3)
l=0

which can be simplified using the formula for a geometric series.

8
3 Lecture 3: Expectation, Uniform, Geometric, Binomial and Poisson
Distributions
Agenda:

1. Recap of Discrete RVs and Probability Mass Functions (PMF)

2. Expectation
3. Some popular Discrete RVs
4. Variance

As a reminder, discrete random variables (DRVs) associate a real number with each possible outcome,
so they are really just functions from Ω → R. The distribution or PMF is the collection of values {a, PX (a) :
a ∈ A} where A is the set of all possible values taken by the RV X

Remark 3.1 (Functions of RVs are still RVs). Let Y = g(X). Then we have
X
PY (y) = PX (x)
{x|g(x)=y}

An RV itself is a function, and the function of a function is still a function!

Example 3.2. Let Y = |X|, where X is uniformly distributed between −2 and 2. So then PX (x) =
1/5, ∀x ∈ {−2, −1, 0, 1, 2}. Then PY (y) = 2/5 for y = 1, 2 and PY (y) = 1/5 for y = 0.

3.1 Expectation

Definition 3.3. We have the expectation of a discrete RV X that takes on values in a set X is
X
E[X] = xPX (x)
x∈X

P
Alternatively, we also have E[X] = ω∈Ω X(ω)P (ω)

Theorem 3.4 (Expectations of Functions of RVs). Let Y = g(X). Then we have that
X X
E[Y ] = y Pr(Y = y) = g(x) Pr(X = x)
y x

Note that there are no restrictions on the function g, so it holds for any function.

Proof. We start by noting X

Pr(Y = y) = Pr(X = x)
x:g(x)=y

9
Then, we have that
X X X
E[Y ] = y Pr(Y = y) = y Pr(X = x)
y y x:g(x)=y
X X
= g(x) Pr(X = x)
y x:g(x)=y
X
= g(x) Pr(X = x).
x

We can then use the above theorem to prove linearity of expectations!

Theorem 3.5. (Linearity of Expectation)

We have
E[X + Y ] = E[X] + E[Y ]
for arbitrary X and Y that are defined on the same probability space. This of course generalizes (via
induction) to more than just two RVs.

Proof. We let g(X, Y ) = X + Y . Then, according to the above theorem, we have that
X
E[X + Y ] = (x + y) Pr(X = x, Y = y)
x,y
X X
= x Pr(X = x, Y = y) + y Pr(X = x, Y = y)
x,y x,y
XX XX
= x Pr(X = x, Y = y) + y Pr(X = x, Y = y)
x y y x
X X X X
= x Pr(X = x, Y = y) + y Pr(X = x, Y = y)
x y y x
X X
= x Pr(X = x) + y Pr(Y = y) (law of total probability)
x y

= E[X] + E[Y ].
The extremely important property of linearity of expectations, which you may already be familiar with,
is that this holds even if X and Y are dependent on each other. The fact that we don’t need any assumptions
about independence is what makes the linearity property of expectation so powerful and useful!

Example 3.6. The average of the sum of two rolls of the dice X1 , X2 is

E[X] = E[X1 + X2 ] = E[X1 ] + E[X2 ] = 7

Example 3.7. Suppose Prof Ramchandran collects homeworks from n students, shuffles them
randomly, and then hands them back (at random). What is the expected number of students who
get their homework back? More formally, what is the expected number of fixed points in a random
permutation of n points?

Solution: Let Xi be the indicator RV that equals 1 if student i gets their homework back,
and equals 0 otherwise. Then we can note that the number of students who get their homework back
X, is exactly equal to X1 + ... + Xn . So then
n
X X 1
E[X] = E[X1 + ... + Xn ] = E[Xi ] = i = 1n Pr(Xi = 1) = n · =1
i=1
n

10
 Remarkably, we see that the expected number of fixed points is always 1, regardless of how large or
small n is. This technique of defining indicator RVs and applying linearity of expectation is extremely
powerful and will come up over and over again in this course. When in doubt, come up with some
indicators!

Remark 3.8. The Xi ’s in the previous example are not independent (exercise: why?), yet we can
still apply linearity of expectation!

2
Definition 3.9. We define the Variance of a RV X, sometimes denoted σX is

Var(X) = E[(X − E[X])2 ]

And furthermore the standard deviation is

p
σX = Var(X)

Exercise 3.10. From the definition of variance derive that

Var(X) = E[X 2 ] − E[X]2

Theorem 3.11 (Discrete Tail Sum Formula). The (discrete) tail sum formula that we know and love
for positive valued random variables is
X ∞
X
E[X] = x Pr(X = x) = Pr(X ≥ k)
x k=1

There is a derivation that just does some tricks with algebra inside summations, but first I will give a
hopefully more intuitive picture of what is going on here.

P∞
Consider the above picture. The regular formula for expectation, E[X] = k=1 k Pr(X = k), is equivalent
P∞
to calculating the area of the above graph horizontally, while the tail sum formula k=1 Pr(X ≥ k), is
equivalent to calculating the area of the above graph vertically.
Proof. Now we give the (less intuitive) algebraic proof:
∞
X
E[X] := x Pr(X = x)
x=1
Px
notice here that x Pr(X = x) = k=1 Pr(X = x), so then we have:

11
 ∞ X
X x
E[X] = Pr(X = x)
x=1 k=1
X∞ X ∞
= Pr(X = x)
k=1 x=k
X∞
= Pr(X ≥ k)
k=1

P∞ Px P∞ P∞
Exercise 3.12. Convince yourself that x=1 k=1 Pr(X = x) = k=1 x=k Pr(X = x). It may
help to draw a graph of an arbitrary distribution, with Pr(X = x) as the y-axis and x as the x-axis.

3.2 Some Popular Discrete Random Variables

Definition 3.13 (Discrete Uniform RV). The discrete uniform distribution over [n] = {1, ..., n} has
PMF:
1
PX (k) = , ∀k ∈ [n]
n

n+1
We can easily see that for uniform X, we have E[X] = 2 .

Definition 3.14 (Bernoulli (”coin flip”) RV). The Bernoulli(p) RV takes on the value 1 with probability
p, and 0 with probability 1 − p. Explicitly:
(
p if k = 1
PX (k) =
1 − p if k = 0

And we can easily calculate that E[X] = p. We also have

Var(X) = E[X 2 ] − E[X]2 = p − p2 = p(1 − p)

Definition 3.15 (Indicator RV). An indicator RV of an event A takes on the value of 1 if A happens/is
true and 0 otherwise: (
1 A is true
X = {1}A = 1A =
0 else

We can note then that

E[1A ] =
X
x Pr(X = x) = Pr(A)
x

Definition 3.16 (Binomial Random Variable). If X ∼ Bin(n, p) then we define the PMF (probability
mass function) as:  
n k
PX (k) = Pr(X = k) = p (1 − p)n−k
k
The Binomial
Pn distribution is by definition also just the sum of n iid Bernoulli variables with parameter
p. X = i=1 Bi where Bi ∼ Ber(p)

12
 It is not too difficult to calculate the expectation and variance of a binomial random variable, precisely
because it can be represented as the sum of n i.i.d. Bernoullis. We have that we can use linearity of
expectations to calculate the expectation of X ∼ Bin(n, p). We have
n
X n
X n
X
E[X] = E[ Bi ] = E[Bi ] = p = np
i=1 i=1 i=1

Example 3.17. Let Y = aX + b. Then we have that

Var(Y ) = Var(aX + b) = E[(aX + b) − E[aX + b]]

= E[((aX + b) − (a E[X] + b))2 ]
= E[(aX − a E[X])2 ]
= a2 E[(X − E[X])2 ]
= a2 Var(X)

Note that adding a constant does not affect the variance, nor should it intuitively, as we are simply
shifting where the variable occurs and not affecting the spread of the variable at all. Multiplying by
a constant, however, should and does affect the spread and therefore the variance of an RV.

Definition 3.18 (Geometric Random Variable). A geometric random variable counts the time until the
first success. We have that the PMF of a geometric random variable with parameter p (the probability
of success is p) is as follows:
Pr(X = k) = (1 − p)k−1 p
The above formula makes sense because we need the first k−1 events to be failures, which happen with
probability 1 − p, and then we need the k th event to be a success, which happens with probability p.
Also intuitively, if we want to calculate the probability Pr(X > k), then we need the first k events to
all be failures, and it does not matter at all what happens after that. Therefore, Pr(X > k) = (1−p)k ,
which tells us that the CDF of a geometric RV is Pr(X ≤ k) = 1 − Pr(X > k) = 1 − (1 − p)k . As a
sanity check, we can differentiate the CDF and find that it does indeed equal the PDF.

We can also calculate more easily the expectation of geometric random variable using the tail sum formula.
We have that
∞ ∞
X X 1
E[X] = Pr(X ≥ k) = (1 − p)k−1 =
i=1 i=1
p
Where the last step follows from the formula for infinite geometric series.

13
4 Lecture 4: (Co)variance, Correlation, Conditional / Iterated Expec-
tation, Law of Total Variance
Agenda

1. Recap of expectation, their properties, and popular RVs

2. Memoryless property of Geometric(p) RVs

3. Conditional RV and Iterated Expectation

4. Covariance

4.1 Geometric RV and Properties, Poisson RV

Example 4.1 (Coupon Collector Problem). Imagine we have N balls of different colors, and we sample
with replacement. What is the expected number of trials before we see all of the colors? To address
this problem, we start by defining a few variables. Let Cr be the number of samplings required
until we see at least r distinct colors. Then we know that C1 = 1 and is in fact not at all random.
We further define Xi as the number of samplings required to see i distinct colors given that we
have already seen i − 1 colors. We note here also that each Xi is a geometric random variable with
parameter (probability of success) p = N −i+1
N We also note that we have

N
X
CN = Xi
i=1

Then,
N
X N N
E[CN ] = E[Xi ] = 1 + + + ... + N ≈ N log N
i=1
N −1 N −2

Definition 4.2 (Poisson Random Variable). We define X ∼ P ois(λ) with the following PMF:

λk e−λ
Pr(X = k) =
k!

In general, the parameter λ describes a rate, i.e. the number of customers entering the store in a hour.
We can calculate for X ∼ P ois(λ) the expectation:
∞ ∞ ∞
X λk e−λ X λk e−λ X λk−1
E[X] = k = k = λe−λ = λe−λ eλ = λ.
k! k! (k − 1)!
k=0 k=1 k=1

Exercise 4.3. Prove that for X ∼ P ois(λ):

Var(X) = λ

Exercise 4.4 (Poisson Merging). Prove that for X ∼ P ois(λ) and Y ∼ P ois(µ) we have X + Y ∼
P ois(λ + µ) (this is done in discussion)

14
 Exercise 4.5 (Poisson splitting). Prove that if we ”split” X ∼ P ois(λ) into two paths, by having an
arrival take one path with probability p and the other with probability 1 − p. Prove that the number
of arrivals to the first path Y is P ois(pλ) and is moreover independent of the number of arrivals to
the second path Z, which is distributed according to P ois((1 − p)λ). (this is a homework problem)

We now explore the relationship between the binomial distribution and poisson distribution. The poisson
distribution actually turns out to be a limit of the binomial distribution, as we let n get large and p go to
zero. Specifically, we must have that limn→∞ npn = λ. Consider letting p = nλ . Then we get the PMF for
the binomial becomes:
 
n λ k λ
Pr(X = k) = ( ) (1 − )n−k
k n n
n(n − 1)...(n − k + 1) λk λ
= k
(1 − )n−k
n k! n
n n − 1 n − k + 1 λk λ n λ
= ... (1 − ) (1 − )k .
n n n k! n n
Now, as we let n → ∞, we can see that the first k left terms go to 1, as well as the rightmost term. We
also know that the second to rightmost term approaches e−λ . This leaves us with the pdf for the poisson
k −λ
distribution: Pr(X = k) = λ k!
e
.

Example 4.6 (St. Petersburg Paradox). I keep tossing a fair coin until I get heads. If this takes n
tosses, then I get 2n dollars. How much should I pay to play this game? Well, if W is the amount I
win, we can calculate:
∞
X 1 1 1 1
E[W ] = 2k = 2( + 4 + 8 + . . . ) = 1 + 1 + 1 + .... = ∞
2k 2 4 8
k=0

So I should pay an unbounded amount to play this game? Bernoulli said we should actually calculate
log U where U is our utility/payout, in which case we would only pay $4 to play this game.

Lemma 4.7. If X and Y are independent,

E[XY ] = E[X] E[Y ]

Proof.
XX
E[XY ] = xyPXY (x, y)
x y
XX X X
= xyPX (x)PY (y) = xPX (x) yPY (y) = E[X] E[Y ].
x y x y

Remark 4.8. The converse is generally not true:

6
E[X] E[Y ] = E[XY ] =⇒ X is independent of Y

15
 Lemma 4.9. If X and Y are independent,

Var(X + Y ) = Var(X) + Var(Y )

Proof. Without loss of generality (WLOG), we can say E[X] = E[Y ] = 0, since variance is not affected by
the shifting of a constant and therefore subtracting out the means does not alter the variance. Then if we
let Z = X + Y , we have

Var(Z) = Var(X + Y ) = E[(X + Y )2 ] = E[X 2 + Y 2 + 2XY ]

= E[X 2 ] + E[Y 2 ] + 2 E[X] E[Y ] = Var(X) + Var(Y ).

The above two lemmas of course generalize to more than just two independent variables via induction.
We can also use the above lemma to calculate the variance of a binomial very easily, since a binomial
X ∼ Bin(n, p) is equal to B1 + · · · + Bn , where each Bi ∼ Bern(p). Then, we have that (since the Bi are
iid)
Xn Xn n
X
Var(X) = Var( Bi ) = Var(Bi ) = p(1 − p) = np(1 − p)
i=1 i=1 i=1

The above lemma raises the question, what if X1 and X2 are not independent, but we would like to
calculate Var(X1 + X2 )?

Definition 4.10 (Covariance). Consider Var(X + Y ) = E[(X + Y − E[X] − E[Y ])2 ]. Now let X̂ =
X − E[X] and Ŷ = Y − E[Y ]. Then

Var(X + Y ) = E[(X̂ + Ŷ )2 ] = E[X̂ 2 ] + E[Ŷ 2 ] + 2 E[X̂ Ŷ ].

This last term, E[X̂ Ŷ ], is called the covariance of X and Y , and it tells us how they change with
each other. We have that

Cov(X, Y ) = E[(X − E[X])(Y − E[Y ])] = E[XY ] − E[X] E[Y ].

Intuitively, the covariance between two variables is related to how they affect each other. If X1 increasing
causes X2 to generally increase, then the covariance will be positive. If X1 increasing causes X2 to generally
decrease, then the covariance will be negative.

Definition 4.11 (Correlation Coefficient).

Cov(X, Y )
ρ(X, Y ) = p
Var(X) Var(Y )

The above is known as the correlation coefficient of two variables, and is always between -1 and 1.
This can be proved using the Cauchy-Schwarz Inequality (try it!)

4.2 Conditioning of RVs

When we consider X|Y , the first thing to note is that this is just another random variable, with its own
PMF PX|Y (x|y) = Pr(X = x|Y = y). Therefore, we must still have that
X
PX|Y (x|y) = 1
x

16
 Lemma 4.12 (Memorylessness of Geometric RVs). We have that for geometric RV X

Pr(X = k + m|X > k) = Pr(X = m)

Proof.

Pr(X = k + m|X > k) = Pr(X = k + m ∩ X > k)/ Pr(X > k)

Pr(X = k + m) (1 − p)k+m−1 p
= =
Pr(X > k) (1 − p)k
= (1 − p)m−1 p = Pr(X = m).

We can use a clever conditioning trick, along with the memorylessness property, to calculate the variance
of a geometric random variable. First, we need E[X 2 ]. We have by total probability:

E[X 2 ] = E[X 2 |X = 1] Pr(X = 1) + E[X 2 |X > 1] Pr(X > 1)

= p + (1 − p) E[(1 + X)2 ],

where E[X 2 |X > 1] = E[(1 + X)2 ] follows from the memorylessness property (convince yourself this is true).
Then,
2
E[X 2 ] = p + (1 − p)(1 + + E[X 2 ])
p
2 − 2p 2−p
=⇒ p E[X 2 ] = 1 + =
p p
2 − p
=⇒ E[X 2 ] = .
p2
Then we have that
2−p 1 1−p
Var(X) = E[X 2 ] − E[X]2 = 2
− 2 = .
p p p2

Example 4.13 (Romance is dead). 2m people form couples. 50 years from now, the probability that
any person is alive is p. Now suppose that there are A people alive after 50 years. Let S be the
number of couples for which both people are still alive. We would like to find E[S|A = a]. In order
to do this, we further define Xi as the indicator that the first personPof couple i survives, and Yi as
the indicator that the second person of couple i survives. Then S = i Xi Yi . Then, we have
X X
E[S|A = a] = E[ Xi Yi |A = a] = E[Xi Yi |A = a]
i i
= m E[Xi Yi |A = a]
= m Pr(Xi Yi = 1|A = a)
a a−1
=m
2m 2m − 1
2m−2


a−2
=m 2m

.
a

Why have we included the last equality, rather than simplifying further? Because it lends itself to an
alternate interpretation of the solution. Consider couple i. What is the probability that they survive,
given that A = a? Well 2m−2


a−2 is the number of ways for a people to survive including this specific

17
 2m


couple, and a is the number of ways for a people to survive in general. More formally, we have:

Pr(A = a|Xi Yi = 1) Pr(Xi Yi = 1)

Pr(Xi Yi = 1|A = a) =
Pr(A = a)

Now, A is a Bin(2m, p) and A|Xi Yi = 1 is a Bin(2m − 2, p). So we have:

2m−2 a−2


a−2 p (1 − p)2m−a p2
= 2m a


2m−a
a p (1 − p)
2m−2


a−2
= 2m

.
a

And all we have to do is use linearity of expectations (and multiply by m) to get the same answer as
above.

18
5 Lecture 5: Iterated Expectation, Continuous Probability, Uniform,
Exponential Distributions
Agenda

1. Law of Iterated Expectations

2. Continuous probability (CDF, Uniform, Exp)

5.1 Iterated Expectation

Recall how conditional expectation works:
X
E[X|Y = y] = x Pr(X = x|Y = y)
x

We say that E[X|Y = y] is the “expectation of X w.r.t. the distributions of X conditioned on Y = y, and
it is really just a number.

Definition 5.1. Let X and Y be RVs. Then E[X|Y ] is also a RV, the conditional expectation of X
given Y , which has the value E[X|Y = y] with probability Pr(Y = y). It is important but subtle to
note that E[X|Y ] is a RV itself.

Example 5.2. Suppose we roll a die N times. Let X be the sum of the die rolls. Then we have that
7
E[X|N = 1] =
2
E[X|N = 2] = 7
7n
and in general, E[X|N = n] = 2 , and in general:

7N
E[X|N ] =
2
The difference here is subtle, but the last equality is actually a much stronger statement, as it equates
random variables rather than just numbers.

Out of this comes a natural question: since E[X|Y ] is a RV, what is its expectation?

Theorem 5.3 (Iterated Expectations/Tower Rule).

E[E[X|Y ]] = E[X]

Proof.
X
E[E[X|Y ]] = E[X|Y = y] Pr(Y = y)
y
XX
= x Pr(X = x|Y = y) Pr(Y = y)
y x
X X
= x Pr(X = x, Y = y)
x y
X
= x Pr(X = x) = E[X].
x

19
 Example 5.4. We roll a die N times where N ∼ Geom(p). As before, X represents the sum of the
N die rolls. Then we have:
 
7N 7 7
E[X] = E[E[X|N ]] = E = E[X] =
2 2 2p

Example 5.5 (Drunken walk on a line). Suppose we take a random walk, starting at the origin, on a
discretized line. Then if Xn+1 is our location at time n + 1, then we have the recurrence:

Xn+1 = Xn + 1+ − 1−

where 1+ is an indicator for drunk taking a +1 step, and likewise 1− is an indicator for drunk taking
a −1 step. Then we have:

E[Xn+1 ] = E[Xn ] + 1/2 − 1/2 = E[Xn ] = 0

But what about the variance of the walk? E[Xn2 ] =?. We have
2
Pr(Xn+1 = (k + 1)2 |Xn = k) = Pr(Xn+1
2
= (k − 1)2 |Xn = k) = 1/2

So then we have:
2 (k + 1)2 + (k − 1)2
E[Xn+1 |Xn = k] = = k2 + 1
2
2
=⇒ E[Xn+1 |Xn ] = Xn2 + 1
Then we can calculate
2 2
E[Xn+1 ] = E[E[Xn+1 |Xn ]] = E[Xn2 ] + 1
2
= E[Xn−1 +1+1
and then, after noting E[X02 ] = 0, we can see that

Var(Xn ) = E[Xn2 ] = n

5.2 Continuous Probability

Continuous RVs is a concept you should be relatively familiar with from CS70, but we will go over it quickly
again and there are some subtleties to make sure are clear.

In most settings, a continuous sample space is more natural than a discrete one (such as distance,
time, temperature, etc). For a continuous RV, there is no such thing as Pr(X = x). Well there is, but
it’s just equal to zero and generally pretty meaningless. We need to instead define probability over sets
that have ”length” and quantify ”allowable events”. What ”allowable events” refers to here gets more into
measure theory, which we are not going to get into in this course, as in virtually all engineering applications
the distinction is unimportant. So rather than talking about Pr(X = x), we instead talk about fX , which
is the probability density function (PDF) of a continuous random variable.

Definition 5.6. X is a continuous RV if

1. ∃ a non-negative function fX s.t.
Z
P(X ∈ B) = fX (x)dx
B

20
 is well-defined.
2. It must hold that Z ∞
fX (x)dx = 1
−∞

The function f is characterized by the random variable X, hence the subscript.

Remark 5.7. Pr(X = a) = 0, which means that Pr(X < a) = Pr(X ≤ a) for continuous random
variables, and henceforth I will be lazy and interchange < and ≤ for continuous RVs at will.

This density has the property that if we wish to calculate the probability that our random variable falls
in a small δ sized interval, we have
Z x+δ
Pr(X ∈ [x, x + δ]) = fX (t)dt ≈ fX (x)δ
x

for small enough delta, of course. Then we have

Pr(X ∈ [x, x + δ])

fX (x) ≈
δ
Hence the name ”density function”. Note that it is perfectly fine for the density to be greater than 1 at
any particular point, as it is not a probability. We have only the requirement that the integral of fX
over its domain must be equal to 1 (think about why this must be), and that the density must be
nonnegative. Another useful interpretation may be to think of PDF values at certain points as relative
likelihoods; that is, if fX (s) = 2fX (t), then we are twice as likely to see values in a small δ neighborhood
around s than values in a small δ neighborhood around t (if the density is continuous).

1
Example 5.8. let fX (x) = √
2 x
for 0 < x < 1 and take on the value 0 otherwise. Then we have that
it is nonnegative, and that Z 1
fX (x)dx = 1
0
So this is a valid PDF.

Now we mention the cumulative distribution function, which completely analogously to the discrete
case is simply Pr(X < x). Since the CDF would be
Z x
F (x) = fX (t)dt
−∞

The CDF has the following properties:

1. FX (∞) = 1
2. FX (−∞) = 0

3. if X is discrete, then
Pr(X = k) = FX (k) − FX (k − 1)
and in the continuous case:
d
fX (x) = FX (x)
dx
Where the last fact follows from the fundamental theorem of calculus (if F is differentiable). This can
be a very useful fact, as often the CDF is easier to calculate than the PDF.

21
 Example 5.9. Imagine throwing darts at a unit circle. We model this by saying that the location of
where the dart lands in the circle is completely random (i.e. uniform over the circle). We would like
to find the CDF and PDF of Y , which is the distance from the origin of where the dart lands. We
have that
area of circle of radius y
Pr(Y ≤ y) =
area of whole circle
πy 2
= = y2
π
. Then we have that simply
d
fY (y) = FY (y) = 2y
dy
We can calculate that:

P (0.5 < Y < 0.6) = FY (0.6) − FY (0.5) = 0.36 − 0.25 = 0.11

We have some analogous definitions and lemmas that pretty much follow from the discrete case:

Definition 5.10. The expectation of a continuous RV X is

Z ∞
xfX (x)dx
−∞

Lemma 5.11. Z ∞
E[g(X)] = g(x)fX (x)dx
−∞

Lemma 5.12. if X, Y are independent, then

FX,Y (x, y) = FX (x)FY (y)

Now we go over some popular continuous RVs.

Definition 5.13 (Uniform RV). If X ∼ U nif [a, b], then it must have constant probability density
between a and b and zero density everywhere else, which tells us that
1
fX (x) =
b−a
for x ∈ [a, b].

We can calculate for X ∼ U [a, b] that:

Z b
1 a+b
E[X] = x dx =
a b−a 2

and also
(b − a)2
Var(X) = E[X 2 ] − E[X]2 =
12

22
Exercise 5.14. verify the Variance of a uniform RV between a and b is actually what we claimed
above.

Definition 5.15 (Exponential RV). Let’s say we wanted to find a continuous RV that had the same
”memoryless” property as the discrete Geometric RV, and analogously measured ”time to success”
(or failure, however you want to look at it). But now this time, time is a continuous thing, say the
amount of time before a lightbulb burns out. Specifically, for the memoryless property, we want
Pr(X > t + s|X > s) = Pr(X > t). That is, we want

Pr(X > t + s ∩ X > s) Pr(X > t + s)

= = Pr(X > t)
Pr(X > s) Pr(X > s)

The question then becomes, what function g(t) = Pr(X > t) satisfies g(s+t)
g(s) = g(t)? Well, eventually,
we might notice that g(x) = ex works! The problem is, this increases g(x) as x increases, which
is not the behavior we want if we are to keep the analogy. Well, g(x) = e−x also works, and it is
monotonically decreasing, so that is better! In fact, we can even throw in a constant g(x) = e−λx ,
for increased versatility, and it still is monotonically decreasing and memoryless. Then we have

FX (x) = 1 − Pr(X > x) = 1 − e−λx

d
=⇒ FX (x) = fX (x) = λe−λx
dx
for any λ > 0. We can further check that this integrates to 1 over its domain (since it is measuring
time to success, this is a positive random variable):
Z ∞ Z ∞
fX (x) = λ e−λx = 1
0 0

as desired. And with that I conclude the most long winded introduction to the exponential random
variable that has ever been.

Exercise 5.16. Show that if X ∼ Exp(λ), then

1
E[X] =
λ
1
Var(X) =
λ2

Definition 5.17 (Laplace Distribution). Let Z = X − Y , where X, Y ∼ exp(λ), and X and Y are
independent. Then how is Z distributed? Well, if X > Y , then by the memoryless property we have
that Z is simply an exponential RV. This happens with probability 1/2, so we have fZ (z) = 21 λe−λz .
What if then Y > X? Then once again by the memoryless property, we get that Z is simply a negated
exponential RV: fZ (z) = 12 λe+λz . So putting this together we have what is known as the Laplace
Distribution:
1
fZ (z) = λe−λ|z|
2

23
6 Lecture 6: Normal Distribution, Continuous Analogs, Derived Dis-
tributions
Agenda: see above

6.1 Review

Exercise 6.1. Let R be the distance from the origin of a point randomly sampled on a unit ball (in
R3 ).
1. what is the CDF of R?
2. PDF?

3. Expectation?

6.2 Normal Distribution

Definition 6.2 (Normal Distribution). Let X ∼ N (µ, σ 2 ), where µ is the mean of the distribution and
σ is the standard deviation. Here is the PDF:
1 −(x−µ)2
fX (x) = √ e 2σ 2
2πσ 2
We call the pdf of X ∼ N (0, 1) is FX (x) = Φ(x), which cannot be expressed in elementary functions

The PDF of the normal is clearly positive. We would like to also show that it integrates to 1:
Proof. We will show this when µ = 0 and σ 2 = 1. The idea is to show that
Z ∞ 2
fX (x)dx =1
−∞

We have that:
Z ∞ 2 Z ∞  Z ∞ 
fX (x)dx = fX (x)dx fY (y)dy
−∞ −∞ −∞
Z ∞Z ∞
= fX (x)fY (y)dxdy
−∞ −∞
Z ∞Z ∞
1 −(x2 +y2 )/2
= e dxdy
−∞ −∞ 2π
Z 2π Z ∞
1 −(r2 )/2
= e rdrdθ (using polar integration, where dydx = rdrdθ)
0 −∞ 2π
Z ∞
2
= e−(r )/2 rdr.
−∞

We can use u substitution to solve this integral, which will evaluate to 1 (think about the pdf of the
exponential RV! Or just do it manually).

Some properties of Normal distributions:

2
1. if X, Y are independent normals, then Z = X + Y is also normal Z ∼ N (µX + µY , σX + σY2 ).

24
 2. The sum of two dependent normals isn’t always Normal. Consider X ∼ N (0, 1), and Y = X w.p. 1/2
and −X wp 1/2. Then both X and Y are normal but X + Y is not normal.
3. We have that if X ∼ N (µ, σ 2 ), then
X −µ
∼ N (0, 1)
σ

Example 6.3. Let X ∼ N (2, 16). We wish to find Pr(−2 < X < 6). We have

X −2
Pr(−2 < X < 6) = Pr(−4 < X − 2 < 4) = Pr(−1 < < 1)
4
= Pr(−1 < N (0, 1) < 1) = Φ(1) − Φ(−1) = 2Φ(1) − 1 ≈ 0.68
Where Φ is the CDF of the standard normal distribution.

Exercise 6.4. convince yourself that Φ(1) − Φ(−1) = 2Φ(1) − 1 if you haven’t already.

Example 6.5. Suppose male height is distributed as N (70, 5) and female height is N (64, 4). What’s
the probability that a random chosen male is taller than a randomly chosen female? Express your
answer in terms of Φ.

Ans: Let X be the boys height and Y the girls height. We want to calculate
P (X − Y > 0) = P (Y − X < 0). Note that Y − X ∼ N (−6, 9), and so

Y −X +6
√ ∼ N (0, 1)
9
So we have
Y −X +6
P (Y − X < 0) = P ( < 2) = Φ(2)
3

6.3 Continuous Analogs of Discrete RVs

For joint distributions, we can generalize from the discrete case:
X
P (A) = PX,Y (x, y)
(x,y)∈A

and analogously: Z
P (A) = fX,Y (x, y)dxdy
A
The definitions of marginal probabilities, conditional probabilities, multiplication rule, and Bayes Rule
all carry over naturally into the domain of continuous probability, all you need to do is replace summations
with integrals and pX ’s with fX ’s.

Example 6.6. We can have discrete and continuous RVs defined jointly. For example. For example,
let X be the outcome of a die roll, and Y ∼ Exp(X). Then we have
1
pX (x) =
6
and
fY |X (y|x) = xe−xy

25
 Example 6.7. Let X ∼ Bern(1/2) and Y = 2X. We have that the distribution of Y is
y
Pr(Y = y) = Pr(2X = y) = Pr(X = )
2
more generally, if X is discrete RV, and Y = f (X), then

Pr(Y = y) = Pr(f (X) = y) = Pr(X ∈ f −1 (y))

Be careful! Is it then true that in the continuous case if X ∼ U [0, 1] and Y = 2X. Is it then true that
y
fY (y) = Pr(Y = y) = Pr(2X = y) = Pr(X = y/2) = fX
2
NO. There are many things wrong here, first of all the quantity Pr(Y = y) = 0, ∀y. Second, this does not
integrate to 1: Z 2 Z 2
fY (y)dy = fX (y/2)dy = 2
0 0
Instead, we have to derive the CDF of Y properly using the CDF. It IS true that:
y y
FY (y) = Pr(Y ≤ y) = Pr(2X ≤ y) = Pr(X ≤ ) = FX (
2 2
and then
d 1 y
fY (y) = FX (y/2) = fX ( )
dy 2 2
Which we can check does integrate to 1.

Example 6.8 (More on the relationship between Exponential and Geometric RVs). Toss a coin every
δ seconds, and let the probability of heads p = 1 − e−λδ , with δ << 1. Let N ∼ Geom(p) and
X ∼ exp(λ). Then we have that FN (n) = Pr(N < n) = 1 − e−λnδ = FX (nδ). If you graph FN (n)
and FX (nδ), then you can see how the exponential is the limit of the geometric as δ → 0.

It is useful to know that the Covariance is a multilinear function, meaning

Cov(X + Y, W + Z) = Cov(X, W ) + Cov(X, Z) + Cov(Y, W ) + Cov(Y, Z)

And it is also useful to note that the variance Var(X) = Cov(X, X). We also have that Cov(aX + b, Y ) =
a Cov(X, Y ). This yields the following useful identity:
X  X XX
Var Xi = Var(Xi ) + Cov(Xi , Xj )
i i j6=i

The Tower Rule or Iterated Expectation or the Law of Total Expectation also holds in the
continuous case. We have:
Z Z
E[E[X|Y ]] = fY (y) xfX|Y (x|y)dxdy
Y X
ZY Z X
Z Z
= xfX|Y (x|y)fY (y)dxdy = xfX,Y (x, y)dydx
ZY X X Y

= xfX (x)dx = E[X].

X

The above result should make intuitive sense when you think about it, and the intuition is quite similar
to the intuition behind discrete total probability. If we want to find E[X], and the instances of Y subdivide
our probability space, it may be easier to calculate E[X|Y ] for every Y . But then we have to weight each
expectation the probability that particular instance of Y happens, hence the outside expectation over the Y
variable.

26
Example 6.9. Consider trying to estimate X given some information Y with the estimate E[X|Y ].
Well we have that the error E is E = X − E[X|Y ], and we further have that

E[E] = E[X] − E[E[X|Y ]] = E[X] − E[X] = 0

and therefore E[X|Y ] is called an unbiased estimator. We will learn more about this later in the
semester though when we talk about MMSE.

27
7 Lecture 7: Order Statistics, Convolution, Moment Generating Func-
tions
Agenda:
1. Law of Total Variance
2. Order Statistics
3. Convolution
4. Moment Generating Functions

7.1 Conditional Variance and Law of Total Variance

Definition 7.1 (Conditional Variance). Let X, Y be RVs. We can define the conditional variance
Var(X|Y = y) as the variance of the conditional distribution P (X = x|Y = y).

Remark 7.2. Var(X|Y ) is a RV that assumes the value Var(X|Y = y) with probability Pr(Y = y).

Lemma 7.3 (Total Variance). We have that

Var(X) = E[Var(X|Y )] + Var(E[X|Y ])

I will now try to offer some sort of intuition before the formal proof. We want to answer the question:
how much does X vary? Well, if we fix Y , we could take the expectation over all the y ∈ Y of Var(X|Y ).
But even if we are fixing Y , there is still some variance in X, and therefore some variance in E[X|Y ], which
is where the second term comes into play. The first term is the expected variance from the mean of X|Y ;
the second is the variance of that mean.
Proof. We have that

Var(X) = E[X 2 ] + E[X]2

= E[E[X 2 |Y ]] − (E[E[X|Y ]])2
= E[Var(X|Y ) + E[X|Y ]2 ] − (E[E[X|Y ]])2
= E[Var(X|Y )] + E[E[X|Y ]2 ] − (E[E[X|Y ]])2

= E[Var(X|Y )] + Var(E[X|Y ]).

Example 7.4. We have a biased coin, we toss is n times, and we let X be the number of heads, and
Y ∼ U [0, 1] be the probability of heads (the bias of the coin). First, we have that
n
E[X] = E[E[X|Y ]] = E[nY ] = n E[Y ] =
2
Now, we can calculate the variance:

Var(X) = Var(E[X|Y ]) + E[Var(X|Y )]

= Var(nY ) + E[nY (1 − Y )]
= n2 Var(Y ) + n E[Y ] − n E[Y 2 ]
n2 n n n2 n
= + − = + .
12 2 3 12 6

28
 n
Compare this value to tossing a fair coin n times, which has variance 4.

Example 7.5 (Random number of Random Variables). Say we have Y = X1 + ... + XN , where the Xi
are all independent and N is also random. What is Var(Y )? First, we have:

E[Y ] = E[E[Y |N ]] = E[N E[Xi ]] = E[N ] E[Xi ]

Where the second to last equality follows from linearity of expectations. Also, since N is given in the
inner expectation, we can treat it as a constant (until the outer expectation). We then have:

Var(Y ) = E[Var(Y |N )] + Var(E[Y |N ])

= E[N Var(Xi )] + Var(N E[Xi ])
= E[N ] Var(Xi ) + E[Xi ]2 Var(N ).

7.2 Order Statistics

Let X be a continuous RV for which x1 , x2 , ..., xn are values of a random sample of size n. We can then
reorder the xi ’s from smallest to largest (we don’t need to worry about ties, as we are in a continuous sample
space here!).

Example 7.6. Suppose X ∼ U [0, 1], and n = 4, and we observe x1 = 0.5, x2 = 0.7, x3 = 0.2, x4 = 0.1.
Then we can order them as

x(1) = 0.1, x(2) = 0.2, x(3) = 0.5, x(4) = 0.7

where x(i) i the ith smallest observation

We call X (i) = x(i) the ith order statistic.

Theorem 7.7. If X has pdf fX (x), the marginal pdf of the ith order statistic is

n!
fX (i) (y) = (FX (y))i−1 (1 − FX (y))n−i fX (y)
(i − 1)!(n − i)!

Proof. We present a sketch of the proof. We would like to calculate

Pr(X (i) ∈ {y, y + dy}) ≈ fX (i) (y)dy
We need i − 1 of the samples to be less than y, which is the (FX (y))i−1 term. We also need exactly one to
be right around y, which is approximately fX (y)dy. Finally, we need (n − i) of the samples to be greater
than y, which is the (1 − FX (y))n−i term. Lastly, we have to count how many ways we can pick with ones
come first

and which one is the the ith largest (which exactly determines which ones come after y), which is
n n!
n ∗ i−1 = (i−1)!(n−i)! . Combining all of these together yields the exact expression we were looking for!

Example 7.8 (Special case when X is uniform). Suppose X ∼ U [0, 1]. Recall that fX (x) = 1, and
FX (x) = x (convince yourself if you’ve forgotten why this is true!). Then we can plug in and see that
n!
fX (i) (y) = y i−1 (1 − y)n−i
(i − 1)!(n − i)!
for 0 < y < 1. This is a special case of a Beta Distribution.

29
 Exercise 7.9. What is the probability that the 9th smallest of of ten draws from X ∼ U [0, 1] is greater
than 0.8?

7.3 Convolution
Let Z = X + Y , where X and Y are both continuous and independent. We would like to calculate the PDF
of Z. We can relate Z to X using total probability:
Z
fZ (z) = fX,Z (x, z)
x

Furthermore, we have

FZ|X = Pr(X + Y ≤ z|X = x) = Pr(Y ≤ z − x|X = x) == Pr(Y ≤ z − x) = FY (z − x)

=⇒ fZ|X (z|x) = fY (z − x)
Now, incorporating this into our original expression for fZ (z), we have
Z
fZ (z) = fX (x)fY (z − x)dx = (fX ∗ fY )(z)
x

which is called a convolution. Intuitively, the expression should make sense, as we are just integrating over
all possible combinations of X and Y that could sum to z. The discrete case is entirely analogous:
X
Pr(Z = z) = Pr(X = k) Pr(Y = n − k)
k

Example 7.10. Suppose X, Y ∼ U [0, 1] are independent. What is fZ (z), where Z = X + Y ? We

could do an integral and get the right answer via the definition of the convolution, but we can also
visually see that it becomes a triangle:

TODO 1. tikz :(

As a general remark, convolution always creates more uncertainty than we started out with. In your
homework you will show that if X, Y ∼ N (0, 1) are independent, then Z = X + Y ∼ N (0, 2).

7.4 Moment Generating Functions (MGFs)

Definition 7.11 (Moment Generating Functions). We define the Moment Generating Function of
an RV X as
MX (s) = E[esX ]

Whats the point of MGFs? It seems like a fairly arbitrary definition. Well, first recall the Taylor series
for e:
(sX)2 (sX)3
esX = 1 + sX + + + ...
2! 3!
s2 s3
=⇒ E[esX ] = 1 + s E[X] + E[X 2 ] + E[X 3 ] + ...
2! 3!
Then, we can observe that
d
E[esX ] = E[X]
ds s=0

30
and
d2
E[esX ] = E[X 2 ]
ds2 s=0
continuing in this manner, we can see that

dn
MX (s) = E[X n ]
dsn s=0

Which is an extremely useful property of the MGF and can help with many computations. We also note
that MX (0) = 1 must be true.

31
8 Lecture 8: MGFs, Bounds/Concentration Inequalities (Markov, Cheby-
shev, Chernoff)
Agenda:

1. MGF’s (examples and properties)

2. Limit theorems (Markov, Chebyshev, Chernoff)

8.1 Properties of MGFs

Recall that the Moment Generating Function (MGF) of an RV X is the transform:
∞ ∞
sk E[X k ]
X Z
MX (s) = E[esX ] = = esx fX (x)dx
k! −∞
k=0

and that
dn
MX (s) = E[X n ]
dsn s=0
Some utilities of the MGF:

1. Finding higher moments often becomes easier (derivatives are usually easier than integrals!)
2. Convolution becomes multiplication in the MGF domain, which is often much easier (again, avoiding
integrals)
3. Great analytical tool to prove things (such as the CLT!)

And here are some properties to keep in mind:

1. MX (0) = 1
2. if X > 0, then MX (−∞) = 0
3. if X < 0, then MX (∞) = 0

4. if Y = aX + b, we have

MY (s) = E[es(aX+b) ] = esb E[easX ] = esb MX (as)

Example 8.1 (MGF of exponential RV). Let X ∼ Exp(λ). Then we have that:

Z ∞
sX
MX (s) = E[e ] = esX λe−λx dx
0
Z ∞
=λ ex(s−λ) dx
0
∞
ex(s−λ)
=λ
s−λ 0
λ
= . (assuming λ > s)
λ−s
It is fine here that the MGF is not defined for all s, as we only need for it to be defined around s = 0
so that we can take derivatives evaluated at s = 0.

32
 We can use the MGF of an exponential to easily calculate moments:

0 y 1
E[X] = MX (0) = =
(y − s)2 s=0 λ

and we note that

dk λk! k!
E[X k ] = MX (s) = =
dsk s=0 (λ − s)k+1 s=0 λk

Example 8.2 (MGF of a Poisson). We have that for X ∼ P ois(λ) that

∞
X
MX (s) = esk Pr(X = k)
k=0
∞
X e−λ λk
= esk
k!
k=0
∞
X (es λ)k
= e−λ
k!
k=0
−λ es λ s
=e e = e−λ+λe ,

which is valid for all values of s.

Example 8.3 (MGF of Normal RV). Let X ∼ N (0, 1). Then we have
Z ∞
1 2
sX
E[e ] = √ esx e−x /2 dx
2π −∞
Z ∞
1 2
=√ esx−x /2 dx
2π −∞
s2 /2 Z ∞
e 2 2
= √ e−(x /2−sx+s /2) (complete the square in the exponent)
2π −∞
Z ∞
2 1 2
= es /2 √ e−(x−s) /2
2π −∞
2
= es /2
.
2
In the last line we have used that fact that √12π e−(x−s) /2
is the PDF of a standard normal that
has been shifted by s, and so must integrate to 1.

Now, if Y ∼ N (µ, σ 2 ), then Y = σX + µ and we have

2 2
E[esY ] = E[es(σX+µ) ] = eµs E[eσY s ] = eµs+σ s /2
.

Remark 8.4. An interesting and useful fact (that we will not prove in this course) is that a given
MGF corresponds to a unique CDF. This is related to the fact that MX (s) is just a Laplace transform
of fX (x). Inversions are usually performed by just pattern matching.

Remark 8.5 (Convolving densities corresponds to multiplying their transforms). Take Z = X + Y , and

33
 assume X and Y are independent. Then we have that

MZ (s) = E[esZ ] = E[es(X+Y ) ] = E[esX ] E[esY ] = MX (s)MY (s)

Example 8.6 (MGF of binomial). We can use the above remark very nicely in computing the MGF
of a binomial RV, because we can use the fact that a binomial is simply the sum of bernoullis. We
have X ∼ Bin(n, p) = Y1 + ... + Yn , where Yi ∼ Ber(p). We have then

MYi (s) = E[eYi s ] = (1 − p)es·0 + pes = 1 − p + pes

=⇒ MX (s) = (1 − p + pes )n

Example 8.7 (Summing of a random number of random variables). Let Y = X1 + · · · + XN , where

X1 , . . . , XN are i.i.d. and N is a RV. We then have that

MY (s) = E[eY s ] = E[E[eY s |N ]]

= E[E[es(X1 +···+XN ) |N ]] = E[MX (s)N ]
= E[eN ln(MX (s)) ]
= MN (ln MX (s)).

Example 8.8 (Sum of Geometric number of exponential RVs). We will begin with the fact that if
N ∼ Geom(p), then
pes
MN (s) =
1 − (1 − p)es
Then, if Y = X1 +· · ·+XN , where each Xi is an iid exponential RV. Then, from the previous example,
λ
we have that MY (s) = MN (ln(MX (s))) We also have from before that MXi (s) = λ−s . Then, we
have
λ
pMXi (s) p λ−s
MY (s) = = λ
.
1 − (1 − p)MXi (s) 1 − (1 − p) λ−s

8.2 Limiting Behavior of RV’s

Suppose we observe a sequence X1 , X2 , ..., Xn i.i.d. samples. We let
P
Xi
Mn =
n
be the sample mean (which makes sense, as it is just an average). We have:
n E[Xi ]
1. E[Mn ] = n =µ

2. Assuming Var(Xi ) < ∞, we have

1 X Var(Xi )
Var(Mn ) = Var(Xi ) = =⇒ 0
n2 n
as n =⇒ ∞
A natural question is then: What happens to the “deviation” |Mn − E[Mn ]| = |Mn − µ|?

34
 Definition 8.9 (Markov Bound). For a non-negative random variable, we have that

aP (X ≥ a) ≤ E[X]

(
1 X≥a
Proof. Define the indicator variable Z = . Then we can see that aZ ≤ X by examining the
0 otherwise
two cases.

• If X < a then Z = 0, so the condition is 0 ≤ X, which is true because we are considering X non-
negative.
• If X ≥ a then Z = 1, so the condition is a ≤ X, which is true by the condition with which we started
this case.

Thus, we can take expectation on both sides:

E[aZ] ≤ E[X]
a E[Z] ≤ E[X]
aP(X ≥ a) ≤ E[X].

Example 8.10. Let X ∼ U [0, 1]. Then we have

1/2
Pr(X > 3/4) ≤ = 2/3
3/4

and
1
Pr(X > 1) ≤
2
Which seems pretty stupid/not very powerful. But it is this way because it makes very little assump-
tions on the RV. We don’t hate on Markov too much because it is actually the building block for
many other bounds, and is often very useful when we don’t know much or anything about the higher
moments of our RV.

Remark 8.11 (Markov Inequality intuition). Say my distribution has a mean of µ, and I want to
maximize the probability that Pr(X ≥ kµ). How would I do this? I would do this by letting X take
on a value of kµ with probability k1 , and X = 0 otherwise. This achieves the correct expectation
while still maximizing Pr(X ≥ kµ).

Definition 8.12 (Chebyshev’s Inequality). Chebyshev’s Inequality states

Var(X)
Pr(|X − µ| ≥ a) ≤ ,
a2
where µ = E[X].

Proof. We know that Var(X) = E[(X − µ)2 ]. We then have that

Var(X)
Pr((X − µ)2 ≥ a) ≤
a

35
by Markov’s inequality. This implies
√ Var(X)
=⇒ Pr(|X − µ| ≥ a) ≤
a
Var(X)
=⇒ Pr(|X − µ| ≥ a) ≤ .
a2

Note that Chebyshev’s inequality holds for any random variable, not just positive ones (in contrast to
Markov’s inequality. We also note the special case:
1
Pr(|X − µ| ≥ kσ) ≤
k2
when X has mean µ and variance σ 2 .

Remark 8.13 (Weak Law of Large Numbers). We can use Chebyshev’s inequality to show a result
known as the Weak Law of Large Numbers. Suppose we have an average of a bunch of i.i.d. RVs
Mn = X1 +···+X
n
n
. Then we have that Var(Mn ) = n Var(X
n2
i)
= Var(X
n
i)
. This implies via Chebyshev’s
inequality that:
σ
P r(|Mn − E[Xi ]| ≥ a) ≤
na2

Definition 8.14 (Chernoff Bound). Suppose we know the MGF of our random variable MX (s) =
E[esX ]. Note that this is a positive RV, so we can apply markov’s inequality:

E[esX ] MX (s)
Pr(esX ≥ a) ≤ =
a a
E[esX ]
=⇒ Pr(esX ≥ eas ) ≤
eas

E[esX ]
=⇒ Pr(sX ≥ as) ≤
eas
x
where the last step follows since f (x) = e is monotonic. Then, if s > 0 we have

E[esX ]
=⇒ Pr(X ≥ a) ≤
eas
alternatively, if s < 0 we have
E[esX ]
=⇒ Pr(X ≤ a) ≤
eas

Note that the Chernoff bound is a function of s. We often have to choose the optimal choice for s to get
a good bound (take derivative and set to zero!). Also if we recall the Taylor series for ex , the idea behind
a Chernoff bound is that it can use all the moments of a RV to bound said RV. Compare this to Markov’s,
which only uses the first moment, and Chebyshev’s, which only uses the second moment. This might lead
one to think that Chernoff is always better than applying Markov/Chebyshev bounds, or even applying
Markov’s bound to higher moments of the random variable. This leads to the following remark:

Remark 8.15 (Is Chernoff always better than Markov/Chebyshev?). In short, no. Consider using
Markov’s inequality to bound a higher moment of our RV X. This yields (provided the higher

36
 E[X k ]
moment is positive of course) Pr(X ≥ a) ≤ ak
. Here I claim:

E[X k ] E[esX ]
inf k
≤ inf
k>0 a s>0 eas
Why is this true? Lets examine the RHS:

E[esX ] 1 X sk E[X k ]
=
eas eas k!
k
X (as)k e−as  E[X k ]

= .
k! ak
k

Now, the above expression is simply averaging over the moment bounds where you let the moment
be distributed as a Poisson random variable with parameter as, and in general, the minimum over
the moment bounds will be smaller than the average (no matter how the averaging is done, and so
minimizing over s doesn’t change anything), and thus we get the result.

37
9 Lecture 9: Convergence, Weak and Strong Law of Large Numbers,
Central Limit Theorem
Agenda:
1. Recap of Limit Theorems (Chernoff)
2. Laws of Large Numbers (WLLN, convergence in probability)
3. Central Limit Theorem

9.1 Recap of Bounds

Example 9.1. Let X ∼ N (0, 1). We can bound the tail probabilities of X using the chernoff bound:

E[esX ]
Pr(X ≥ k) ≤
esk
Recalling the MGF of a normal distribution, we have:
2
es /2 2
= sk = es /2−sk
e
Minimizing this expression over s > 0 corresponds to minimizing the exponent. Taking the derivative,
we see
−k + s∗ = 0 ⇒ s∗ = k
Plugging this optimal value s∗ in, we get:
2
Pr(X ≥ k) ≤ e−k /2

Which is actually exponential decreasing, which is much closer to the true behavior of the normal
distribution.

Exercise 9.2. Extend the above exercise to show that for X ∼ N (0, 1), we have
2
Pr(|X| ≥ k) ≤ 2e−k /2

Definition 9.3 ((Weak) Law of Large Numbers (WLLN)). If we perform an experiment n times inde-
pendently and
n
1X
Mn = Xi
n i=1

• If Xi has mean µ and variance σ 2

Pn
• E[Mn ] = E[ n1 i=1 Xi ] = n1 E[Xi ]n = µ
•
1 X σ2
Var(Mn ) = 2
Var(Xi ) =
n n
This tells us that if X1 , ...., Xn are i.i.d. RV’s with mean µ and finite variance, then for every  > 0,
we have
Pr(|Mn − µ| ≥ ) → 0
as n → ∞

38
Proof. The proof of the last claim is quite simple and only uses Chebyshev’s inequality. It tells us at what
”rate” this probability goes to zero as n → ∞. We have
σ2
Pr(|Mn − µ| ≥ ) ≤ →0 as n → ∞
2 n

What does the WLLN tell us? It tells us that

lim Pr(|Mn − µ| ≥ ) = 0
n→∞

Remark 9.4. Similar to the definition of the limit. For any  > 0, δ > 0, there exists some n0 (, δ)
such that
Pr(|Mn − µ| ≥ ) ≤ δ)
for all n > n0 (, δ). We say then that Mn converges in probability to µ.

Example 9.5. Let Yn = min(X1 , ..., Xn ) for Xi ∼ U [0, 1]. We have that

Pr(|Yn − 0| ≥ ) = Pr(|X1 | > , |X2 | ≥ , ..., |Xn > ) = (1 − )n

Which goes to zero for all  > 0 as n → ∞. This tells us that Yn converges in probability to 0.

Example 9.6. Suppose we have an arrival process where we divide the number line into exponentially
increasing sized intervals:
Ik = {2k , 2k + 1, ..., 2k+1 − 1}
And suppose we have exactly one arrival in each interval. So we let Yn = 1 if there is an arrival at
time n, and Yn = 0 if there is no arrivals. We then have that

Pr(Y1 = 1) = 1

Pr(Y2 = 1) = Pr(Y3 = 1) = 1/2

1
Pr(Yn = 1) = if n ∈ Ik
2k
This implies that
1
lim Pr(|Yn − 0| ≥ ) = lim Pr(Yn = 1) = lim =0
n→∞ n→∞ k→∞ 2k
Which tells us that Yn converges in probability to 0.

The above highlights the weakness of convergence of probability. We can see of course that for any
finite n, there are certainly an infinite number of 1’s (arrivals) after n, yet it still converges in probability.
This is fixed by something known as almost sure convergence, which we will not get deep into in this course.
Pn
Question: What happens to Sn = i=1 Xi . This is just a bunch of convolutions! In particular, if each
Xi ∼ U [0, 1], we know that convolving two uniform pdfs looks like a triangle pdf. Convolving yet again
gives us a quadratic polynomial. Each time we convolve the width gets higher (the variance blows up) and
the order of the polynomial becomes larger. This general phenomenon happens for non-uniform iid RVs
(amazingly) as well!

Our problem is that the mean and variance of Sn both blow up as n → ∞. To fix this, we define

cn = Sn√− nµ
S
nσ

39
which we can verify has zero mean and unit variance.

Theorem 9.7 (Central Limit Theorem). The CLT says that

cn ≤ x) = Φ(x)
lim Pr(S

where Φ(x) is the CDF of the standard normal distribution! This type of convergence is known as
convergence in distribution.

Proof. We present a sketch of the proof. Note that Sn → N (0, 1) implies that Sn → N (nµ, nσ 2 ).

Exercise 9.8. See Sinho’s notes on modes of convergence (I will hopefully type up my own sometime
soon, but these are very good)

Remark 9.9 (SLLN vs WLLN). The WLLN, as we already discussed, says that
σ
Pr(|Mn − E[Xi ]| ≥ a) ≤
na2
Which tells us that
lim Pr(|Mn − E[Xi ]| ≥ a) = 0
n→∞

The Strong Law of Large Numbers, on the other hand, says something stronger. It says that:

Pr( lim Mn = µ) = 1
n→∞

On the surface, these look similar. But the key difference is that for some  > 0, the SLLN says
that |Mn − µ| >  will only happen a finite number of times (in other words, there exists some N
such that n > N ⇒ |Mn − µ| < ). On the other hand, the WLLN makes no such guarantee. More
specifically, the WLLN says that Mn converges in probability, while the SLLN says Mn converges
almost surely or with probability one. For more details on the difference between these two things,
you should refer to Sinho’s notes or the course notes.

40
10 Lecture 10: Information Theory
Agenda:

1. Recap of WLLN
2. Proof of CLT
3. Introduction to Information Theory (Entropy, Compression)

10.1 Proof of CLT

Recall the CLT:

Theorem 10.1 (Central Limit Theorem). The CLT says that

cn ≤ x) = Φ(x)
lim Pr(S

where Φ(x) is the CDF of the standard normal distribution! This type of convergence is known as
convergence in distribution.

where we had defined S

cn as
cn = Sn√− nµ
S
nσ
Proof. Let Pn
Xi
Zn = i=1
√
n
where each Xi is iid and E[Xi ] = 0 and Var(Xi ) = 0. We also note that if Y ∼ N (0, 1), then MY (s) =
2
es /2 and furthermore log MY (s) = s2 /2. So it suffices to show that the log of the MGF of Zn is s2 /2. We
have
n
s X
MZn (s) = E[esZn ] = E[exp( √ Xi )]
n i=1
s s
= E[exp( √ X1 ) · · · exp( √ Xn )]
n n
s s
= E[exp( √ X1 )] · · · E[exp( √ Xn )]
n n
 n
s
= MX ( √ )
n
0 00
Now, recall that MX (0) = 1, and MX (0) = 0, and MX (0) = 1, by our assumptions and the properties of
the MGF. Now we consider:
log MX ( √sn )
  " #
s
lim log MZn (s) = lim n log MX ( √ ) = lim 1
n→∞ n→∞ n n→∞
n

Now, letting y = √1
n  
log MX (sy)
= lim
y→0 y2
Now notice that the limit of both the numerator and the denominator is zero, so we can use L’Hopital’s rule!
0
 
sMX (sy)
= lim
y→0 2yMX (sy)

The numerator and denominator once again both go to zero. L’Hopital again!

41
 00
s2 MX s2
 
(sy)
= lim =
y→0 2MX (sy) + 2ysM 0 (sy) 2
X

Example 10.2 (Polling Example). Suppose we ask n randomly sampled voters if they support candidate
X. So Xi = 1 if yes, and zero otherwise. Suppose we want a 95% confidence interval that |M
Pn −p| < ,
where p is the true probability that each voter supports our candidate, and Mn = n1 Xi is the
empirical mean. Well, Chebyshev tells us that

Var(Mn )
Pr(|Mn − p| ≥ a) ≤
a2
But now we note that Var(Xi ) = p(1−p) ≤ 1/4, which tells us that Var(Mn ) = n1 Var(Xi ) ≤ 4n
1
.
Now, suppose we want to know our p value to within 0.1 with probability at least 95%. Mathemati-
cally, we want:
Pr(|Mn − p| ≥ 0.1) ≤ 0.05
and we know

Var(Mn ) 1
Pr(|Mn − p| ≥ 0.1) ≤ ≤
0.12 4n(0.01)
Which implies that in order for us to obtain a 95% confidence interval, we need to set n ≥ 500. If
a = 0.01, then we would need n ≥ 50000 for a 95% confidence interval!

Now, let’s compare this with the CLT method. The CLT tells us that

Mn − E[Mn ]
p → N (0, 1)
Var(Mn )

and we want
Pr(|Mn − p| ≥ 0.1) ≤ 0.05
|Mn − p| 0.1
⇐⇒ Pr( 1 ≥ √ ) ≤ 0.05
√
2 n
1/(2 n)

But notice that the left hand side is roughly a standard normal. To get a 95% confidence interval
for a normal distribution, we use the fact that we know 95% of the probability mass lies within 2
standard deviations, and in this case a standard deviation is 1. So we have
√
0.2 n ≥ 2 ⇒ n ≥ 100

Which we can see is much better than the result Chebyshev gives us.

10.2 Intro to Info Theory

The field of information theory was pioneered by Claude Shannon in his seminal 1948 paper ”A Mathemati-
cal Theory of Communication”. There is a great textbook on the topic ”Elements of Information” by Cover
and Thomas, which is a highly recommended resource. Also, if you are interested in this topic further, you
should take EECS 229A!

Shannon was concerned with the question, how much information can I reliably send over a noisy chan-
nel?

42
 Info Source transmitter noise

message signal
ok ok

ok

noise source

TODO 2. fix this diagram

There are two things we can concern ourselves with.

1. How much can we compress our information in the presence of no noise? This is known as the Source
Coding problem.
2. How much information can we send in the presence of noise? This is known as the Channel Coding
Problem
Shannon was able to answer both of these questions, and he was also even able to say that we can
separately optimize for both of these criterion and arrive at a globally optimal solution!

43
11 Lecture 11: Info Theory, Binary Erasure Channel
Agenda:
1. Information theory overview (Entropy, AEP, Capacity of BEC)
Recall that there were two fundamental questions Shannon was exploring:
1. How much can we compress our information in the presence of no noise? This is known as the Source
Coding problem.
2. How much information can we send in the presence of noise? This is known as the Channel Coding
problem.

Theorem 11.1 (Source Coding Theorem). Given N i.i.d. RV’s X1 , ..., Xn , each having entropy H(X),
then these can be compressed with a source coding channel into no more than N (H(X)+) bits, ∀ > 0
as N → ∞.
Conversely, we also have that compression to fewer than N H(X) bits is impossible without loss of
information.

Definition 11.2 (Entropy). The entropy of a discrete RV X is defined as

X 1
H(X) := PX (x) log
PX (x)
x∈X
1
= E[log ].
PX (x)

We can interpret this definition very roughly by noting that the quantity log PX1(x) roughly corresponds
to the “surprise” of seeing the outcome x. Then the entropy corresponds to the “average surprise” of our
distribution. Another interpretation of entropy is that is correlated to the uncertainty of the random variable.

Example 11.3. When X ∼ Bern(p), then

1 1
H(X) = p log + (1 − p) log =: H(p)
p 1−p
We can graph this quantity as p varies from 0 to 1. Note that at 0 and 1, the quantity is 0, and at
p = 1/2, the quantity is 1. We also can calculate that H(0.11) = 1/2. This tells us that if we have a
really long sequence of Bern(0.11) RV’s, then roughly half of the bits are “redundant”, i.e. they can
be compressed.

We further can naturally define

44
 1. X 1
H(X, Y ) = PX,Y (x, y) log
x,y
PX,Y (x, y)

Exercise 11.4. Show that

H(X, Y ) = H(X) + H(Y |X)
where
X
H(Y |X) := p(x) H(Y |X = x)
x∈X
X X
=− p(x) p(y|x) log p(y|x)
x∈X y∈Y
XX
=− p(x, y) log p(y|x)
x∈X y∈Y
X
=− p(x, y) log p(y|x)
x∈X ,y∈Y
X p(x, y)
=− p(x, y) log
p(x)
x∈X ,y∈Y
X p(x)
= p(x, y) log .
p(x, y)
x∈X ,y∈Y

Example 11.5. We now consider a motivating example for the AEP. Suppose we flip a coin n times
independently. What is a “typical” sequence? Well, there are 2n total sequences, but a “typical”
sequence has np heads and n(1 − p) tails. The probability of a particular “typical sequence” S is:

P (S) = pnp (1 − p)n(1−p)

= 2np log p 2n(1−p) log(1−p)
= 2n(p log p+(1−p) log(1−p) = 2−nH(p) .
n


Our next question is then, how many such typical sequences are there? Well, there are exactly np ,
nH(p)
which it turns out is approximately 2 for large n! How do we know this? Well it uses Stirling’s
approximation, and we won’t go into detail here, but the first steps look something like this:
 
n n!
=
np (np)!(n(1 − p))!

n
and we use the fact that n! ≈ ne .

What does this example tells us? Well, we have 2nH(p) sequences, and all of these sequences occur
with probability 2−nH(p) . This means virtually all of the probability must be used up by these “typical
sequences”! This is known as the Asymptotic Equipartition Property, and is really quite a mind-
boggling phenomenon, which is hopfully illustrated by this following example:

Example 11.6. Suppose our sequence of RVs are iid Bern(0.11), and we are sending sequences of
n = 1000 of these bits. We know that H(p) = 0.5. This tells us that our “typical set” is composed of
the set of approximately 2500 sequences containing roughly 1000 · 0.11 1’s and 1000 · 0.89 0’s, and each
of the sequences in this typical set have roughly equal probability. Then the source coding theorem

45
 tells us we can transmit these sequences of 1000 bits with on average only around 500 bits!

How could we achieve this in practice? This is a very difficult question, and one that information theorists
do not typically concern themselves with. We can, however, consider the following computationally infeasible
scheme:
1. put each of the 2500 “typical” sequences into a lookup table with 2500 entries
2. if the input sequence is in the typical set, simply send a “0” following by the bit string that is the
index of the typical sequence in the lookup table. The decoder can just look up the typical sequence
in his copy of the lookup table when he receives the compressed message.
3. if the sequence is not “typical”, just send a “1” followed by the whole sequence. This happens with
probability that goes to zero as n → ∞.
The bit at the beginning is simply to let the receiver know whether to look in the lookup table or to just
look at the next 1000 bits. This scheme is entirely infeasible because we cannot store 2500 size lookup table
in our computer, and much research in the last 50 years has been devoted to achieving the source coding
theorem in practice.

Theorem 11.7 (AEP). We now formalize the Asymptotic Equipartition Property. If X1 , ..., Xn are
i.i.d. ∼ PX (x), then
1
− log P (X1 , ..., Xn ) −→ H(X)
n
in probability as n → ∞

11.1 Capacity of BEC

We have a Binary Erasure Channel looks like this:

1−δ
0 PPP - 0
PP
δ PPPP
q e
P
1


δ 

1 -1
1−δ
Where this models the “noise” of a channel which takes a bit and erases it (maps it to e) with some
probability δ. We also have a Binary Symmetric Channel, which looks like this:
1−p
0 Q
-

3 0
Q
pQQ

Q
p QQ

 Q
1 1
 QQ
s
-
1−p
As you can see, it flips each bit independently with probability p.

For the rest of this lecture, we will focus on the Binary Erasure Channel. Intuitively, we note that a
binary erasure channel should have a higher capacity, which we will define shortly, than a BSC, because a
BEC tells you exactly which bits have been corrupted.

46
 Definition 11.8 (Capacity). We say that the capacity of a channel is the maximum rate of reliable
communication for that channel. Mathematically,
Ln
Rate = R =
n
where Ln is the length of your message, and n is the length of your encoding.

Say m is the message your encoder receives (so m ∈ {0, 1}Ln ), and at the end your decoder outputs a
guess m̂. We would like to minimize the probability of error:

Pe(n) = max Pr[m 6= m̂]

m

We say that rate R is achievable for the channel if for every positive number n that is “long enough”, there
exists and encoder and decoder functions fn and gn respectively such that

Pe(n) → 0

as n → ∞. The largest achievable rate R is called the capacity of our channel.

Theorem 11.9. We have that the capacity of a BEC channel is

CBEC(p) = 1 − p

bits per channel use.

This is really a remarkable result (think about why!). We have to show two things:
1. The converse: We need to be able to show that it is not possible to achieve a rate of 1 − p +  for any
 > 0.
2. achievability: We would like to show that there is actually a scheme (even if it is computationally
infeasible) that achieves this 1 − p rate
The proof of the converse goes as follows: Suppose there is a genie which is actually helping you encode
and decode your message by telling you in advance exactly which bits will be erased. We can show that
even with this help, we cannot achieve a capacity better than 1 − p as n → ∞.

47
12 Lecture 12: Wrapup of Info Theory
Agenda:

1. Info theory wrapup (Capacity of BEC, converse and achievability)

2. Quick Note on Huffman Codes
3. Markov Chain Intro

Recall the setup of the BEC, which erases each bit independently with probability p.
encoder channel decoder
m ∈ {0, 1}Ln −−−−−→ X (n) −−−−−→ Y (n) −−−−−→ m̂
Suppose we have an input of Ln bits into our channel. We encode our Ln bits into a sequence of n bits,
where n ≥ Ln (to account for the noise of the channel). Then we have the rate of our channel is
Ln
Rate = R = bits per channel use
n
and the capacity C is simply the maximum rate which we can reliably communicate (i.e. not lose any
information with high probability). We say that the probability of error is:

Pe(n) = max Pr(m̂ 6= m)

We would like to more thoroughly prove the theorem from last time, namely that

CBEC = 1 − p

As we mentioned last time, we need to show two things:

1. The converse: We need to be able to show that it is not possible to achieve a rate of 1 − p +  for any
 > 0.
2. achievability: We would like to show that there is actually a scheme (even if it is computationally
infeasible) that achieves any rate up to 1 − p
Proof. 1. Converse: The idea behind the converse is to have a genie tell you exactly which bits will be
erased beforehand. Even with this information, you cannot achieve a rate better than 1−p bits/channel
use of reliable communication.
2. Achievability: We would like to show that we can achieve a rate R = 1 − p −  for any  > 0.
Shannon’s insight was that we can leverage the SLLN to do this! By the SLLN, the probability that
the channel erases exactly np of the n input symbols is exactly 1 as n → ∞. Shannon’s idea was then
to create a massive lookup table. Each row of the table corresponded to an input, so there are 2L rows.
There were then n columns, so each input corresponded to an n bit string, which is represented by
X (n) in our diagram. Then how was this table populated? Shannon’s idea was to populate the table
with iid Bern(1/2) coin flips! This lookup table is called the Codebook C. Each row ci corresponds
to a ”codeword” corresponding to a specific input message m.

WLOG, we can assume that the BEC channel erases the last np bits (we know it erases almost exactly
np random bits, so we might as well assume they all come at the end). Then we can just consider C 0 ,
which is a truncated codebook with all np bits shoved to the end of each codeword (so the entire right
half of the original codebook is now just erasures).

Now, how should the receiver decode? The decoder simply consults his own codebook (he has his
own copy), to see which one of the 2L codewords matches on the n(1 − p) bits that were sent. When
do we get an error? We get an error when more than one codeword is consistent with the n(1 − p)
bits the decoder receives from the channel.

48
 Analysis: We can assume further WLOG that message 1 was sent. We have then that
P (error) = Pr(c01 is not unique)
 L 
2
[
= Pr  {c0i = c01 }
i=2

2L
X
≤ 2−n(1−p)
i=2
L −n(1−p)
≤2 2
= 2nR−n(1−p) = 2n(R−(1−p)) ,
which goes to zero if R < 1 − p. In particular, if R = 1 − p − , then
n→∞
Pe(n) ≤ 2−n −−−−→ 0,
exponentially fast!

Example 12.1. If n = 10000, p = 0.5,  = 0.01. We know that

1
CBEC(1/2) =
2
which implies our capacity is 5000 bits. But we back off, we have L = 10000(1 − 0.5 − 0.01) = 4900.
Then we have
Pe ≤ 2−10000∗0.01 = 2−100
which is extremely small.

Here is a theorem we won’t prove:

Theorem 12.2. The capacity of a BSC channel is

CBSC(p) = 1 − H(p)

This should make sense, as we get a capacity of zero when p = 1/2, and a capacity of 1 when p = 0 or
p = 1. In general, we have the following theorem from Shannon:

Theorem 12.3. For a general Discrete Memoryless Channel (DMC) which has a conditional proba-
bility P (Y |X), we have that:

C = max I(X; Y ) = max H(X) − H(X|Y )

P (X) P (X)

Intuitively, the mutual information I(X; Y ) (which you explore a bit more in discussion and homework),
tells us how much information you learn about X being given Y . Then of course we should maximize this
in order to be able to transmit the most information through our channel!

12.1 Huffman Coding

Suppose we have a an alphabet X ∈ {A, B, C, D} where PA = 0.4, PB = 0.35, PC = 0.2, and PD = 0.05.
We can calculate that
H(X) = 1.74
Then Huffman’s algorithm to create an encoding for this alphabet is as follows:

49
 1. Remove two members of our alphabet with the smallest probabilities, and assign them a the bits 0 and
1 respectively. Then, add their probabilities, concatenate the letters, and add the combined letters
back into the alphabet.
2. keep doing this until there is only one giant combined member of our alphabet (which will have
probability 1).

After running this algorithm, we can read off the encodings by running backward through the binary tree
we created when running the algorithm.

X = A?

A[0] X = B?

B[10] X = C?

C[110] D[111]

The result of running this algorithm on our example (work this out yourself!) gives

A→0 B → 10 C → 110 D → 111

We can further calculate that the expected number of bits we have to use is 1.85. Notice that this is not quite
optimal in that it does not achieve the entropy. This is because we have to work with integers, whereas the
entropy does not. We can show that Huffman coding is actually optimal when each member of our alphabet
has a probability of the form p = 21i .

50
13 Lecture 13: Markov Chains

Definition 13.1 (Markov Chain). A Markov chain is a sequence of random variables X0 , X1 , X2 , ...
satisfying the following 3 conditions:
1. The assumption that

P r(Xn+1 = cn+1 |X0 = c0 , ..., Xn = cn ) = P r(Xn+1 = cn+1 |Xn = cn )

2. X0 , X1 , ... take on values from some set S

3. X0 is an arbitrary pmf on S.

For a homogeneous discrete time Markov chain, we say P r(Xn+1 = i|Xn = j) = Pji

Example 13.2. Here is an example of a markov chain, represented with a diagram. It represents the
three fundamental states of any Berkeley student.

0.7 0.6
0.2

fine ok
0.2

0.1 0.1 0.4

0.2

ugh

We can specify what our initial state X0 is, and answer questions such as what is the P r(X5 =
ugh)? Over 16 weeks, what fraction of time are you ok?

Example 13.3 (PageRank). PageRank is google’s algorithm for returning search results. It is now
much more complicated, but at its core it uses Markov chains to determine how popular each website
on the internet is. There are a few ways to formulate this notion:

1. Score each page i with πi , such that

X
πi = πj Pji
j

X
πi = 1
i

The first equation is called a balance equation. More on that later.

2. bot randomly picks link on each page it visits. πi is the equal to the probability that the bot is
on page i at some point in time t  0.

51
 3. πi = fraction of time bot spends on page i.
All three of these formulations are equivalent.

Let’s start working our way more towards these balance equations. First, we are interested in what
happens to finite states as n → ∞. We define rij (n) as the probability of going from state i to state j in n
time steps. Well, rij (1) = Pij , since there is only one way to get from i to j in one time step. rij (n) is more
complicated, but luckily we can actually write it in terms of rij (n − 1) as follows:
X
rij (n) = rik (n − 1)Pkj
k∈S

The above are a form of the Chapman Kolmogorov Equations. They should intuitively make sense: the
only way to get from i to j in n steps is if you first get to somewhere else in n − 1 steps, and then make the
last step to state j. We are just summing over all the possible places you could be at time step n − 1. Lets
examine rij (2). We have that X X
rij (2) = rik (1)Pkj = Pik Pkj
k∈S k∈S
 
P1j
 P2j 

 
= Pi1 Pi2 ··· Pim  . 
 .. 
Pmj
Now further recall from CS70 our transition probability matrix:
 
P11 P12 · · · P1m
 P21 P22 · · · P2m 
 
 .. .. .. .. 
 . . . . 
Pm1 Pm2 · · · Pmm

We can then see that rij (2) = (P 2 )ij . This is quite convenient! It is also very easy to then see that
rij (n) = (P n )ij , or the (i, j)th entry of P n . If the values of each column of P n converge to the same value,
then this tells us that no matter where we start out, you have an equal probability of ending up in a given
state.

Remark 13.4. Consider the following Markov chain:

1 2

It is easy to see that we will ”ping pong” infinitely back and forth, and it is entirely deterministic
which state we are in at any given time (given that we know where we started).

Example 13.5 (2 spiders, 1 fly). Consider the following Markov chain:

52
 1 1
1/2 1/2 1/2 1/2

0 1 2 3 4 5

1/2 1/2 1/2 1/2

We will intuitively always end up either at state 0 or state 5, and it is much more likely that we
get stuck at 5 if we start in state 4 than if we start in state 1. So once again, P r(Xn = i) is not
always independent of where we start. In which situations is it? Stay tuned...

P We first note that a more concise way to write (1) in the PageRank example would be πP = π where
i πi = 1. Such a π satisfying these two equations is called the stationary distribution of a markov
chain. We further note the following definitions:

Definition 13.6. State i is recurrent if, starting in state X0 = i, the chain will revisit i at some point
with probability one. Furthermore, we say that a state is positive recurrent if E[Ti ] < ∞, where
Ti is the time to return to state i after leaving it. Otherwise if E[Ti ] = ∞ then the state is called
null recurrent (provided the probability we return to state i is still 1). If a state is not recurrent
then it is called transient.

Definition 13.7. The class of a state i is {j : j accessible from i and i accessible from j}

Proposition 13.8. The states in a class are either all recurrent or all transient.

Proof. Let i and j be in the same class and suppose towards a contradiction that i is recurrent while j is
transient. Since there is a path from i to j, there must be some n ≥ 1 such that Pijn > 0. Now, given
that we start in state i, I will revisit i infinitely often by recurrence. It takes Geom(Pijn ) visits to i before
I will successfully land in state j n steps later. Hence, j is recurrent since geometric RVs are almost surely
finite.

Definition 13.9. Consider si = {n : rii (n) > 0}. Then we define the periodicity of a state as
GCD(si ). In english, the periodicity of a state is the GCD of the all the possible times we could
return to that state. In the ”ping pong” example, both states have a periodicity of 2. If a state has
a self loop, then its periodicity is trivially one.

Proposition 13.10. All the states in a class have the same period.

Proof. We start by denoting d(s) as the period of state s. Once again, consider i and j in a communicating
class together. We know i and j are accessible from each other, so WLOG consider a path of length n from
i to j and a path of length m from j to i. Then there is a path of n + m from i to i, so it follows from the
definition of the period that n + m is divisible by d(i). Consider any path from j to j. Say it has length t.
This creates yet another path from i to i of length n + t + m (first go from i to j, then j to j, then back to
i). B the same logic, we have that n + m + t is divisible by d(i). This implies that t is divisible by d(i), for
all t such that there is a path of length t from j back to j. Since this holds for all t, this means that d(i) is

53
a factor of {n : rjj (n) > 0}, and by definition it is less than or equal to the greatest common factor, d(j)1 .
Reversing the roles of i and j in the above argument implies that d(j) ≤ d(i), which implies that d(j) = d(i),
as desired.
If the above proof was confusing, it is very helpful to draw it out!
In general, any MC with a single aperiodic recurrent class (and some transients) must converge in the
following sense:
1. for each state j,
(n)
lim Pij = πj , ∀i
n→∞

2. The πj are given by a system of equations:

m
X X
πj = πk Pkj πi = 1
k=1 i

3. πi = 0 if state i is transient, and πi > 0 if i is recurrent.

Now, what if we wanted to find the expected amount of time to get from one state to another, given that
we are in stationarity? We will now develop a tool known as first-step equations to deal specifically with
this omnipresent problem. It is actually easiest to see with an example.

Example 13.11. Consider the MC below.

1/2 1/2

1/3
1/2

1 2 3 4 1/2
1/3 1/3 1/2

1/2

We further define xi as the expected amount of steps we must take to reach a certain special
state, say 1 in this case. Then trivially we can observe that x1 = 0. What about x2 ? Well, with 1/3
probability, we are done, but we could also could go to states 3 and 4. By splitting up into cases, we
can see

x2 = 1 + Pr(we go to 1) E[time to 1 from 1]

+ Pr(we go to 2) E[time to 1 from 2]
+ Pr(we go to 3) E[time to 1 from 3]
+ Pr(we go to 4) E[time to 1 from 4]
= 1 + 1/3 · 0 + 0 · x2 + (1/3)x3 + (1/3)x4

Note that we include the 1+ since we need to take at least one step no matter what happens. Using
similar logic, we can come up with the following system of equations for the other nodes:

x3 = 1 + (1/2)x3 + (1/2)x4

x4 = 1 + (1/2)x2 + (1/2)x4
Which leaves us with three equations and three unknowns, which means we can solve for each xi .

1 We can even claim that d(j) is divisible by d(i), but why overcomplicate things?

54
 In general, we can use the same idea to define a mean recurrence time t∗s = the average number of
steps the MC takes to return to state s. Then we have
m
X
t∗s = 1 + Psi ti
i=1

where ti is of course the expected amount of time to get from state i to state s.

Example 13.12. We can consider the same Markov chain from the previous example, but a more
general hitting time problem. Given sets A and B such that A∩B = ∅, we want to find the probability
that we reach a node in set A before we reach a node in set B. Using the MC from the previous
example, we can let A = {1} and B = {4}. Then now we can define xi = probability that we reach
A before B given we start in state i. Then trivially, x1 = 1 and x4 = 0. We also have by splitting
into cases.

x2 = Pr(we go to 1) · Pr(we get to A first given go to 1)

+ Pr(we go to 2) · Pr(we get to A first given go to 2)
+ Pr(we go to 3) · Pr(we get to A first given go to 3)
+ Pr(we go to 4) · Pr(we get to A first given go to 4)
= 1/3 · 1 + 0 · x2 + 1/3 · x3 + 1/3 · 0

Similarly, we can formulate another equation for x3 , which would allow us to solve for our two
unknowns.

Remark 13.13. There is an inherent connection to the material we have (or will) learned about in
CS188. We can think about collecting a reward Ri every time to MC is in state i, and then we can
further define ri as the expected reward we get starting from state i until we reach some set A. Then
we have
ri = Ri ∀i ∈ A
X
ri = Ri + Pij rj ∀i ∈
/A
j

We can also think about adding in a ”discount factor” so if X(n) = i then we receive reward
β n Ri , where β is the discount factor. Then similarly we have:

ri = Ri ∀i ∈ A
X
ri = Ri + β Pij rj ∀i ∈
/A
j

Exercise 13.14. Suppose Alice commutes between 2 houses every week. If the weather is great (this
happens with probability p), she grabs her fishing rod and fishes on her way to the other house.
There are N fishing rods. Assuming this has been going on for a very long time already, what is the
probability that she has no rods when the weather is good? Hint: Set up a MC with N + 1 states.

55
14 Lecture 14: More Markov Chains
14.1 First-step equation modeling

Example 14.1. What is the expected number of tosses until you see two consecutive heads in a row
(assuming the coin is fair)?
We can model this with a Markov chain with three states: the state of having seen zero heads,

1 1
1/2 1/2

0 1 2

1/2
one head, and two heads.
Then, we define
T2 = min{n ≥ 0|Xn = 2}
and then
β(i) = E[T2 |X0 = i]
clearly, β(2) = 0. We also have that
1 1
β(0) = 1 + β(0) + β(1)
2 2
1 1
β(1) = 1 + β(0) + β(2)
2 2
We can solve these equations, since there are three variables and three unknowns (try it!)

In general, for First Step Equations, for a MC over state space X = {1, 2, ..., N } and A ⊂ X we let

TA = min{n ≥ 0|Xn ∈ A}

and then the expected hitting time from each node as

βA (i) = E[TA |X0 = i] ∀i ∈ X

and note we have that

βA (i) = 0 ∀i ∈ A

Example 14.2. Consider the following MC.

1/2 1/2

1/3
1/2

1 2 3 4 1/2
1/3 1/3 1/2

1/2

56
 Considering the above MC chain, a question we could possibly ask is: what is the probability that
I hit state 1 before I hit state 4? This is obviously dependent on what state we start in. In a very
similar manner to the first step equations, we can define some clever variables and solve a system of
equations. We let
α(i) = Pr[T1 < T4 |X0 = i]
Which is simply the probability that we hit state 1 before we hit state 4 given that we start in state
i. Then we can note immediately that

α(1) = 1, α(4) = 0

and we can also set up the relations:

1 1 1
α(2) = α(1) + α(3) + α(4)
3 3 3
1 1
= + α(3)
3 3
1 1
α(3) = α(3) + α(4)
2 2
and so

α(3) = α(4) = 0
1 1 1
α(2) = + α(3) = ,
3 3 3
 
which gives the final result α(i) = 1 1/3 0 0 .

Example 14.3. We once again flip a fair coin until we see two consecutive heads. Whats the expected
number of tails I see?

We can model this via a Markov chain seen below, with a reward function g:

1
1/2 1/2

S H HH

1/2
1/2

1/2
T

Then we have that g(S) = g(H) = g(HH) = 0 and g(T ) = 1. And we can define γ(s) as the
expected total reward given that we start in state s. We have that
1 1
γ(S) = γ(H) + γ(T )
2 2
1 1
γ(H) = γ(HH) + γ(T )
2 2

57
 1 1
γ(T ) = 1 + γ(T ) + γ(H)
2 2
γ(HH) = 0
we can solve this system of equations to get γ(S) = 3.

Theorem 14.4. If MC is irreducible, aperiodic, and positive recurrent, then

lim Pr[Xn = j|X0 = i] = π(j)

n→∞

and the MC is said to be asymptotically stationary.

In general, in the finite setting, every irreducible MC has all its states being positive recurrent. On the
other hand, in the infinite case, we can have all states being positive recurrent, null recurrent, or transient.

Theorem 14.5 (Big Thm for MCs). 1. A MC is either irreducible or reducible

2. if the MC is irreducible, then it is either transient (in which case no π exists), positive recurrent
(a unique π exists), or null recurrent (no π exists).
3. furthermore, if the chain is positive recurrent, then it is either periodic or aperiodic. If it is
aperiodic, then no matter where we start we always converge to π.

Example 14.6 (Another null recurrent MC). Consider

1/2
1/2 2/3 3/4 (i − 1)/i i/(i + 1)

1 2 3 ··· i i+1
1/3

1/4

1/(i + 1)

Is this MC transient or recurrent? Recall that being transient is the same as the probability of
not returning to a state is greater than 0. We have
1 2 3 n 1
Pr[We do not return to state 1 at time n — start at state 1] = · · ··· =
2 3 4 n+1 n+1
This goes to zero as n → ∞, so the chain is recurrent. But is it positive or null recurrent?
We have that
β(1) = E[T1 |X0 = 1]

14.2 Reversibility of MCs

Assume we have an irreducible and positive recurrent Markov Chain, initialized at its invariant distribution

58
π. The notion of reversing a chain is as follows: Suppose for every n, (X0 , X1 , ..., Xn ) has the same joint
pmf as its ”time reversed” version (Xn , ..., X0 ), then we call the chain reversible.

59
15 Lecture 15: Wrapup (reversible) Markov Chains, and beginning
Poisson Processes
Agenda:

1. Reversible MCs
2. Poisson Processes

15.1 Reversible MCs

Consider an irreducible MC {Xn }∞
n=0 on the finite state space X with transition probability matrix P . The
question is: When does a MC “look the same” whether it is run forward or backward? More formally, when
does running the chain backwards give the same transition probabilities and invariant distribution? Here
are some facts:
1. A MC run backward is always still a MC (needs proof)
2. If the MC is reversible, then the backward chain is the same MC as the forward chain.

Proof. 1. We have that

Pr[Xk = ik |Xk+1 = ik+1 , ..., Xk+n = ik+n ]
Pr[Xk = ik Xk+1 = ik+1 , ..., Xk+n = ik+n ]
=
Pr[Xk+1 = ik+1 , ..., Xk+n = ik+n ]
Now, we use the Markov Property, and I drop the ij ’s for simplicity:

Pr[Xk+n |Xn+k−1 ] Pr[Xn+k−1 |Xn+k−2 ] · · · Pr[Xk+1 |Xk ] Pr[Xk ]

Pr[Xk+n |Xn+k−1 = in+k−1 ] Pr[Xn+k−1 |Xn+k−2 ] · · · Pr[Xk+2 |Xk+1 ] Pr[Xk ]

π(ik )P (ik , ik+1 )

=
π(ik+1 )
Notice that this is only a function of ik+1 , which shows that the backwards chain satisfies the Markov
Property! Furthermore, if we denote P̃ as the transition probability matrix for the reversed chain, then
we have that:
π(ik )P (ik , ik+1 )
P̃ik+1 ,ik =
π(ik+1 )
So then, if our chain is reversible, we have the condition that

π(ik )P (ik , ik+1 )

P̃ik+1 ,ik = Pik+1 ,ik =
π(ik+1 )
π(ik )P (ik , ik+1 )
=⇒ Pik+1 ,ik = .
π(ik+1 )

Theorem 15.1. If a MC is reversible, it has an invariant distribution π

P
Proof. We need to show that ∀j, π(j) = i π(i)Pij ⇐⇒ π = πP . We have that:
X X X
π(i)Pij = π(j)Pji = π(j) Pji = π(j).
i i i

Summary: Detailed balance equations being satisfied are sufficient but not necessary to have a stationary
distribution.

60
 Remark 15.2 (Sufficient condition for MC to be reversible). Fact: Start with a graph associated with
a MC, forget self loops and make all the arrows undirected. Then we have an undirected graph. If
this resulting graph is a tree, then detailed balance equations hold. Note that the converse does not
necessarily hold. Also note that this is not a necessary condition for detailed balanced equations to
hold, only sufficient.

15.2 Poisson Processes

A Poisson Process is the continuous time analog of a ”coin flip” or Bernoulli process. Some motivation:
1. Good model for arrivals of packets at a router, customers arriving at a cashier, photons at a detector,
etc.

Definition 15.3 (Poisson Process). We denote Nt as the total number of arrivals we have at any time
t.

TODO 3. draw graph

We denote Ti as the time of the ith arrival, and Si as the inter-arrival times, so

Si = Ti − Ti−1

and we define:
S1 , ..., Sn ∼iid Expo(λ)
Formally, we define: (
maxn≥1 {n|Tn ≤ t} t≥0
Nt =
0 t < T1

Recall for an exponential distribution τ ∼ Expo(λ), we have

1. Fτ (t) = 1 − e−λt
1
2. E[τ ] = λ
1
3. Var(τ ) = λ2

4. Memorylessness: Pr[τ > t + s|τ > s] = Pr[τ > t]

5. Pr[τ ≤ t + ]|τ > t] = λ + o()
Note that the ”little-o” notation just refers to any function such that:
o()
lim =0
→0 
Note that for example 2 ∈ o()
proof of (5).
Pr[τ ≥ t + ]|τ > t] = Pr[τ > ] = e−λ = 1 − λ + o()
The above probability is the probability that there are no arrivals in a tiny  amount of time. Then
the probability of one arrival is approximately λ, and the probability of more than one arrival in a tiny 
amount of time is o(), which we assume is essentially zero. So in a tiny amount of time, we only ever see
one or zero arrivals. In Bertsekas, we start with this assumption and then derive that the interarrival times
must be exponential, but we follow the Walrand book and assume that they are exponential and then derive
this property.

61
 Theorem 15.4. Poisson Processes are memoryless.

In pictures, if Nt ∼ P P (λ), then so is (Nt0 +s − Nt ). The implication is that if we take increments of

a poisson process that do not overlap in time, then these increments are independent and stationary
(meaning if we shift in time, the statistics remain the same).

⇒ ∀0 ≤ t1 < t2 < ... < tn {(Ntn+1 − Ntn )}are independent and distribution depends only on (tn+1 − tn )

Proof. Straightforward from the memoryless property of the exponential.

Theorem 15.5. If N = {Nt |t ≥ 0} is a P P (λ), then Nt = the number of arrivals in (0, t) is distributed
according to a poisson distribution with parameter λt:

e−λt (λt)k
Pr(Nt = k) =
k!

Proof. We start by finding the joint probability density of T1 , ..., Tk , Tk+1 , where we know there are k arrivals
in (0, t). We have

f (t1 , ..., tk )dt1 · · · dtk+1 = Pr[T1 ∈ {t1 , t1 + dt1 }, ..., Tk ∈ {tk , tk + dtk }, Tk+1 > t]
= Pr[S1 ∈ {t1 , t1 + dt1 }, S2 ∈ {t2 − t1 , t2 − t1 + dt2 }, ...,
Sk ∈ {tk − tk−1 , tk − tk−1 + dtk }, Sk+1 > t − tk ]

   
= λe−λt1 dt1 λe−λ(t2 −t1 ) dt2 · · · λe−λ(tk −tk−1 dtk e−λ(t−tk )
= λk e−λt dt1 dt2 · · · dtk .

Note that this joint distribution does not(!) depend on t1 , ..., tk , which tells us that conditioned on the
number of arrivals in an interval, those arrivals are uniformly distributed in the interval! Of course, we must
have that they are in the correct order still.

62
16 Lecture 16: Properties of Poisson Processes
Agenda:

1. Recap of Poisson Processes

2. Proof that number of arrivals in (0,T) is ∼ P ois(λT ).

3. examples
4. Merging and Splitting of PPs

5. Erlang Distribution
6. Random-Incidence-Paradox

Recall we have this theorem:

Theorem 16.1. If N = {Nt |t ≥ 0} is a P P (λ), then Nt = the number of arrivals in (0, t) is distributed
according to a Poisson distribution with parameter λt:

e−λt (λt)k
Pr(Nt = k) =
k!

and we had begun working through a proof:

Proof. We start by finding the joint probability density of T1 , ..., Tk , Tk+1 , where we know there are k arrivals
in (0, t). We have

f (t1 , . . . , tk )dt1 · · · dtk+1 = Pr[T1 ∈ {t1 , t1 + dt1 }, . . . , Tk ∈ {tk , tk + dtk }, Tk+1 > t]
= Pr[S1 ∈ {t1 , t1 + dt1 }, S2 ∈ {t2 − t1 , t2 − t1 + dt2 }, . . . ,
Sk ∈ {tk − tk−1 , tk − tk−1 + dtk }, Sk+1 > t − tk ]

   
= λe−λt1 dt1 λe−λ(t2 −t1 ) dt2 · · · λe−λ(tk −tk−1 dtk e−λ(t−tk )
= λk e−λt dt1 dt2 · · · dtk
=⇒ fT1 ,...,Tk (t1, ..., tk ) = λk e−λt

Note that this joint distribution does not depend on t1 , ..., tk , which tells us that conditioned on the
number of arrivals in an interval, those arrivals are uniformly distributed in the interval! Of course, we must
have that they are in the correct order still. The way I like to think about this is simply dropping these
arrivals randomly in the interval, and then assigning the arrivals to be in the correct order. Now, we have
Z Z Z
NT (k) = ··· fT1 ,...,Tk (t1 , ..., tk )dt1 · · · dtk
t1 t2 tk
Z t Z t
k −λt
=λ e ··· dt1 · · · dtk .
0 0

The above expression is only correct if we have the condition that t1 < ... < tk . Let S be the support of the
pdf. Then this equals
λk e−λt V ol(S)
What is V ol(S)? If we had no constraints as to order, then the volume would be tk . But by symmetry, all
of the possible orderings (of which there are k!) have the same volume, so we have to divide by k!. If this is
not intuitive, then consider the case when k = 2.

63
 TODO 4. draw square for k =2, and show how vol(S) = t2 /2!

Then we have
λk e−λt tk
Nt (k) =
k!
which is a Poisson distribution with parameter λt, as desired!

Example 16.2 (Fishing). Bob catches fish according to a PP(λ = 0.6/hr). If he catches at least one
fish in the first two hours, he quits. Otherwise, he continues until he has caught his first fish.
1. What is the probability that bob fishes for more than two hours?
2. What is the probability that Bob catches at least two fish?

3. What is the expected number of fish Bob catches?

4. What is the expected fishing time, given that he has been fishing for 4 hours already?
Answers:

1. P r[N2 = 0] = e−λ·2 = e−1.2

2. 1 − Pr(N2 = 1) − Pr(N2 = 0) = 1 − e−1.2 − 1.2e−1.2
3. Total number of fish caught = fish caught in [0,2] + fish caught in [2,∞]. Then we can use
linearity of expectation and we have

E[total fish caught] = E[P ois(1.2)] + 1 · Pr[still fishing in (2, ∞)]

1.2 + e−1.2

4. We of course use the memoryless property, and we get

1
4 + E[Expo(0.6)] = 4 + = 5.66hrs
0.6

16.1 Merging and Splitting

Merging:

Suppose we have N1 is a P P (λ1 ) and N2 ∼ P P (λ2 ). Then we have the following fact:
N = N1 + N2 ∼ P P (λ1 + λ2 )
This fact follows easily from the fact that the sum of two independent poisson random variables is still
poisson with their parameters added, which we have proven earlier in the semester (can be proven with
MGFs or with a convolution).
Splitting:
Suppose we have N ∼ P P (λ), and then we take each arrival and send it to N1 with probability p, and send
it to N2 with probability 1 − p. We do this independently for each arrival. Then here are some facts:
1. N1 ∼ P P (λp)
2. N2 ∼ P P (λ(1 − p))
3. N1 (t) and N2 (t) are independent RVs.
These again follow from the proof of poisson random variable splitting we did in homework earlier in the
semester.

64
 Example 16.3. Suppose we have two lightbulbs have independetly and exponentially distributed
lifetimes Ta and Tb respectively, with parameters λa and λb respectively. What is the distribution of
Z = min(Ta , Tb )?

Well, we can recall that this is simply an exponential RV with rate λa + λb (or can easily derive
this by examining the CDF). But a way cooler way is to notice that that Ta and Tb are the times of
the first arrivals of two independent Poisson Processes with rates λa and λb . The min(Ta , Tb ) is the
first arrival of the merged PP, which we know has rate λa + λb , so then we know that

min(Ta , Tb ) ∼ Expo(λa + λb )

16.2 Erlang Distribution

Recall that we defined Tk = S1 + ... + Sk to be the time of the k th arrival of the poisson process. We can
observe:

1. E[Tk ] = E[Si ] = λk
P

k
2. Var(Tk ) = k Var(Si ) = λ2

We would like to know the pdf of Tk . The distinctly uncool way to calculate this would be with a big
convolution. But we can do something easier:

fTk (t)dt = Pr[k-1 arrivals in (0,t)] Pr(1 arrival in (t,t+dt))

e−λt (λt)k−1
= · λdt
(k − 1)!
e−λt λk tk−1
=⇒ fTk (t) =
(k − 1)!
This is known as the k th -order Erlang Distribution.

65
17 Lecture 17: CTMCs
Agenda:
1. Quick Recap of PPs
2. Random Incidence Paradox
3. CTMC’s: Introduction
4. Rate Matrix and Stationary Distributions

17.1 Random Incidence Paradox (RIP)

Consider a Poisson process with rate λ, and suppose it has been going on infinitely long. The question we
would like to answer is: if I pick a random t∗ , what is the expected length of the interval in which it falls?
It is very tempting to say that, since each interarrival is Expo(λ), that then the expected length of the
interval is just the expectation of that exponential random variable, which is λ1 . Let’s call L the length of
the interval in which t∗ falls. We claim then that L is distributed according to an Erlang-2(λ) distribution.
Why is this the case?
Lets say t∗ falls between Ti and Ti+1 . Lets call U := Ti and V := Ti+1 . Then we have that
L = (t∗ − U ) + (V − t∗ )
We have by the memorylessness property that V − t∗ is distributed according to an exponential distribution!
Now what about t∗ − U ? We have:
Pr(t∗ − U > x) = Pr(more than x sec have elapsed since last arrival)
= Pr(no arrivals in [t∗ − x, t∗ ])
= Pr(N (x) = 0) = e−λx .
Now we note that this looks like 1 − FX (λ) where X ∼ Expo(λ) (and F is the CDF of X), therefore t∗ − U
must be an exponential random variable as well. Hence L is the sum of two independent exponential random
variables and therefore an Erlang-2 distribution.

Remark 17.1. The key takeaway from the section above is that a Poisson process run backwards is
still a Poisson process with exponential interarrival times.

Remark 17.2. Here is some more intuition for RIP. Suppose the bus schedule is fixed deterministically,
a bus comes after 5 mins, then after 55 minutes, then after 5 minutes, then after 55 minutes, etc.
Then we have that the average interarrival time is of course 30 minutes. However, what if we just
randomly show up to the bus stop? Then we the expected length of the interval we arrive in is
actually:
(5/60) · 5 + (55/60) · 55 = 50.83

17.2 Continuous-Time Markov Chains (CTMCs)

Similar to a discrete time Markov Chain, we start with a countable set X of states. Then the process is
{Xt : t ≥ 0}, defined via the following:
1. One is given an initial prob distribution over X
2. a rate matrix Q where
(a) Q(i, j) ≥ 0 ∀i 6= j.
P
(b) j Q(i, j) = 0.

66
 Example 17.3. We could have  
−4 3 1
Q= 0 −2 2
1 1 −2
(Note: This follows the convention in Walrand’s book, not Bertsekas).

Definition 17.4. A CTMC with initial distribution π and rate matrix Q is a process {Xt , t ≥ 0} such
that Pr(X0 = i) = π(i), and
(
Q(i, j) + o() i 6= j
Pr(Xt+ = j|Xt = i, Xu , u < t) =
1 + Q(i, i) + o() i = j

The above definition follows the traditional Markov property we are used to (when  is small enough),
and note that X
Pr(Xt+ 6= i|Xt = i) =  Q(i, j)
i6=j
X
=⇒ Pr(Xt+ = i|Xt = i) = 1 −  Q(i, j) = 1 + Q(i, i)
i6=j

Where in the above I have dropped the o() terms.

Example 17.5. Consider the Markov chain below:

1 2

1 1 2

3 1

Where  
−4 3 1
Q= 0 −2 2
1 1 −2
And suppose our initial π is π = (1/3, 1/3, 1/3). Then we have:

Pr(Xt+ = 3|Xt = 1) = Q(1, 3)

We can set up the following jump chain:

and we define qi = |Qii |.

67
18 Lecture 18: More on CTMCs
Agenda:
1. Review of CTMC definition and properties
2. Rate matrix Q and stationary distribution π
3. Examples
4. First Step Equations for CTMC
5. Simulating a CTMC using a DTMC
Recall that a CTMC is defined by a rate matrix Q where

Q(i, j) ≥ 0 ∀i 6= j
X
Q(i, j) = 0
j

And by definition we have

Q(i, j) ≥ 0 ∀i 6= j
Q(i, i) ≤ 0
The holding time in state i, which is the amount of time we wait in state i before making a jump, is
∼ Expo(q(i)) where q(i) = −Q(i, i)
Recall we also have the continuous analog of the Markov Property:
(
Q(i, j) + o() i 6= j
Pr(Xt+ = j|Xt = i, Xu , u < t) =
1 + Q(i, i) + o() i = j

And in particular we have

X
Pr(Xt+ = i|Xt = i) = 1 −  Q(i, j) = 1 − (−Q(i, i)) = 1 − q(i)
i6=j

If the current state is i, the time to “jump” is Expo(q(i).

Lets go back to the example we were looking at then end of last lecture:

Example 18.1. Consider the Markov chain below.

1 2

1 1 2

3 1

Where  
−4 3 1
Q= 0 −2 2
1 1 −2

68
 And suppose our initial π is π = (1/3, 1/3, 1/3). Then we have:

Pr(Xt+ = 3|Xt = 1) = Q(1, 3)

We can setup the following embedded DTMC :

3/4

1 2

1/4 1/2 1

3 1/2

This DTMC models the jumps of the CTMC, but potentially does not model how long we are
waiting in each state in the CTMC. We get these probabilities by remembering the properties of
exponential splitting. Then we have

Pr(Xt+ = 3|Xt = 1) = (4)(1/4)

How did we get this? Well, we need to jump in time (0, ), which happens roughly with probability q(i).
Then, when we jump, we need to jump to the correct state j, which happens with probability Q(i,j)
q(i) . Both
of these things need to happen in order to transition to state j from state i, so we have
Q(i, j)
Pr(Xt+ = j|Xt = i) = q(i) = Q(i, j)
q(i)

Example 18.2 (B&T 7.14). Say we have a Normal state (1) and a test state (2) and a repair state
(3).

1 2
2.5

3 2.5

What is the stationary distribution of this Markov Chain? Recall that for discrete Markov Chains,
we needed to solve for π = πP . However, for a continuous time markov chain, we need to solve for
X
πQ = 0 πi = 1
i

This is known as the ”Rate conservation principle” or ”rate in = rate out” (can you see why?). Then

69
 we have  
−1 1 0
Q = 2.5 −5 2.5
3 0 −3
Writing out the equations, we have
5
π(1) · 1 = π(2) + π(3) · 3
2
Notice that the left hand side is the flow coming out of state 1, while the right hand side is the flow
going into state 1! For me, it is easier to remember this concept than to write out the equations by
just remembering the matrix formula. We can set up the rest of the equations and solve to find

π = (30/41, 6/41, 5/41)

Remark 18.3 (Poisson Processes are CTMCs). If we have a P P (λ), we can model it as a CTMC as
follows:

λ λ λ

1 2 3 ···

Example 18.4. We can consider the two state markov chain which transitions from state 0 to state
one with rate λ, and from state 1 to state 0 with rate µ. Then by the flow equations we have

−λπ0 = µπ1 − µπ1 = λπ0 π0 + π1 = 1

We can solve these equations to find that

µ λ
π0 = π0 =
λ+µ λ+µ
So when λ = 1 and µ = 2, we are ”parked” in state 0 twice as much as we are parked in state 1.
However, the embedded DTMC has the stationary distribution (1/2, 1/2), no matter what λ and µ
are. Clearly, we need to do something different if we want our DTMC to have the same stationary
distribution as the CTMC.

18.1 Hitting Times

Example 18.5. Consider 20 lightbulbs that have indep. lifetimes that are exponentially distributed
with rate 1 (month). How long before all the bulbs die out?
We can model this with 21 states, corresponding to the number of lightbulbs still alive. We transition
from state 20 to state 19 with rate 20 (min of 20 exponentials!), and from 19 to 18 with rate 19, and
so on. How long does it take for us to get to zero? We have to come up with first step equations,
which are quite analogous to the ones we saw for DTMCs. The biggest difference is that we are not
transitioning after 1 time step now, we are transitioning on average after 1/q(i) amount of time (the
mean of the exponential) if we are in state i. We can define xi as the expected amount of time to hit

70
 zero given you are in state m. We have then
1
xi = + xi−1
i
This implies that
1 1
x20 = + + · · · + 1 ≈ 3.6
20 19

Example 18.6. Now assume the burnt out bulbs are replaced after an exponential amount of time
with mean 0.1 month (meaning λ = 10). Now what is the expected amount of time until all our bulbs
have burnt out? Now our FSE looks like:
1
β(20) = + β(19)
20
and more generally for 1 ≤ m ≤ 19:
1 m 10
β(m) = + β(m − 1) + β(m + 1)
m + 10 m + 10 m + 10
and finally β(0) = 0. Solving for these equations recursively yields

β(20) ≈ 2488

18.2 Simulating a CTMC with a DTMC

Let’s consider the same example as before.

1 2
2.5

3 2.5

where
 
−1 1 0
Q = 2.5 −5 2.5
3 0 −3
We then define Λ = maxi q(i) = 5. This is intuitively our ”clock delay”. We can form the DTMC by dividing
all the transition rates by Λ and adding self loops when necessary:

71
 4/5
1/5

1 2
1/2

3/5 1/2

2/5

We can verify that this π is the same for this DTMC as for the CTMC.

72
19 Lecture 19: Random Graphs
Agenda:
1. Wrapup of CTMCs (simulating CTMC with DTMC)
2. Random Graphs
(a) intro, definition
(b) Erdös-Renyi G(n, p) random graph model
(c) Threshold conditions for graph connectivity

19.1 recap of CTMCs

Why would we want to simulate a CTMC with a DTMC? For one, it’s easier to implement and do on a
computer. Two key points about simulating CTMCs with DTMCs:
1. The jump or embedded chain has no self loops, and in general the stationary distribution of this
chain and the corresponding CTMC is not the same. Intuitively, this is because if we have different
values of q(i) for each state i, then we are ”waiting” longer at certain states, which is not reflected in
the jump chain.
2. If we want the corresponding DTMC to have the same stationary distribution, we have to form a
DTMC by dividing transition by Γ = maxi q(i), and adding self loops where necessary. This effectively
adds in a waiting time to the corresponding DTMC. Here we can think of Γ = maxi q(i) as the clock
rate of the markov chain.
The stationary distribution remains the same in the second case because our new matrix P = I + Q/Γ.
We can verify that an eigenvalue of Q is also an eigenvalue of P , so therefore the stationary distributions
must be the same.

19.2 Random Graphs

Some motivation:
1. Graphs, and random graphs, are everywhere. They have applications to the behavior of social networks,
biological networks, recommendation systems (matrix completion), etc.
2. Modeling epidemics (very topical) involves random graphs.

Definition 19.1 (Erdös-Renyi (ER) Random Graphs). Given a positive integer n and a probability value
p ∈ (0, 1].
Then G(n, p) is a random graph which is undirected graph on n vertices such that each
of the n2 edges are present independently and with probability p.

Intuitively, we are just drawing n vertices, and for each pair of vertices, we flip a biased coin (prob p of
heads), and if it comes out heads, we draw an edge between these two vertices.

Erdös and Renyi stated a number of results that are based on “thresholds” of p needed for certain structural
properties of the graph to emerge.

1
Example 19.2. 1. If p = n2 , then we see at least one edge with high probability.
1
2. if p = n3/2
, then the first “3-node trees” (incomplete triangles) start to emerge.
1
3. if p = n, then the first cycles begin emerging

73
 4. if p = n1 , then the first “Giant Component” emerges. Specifically, if p = 1−
n , then the largest
connected components are of size O(log n), but if p = 1+
n , then suddenly the size of the largest
component is of size O(n).

We will focus today on arguably the most important threshold for random graphs: the threshold for
connectivity.

Lemma 19.3. If p > logn n , then our graph is connected w.h.p. Otherwise, if p < log n
n then our graph
is not connected with high probability

Remark 19.4. We have that the probability of a particular fixed graph G0 with m edges appearing
is  n

n
Pr(G(n, p) = G0 ) = 2 pm (1 − p)( 2 )−m
m

Question 1: What is E[# edges in G]? We have that there are n2 possible edges, each appearing with

probability p, so by linearity of expectations (after defining appropriate indicators), we have

 
n
E[# edges in G] = p
2

Question 2: If we pick an arbitrary vertex and let D be its degree, then what is the distribution of D?
What is the expected degree?
Answer: We have that D ∼ Binom(n − 1, p), and therefore we have
 
n−1 d
Pr(D = d) = p (1 − p)n−1−d ∀d ∈ {0, 1, ..., n − 1}
d
and E[D] = p(n − 1).
µ
Question 3: Suppose now that pn = n for a constant µ > 0. What is the approximate distribution of D
when n → ∞, pn → 0, and pn n → µ?
Answer:
D ∼ P oisson(µ)
And we have
e−µ µd
Pr(D = d) ≈
d!
Question 4: What is the probability q that a node is isolated?
Answer: q = (1 − p)n−1

Theorem 19.5 (E-R ’61). Let pn = λ logn n . Then

1. If λ < 1, then
n→∞
Pr(G(n, p) is connected) −−−−→ 0

2. If λ > 1, then
n→∞
Pr(G(n, p) is connected) −−−−→ 1

ln n+c
Remark 19.6. if pn = n for a constant c ∈ R, then it can be shown that
n→∞ −c
Pr(G(n, p) is connected) −−−−→ e−e

Before we begin the proof of the the theorem, we need this quick lemma:

74
 Lemma 19.7. If X is a non-negative integer valued RV, then

Var(X)
Pr(X = 0) ≤
E[X]2

Proof.

Var(X) = E[(X − E[X])2 ] = Pr(X = 0) E[X]2 + Pr(X = 1)[E[X] − 1]2 + Pr(X = 2)[E[X] − 2]2 + . . .
≥ Pr(X = 0) E[X]2
Var(X)
=⇒ Pr(X = 0) ≤ .
E[X]2

Now we can do the proof of the theorem:

Proof. For (1), it is sufficient to show that there will be isolated nodes with high probability. This is actually
something stronger than we need, but we will prove it anyway. We would like to show
n→∞
Pr(no isolated nodes) −−−−→ 0

Let X be the number of isolated nodes in our graph. First, lets find E[X]. We define Ii as the indicator
RV of the event that node i is isolated. Then we have that
n
X n
X
E[X] = E[Ii ] = Pr(node i is isolated) = nq = n(1 − p)n−1
i=1 i=1

Then we have that

−λ ln n
ln E[X] = ln n + (n − 1) ln(1 − p) ≈ ln n + (n − 1)(−p) = ln n + (n − 1)
n
Where in the second equality we have used the fact that via Taylor series expansion, for small x, we have
ln(1 − x) ≈ −x. Then we have finally
n−1 n→∞
ln E[X] ≈ ln n − λ ln n ≈ ln n(1 − λ) −−−−→ ∞
n
And we have that
E[X] ≈ e(ln n)(1−λ) = n1−λ
Note that we are not done yet. Just because the expectation of a RV goes to infinity does not mean that
the probability that it is not zero goes to zero. Consider the RV
(
0 w.p. 1 − n1
W =
n w.p. n1
2

n→∞
Then we can see that E[W ] −−−−→ ∞, but also the probability that W = 0 goes to one as n goes to infinity.
To finish the proof, we need to get a handle on the variance of X, as well as use the lemma we proved above.
We have X
Var(X) = Var( Ii )
i

We note here that the our indicators are not independent, so we have to do some more work.
n
X n X
X
Var(X) = Var(Ii ) + Cov(Ij , Ik ) = n var(I1 ) + n(n − 1) Cov(I1 , I2 )
i=1 j=1 k6=j

75
 Now, in order to continue, we need to figure out what the covariance term is. We have

Cov(I1 , I2 ) = E[I1 I2 ] − E[I1 ] E[I2 ]

Here since Ii is an indicator, E[Ii ] is just equal to the probability that node i is isolated, and E[I1 I2 ] is the
probability that both nodes one and two are isolated, so we have

q2
Cov(I1 , I2 ) = (1 − p)n−1 (1 − p)n−2 − (1 − p)n−1 (1 − p)n−1 = − q2
1−p
Now we can plug this back into our original expression, and we find that
 2
pq 2

q
Var(X) = nq(1 − q) + n(n − 1) − q 2 = nq(1 − q) + n(n − 1)
1−p 1−p

Now, we use our lemma to upper bound the probability that X = 0:

2
pq
Var(X) nq(1 − q) + n(n − 1) 1−p
Pr(X = 0) ≤ =
E[X]2 n2 q 2
1−q n−1 p
≤ + .
nq n 1−p
1−q n→∞ p n→∞
Now we are done, because nq −
−−−→ 0 and 1−p −
−−−→ 0. So we have proven the first part of the theorem.

How do we prove the second part? Namely, we want to show that if λ > 1, we want to show that
n→∞
Pr(G not connected) −−−−→ 0

We will give only a proof sketch here. The idea is that the “Graph is disconnected” ≡ “there exists a set of
size k (where 1 ≤ k ≤ n/2) such that there is no edge between this set and its complement”. Next, we will
apply the union bound twice to get the result.
n/2
[
Pr(graph is not connected) = Pr( (∃set of size k disconnected from everything))
k=1
n/2  
X n
≤ Pr(a specific set of size k is disconnected)
k
k=1
n/2  
X n
= (1 − p)k(n−k) .
k
k=1

We can show that this summation goes to zero as n goes to infinity, but we omit the details here because it
gets a bit messy. The details can be found in the appendix of the class notes.

76
20 Lecture 20: Wrapup of Random Graphs and Starting Statistical
Inference
Agenda:
1. Random Graphs (finish proof of graph connectivity cutoff)
2. Statistical Inference (MAP and MLE and examples)

20.1 Statistical Inference

There are two schools of thought when it comes to statistical inference:
1. Bayesian: Treats unknowns as RVs with known distributions and priors, which effectively moves
statistics to the realm of probability analysis.
2. Frequentist: Treats unknown as deterministic parameters to be estimated (for example, the mass of
an electron). Bayesian priors reflect our knowledge.
The basic premise: There are some number N possible exclusive causes of a particular symptom.
Exactly 1 of the N possibilities is the correct cause.

In the above figure, the pi ’s are the priors, which tells us how likely each of our causes are a priori. The
qi ’s tell us the conditional probability of the symptom given a specific cause i. However, we are looking for
the posterior probability πi , which is the conditional probability of cause i given the symptoms we are
seeing. We will use the all powerful Bayes Rule to achieve figure this out. We have:
Pr(ci ∩ S) Pr(S|ci ) Pr(ci )
πi = Pr(ci |S) = =P
Pr(S) i Pr(S|ci ) Pr(ci )
pi qi
=P
i pi qi
This is actually our first theorem:

77
 Theorem 20.1 (Bayes’ Theorem).
pi qi
πi = P
i pi qi

Then the Maximum A Posteriori (MAP) estimate of the cause given the symptom is arg maxi πi =
arg maxi pi qi .
The Maximum Likelihood Estimate (MLE) is the same thing, except we assume that all our priors are
just uniformly distributed (so no cause is more likely than another). So then the MLE is arg maxi qi .

More generally, we have that

M AP (X|Y = y) = arg max Pr(X = x|Y = y)

x

M LE(X|Y = y) = arg max Pr(Y = y|X = x)

x

Let’s do some analysis on the MAP/MLE of a BSC channel. Recall the BSC channel looks like this:
1−p
0 Q
-

3 0
Q
pQQ 

Q 
p 
 Q Q
 Q
1 1
 QQ
s
-
1−p

Theorem 20.2. For a BSC(p) with p < 1/2, we have

M AP [X|Y = 0] = 1p>1−α
M AP [X|Y = 1] = 1p<α

and
M LE[X|Y ] = Y
where α = Pr(X = 1).

Proof. We have M AP [X|Y = 1] = arg maxi∈{0,1} pi qi . If p0 q0 > p1 q1 , then we guess that x̂ = 0, and
otherwise if p0 q0 < p1 q1 , then our guess is x̂ = 1. We have

p0 q0 = (1 − α)p p1 q1 = α(1 − p)

Then we have that p0 q0 < p1 q1 ⇔ p < α, which means that

X̂M AP (Y = 1) = 1p<α

which is exactly what we wanted to show. We can do something very similar for the case when we observe
Y = 0. Finally, we note that M LE[X|Y ] is equal to our MAP estimate, when we let α = 1/2. Then we get
the result claimed.

78
21 Lecture 21: Wrapup of MLE/MAP and Hypothesis Testing/Neyman-
Pearson
Agenda:

1. Wrapup of MLE/MAP
2. Hypothesis Testing and Neyman-Pearson

21.1 Wrapup of MLE/MAP

Example 21.1 (AWGN channel). AWGN (Additive White Gaussian Noise) channel is just a channel
that takes in X and outputs Y = X + Z where Z ∼ N (0, σ 2 ). Assume X is Bernoulli, then when
X = 0, we have Y ∼ N (0, σ 2 ), and when X = 1 we have Y ∼ N (1, σ 2 ). If we plot this, we can see
that these are just two Gaussian pdf’s with different means that have some overlap:

Our symptom is Y = y, while our causes are X = 0 or X = 1. Then we note that

Pr(Y = y|X = 0) ≈ f0 (y) Pr(Y = y|X = 1) ≈ f1 (y)

where f0 and f1 are the densities of the normal distribution centered at 0 and 1 respectively. Then
our MAP rule says we should declare X̂ = 0 if

p0 f0 (y) ≥ p1 f1 (y)

and otherwise we should declare X̂ = 1. Equivalently, we guess X̂ = 0 if

f1 (y) p0
≤
f0 (y) p1
f1 (y)
where this f0 (y) is known in the business as a likelihood ratio L(y). In particular, we have
2
(y−1)
√1 exp −
2π 2σ 2
L(y) = 1 −y 2
√
2π
exp 2σ2
 
2y − 1
= exp
2σ 2

79
We can take the log of the likelihood LL(y) := log L(y)
2y − 1
LL(y) =
2σ 2

Then we guess X̂ = 0 iff  

p0
LL(y) ≤ log
p1
or in other words we guess zero if  
1 p0
y < + σ 2 log
2 p1
and this is our MAP rule. what about our MLE? Well we just set p0 = p1 in that case and our rule
becomes to guess X̂ = 0 iff
1
y<
2

In the above example, we can see how the MAP rule affects our decisions. If pp01 = e and σ 2 = 0.1,
then our new cutoff is 0.6, indicating that we are inclined to believe that the cause was X = 0 even
if the density is higher for X = 1.

Example 21.2 (German Tank Problem). This problem was motivated by WWII, where the allies
wanted to estimate how many tanks the Germans had just by observing the serial numbers of the
captured/destroyed tanks. Suppose we have a bucket with N balls, each labeled 1 through N , where
N is an unknown integer. What is
M LE[N |Y = m]
Let’s say we observe Y = 7. What is the MLE of N given your observation? We have
(
0 if n < 7
M LE[N |Y = 7] = arg max Pr[Y = 7|N = n] = arg max
n n 1/n if n ≥ 7

Which implies that M LE[N |Y = 7] = N̂ = 7, and in general

M LE[N |Y = m] = m

What if we observe k balls, y1 , ..., yk ? There are nk sets of k distinct numbers that are subsets

80
 of [n] = {1, ..., n}. Each subset is equally likely, so
( 1
if y1 , ..., yk ∈ [n]
Pr(y1 , ..., yk |n) = (nk)
0 otherwise

This is once again maximized when n = max{y1 , y2 , ..., yk } = mk . This is once again a weird
solution, and arises because the MLE is a biased estimator. It can be fixed, but we won’t get into
how in this course.

21.2 Hypothesis Testing

Motivation: In many settings, the notion of a prior doesn’t make much sense. What’s the prior of your house
being on fire? MLE and MAP are “point-estimates”, which are not meaningful when priors are not sensible
to assign (e.g. alarm systems, spam filters, medical tests, etc.)
We are going to use the Formulation of Neyman and Pearson:
Consider X ∈ {0, 1} is the inference RV of interest, and it induces a continuum of tradeoffs based on the
observation. Our goal is to maximimize the probability of correct detection:

max P CD = max Pr(X̂ = 1|X = 1)

such that the probability of false alarm is less than some value β:

P F A = Pr(X̂ = 1|X = 0) ≤ β

Then the Neyman-Pearson method is to:

1. Observe Y

2. Two hypotheses:
• H0 : Y ∼ f (y|X = 0). This is called the null hypothesis
• H1 : Y ∼ f (y|X = 1). This is called the alternative hypothesis
3. formalize some decision rule
r : R → {0, 1}
where X̂ = r(Y ).

Alternatively, but equivalently, we could try to minimize Pr(r(Y ) = 0|X = 1] which is called a false
negative subject to Pr(r(Y ) = 1|X = 0) ≤ β which is called a false positive.

Remark 21.3. 1. There are no priors

2. there are only two hypotheses

3. False negatives are far more critical than false positives.

Remark 21.4. False Positives are also known as type-I error, while false negatives are also known
as type-II errors. However, we will be following the notation found in Walrand’s textbook.

Recall our goal of maximizes PCD while minimizing PFA. This can be drawn as what is known as an
ROC curve (the reason for the name is historical, it’s just jargon). If β = 1, then we can just always guess
X̂ = 1, but we will have a lot of false alarms.

81
 The above figure illustrates that all valid decision rules must fall under the ROC curve. The optimal
decision rule, however, always falls on the ROC curve.

f (y|1)
Theorem 21.5 (Neyman-Pearson). Recall the Likelihood ratio L(y) = f (y|0) Then the optimal decision
rule is 
1 if L(Y ) > λ

∗
r (Y ) = 0 if L(y) < λ

1 w.p. γ if L(y) = λ


where λ > 0 and γ ∈ [0, 1] are chosen to make sure that

Pr(X̂ = 1|X = 0) = β

Intuitively, since we are allowed to err with probability β, we want to use all of this slack in order to
maximize our probability of correct detection. If L(y) is ”large” then we are declaring X̂ = 1, while otherwise
we guess zero. λ controls the “sensitivity” of your detector. We want to choose λ sensitive enough to just
meet the PFA constraint β.

Example 21.6 (Bias of a Coin). Let H0 correspond to the hypothesis that our coin is fair, while H1
corresponds to the hypothesis is biased to land heads 60% of the time. We observe Yi for the ith coin
toss, i = 1, ..., n. We would like the PFA = Pr(X̂ = 1|X = 0) ≤ 0.05. We have

Pr(Y1 = y1 , ..., Yn = yn |X = 0) = (0.5)n Pr(Y1 = y1 , ..., Yn = yn |X = 1) = (0.6)H (0.4)n−H

Then we have that
n  H
(0.6)H (0.4)n−H

0.4 0.6
L(Y1 , ..., Yn ) = =
(0.5)n 0.5 0.4
where H = number of heads observed. H is known in the business as a sufficient statistic for the
detection problem, because n is given and beyond that L only depends on H. The Neyman-Pearson
theorem says that (
1 H ≥ n0
X̂ =
0 H < n0
where Pr(H ≥ n0 |X = 0) = 0.05. We technically need to find a threshold on L(y), but since L(y)
depends monotonically on H, we can just equivalently find a threshold on H, which is intuitive and

82
also a lot easier in this particular problem. H ≥ n0 if and only if L(y) ≥ λ. Now all we have to
do is figure out what n0 is for a PFA of 5%. If X = 0, then H ∼ Binom(n, 21 ), so E[H] = n2 and
Var[H] = n4 . We are trying to bound the probability Pr(H ≥ n0 |X = 0), as this is exactly the PFA.
Here, we can use the CLT to argue that
!
H − E[H] n0 − E[H]
Pr(H ≥ n0 |X = 0) = Pr p ≥p
Var(H) Var(H)
!
n0 − n2
≈ Pr N (0, 1) ≥ p
n/4
!
n0 − n2
= 1 − Pr N (0, 1) < p = 0.05
n/4
n0 − n/2
=⇒ √ = Φ−1 (0.95) = 1.65
n/2
√
=⇒ n0 = 0.825 n + n/2
if n = 100, then we find that n0 = 58.25

Remark 21.7. In the above example, if the bias of the coin in our alternative hypothesis, then nothing
in our calculations at the end of the problem changes, and our cutoff n0 remains 58.25 for a 5% PFA.
However, the PCD will be different (namely, it will be significantly higher) for this different alternative
hypothesis. This phenomenon that a single rule works for a whole array of alternative hypotheses is
sometimes call the ”UMP rule” (uniformly most powerful).

83
22 Lecture 22: Wrapup of Hypothesis Testing and Beginning of LLSE
Agenda
1. Hypothesis Testing Wrapup (more examples and proof)
2. Estimation (Linear Least Squares Estimation (LLSE))

22.1 Proof of Neyman-Pearson

First, we show an example of why we might need a randomized rule (the case when L(y) = λ and we have
to “ring the alarm” (meaning guess X̂ = 1) with probability γ).
As slightly more motivation, Consider two hypotheses H0 and H1 , but we have no observation Y . Then our
decision is not a function but either r = 0 always or r is a random variable. If r = 0 is a constant then

Pr(X̂ = 1|X = 0) = 0 ≤ β

so our PFA is golden, but or PCD is terrible:

Pr(X̂ = 1|X = 1) = 0

The idea is we can choose r randomly, in particular we can set

(
1 w.p. β
r=
0 w.p. 1 − β

Then we have that the PFA = Pr(r = 1|X = 0) = Pr(r = 1) = β, and the PCD = Pr(r = 1|X = 1) = β
which is better than the other rule.
Now, we prove the Neyman-Pearson Theorem:
Proof. Consider a binary hypothesis testing problem. The idea of the proof is to show that any other decision
rule (other than Neyman-Pearson rule) having the same PFA spec β will not result in a better PCD. Let’s
denote X̃ as our alternate decision rule, and X̂ as our regular N-P decision rule. Mathematically, we would
like to show that if Pr(X̃ = 1|X = 0) ≤ β, then Pr(X̃ = 1|X = 1) ≤ Pr(X̂ = 1|X = 1). To do so we need
the following lemma:

Lemma 22.1.
(X̂ − X̃)(L(y) − λ) ≥ 0

Proof. if L(y) > λ, then X̂ = 1 which implies that X̂ − X̃ ≥ 0. Otherwise, if L(y) < λ, then X̂ = 0 which
implies X̂ − X̃ ≤ 0 and the inequality still holds. Finally, if L(y) = λ, then we get 0 ≥ 0.

If we expand the equation in the lemma, we get the equivalent:

X̂L(y) − X̃L(y) ≥ λX̂ − λX̃

Now, we take E[·|X = 0] on both sides of the above equation to get:

 
E[X̂L(y)|X = 0] − E[X̃L(Y )]|X = 0] ≥ λ E[X̂|X = 0] − E[X̃|X = 0]
 
= λ Pr(X̂ = 1|X = 0) − Pr(X̃ = 1|X = 0) ≥ 0

Here, we used the fact that λ > 0 and Pr(X̂ = 1|X = 0) = β while Pr(X̃ = 1|X = 0) ≤ β. So now we have
that
E[X̂L(y)|X = 0] ≥ E[X̃L(y)|X = 0]

84
Now, we have the LHS of the above equation is
Z
LHS = g(Y )L(y)fY |X (y|0)dy

fY |X (y|1)
Z
= g(y) fY |X (y|0)dy
fY |X (y|0)
Z
= g(y)fY |X (y|1)dy = E[X̂|X = 1] = Pr(X̂ = 1|X = 1) = P CD

Using very similar logic, we can show that the RHS is the PCD for the alternate decision rule. Then we
find that the N-P outperforms any other decision rule that satisfies the same specs!

22.2 Estimation
There are numerous applications involving needing to estimate quantities of interest.
1. Radar and Lidar
2. Multi-antenna wireless systems (MIMO systems: multiple input multiple output)
3. GPS
4. sensor networks
5. IoT (internet of things, every device has a sensor on it)
6. Machine Learning
Canonical Estimation Problem: You are given Y , and use your estimator produce an estimate X̂,
which we then compare to the actual value X to get some error in estimation ∆. Our goal is naturally to
estimate X for Y as accurately as possible, i.e. we want E[∆2 ] to be ”small”.

Definition 22.2. The LLSE (linear least-squares estimate) is an estimate where we constrain X̂ to
be a linear function of Y :
X̂ = a + bY

In the LLSE setting, we would like to minimize

E[(X − X̂(Y )2 )2 ]
We can also consider adding a quadratic term, i.e. allowing X̂ = a + bY + cY 2 . This would be the
QLSE (quadratic least-squares estimator). One can easily imagine adding more and more terms, and more
generally one can consider what is known as the MMSE, which is just the best function X̂(Y ), and not
constrained to be linear or even a polynomial, but we are getting ahead of ourselves.

For the moment, let’s assume we know the joint statistics of X and Y , and derive the LLSE. Recall our goal
is to minimize f (a, b) = E[(X − X̂)2 ] = E[(X − a − bY )2 ]
E[(X − a − bY )2 ] = E[X 2 + a2 + b2 Y 2 − 2aX + 2abY − 2bXY ]
Then we have
∂f
= 2a − 2 E[X] + 2b E[Y ] = 0
∂a
∂f
= 2b E[Y 2 ] + 2a E[Y ] − 2 E[XY ]
∂b
Solving these equations for a, b gives us our best linear estimate:
Cov(X, Y )
L[X|Y ] = a + bY = E[X] + [Y − E[Y ]]
Var(Y )

85
23 Lecture 23: Geometry of RV’s: LLSE and MMSE
Agenda:
1. Recap of LLSE
2. Hilbert Space of Random Variables
3. MMSE

Recall that The goal of LLSE is to estimate X as the most accurate linear function of Y :

L[X|Y ] = X̂ = a + bY

Last lecture we solved for a and b with calculus to find the LLSE formula:
Cov(X, Y )
L[X|Y ] = a + bY = E[X] + [Y − E[Y ]]
Var(Y )

23.1 Hilbert Spaces

Without getting too into the details, a Hilbert space is roughly a “complete inner product vector space”.
A vector space V has 0 ∈ V , is closed under addition, closed under scalar multiplication. For example Rn
is a Hilbert space. More details on the formulation can be found in the notes on the course website. An
inner product space is also equipped with an inner product h·, ·i : V × V → (0, ∞) which satisfies symmetry,
linearity, and positivity (if any of these words are not clear, just google the definition of an inner
p product or
read the notes). An inner product also always induces an norm k·k : V → (0, ∞) where kvk = hv, vi. Now,
the most important concept for our purposes will be that of an orthogonal projection onto a subspace.
Suppose we have some subspace U of our vector space. Then the orthogonal projection onto U is the map

P :V →U s.t. PU (y) := arg min ky − xk

x∈U

An orthogonal projection satisfies the properties that 1) PU (y) ∈ U and y − PU y ∈ U ⊥ . Here we have

ky − xk2 = ky − PU (y) + PU (y) − xk2 = ky − PU (y)k2 + 2hy − PU (y), PU (y) − xi + kPU (y) − xk2

Now we note that y − PU (y) ∈ U ⊥ and PU (y) − x ∈ U so therefore hy − PU (y), PU (y) − xi = 0. So then
we have
ky − xk2 = ky − PU (y)k2 + kPU (y) − xk2 ≥ ky − PU (y)k2
with equality if and only if x = PU (y)!

Recall the Gram-Schmidt process which is used to “orthogonalize” an arbitrary basis of vectors. Suppose
we have two vectors v1 and v2 and we would like to make them orthonormal while still spanning the same
space. Then we can do the following:
v1
1. Set u1 = kv1 k

2. set w2 = v2 − hv2 , u1 iu1

w2
3. set u2 = kw2 k

This process can easily be generalized to orthonormalize a general set of vectors.

86
23.2 Properties of LLSE
For convenience here is the LLSE again:

Cov(X, Y )
L[X|Y ] = a + bY = E[X] + [Y − E[Y ]]
Var(Y )

And here are some properties of it:

1. E[X̂] = E[X]
you should check this! Also this means that the LLSE is unbiased.

2. Projection Property: Cov(X − X̂, Y ) = Cov(∆, Y ) = 0

Exercise 23.1. verify this!

This means that the estimation error is uncorrelated with the observation.

Let’s rederive L[X|Y ] using geometry. To do so, we need to define the vector space perspective of random
variables:
Assume X, Y are zero-mean RVs with finite second moments. Then we have the following association of RVs
as a vector space:

RV X Geometry
random variable X a vector
RVs X and Y two vectors with an angle θ between them
E[XY ] hX, Y i = kXkkY k cos(θ)
E[XY ] = 0 θ = π2
E[X 2 ] 2
hX, Xi = kxk which is the norm of X
hX,Y i
ρ = √ E[XY
2
√] 2 kXkkY k = cos(θ)
E[X ] E[Y ]

Table 1: Correspondences between random variables and their geometry

Now we can derive L[X|Y ] geometrically. Our basis for the observation space Y is {1, Y }, where Y may
have nonzero mean. This means that the vector representation of 1 may not be orthogonal to Y . We would
like to project X onto this basis, but first it must be orthogonal! This is where Gram-Schmidt comes into
play. 1 as a vector is already a unit vector. Our orthonormal Y becomes

Y − hY, 1i
Ȳ =
kY − hY, 1ik

So {Ȳ , 1} is an orthonormal basis, so then

P{1,Ȳ } (X) = P{Ȳ } (X) + P{1} (X)

= hX, 1i · 1 + hX, Ȳ i · Ȳ
" #
X(Y − E[Y ]) (Y − E[Y ])
= E[X] + E p p
Var(Y ) Var(Y )
Cov(X, Y )
=⇒ L[X|Y ] = E[X] + (Y − E[Y ])
Var(Y )
Which is the answer we saw before!

87
Example 23.2. Let’s look at when X and Y are both zero mean. Consider the picture:

In the picture, we have flipped Y and X from our normal convention, but this builds character.
We have
hX, Y i E[XY ] Cov(X, Y )
L[Y |X] = bX = P rojY X = 2
X= 2
X= X
kXk E[X ] Var(X)
Which is exactly what we expected

Example 23.3. Suppose Y = αX + Z where X, Z are zero-mean. What is L[X|Y ]? We have

Cov(X, Y ) E[XY ]
L[X|Y ] = Y = Y
Var(Y ) E[X 2 ]

And we have
E[XY ] = E[X(αX + Z)] = α E[X 2 ] + E[XZ] = α E[X 2 ]
and
E[Y 2 ] = E[(αX + Z)2 ] = α E[X 2 ] + E[Z 2 ]
So finally, we have
α E[X 2 ] α−1 Y
L[X|Y ] = · Y =
α2 E[X 2 ] + E[Z 2 ] 1 + SN1 R
signal power α2 E[X 2 ]
where SNR stands for the signal to noise ratio and it is noise power = E[Z 2 ] Remarks:
1
1. If SNR  1, then L[X|Y ] ≈ α

2. If SNR  1, then L[X|Y ] ≈ 0

Both of these should make intuitive sense. We can also think about this problem geometrically:

88
 Now, we would like to find BE. But we can notive that the triangles BDE and BAC are similar
triangles! This implies that
BE BA
=
BD BC
BA · BD αkXkkXk
=⇒ BE = =⇒ bkY k =
BC kY k
αkXk2 α E[X 2 ]
=⇒ b = =
kY k2 α2 E[X 2 ] + E[Z 2 ]
Which is exactly the same as before, except this time we only used geometry!

A final remark before we end today: in the general LLSE problem with zero mean X and Y , we have

Error = E[(X − X̂)2 ] = E[∆2 ] = E[X 2 ] sin2 (θ)

= E[X 2 ](1 − cos2 (θ)) = E[X 2 ](1 − ρ2 )

Cov2 (X, Y )
 
= E[X 2 ] 1 −
E[X 2 ] E[Y 2 ]
Cov2 (X, Y ) Cov2 (X, Y )
= E[X 2 ] − = σx2 −
2
E[Y ] σY2
2
And we can notice that the above expression goes to σX as Cov(X, Y ) goes to zero. This makes intuitive
sense, as the less related X is to Y , the less information we can gain about X by observing Y , so our error
will remain nearly as large as our uncertainty about X.

89
24 Lecture 24: MMSE and Jointly Gaussian Random Variables
Agenda

1. Wrapup of LLSE/Geometry
2. Connection with Linear Regression
3. MMSE and its geometry
4. Jointly Gaussian Random Variables

24.1 Recap of LLSE

Recall that we derived the LLSE formula geometrically last time as the orthogonal projection. of X onto
the the subspace of linear functions of the form a + bY . We also saw that:
1. The LLSE is unbiased, meaning E[X̂] = E[X]
2. The estimation error ∆ is uncorrelated with Y , meaning Cov(∆, Y ) = E[∆Y ] = 0
We have the proof that the LLSE is optimal using our standard trick:
Proof. let g(Y ) = a + bY . Then we have

kX − g(Y )k2 = kX − L[X|Y ] + L[X|Y ] − g(Y )k2

= kX − L[X|Y ]k2 + 2hX − L[X|y], L[X|Y ] − g(Y )i + kL[X|Y ] − g(Y )k2

now note that X − L[X|y] = ∆, and furthermore L[X|Y ] − g(Y ) is some linear function of Y , so by our
second fact above, we have hX − L[X|y], L[X|Y ] − g(Y )i = 0. Then,

kX − g(Y )k2 = kX − L[X|Y ]k2 + kL[X|Y ] − g(Y )k2 ≥ kX − L[X|Y ]k2

which tells us that the LLSE is our best linear estimator

We have derived all of this in the scalar case, but it is important to note that all of this holds essentially
in the case when X and Y are vectors as well. In particular, we have:

L[X|Y ] = E[X] + Cov(X, Y )Σ−1

Y (Y − E[Y ])

Where ΣY = E[(Y − E[Y ])(Y − E[Y ])T ] and Cov(X, Y ) = E[(X − E[X])(Y − E[Y ])T ].
The details can be found in Walrand. But it looks almost exactly the same as the scalar case!

Remark 24.1. So far, we have assumed a Bayesian framework, assuming complete knowledge of our
joint distribution of X and Y . If we take a non-probabilistic ”data-driven” perspective, then this just
becomes linear regression.

• We assume we have access to samples {(x1 , y1 ), ..., (xk , yk )}

• Goal: construct g(Y ) = a + bY such that
k
1X
E(a, b) = |xi − a − byi |2
k i=1

To solve this, we take the partial derivatives of E wrt a and b and set them equal to zero. This
is a good exercise, and you will find that we get the the same exact formula as we have previously
derived! The only difference is that the means, variances, and covariance will be replaced with the

90
 empirical means, variance, and covariance. This means that by the strong law of large numbers, that
linear regression converges to the LLSE.

24.2 MMSE Estimation

Once again the goal is to minimize E[(X − X̂(Y ))2 ], but now X̂(Y ) can be any function of Y .
Intuition: Suppose we don’t even observe Y . What is the MMSE estimate of X given nothing? Well it
should be E[X]! If this is not convincing enough, you can show that

arg min E[(X − c)2 ] = E[X]

c

What if Y is given? The natural extension would be to guess that M M SE[X|Y ] = X̂(Y ) = E[X|Y ]

In the above picture, the red line represents a kind of ”center of mass” of the blob given some observation
y. If we are given y in the above picture, then x could be any of the values inside the striped bar, but we
choose the one that intersects with the center of mass line.

Before, we performed an orthogonal projection onto the space spanned by Y and 1 to get the LLSE of X
given Y . Now, intuitively, we are projecting onto the space of all possible functions of Y , rather than just
linear ones. We would like to show that E[X|Y ] is indeed this orthogonal projection.

Theorem 24.2. The MMSE of X given Y is given by

g(Y ) = E[X|Y ]

Lemma 24.3. 1. for all functions ϕ(·),

E[(X − E[X|Y ])ϕ(Y )] = 0

This means that our projection is indeed orthogonal!

91
 2. If there exists a function g(Y ) such that

E[(X − g(Y ))ϕ(Y )] = 0

for all ϕ(·), then g(Y ) = E[X|Y ]

Together, these two claims mean that the orthogonal projection is both optimal and unique.

Proof. 1. We would like to show that E[∆ϕ(Y )] = 0 for all ϕ

⇔ E[Xϕ(Y )] = E[E[X|Y ]ϕ(Y )]

But this is immediate as we have

E[E[X|Y ]ϕ(Y )] = E[E[ϕ(Y )X|Y ]] = E[ϕ(Y )X]

Where we have used the fact that ϕ(Y ) can be treated as a constant when Y is given, and then we
have used iterated expectation.
2. For the proof of this see Walrand, but it is just algebra

Now we can prove the theorem:

Proof. The idea of the proof is the same as in the LLSE case. We have:

E[|X − h(Y )|2 ] = E[|X − E[X|Y ] + E[X|Y ] − h(Y )|2 ]

= E[|X − E[X|Y ]|2 ] + E[| E[X|Y ] − h(Y )|2 ] + 2 E[(X − E[X|Y ])(E[X|Y ] − h(Y ))]
Again, we note that X − E[X|Y ] = ∆ is our error term, and that E[X|Y ] − h(Y ) is just some function of Y .
By the lemma, ∆ is orthogonal to any function of Y so the term 2 E[(X − E[X|Y ])(E[X|Y ] − h(Y ))] = 0
and we have

E[|X − h(Y )|2 ] = E[|X − E[X|Y ]|2 ] + E[| E[X|Y ] − h(Y )|2 ] ≥ E[|X − E[X|Y ]|2 ]

with equality iff h(Y ) = E[X|Y ].

Consider the following picture (which can be found in Walrand) for intuition:

92
The above picture is highlighting that the set of linear estimators is just a small subspace of all possible
estimators. In general, it does not happen that M M SE[X|Y ] equals the L[X|Y ]. However, it does sometimes
happen, and when it does happen this means that the best possible estimator of X given Y is a linear function.

Example 24.4. Suppose we know that Y is uniformly distributed between -1 and 1, and we are told
that X = Y 2 . Then is it clear that E[X|Y ] = E[Y 2 |Y ] = Y 2 and this is the MMSE. However,

E[XY ]
L[X|Y ] = E[X] + Y
E[Y 2 ]
1
But E[XY ] = E[Y 3 ] = 0 so L[X|Y ] = E[X] = 3. In this case it is clear that the LLSE and the
MMSE do not coincide.

Example 24.5. Suppose X, Y are i.i.d. RVs and you observe X + Y and we want to estimate X given
X + Y . We have by symmetry (since X and Y are indistinguishable RVs

E[X|X + Y ] = E[Y |X + Y ]

but we also know that E[X + Y |X + Y ] = X + Y , so then it is clear by linearity of expectations that

X +Y
E[X|X + Y ] =
2
Note that this is a special case when the LLSE and MMSE collide, i.e. that the MMSE is linear.

24.3 Jointly Gaussian RVs

We will start with a very important theorem:

Theorem 24.6. If X and Y are jointly gaussian random variables, then

L[X|Y ] = E[X|Y ]

First, we have to define what jointly gaussian means

Definition 24.7 (Jointly Gaussian RVs). Let f (X1 , X2 ) be the joint pdf of X1 and X2 . If f (X1 , X2 )
is such that
α1 X1 + α2 X2 ∼ Normal pdf
for all α1 , α2 ∈ R. Alternatively, X1 and X2 are said to be JG RVs if every linear combination
α1 X1 + α2 X2 is a normal pdf.

As a fun bonus, we also prove the law of total variance (from way back in the beginning of the course)
geometrically:

Remark 24.8 (Geometric interpretation of the Law of Total Variance). First, we perform some manip-
ulation that will be useful later:

E[Var(X|Y )] = E[E[(X − E[X|Y ])2 |Y ]]

= E[(X − E[X|Y ])2 ]

= Var(X − E[X|Y ])
Now we will see that the law of total variance is simply an expression of the pythagorean theorem!

93
Consider:

Var(X) = E[Var(X|Y )] + Var(E[X|Y ]) = Var(X − E[X|Y ]) + Var(E[X|Y ])

In the geometric representation of RVs, E[X|Y ] is as we know a projection of X onto the space of
functions of Y . Then, we have that Var(X) is the square of the length of X (which is the standard
deviation), and Var(X − E[X|Y ]) + Var(E[X|Y ]) (which are orthogonal by the definition of the
MMSE) is the sum of the squares of the lengths of the two vectors that add to form X.

94
25 Lecture 25: Jointly Gaussian Random Variables and Scalar Kalman
Filter
Agenda:

1. Jointly Gaussian RVs

2. Orthogonal Updates and Kalman Filters

25.1 Jointly Gaussian RVs

Recall that we see at the end of last lecture that:

Theorem 25.1. If X and Y are jointly gaussian random variables, then

L[X|Y ] = E[X|Y ]

First, we have to define what jointly gaussian means

Definition 25.2 (Jointly Gaussian RVs). Let f (X1 , X2 ) be the joint pdf of X1 and X2 . If f (X1 , X2 )
is such that
α1 X1 + α2 X2 ∼ Normal pdf
for all α1 , α2 ∈ R. Alternatively, X1 and X2 are said to be JG RVs if every linear combination
α1 X1 + α2 X2 has a normal pdf.

There is a completely equivalent definition that goes as follows. Y1 , ...., Yn are considered Jointly Gaus-
sian if  
Y1
 Y2 
Y = . 
 
 .. 
Yn
has a multivariate normal pdf, which we will define below.

Definition 25.3. A random vector Y ∼ N (µY , ΣY ) is JG with mean µy and covariance matrix ΣY if

Y = AX + µY

Where ΣY = AAT and X ∼ N (0, I) so X is a just a vector of independent standard gaussians.

Here the covariance matrix ΣY describes the pairwise covariance between every element of the vector Y .
It is easy to see then that ΣY is a symmetric matrix, since (ΣY )i,j = Cov(Yi , Yj ) = Cov(Yj , Yi ) = (ΣY )j,i .
Here we can compute the covariance matrix Var(Y ) = ΣY as follows:

Var(Y ) = E[(Y − µY )(Y − µY )T ] = E[AX(AX)T ] = A E[XX T ]AT = AAT

Since E[XX > ] = I since X is a standard multivariate normal distribution.

Example 25.4. for n = 2, suppose

    
Y1 1 2 X1
Y = =
Y2 1 −1 X2
| {z }
A

95
Then we can compute  
5 −1
ΣY = AA> =
−1 2

Theorem 25.5. If Y ∼ N (µY , ΣY ) then its pdf is given by

 
1 1
fY (y) = p exp − (Y − µY )T Σ−1
Y (Y − µY )
(2π)n/2 det(ΣY ) 2

Note: the level curves of this joint pdf are ellipses, and we will see some pictures of this later. The
level curves are the set of y’s that give fY (y) = c for some constant c.

Example 25.6. Again, we suppose n = 2, and furthermore suppose Y1 and Y2 are uncorrelated. Then
we have:     
Y σ 0 X1
Y = 1 = 1
Y2 0 σ2 X2
| {z }
A

Then we also have

 2
1/σ12
  
σ 0 0
ΣY = AA = 1>
and Σ−1 =
0 σ22 Y 0 1/σ22

Now plugging into our pdf for the multivariate gaussian we have
1  1 
fY (y1 , y2 ) = exp − Y > Σ−1
Y Y
(2π)n/2 σ 1 σ2 | 2 {z }
h i
− 21 y12 /σ12 +y22 /σ22

 1  −y 2  1  −y 2 
1 2
= √ exp 2
√ exp = fY1 (y1 )fY2 (y2 )
2πσ1 2σ1 2πσ2 2σ22
The above calculations show that Y1 and Y2 are actually independent! This is quite remarkable,
because we only assumed that they were uncorrelated in the beginning of this example, and recall
that in general two random variables being uncorrelated does not necessarily mean that they are
independent. But in the case of jointly gaussian random variables, it does!

The above example essentially proves (a special case of) the following very important lemma:

Lemma 25.7. If Y1 and Y2 are uncorrelated and jointly gaussian, then they are also independent.

Remark 25.8. This is not super important, but we discuss here intuitively why the level sets of
gaussians are ellipses. To do so, we just look at the 2-D case. Recall if Y1 and Y2 are uncorrelated
(and therefore also independent), then we have

1  1 h y2 y 2 i
1
fY (y1 , y2 ) = exp − 2 + 22
(2π)n/2 σ 1 σ2 2 σ1 σ2
Then clearly level sets for this function correspond to solutions to the equation:
y12 y2
2 + 22 = c
2σ1 2σ2

96
 For the case when σ1 = σ2 , the above equation just corresponds to a circle in the y1 , y2 plane. If on
the other hand σ12 = 2σ22 , then the equation corresponds to an ellipse with its longer axis along the
y1 axis. An analogous phenonmenon occurs when σ22 = 2σ12 .
The more complicated case is when we don’t actually assume that Y1 and Y2 are uncorrelated. For
example, if we assume as in the example above that
 
5 −1
ΣY =
−1 2

Then we can compute (with some work not shown) the pdf of Y as
1  −1 
fY (y) = exp Y > Σ−1
Y Y
2π · 3 | 2 {z }
h 2 2
i
2y1 −2y1 y2 +5y2
− 18

Now, the equation in the exponent (if we complete the square a couple times) is
 y − a 2  y − a 2
1 1 2 2
+ =c
b1 b2
Which if we set equal to some constant c, is just the equation for a rotated ellipse in the y1 , y2 plane.
Moreover, the axes for this rotated ellipse are given by the eigenvectors of the inverse covariance
matrix Σ−1
Y , but this is getting way out of scope.

Recall the first definition of JG random variables. (X1 , ..., Xn ) are JG if and only if α1 X1 + ... + αn Xn
is a univariate normal for everal value of α1 , ..., αn ∈ R.

Example 25.9. Suppose X, Y ∼ N (0, 1) i.i.d. RV’s. Let Z = X + Y and W = X − Y . Are Z and W
independent or not?
We have

Cov(Z, W ) = E[ZW ] − E[Z] E[W ] = E[(X + Y )(X − Y )] = E[X 2 ] − E[Y 2 ] = 0

Which means that Z and W are uncorrelated. However, they are also jointly gaussian, so by the
lemma they are independent! This can be nicely visualized/proven geometrically:

In the above figure, we have plotted X and Y geometrically in the hilbert space of random variables we
introduced earlier. Note that they are orthogonal by definition. Furthermore, not that the triangles
(0, X, Z) and (0, X, W ) are similar iscoceles triangles. These two facts tell us that the angle between
Z and W must be 90 degrees, which means Z and W must also be orthogonal.

Remark 25.10. Linear combinations of JG RVs are still JG. This follows directly from the definition
of jointly gaussian.

97
 Example 25.11. Let (
1 w.p. 1/2
W =
−1 w.p. 1/2
And we let X ∼ N (0, 1) and X, W are independent. We set Y = W X
Question 1: are X and Y uncorrelated?
We have E[XY ] = E[X 2 W ] = E[X 2 ] E[W ] = 0, so yes.
Question 2: What is the distribution of Y ?
By symmetry, Y ∼ N (0, 1)
Question 3: Are X and Y independent?
Clearly Y = W X is not indepedendent of x.
So what is going on here? Doesn’t this contradict our lemma?
Question 4: Are X and Y jointly gaussian?
Consider (
2X w.p. 1/2
Z =X +Y =
0 w.p. 1/2
Which is not gaussian so we cannot apply the lemma, so there is no contradiction above.

Now, we probably the most important theorem from today’s lecture:

Theorem 25.12. If X and Y are jointly gaussian, then E[X|Y ] = L[X|Y ].

Recall:
1. If (X, Y ) are JG, then all linear combinations of X and Y are jointly gaussian.

2. If (X, Y ) are JG and uncorrelated, then X, Y are independent

Proof. 1. First, we know that X − L[X|Y ] ⊥ Y by the projection property of LLSE.
2. If (X, Y ) are JG so are linear combinations of X, Y , namely (X − L[X|Y ]) and Y .

3. Now, we can conclude that X − L[X|Y ] and Y must be independent, by the lemma.
4. This implies that X − L[X|Y ] and ϕ(Y ) are independent for all functions ϕ(·).
5. This implies that X − L[X|Y ] is orthogonal to ϕ(Y ) (since independence implies uncorrelated.)
6. This means that L[X|Y ] must be our MMSE estimate E[X|Y ], since X − E[X|Y ] is unique and must
be orthogonal to every function of Y .

25.2 Kalman Filter

In general, there are many different forms of inference that pop up in the literature/real life settings:

1. Filtering: Filtering is done in real time, for example tracking position in real time. We are trying to
guess X̂ given a sequence of observations Y1 , ..., Yn
2. Prediction: We are given T observations Y1 , ..., YT and we are trying to predict what we will observe
in the future, i.e. YTi , i = 1, 2, .... This is a lot of machine learning and can be used for radar tracking,
stock market predictions, predictive coding (speech, image, video, etc.).
3. Smoothing: Infer X̂t for t ≤ T given observations Y1 , ..., YT . This is offline (which is the biggest
difference between smoothing and filtering), i.e. inferring the cause of a car crash by post processing
a video.

98
 4. Max Likelihood State Estimation (MLSE) Given Y0 , ..., YT , we want to output the most likely
possible sequence of states X̂0 , ..., X̂T . The big difference between this and smoothing is we are trying
to get the entire sequence, not just one particular timestep. Examples of this include the convolutional
coding (the Viterbi algorithm), auto-correct, and speech recognition.
The Kalman Filter is of course a filtering algorithm to update the estimate of the state X(n) or Xn of
a system. The system has a state X(n) and an observation (or output) Y (n) at time n = 0, 1, ... according
to the State Space Equations:
X(n + 1) = AX(n) + V (n)
Y (N ) = CX(n) + W (n)
In the above equations, there is sometimes an optional control input BU (n) added to the equation for
X(n + 1), but we won’t consider that case in this class. Here, W (n) and V (n) are some zero mean and
orthogonal noise terms. We denote the Cov(Vn ) = ΣV and Cov(Wn ) = ΣW .
The objective of the kalman filter is to estimate X̂ = L[X(n)|Y (0), ..., Y (n)]

Theorem 25.13 (Kalman Filter).

 
X̂n|n = AX̂n−1|n−1 + kn Yn − CAX̂n−1|n−1 (1)
h i−1
kn = Σn|n−1 C > CΣn|n−1 C > + ΣW (2)
Σn|n−1 = AΣn−1|n−1 + ΣV (3)
Σn|n = (I − kn C)Σn|n−1 (4)

where
• ΣW = Cov(Wn )

• ΣV = Cov(Vn )
• Σn|n−1 = Cov(Xn − AX̂n−1|n−1 )
| {z }
∆n|n−1

• Σn|n = Cov(Xn − X̂n|n )

| {z }
∆n|n

Don’t worry if the above notations and equations don’t make much sense yet. We haven’t explained a
lot of it, we are just stating it above for the general vector case. Next lecture, we will derive the scalar case
geometrically, which looks entirely analogous to the vector case and should hopefully provide some much
needed intuition about what is going on with the Kalman filter.

99
26 Lecture 26: Kalman Filter
Agenda:
1. Recap of Kalman Filter setup
2. Orthogonal Updates
3. Derivation of the scalar Kalman filter using geometry.
In the scalar case, our state-space equations are as follows:

Xn = aXn−1 + Vn−1

Yn = cXn + Wn
However, we note here that without loss of generality, we can divide the second equation by c which
yields the equation Yn /c = Xn + Wn /c. This can be though of as just a different observation with a different
noise on the Xn variable, so from now on WLOG we just set c = 1 and our equations are:

Xn = aXn−1 + Vn−1

Yn = Xn + Wn
Recall that the objective of a kalman filter is to estimate our state at time n, Xn in an online fashion using
our observations Y1 , ..., Yn . Our estimate, since we are in Gaussian land, will be X̂n = L[Xn |Yn , ..., Y1 ]. Lets
recall some notation:
• X̂n|n = L[Xn |Y1 , ..., Yn ] is our estimate of Xn at time n

• Similarly, X̂n|n−1 = L[Xn |Y1 , ..., Yn−1 ] is the LLSE estimate of Xn at time n − 1.

• ∆n|n = Xn − X̂n|n

• ∆n|n−1 = Xn − X̂n|n−1
• E[∆2n|n ] = σn|n
2

• E[∆2n|n−1 ] = σn|n−1
2

• E[Vn2 ] = σV2
• E[Wn2 ] = σW
2

26.1 Orthogonal Updates

Recall when we were looking at the LLSE the following lemma:

Lemma 26.1. If X, Y, Z are zero-mean and E[Y Z] = 0 (so Y is orthogonal to Z), then

L[X|Y, Z] = L[X|Y ] + L[X|Z]

However, this only works if Y, Z are orthogonal. For the general case, we have the following theorem:

Theorem 26.2. Again suppose X, Y, Z are zero-mean, but this time, Y and Z could be correlated.
We have
L[X|Y, Z] = L[X|Y ] + L[X|Z̃]
Where Z̃ = Z − ProjY Z = Z − L[Z|Y ]

100
Proof. The key here is to just note that Z̃ is orthogonal to Y , so we can just apply the previous lemma.
Now, we are going to give an outline of the kalman filter. The kalman filter is a recursive way of updating
estimates based on prediction and update (after observing the new sample point), one sample at a time.
Recursively estimate Xn given Y n = Y1 , ...., Yn by first finding L[Xn |Y1 , ..., Yn−1 ] at time n − 1, and then
updating the estimate based on the new observation Yn at time n. Specifically, we have

L[ Xn | Y1 , ..., Yn−1 , Yn ] = L[ Xn | Y1 , ..., Yn−1 ] + L[ Xn | Ỹn ]

|{z} | {z } |{z} |{z} | {z } |{z} |{z}
X Y Z X Y X Z̃

Where we have drawn the an analogy to the lemma above. Here Y˜n = Yn − L[Yn |Y1 , ..., Yn−1 ]. Here, Y˜n
represents the innovative part of our latest observation. It is the component of the latest observation that
is orthogonal to all of our previous observations, so it represents new information. Below, we highlight the
”predict then update” logic of the Kalman Filter:

predict update
observe Y2
z }| { z }| {
L[X1 |Y1 ] −−−−−−−→ L[X2 |Y1 , Y2 ] = L[X2 |Y1 ] + L[X2 |Ỹ2 ]
predict update
observe Y3
z }| { z }| {
−−−−−−−→ L[X3 |Y1 , Y2 , Y3 ] = L[X3 |Y1 , Y2 ] + L[X3 |Ỹ3 ]
observe Y
4
−−−−−−−→ ···

With these tools, we are now ready to geometrically derive the scalar Kalman Filter

26.2 Scalar Derivation of Kalman filter

In the scalar case, our state space equations look like:

Xn = aXn−1 + Vn

Yn = Xn + Wn
and we have the Kalman update equations:

X̂n|n = X̂n|n−1 + kn (Yn − X̂n|n−1 ) (5)

2
σn|n−1
kn = 2 2 (6)
σn|n−1 + σW
2
σn|n−1 = a2 σn−1|n−1
2
+ σV2 (7)
2 2
σn|n = (1 − kn )σn|n−1 (8)

Let’s derive these equations in the scalar case. Note that after time n − 1, we know X̂n−1|n−1 and
2 2
σn−1|n−1 . Then, at time n, we get Yn , and we do some updates to get X̂n|n and σn|n . We can derive the
first equation algebraically:

X̂n|n = L[Xn |Y1 , ..., Yn ] = L[Xn |Y1 , ..., Yn−1 ] + L[Xn |Yn − L[Yn |Y1 , ..., Yn−1 ]]

Which, letting Y (n) = Y1 , ..., Y can be concisely written as

X̂n|n = L[Xn |Y (n) ] = L[Xn |Y (n−1) ] + L[Xn |Yn − L[Yn |Y (n−1) ]]

= X̂n|n−1 + L[Xn |Ỹn ] = X̂n|n−1 + kn Ỹn

101
We can also very easily derive X̂n|n−1 algebraically, so we will do that now:

X̂n|n−1 = L[Xn |Y1 , ..., Yn−1 ]

= L[aXn−1 + Vn |Y1 , ..., Yn−1 ]
= aL[Xn−1 |Y1 , ..., Yn−1 ] + L[Vn |Y1 , ..., Yn−1 ]
= aX̂n−1|n−1

Where in the last step we have used the fact that Vn is orthogonal zero-mean noise. Lastly, we note that

Ỹn = Yn − L[Yn |Y (n−1) ]

= Yn − L[Xn + Wn |Y (n−1) ]
= Yn − L[Xn |Y (n−1) ] − L[Wn |Y (n−1) ]
= Yn − X̂n|n−1

Now, we are ready to examine some geometry to derive the remaining equations. To start doing this, consider
the diagram below:

Try to think of the above diagram as kind of like a laptop which is at 90 degrees. The triangle
(x̂n|n−1 , xn , yn ) forms a plan which is orthogonal to the rectangle containing the origin at the bottom of
the figure. There are a plethora of other things to notice about the above diagram.
• Note first that X̂n|n−1 is orthogonal to (Xn − X̂n|n−1 ). This is because X̂n|n−1 is the orthogonal
projection of Xn onto the subspace spanned by Y1 , ..., Yn−1 .
• Ỹn is orthogonal to X̂n|n−1 . This is becauses Ỹn must be orthogonal to the subspace spanned by
Y1 , ..., Yn−1 , and as we mentioned already, X̂n|n−1 lives in that subspace.

• kn Ỹn is the orthogonal projection of Xn onto Ỹn . This is a little harder to see given the way the
diagram is drawn (there are a lot of right angles in this diagram and it is hard to draw them all so
that they actually look like right angles)
• Wn is orthogonal to everything, but in particular it is orthogonal to Xn , as denoted in the diagram.
We would like to figure out what kn actually is based on this picture. To do this, we note that the triangles
(x̂n|n−1 , x̂n|n , xn ) and (xn , x̂n|n , yn ) and (x̂n|n−1 , xn , yn ) are all similar triangles. This means in particular
that
kkn Ỹn k k∆n|n−1 k
=
k∆n|n−1 k kỸn k

102
Where ∆n|n−1 = Xn − X̂n|n−1 is the line segment connecting xn and X̂n|n−1 in the above diagram. Rear-
ranging, we can see that
2 2
∆n|n−1 σn|n−1
kn = 2 = 2 2
σn|n−1 + σw
Ỹn
2 2 2
Where in the last line we have used the pythagorean theorem to argue that Ỹn = ∆n|n−1 + kWn k .
Finally, we can verify the last equation by once again using similar triangles to note that:

∆2n|n kWn k (1 − kn )Ỹn

= =
∆2n|n−1 Ỹn kWn k
2
∆2n|n kWn k (1 − kn ) Ỹn
=⇒ 2 =
∆2n|n−1 Ỹn kWn k
2 2
=⇒ σn|n = (1 − kn )σn|n−1

This is exactly what we wanted! For the last of the equations, we examine the following diagram:

First, we note that (xn , axn−1 , x̂n|n−1 ) is a right triangle. We also note that (0, x̂n|n−1 , axn−1 ) and
(0, x̂n−1|n−1 , xn−1 ) are similar triangles. This implies that

axn−1 − x̂n|n−1 = a ∆n−1|n−1

We further have since Vn−1 is orthogonal to axn−1 − x̂n|n−1 that by the pythagorean theorem:
2 2 2
∆n|n−1 = a∆n−1|n−1 + kVn k
2
=⇒ σn|n−1 = a2 σn−1|n−1
2
+ σV2
Which is exactly what we wanted! This was the last equation we have to verify, and so we are done. We have
proved the scalar Kalman Filter entirely geometrically! The vector versions are just direct generalizations
of the scalar equations, but they do not have such a nice geometric interpretation and must be derived
algebraically.
Some final remarks:

103
 2
1. At iteration n, the algorithm has inputs X̂n|n−1 , σn−1|n−1 and new observation Yn , and outputs
2
X̂n|n , σn|n for the next time step to use.
2 2
2. the kalman gain kn and the errors σn|n−1 and σn|n can be pre-computed, because they do not depend
on the X and Y ! Only X̂n|n needs to be computed in real time.
3. This algorithm is easy to implement (just a few lines of code are required).

4. If Vn and Wn are Gaussians, then the Kalman filter is also giving us the MMSE estimate!
In the example below we highlight how we can precompute these variances without even seeing any data,
and how often these variances converge to a ”steady state”

Example 26.3. Suppose

a
z}|{ N (0,1)
1 z}|{
Xn = √ Xn−1 + Vn
2
Yn = |{z}
2 Xn + Wn
|{z}
c N (0,1)

Then we have from our Kalman filter equations:

2
2σn|n−1
kn = 2 (9)
4σn|n−1 +1
2 1 2
σn|n−1 = σ +1 (10)
2 n−1|n−1
2
2 2
σn|n−1
σn|n = σn|n−1 (1 − 2kn ) = 2 (11)
4σn|n−1 + 1

2
1. When n = 0, we have X̂0|0 = 0 and σ0|0 = E[X02 ] = 2, since σX
2
= 12 σX
2 2
+ σV2 =⇒ σX = 2σV2 =
2.

2. When n = 1, we can compute

2 1 2
σ1|0 = σ +1=2
2 0|0
2
2σ1|0
k1 = 2 +1 = 4/9 = 0.444
4σ1|0
2 2
σ1|1 = σ1|0 (1 − 2k1 ) = 2/9 = 0.222
2
3. repeating this for n = 2, we find that σ2|2 = 0.204
2
4. Similarly for n = 3, we find σ2|2 = 0.204. We seem to have converged!

Indeed, if we take an analytical approach to the steady-state solution, using the equations we can
derive
1 2
2 2 σn−1|n−1 + 1
σn|n = 2
2σn−1|n−1 +5
2 2 2
and then using the fact that in steady state, σn|n = σn−1|n−1 to solve for limn→∞ σn|n and we find
that it equals 0.2037. Which had basically already achieved by time step n = 3!

104
27 Extra Content: Hidden Markov Models
In Kalman Filtering, we are given a sequence of observations coming at us in order Y1 , ..., Yn and we would
like to come up with the most accurate prediction for our current actual state, Xˆn , in real time. However,
In many applications, such as autocorrect or speech recognition, we may want to actually guess the best
estimate for our state at all time steps X̂1 , ..., Xˆn . This is, as we mentioned awhile back, known as MLSE,
or Maximum Likelihood State Estimation. In this note we explore Hidden Markov Models, which are a
way to model the underlying relationship between the true states and our observations. Formally, we have
the following definition:

Definition 27.1. A Hidden Markov Model is a random sequence {(X(n), Y (n)); n ≥ 0} such that
X(n) ∈ X = {1, ..., N } and Y (n) ∈ Y = {1, ..., M }.
Here X and Y are simply our state and observation spaces, respectively. Here we also assume that
our states X(i) are characterized by a state transition matrix P with some initial distribution π0 .
The state observation model Q tells us that when we are in state x ∈ X , we observe y ∈ Y with
probability Q(x, y).

Below we have a nice visualization of an HMM. It represents an HMM that has been running for T
time steps. The probabilities of the next states we visit is characterized by P , while the probabilities of the
observations we see given our current state are characterized by our state observation model Q.

P P P P
Markov process: X1 X2 X3 ... XT

Q Q Q Q

Observations: Y1 Y2 Y3 ··· YT

Figure 1: An example hidden markov chain that has run for T time steps.

In the context of speech recognition, the Xn may be segments of sentences or words, while the Yn are
sounds or something similar. Note that in this model, we are assuming that each successive state is only
dependent on the previous state, and that each observation is only dependent on the current state. The
structure of the language itself determines the relationship between the states Xi , while the relationship
between Xi and Yi can be speaker dependent. Our problem is as follows: suppose we have observed Yn :=
(Y0 , ..., Yn ) = yn = (y0 , ..., yn ). What is the most likely sequence Xn that explains these observations?
Formally, we want to find
M AP [Xn |Yn = yn ]
which is the same as finding the sequence xn ∈ X n+1 that maximizes

Pr[Xn = xn ∩ Yn = yn ]
Pr[Xn = xn |Yn = yn ] =
Pr[Yn = yn ]

Maximizing this expression is equivalent to maximizing the numerator. Now, from the definition of a the
hidden markov model (which encodes our assumptions about the system), we have by applying Bayes rule
multiple times along with the properties of Markov chains for n = 1:

Pr[x0 , x1 , y0 , y1 ]

= Pr[y1 |x0 , x1 , y0 ] Pr[x1 |x0 , y0 ] Pr[y0 |x0 ] Pr[x0 ]

= Pr[x0 ] Pr[y0 |x0 ] Pr[x1 |x0 ] Pr[y1 |x1 ] = π0 (x0 )Q(x0 , y0 )P (x0 , x1 )Q(y1 , x1 )

105
where in the last step we have substituted P and Q for our probabilities using the model we have set up.
Extending this, it is not too hard to see then that

arg max Pr[Xn = xn |Yn = yn ]

xn ∈X n+1
h i
= arg n
max
n+1
π (x
0 0 )Q(x ,
0 0y )P (x 0 , x1 )Q(y1 , x1 ) · · · P (x n−1 , xn )Q(y n , xn )
x ∈X

Now, since logarithms are monotonic, we can equivalently minimize the negative log of the above expres-
sion. This may seem mysterious at first, but actually has a very nice interpretation.

arg max Pr[Xn = xn |Yn = yn ]

xn ∈X n+1

h n
X i
= arg max log(π (x
0 0 )Q(x ,
0 0y )) + log(P (x m−1 , xm )Q(x ,
m my ))
xn ∈X n+1 | {z } m=1 | {z }
−d0 (x0 ) −dm (xm−1 ,xm )

h n
X i
= arg n
min
n+1
d0 (x0 ) + dm (xm−1 , xm )
x ∈X
m=1

Above we have define these terms as −di since they are logs of probabilities, so in this way the di will be
positive. This in turn lends itself very nicely to the interpretation of the above expression as a graph, known
in this setting as a trellis diagram.

t=1 t=2 t=3

s1 s1 s1

s2 s2 s2

s3 s3 s3

s4 s4 s4

y1 y2 y2

Figure 2: Trellis of the observation sequence y1 ,y2 ,y2 for the above HMM. The thick arrows indicate the
most probable transitions. As an example, the transition between state s1 at time t=2 and state s4 at time
t=3 has probability α2 (1)a14 b4 (y2 ), where αt (i) is the probability to be in state si at time t.

106
28 Extra Content: Expectation Maximization

107