PaperlayerView exact revision on arXiv

Source-linked AI summary

Memory Prediction Excess: A Probabilistic Quantity for Predictive Gain and Memory Length in Stochastic Processes

Jiahao Jiang

arXiv:2610.06894v1stat.MLcs.ITcs.LGmath.ITmath.PR

TL;DR

The paper asks how much past information improves the probability of correctly predicting the next state. It defines MPE as the gain in optimal accuracy from using the full history rather than the static marginal, and extends the measure to truncated histories. It characterizes bounds and memory-length behavior, including a Markov-order bound on the minimal memory length for finite-order Markov chains.

  • Problem

    The paper examines how much past information can improve next-state prediction, a question complementary to measures of information content and flow and to stochastic prediction frameworks.

    Source: §1 · p. 2

  • Method

    For discrete-time finite-state processes, the paper defines MPE as expected optimal conditional accuracy given the full history minus optimal static accuracy, then extends it to finite-length histories.

    Source: §1 · pp. 4–5

  • Results

    The paper characterizes MPE bounds and degenerate cases, establishes monotonicity of expected optimal accuracy with history length, and shows that finite-history MPE saturates at the Markov order for finite-order Markov chains.

    Source: §1 · p. 5

  • Takeaways & Limitations

    MPE provides a probabilistic measure of predictive gain from memory that complements classical information-theoretic approaches.

    Source: §1 · p. 5

    The analysis assumes discrete-time finite-state processes and positive state marginals to avoid repeated treatment of null events.

    Source: §2 · p. 5, §3 · p. 9

Abstract

from arXiv · show

A central question in the prediction of stochastic processes is the extent to which past information can improve the probability of correctly predicting the next state. We introduce the Memory Prediction Excess (MPE) to address this question quantitatively. The MPE measures the average improvement in prediction accuracy obtained by using the entire observed history relative to using only the static marginal distribution, in discrete-time finite-state processes. It is defined as the difference between the expected optimal conditional prediction accuracy and the optimal static prediction accuracy. Its basic properties are examined: the MPE is always non-negative; it admits an upper bound depending on the static accuracy, attained if and only if the future is almost surely a deterministic function of the past; and degenerate cases in which the MPE vanishes are characterized. A normalized version, taking values in the unit interval, is introduced as a dimensionless measure of predictive efficiency. A lower bound is derived by comparing predictions based on histories of different lengths, showing that the expected optimal prediction accuracy is monotone with respect to the history length. The framework is extended to finite-length histories, where the finite-history MPE (FH-MPE) measures the predictive gain attainable when only the most recent observations are retained. This leads to the notion of a minimal memory length required to achieve the same predictive performance as the full history. For finite-order Markov chains, this minimal memory length is shown to be bounded by the Markov order. The MPE and its variants are formulated in terms of conditional probabilities and prediction accuracies, offering a probabilistic perspective on the predictive utility of memory that is complementary to classical information-theoretic approaches.

1 | INTRODUCTION

The introduction frames the paper around how much past information improves next-state prediction, a question complementary to information-theoretic and modeling approaches. It introduces MPE and outlines results on its bounds, normalization, and dependence on history length.

1 | INTRODUCTION

  • The introduction presents MPE as complementary to measures of information content and flow, dependence, and stochastic prediction frameworks.The reviewed approaches include entropy, mutual information, transfer entropy, maximal correlation, and probabilistic models.Source: §1 · pp. 2–4
  • The Memory Prediction Excess (MPE) measures the average gain in optimal prediction accuracy from using the full observed history rather than only the static marginal distribution.The paper situates this probabilistic measure alongside broader information-theoretic approaches.Source: §1 · pp. 4–5
  • For discrete-time finite-state processes, the paper characterizes MPE non-negativity, its sharp upper bound and attainment condition, and cases where it vanishes.It also introduces normalized MPE as the achieved proportion of maximal predictive gain.Source: §1 · p. 5
  • The paper derives a lower bound by comparing histories of different lengths, establishing that expected optimal prediction accuracy is monotone in history length.For finite-order Markov chains, finite-history MPE saturates at the Markov order, which bounds the minimal memory length needed to attain full-history performance.Source: §1 · p. 5

2 | DEFINITION OF MEMORY PREDICTION EXCESS

This section defines MPE for a discrete-time process with finite state space by contrasting optimal prediction from the full history with a static marginal baseline. It sets up the histories and conditional accuracies needed for that comparison and expands the quantity over possible histories.

