Chapter 4 From N-grams to Bigrams: A Language Model by Hand

4.1 The problem: turn observations into predictions

We have followed text through tokens and numerical representations, but one question remains: where do the probabilities for the next token come from? A neural network can make this question difficult to inspect because its learned state is large. We will first build a model whose complete state fits in a small table.

Imagine completing “The cat sat on the …” after seeing several example sentences. One possible starting rule is to count which pieces followed “the,” then give more frequent continuations a larger chance. Counting is simple enough to inspect: we can see exactly which examples affected a prediction.

For the calculation, replace ordinary words with just a few letters. The letters do not abbreviate hidden meanings; they let us study order and frequency without also solving vocabulary or factual questions. A string is simply a sequence of characters. Our training collection contains three strings:

Example 1: ab
Example 2: ab
Example 3: ac

The duplicate ab records two observations and must be counted twice. Each letter is one token. We deliberately use a character vocabulary separate from Chapter 3’s tokenizer, and no embedding table is needed. This isolates the estimation problem: how should a finite collection of observed sequences determine probabilities for possible future sequences?

The progression will be to count individual tokens, discover what is lost by ignoring order, retain one previous token, and then confront combinations missing from the data. Each modification fixes a specific limitation while introducing a choice or cost. We will use the same three strings throughout, so changes in predictions can be traced to changes in the model.

4.2 State the vocabulary, boundaries, and prediction task

If we give a model only a, b, and c as choices, every choice adds another letter. How would it express “the text ends here”? Stopping needs its own possible result. We also need a way to identify the first prediction, before any letter exists. A predictor must therefore handle both the beginning and the ending. Define BOS, beginning of sequence, as a context marker, and EOS, end of sequence, as a possible prediction. Predicting EOS completes the string; it is not a letter added to the visible text.

The predictable vocabulary, in fixed order, is [a,b,c,EOS]. Its size is four. The three letters in BOS or EOS form one marker name, not three separate tokens. BOS belongs only to the context and is never predicted. Each training string is treated independently: reset to a starting context, predict its characters, then predict EOS. Do not join the end of one example to the beginning of another.

Table 4.1 — Prediction events before choosing a context model.

Training string	Tokens to predict, including the end	Number of events
First ab	a, b, EOS	3
Second ab	a, b, EOS	3
ac	a, c, EOS	3
Total	a: 3; b: 2; c: 1; EOS: 3	9

For each event, the model allocates probability among all four candidates. A probability distribution is a nonnegative allocation whose total is one. Once the context and estimation rule are fixed, the same rule is used at every prediction step.

4.3 Begin with a model that ignores order

Example 4.1 — The Unigram baseline. Begin by ignoring what came before and counting individual predicted tokens. This is the Unigram, or one-token, model. In Table 4.1, b appears twice among nine prediction events. Its observed share, called its relative frequency, is therefore 2/9. Our first estimation rule uses that observed share as its probability for a future prediction. Count each candidate and divide by all nine prediction events. This gives the same distribution at every position:

Next token	Count	Probability
a	3	3/9
b	2	2/9
c	1	1/9
EOS	3	3/9

This model has learned that a is more frequent than c, and that termination is common. But it uses that information without regard to the prefix. At the beginning, it can choose b, c, or EOS even though every training example starts with a. After a, it still assigns the largest individual shares to a and EOS, although the observed successors were b, b, and c.

Why does seeing b twice after a not make b the preferred prediction there? Because we removed the “after a” information when pooling the counts. The model has no separate record to consult for that situation. The defect follows from what the model stores. A collection with the same individual token counts but a different order would produce the same Unigram distribution. It cannot distinguish arrangements that its representation discards.

This suggests a minimal revision: keep separate counts for different previous tokens. After a, use only observations made after a; after b, use observations after b. We obtain a Bigram model. The prediction vocabulary stays the same, and the training examples stay the same. What changes is the condition used to organize evidence.

