🌏 中文版
Video status: Recordings require sign-in or course authorization. Source details
This is article 14 in Reading Stanford CS109, covering Summer 2026 Lecture 13: Multinomial on July 14 with Chris Gregg. Its Summer agenda follows the worksheet, answer key, LLM Learning Guide, and shared Spring-dated reader chapters on the Multinomial and Federalist Papers. The Canvas recording is inaccessible, so spoken material is not reconstructed.
The worksheet and answer key are both complete two-page P1–P6 plus challenge artifacts. The LLM guide displays a third page, but it contains only a carried-over closing sentence and page number—not a seventh concept or additional agenda item.
P1: Review inference with a two-node network
The network is Overloaded→Slow, with P(Overloaded=1)=0.1, P(Slow=1|Overloaded=1)=0.95, and P(Slow=1|Overloaded=0)=0.2. Thus
P(Overloaded=1,Slow=0)=0.1×0.05=0.005The Slow marginal is 0.95(0.1)+0.2(0.9)=0.275, giving
P(Overloaded=1|Slow=1)
= 0.095/0.275 = 19/55 ≈ 0.345Rejection sampling would retain only Slow=1 joint samples and report the fraction with Overloaded=1. This reconnects factorization, Bayes, and sampling in one small model.
P2: Count orderings with repeated types
A 12-position DNA fragment has four A, three C, two G, and three T nucleotides. Starting from 12!, swaps among identical bases do not create new sequences, so
C(12;4,3,2,3)
= 12!/(4!3!2!3!)
= 277,200When each position independently chooses among four bases uniformly, one specific sequence has probability (1/4)^12. Summing all mutually exclusive sequences with the target counts gives
P(counts 4,3,2,3)
= 277,200(1/4)^12
≈ 0.0165This exposes the Multinomial PMF's structure: the probability of one ordering times the number of orderings with the same counts.
P3: A Load Balancing joint PMF
Ten requests independently route to three data centers with probabilities 0.5, 0.3, and 0.2. For counts (X1,X2,X3),
(X1,X2,X3) ~ Multinomial(10;0.5,0.3,0.2)
P(X1=c1,X2=c2,X3=c3)
= 10!/(c1!c2!c3!) × 0.5^c1 0.3^c2 0.2^c3The PMF applies to nonnegative counts satisfying c1+c2+c3=10. For (5,3,2),
10!/(5!3!2!) × 0.5^5 0.3^3 0.2^2
≈ 0.0851A Multinomial requires a fixed number of independent trials, exactly one category per trial, and unchanged category probabilities. Drawing cards without replacement violates both independence and constant probabilities.
P4: Loot Boxes and a Binomial marginal
Eight loot boxes have common, rare, and legendary probabilities 0.6, 0.3, and 0.1. Exactly (4,3,1) occurs with probability
8!/(4!3!1!) × 0.6^4 0.3^3 0.1
≈ 0.0980Looking only at the legendary count recolors categories into “legendary” and “everything else”:
Xlegendary ~ Bin(8,0.1)
P(Xlegendary=1)=C(8,1)0.1(0.9)^7≈0.383Generally, each Xi~Bin(n,pi). Different category counts are not independent because they must sum to fixed n; an extra outcome in one category reduces the total available to others.
P5: A large Midterm Rooms expression
Three hundred students independently enter rooms with probabilities 0.3, 0.2, and 0.5. Exactly (90,60,150) has probability
300!/(90!60!150!) × 0.3^90 0.2^60 0.5^150The worksheet permits an unevaluated expression; the key gives approximately 0.00306. Direct factorials and tiny powers risk overflow and underflow, foreshadowing P6's log computation.
P6: Bag-of-words authorship inference
An anonymous pamphlet has counts upon:2, whilst:1, and commerce:3, with equal priors on authors H and M. Under bag of words,
P(H|doc) ∝ P(H) × ∏i P(word_i|H)^n_iThe Multinomial coefficient depends only on document counts, so it is identical for H and M and cancels. Unshown words with identical probabilities under both authors also contribute only shared factors.
Multiplying thousands of tiny values underflows to floating-point zero. Logs use log(ab)=log a+log b and log(a^n)=n log a, turning a product into a stable sum. Since log is increasing, the ranking is unchanged:
H: 2ln(0.005)+ln(0.0001)+3ln(0.002) ≈ -38.45
M: 2ln(0.0005)+ln(0.001)+3ln(0.003) ≈ -39.54H has the larger, less negative log-score. Their difference is about 1.09, so the likelihood ratio is e^1.09≈3: H is roughly three times as likely as M.
Challenge: The Multinomial contains the Binomial
With r=2, set X1=k, X2=n-k, and p2=1-p1:
P(X1=k,X2=n-k)
= n!/[k!(n-k)!] × p1^k(1-p1)^(n-k)
= C(n,k)p1^k(1-p1)^(n-k)This is exactly the Bin(n,p1) PMF. For general r, recolor each trial as “type i” or “anything else.” The success probability becomes pi, proving directly that Xi~Bin(n,pi) without summing over all other category counts.
How to use the LLM Learning Guide
The six guide concepts are the Multinomial coefficient, joint PMF, applicability assumptions, Binomial marginals, bag-of-words authorship, and log probabilities. First verify that counts and category probabilities each sum correctly, then write “number of orderings × probability of one ordering” on separate lines. For text, cancel author-independent factors before moving into log space to compare scores.
Material boundaries
- This guide covers formal P1–P6, the optional challenge, and all six LLM-guide concepts; no problem is missing across pages.
- The guide's third page contains only closing text and a page number, not another concept.
- The Canvas recording is inaccessible, so no additional spoken examples or claims are inferred.
- The worksheet and substantive guide content are two pages each. The short-material exception applies; the article remains
draft: truepending independent review.
Course video sources
Verified the official Summer 2026 archive: the course is recorded and its syllabus says recordings are available through Canvas. The archived homepage's Videos link redirects to Stanford Canvas login and requires course access. None of the lectures in the 2022 Stanford Online public playlist matches this lecture's title, so no public player is provided and recordings from other offerings are not passed off as this one.
Official sources:
- CS109 Summer 2026 — Canvas lecture recordings (login required)
- CS109 Summer 2026 — archived official schedule
- CS109 Summer 2026 — archived syllabus and recording policy
- Stanford Online CS109 2022 public playlist (different offering, supplementary)
Checked: 2026-10-10.
Update Log
- 2026-10-10: Added explicit video status and checked recording sources and access notes.
- 2026-10-10: Rechecked video status. Confirmed Summer 2026 recordings need Canvas sign-in and the 2022 public playlist has no matching lecture; status unchanged and check date added.
References
Loading...