Information Theory
Chris Gregg
CS109, Stanford University
Autumn 2026
Learning Goals
Uncertainty Theory
3
Beta Distributions
Adding Random Vars
Central Limit Theorem
Sampling
Algorithmic Analysis
Thompson Sampling
Bootstrapping
Information Theory
4
WorldeBot
Decision Trees
Value of Info in Poker
Adaptive Tests
Comparing Distributions
Compression of Data
Four Prototypical Trajectories
Review
Expectation
6
All the values that X can take on
The probability that X takes on that value
Limitation of Expectation
7
X = time to complete the medical diagnosis problem (in seconds)
Summarize the distribution in one number
Expectation of a Function
8
Law of unconscious statistician
So for example…
9
Def: Law of Total Expectation
Four Prototypical Trajectories
End Review
Plot Line
11
Four Prototypical Trajectories
I am thinking of an animal…
13
I am thinking of an animal
14
I am Celeste is thinking of an animal
15
Four Prototypical Trajectories
What is the best question to ask?
Question Choosing Algorithms
17
Hey what’s that?
Which Question is Better?
18
Is it a pet?
Is it a Dog?
Which Question is Better?
19
Is it a pet?
Is it a Dog?
no
p = 0.56
yes
p = 0.44
no
p = 0.77
yes
p = 0.23
Which Question is Better?
20
Is it a pet?
Is it a Dog?
no
p = 0.56
yes
p = 0.44
no
p = 0.77
yes
p = 0.23
Which Question is Better?
21
Can you “score” how bad each of these PMFs are?
Which Question is Better?
22
Can you “score” how bad each of these PMFs are?
uncertain
Four Prototypical Trajectories
What we really need is a measure of our uncertainty in a random variable
Uncertainty of a Random Variable
24
Let X be any random variable. We can calculate a statistic, “Uncertainty” to express how much we don’t know about X
Low uncertainty
High uncertainty
Uncertainty of a Random Variable
25
Let X be any random variable. We can calculate a statistic, “Uncertainty” to express how much we don’t know about X
Expected “Surprise” when I observe X
Low uncertainty
High uncertainty
Uncertainty of a Random Variable
26
Uncertainty is expected Surprise
Let X be any random variable. We can calculate a statistic, “Uncertainty” to express how much we don’t know about X
Low uncertainty
High uncertainty
27
Four Prototypical Trajectories
Ok, but then what is our measure of Surprise?
Surprise of an Event
28
High probability events are not surprising
Low probability events are surprising
Relationship should be monotonic
Surprise of an Event
29
Here are three reasonable options
Probability of event, P(E)
High probability events are not surprising
Low probability events are surprising
Relationship should be monotonic
Surprise of an Event, I(E)
30
I(E) stands for “Information Content” aka
“Surprisal” aka
“Self-Information”
Surprise of an Event, I(X = x)
31
I(X = x) stands for “Information Content” aka
“Surprisal” aka
“Self-Information”
Four Prototypical Trajectories
Back to the measure of uncertainty in the outcome of a random variable
Uncertainty of a Random Variable
33
Let X be any random variable. We can calculate a statistic, “Uncertainty” to express how much we don’t know about X
Low uncertainty
High uncertainty
Uncertainty is expected Surprise
Uncertainty of a Random Variable
34
Uncertainty is expected Surprise
Let X be any random variable. We can calculate a statistic, “Uncertainty” to express how much we don’t know about X
Uncertainty of a Random Variable
35
Let X be any random variable. We can calculate a statistic, “Uncertainty” to express how much we don’t know about X
Uncertainty is expected Surprise
Our favorite measure of Surprise
1/x is the same as x-1
Log of a power (here -1)
Pull the negative out
Uncertainty of a Random Variable
36
Let X be any random variable. We can calculate a statistic, “Uncertainty” to express how much we don’t know about X
My preferred name for ”entropy” aka H(X)
Calculates expected surprise
Four Prototypical Trajectories
Back to
I am thinking of an animal…
Which Question is Better?
38
no
p = 0.77
Which Question is Better?
39
no
p = 0.77
Which Question is Better?
40
no
p = 0.77
Which Question is Better?
41
no
p = 0.77
Which Question is Better?
42
no
p = 0.77
Which Question is Better?
43
no
p = 0.77
Which Question is Better? Example 2
Suppose your possible animals are: Cat, Dog, Eagle, Shark, and assume each is equally likely.
Before asking anything, H(X) = 2 bits because there are 4 equally likely possibilities.
44
Suppose your possible animals are: Cat, Dog, Eagle, Shark, and assume each is equally likely.
Before asking anything, H(X) = 2 bits because there are 4 equally likely possibilities.
Now, we ask the question: “Does the animal have fur?”
The answers partition the animals:
Yes: {Cat, Dog}
No: {Eagle, Shark}
Which Question is Better? Example 2
45
Now, we ask the question: “Does the animal have fur?”
The answers partition the animals:
Yes: {Cat, Dog}
No: {Eagle, Shark}
You do not yet know whether the answer will be “yes” or “no, but you do know the probabilities:
Which Question is Better? Example 2
46
Now, we imagine each outcome separately:
If the answer is “yes”: we have {Cat, Dog}, and the remaining entropy is
because there are 2 equally likely animals left.
Which Question is Better? Example 2
47
Why this?
D and
Which Question is Better? Example 2
48
Now, we imagine each outcome separately:
If the answer is “no”: we have {Eagle, Shark}, and the remaining entropy is also:
because there are 2 equally likely animals left.
Which Question is Better? Example 2
49
So, we compute the average remaining uncertainty weighted by the probabilities of the branches:
Which Question is Better? Example 2
50
Suppose your possible animals are: Cat, Dog, Eagle, Shark, and assume each is equally likely.
Before asking anything, H(X) = 2 bits because there are 4 equally likely possibilities.
Next, we ask the question: “Does the animal live underwater?”
The answers partition the animals:
Yes: {Shark}
No: {Cat, Dog, Eagle}
Which Question is Better? Example 2
51
Next, we ask the question: “Does the animal live underwater?”
The answers partition the animals:
Yes: {Shark}
No: {Cat, Dog, Eagle}
Probabilities:
Entropies: (the animal is completely identified)
Which Question is Better? Example 2
52
Why this?
The animals are equally likely, so
Which Question is Better? Example 2
53
Expected remaining entropy:
Because this is larger than 1 bit (from the “fur” question), this question is words.
Big idea: Before asking the question, the answer itself is random, so the remaining entropy after asking is also random. So, we evaluate a question by its expected remaining entropy.
Which Question is Better? Example 2
54
Uncertainty (aka Entropy) in code
55
def calc_uncertainty(pmf):
# this calculates the entropy of the distribution
# aka the uncertainty
uncertainty = 0
for x in pmf:
p_x = pmf[x]
# skip zero probabilities
if p_x == 0: continue
surprise_x = np.log2(1/p_x)
uncertainty += surprise_x * p_x
return uncertainty
Uncertainty of X
Surprise(x)
Expected Surprise
Four Prototypical Trajectories
To the code!
Four Prototypical Trajectories
Entropy in the sum of two dice.
What is more informative:
I tell you that the sum is odd
I tell you the value of the first dice is 1
Four Prototypical Trajectories
Traffic Predictions Over Time
Should You Wait to Plan Your Route?
59
Prediction 1 day in advance
Prediction 30 mins in advance
Should You Wait to Plan Your Route?
60
Prediction 1 day in advance
Prediction 30 mins in advance
Should You Wait to Plan Your Route?
61
Prediction 1 day in advance
Prediction 30 mins in advance
Should You Wait to Plan Your Route?
62
Prediction 1 day in advance
Prediction 30 mins in advance
Should You Wait to Plan Your Route?
63
Hours you wait until you plan
Let X be the amount of time to drive from SF to Stanford
Uncertainty in X, H(X)
Four Prototypical Trajectories
Limitations of Entropy for Decision Making?
65
WorldeBot
Decision Trees
Value of Info in Poker
Adaptive Tests
Comparing Distributions
Compression of Data
Four Prototypical Trajectories
Distance Between Two Distributions
67
Recall this
Distance Between Two Distributions
68
Total Variation (TV)
Earth Movers (EMD)
Loop over all possible values and calculate the absolute difference in probability
Imagine one distribution is a lump of dirt. How much work would it take to make it look just like the other?
Solved using a Linear Program Solver
Kullback Leibler (KL)
Expected excess surprise from using Y as a model instead of X when the actual distribution is X.
Three reasonable ideas
Let real data be Y
Let poisson prediction be X
KL Divergence Without Tears
69
How much more surprising is x under Y than X?
KL Divergence Without Tears
How much more surprising is x under Y than X?
Surprise according to?
KL Divergence Without Tears
How much more surprising is x under Y than X?
Surprise according to?
Surprise!
KL Divergence Without Tears
How much more surprising is x under Y than X?
Surprise according to?
Surprise!
1/x = x-1
KL Divergence Without Tears
How much more surprising is x under Y than X?
Surprise according to?
Surprise!
1/x = x-1
Log rules
KL Divergence Without Tears
How much more surprising is x under Y than X?
Surprise according to?
Surprise!
1/x = x-1
Log rules
People often use natural log
KL Divergence in Code
from scipy import stats
import math
�def kl_divergence(predicted_lambda, observed_pmf):
"""
We predicted that the number of hurricanes would be
X ~ Poisson(predicted_lambda) and observed a real world
number of hurricanes Y ~ observed_pmf
"""
X = stats.poisson(predicted_lambda)
divergence = 0
# loop over all the values of hurricanes
for i in range(0, 40):
pr_X_i = X.pmf(i)
pr_Y_i = observed_pmf[i]
excess_surprise_i = math.log(pr_X_i / pr_Y_i)
divergence += excess_surprise_i * pr_X_i
return divergence
Let real data be Y
Let poisson prediction be X
WorldeBot
Decision Trees
Value of Info in Poker
Adaptive Tests
Comparing Distributions
Compression of Data
Where are we in CS109?
77
On Friday…