Markov Chains

Take the first two chapters of Alice’s Adventures in Wonderland, 128 sentences and 16,803 letters once the spaces are gone, and sort every letter into a vowel or a consonant the way Markov sorted Pushkin. A little over a third of them are vowels, 38.14 percent. If the letters were drawn independently, like a coin weighted towards consonants, the chance of a vowel would be 38.14 percent after anything at all, and knowing the letter before would tell us nothing.

It tells us a great deal. After a vowel the next letter is a vowel 14.61 percent of the time, and after a consonant it is a vowel 52.70 percent of the time, so the kind of letter just read moves the chance of a vowel by a factor of more than three and a half.

Two choices were made before any counting. Spaces are dropped, as Markov dropped them, and y is counted as a consonant, which is the usual convention and is wrong for a word like rhythm; a different choice would move every number on the page slightly.

Markov’s way out was to let each letter depend on the letter before it and on nothing earlier. Once we know the current letter is a consonant, the chance that the next is a vowel is 0.5270 whether the consonant followed a vowel, followed two consonants, or opened the sentence. The whole history of the text is allowed to matter only through the one letter it left us at.

P(Xₜ₊₁ = j | Xₜ = i, Xₜ₋₁, …, X₀)  =  P(Xₜ₊₁ = j | Xₜ = i)  =  pᵢⱼ

A sequence that behaves this way is a Markov chain, the letters or whatever else it moves between are its states, and pᵢⱼ is the probability of a step from state i to state j. The claim is one of conditional independence. The letter two places back still predicts the next letter, since it predicts the letter in between, and step 17 measures by how much; what the assumption says is that once the letter in between is known, the one before it adds nothing further.

A second assumption is folded into that equation, and it is easy to miss because it has no symbol of its own. The same pᵢⱼ is used at every position of every sentence, in the first chapter and the third alike, so the chain is homogeneous in time. Step 14 checks it by counting each chapter separately.

With two states there are four probabilities, and they fit in a table whose rows are the letter now and whose columns are the letter next. Each row is a complete answer to the question of what comes next, so each row sums to one, 0.1461 and 0.8539 after a vowel, 0.5270 and 0.4730 after a consonant. Nothing else is learned.

P  =  [ p_VV  p_VC ]  =  [ 0.1461  0.8539 ]
      [ p_CV  p_CC ]     [ 0.5270  0.4730 ]

The convention here is the usual one in probability, rows for where a step starts, and a distribution over the states written as a row that the table multiplies from the right. Some texts, particularly in linear algebra, put the starting state in the columns instead, and every equation on this page would then be transposed with nothing about the chain changed.

Fitting a chain means counting its steps. Every adjacent pair of letters is one observed step from the first letter’s state to the second’s, and each row of counts divided by its total is that state’s row of the table. Nothing is iterated, tuned or searched.

Alice calling her cat is short enough to do with a pencil. Oh my dear Dinah is thirteen letters once the spaces go, and each is marked below as a vowel or a consonant, with the y of my counted as a consonant by the page’s convention.

…

after a vowel       1 + 4 = 5 steps    p_VV = 1 ⁄ 5 = 0.2000    p_VC = 4 ⁄ 5 = 0.8000
after a consonant   3 + 4 = 7 steps    p_CV = 3 ⁄ 7 = 0.4286    p_CC = 4 ⁄ 7 = 0.5714

Across all 128 sentences, vowels start 6,384 transitions and consonants start 10,291. Count where each kind of transition goes, then divide by its row total.

P(vowel | vowel) = 933 / 6,384 ≈ 0.1461
P(consonant | vowel) = 5,451 / 6,384 ≈ 0.8539
P(vowel | consonant) = 5,423 / 10,291 ≈ 0.5270
P(consonant | consonant) = 4,868 / 10,291 ≈ 0.4730

Each row sums to one because it covers every observed destination from that starting state.

p_VV  =  933 ⁄ 6,384  =  0.1461          p_CV  =  5,423 ⁄ 10,291  =  0.5270

…

