Technical Program

Paper Detail

Paper Title Being correct eventually almost surely
Paper IdentifierTH2.R4.1
Authors Changlong Wu, Narayana Santhanam, University of Hawaii at Manoa, United States
Session Testing and Classification III
Location Odéon, Level 3
Session Time Thursday, 11 July, 11:40 - 13:00
Presentation Time Thursday, 11 July, 11:40 - 12:00
Manuscript  Click here to download the manuscript
Abstract We study the problem of predicting upper bounds on the next draw of an unknown probability distribution after observing a sample generated by it. The unknown distribution is modeled as belonging to a class P of distributions over natural numbers. The goal is to err only finitely many times even though the game proceeds over an infinite horizon, and though there is no upper bound on what the next sample can be. If a universal prediction scheme exists that makes only finitely many errors regardless of what model in P generated the data, we say P is eventually almost surely (e.a.s.) predictable. In this paper, we fully characterize when P can be e.a.s.-predictable.