R.I.P.
๐ป
Ghosted
Computability Limits of Sequential Hypothesis Testing
May 04, 2026 ยท Grace Period ยท + Add venue
Authors
Amir Leshem
arXiv ID
2605.02501
Category
cs.IT: Information Theory
Cross-listed
math.LO
Citations
0
Abstract
Sequential hypothesis testing asks for decision rules that update as data arrive. A natural goal is \emph{eventual correctness}: the rule may change its mind early on, but it should make only finitely many wrong decisions almost surely. Starting from Cover's theorem, which guarantees such behavior for membership in a countable set of candidate means, we ask a sharper question: \emph{which sets actually admit computable sequential decision procedures with finitely many errors?} We answer this optimally by giving a complete characterization both necessary and sufficient of the subsets of $\Q$ that admit a computable finite-error sequential membership test. We further extend the characterization to any \emph{effectively presented} countable family of real means, exactly the setting in which Cover's identification rule can be implemented computably. Beyond the technical boundary, the results clarify within a precise probabilistic setting what it can mean for inquiry to ``converge to the truth,'' and they formalize a limit to which empirical methods can be expected to succeed when only eventual stabilization (rather than fixed-time guarantees) is demanded. keywords: Cover's theorem, sequential decision procedures, finite error learning, limit computability, $ฮ^0_2$ sets.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Information Theory
R.I.P.
๐ป
Ghosted
A Vision of 6G Wireless Systems: Applications, Trends, Technologies, and Open Research Problems
R.I.P.
๐ป
Ghosted
Towards Smart and Reconfigurable Environment: Intelligent Reflecting Surface Aided Wireless Network
๐
๐
The Cartographer
Wireless Communications with Unmanned Aerial Vehicles: Opportunities and Challenges
R.I.P.
๐ป
Ghosted
Reconfigurable Intelligent Surfaces for Energy Efficiency in Wireless Communication
๐
๐
The Cartographer