Multinomial

Chris Gregg

CS109, Stanford University

Summer 2026

Exciting Day!

2

Chris Piech, CS109

Who wrote Federalist Paper 53?

3

madison.txt

hamilton.txt

unknown.txt

Chris Piech, CS109

4

First, some review

Chris Piech, CS109

Recall the good times

5

Chris Piech, CS109

How Many Ways Are There to Order…

6

(H, H, H, H, T, T, T, T, T, T)

(H, H, H, T, H, T, T, T, T, T)

(H, H, H, T, T, H, T, T, T, T)

(H, H, H, T, T, T, H, T, T, T)

(H, H, H, T, T, T, T, H, T, T)

(H, H, H, T, T, T, T, T, H, T)

(H, H, H, T, T, T, T, T, T, H)

(H, H, T, H, H, T, T, T, T, T)

(H, H, T, H, T, H, T, T, T, T)

(H, H, T, H, T, T, H, T, T, T)

(H, H, T, H, T, T, T, H, T, T)

(H, H, T, H, T, T, T, T, H, T)

(H, H, T, H, T, T, T, T, T, H)

(H, H, T, T, H, H, T, T, T, T)

(H, H, T, T, H, T, H, T, T, T)

(H, H, T, T, H, T, T, H, T, T)

(H, H, T, T, H, T, T, T, H, T)

(H, H, T, T, H, T, T, T, T, H)

(H, H, T, T, T, H, H, T, T, T)

(H, H, T, T, T, H, T, H, T, T)

(H, H, T, T, T, H, T, T, H, T)

(H, H, T, T, T, H, T, T, T, H)

(H, H, T, T, T, T, H, H, T, T)

(H, H, T, T, T, T, H, T, H, T)

4 heads and 6 tails?

Chris Piech, CS109

How Many Ways Are There to Order…

7

(H, H, H, H, T, T, T, T, T, T)

(H, H, H, T, H, T, T, T, T, T)

(H, H, H, T, T, H, T, T, T, T)

(H, H, H, T, T, T, H, T, T, T)

(H, H, H, T, T, T, T, H, T, T)

(H, H, H, T, T, T, T, T, H, T)

(H, H, H, T, T, T, T, T, T, H)

(H, H, T, H, H, T, T, T, T, T)

(H, H, T, H, T, H, T, T, T, T)

(H, H, T, H, T, T, H, T, T, T)

(H, H, T, H, T, T, T, H, T, T)

(H, H, T, H, T, T, T, T, H, T)

(H, H, T, H, T, T, T, T, T, H)

(H, H, T, T, H, H, T, T, T, T)

(H, H, T, T, H, T, H, T, T, T)

(H, H, T, T, H, T, T, H, T, T)

(H, H, T, T, H, T, T, T, H, T)

(H, H, T, T, H, T, T, T, T, H)

(H, H, T, T, T, H, H, T, T, T)

(H, H, T, T, T, H, T, H, T, T)

(H, H, T, T, T, H, T, T, H, T)

(H, H, T, T, T, H, T, T, T, H)

(H, H, T, T, T, T, H, H, T, T)

(H, H, T, T, T, T, H, T, H, T)

4 heads and 6 tails?

Chris Piech, CS109

How Many Ways Are There to Order…

8

3 As, 5 Bs and 2Cs

Chris Piech, CS109

How Many Ways Are There to Order…

9

3 As, 5 Bs and 2Cs

Chris Piech, CS109

How Many Ways Are There to Order…

10

3 As, 5 Bs and 2Cs

Chris Piech, CS109

Counting unordered objects

11

Multinomials generalize Binomials for counting.

How many ways are there�to order n heads

and (n-k) tails

Called the binomial coefficient�because of something from Algebra

How many ways are there�to order n₁ outcomes of type 1

n₂ outcomes of type 2

n₃ outcomes of type 3…

n_r outcomes of type r

Binomial coefficient

Multinomial coefficient

Chris Piech, CS109

Where are we in CS109?

12

Chris Piech, CS109

Today: Compare and Contrast Many Examples

13

Age from C14

Updated Delivery Prob

Age from Name

Hidden Chambers

Stanford Eye Test

Updating Lidar Belief

Chris Piech, CS109

Joint Table for 3 Random Variables?

14

D is disease, S is can smell, F is fever status

Chris Piech, CS109

Joint Table for 3 Random Variables?

15

D is disease, S is can smell, F is fever status

Chris Piech, CS109

Joint Table for 10 Random Variables?

