Polynomial-Time Minimax Prediction for Stationary Renewal Processes

Xinyu Chen, Yiming MaarXiv 2026 · arXiv

TL;DR

This paper introduces the first polynomial-time algorithm for minimax optimal next-symbol prediction in stationary binary renewal processes. By developing a clever dynamic programming approach to calculate "censored prefix marginals," the authors achieve the theoretically optimal $O(n^{-1/2})$ risk bound in $O(n^3)$ time, resolving a significant computational bottleneck in universal prediction.

What Problem Does This Paper Address?

Renewal processes are a cornerstone of probability theory, used to model events that occur at random intervals (like heartbeats, packet arrivals in a network, or machine failures). In a binary renewal process, we observe a sequence of 0s and 1s, where a '1' marks an event and the number of 0s between 1s (the "gap") follows an unknown distribution.

The goal is universal prediction: given a history of $n$ symbols, how accurately can we predict the $(n+1)$-th symbol without knowing the underlying distribution?

Statisticians previously proved that the best possible error rate (specifically, the minimax Kullback–Leibler risk) for this problem is $O(n^{-1/2})$. However, the math used to prove this was "non-constructive" from a computational standpoint. To actually calculate the optimal prediction, you would traditionally need to enumerate an astronomical number of possible sequence completions—a task that grows superpolynomially with the length of the sequence. This paper bridges the gap between theoretical optimality and practical computation.

Methods

The authors base their approach on type-uniform renewal codes. In this framework, all sequences that share the same "type" (the same start position, end position, and histogram of gap lengths) are assigned equal probability.

The core technical contributions are:

  1. Exact Dynamic Programming for Censored Marginals: The authors developed a way to calculate the probability of a sequence prefix without enumerating all possible completions. This is tricky because the "last gap" in an observed sequence is often "censored"—we know it has lasted at least $d$ time steps, but we don't know when it will end.
  2. Coefficient Recurrences: They represent the possible future completions using generating functions and use recurrences to update the coefficients of these functions.
  3. Shared Suffix Updates: The optimal predictor requires averaging results over all suffixes of the observed history. Instead of recomputing from scratch for each suffix, the authors use a "sliding window" style update. By multiplying or dividing by specific polynomials as they move through the sequence, they reduce the total complexity to $O(n^3)$ arithmetic operations.

Datasets

As a theoretical and algorithmic paper, it does not use large-scale empirical datasets (like ImageNet or GLUE). Instead, the authors focus on algorithmic verification:

  • Exhaustive Oracle: For small horizons ($N \le 10$), they compared their algorithm's output against an "oracle" that brute-force enumerates all $2^N$ possible binary strings to ensure the math is exact.
  • Synthetic Stress Tests: They evaluated the algorithm on "dense all-one" histories (sequences of all 1s) to measure how the execution time scales as $N$ increases up to 64.

Key Insights and Ideas

  • The "Aha" Moment on Censoring: The hardest part of renewal prediction is the trailing zeros. The authors realized they could track "marked coefficients" that specifically record whether a potential future gap exceeds the currently observed "age" of the process.
  • Polynomial Bit Complexity: The authors didn't just aim for a low number of operations; they ensured the size of the numbers (the bit complexity) remains polynomial. By using exact rational arithmetic, they avoid the precision errors that plague floating-point implementations in high-dimensional probability.
  • Suffix Averaging is Essential: The paper proves that "shortcuts"—like only using the full-word score without averaging over suffixes—fail to reach the optimal risk. The $O(n^3)$ complexity is the price paid for this necessary statistical robustness.

Key Results

  • Computational Efficiency: The algorithm achieves a total complexity of $O(n^3)$ arithmetic operations and $O(n^2)$ storage.
  • Statistical Optimality: It is guaranteed to attain the minimax risk of $O(n^{-1/2})$ for any stationary renewal process with a finite-mean interarrival law.
  • Empirical Scaling: In their Python implementation, a horizon of $N=64$ took approximately 119 milliseconds to compute, with the number of "kernel visits" scaling almost perfectly with $N^3$ as predicted.

Limitations and Future Work

  • Assumptions: The current model assumes independent gaps and a stationary starting state. It does not yet account for "noisy" observations or processes where gaps might be dependent (like Markov-modulated renewal processes).
  • Horizon-Free Updates: The current algorithm is designed for a fixed observation horizon $N$. The authors note that a "horizon-free" version—where the predictor can be updated infinitely as new data arrives without knowing the total length in advance—is not yet asserted.
  • Practical Scale: While $O(n^3)$ is "efficient" in computer science terms, it may still be too slow for extremely high-frequency data (where $n$ is in the millions) without further optimization or parallelization.

Summary updated

Abstract

The minimax next-symbol Kullback-Leibler risk for stationary binary renewal processes is known to have order n^(-1/2). We give a polynomial-time predictor attaining this order for an arbitrary unknown finite-mean interarrival law. The construction uses a classical type-uniform renewal code. Its contribution is an exact dynamic program for censored prefix marginals, avoiding enumeration of gap histograms or binary completions. Combined with an established prediction reduction, it gives risk at most [log M_(n+1)+log(n+2)]/n, where M_N counts renewal types. Shared suffix updates reduce the total computation to O(n^3) arithmetic work and polynomial bit complexity, without tail, mixing, known-mean, or bounded-support assumptions. The statistical rate and its lower bound are prior results; the proposed advance concerns computation.
BibTeX
@misc{chen2026polynomial,
  author = {Xinyu Chen and Yiming Ma},
  title = {{Polynomial-Time Minimax Prediction for Stationary Renewal Processes}},
  year = {2026},
  eprint = {2611.01430},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01430},
}
Figure