arXiv preprint ·
Polynomial-Time Minimax Prediction for Stationary Renewal Processes
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Information Theory
Achievability of CSS codes performance limits over Pauli channels under separate ML decoding with bounded graphical complexity
Secrecy Sum-Rate Maximization for RSMA-Enabled Pinching-Antenna Systems
A Beam-Switched Sparse Circular Array for Passive Wi-Fi Sensing
MDS Algebraic Geometry Codes of Square-Root Length on Hyperelliptic Curves
Nearest Is Not Safest: Fluid-Antenna Port Selection for Over-the-Air Backpropagation in Urban Multipath
Get the few papers worth your time in Information Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.