The division is not a convention. Among every table we could write down, it is the one under which the counted text is most probable. The probability of the text is a product of one table entry per step, and the vowel row enters that product 933 times as p_VV and 5,451 times as 1 − p_VV, so the logarithm of the product, for that row, is a curve in p_VV alone.

log L(p_VV)  =  933 · ln p_VV  +  5,451 · ln(1 − p_VV)

…

The likelihood is largest where its derivative is zero. Equate the two terms and solve for the vowel-to-vowel probability.

933 / p_VV = 5,451 / (1 − p_VV)
933(1 − p_VV) = 5,451p_VV
p_VV = 933 / (933 + 5,451) = 933 / 6,384

The same argument applies to each row separately. A row’s entries appear only in transitions leaving that row’s state. The fitted table gives the observed text a log likelihood of −9,773.73 nats, the largest available under this model.

Counting stops at the end of each sentence. The last letter of one sentence and the first of the next are never counted as a step, because nobody wrote them as one, and each sentence is a separate sequence. That is why 16,803 letters give 16,675 steps, 128 fewer than one unbroken run of letters would give, one for each sentence.

The first letter of each sentence is a second thing the count leaves out. A chain is a table of steps, and a step needs somewhere to start, so the first state of each sequence is taken as given. Where sentences tend to start is a separate distribution over a separate quantity, and a model that wanted it would have to count it separately; the chain on this page never learns it, and when it scores a sentence in Part 5 it scores every letter but the first.

Ask where the chain will be two letters after a vowel. The walk has to pass through a letter in between, which is a vowel with probability 0.1461 and a consonant with probability 0.8539, and from each of those the second step goes by that state’s own row. Adding the two routes gives the chance of a vowel two letters on.

P(vowel two on | vowel now)  =  0.1461 × 0.1461  +  0.8539 × 0.5270  =  0.4713

Doing that for every pair of states at once is multiplying the table by itself, and n steps is the table raised to the nth power. A starting distribution written as a row π₀ is carried n steps by multiplying on the right.

πₙ  =  π₀ Pⁿ          Pᵐ⁺ⁿ  =  Pᵐ Pⁿ

Start one walk at a vowel and another at a consonant and follow the chance of a vowel in each. After one step they are far apart, 0.1461 against 0.5270. After two they have crossed, 0.4713 against 0.3263, after three they have crossed back, 0.3475 against 0.4027, and by the fifth step both are within half a hundredth of 0.3816, which is where every walk ends up and the subject of Part 4.

…

The crossing is not noise. For a two-state chain the gap between a walk and where it settles is multiplied at every step by one number, the table’s second eigenvalue, which for two states is the difference between the two chances of a vowel, and here it is negative.

λ₂  =  p_VV − p_CV  =  0.1461 − 0.5270  =  −0.3808

distance from settled after n steps  =  distance at the start × |λ₂|ⁿ

The sign is the alternation, since a vowel makes a consonant likely and a consonant makes a vowel fairly likely, so the walk overshoots in each direction in turn. The size is the speed, since each step leaves 0.3808 of the remaining distance, 0.6184 at the start from a vowel, 0.2355 after one step, 0.0897 after two, and 0.00004 after ten.

The same question can be asked of a chain over every letter and the space, counted on the same two chapters. There is no single pair of walks to compare now, so for each number of steps the second view of the widget above takes the worst of the twenty-seven starts, the one still furthest from where the chain settles. Distance here is the largest difference, over every set of symbols, between the chance the walk gives it and the chance the settled distribution gives it.

distance(π, σ)  =  ½ Σⱼ |πⱼ − σⱼ|

The worst start for the first four steps is q, which is followed by u 95 percent of the time, so a walk from q knows where it is going for longer than a walk from anywhere else. It is 0.9264 from settled after one step, 0.4918 after two, 0.1580 after three and 0.0442 after four. From the fifth step the worst start is v, and by the tenth the worst distance is 0.00004.

Every walk in Part 3 approached the same place, a chance of a vowel of 0.3816. That distribution has a property that makes it findable without walking. Take it as the starting distribution, carry it one step, and it comes back unchanged, since the vowels turning into consonants are exactly balanced by the consonants turning into vowels.

π P  =  π          Σⱼ πⱼ  =  1

