High-Confidence Predictions under Adversarial Uncertainty

High-Confidence Predictions under Adversarial Uncertainty - Andrew Drucker

Andrew Drucker
Massachusetts Institute of Technology
February 13, 2012
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)

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.