The names describe how many tokens take part in one prediction: the preceding context together with the next token. An N-gram is a consecutive piece of N tokens. An N-gram language model uses N−1 previous tokens as context to predict one next token: the target itself accounts for the remaining member of the N-token piece.

Table 4.2 — Model order and context.

Order	Name	Previous tokens used	Context at the end of … a b
1	Unigram	0	Empty
2	Bigram	1	b
3	Trigram	2	a b
N	N-gram	N−1	Last N−1 tokens

A Trigram still predicts one token at a time. At the start of a sequence, we supply N−1 BOS markers so that the context has the required length. These markers provide context without adding predicted events. The Unigram has no context and needs no BOS padding.

4.4 Retain one previous token: the Bigram model

4.4.1 Count the nine transitions

With one previous token as context, the training strings become:

BOS → a → b → EOS
BOS → a → b → EOS
BOS → a → c → EOS

Read the first line as three questions with known answers: at the start, what comes next? a. After a, what comes next? b. After b, what comes next? the end. An arrow is one observation of a successor given a context. There are still nine prediction events, but they now have context labels.

Example 4.2 — Reconstructing the trained state. Begin with zero counts and process the arrows in order.

Table 4.3 — Every count update.

Event	Observed transition	Updated cell
1	BOS→a	1
2	a→b	1
3	b→EOS	1
4	BOS→a	2
5	a→b	2
6	b→EOS	2
7	BOS→a	3
8	a→c	1
9	c→EOS	1

We need to find these counts quickly during prediction, so arrange them in a table. Put the previous token in the row label and the next token in the column label. The cell where row a meets column b receives the count for a→b: two. A cell left at zero means that particular pair never appeared. Group all the final counts in this way.

Table 4.4 — Complete Bigram count table.

Previous token	Next a	Next b	Next c	Next EOS	Row total
BOS	3	0	0	0	3
a	0	2	1	0	3
b	0	0	0	2	2
c	0	0	0	1	1

The row for a contains three observations: two b successors and one c successor. The b and c rows record termination. There is no row predicting BOS, and no prediction after EOS. Resetting between strings prevents an artificial EOS→a transition from entering the data.

This count table is the fitted state of our model. Training, for this model, is the counting procedure applied to the designated training collection. It does not require gradients. The neural procedure in Chapter 2 estimates model state differently; both procedures must be distinguished from later reading of the fitted state.

4.4.2 Normalize within the relevant context

We now return from recording the past to predicting the next piece. Imagine a separate ticket bag for each row. The a bag has three tickets: b, b, and c. Choosing that bag means we already know the previous token was a. Drawing uniformly from its tickets gives b chance 2/3 and c chance 1/3. Return the ticket after drawing; prediction reads the stored counts without changing them. This is the idea of a conditional probability: make the prediction using the observations that meet the given condition.

To predict after a, allocate each candidate its observed share of that row: [0,2/3,1/3,0]. Only three events meet the condition “previous token is a,” so the denominator is three, not nine.

If we divided the a-row counts by nine, their sum would be 3/9 rather than one. Those numbers describe shares of all training events, not a full allocation of what comes next given a. Conditional prediction requires first selecting the relevant row, then normalizing within it.

Let $C(h,x)$ count how often token x followed context h, and let $C(h)$ denote the sum of the outgoing counts in that row. The empirical conditional estimate is:

$$P_0(x\mid h)=\frac{C(h,x)}{C(h)},\qquad C(h)>0.$$

The vertical bar reads “given”: candidate x is on the left and the known context h is on the right. For the a→b example, h is a, x is b, C(h,x) is the cell count 2, and C(h) is the row total 3. The formula therefore reads “chance of b after a = count of a→b divided by count of predictions after a.” The subscript 0 identifies the version without smoothing, an adjustment introduced below. The condition on the right requires a nonzero denominator.

For a→b, the estimate is 2/3. For BOS→a, it is 3/3 = 1. For b→EOS, it is 2/2 = 1; for c→EOS, it is 1/1 = 1. All four probability rows sum to one. We now have a rule for every step reachable from BOS under this unsmoothed model.

