N-gram Language Models › The Markov Assumption

The chain rule gives us an exact decomposition, but it demands something impractical: reliable estimates of probabilities conditioned on arbitrarily long histories. The key insight of n-gram models is to make a simplifying assumption that trades some accuracy for tractability.

The assumption is named after the Russian mathematician Andrey Markov, who studied stochastic processes with this "memoryless" property in the early 20th century. In a Markov chain, the probability of the next state depends only on the current state, not on the full history of how you arrived there. In the context of language, it means we assume the future depends only on the recent past, not the distant past.

For a unigram model ($n = 1$), each word is treated as completely independent of all others:

The unigram model ignores all context. It assigns the same probability to "cat" whether the preceding words were "the fluffy" or "the entire concept of." This is obviously a poor approximation, but unigrams are useful as a baseline and as a component in more sophisticated models.

For a bigram model ($n = 2$), each word depends only on the single word immediately before it:

where:

• $P(w_i|w_1, \ldots, w_{i-1})$: the true conditional probability given the full history (left side)
• $P(w_i|w_{i-1})$: the bigram approximation using only the immediately preceding word (right side)
• $\approx$: indicates this is an approximation, not an equality

For a trigram model ($n = 3$), the memory extends to two previous words:

where:

• $w_{i-2}$: the word two positions before the current word
• $w_{i-1}$: the word immediately before the current word
• The context $(w_{i-2}, w_{i-1})$ forms a two-word history window

In general, for an n-gram model, the Markov approximation is:

where the context window spans exactly $n-1$ preceding words. We discard information from the distant past to make estimation tractable from finite data.

Why does this help? Consider the difference in what we need to estimate for the sentence "the cat sat on the mat":

• Full history: We need $P(\text{mat}|\text{the cat sat on the})$, requiring counts of the specific five-word context.
• Trigram: We need $P(\text{mat}|\text{on the})$, requiring only counts of the two-word context.
• Bigram: We need $P(\text{mat}|\text{the})$, requiring only counts of the single word "the."

Shorter contexts appear far more frequently in training data, giving us more reliable probability estimates. The Markov assumption is an approximation, but it works surprisingly well in practice because language has enough local structure that nearby words carry most of the predictive information. The word that most immediately constrains "mat" is likely "the" (or "on the"), not the first word five positions back.