[35] Let x be a string. A prediction strategy P is a mapping from the set of strings of length less than l(x) into the set of rational numbers in the segment [0, 1]. The value P(x1 ...xi) (iComments. Hence, if S x is a smallest set such that K(S) ≤ i, then S can be converted into a best strategy of complexity at most i to predict the successive bits of x given the preceding ones, and vice versa. The snooping curve was proposed by V.V. Vyugin [Theoret. Comput. Sci., 276:1-2(2002), 407–415], who obtained partial results. Because of Item (a), Lemma 5.5.2 and Theorem 5.5.2 describe the coarse shape of all possible snooping curves. From Item

(b) it follows that the witness set of hx(i) not only is an almost best-fitting model for x, but also can be converted into an almost best predictor for the successive bits of x.
The notion of the snooping curve sx(i) of a finite string x quantifies the quality of prediction expressed in terms of the errors in predicting the probabilities of the consecutive elements of x. In the prediction situation in Section 5.2.7 we wanted to predict the actual consecutive elements of an infinite sequence, and the quality of the prediction algorithm is given by the number of mistakes we make. Source: [N.K. Vereshchagin and P.M.B. Vit´anyi, IEEE Trans. Inform. Theory, 50:12(2004), 3265–3290].