Relative counts are estimates based on this sample. The a row’s 2/3 does not establish that the true source of all possible future data uses exactly that probability. It specifies the predictor fitted from these observations.

4.5 Assign probability to a complete sequence

4.5.1 Follow a prescribed path

Example 4.3 — Scoring ab. Suppose the string is given rather than generated. The model must start with a, continue with b, and then stop. The required path is BOS→a→b→EOS.

Required transition	Conditional probability
BOS→a	1
a→b	2/3
b→EOS	1

The probability of satisfying all three successive requirements is their product:

$$P_0(\text{ab,EOS}\mid\text{BOS})=1\times\frac23\times1=\frac23.$$

Multiplication tracks a succession of requirements. The first step always reaches a. Among the choices there, a share of 2/3 proceeds to b; every such path then ends. Thus the share completing ab is 2/3. More generally, if only half of those b paths ended, the complete-string probability would be half of 2/3, or 1/3. That hypothetical extra requirement illustrates why we multiply: each new factor takes a share of the paths that have already met the earlier requirements. Adding factors would not do that and would exceed one in the original example.

For ac, the middle factor becomes 1/3 and the last remains one, giving probability 1/3. These are the only complete strings reachable in this particular model, and their probabilities sum to one.

Writing the same calculation for any length. The preceding example can be written without naming a and b, so that the rule applies to a sequence of any length. The probability chain rule expresses a joint sequence probability as a product of conditional probabilities. Using only a short suffix as the condition is a separate modeling assumption; the chain rule itself does not require a Bigram approximation. Let $x_t$ be the token at position t, $x_{<t}$ all earlier tokens, and $h_t$ the suffix used by the N-gram model. We approximate the full-history conditional by:

$$P(x_t\mid x_{<t})\approx P_N(x_t\mid h_t),\qquad |h_t|=N-1.$$

The t in a subscript is a position number, not a multiplier. The symbol < in the history subscript means “positions before t”; the vertical bars around the context measure how many tokens it contains. For Bigram and the string ab, the successive contexts are BOS, a, and b. A Trigram would use BOS BOS, BOS a, and a b for those same predictions. The change is how much history each step consults.

For a complete sequence of T ordinary tokens, followed by $x_{T+1}=\mathrm{EOS}$, the probability under that model is:

$$P_N(x_1,\ldots,x_T,\mathrm{EOS})=\prod_{t=1}^{T+1}P_N(x_t\mid h_t).$$

The symbol ∏ means multiply one factor for each listed position. Its lower and upper limits say to start at position 1 and stop at T+1. For ab, T is 2: positions 1 and 2 contain a and b, and position 3 contains EOS. Expanding the product gives exactly the three factors already calculated above, 1 × 2/3 × 1. The initial contexts use BOS padding, which is not generated. The approximation concerns the context model; the product is the exact definition of the resulting model’s path probability. Standard treatments of N-grams develop these count, boundary, and chain-rule conventions. Jurafsky and Martin, §§3.1–3.3

4.5.2 Distinguish a prefix from a finished string

Consider two requests: “start with ab” and “write exactly ab and stop.” Both require a followed by b, but the second adds an ending requirement. A prefix probability answers the first request, regardless of what happens afterward. A complete-string probability also requires termination at that point. In the unsmoothed Bigram, the prefix ab always ends next, so the two numbers happen to agree. That agreement is a property of this table, not a general rule.

The Unigram makes the distinction visible immediately. It can continue after b, so reaching ab is no longer enough. Its prefix ab has probability 3/9 × 2/9 = 2/27. Requiring EOS adds a factor 3/9, giving 2/81 for complete ab. Omitting the ending factor would answer a different question.

The same Unigram assigns complete ac probability 3/9 × 1/9 × 3/9 = 1/81, but complete aa probability 3/9 × 3/9 × 3/9 = 1/27. It prefers aa, even though the training collection contains ac and no aa. This numerical failure is another consequence of forgetting order; the Bigram corrects it on the observed paths by conditioning on the previous token.