2.1 | Notation for Histories and Elementary Probabilities

  • A history is represented as a path of observed states, with its probability distribution defined over the finite set of possible paths.The setup assumes finite state space and positive state marginals; vanishing probabilities are said to require only trivial modifications.Source: §2 · p. 5, §2.1 · pp. 5–6

2.2 | Static Optimal Prediction Accuracy

  • Static optimal prediction accuracy is the largest marginal probability of the next state and serves as the baseline when no historical information is used.The maximizing state need not be unique; any maximizing choice yields the same accuracy.Source: §2.2 · p. 6

2.3 | Conditional Probabilities Given the History

  • Conditional probabilities of the next state given the observed history provide the history-dependent quantities used to define optimal prediction accuracy.Values assigned on zero-probability histories do not affect expectations or almost-sure statements.Source: §2.3 · pp. 6–7

2.4 | History-Dependent Optimal Prediction Accuracy as a Random Variable

  • For each history, the maximal conditional probability is the best correct-prediction probability available after observing that history; across random histories it is a random variable.Its values lie between 1/|A| and 1.Source: §2.4 · p. 7

2.5 | Formal Definition of the MPE

  • MPE is the expected optimal conditional prediction accuracy using the full observed past minus the optimal static accuracy based on the next-state marginal.The section treats discrete-time processes with finite state spaces and assumes positive state marginals to keep conditional probabilities well-defined in the elementary sense.Source: §2 · p. 5, §2.5 · pp. 7–8

2.6 | Explicit Expansion in a Discrete State Space

  • The explicit expansion expresses MPE as an average over histories of the maximal conditional state probability minus the maximum marginal state probability.This subtracts averaging after maximization from maximization after averaging; the section notes that this structure underlies the non-negativity argument.Source: §2.6 · p. 8

3 | BASIC PROPERTIES OF MEMORY PREDICTION EXCESS

This section examines the basic extremal properties of MPE for discrete-time finite-state processes, including its non-negativity and upper bound. It characterizes when MPE vanishes and when the upper bound is attained in terms of the predictive role of the past.

3.1 | Non-negativity of the MPE

  • The MPE is non-negative because average optimal prediction accuracy using the full history is at least the static accuracy.This is an expectation-level comparison for discrete-time finite-state processes.Source: §3.1 · p. 10

3.2 | Upper Bound and Sharpness Condition

  • The MPE satisfies MPE ≤ 1-U_n ≤ 1-1/|A|, and reaches its first upper bound if and only if the future is almost surely a deterministic function of the past.The universal bound depends only on the state-space size; in the deterministic case, conditional optimal prediction accuracy is 1 almost surely.Source: §3.2 · pp. 11, 14

3.3 | Degenerate Cases of the MPE

  • The next subsection examines two scenarios in which the MPE attains its lower bound of zero.The supplied passage introduces these cases but does not specify them.Source: §3.3 · p. 14
  • The MPE ranges from 0 to 1 − U_n: independence or already-perfect static prediction gives 0, while a past-determined future attains 1 − U_n.The upper endpoint is the bound established for the MPE; between the extremes, positive non-maximal values indicate partial predictive improvement from history.Source: §3.3 · pp. 16–17
  • When the future is independent of history, memory adds no predictive information; when static accuracy U_n is 1, prediction is already perfect, so the MPE is zero.In either case, conditioning on history cannot improve optimal prediction accuracy.Source: §3.3 · p. 17
  • If the past determines the future almost surely, conditional prediction accuracy is 1 and the MPE attains its upper bound, 1 − U_n.Positive but non-maximal MPE values indicate that historical information provides only a partial improvement in prediction accuracy.Source: §3.3 · p. 17

4 | NORMALIZED MEMORYPREDICTIONEXCESSANDITSINFORMATION-THEORETIC CONTEXT

This section introduces a normalized Memory Prediction Excess to express historical information’s predictive gain relative to the maximum possible gain and situates prediction accuracy alongside information-theoretic measures. It also establishes bounds showing that expected optimal prediction accuracy does not decrease as history length grows.

4.1 | Definition of Normalized Memory Prediction Excess

  • For U_n < 1, Δeff_n = Δmem_n/(1 − U_n) measures the fraction of the maximal possible gain achieved and lies in [0, 1].It removes the scaling effect of static accuracy, enabling comparisons across time indices and stochastic processes; when U_n = 1, Δeff_n is defined as 0.Source: §4.1 · pp. 17–19
  • Δeff_n = 0 when U_n = 1 or X_{n+1} is independent of the history; Δeff_n = 1 exactly when X_{n+1} is almost surely a function of that history.Values strictly between zero and one represent partial realization of the maximal possible predictive gain.Source: §4.1 · pp. 18–19

