Markov Text

Words by the Numbers

Chapter 5 · Markov Text

Words by the Numbers 4 counted which words sit next to each other. This chapter turns those counts around: if you know the word you just read, which word is likely to come next? Answer that question with the counts and you can also run it backwards and write text, one word at a time, by rolling dice weighted by the counts. The result is a Markov chain text generator. It is about twenty lines of Python, it has no idea what any word means, and its output still sounds almost right, which is the interesting part. The maths is light: counting, division and multiplying probabilities.

What was run, and what to trust

Every Python snippet in this chapter and in the three exercise solutions was executed (Python 3.14), and the output in the comments is what Python printed. The real text is the same as in Words by the Numbers 4: the reference documentation that ships inside Python (the pydoc_data.topics module), about 74,500 word tokens of technical English. It is not typical prose, and its counts change a little between Python versions, so expect small differences on your machine. The generated passages depend on the random seed given in the code; other seeds give other text. The tiny sentences in the first snippet and in Exercise 1 are invented, illustrative examples. Background facts come from a web search that returned summaries of web pages; such fetched pages are often truncated or model-summarised, so treat the wording as a paraphrase. The search confirmed Markov's use of the poem Eugene Onegin and the figures quoted below; it did not give Shannon's exact word-level orders or example sentences, so those are left out and the reader is pointed to his paper (check). Statements marked (check) were not confirmed against a source.

Where the Idea Came From

Andrey Markov studied sequences in which the next item depends on the current one. In a 1913 lecture he applied the idea to text: according to the search summaries, he took the first 20,000 letters of Pushkin's verse novel Eugene Onegin, marked each letter as a vowel or a consonant (8,638 vowels and 11,362 consonants), and showed that the chance of a vowel depends on what came before it. An English translation of the paper appeared in 2006, per the same sources. In 1948 Claude Shannon's paper A Mathematical Theory of Communication used the same kind of model to produce approximations of English of increasing order; sources describe them as a series of Markov-chain models, but I could not confirm the orders or the sample sentences from a source, so look them up in the paper itself (check). Words by the Numbers 9 comes back to Shannon.

Predicting the Next Word

The model has one rule: the next word depends only on the word just read, not on anything earlier. For each word, keep a list of every word that has followed it. The list keeps repeats, so a word that followed three times out of four is three times as likely to be picked when you choose from the list with random.choice. Picking from the list is the same as picking by probability.

import random
from collections import Counter, defaultdict

text = "the cat sat on the mat and the cat saw the dog"
words = text.split()
followers = defaultdict(list)
for a, b in zip(words, words[1:]):
    followers[a].append(b)
print(dict(followers))
counts = Counter(followers["the"])
total = sum(counts.values())
print({w: f"{c}/{total}" for w, c in counts.items()})

# chance of the path the -> cat -> sat: P(cat after the) x P(sat after cat)
p = (counts["cat"] / total) * (Counter(followers["cat"])["sat"] / len(followers["cat"]))
print("chance of cat then sat, starting from the:", p)

random.seed(4)
word, out = "the", ["the"]
for _ in range(7):
    if word not in followers:
        break                      # 'dog' ended the text: no follower seen
    word = random.choice(followers[word])
    out.append(word)
print(" ".join(out))
# {'the': ['cat', 'mat', 'cat', 'dog'], 'cat': ['sat', 'saw'], 'sat': ['on'], 'on': ['the'], 'mat': ['and'], 'and': ['the'], 'saw': ['the']}
# {'cat': '2/4', 'mat': '1/4', 'dog': '1/4'}
# chance of cat then sat, starting from the: 0.25
# the mat and the dog
    

the was followed by cat twice, mat once and dog once, so the chance of cat after the is 2/4. To get the chance of a whole path, multiply the steps: cat after the (2/4) times sat after cat (1/2) is 1/4. The generated line also shows the model's one structural weakness: it stopped at dog, which ended the sample text, so no follower had ever been seen. Real generators need a rule for that; the next snippet jumps to a random word.

A Chain Built from Real Text

Now the same idea on the whole documentation text. The snippet builds the follower lists, counts how many words have only one kind of follower, and prints three short passages. Starting words are drawn from the full list of tokens, so common words start more often. When a word has no follower the code jumps to a random word, and the lists never run across the end of one documentation topic into the next.

import random, re
from collections import defaultdict
from pydoc_data.topics import topics

def tokens(text):
    return re.findall(r"[a-z]+(?:'[a-z]+)?", text.lower())

followers = defaultdict(list)
starts = []
for doc in topics.values():
    w = tokens(doc)
    starts.extend(w)
    for a, b in zip(w, w[1:]):
        followers[a].append(b)