It is called the stationary distribution. For two states the balance can be solved by hand, since the flow from vowels to consonants has to equal the flow back.

π_V × p_VC  =  π_C × p_CV

π_V  =  p_CV ⁄ (p_CV + p_VC)  =  0.5270 ⁄ (0.5270 + 0.8539)  =  0.3816

stationary vowel share = (3/7) / (3/7 + 4/5)
                       = 15/43 ≈ 0.3488
observed vowel share = 5/13 ≈ 0.3846

Repeatedly updating the probability distribution approaches stationarity on a finite irreducible, aperiodic chain. A single sampled endpoint is only one observation, not a distribution. Solving the balance equations finds the stationary probabilities directly.

πP = π
π(P − I) = 0
Σᵢ πᵢ = 1

One balance equation is redundant because every row of the transition matrix sums to one. Replace that equation with the requirement that the probabilities sum to one. When the chain has a unique stationary distribution, the resulting system has one solution.

π (P − I)  =  0,   with one of its equations replaced by   Σⱼ πⱼ  =  1

Whether it has exactly one is decided by which states can reach which, and none of the magnitudes matter. If every state can eventually reach every other, the chain has exactly one stationary distribution, which is the theorem of Perron and Frobenius applied to a table of probabilities, and more generally it has exactly one whenever there is a single group of states that a walk can enter and never leave.

A table with every entry above zero satisfies both, which is one of the things smoothing does, and Part 7 is about the tables that fail.

The chain settles at a vowel with probability 0.3816, and 38.14 percent of the letters it was counted on are vowels. On the letter chain the agreement is as close, the largest gap over all twenty-seven symbols being 0.0019, and the widget draws the settled share of every symbol beside its share of the text.

…

That agreement is almost guaranteed, and it is worth seeing why before being impressed by it. Take the share of steps that start at each letter and multiply it by the table. What comes out is the share of steps that end at each letter, and the two shares differ only by the first and last letter of each sentence, so the text’s own letter shares nearly solve πP = π by construction.

On oh my dear Dinah, a single sentence where the two ends are two of its thirteen letters, the gap is 0.3846 against 0.3488. On 128 sentences it is 0.3814 against 0.3816.

Σᵢ (share of steps starting at i) × pᵢⱼ  =  share of steps ending at j

The informative checks are the ones the construction does not force. The third chapter, never counted, is 39.16 percent vowels, 0.0100 above where the chain settles, and over the letters its largest gap is 0.0097, for d, which the chain settles at 0.0350 and the chapter uses 0.0447 of the time. A walk of 20,000 letters drawn from the chain itself lands within 0.0054 of the settled shares for every symbol.

Step 2 said the same table is used at every position. Count each chapter on its own and the vowel row drifts, a vowel following a vowel 13.96 percent of the time in the first chapter, 15.29 in the second and 17.01 in the third, while the consonant row barely moves, 52.56, 52.85 and 53.41.

Whether that drift is the third chapter having different habits or the ordinary variation in a count of a couple of thousand vowels is a question this chain cannot ask, since it has one table and no notion of position. A chain allowed a different table in each chapter would be a different model, with three times as many numbers to count.

Drawing from a chain is walking it at random. Start at a letter, draw the next from that letter’s row, and repeat. Shannon printed exactly this in 1948, English written by counts with no memory and then with one and two letters of it, and the same exercise on Alice is below, every sample started from the same seed so that the only thing changing is the memory.

…

With no memory the letters come in the right proportions, a great deal of e and of space, and in no order at all. One letter of memory gives something the eye accepts as the shape of English, thing rs bof te an, with real short words turning up by accident because the pairs in them are common. Two letters, which is a chain whose states are pairs of letters, writes then es ing pook all a, and three writes the geotuy of thought, where most of the short words are words.

The samples show what the chain knows without putting a number on it. To measure it, read the third chapter one letter at a time, ask the chain for the probability of each letter given the one before it, and average the logarithm, in bits, over every letter scored. The obvious alternative knows only how common each letter is, and it is the chain’s own stationary distribution used as though every letter were drawn afresh.

bits per letter  =  −(1 ⁄ M) Σ over scored positions of  log₂ P(letter | what the model remembers)

