Memory Prediction Excess (MPE): Quantifying the Value of Historical Information for Stochastic Process Prediction

A Core Question Often Overlooked: How Much Are Historical Observations Actually Worth?

When predicting stochastic processes, we instinctively assume that more history means better predictions. But just how much is this intuition of "more is better" actually worth? Compared to relying solely on a static marginal distribution, how much does past observations actually improve prediction accuracy? This is a question that seems straightforward yet has long lacked precise quantification tools.

A newly published arXiv paper (arXiv:2610.06894v1) introduces a probabilistic quantity called Memory Prediction Excess (MPE), aiming to answer this question from a purely probabilistic perspective. It targets discrete-time, finite-state stochastic processes, measuring the average improvement in prediction accuracy when using the full history compared to using only the static marginal distribution.

Definition and Basic Properties of MPE

The definition of MPE is quite direct: it equals the "expected optimal conditional prediction accuracy" minus the "optimal static prediction accuracy." In other words, one term is the best prediction accuracy achievable with access to the full history, and the other is the best accuracy achievable using only the overall distribution (without any context). The difference between these two is the "net gain" brought by historical information.

The paper outlines several key properties of MPE, which form the theoretical backbone of this measure:

Non-Negativity and Upper Bound

MPE is always non-negative — this aligns with intuition, since additional historical information can only help (or at worst not hurt) optimal prediction. More interestingly, there exists an upper bound that depends on the static accuracy, and this bound is achieved if and only if "the future is almost surely a deterministic function of the past." In other words, memory only achieves its theoretical maximum value when the history completely determines the next state.

Degenerate Cases

The paper also characterizes degenerate cases where MPE equals zero. When history provides no help for prediction, MPE drops to zero, and the process becomes essentially "memoryless" in a predictive sense. Characterizing these boundary cases makes MPE more than just a number — it becomes a diagnostic tool for revealing the underlying structure of a process.

Normalized Version

To enable comparisons across different processes, the authors introduce a normalized MPE taking values in the unit interval [0, 1], serving as a dimensionless measure of "predictive efficiency." This treatment elevates MPE from an absolute quantity to a relative one, facilitating cross-scenario comparisons.

Does More History Always Help? A Proof of Monotonicity

By comparing prediction performance across different history lengths, the paper derives a lower bound and proves an important result: the expected optimal prediction accuracy is monotonically non-decreasing in history length.

This means that mathematically, longer histories never hurt predictive ability — prediction accuracy is monotonically non-decreasing in history length. This provides rigorous probabilistic backing for the engineering intuition that "more information is better," while also raising a more practical question: if longer histories are always (weakly) better, how much history do we actually need to keep?

Finite History and Minimum Memory Length

In real systems, retaining infinite history is neither practical nor necessary. The paper therefore extends the framework to finite-length histories, introducing Finite-History MPE (FH-MPE) to measure the prediction gain achievable when retaining only the most recent observations.

This naturally gives rise to a practically valuable concept — minimum memory length: the minimum amount of history needed to achieve prediction performance equivalent to having the full history. This quantity translates an abstract theoretical measure into an actionable design parameter.

Bound Results for Markov Chains

For finite-order Markov chains, the paper proves that this minimum memory length is upper-bounded by the Markov order. This is a clean and elegant result: for a k-th order Markov process, you need to remember at most the most recent k steps to achieve prediction performance as good as remembering the entire history. This is highly consistent with the definition of the Markov property and validates the internal consistency of the MPE framework.

A k-th order Markov chain is a stochastic process in which the conditional distribution of the current state depends only on the most recent k historical states, and is independent of earlier history. The most common first-order Markov chain (i.e., the standard Markov chain) satisfies the memoryless property: "given the current state, the future is independent of the past." The k-th order generalization allows the system to maintain dependence over a longer sliding window, but the dependency window remains finite and fixed. The paper's conclusion that "the minimum memory length is upper-bounded by the Markov order" is significant because it builds a bridge: the Markov order is a structural parameter of the process, while the minimum memory length is an operational parameter for the prediction task — and here the two are precisely linked. This means that even without knowing the true order of the process, one can estimate the convergence behavior of MPE across different history lengths to reverse-engineer an effective memory cutoff point.

Complementary Relationship with Information-Theoretic Methods

The positioning of MPE is worth noting. The authors explicitly state that MPE and its variants are formulated using conditional probabilities and prediction accuracy, providing a probabilistic perspective on the predictive utility of memory that complements classical information-theoretic approaches (such as mutual information and excess entropy).

Classical information theory typically measures "reduction in uncertainty" in bits, while MPE directly targets "how often predictions are correct" — a metric more closely aligned with actual decision-making. For applications that care about real prediction hit rates rather than abstract information quantities — such as sequence prediction, state estimation, and online learning systems that need to trade off memory costs — this accuracy-centric measure may be more intuitive and easier to interpret.

In classical information theory, Excess Entropy is the closest counterpart to MPE. Excess entropy measures "the amount of information in the past that is useful for predicting the future," in bits, defined as the mutual information between the past and the future. Mutual information more broadly quantifies the degree of statistical dependence between two random variables, also measured in bits. What both of these metrics have in common is that they characterize "how many bits of uncertainty are eliminated," rather than "how many predictions are correct." This distinction is not trivial in practice: a system may gain significantly in the information-theoretic sense (high mutual information), yet show limited improvement in accuracy — for example, when the state space distribution is highly skewed, the optimal prediction strategy almost always guesses the most frequent state, and the bit-level gain from historical information may not translate into improved hit rates. MPE bypasses this "translation loss" by operating directly on the metric that decision-makers ultimately care about.

Significance and Limitations

The value of MPE lies in transforming the vague question of "how much does memory contribute to prediction" into a set of well-defined, provably characterized probabilistic quantities, and deriving practical results such as the minimum memory length. For system designers who need to trade off between prediction performance and storage/computation costs, this framework provides a theoretical foundation.

It should be noted that the paper is currently limited to discrete-time, finite-state stochastic processes. This ensures rigor but also limits the direct scope of applicability. Generalizations to continuous-state and continuous-time processes, as well as estimation methods on real data, remain open questions for future work. As a newly submitted theoretical paper, its practical effectiveness still awaits the test of time.