A Markov chain is a random process that moves between states, and the probability of each next state depends only on the current state, not on how the process got there. Three things fully describe it: a state space, a transition matrix of probabilities between states, and a starting distribution. Shannon’s 1948 paper modelled English text as generated by an ergodic Markov process. Is a large language model a Markov chain too? Formally, yes. With a finite vocabulary and a finite context window, an autoregressive model is equivalent to a Markov chain whose states are every possible window of tokens. Zekri et al. connect that equivalence to failures seen in practice, such as repetitions and incoherent replies at high temperature.
What counts as a state in a Markov chain?
A state is what the process holds right now, and it alone sets the odds of what happens next. Powell and Lehe’s illustration models a baby’s behaviour with states such as “playing”, “eating”, “sleeping” and “crying”, which together form the state space. In the classic drunkard’s walk the state is a position on the number line: from 5, the walk moves to 4 or 6 with probability 0.5 each, whether it arrived at 5 from 4 or from 6.
That is the Markov property in practice: a prediction made from the present state is as good as one made from the full history. Many applications use finite or countably infinite state spaces, which have a simpler statistical analysis.
The property sounds restrictive, but a finite span of history fits inside a well-chosen state. Tomorrow’s weather can depend on both yesterday and today if each state becomes a two-day sequence, giving a nine-state model at the price of an exponential increase in states. More generally, a process that is not Markovian can often be given a Markovian representation by widening what “the current state” contains, as with an autoregressive time series of order greater than one. Keep that trick in mind, because it is how an LLM becomes a Markov chain.
When the system is not just observed but steered by actions, the same idea becomes a Markov decision process, the setting behind reinforcement learning agents that learn by trial and error.
How a Markov chain transition matrix sets next-step probabilities
A transition matrix lists every state once as a row and once as a column, and each cell holds the probability of moving from the row’s state to the column’s state. Its entries are non-negative and each row sums to 1, so every row is a probability distribution over next states (a “stochastic” or “row-stochastic” matrix).
Prediction is matrix multiplication. Multiplying today’s distribution, written as a row vector, by the matrix P gives tomorrow’s distribution. The probability of going from state x to state y in t steps is the (x, y) entry of P raised to the power t, which holds when the chain is time-homogeneous, meaning P is the same at every step. As Hayes puts it, P predicts tomorrow, P² the day after, P³ three days out, and the whole future unfolds from that one matrix.
Worked example: a two-state weather chain, step by step
Healey’s text-generation tutorial starts from a weather chain: if it is sunny, there is a 90% chance it stays sunny and a 10% chance of rain tomorrow; if it is rainy, the odds are 50/50.
| From \ To | Sunny | Rainy |
|---|---|---|
| Sunny | 0.9 | 0.1 |
| Rainy | 0.5 | 0.5 |
Two days ahead, square the matrix. Starting sunny, the chance of sun in two days is 0.9 × 0.9 + 0.1 × 0.5 = 0.86, and of rain 0.9 × 0.1 + 0.1 × 0.5 = 0.14. Starting rainy, sun in two days is 0.5 × 0.9 + 0.5 × 0.5 = 0.70 and rain 0.5 × 0.1 + 0.5 × 0.5 = 0.30. Both rows still sum to 1, as they must.
The long-run answer comes from solving π = πP. For sun: π_S = 0.9 π_S + 0.5 π_R, so 0.1 π_S = 0.5 π_R and π_S = 5 π_R; with π_S + π_R = 1, the stationary distribution is (5/6, 1/6), roughly 0.833 sunny and 0.167 rainy. The two-step rows (0.86 and 0.70 for sun) are already closing in on that 0.833 from either side.
What is a stationary distribution, and why should a text generator care?
A stationary distribution π is a row vector of non-negative entries summing to 1 that the transition matrix leaves unchanged. Equivalently, π is a left eigenvector of the row-stochastic matrix with eigenvalue 1, which is always the matrix’s largest left eigenvalue. The terms equilibrium, stationary and steady-state distribution all mean the same thing.
Existence and convergence are separate questions. A finite chain that is irreducible (any state can reach any other) has a unique stationary distribution. For the chain to actually converge to it, so that the rows of P^k approach a rank-one matrix with every row equal to π, it must also be aperiodic. The Cambridge lecture notes use a two-state chain with invariant distribution (1/2, 1/2) to show what goes wrong when aperiodicity fails. Shannon wrote the same equilibrium condition for language sources in 1948 and noted that, in the ergodic case, the state probabilities approach equilibrium from any starting condition.
Read π as the long-run share of time the chain spends in each state, the interpretation behind ranking web pages by a random surfer. Hayes draws out the consequence: run the system long enough and the probability of a given state no longer depends on where it started.
For an LLM viewed as a Markov chain, the stationary distribution is independent of the input prompt. How long “long enough” is depends on the mixing time, the number of steps needed to come within a set distance of π. A slowly mixing chain stays near its initial state and explores little of its state space; a rapidly mixing one forgets where it began.
How does a Markov chain generate text? The “eau” example
A Markov text generator treats recent characters or words as the state and samples the next one weighted by its frequency in a source text. Hayes describes a kth-order character model in which each state is a sequence of k characters and the transition probabilities are weighted by how often each character follows that sequence. In his source poem, the sequence “eau” appears 27 times: 18 times it is followed by “t” (as in “beauty”), four times by “x” (as in “Bordeaux”), with four other possible sequels. So from the state “eau”, the next state is “aut” with probability 18/27 ≈ 0.667.
The mechanics are simple: given a k-letter seed, sample the next character from that state’s row, drop the leftmost letter, append the new one, and repeat. Word-level bigram generators use the same technique. Jurafsky and Martin describe bigram generation as sampling a first word after the sentence-start token, then a bigram starting with that word, and so on. The Mark V. Shaney program used word triplets from a sample text, with repeated triplets counted separately so that frequent sequences are proportionally more likely.
Order controls quality, and Hayes’s results show the trade-off clearly. A first-order character model produces gibberish, third order is mostly pronounceable, fifth order consists almost entirely of real words, and by seventh order whole phrases are lifted from the original text. Healey reaches the same judgement at word level: a state size of one is often too random, two is a good starting point, and higher can reproduce the corpus too closely.
The cost of a longer memory: states grow as V^k
Each extra step of memory multiplies the parameter count by V. A Markov bigram model over a vocabulary of size V has on the order of V² parameters and a trigram model V³; each increase in order multiplies the count by V.
Two problems follow. The parameter count grows exponentially with order, and a counted model cannot generalise to sequences it never saw; Jurafsky and Martin name both as the problems neural language models were built to solve. Any finite corpus misses perfectly acceptable word sequences, which maximum-likelihood estimates then assign zero probability.
Is an LLM a Markov chain, or does the comparison break down?
The honest answer has two halves. Our view: formally an LLM is a Markov chain, and that framing is a useful lens on long-run decoding behaviour, but it is a poor mental model of how the model computes its next-token probabilities, because the state space is astronomically large and the transition function is learned rather than tabulated.
The formal answer: yes, over the context window
Zekri et al. (2024) show that an autoregressive model with vocabulary size T and context window K is equivalent to a Markov chain with a sparse, block-structured transition matrix of size Σ_{i≤K} T^i, of order T^K, capturing every possible output for every input the vocabulary and window allow. The insight is that, however unbounded generation looks, a finite vocabulary and window make all possible input sequences enumerable. This is the state-widening trick from earlier: the state is the whole token sequence, not the last token.
The structure is worth following. Short sequences grow by one token per step until the window is full; after that, the model must drop the first token to continue, and transitions among full-length sequences form a block of size T^K × T^K. Sequences shorter than K are transient, while the full-length ones form a single recurrent, ergodic class. In Zekri et al.’s analysis, which assumes plain softmax sampling at positive temperature, every vocabulary token receives non-zero probability at each step, and the chain is ergodic with a unique stationary distribution.
Zekri et al. state that the true stationary distribution is intractable because of the size of the state space.
What the Markov view explains: loops and temperature
The Markov framing offers an account of repetition. Zekri et al. argue that the stationary distribution is independent of the prompt, and that reaching it should send the model into a loop of repetitions, a behaviour that occurs frequently in practice and is why repetition penalties exist. Ildiz et al. (2024) reach repetition by a different route: they map self-attention to a context-conditioned Markov chain that reweights a base transition matrix, and show that its non-mixing nature collapses generation onto a limited subset of tokens, offering a mathematical explanation for repetitive text. The two accounts locate the cause differently (one in convergence to equilibrium, the other in a failure to mix), which is a sign the theory is not settled.
Zekri et al. argue that raising temperature speeds convergence to the stationary distribution and reduces coherence; their earlier version made the same prediction from the other side, expecting lower temperatures to slow convergence. One study of Markovian generation chains treated sentences as states and a prompted model as the transition operator, feeding each output back as input. Under greedy decoding, trajectories typically fell into fixed points or short cycles within a few steps, while sampling-based decoding produced longer phases of new sentences before any repeat. Higher temperature tended to delay or prevent entry into small recurrent sets. Over 500 iterations the chains had not settled into a stationary regime, and more than two-thirds were still producing never-seen sentences between steps 451 and 500.
These results do not strictly contradict each other: one is a bound on a token-level chain over full windows, the other an observation of a sentence-level chain over a finite horizon. We weight the empirical finding more heavily for practical decisions: greedy decoding loops quickly and sampling postpones it.
Where the simple analogy breaks
The transition function is learned, not counted. Neural language models project words into a continuous space where words with similar contexts get similar representations, which is how they avoid the exponential parameter growth and zero-count problems of n-grams. (The mechanics behind that are covered in how neural networks underpin generative AI.) Zekri et al. make the gap concrete: an LLM’s sample complexity is linear in vocabulary size T, against O(T^K) for the frequentist approach of filling in a transition table by counting.
The state is the whole token window, up to K tokens. Transformers use attention to look back over the entire context, and in the Ildiz et al. framing the prompt reweights the transition matrix while positional encoding scales transition probabilities by position. Anything that changes what sits in the window changes the state, and putting retrieved text there is what retrieval-augmented generation does.
Transformers also learn Markov chains in stages. Trained on in-context Markov chain tasks, they pass from uniform predictions to in-context unigram statistics and then, after a rapid phase transition, to the correct bigram solution, using statistical induction heads that approach Bayes-optimal next-token probabilities. The 2024 paper Attention with Markov found that single-layer transformers trained on first-order chains often get trapped in local minima that represent the unigram distribution, while models with two or more layers reliably reach the true bigram kernel.
Decoding settings change the effective chain. Temperature and top-p redistribute transition mass, and sampling enlarges the set of reachable next steps compared with greedy decoding. Varying the prompt across iterations makes the kernel time-inhomogeneous, which can be cast as a time-homogeneous chain by adding the prompt to the state. Jurafsky and Martin note that natural language itself is not stationary, so statistical models of it give only an approximation.
Markov chain model vs LLM, side by side
| Aspect | Classic Markov chain text model | LLM viewed as a Markov chain |
|---|---|---|
| State | Last k characters or words | Entire token window, up to K tokens |
| Number of states | Up to V^k; parameters multiply by V per order | Of order T^K |
| Where transition probabilities come from | Counted frequencies from a corpus | A trained network’s output over the vocabulary |
| Unseen contexts | Zero probability without smoothing | Generalises through continuous representations |
| Stationary distribution | Computable by solving π = πP | Exists and is unique, but intractable |
| Typical failure | Gibberish at low order, copying at high order | Loops under greedy decoding; sampling delays them |
| Where it fits | Fast, simple generation with limited coherence | Generation that attends over the entire context |
Diffusion image models use a Markov chain as well, in the forward process that adds noise step by step; how the forward and reverse processes work is a separate subject.
Using the Markov lens on a model that repeats itself
One practical use of all this is diagnostic. When a deployed model starts cycling through the same phrases, check the decoding configuration first (greedy versus sampling, temperature, top-p, repetition penalty), since those settings redistribute transition mass. In one study greedy decoding entered short, model-specific cycles after few steps, and repetition penalties exist because many LLMs loop in practice.
What the lens cannot yet tell you is which mechanism produces the loops: convergence towards a prompt-independent equilibrium or a failure to mix. Until that is settled, treat the Markov framing of an LLM as a source of good questions about decoding rather than a model of how the network thinks.