4.6 Generate by choosing a path through the fitted table

Scoring and generation use the same probabilities in different ways. Scoring reads the probability of a supplied next token. Generation selects the next token from the distribution, appends it, and chooses a new context.

Follow only the arrows leaving a

Example 1BOS → a → b → EOS

Example 2BOS → a → b → EOS

Example 3BOS → a → c → EOS

Collected successors:bbc

b: 2 / 3Two of the three tickets

c: 1 / 3One of the three tickets

Freeze this table. The next operation can take either branch ↓

Generate

Choose b or c using these shares, append it, then look up the next row.

Evaluate

If the supplied next token is b, read 2/3. If it is c, read 1/3.

Both branches read the counts. Neither adds a training observation.

Figure 4.1 — One trained count structure supports two different read operations. Original book diagram · CC BY-SA 4.0.

Figure 4.1 separates the training operation from these two read operations. Neither scoring a string nor generating one increases any count. If generated text is later included in training, that is an additional, explicit fitting step.

Example 4.4 — A reproducible generation trace. Start at BOS with the unsmoothed Bigram. Candidate order is [a,b,c,EOS]. Assign each candidate a half-open interval of length equal to its probability. At context a, a has zero length, b occupies the first 2/3, c the final 1/3, and EOS has zero length.

Figure 4.1’s b, b, c tickets provide the same a-row chances as those intervals. The table below records one sequence of numerical draws. First follow what each draw selects; the exact arithmetic used to reproduce the draws is given after the trace.

Table 4.5 — Seed 42, N=2, no smoothing.

Step	Context	Draw, rounded	Selection
1	BOS	0.252345	a; it has probability 1
2	a	0.088125	b; the draw is below 2/3
3	b	0.577281	EOS; it has probability 1

The visible result is ab, with stopping reason EOS. The actual rule uses the full draw, not the rounded display. Restarting with the same model, candidate order, seed, and algorithm produces the same trace. Different seeds need not produce different strings: many draws choose the same interval.

The accompanying fixed procedure allows at most 12 draws, including an EOS draw. An EOS result is complete. Reaching the draw limit first yields a truncated prefix. Encountering an undefined distribution is a third, distinct stop reason. A reproducible record must include these conventions; the seed alone cannot specify the experiment.

Reproduction detail: where the draws come from. A pseudorandom generator follows a numerical rule that produces a repeatable sequence of draws. Its starting state is the seed. It supplies choices to the model; it does not train the model. Our LCG32 rule starts at 42. Repeatedly multiply the current state by 1664525, add 1013904223, and keep the remainder after division by 4294967296 as the new state. Here “remainder” has its ordinary division meaning: for example, 10 divided by 3 leaves remainder 1. The first three new states are 1083814273, 378494188, and 2479403867. Divide each by 4294967296 to obtain the respective draw in Table 4.5, before rounding. These large constants specify the random-number procedure, not learned language-model parameters.

4.7 Let the model encounter a missing combination

The Bigram has captured the observed order, but consider complete aa. Its first step BOS→a has probability one. Its next required step a→a has probability zero, because no a followed a in training. The prescribed path is therefore unreachable and has probability zero.

The training collection did not prove that aa is impossible. The estimator converted “not observed here” into a zero probability. With a small collection, that is often too strong a conclusion about future inputs.

The ticket bags make another failure easier to see. The a bag exists and contains three tickets, just none labeled a. But what if the relevant bag had no tickets at all? We could not draw anything from it. A related but different problem appears at higher order. A Trigram distinguishes the contexts BOS BOS, BOS a, a b, and a c. For the first training ab, its events are BOS BOS→a, BOS a→b, and a b→EOS. It still has nine events overall.

Ask for the Trigram distribution after a a. That context never occurred. All four counts are zero, and the denominator is zero. The unsmoothed row is undefined, not a distribution of four zeros. Four zeros sum to zero rather than one.