16

Imagine you have 10 discrete RVs which can each take on 5 values

# unique assignments

Chris Piech, CS109

Joint Table for 10 Random Variables?

17

Imagine you have 10 discrete RVs which can each take on 5 values

# unique assignments

Chris Piech, CS109

Joint Table for 10 Random Variables?

​

​

• 10 million entries in your joint table.

​

• So, we are going to need models …

​

• … probabilistic models …

18

Imagine you have 10 discrete RVs which can each take on 5 values

# unique assignments

Chris Piech, CS109

Joint Table for 10 Random Variables?

​

​

• 10 million entries in your joint table.

​

• So, we are going to need models …

​

• … probabilistic models …

19

Imagine you have 10 discrete RVs which can each take on 5 values

# unique assignments

Chris Piech, CS109

Joint Table for 10 Random Variables?

​

​

• 10 million entries in your joint table.

​

• So, we are going to need models …

​

• … probabilistic models …

20

Imagine you have 10 discrete RVs which can each take on 5 values

# unique assignments

Chris Piech, CS109

Multiple Random Variables. Start of Digital Revolution

21

Chris Piech, CS109

22

Cousin 1

Cousin 2

?

Parent 1

Parent 2

?

?

Grand Parent 1

?

Grand Parent 2

?

Spouse 1

?

Spouse 2

?

You observe that someone has a recessive gene.

What is the probability that their cousin has the same recessive gene?

Four Prototypical Trajectories

Roll 100 dice.

X₁ = How many 1s?

X₂ = How many 2s?

X₃ = How many 3s?

X₄ = How many 4s?

X₅ = How many 5s?

X₆ = How many 6s?

How big is the joint table?

Chris Piech, CS109

Four Prototypical Trajectories

Sometimes the structure of the variables suggests a more efficient representation

Chris Piech, CS109

Multinomial RV

25

Chris Piech, CS109

Probability

26

Binomial RV

Multinomial RV

Chris Piech, CS109

Probability

27

Binomial RV

Multinomial RV

Chris Piech, CS109

Probability

28

Binomial RV

Multinomial RV

Chris Piech, CS109

Probability

29

Binomial RV

Binomial # of ways of ordering the successes

Multinomial RV

Chris Piech, CS109

Probability

30

Binomial RV

Binomial # of ways of ordering the successes

Multinomial RV

Chris Piech, CS109

Probability

31

Multinomial RVs generalize Binomial RVs

Binomial RV

Binomial # of ways of ordering the successes

Multinomial RV

Chris Piech, CS109

Recall the Binomial Derivation: What if more than two outcomes?

32

Chris Piech, CS109

Three Outcomes A, B, C

33

What is the probability of exactly 4 As, 1 B and 5 Cs?

Chris Piech, CS109

Multinomial Random Variable?

34

Joint PMF

where

and

Probability of each ordering is equal + mutually exclusive

Chris Piech, CS109

Multinomial Random Variable?

35

Joint PMF

where

and

Multinomial # of ways of ordering the outcomes

Probability of each ordering is equal + mutually exclusive

Chris Piech, CS109

Four Prototypical Trajectories

Sometimes the structure of the variables suggests a more efficient representation

Chris Piech, CS109

Four Prototypical Trajectories

I roll 6 dice. What is more probable:

1. I roll 6 “sixes”

B) I roll exactly one of each number

Chris Piech, CS109

Hello dice rolls, my old friends

• A 6-sided die is rolled 7 times.
• What is the probability of getting:

38

• 1 one
• 1 two

• 0 threes
• 2 fours

• 0 fives
• 3 sixes

🤔

Chris Piech, CS109

Hello dice rolls, my old friends

• A 6-sided die is rolled 7 times.
• What is the probability of getting:

39

• 1 one
• 1 two

• 0 threes
• 2 fours

• 0 fives
• 3 sixes

Chris Piech, CS109

Hello dice rolls, my old friends

• A 6-sided die is rolled 7 times.
• What is the probability of getting:

40

• 1 one
• 1 two

• 0 threes
• 2 fours

• 0 fives
• 3 sixes

Chris Piech, CS109

Hello dice rolls, my old friends

• A 6-sided die is rolled 7 times.
• What is the probability of getting:

41

• 1 one
• 1 two

• 0 threes
• 2 fours

• 0 fives
• 3 sixes

Chris Piech, CS109

Hello dice rolls, my old friends

• A 6-sided die is rolled 7 times.
• What is the probability of getting:

42

• 1 one
• 1 two

• 0 threes
• 2 fours

• 0 fives
• 3 sixes

# of times�a six appears

Chris Piech, CS109

Hello dice rolls, my old friends

• A 6-sided die is rolled 7 times.
• What is the probability of getting:

43

• 1 one
• 1 two

• 0 threes
• 2 fours

• 0 fives
• 3 sixes

# of times�a six appears

choose where�the sixes appear

Chris Piech, CS109

Hello dice rolls, my old friends

• A 6-sided die is rolled 7 times.
• What is the probability of getting:

44

• 1 one
• 1 two

• 0 threes
• 2 fours

• 0 fives
• 3 sixes

# of times�a six appears

probability�of rolling a six

choose where�the sixes appear

Chris Piech, CS109

Hello dice rolls, my old friends

• A 6-sided die is rolled 7 times.
• What is the probability of getting:

45

• 1 one
• 1 two

• 0 threes
• 2 fours

• 0 fives
• 3 sixes

# of times�a six appears

probability�of rolling a six

choose where�the sixes appear

this many times

Chris Piech, CS109

Parameters of a Multinomial RV?

46

Chris Piech, CS109

Most useful when probabilities are not equal

47

Chris Piech, CS109

Most useful when probabilities are not equal

48

You have a funny shaped six-sided die with the following probabilities:

• P(1) = 0.2, P(2) = 0.3
• P(3) = 0.1, P(4) = 0.1
• P(5) = 0.1, P(6) = 0.2

You roll the die 6 times.

What is the probability of getting exactly: two 2s, two 4s, and two 6s?

Chris Piech, CS109

The Federalist Papers

49

Chris Piech, CS109

Four Prototypical Trajectories

Intro to Natural Language Processing

Chris Piech, CS109

51

Dear Professor Piech. Can you help me? I have a large amount of money in my dorm room, but I can’t get it out. If you sent me a $500 coupa card I could distract my TA and pay you back double.

Sam Smith

60%

60%

40%

1

2

Let E be the entire email text. Let F be the event the email is Spam.

3

string_pr(f"This email is spam: {email}")

string_pr(f"This email is spam: ")

email

Chris Piech, CS109

52

string_pr(f"This email is spam: {email}")

string_pr(f"This email is spam: ")

email

spam

"This email is spam: Pay for drugs"

The token at index 1 is “this”

Chris Piech, CS109

53

string_pr(f"This email is spam: {email}")

string_pr(f"This email is spam: ")

email

spam

"This email is spam: Pay for drugs"

The token at index 1 is “this”

Chris Piech, CS109

54

string_pr(f"This email is spam: {email}")

string_pr(f"This email is spam: ")

email

spam

"This email is spam: Pay for drugs"

The token at index 1 is “this”

Chris Piech, CS109

55

string_pr(f"This email is spam: {email}")

string_pr(f"This email is spam: ")

email

spam

"This email is spam: Pay for drugs"

The token at index 1 is “this”

drugs

Chris Piech, CS109

Four Prototypical Trajectories

We are going to contrast that to an older (but cheaper) method…

Chris Piech, CS109

Four Prototypical Trajectories

Before 2021…

Chris Piech, CS109

Probabilistic text analysis

58

Chris Piech, CS109

Probabilistic text analysis

59

Chris Piech, CS109

Probabilistic text analysis

60

👈

Chris Piech, CS109

Probabilistic text analysis

61

👈

A document is a large multinomial.

(according to the Global Language Monitor,�there are 988,968 words in the English language used on the internet.)

Chris Piech, CS109

Model text as a multinomial

62

Chris Piech, CS109

Model text as a multinomial

Example document:

“Pay for drugs with a credit-card. drugs is great. So are credit-cards. Risk free drugs. Click for free.”

n = 18

63

Chris Piech, CS109

Model text as a multinomial

Example document:

“Pay for drugs with a credit-card. drugs is great. So are credit-cards. Risk free drugs. Click for free.”

n = 18

64

drugs = 3

Free = 2

Risk = 1

Credit-card: 2

…

For = 2

Chris Piech, CS109

Model text as a multinomial

Example document:

“Pay for drugs with a credit-card. drugs is great. So are credit-cards. Risk free drugs. Click for free.”

n = 18

65

drugs = 3

Free = 2

Risk = 1

Credit-card: 2

…

For = 2

Probability of seeing this document | spam

Chris Piech, CS109

Model text as a multinomial

Example document:

