1 of 77

Information Theory

Chris Gregg

CS109, Stanford University

Autumn 2026

2 of 77

Learning Goals

  1. Calculate information gain
  2. Make choices that maximize information gain
  3. Numerically score how similar two distributions are

3 of 77

Uncertainty Theory

3

Beta Distributions

Adding Random Vars

Central Limit Theorem

Sampling

Algorithmic Analysis

Thompson Sampling

Bootstrapping

​

Information Theory

4 of 77

4

WorldeBot

Decision Trees

Value of Info in Poker

Adaptive Tests

Comparing Distributions

Compression of Data

5 of 77

Four Prototypical Trajectories

Review

6 of 77

Expectation

6

All the values that X can take on

The probability that X takes on that value

7 of 77

Limitation of Expectation

7

X = time to complete the medical diagnosis problem (in seconds)

Summarize the distribution in one number

8 of 77

Expectation of a Function

8

Law of unconscious statistician

So for example…

9 of 77

9

Def: Law of Total Expectation

10 of 77

Four Prototypical Trajectories

End Review

11 of 77

Plot Line

11

  1. We want to chose questions in think of an animal (Let X be the animal random var)

​

  1. Idea! Select the question which most reduces our “uncertainty” in X

​

  1. We can measure “uncertainty” as “expected amount of surprise when we find out X”

​

  1. We can measure “surprise” in an assignment as log 1/P(X=x)

​

  1. This measure of uncertainty of X is super helpful for lots of problems!

12 of 77

Four Prototypical Trajectories

I am thinking of an animal…

13 of 77

13

14 of 77

I am thinking of an animal

14

15 of 77

I am Celeste is thinking of an animal

15

16 of 77

Four Prototypical Trajectories

What is the best question to ask?

17 of 77

Question Choosing Algorithms

17

Hey what’s that?

18 of 77

Which Question is Better?

18

Is it a pet?

Is it a Dog?

19 of 77

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

20 of 77

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

21 of 77

Which Question is Better?

21

Can you “score” how bad each of these PMFs are?

22 of 77

Which Question is Better?

22

Can you “score” how bad each of these PMFs are?

uncertain

23 of 77

Four Prototypical Trajectories

What we really need is a measure of our uncertainty in a random variable

24 of 77

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

25 of 77

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

26 of 77

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 of 77

27

Four Prototypical Trajectories

Ok, but then what is our measure of Surprise?

28 of 77

Surprise of an Event

28

High probability events are not surprising

Low probability events are surprising

Relationship should be monotonic

29 of 77

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

30 of 77

Surprise of an Event, I(E)

30

I(E) stands for “Information Content” aka

“Surprisal” aka

“Self-Information”

31 of 77

Surprise of an Event, I(X = x)

31

I(X = x) stands for “Information Content” aka

“Surprisal” aka

“Self-Information”

32 of 77

Four Prototypical Trajectories

Back to the measure of uncertainty in the outcome of a random variable

33 of 77

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

34 of 77

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

35 of 77

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

36 of 77

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

37 of 77

Four Prototypical Trajectories

Back to

I am thinking of an animal…

38 of 77

Which Question is Better?

38

no

p = 0.77

39 of 77

Which Question is Better?

39

no

p = 0.77

40 of 77

Which Question is Better?

40

no

p = 0.77

41 of 77

Which Question is Better?

41

no

p = 0.77

42 of 77

Which Question is Better?

42

no

p = 0.77

43 of 77

Which Question is Better?

43

no

p = 0.77

44 of 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

45 of 77

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

46 of 77

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

47 of 77

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

48 of 77

Why this?

​

​

​

​

​

​

​

D and

Which Question is Better? Example 2

48

49 of 77

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

50 of 77

So, we compute the average remaining uncertainty weighted by the probabilities of the branches:

​

​

​

​

​

​

  • Before the question: 2 bits
  • Expected remaining entropy after 1 question: 1 bit
  • Information gained: 1 bit

Which Question is Better? Example 2

50

51 of 77

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

52 of 77

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

53 of 77

Why this?

​

​

​

​

​

​

The animals are equally likely, so

Which Question is Better? Example 2

53

54 of 77

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

55 of 77

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

56 of 77

Four Prototypical Trajectories

To the code!

57 of 77

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

58 of 77

Four Prototypical Trajectories

Traffic Predictions Over Time

59 of 77

Should You Wait to Plan Your Route?

59

Prediction 1 day in advance

Prediction 30 mins in advance

60 of 77

Should You Wait to Plan Your Route?

60

Prediction 1 day in advance

Prediction 30 mins in advance

61 of 77

Should You Wait to Plan Your Route?

61

Prediction 1 day in advance

Prediction 30 mins in advance

62 of 77

Should You Wait to Plan Your Route?

62

Prediction 1 day in advance

Prediction 30 mins in advance

63 of 77

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)

64 of 77

Four Prototypical Trajectories

Limitations of Entropy for Decision Making?

65 of 77

65

WorldeBot

Decision Trees

Value of Info in Poker

Adaptive Tests

Comparing Distributions

Compression of Data

66 of 77

Four Prototypical Trajectories

Distance Between Two Distributions

67 of 77

67

Recall this

68 of 77

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

69 of 77

KL Divergence Without Tears

69

How much more surprising is x under Y than X?

70 of 77

KL Divergence Without Tears

How much more surprising is x under Y than X?

Surprise according to?

71 of 77

KL Divergence Without Tears

How much more surprising is x under Y than X?

Surprise according to?

Surprise!

72 of 77

KL Divergence Without Tears

How much more surprising is x under Y than X?

Surprise according to?

Surprise!

1/x = x-1

73 of 77

KL Divergence Without Tears

How much more surprising is x under Y than X?

Surprise according to?

Surprise!

1/x = x-1

Log rules

74 of 77

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

75 of 77

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

76 of 77

WorldeBot

Decision Trees

Value of Info in Poker

Adaptive Tests

Comparing Distributions

Compression of Data

77 of 77

Where are we in CS109?

77

On Friday…