Table 4.6 — Two kinds of missing evidence.

Query	Relevant observed counts	Result without smoothing
Bigram, candidate a after context a	Row [0,2,1,0], total 3	Defined probability 0/3 = 0
Trigram, distribution after context a a	Row [0,0,0,0], total 0	Undefined; normalization would divide by zero

Complete aa is nevertheless unreachable from the Trigram’s start: the earlier BOS a→a step already has a defined zero probability. No assignment to the later unseen row can restore a path whose prefix cannot occur. This is an argument about reachability, not an instruction to treat the arithmetic expression “zero times undefined” as an ordinary product. The implementation preserves both facts: the sequence is unreachable, and inspecting its later row reports undefined.

4.8 Revise the estimate with smoothing

4.8.1 Reserve some probability for every candidate

In the ticket picture, we could place one extra ticket for each candidate in every bag, even an empty bag. Every candidate would then have a chance, and every bag would contain tickets. The numerical version is to add a positive amount to every candidate count before normalizing. Add-one smoothing adds one. For the a row, the calculation becomes:

Example 4.5 — Redistributing the a-row probability.

Candidate	Observed count	Count plus one	Adjusted probability
a	0	1	1/7
b	2	3	3/7
c	1	2	2/7
EOS	0	1	1/7
Total	3	7	1

The four added units are part of an estimation rule, not four new observations. The denominator rises from three to seven because there are four predictable candidates. BOS is not a fifth candidate. Adding to numerators without changing the denominator would make the total probability exceed one.

Let $\alpha$ be the amount added to each candidate, and let $V$ be the number of predictable candidates. Here α is either zero or one and V is four. The general add-α expression is:

$$P_\alpha(x\mid h)=\frac{C(h,x)+\alpha}{C(h)+\alpha V}.$$

Read alpha as the amount added to one candidate. Since there are V candidates, the row total increases by alpha times V. For a→b with add-one, the numerator is 2 + 1 = 3 and the denominator is 3 + 1 × 4 = 7. The formula therefore reproduces 3/7 in the table.

When α=0, this reduces to the unsmoothed estimate where the row total is positive. When α=1, every candidate has positive probability, including candidates in an unobserved context.

The adjustment has a cost. b’s share after a falls from 2/3 to 3/7. Positive mass assigned to previously unseen choices must come from the previously observed choices if the total is to remain one. Smoothing is therefore a decision about allocating uncertain probability, not a cost-free correction.

4.8.2 Recalculate all rows and all path factors

Smoothing applies to every row, including the start and the ending decisions.

Table 4.7 — Complete add-one Bigram distribution.

Context	P₁(a)	P₁(b)	P₁(c)	P₁(EOS)
BOS	4/7	1/7	1/7	1/7
a	1/7	3/7	2/7	1/7
b	1/6	1/6	1/6	3/6
c	1/5	1/5	1/5	2/5

For example, b’s observed row [0,0,0,2] becomes [1,1,1,3], total six. Its probability of stopping is now 3/6 rather than one. Every term in a complete-string calculation must use the adjusted table.

Example 4.6 — Complete sequences after smoothing. For aa, take a at the start, another a after a, and then EOS after a:

$$P_1(\text{aa,EOS})=\frac47\times\frac17\times\frac17=\frac4{343}\approx0.011662.$$

For the observed strings, the corresponding products are:

$$P_1(\text{ab,EOS})=\frac47\times\frac37\times\frac36=\frac6{49}\approx0.122449,$$ $$P_1(\text{ac,EOS})=\frac47\times\frac27\times\frac25=\frac{16}{245}\approx0.065306.$$

The formerly impossible aa now has positive probability; the observed ab and ac have lower probabilities than before. These three values do not sum to one because they no longer exhaust the possible outputs. The model can stop immediately, begin with b or c, or produce longer strings. Each next-token row still sums to one.

