## 1 Introduction  
The relation between compression and prediction dates back at least as far as [PERSON] in the fourteenth century. This relation was not properly formalized, however, until the notion of Kolmogorov complexity was developed in the twentieth century [1; 2; 3]. Since then, there have been many efforts to harness compression algorithms for prediction, with a number of researchers focusing particularly on prediction for prefetching either disk pages or web pages. We refer the reader to the text by [PERSON] and [PERSON] [4] and references therein for a thorough discussion. For example, [PERSON] and [PERSON] [5] showed that a prefetcher based on LZ78 [6] is asymptotically competitive with the best finite-state prefetcher. For prefetching, however, the alphabet of possible elements--_i.e._, all pages on the disk or web--is huge. In this paper we investigate, therefore, what effect the size of the alphabet has on predictability.  
[PERSON] and [PERSON] considered the problem of pure prefetching, in which the prefetcher can replace all the contents of the cache between each page request. They combined a predictor by [PERSON] [7],which is asymptotically competitive against any memoryless predictor, with an instantaneous version of LZ78, thus obtaining a predictor such that, for any finite-state predictor and any sequence, their predictor's success rate converges to or exceeds the finite-state predictor's success rate with probability approaching 1 as the sequence length increases. (As [PERSON] and [PERSON] noted, a similar construction for predicting binary sequences was given by [PERSON], [PERSON] and [PERSON] [8].) Notice that this bound cannot be improved to hold with certainty instead of with high probability: the predictor must be randomized because, for any deterministic predictor, an adversary can choose each bit of the sequence to be the opposite of what the predictor guesses. [PERSON] and [PERSON]'s proof is based on the fact that, for any finite-state compressor and any sequence, LZ78's asymptotic compression ratio is at most that of the finite-state compressor; this necessarily involves the assumption that both the alphabet and the context length used in prediction are fixed. It is known what effect the size of the alphabet has on compressibility, both when we make certain assumptions about the source of the sequence [9,10] and when we want to bound the size of the encoding in terms of the \(k\)th-order empirical entropy of the sequence [11,12]. We will define a notion of predictability that is analogous to empirical entropy and use similar arguments to give nearly tight bounds on how large the alphabet can be before we cannot guarantee good prediction.  
The rest of this paper is laid out as follows: in Section 2 we briefly review several notions of entropy in computer science--Shannon entropy, empirical entropy, Renyi entropy and min-entropy--before defining empirical predictability; in Section 3 we show that we can achieve good expected prediction in terms of a sequence's \(k\)th-order empirical predictability when \(k\leq\log_{\sigma}n-3-\epsilon\), where \(k\) is the length of the contexts considered when making predictions, \(\sigma\) is the size of the alphabet, \(n\) is the length of the sequence and \(\epsilon>0\) is a constant; in Section 4 we show we cannot achieve the same bound when \(k\geq\log_{\sigma}n\). A preliminary version of these results [13] was reported at the 9 th Canadian Workshop on Information Theory (CWIT '05) while the author was at the University of Toronto.