A Markov chain is a random process that produces one symbol after another — a sequence of letters, a stream of packets, consecutive frames of video — where each next symbol can depend on the current one but on nothing further back. A random process that produces symbols this way almost never has independent symbols, and Markov chains are the simplest honest model of that dependence; Chapter 8's entropy rate is built directly on top of one.
"Unit memory" is the whole idea, and it's less restrictive than it sounds. A board game where your next move depends only on which square you're standing on right now — not on how you got there — is a Markov chain, even though the full game history obviously mattered to get you to that square. The square itself already summarizes everything about the past that's still relevant. Tomorrow's weather depending only on today's weather (not on last week's) is the same idea: today is a complete-enough summary of "how did we get here" for predicting tomorrow, even though it clearly isn't a complete summary of the whole week.
The transition matrix is just a lookup table wearing matrix notation: column j lists every place you could go next, given you're currently in state j, and how likely each destination is.
A discrete random process is a sequence of random variables \{X_i\}_{i=1}^{\infty}, all drawn from the same finite set of possible values (the states). The process is a Markov chain if it has unit memory: the next state depends on the current state, but on nothing further back — P(X_{n+1}=x_{n+1} \mid X_n=x_n, X_{n-1}=x_{n-1}, \ldots, X_1=x_1) = P(X_{n+1}=x_{n+1}\mid X_n = x_n). When this conditional distribution doesn't depend on n either, the chain is stationary (or time-homogeneous), and it's fully described by one transition matrix P, where P_{ij} is the probability of moving to state i next, given the chain is in state j now. Each column of P sums to 1 — from any given state, the chain has to go somewhere.
Weather as a two-state chain
Press Play — watch the distribution settle into a fixed steady state no matter which state it started in.
Loading interactive…
Worked example
Reading a transition matrix
-
1
A three-state chain (states A, B, C) has transition matrix P = \begin{pmatrix} 0.5 & 0.2 & 0 \\ 0.5 & 0.6 & 0.4 \\ 0 & 0.2 & 0.6 \end{pmatrix}. If the chain is currently in state B, what's the probability it moves to state A next? Confirm the matrix is a valid transition matrix.
-
2
Read the column, not the row. P_{ij} is "probability of i next, given j now," so "currently in B, moving to A" is row A, column B: P_{AB} = 0.2. To check validity, each column must sum to 1: column A is 0.5+0.5+0=1, column B is 0.2+0.6+0.2=1, column C is 0+0.4+0.6=1.
-
3\boxed{P(\text{A next} \mid \text{B now}) = 0.2, \text{ and all three columns sum to 1}}
One step of the three-state chain, entry by entry
Step through P times the starting distribution (all mass in state A) — confirm the result matches column A of P exactly.
Loading interactive…
Markov chain or not?
Sort each process by whether the Markov (unit-memory) property genuinely holds.
Loading interactive…
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
What this task checks
Structure checked automatically. Whether your ideas are convincing isn't graded, so reread with the checklist.
The compiler says
A model answer
Correct answer
Also accepted:
Why
Why
Where this goes next
Chapter 8 defines the entropy rate of a Markov source directly from this section's transition matrix P: a Markov source has strictly less entropy per symbol than an i.i.d. source built from the same single-letter frequencies, and the gap is computed from P itself. That is also why text compressors and predictive keyboards, which model letter-to-letter dependence ("q" is followed by "u" almost every time in English), beat ones that treat each letter as independent.
Check your understanding (counts toward your progress)
The 'unit memory' property of a Markov chain means:
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
That's the OPPOSITE of unit memory — a general (non-Markov) process can depend on the whole past.
Nothing prevents a Markov chain from revisiting states — most do, repeatedly.
A Markov chain's state probabilities can be very unequal; unit memory is about dependence, not uniformity.
Why
Unit memory means P(X_{n+1}\mid X_n, X_{n-1},\ldots) = P(X_{n+1}\mid X_n) — only the current state matters for what comes next.
P_{AB} in a transition matrix represents:
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
That's P_{BA}'s meaning — the row/column roles are swapped from what you picked.
Why
By this course's convention, P_{ij} is the probability of moving TO state i NEXT, GIVEN state j NOW — so P_{AB} reads 'A next, given B now'.
Read the subscript convention literally: P_{ij} names the destination state i first and the starting state j second — match P_{AB} against that pattern.
A language model predicts the next letter using the current letter AND the previous letter (a two-letter window). Is this a (first-order) Markov chain on individual letters?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
'Recent' isn't the test — unit memory specifically means only the SINGLE current state, not a window of several.
Not every language model is Markov chains — only ones whose next-symbol distribution depends on exactly one previous state qualify.
The property either holds structurally for the whole model or it doesn't — it's not something that varies letter pair by letter pair.
Why
A first-order Markov chain's next state depends on exactly one previous state. A two-letter window is a longer memory — it CAN be turned into a first-order chain by redefining the state as a letter-PAIR, but as stated over single letters, it isn't first-order Markov.
Ask specifically what determines the NEXT letter here — is it a single current state, or something wider than that single state?
A transition matrix's column for state j has entries 0.6, 0.1, and an unknown third entry. What must the third entry be for P to be a valid transition matrix?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Every column of a transition matrix must sum to 1 (the chain has to go somewhere from state j): 0.6+0.1+x=1 \Rightarrow x=0.3.
Correct answer
Also accepted:
Why
Every column of a transition matrix has to sum to exactly 1 — set up that equation with the two known entries and the unknown third one.
Practice: Markov chains (5 problems · doesn’t affect your progress)
An autocomplete model predicts the next word using ONLY the current word (not any earlier words). Does this satisfy the Markov (unit-memory) property?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Whether it's realistic for language isn't the test — structurally, conditioning on exactly the current word alone is unit memory by definition, whatever the resulting prediction quality.
Vocabulary size has nothing to do with the unit-memory property — that's about how many PAST states the next state depends on.
Unit memory is about how much history matters, not about whether the process is deterministic or random.
Why
Conditioning the next word on exactly the current word, and nothing further back, is precisely the unit-memory definition — the model is Markov, whether or not it's a realistic language model.
Yes — the next state depends only on the current state
A transition matrix's column for some state has entries 0.45, 0.35, and an unknown third entry. What must the third entry be?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Every column must sum to 1: 0.45+0.35+x=1 \Rightarrow x=0.2.
Correct answer
Also accepted:
Why
A three-state chain (X, Y, Z) has transition matrix P=\begin{pmatrix}0.4&0.1&0.3\\0.3&0.6&0.2\\0.3&0.3&0.5\end{pmatrix} (rows and columns both ordered X, Y, Z, so P_{ij} is i next given j now). Given the chain is currently in state Y, what's the probability it moves to state Z next?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
'Currently Y, moving to Z next' is row Z, column Y: P_{ZY}=0.3.
Correct answer
Also accepted:
Why
Read the column for the CURRENT state (Y), then pick out the row for the destination you want (Z) — not the other way around.
A weather model's tomorrow depends on both today AND yesterday's weather (a two-day window), so it isn't first-order Markov on single days. If you instead define a NEW state as the ordered pair (yesterday's weather, today's weather), is the resulting process first-order Markov on these pair-states?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Pairing states is exactly the standard fix for this kind of violation — it folds the extra history into the current state itself.
The pairing trick works for any finite state set, not just a two-state one — nothing about it depends on there being only two weather states.
The next pair-state follows immediately from the current pair-state, one step at a time — no extra delay is needed.
Why
Redefining the state as the pair (yesterday, today) folds the entire two-day dependency into a single current state — moving to the next pair-state depends only on that current pair, restoring unit memory at the cost of a larger state space.
Yes — tomorrow's pair state depends only on today's pair state, since it's built from exactly the two days the original model needed
A packet-delivery chain has a state 'delivered' that, once entered, is never left — its column in P has a single 1 (staying in 'delivered') and 0s everywhere else. Does this column still satisfy the transition-matrix requirement that each column sums to 1?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Nothing about the rule requires the mass to spread across multiple states — it only requires the column's entries to add up to 1.
A state that's never left (an absorbing state) is a perfectly ordinary, valid part of a Markov chain.
The column-sum rule is entirely a per-column arithmetic fact — it doesn't depend on how many states the chain has overall.
Why
The column-sum-to-1 rule only requires the chain go somewhere from that state next, and 'somewhere' is allowed to be back into the same state — a column of all zeros except a single 1 in its own row still sums to exactly 1, so an absorbing state is a perfectly valid part of a Markov chain.
Yes — 1+0+0+\cdots=1, same requirement as any other column