Prediction strategies without loss Rina Panigrahy Stanford University Microsoft Research Silicon Valley Stanford, CA

Consider a sequence of bits where we are trying to predict the next bit from the previous bits. Assume we are allowed to say'predict 0' or'predict 1', and our payoff is +1 if the prediction is correct and 1 otherwise. We will say that at each point in time the loss of an algorithm is the number of wrong predictions minus the number of right predictions so far. In this paper we are interested in algorithms that have essentially zero (expected) loss over any string at any point in time and yet have small regret with respect to always predicting 0 or always predicting 1.