N-grams, the chain rule and the Markov assumption

Take the phrase the water of Walden Pond and lay a frame two words wide over its start. Inside the frame you read the water. Slide it one word to the right and you read water of, then of Walden, then Walden Pond. Widen the frame to three words and the same sweep gives the water of, water of Walden and of Walden Pond. Those are the bigrams and trigrams of the phrase.

The general rule: an n-gram is a contiguous run of n tokens, read in order. A Unigram is a single token. A sequence of L tokens contains exactly L - n + 1 n-grams of order n, because the frame has that many starting positions. For our five-token phrase that is 5, 4 and 3.

The word carries a second meaning that you must keep apart from the first. "N-gram" also names the probabilistic model that predicts a word from the previous n - 1 words, so a "bigram model" is built from bigram counts and predicts each word from one word of context. Jurafsky and Martin call this "a bit of terminological ambiguity" and use the same Walden Pond examples as the slide [SLP3, ch. 3]. Context nearly always disambiguates: "count the trigrams" means the sequences, "train a trigram" means the model.

The units need not be words. In current systems the frame often slides over BPE subword tokens from Lecture 02, and nothing in this part changes when it does; only the vocabulary does. To see what n-gram counting looks like at web scale, here are the n-gram counts Google released from about a trillion tokens of English web text, after dropping the rare ones.

Distinct bigrams, trigrams and fourgrams climb steeply even after rare n-grams are dropped. The fivegram row dips only because every n-gram seen fewer than 40 times was discarded, and the long tail is where most fivegrams live. Longer windows produce more distinct patterns, each seen fewer times. That is Sparsity, and it will drive the rest of this part.

Suppose you want the probability that the next word is blue given the history The water of Walden Pond is so beautifully. The most direct estimate is a relative frequency: of all the times this eight-word history appeared in a corpus, in what fraction was it followed by blue?

The formula is correct. The trouble is the denominator. How many times does that exact eight-word history occur, even on the whole web? Probably zero, and if it occurs at all, a handful of times, which is far too few to estimate a probability. Jurafsky and Martin put it plainly: "even the entire web isn't big enough", because language is creative and "new sentences are invented all the time" [SLP3, ch. 3]. Most sentences you will read today have never been written before.

The arithmetic of histories

A short calculation shows that no amount of data closes the gap. With a vocabulary of V = 10,000 words, the number of possible histories of length k is V^k. A corpus of a trillion tokens contains at most about 10^12 history occurrences, one per position.

At k = 8 there are 10^32 possible histories, so even if every position in the corpus held a different history, at most a 10^-20 fraction of them could be seen once. The model needs many observations of each history, and it gets zero for nearly all of them. This is Sparsity in its most extreme form.

Before cutting the history short, look at what probability theory gives for free. The probability of the sentence its water is so transparent can be written as a product of five next-word probabilities:

Each factor predicts one word given all the words before it. Five words, five factors, and the product is exactly the joint probability. This is the chain rule of probability, which follows from applying the definition P(A, B) = P(A) P(B | A) repeatedly. In general:

What the chain rule buys is a change of question. "How probable is this sentence?" becomes "how probable is each next word, given what came before?", asked once per position. That is why a next-word predictor and a sentence scorer are the same object: give me one and I can build the other. Every language model you will meet, n-gram or neural, rests on this identity.

What it does not buy is any relief from the counting problem. Look at the last factor: P(transparent | its water is so) still conditions on the whole preceding history, and for a long sentence the late factors carry exactly the long histories that the previous concept showed we cannot count. As SLP3 admits, "using the chain rule doesn't really seem to help us!" It restates the problem in a usable shape; the next concept solves it.

Here is the move that makes language modelling learnable. Instead of P(blue | The water of Walden Pond is so beautifully), use P(blue | beautifully). Instead of asking about an eight-word history nobody has ever written, ask how often blue follows beautifully, which a modest corpus can answer. A Trigram model keeps one more word and uses P(blue | so beautifully).

This is the Markov assumption: the next word depends only on the last few words, not on the whole history. Written generally, with N the order of the n-gram model:

Read the subscripts carefully, because two letters share a name. Lowercase n is the position of the word being predicted. Uppercase N is the order of the model. The window w_(n-N+1) ... w_(n-1) contains exactly N - 1 words. For N = 2 it is P(w_n | w_(n-1)), the Bigram model; for N = 3 it is P(w_n | w_(n-2), w_(n-1)).