For an unseen Trigram context such as a a, add-one produces [1,1,1,1], total four, hence a uniform row. That equality follows from the symmetric rule applied to no observations. It is not evidence that the real data source uses equal shares.

Example 4.7 — Why order changes smoothed aa. Trigram uses BOS BOS to predict the first a, BOS a to predict the second, and a a to predict EOS. The factors are 4/7, 1/7, and 1/4, giving 1/49. Bigram’s last context is only a and gives EOS 1/7, explaining its different result 4/343.

Add-one is chosen because every adjustment is visible. More effective language-model smoothing methods exist; this chapter does not treat add-one as the best estimator. Its purpose is to expose both the repair and the probability redistribution it requires. Jurafsky and Martin, §3.6.1

4.9 Compare models under one stated evaluation procedure

Smoothing made aa possible but reduced the probability of the observed strings. To decide whether that tradeoff helps, we have to state what performance we want to compare—the same issue that arose when judging replies in Chapter 1.

Evaluation applies a fitted model to specified cases and a criterion without refitting on those cases. Here the fixed diagnostic strings are ac and aa. They do not enter the counting operation. The first deliberately repeats a training string; the second introduces an unseen combination. This is a diagnostic comparison, not an independent test of generalization to ordinary language.

Table 4.8 — All six fixed settings, scoring complete strings including EOS.

Order and smoothing	P(ac, EOS)	P(aa, EOS)
Unigram, α=0	1/81 ≈ 0.012346	1/27 ≈ 0.037037
Bigram, α=0	1/3 ≈ 0.333333	0
Trigram, α=0	1/3 ≈ 0.333333	0
Unigram, α=1	32/2197 ≈ 0.014565	64/2197 ≈ 0.029131
Bigram, α=1	16/245 ≈ 0.065306	4/343 ≈ 0.011662
Trigram, α=1	16/245 ≈ 0.065306	1/49 ≈ 0.020408

The preceding examples account for the context-sensitive rows. For smoothed Unigram, the counts [3,2,1,3] become [4,3,2,4], total 13. Hence ac receives 4/13 × 2/13 × 4/13 = 32/2197, and aa receives 4/13 × 4/13 × 4/13 = 64/2197.

What does “better” mean here? If the criterion is probability assigned to complete ac alone, unsmoothed Bigram beats its add-one version. A different criterion asks how much probability a setting gives to seeing both diagnostic strings as separate, independent draws from that fixed model. This is their joint likelihood under the setting, calculated by multiplying their probabilities. We hold the observations fixed and compare the model settings, rather than ask whether either string is true. Unsmoothed Bigram gives zero, whereas add-one Bigram gives a positive product. The same change can improve one stated criterion while reducing an individual example’s probability.

This illustrates Chapter 1’s requirement to keep a score attached to its evaluation conditions. Reusing these two visible cases to inspect model settings is useful diagnosis; it does not turn them into a blind or representative test. For an actual comparison, training and evaluation selection must be designed for the question being investigated.

Sequence probabilities also depend on the tokenization and on the number of multiplied factors. They are not factual truth scores, and raw values should not be compared across different tokenizers as if they measured the same event representation. Chapter 6 introduces more systematic probability and length-aware evaluation tools.

4.10 Analyze what increasing N can and cannot repair

A longer context can distinguish histories that a shorter model merges. For a Trigram, a b and c b are different contexts; a Bigram maps both to b. This is a genuine increase in available information, but not an unlimited memory.

Example 4.8 — An unavoidable fixed-window failure. Treat words as tokens and compare prefixes red key x x and blue key x x when the next output must report the earlier color. Bigram selects x in both cases; Trigram selects x x in both. Under either model, equal selected contexts produce equal distributions. The model cannot give a color-dependent distribution when its lookup key contains no distinguishing color.

No amount of additional counting of those same short contexts can restore which earlier color occurred in a particular input. Increasing N can include a more distant clue, but any fixed context length can be exceeded. A longer window also cannot use an external document that was never supplied to the sequence.

