Polynomial-Time Minimax Prediction for Stationary Renewal Processes
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.
Related
- Local stability and rates of convergence to equilibrium for the Nonlinear Renewal Equation; applications to Hawkes processes
- marp: Model-Averaged Inference for Parametric Renewal Processes in R
- Forecasting of infectious disease epidemics in sexual networks using attenuated renewal processes
- Obtaining Game-Stationary Points for Smooth Nonconvex-Nonconcave Minimax Problems via First-Order Methods
- Dudley-type bound for stationary Bernoulli processes
BibTeX
@misc{chen2026polynomialtime,
title = {{Polynomial-Time Minimax Prediction for Stationary Renewal Processes}},
author = {Xinyu Chen and Yiming Ma},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01430},
eprint = {2611.01430},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01430},
}
RIS
TY - UNPB
TI - Polynomial-Time Minimax Prediction for Stationary Renewal Processes
AU - Xinyu Chen
AU - Yiming Ma
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01430
UR - https://arxiv.org/abs/2611.01430
AB - 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.
ER -