print("distinct words with a follower:", len(followers))
one = sum(1 for f in followers.values() if len(set(f)) == 1)
print("words with only one kind of follower:", f"{one / len(followers):.0%}")

random.seed(7)
for _ in range(3):
    word = random.choice(starts)
    out = [word]
    while len(out) < 18:
        word = random.choice(followers[word]) if word in followers else random.choice(starts)
        out.append(word)
    print(" ".join(out))
# distinct words with a follower: 3288
# words with only one kind of follower: 38%
# should look for a function or none if stmt an extra argument for example split if only calls
# continue id continue or methods object rshift self args because otherwise str bytes join a common sequence types
# attributes the class s keys for getitem return true the traceback attached to the container only or rxor
    

Of the 3,288 words that have a follower, 38% were only ever followed by one kind of word, so the chain has no choice there. Read the passages in pieces: an extra argument for example and the traceback attached to the container are fluent fragments, and each pair of neighbouring words really occurs in the source. But no sentence lasts: the model has no memory of how the sentence began, so it wanders into something unrelated after a few words. That is the “almost right”. Every pair is plausible and the whole is not. Because the source is technical documentation, the nonsense also sounds technical (continue id continue or methods object rshift self args).

Short Memory, Long Memory

The fix is to remember more. An order-k chain uses the last k words as its context. Order 1 is what you just built; order 2 looks at the last two words (the bigrams of Words by the Numbers 4), order 3 at the last three. Generation works the same way: look up the context, pick a follower, slide the window along by one word. The snippet builds orders 1 to 3, generates 3,000 words from each, and measures two things. The first is how many contexts have only one possible follower. The second is how many 4-word runs in the generated text can be found word for word in the source, which measures copying.

import random, re
from collections import defaultdict
from pydoc_data.topics import topics

def tokens(text):
    return re.findall(r"[a-z]+(?:'[a-z]+)?", text.lower())

docs = [tokens(d) for d in topics.values()]

def build(order):
    chain = defaultdict(list)
    for w in docs:
        for i in range(len(w) - order):
            chain[tuple(w[i:i + order])].append(w[i + order])
    return chain

def generate(chain, order, n, seed):
    rng = random.Random(seed)
    keys = list(chain)
    state = rng.choice(keys)
    out = list(state)
    while len(out) < n:
        if state not in chain:
            state = rng.choice(keys)           # dead end: jump to a random context
            out.extend(state)
            continue
        out.append(rng.choice(chain[state]))
        state = tuple(out[-order:])
    return out[:n]

source4 = set()
for w in docs:
    source4.update(zip(w, w[1:], w[2:], w[3:]))

for order in (1, 2, 3):
    chain = build(order)
    single = sum(1 for f in chain.values() if len(set(f)) == 1) / len(chain)
    out = generate(chain, order, 3000, seed=order)
    windows = list(zip(out, out[1:], out[2:], out[3:]))
    copied = sum(1 for g in windows if g in source4) / len(windows)
    print(f"order {order}: {len(chain):6d} contexts | one possible follower: {single:4.0%} | 4-word runs found in source: {copied:4.0%}")
    print("   ", " ".join(generate(chain, order, 16, seed=order + 10)))
# order 1:   3288 contexts | one possible follower:  38% | 4-word runs found in source:   4%
#     fault after the sequence methods should be supported builds a statement this rule is produced is
# order 2:  27494 contexts | one possible follower:  76% | 4-word runs found in source:  64%
#     more will likely be left undefined object add self other modulo object ilshift self other object
# order 3:  46929 contexts | one possible follower:  91% | 4-word runs found in source: 100%
#     runcall returns it returns the value of the literal for example the annotation list int might
    

As the memory grows the sentences get steadier (the order-3 sample, returns the value of the literal for example the annotation, reads almost like a real documentation sentence), but the freedom disappears. At order 3, 91% of the contexts have a single follower and 100% of the 4-word runs come straight from the source. The 100% is partly built in: an order-3 context plus its follower is itself a 4-word run from the source, so the figure could only fall below 100% where the code jumped to a random context. The generator has stopped writing and started quoting. Order 2 sits in the middle, with 64% of runs found in the source.

Order	Contexts seen	Only one follower	4-word runs found in source
1	3,288	38%	4%
2	27,494	76%	64%
3	46,929	91%	100%

This is the sparsity problem from Words by the Numbers 4 seen from a new side. With about 74,500 words of source, most three-word contexts were followed by a single kind of word, so the model can only repeat what it saw. A longer memory needs far more text. The trade is general: low order gives variety with poor sense, high order gives sense by copying.

How Good Is the Guess?