More context can also leave us with less evidence for each particular situation. An overall survey might contain many respondents, while a group selected by several detailed conditions contains only a few. Counting increasingly specific text histories has the same difficulty: the collection has not grown, but we are dividing its evidence more finely. This is data sparsity. There are more exact histories to estimate as N grows. Over V labels, there are $V^N$ formal length-N combinations: for V=4, the counts are 4, 16, and 64 for orders one, two, and three. The exponent N means multiplying V by itself N times. With four choices, there are four one-token patterns, 4 × 4 = 16 two-token patterns, and 4 × 4 × 4 = 64 three-token patterns. This counts combinations before enforcing the EOS stop rule; some combinations cannot occur inside valid strings, and BOS contexts add separate cases. The point is the multiplicative growth in possible exact patterns, not an instruction to allocate every possible entry.

A sparse implementation can store only observed combinations. Our tiny training collection has 4, 5, and 5 distinct observed events at the three orders, so increasing N does not force actual storage to grow on every collection. Nevertheless, splitting evidence among more possible contexts tends to leave fewer observations per exact case. Longer memory and reliable estimation are separate requirements.

Neural language models use learned representations and shared numerical functions to share statistical structure across inputs rather than estimate each exact context independently. Bengio and colleagues identify this motivation for neural probabilistic language modeling. Causal GPT-style models and N-grams share the next-token prediction task, but differ in representation and context computation. Sharing the objective does not make their mechanisms identical, nor does a richer mechanism guarantee truthfulness or successful use of every clue. Bengio et al., 2003

4.11 Summary and the first project milestone

The Unigram estimated individual-token frequencies but discarded order. Bigram retained one previous token and recovered the observed transitions. The chain rule turned conditional probabilities into complete-sequence probabilities, with EOS accounting for termination. Generation selected a path; evaluation scored a given path; training alone added observations to the fitted state.

Missing combinations exposed two distinct cases: a defined zero after an observed context and an undefined distribution after an unseen context. Add-one allocated positive mass to all candidates, at the cost of reducing mass elsewhere. Increasing N retained more history while increasing the number of exact patterns that might need evidence. The fixed-window counterexample showed a limitation that better counting alone cannot remove.

The first project milestone, called MG-0 in the book plan, is a paper-and-pencil model: reconstruct Tables 4.3–4.4, calculate an unsmoothed and a smoothed complete sequence, explain the fixed generation trace, and analyze a missing combination and an indistinguishable pair of contexts. Keep these calculations with Chapter 1’s evaluation, failure, and risk register. No browser experiment or programming setup is required.

Chapter 5 begins the vector, matrix, and shape foundations needed for numerical models. After that core material and Primer-PY, a later programming exercise returns to implementing a character N-gram model with configurable N. Chapter 6 and Chapter 7 develop probabilities, loss, and parameter learning. Part I has supplied concrete questions those tools must answer.

4.12 Exercises

1. Order and boundaries. For a 5-gram model, state the number of previous tokens and the number of BOS markers used at the start under this chapter’s convention. How many prediction events does a three-character training string contribute?
2. New training collection. Replace the training strings by ab, ac, ac. Construct the complete Bigram count table and calculate unsmoothed complete ac. Which rows change relative to Table 4.4?
3. Prefix versus completion. Under Table 4.7, calculate the probability of prefix ab and of complete ab. Explain the factor relating them. Also calculate the probability of the empty complete string.
4. A different smoothing amount. Add two to every candidate in the original a row. Calculate the distribution and its sum. A colleague instead keeps the denominator at three; explain the resulting error.
5. Unseen contexts. Inspect a a in an unsmoothed Trigram and in an add-one Trigram. Explain why four zero counts do not by themselves define a uniform distribution, and why the smoothed equality is an assumption of the estimator.
6. Separate generation from training. Suppose a generated output is aa. First explain why the original count table is unchanged. Then explicitly add aa as a fourth training string and calculate the new a row and the new unsmoothed complete-aa probability.
7. Longer observed sequence. Starting again from the original three-string collection, add aba as a fourth training string. Count all new events, give the revised a and b rows, and calculate unsmoothed complete aba.
8. A reproducibility defect. Two implementations use seed 42 and the same count table, but one assigns sampling intervals in order [a,b,c,EOS] and the other in order [c,b,a,EOS]. Must their traces agree? Identify what the seed fails to specify.
9. Construct an indistinguishable pair. For a 5-gram model, write two different prefixes whose correct next outputs depend on an earlier distinction but whose last four tokens match. Explain why more training cannot make this model distinguish those particular histories from its selected context alone.
10. Evaluate the evaluation. A report declares add-one universally better because it makes aa possible. Use Table 4.8 to give a counterexample to that criterion-free conclusion, then state what a defensible comparison must specify.

