Part IV · Ch. 35 — Markov Chain & n-gram Language Models

draft

Probabilistic · Sequences · The memoryless ancestor of the LLM. A Markov chain predicts the next symbol from the current state alone; an n-gram language model is that idea aimed at text — the direct forerunner of every next-token predictor in ch. 01, LLM. Card: ../02-types-of-ai/03-probabilistic.kmd.

🎨 Figure F-IV.35.0 — The chain that writes. Brief: a row of word-states linked left to right, each arrow labelled with a transition probability; a sampler pointer walks the chain emitting a sentence, with a faded Transformer attention-fan behind it to show the lineage.

Markov chain over text

1. Definition and short history

A Markov chain is a stochastic process whose next state depends only on the present state, not the full history — the memoryless property. An n-gram language model applies it to language: the probability of the next token is conditioned on the previous \(n-1\) tokens (an \((n-1)\)-order Markov chain over the vocabulary).

The lineage begins with two people counting letters. Andrey Markov (1913) analysed the vowel/consonant sequence of Pushkin's Eugene Onegin to prove dependent events obey the law of large numbers — the first Markov chain fit to real data (full story in the CS Compendium, ch. 01). Claude Shannon (1948, A Mathematical Theory of Communication) turned it into a generator: sampling from letter- then word-statistics of English, he produced text whose "resemblance to ordinary English increases quite noticeably at each step" — the first language-generation model. n-gram models then ran statistical NLP, speech recognition, and machine translation from the 1980s to the ~2010s.

2. Foundations

  • Stochastic processes — Markov chains; the Markov (memoryless) assumption.
  • Information theory — Shannon entropy of a language; perplexity as \(2^{\text{cross-entropy}}\) (a model's per-token surprise).
  • Probability & statistics — maximum-likelihood estimation from corpus counts; smoothing as a prior over unseen events.

3. Algorithms and architectures

  • The model — \(P(w_1\dots w_T) \approx \prod_t P(w_t \mid w_{t-n+1}\dots w_{t-1})\).
  • Estimation — MLE by counts: \(P(w_t\mid \text{ctx}) = \dfrac{\text{count}(\text{ctx}, w_t)}{\text{count}(\text{ctx})}\).
  • Smoothing (unseen n-grams must not get probability 0, or perplexity is infinite):

    add-one