Writing text is hard to score by eye, so test the prediction itself. Hold back every fifth documentation topic as a test set, build the counts from the rest, and for each test position guess the next word. Three guessers compete: always say the word that is commonest in the training text; say the commonest follower of the last word; and say the commonest follower of the last two words, falling back to the last word alone when that pair was never seen in training. A guess counts only if it is exactly the right word, so the scores will look low.

import re
from collections import Counter, defaultdict
from pydoc_data.topics import topics

def tokens(text):
    return re.findall(r"[a-z]+(?:'[a-z]+)?", text.lower())

names = sorted(topics)
train = [tokens(topics[n]) for i, n in enumerate(names) if i % 5 != 0]
test = [tokens(topics[n]) for i, n in enumerate(names) if i % 5 == 0]

uni = Counter(w for d in train for w in d)
c1, c2 = defaultdict(Counter), defaultdict(Counter)
for d in train:
    for a, b in zip(d, d[1:]):
        c1[a][b] += 1
    for a, b, c in zip(d, d[1:], d[2:]):
        c2[(a, b)][c] += 1

def predict(prev2, prev1, mode):
    if mode >= 2 and (prev2, prev1) in c2:
        return c2[(prev2, prev1)].most_common(1)[0][0]
    if mode >= 1 and prev1 in c1:
        return c1[prev1].most_common(1)[0][0]
    return uni.most_common(1)[0][0]

total = 0
hits = Counter()
seen2 = 0
for d in test:
    for a, b, c in zip(d, d[1:], d[2:]):
        total += 1
        seen2 += (a, b) in c2
        for mode in (0, 1, 2):
            hits[mode] += predict(a, b, mode) == c
print("training words:", sum(uni.values()), "| test positions:", total)
print("test positions whose 2-word context was seen in training:", f"{seen2 / total:.0%}")
for mode, label in [(0, "always the commonest word"), (1, "most common follower of last word"), (2, "last two words, fall back to last one")]:
    print(f"{label:40} {hits[mode] / total:5.1%}")
# training words: 68787 | test positions: 5719
# test positions whose 2-word context was seen in training: 67%
# always the commonest word                 6.6%
# most common follower of last word        16.5%
# last two words, fall back to last one    29.8%
    

The ranking is the lesson. Always guessing the commonest word is right 6.6% of the time. Using the last word more than doubles that, to 16.5%, and adding the second word with a fallback reaches 29.8%. Even so, the two-word context was seen in training at only 67% of test positions, so a third of the time the guesser had to fall back. A score near 30% sounds poor, but the guesser is choosing among thousands of words in text that is not predictable by design. Guessing the next word is also the job modern language models do, with far bigger models and far more text (general background, not something I checked; check).

Guesser	Right on held-out topics
Commonest word every time	6.6%
Commonest follower of last word	16.5%
Last two words, fall back to last one	29.8%

Common mistakes

Storing followers as a set, which loses the repeats and so the probabilities; forgetting the dead end at the last word of a text, where no follower exists; letting the chain run across the end of one document into the next; raising the order and mistaking copied text for a good model; judging a generator by one lucky sentence rather than by many; testing a predictor on the same text it was built from, which makes it look far better than it is; and treating a fluent sentence as a meaningful one, since the chain knows only which words sit together, never what they mean.

Exercise 1

Write a short invented passage of your own (one or two sentences). Build the follower lists for a first-order chain. Print how many words and distinct bigrams it has, the followers of three chosen words as fractions, the chance of one exact three-word path, and a short generated line.

📄 View solution

Exercise 2

On the documentation text, for orders 1, 2 and 3, generate 2,000 words and report the number of dead-end jumps, the share of steps where the chain had a genuine choice between different followers, and the mean number of followers per context. How does the freedom fall as the order rises?

📄 View solution

Exercise 3

Hold out every fourth documentation topic as a test set. With a first-order model, report how often the right next word is the model's single best guess, how often it is within its three best guesses, and how often the last word was never seen in training.

📄 View solution

Quick Reference

Markov chain (order 1): the next word depends only on the current word; order k uses the last k words
Build: followers[a].append(b) for each pair from zip(words, words[1:]); keep the repeats
Generate: random.choice(followers[word]), repeat; set random.seed(n) to repeat a run
Chance of a path: multiply the step probabilities, e.g. 2/4 × 1/2 = 1/4
Dead end: a context with no follower; jump to a random context
Order trade-off: low order gives variety and nonsense, high order gives fluency by copying (here, 100% of 4-word runs at order 3)
Test fairly: build on some topics, score on held-out ones

Coming next

Words by the Numbers 6 is about style and authorship: function words, vocabulary richness, comparing authors, and the Federalist Papers puzzle.