Can it use different memory lengths in one model?

Yes. That is the defining feature of a variable-order context representation.

Does it remember the entire past?

Not in the usual bounded-context formulation. It uses suffixes up to a specified or learned limit.

What happens with an unseen context?

The implementation must specify fallback, smoothing, or mixture behavior. An unsupported long context should not silently produce an unjustified zero probability.

AI Glossary / Mathematics and optimization / Intermediate

Variable-order Markov model

Definition

A variable-order Markov model predicts the next symbol in a sequence using a context whose length depends on the recent history. Some histories need only a short suffix, while others use a longer one. This allows the model to represent selected longer dependencies without building a separate high-order distribution for every possible history.

What it means

A fixed-order Markov model always conditions on the same number of recent symbols. If that order is too short, it can miss useful patterns; if too long, many contexts may have little data. Variable-order modeling uses different memory lengths where appropriate.

The memory is an explicit statistical context, not a claim about human recollection. The model normally predicts symbols from a defined alphabet, such as event categories or characters. Different algorithms learn, prune, smooth, or combine contexts in different ways, so the term describes a family rather than one universal training procedure.

How it works

Collect counts or other evidence for candidate suffixes up to a selected maximum depth. Estimate next-symbol probabilities and assess whether extending a shorter context provides enough useful information to justify the added complexity.

A context tree can organize the suffixes. During prediction, a specified selection or mixture rule uses relevant recent history to obtain a distribution over the next symbol. Short or unseen histories need a defined fallback or smoothing policy.

Some methods select a single context model; others, such as context-tree weighting approaches, combine predictions across models. Sequence probabilities follow by multiplying successive conditional probabilities, including an initial-history convention. Training and evaluation must preserve sequence boundaries and prevent future observations from leaking into next-symbol predictions.

Three practical examples

1. Text compression research: adapt next-character probabilities to the amount of recent context that is useful and sufficiently supported.

2. Event-sequence prediction: model recurring categorical workflows where some event patterns depend on one previous event and others on several.

3. Biological sequence analysis: compare variable-length context models with fixed-order baselines for sequence scoring, under suitable validation and alphabet definitions.

Think of it this way

Think of asking how much of a conversation you need to hear before predicting the next response. A short ending can sometimes be enough; another ending requires an earlier phrase to resolve ambiguity.

The analogy stops at statistical prediction. A variable-order Markov model does not thereby understand the conversation, and its finite contexts cannot represent every long-range relationship. Extra context is useful only when the learning procedure can estimate its probabilities reliably.

Worked example

Consider an original binary model with contexts 0, 01, and 11, written in chronological order. Use P(next=1|0)=0.2, P(next=1|01)=0.8, and P(next=1|11)=0.4. Each probability for next=0 is its complement.

Every history of length at least two has exactly one applicable context: if it ends in 0, use the one-symbol context 0; if it ends in 1, inspect the previous bit to distinguish 01 from 11. The context set is therefore complete for such histories and no listed context is a suffix of another.

For history 110, the prediction for 1 is 0.2. For 101, it is 0.8. For 011, it is 0.4. The model uses one or two symbols depending on the suffix, despite having maximum order 2.

Starting with history 10, calculate the probability that the next two symbols are 1 then 0. The first probability is 0.2 because the history ends in 0. After appending 1, the context is 01, so the probability of 0 is 1−0.8=0.2. The conditional probability of the two-symbol continuation is 0.2×0.2=0.04.

This is a fully specified teaching model, not probabilities fitted from observed data or a claim that this context tree is optimal.

Illustrative case study

Fictional case: Moss Operations analyses sequences of categorical service events. A first-order model misses an important distinction between two histories ending in the same event, while a full third-order model contains many rarely seen contexts.

Analysts compare a variable-order model using held-out complete sequences and next-event log loss. They inspect unseen-context behavior and avoid joining the end of one customer's sequence to the beginning of another's. The scenario illustrates a model-comparison workflow without inventing predictive gains or operational outcomes.

Common misconceptions and mistakes

Variable order does not mean choosing a longer context whenever one is available. Rare long contexts can produce unreliable estimates, and some algorithms mix rather than select contexts.

Do not confuse the model with a hidden Markov model: variable-order history and hidden latent states are different mechanisms, though combinations exist.

A context tree's edge-reading convention matters. Some software stores recent symbols first, while written strings usually follow chronological order. Reversing this convention silently changes which histories a node represents and can invalidate an otherwise plausible example.

Business use

The approach offers a compact way to model categorical sequence regularities with interpretable contexts. It can be useful when data volume supports selective memory but not an enormous fixed-order table.

Choose the alphabet, session boundaries, maximum depth, smoothing, and stopping rules deliberately. Evaluate log loss or another task-appropriate measure on independent sequences and compare with a simple baseline. Monitor drift, because a context that predicts well in one operating period may become misleading when the underlying process changes.

Check your understanding

Why does history 110 use context 0, while history 101 uses context 01 in the worked model?

Answer: The listed contexts match suffixes. A final 0 is already a complete context, whereas a final 1 requires inspecting the preceding bit to choose between 01 and 11.

Related terms

Conditional probability
Smoothing
Context tree weighting
Variable-order Bayesian network
Markov model
context tree
prediction suffix tree
sequence likelihood
fixed-order model

Learn next

List all two-bit histories and map each to the worked model's context. Compute several continuation probabilities by updating the suffix after every new symbol. Then fit a small context model with smoothing and compare its held-out log loss with fixed first- and second-order alternatives before increasing the maximum depth.

Sources

Primary source: Begleiter, El-Yaniv and Yona, “On Prediction Using Variable Order Markov Models”, https://arxiv.org/pdf/1107.0051 . Context-tree, suffix-set, and probabilistic suffix-tree discussions were read. The complete three-context example and continuation probability are independently constructed; no training run or comparative performance result is claimed.

Previous: Variable-order Bayesian network Next: Variable sampling fraction