4.2 | Relation to Information-Theoretic Quantities

  • MPE measures improvement in the optimal probability of a correct prediction, complementing information measures of uncertainty, dependence, and information flow.Mutual information captures average reduction in logarithmic uncertainty, while transfer entropy concerns asymmetric information flow; MPE instead asks how much access to history improves the best prediction accuracy.Source: §4.2 · pp. 20–21

4.3 | A Lower Bound for the Memory Prediction Excess

  • The MPE is at least the excess predictive gain attainable from a shorter history, reflecting that additional past information cannot reduce expected optimal prediction accuracy.The bound compares predictions for the same future state using histories of different lengths and motivates the finite-history analysis.Source: §4.3 · pp. 21–22
  • The lower bound and Proposition 3.1’s upper bound together bracket the Memory Prediction Excess.The upper estimate is Δmem_n ≤ 1 − U_n.Source: §4.3 · pp. 24–25
  • The gain from using n+1 history steps is at least the excess over static accuracy already achievable with n steps, because expected optimal prediction accuracy cannot decrease with history length.For almost every shorter-history realization, its optimal accuracy is no greater than the conditional expectation of the longer-history optimal accuracy.Source: §4.3 · p. 24
  • At n=0, the lower bound reduces to Δmem_1 ≥ 0, matching the previously established non-negativity result.With empty history, the conditional prediction accuracy is the unconditional static accuracy, so the lower-bound difference is zero.Source: §4.3 · p. 25

5 | FINITE-HISTORY MEMORY PREDICTION EXCESS

This section extends MPE to predictors using only the most recent k observations and shows that predictive accuracy does not decrease as the retained history grows. It defines the minimal history length needed to attain full-history MPE, which is at most the Markov order for finite-order Markov chains when n is at least that order.

5 | FINITE-HISTORY MEMORY PREDICTION EXCESS

  • For an m-th order Markov chain, the most recent m observations contain all predictive information in the full history.Observations older than m steps provide no further predictive information beyond the recent m-block.Source: §5 · p. 25

5.1 | Definition of Finite-History Memory Prediction Excess

  • FH-MPE measures the average predictive-accuracy gain from conditioning on the most recent k observations, interpolating between the static baseline at k = 0 and full-history MPE at k = n.Earlier observations are discarded when k is less than n.Source: §5.1 · pp. 25, 27

5.2 | Monotonicity of FH-MPE

  • The FH-MPE is monotone in memory length: allowing an additional past observation cannot reduce optimal prediction accuracy.The theorem establishes this by comparing predictions based on histories of lengths k and k + 1.Source: §5.2 · pp. 27–28
  • For fixed n, FH-MPE is nonnegative and nondecreasing from zero at k=0 to the full-history MPE at k=n, which bounds every shorter-history value.This monotonicity holds for discrete-time finite-state processes without additional structural assumptions.Source: §5.2 · p. 32

5.3 | Saturation of FH-MPE for Finite-Order Markov Chains

  • For an m-th order Markov chain, FH-MPE reaches its full-history value at memory length m and remains constant for every k≥m.The recent m observations contain all predictive information in the full history, so older observations add no predictive gain.Source: §5.3 · pp. 33, 35
  • For Markov chains, monotonicity before the order and saturation from m onward together characterize the FH-MPE’s evolution across memory lengths.The combined chain has inequalities up to the Markov order and equal values thereafter.Source: §5.3 · p. 35

5.4 | Minimal Memory Length for Full-History MPE

  • The minimal memory length L_n is the smallest k for which FH-MPE equals full-history MPE; for an m-th order Markov chain, L_n≤m.The minimum exists because k=n always attains the full-history MPE, and the candidate lengths form a finite nonempty set.Source: §5.3 · p. 35, §5.4 · p. 36
  • When U_n = 1, the full-history MPE vanishes and the minimal memory length is L_n = 0.Source: §5.4 · p. 38
  • For an m-th order Markov chain with n ≥ m, L_n ≤ m: the most recent m observations already attain full-history MPE.The saturation property reflects that older observations beyond the most recent m do not alter the conditional distribution of X_{n+1}.Source: §5.4 · pp. 38–39
  • L_n is the shortest history length attaining full-history MPE, and FH-MPE stays at that value for every memory length at or above L_n.In the finite-state setting, 0 ≤ L_n ≤ n.Source: §5.4 · pp. 37, 40
Loading 2610.06894v1…