4.13 Solutions

1. The context contains four previous tokens, initialized with four BOS markers. A three-character string contributes four predicted events: three characters and EOS. Context padding is not itself predicted.
2. BOS is [3,0,0,0], a is [0,1,2,0], b is [0,0,0,1], and c is [0,0,0,2]. Only the BOS row is unchanged. Complete ac has probability 1 × 2/3 × 1 = 2/3. The duplicate now increases c’s conditional share rather than b’s.
3. Prefix ab has probability 4/7 × 3/7 = 12/49. Complete ab adds EOS after b, giving 12/49 × 3/6 = 6/49. The extra factor is the probability of ending at that point. The empty string requires EOS directly from BOS, with probability 1/7.
4. The adjusted counts are [2,4,3,2], total 11, giving [2/11,4/11,3/11,2/11], whose sum is one. Keeping denominator three gives total 11/3. A larger numerator must be accompanied by normalization over all adjusted candidates.
5. Without smoothing, division would be by zero and the row is undefined. With add-one, four adjusted counts of one yield four probabilities of 1/4. The uniformity comes from adding equal amounts in the absence of observations, not from evidence of equal real frequencies.
6. Generation only reads probabilities and selects tokens, so it contributes no observations. Explicitly training on aa adds BOS→a, a→a, and a→EOS. BOS becomes [4,0,0,0]; a becomes [1,2,1,1], total five. Complete aa now has probability 1 × 1/5 × 1/5 = 1/25 without smoothing.
7. The new events are BOS→a, a→b, b→a, and a→EOS, giving 13 events overall. The a row becomes [0,3,1,1], total five; b becomes [1,0,0,2], total three. Complete aba has probability 1 × 3/5 × 1/3 × 1/5 = 1/25. The final EOS must be read from a, not b.
8. No. At context a, draw 0.088125 selects b in the first order but c in the second, because c occupies the initial 1/3 there. The seed specifies generator state, not the candidate-to-interval mapping. Vocabulary order, generator algorithm, parameters, input, and stopping rules belong in the record.
9. For example, red key x x x x and blue key x x x x, followed by a request to emit the earlier color under the stipulated task. Both selected contexts are four x tokens. A fixed function of that same context must return the same distribution; distinguishing the color requires retaining additional information. The task instruction is assumed outside these abbreviated prefixes, not appended as new tokens changing their suffixes.
10. Unsmoothed Bigram assigns ac 1/3, while its add-one version assigns 16/245, a smaller value. If complete-ac probability is the criterion, that change is worse. A defensible comparison specifies the data collection, separation from fitting, token and boundary conventions, metric, and the population or diagnostic question to which the conclusion applies.

4.14 References

• Jurafsky and Martin, Speech and Language Processing, chapter 3: N-gram Language Models. The August 19, 2026 draft explains N-gram counts, sequence probabilities, and evaluation in §§3.1–3.3, and add-one smoothing in §3.6.1. These sections provide a fuller treatment of the count models developed here. All numerical examples in this chapter are original.
• Bengio et al., A Neural Probabilistic Language Model (2003). The paper learns representations that let a language model share statistical information across inputs. It develops one response to the sparsity problem exposed by our growing N-gram tables.