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. Letting Nt denote the number of 1s among the first t bits of x, we say that x is "ε-weakly sparse" if lim inf(Nt/t) ≤ ε.
In REF , the problem of successfully predicting a single 0 in an infinite binary word being revealed sequentially to the predictor is considered; only one prediction may be made, but at a time of the predictor's choosing.
High-confidence predictions under adversarial uncertainty
ITCS '12
Mathematics Computer Science