AI Glossary / Probabilistic machine learning / Intermediate
Higher-order Markov model
Definition
A higher-order Markov model predicts the next state of a sequence using more than one preceding state. An order-k model assumes that the most recent k states contain all the historical information needed for its next-state probability distribution.
What it means
A first-order model looks only at the immediately preceding state. A second-order model can distinguish two histories that end in the same state but have different states just before it.
This extra memory can represent patterns that a shorter context misses. For example, the next step after “review” might differ depending on whether the previous step was “submission” or “revision.” The model treats those recent histories as distinct predictive contexts.
Higher order is an assumption about conditional dependence, not a guarantee of deeper understanding. It still discards history beyond its window. The model may be appropriate as a deliberate approximation even when the real process has longer memory.
How it works
For order k, the defining restriction is P(Xt | all earlier states) = P(Xt | the previous k states), within the model. A tabular version stores a next-state distribution for each possible k-state history.
Training can estimate transitions from counts, with smoothing or other regularization to handle sparse histories. Starting a sequence also requires an initial-history distribution or a documented boundary convention.
An order-k process can be represented as a first-order process over expanded states containing k consecutive original states. The expanded state shifts forward whenever a new observation arrives. This transformation changes the representation, not the amount of history the model uses. Many transitions between arbitrary expanded states are impossible because their overlapping histories must agree.
Three practical examples
- A workflow predictor distinguishes what follows review after an initial submission from what follows review after revision.
- A trigram language model predicts a token using the previous two tokens, making it second order in this sense.
- A sequence analyst compares one-step and multi-step history models for recurring equipment-status patterns.
Think of it this way
Think of keeping the last few cards from a moving sequence on the desk before guessing the next card. Two sequences with the same newest card can still suggest different guesses if the earlier cards differ.
The analogy concerns the information window. It does not imply that real events are produced by a card game or that remembering more cards always improves a prediction when training data are limited.
Worked example
Why the extra state can matter
Consider an invented binary sequence with states 0 and 1. In training data, the history 01 is followed by 1 on eight occasions and by 0 on two occasions. The history 11 is followed by 1 on two occasions and by 0 on eight occasions.
A second-order maximum-likelihood estimate gives P(next = 1 | 01) = 8/10 = 0.8 and P(next = 1 | 11) = 2/10 = 0.2.
A first-order count model pools these histories because both end in 1. For these twenty relevant transitions, it estimates P(next = 1 | current = 1) = (8 + 2)/(10 + 10) = 0.5. The longer context preserves a difference that pooling removes.
In the expanded-state representation, history 01 can transition to 11 with probability 0.8 or to 10 with probability 0.2. It cannot transition directly to 00, because its final 1 must become the next history's first element.
These are unsmoothed estimates from invented counts, not evidence that order two will generalize better. Separate test sequences are needed to compare predictions.
Illustrative case study
Fictional case: forecasting support-ticket steps
A fictional service team predicts the next stage of a support ticket. A first-order model treats all tickets currently in review alike. A second-order model distinguishes tickets arriving from new submission from those returning after revision.
The team compares both models on later, separately held-out tickets. It checks whether the extra context helps frequently observed paths and how it behaves on rare paths. It also prevents events from one ticket being joined to the beginning of another.
The team keeps the higher-order model only if its practical benefit justifies the added complexity. The case illustrates a comparison procedure without assuming a performance improvement.
Common misconceptions and mistakes
A trigram model is not third order under the usual history-length convention. It uses two preceding tokens to predict the third, so it is second order. The n-gram size includes the predicted token.
Higher order does not automatically mean a hidden Markov model. Hidden states are a separate modeling choice; an observed-state sequence can also have higher-order dependencies.
More context increases the number of potential histories and can leave little evidence for each. An unrestricted model with S states and order k has S to the power k history rows, each with S probabilities summing to one. Structure and parameter sharing can reduce this burden.
Business use
Use a higher-order model when recent path information plausibly changes the next event and there is enough data to estimate those differences. Define sequence boundaries, event labels and treatment of missing observations before fitting transitions.
Compare held-out probability or task-specific performance against a lower-order baseline. Inspect rare histories and specify the fallback for unseen ones. If process changes make old transitions unreliable, extending the window alone will not solve the problem. Monitor whether the model's historical assumptions remain suitable.
People also ask
Can it use the entire past?
A fixed-order model uses only its specified recent window for the next-state distribution. Other sequence models can use history differently.
Can it be written as first order?
Yes, by expanding the state to contain the required history, while preserving overlap constraints.
Does increasing k always help?
No. It can capture useful dependencies but also increase sparsity, estimation uncertainty and computational cost.
Check your understanding
For a three-state unrestricted second-order model, how many possible two-state history rows exist, and how many free next-state probabilities does each row have?
Answer: There are 3 × 3 = 9 rows. Each has three probabilities summing to one, giving two free values, or eighteen transition parameters in total before accounting for initial conditions or extra structure.
Related terms
- Markov property
- Markov Chain
- N-gram
- Hidden Markov model
- Smoothing
- sequence modelling
- state-space model
Learn next
Convert a small second-order chain into expanded first-order states. Then compare raw count estimates with smoothed estimates when a relevant history appears only once or never appears in training.
More in Probabilistic machine learning
- Hierarchical softmax - Hierarchical softmax represents a probability distribution over many output classes by arranging them as leaves of a tree and multiplying conditional branch...
- Hierarchical variational autoencoder - A hierarchical variational autoencoder is a variational autoencoder whose generative model contains multiple dependent layers or groups of latent variables.
- Hierarchical variational posterior - A hierarchical variational posterior is an approximate posterior distribution constructed with additional layers of random variables or randomized...
- Horseshoe distribution - The horseshoe distribution is a continuous probability distribution commonly used as a Bayesian shrinkage prior for sparse signals or coefficients.
- Hybrid generative-discriminative training - Hybrid generative-discriminative training combines learning about the distribution of data with learning to predict a target from inputs.
- Implicit neural network layer - An implicit neural network layer defines its output through conditions that the output must satisfy, such as an equation, fixed point or optimization problem.
Sources
Author-written technical reference: Jurafsky and Martin, Speech and Language Processing, chapter 3, N-gram Language Models, on finite-history Markov assumptions and count estimation: https://web.stanford.edu/~jurafsky/slp3/3.pdf
The binary transition counts and support-ticket case are original teaching examples.
Previous: Higher-order logic Next: Highly adaptive lasso