One letter of memory saves 0.8234 bits on every letter of text the chain had never seen, a fifth of what the frequencies alone cost. On Markov’s two classes the saving is 0.0992 bits out of a possible one, a tenth. The positions are a common set, chosen so that every model compared in this Part and the next can score every one of them, and 71 positions of the third chapter are set aside because the two letters before them, or the two ending on them, never occurred together in the first two chapters, which matters to the pair chain of Part 6 and to nothing here.

Step 8 had the chain say that two letters after a vowel the chance of another vowel is 0.4713. The text can be asked the same question directly, by counting every pair of letters two apart. In the first two chapters the answer is 0.3661, and in the third, never counted, 0.3727. The chain is wrong about its own text by more than a tenth, on a question built entirely from the table that text produced.

…

Three letters on the error changes sign, the chain saying 0.3475 and the text 0.4036, and by five letters the two agree to within a few thousandths. That is structure spanning three letters, which no table of pairs can hold.

Part of the gap is not English at all. Grouping twenty-six letters into two classes throws away which vowel and which consonant, and a sequence of classes read off a letter chain is not in general a Markov chain itself. The second view of the widget runs the same check on 20,000 symbols the letter chain wrote, where one letter of memory is true by construction, and the vowel-and-consonant chain still misses two letters on, 0.4560 against 0.4084.

So of the 0.1052 miss on Alice, about half is the grouping and the rest is the text.

The same fact looks different from the chain’s side. Ask the letter chain to predict the third chapter several letters ahead, using the table raised to that power, and score it in bits as before. One letter ahead it scores 3.2906, two ahead 3.9570, three ahead 4.0624, and by six ahead 4.0792, which is the score of the letter shares alone on the same positions.

Within the length of a short word the chain has forgotten what it was reading, which is Part 3’s eigenvalue arithmetic seen on real text. The text has not forgotten, as step 17 showed, and the difference between those two statements is exactly what the one-step assumption throws away.

A chain that remembers two letters needs no new machinery. Make each state a pair of adjacent letters, so the text the becomes the states th and he, and a step from th to he is exactly a prediction of e from the two letters before it. The Markov property holds for pairs as it did for letters, and everything in Parts 2 to 4 applies unchanged, counting included. A chain remembering k letters is a chain whose states are runs of k.

P(xₜ₊₁ | xₜ, xₜ₋₁)  =  P( (xₜ, xₜ₊₁) | (xₜ₋₁, xₜ) )

…

On Markov’s two classes this is cheap, since six classes of memory is only 64 possible states, and the widget scores the third chapter at every length of memory from none to six. Each class remembered helps less than the one before, 0.9651 bits with none, 0.8659 with one, 0.8402 with two, 0.8336 with three, 0.8309 with four and 0.8284 with five.

At six, one step of the third chapter is a run of seven classes the first two chapters never produced, so the chain as counted calls it impossible and gives the whole chapter a probability of zero.

With a smoothing of a half, so that nothing is impossible, the curve turns at three classes, reading 0.8359 there and then 0.8409, 0.8673 and 0.9589, and the longest memory ends up nearly as bad as none. That is the n-grams page’s width trade in miniature, since each longer state is seen fewer times and the invented counts start to outweigh the real ones.

The price of k letters of memory is a table over 27ᵏ possible states, each with a row of 27ᵏ entries. The first two chapters actually produce 27 letters, 363 pairs and 1,982 runs of three, and those are the states each chain holds, since a state never seen gets no row at all.

Longer memory spreads roughly the same number of observed transitions across more states. The average falls from about 774.7 transitions per state with one letter of memory to 10.4 with three. A dense stationary-distribution solve also grows roughly cubically with the number of states.

relative solve work ≈ (1,982 / 363)³ ≈ 163

Moving from two letters of memory to three can therefore multiply the dense solve work by about 160 without providing any additional training text.

The pair chain ought to beat the letter chain on the third chapter, since it knows strictly more. As counted it cannot be scored at all, because 261 of its steps on the third chapter were never counted in the first two, so it needs smoothing, and the widget sweeps how much.

…