“Pay for drugs with a credit-card. drugs is great. So are credit-cards. Risk free drugs. Click for free.”

n = 18

66

drugs = 3

Free = 2

Risk = 1

Credit-card: 2

…

For = 2

Probability of seeing this document | spam

It’s a Multinomial!

Chris Piech, CS109

Model text as a multinomial

Example document:

“Pay for drugs with a credit-card. drugs is great. So are credit-cards. Risk free drugs. Click for free.”

n = 18

67

drugs = 3

Free = 2

Risk = 1

Credit-card: 2

…

For = 2

Probability of seeing this document | spam

It’s a Multinomial!

The probability of a word in spam email being drugs

Chris Piech, CS109

Four Prototypical Trajectories

Who wrote the federalist papers?

Old and New Analysis

70

Chris Piech, CS109

Old and New Analysis

• Authorship of the Federalist Papers
• 85 essays advocating ratification�of the US constitution
• Written under the pseudonym “Publius”�(really, Alexander Hamilton, James Madison, John Jay)
• ​

71

Chris Piech, CS109

Old and New Analysis

• Authorship of the Federalist Papers
• 85 essays advocating ratification�of the US constitution
• Written under the pseudonym “Publius”�(really, Alexander Hamilton, James Madison, John Jay)
• Who wrote which essays?
• Analyze probability of words in each essay and compare against word distributions from known writings of three authors

72

Chris Piech, CS109

Who wrote Federalist Paper 53?

73

madison.txt

hamilton.txt

unknown.txt

Chris Piech, CS109

Where to start?

• We have words, we want to know probability of authorship. We also know probability of words given author…

74

Chris Piech, CS109

Where to start?

• We have words, we want to know probability of authorship. We also know probability of words given author…

75

Well hello again…

Chris Piech, CS109

Who wrote Federalist Paper 53?

76

Prob Hamilton given

Document

Prob Document given Hamilton

Prior belief it was Hamilton

Prob of the document???

Chris Piech, CS109

Who wrote Federalist Paper 53?

77

Model document as a multinomial where we care about count of words

Chris Piech, CS109

Who wrote Federalist Paper 53?

78

Prob hamilton would write word i

Number of times word i is in the doc

Loop over unique words

Chris Piech, CS109

Who wrote Federalist Paper 53?

79

Prob Hamilton given

Document

Prob hamilton would write word i

Prior belief it was Hamilton

Prob of the document???

Number of times word i is in the doc

Loop over unique words

Chris Piech, CS109

Who wrote Federalist Paper 53?

80

Prob that Hamilton wrote it

Prob that Madison wrote it

Chris Piech, CS109

Who wrote Federalist Paper 53?

81

Prob that Hamilton wrote it

Prob that Madison wrote it

Chris Piech, CS109

To the code

82

Chris Piech, CS109

83

What happened?

Chris Piech, CS109

All our probabilities are zero…

84

Chris Piech, CS109

Log Review

85

Chris Piech, CS109

Log Identities

86

Chris Piech, CS109

Products become sums!

87

Chris Piech, CS109

Products become sums!

88

* Spoiler alert: This is important because the product of many small numbers gets hard for computers to represent.

Chris Piech, CS109

Use logs when probabilities become too small!

89

Number of times word i shows up in the doc

Hamilton wrote it

Maddison wrote it

The doc

h_i = Prob Hamilton writes word i

m_i = Prob Maddison writes word i

Chris Piech, CS109

Use logs when probabilities become too small!

90

Number of times word i shows up in the doc

Hamilton wrote it

Maddison wrote it

The doc

h_i = Prob Hamilton writes word i

m_i = Prob Maddison writes word i

Chris Piech, CS109

What does it mean if a log value is positive / negative

91

If a log is positive, its input was > 1

If a log is negative, its input was between 0 and 1

Chris Piech, CS109

Use logs when probabilities become too small!

92

Hamilton Term -12925

Madison Term -11581

Chris Piech, CS109

Use logs when probabilities become too small!

93

Hamilton Term -12925

Madison Term -11581

Chris Piech, CS109

Use logs when probabilities become too small!

94

Hamilton Term -12925

Madison Term -11581

Chris Piech, CS109

Four Prototypical Trajectories

Madison wrote it!

Chris Piech, CS109

Four Prototypical Trajectories

Practice: Midterm question from last year

Chris Piech, CS109

Midterm Question

97

Chris Piech, CS109

Midterm Question (Winter 2025)

98

Chris Piech, CS109