High-confidence predictions under adversarial uncertainty
Abstract
We study the setting in which the bits of an unknown infinite binary sequence x are revealed sequentially to an observer. We show that very limited assumptions about x allow one to make successful predictions about unseen bits of x . First, we study the problem of successfully predicting a single 0 from among the bits of x . In our model, we have only one chance to make a prediction, but may do so at a time of our choosing. This model is applicable to a variety of situations in which we want to perform an action of fixed duration, and need to predict a “safe” time-interval to perform it.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 01, 2013
- Source ID
- 10.1145/2493252.2493257
Entities
People
- Andrew Drucker
Organizations
- Defense Advanced Research Projects Agency
- Division of Computing and Communication Foundations
- Massachusetts Institute of Technology
- National Science Foundation Division of Mathematical Sciences