What the truncation trades

Cutting the history is a deliberate trade of long-range context for learnability. With a short window, each context recurs often enough to count. With a longer window, the model sees more of the sentence but each context is rarer, so the counts become sparse (Sparsity) and unreliable. The order N is the dial between the two, and the last concept of this part looks at where to set it.

In probability terms, an N-gram model is a Markov chain of order N - 1: the state that determines the next step is the last N - 1 tokens. Shannon described English text this way in 1948 as a "discrete Markoff process" [Shannon 1948].

Where the name comes from

In 1913 Andrei Markov took the first 20,000 letters of Pushkin's Eugene Onegin and classified each as a vowel or a consonant: 8,638 vowels and 11,362 consonants. If letters were independent, about 3,731 vowel-vowel pairs would be expected. He counted 1,104. The previous letter clearly mattered [Hayes 2013; Markov 1913, trans. 2006].

Apply the Markov assumption to every factor of the chain rule and a whole sentence becomes a product of short, countable pieces. Under a Bigram model, with the boundary symbols added:

Two new sentence boundary tokens appear. <s> gives the first word something to condition on, so P(its | <s>) measures how likely its is to open a sentence. </s> is predicted after the last word, so P(</s> | transparent) measures how likely the sentence is to stop there. The general bigram formula is:

A Trigram model needs two words of context for the first real word, so it pads with two start symbols, as in P(I | <s><s>) [SLP3 3.1.3]. For our sentence: P(its | <s><s>) P(water | <s> its) P(is | its water) P(so | water is) P(transparent | is so) P(</s> | so transparent). Still one end symbol: stopping is predicted once.

Why the end symbol is not optional

It is tempting to treat </s> as tidy formatting. It is not. Without it, the model never has to spend probability on stopping, and the sentence probabilities stop adding up. SLP3's footnote states the consequence: without the end symbol, "the sentence probabilities for all sentences of a given length would sum to one", so the model defines "an infinite set of probability distributions, with one distribution per sentence length" (Exercise 3.5). A tiny vocabulary makes this concrete.

In 1948 Claude Shannon generated text by sampling words from English statistics. Drawing each word independently by its frequency gave "REPRESENTING AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT NATURAL HERE HE THE A IN CAME THE TO OF TO EXPERT GRAY COME TO FURNISHES THE LINE MESSAGE HAD BE THESE." Drawing each word given the previous one gave "THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHARACTER OF THIS POINT IS THEREFORE ANOTHER METHOD FOR THE LETTERS THAT ..." [Shannon 1948]. One word of context, and local syntax already appears.

The first sample is a Unigram model, P(w), with no context at all. It knows which words are common and nothing about order, a bag of words: it gives dog bites man and man bites dog exactly the same probability. The second is a Bigram model, and a Trigram model with two words of context reads more fluently still.

The price of context

Each extra word of context multiplies the number of possible contexts by V. At V = 10^4 the possible n-grams number 10^4, 10^8 and 10^12 for unigrams, bigrams and trigrams. Real corpora fill only a sliver of these tables. Shakespeare's works have N = 884,647 tokens and V = 29,066 types, giving V^2 ≈ 844 million possible bigrams and V^4 ≈ 7 × 10^17 possible 4-grams. With so few observed 4-grams per context, a 4-gram model trained on Shakespeare starts copying him verbatim, which Part 06 dissects. Even at web scale, Web 1T kept 314.8 million bigrams seen at least 40 times against about 1.85 × 10^14 possible over its 13.59 million unigram types, roughly a 1.7 × 10^-6 fraction (derived, a lower bound).

This is the same Sparsity that defeated full histories, now as a dial rather than a wall. A larger N captures more context but leaves most contexts unseen, giving zero counts and Overfitting to the training text. In practice SLP3 notes that "when there is sufficient training data we use trigram models ... or 4-gram or 5-gram models". At the modern extreme, infini-gram sidesteps the fixed dial altogether: it uses suffix arrays over about 5 trillion tokens to back off to the longest matching context of any length, with millisecond latency and about 47% next-token accuracy [Liu et al. 2024].