At a smoothing of a hundredth the pair chain scores 2.8355 bits against the letter chain’s 3.2438, so two letters of memory are worth another 0.41 bits. At a half it scores 3.9628, and at one it scores 4.4876, worse than the letter shares alone at 4.0677, so a chain that remembers two letters has become a worse model of the chapter than one that remembers none. The letter chain, over the same range, moves only from 3.2436 to 3.2645.

The reason is in the shape of the pair table. Additive smoothing adds the same count to every cell of a row, and a row of the pair chain has 363 cells, one for every pair seen anywhere. After th the next state has to begin with h, and in the first two chapters h was followed by only nine different symbols, so at most nine of those 363 cells can ever be right.

At a smoothing of a half each row is given 181.5 invented steps, against an average of 57.3 real ones, and almost all of the invented ones go to pairs that cannot follow. Drawn at that setting the pair chain writes thaqogsedke umuoumts, and the last sample in step 15 shows the rest of it.

Count a chain on the one word spa. Its classes are C C V, so there are two steps, a consonant to a consonant and a consonant to a vowel, and the vowel ends the word and begins nothing. The vowel’s row of the table is its count of steps to a vowel, zero, divided by its count of steps, also zero, and zero over zero is not a probability. The table does not exist until something is decided.

…

This is not confined to toy words. A chain on the first two chapters remembering three letters has two such states, oud and phy, which occur only as the last three letters of a sentence, one ending she said aloud and the other let s try geography, and nowhere else in 128 sentences.

There are four things anyone can do, and each costs something. Give the stranded state an even row, which invents an observation that it is followed by everything equally. Send it to itself with certainty, which invents a different observation and changes the chain’s structure, since the state becomes a trap that every long walk eventually falls into and that then holds the whole stationary distribution.

Refuse to build the table until text arrives that leaves the state. Or add the same small count to every cell of every row, which gives the stranded row an even spread as a side effect of a choice made for every row at once, and carries the cost Part 6 measured.

Count a chain on banana. Its classes alternate, C V C V C V, so a consonant is always followed by a vowel and a vowel by a consonant, and the table is the flip, ones off the diagonal and zeros on it.

…

The alternating chain has a unique stationary distribution: half vowel, half consonant. Starting from a known consonant never approaches that distribution. The state is certainly a consonant after every even step and certainly a vowel after every odd step.

second eigenvalue = 0 − 1 = −1
magnitude of the remaining-error factor = |−1| = 1

The distribution alternates instead of settling. Starting at the stationary distribution would preserve it, but a known starting state does not converge to it. This chain has period two.

What survives is a weaker statement. Averaged over a long walk, the walk spends half its time at each state, and the widget’s share of time over the first thousand steps reads 0.5 and 0.5. On a periodic chain the stationary distribution means the share of time and nothing about where the walk will be at any particular step. A smoothing of a half breaks the lockstep, since each state can now repeat, and the smoothed chain settles at 0.5122 for a vowel, where every walk arrives.

Count a chain on two words that share no class, rhythm, which is all consonants under the page’s convention, and aeiou. A consonant only ever follows a consonant and a vowel a vowel, so the table is the identity, and a walk that starts in one class never leaves it.

…

Each class on its own is a stationary distribution, all consonant or all vowel, and so is every mixture of the two, a third and two thirds, a half and a half, any split at all, since each part stays where it is. The stationary distribution is no longer a single thing to be solved for, the linear system of step 12 has a whole line of solutions, and the chain’s long run depends entirely on where it starts.

What breaks uniqueness is two closed groups, and the word asks shows that reducibility alone does not. Its classes are V C C C, so the vowel is left once for a consonant and never returned to, and it cannot be reached from the consonant, which makes the chain reducible. It still has exactly one stationary distribution, all of it on the consonant, because only one group of states is closed, and the vowel the word started from holds no share at all.

Smoothing joins the two words’ classes into one group again, and the smoothed chain settles at 0.4545 for a vowel.

Beside the three cases above there are other places where the definition has nothing to say, or says something that has to be decided before it means anything. Each row is a fact about the mathematics of a counted chain, and several carry a choice that somebody has to make.