Computer Science/Discrete Mathematics Seminar I

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) <= 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.