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. Our main focus is the problem of successfully predicting a single 0 from among the bits of x. In our model we get just one chance to make a prediction, at a time of our choosing. This models a variety of situations in which we need to perform an action of fixed duration, and must predict a "safe" time-interval to perform it.

Letting N_t denote the number of 1s among the first t bits of x, we say that x is "eps-weakly sparse" if lim inf (N_t:t) \leq eps. Our main result is a randomized algorithm that, given any eps-weakly sparse sequence x, predicts a 0 of x with success probability as close as desired to 1 - eps. Thus we can achieve essentially the same success probability as under the much stronger assumption that each bit of x takes the value 1 independently with probability eps. We extend this result to successfully predict a bit (0 or 1) under a broad class of assumptions on x.

We also propose and solve a variant of the well-studied "ignorant forecasting" problem. Given sequential access to *any* binary sequence x, we show how to predict the fraction of 1s appearing in an unseen interval of x. Given freedom to choose the length and location of the interval, we can achieve this with high accuracy and reliability.

Reference: A. Drucker, High-Confidence Predictions Under Adversarial Uncertainty. ITCS 2012 and TOCT 2013