## 2 Empirical Predictability  
[PERSON] [14] defined the entropy of a random variable to be our uncertainty about its value. Specifically, if a random variable \(\mathcal{X}\) takes on one of \(\sigma\) values according to a probability distribution \(P=p_{1},\ldots,p_{\sigma}\), then  
\[H(\mathcal{X})=\sum_{j=1}^{\sigma}p_{j}\log\frac{1}{p_{j}}\]  
The base of the logarithm determines the unit of uncertainty; in computer science, the base is usually assumed to be 2 with the result that the unit is the bit (_i.e._, our uncertainty about the outcome of flipping a fair coin). Throughout the rest of this paper we write \(\log\) to mean \(\log_{2}\). Given \(P\), the expected number of bits needed to encode the value of \(\mathcal{X}\) is at least \(H(\mathcal{X})\) and less than \(H(\mathcal{X})+1\). The 0 th-order empirical entropy \(H_{0}(S)\) of a sequence \(S[1\ldots n]\) is simply our uncertainty about an element chosen uniformly at random from \(S\), _i.e._,  
\[H_{0}(S)=\frac{1}{n}\sum_{a\in S}\mathsf{occ}(a,S)\log\frac{n}{\mathsf{occ}(a,S)}\]  
where \(a\in S\) means that element \(a\) occurs in \(S\) and \(\mathsf{occ}(a,S)\) is its frequency. For \(k\geq 1\), the \(k\)th-order empirical entropy \(H_{k}(S)\) of \(S\) is our expected uncertainty about the random variable \(s[i]\) in the following experiment: \(i\) is chosen uniformly at random between 1 and n; if \(i\leq k\), then we are told \(s[i]\); if \(i>k\), then we are told \(s[i-k\ldots i-1]\) and asked to guess \(s[i]\). Specifically,  
\[H_{k}(S)=\frac{1}{n}\sum_{|\alpha|=k}|S_{\alpha}|H_{0}(S_{\alpha})\]  
where \(S_{\alpha}\) is the concatenation of the elements in \(S\) immediately following occurrences of the \(k\)-tuple \(\alpha\). Notice that \(|S_{\alpha}|=\mathsf{occ}(\alpha,S)\) unless \(\alpha\) is a suffix of \(S\), in which case it is 1 less. Given a table listing the frequency of each \((k+1)\)-tuple in \(S\), it takes about \(nH_{k}(S)\) bits to encode \(S\). For further discussion of empirical entropy, we refer readers to [PERSON]'s analysis [15] of the Burrows-Wheeler Transform. The Renyi entropy of order \(t\) of \(\mathcal{X}\) is defined as  
\[\frac{1}{1-t}\log\left(\sum_{j=1}^{\sigma}p_{j}^{t}\right)\]  
for \(0\leq t\
eq 1\), where the random variable \(\mathcal{X}\) again takes on values according to the probability distribution \(P=p_{1},\ldots,p_{\sigma}\). The Renyi entropy of order 0 of \(\mathcal{X}\) is the logarithm of the size of the support of \(P\). The limit of the Renyi entropy of order \(t\) of \(\mathcal{X}\) as \(t\) approaches 1 is the Shannon entropy \(H(\mathcal{X})\) of \(\mathcal{X}\); as \(t\) approaches infinity, the limit is \(-\log\sup_{1\leq j\leq\sigma}p_{j}\), which is often called the min-entropy of \(X\). Min-entropy is related to predictability because, given \(P\) and asked to guess the value of \(X\), our best strategy is to choose the most probable value and, thus, guess correctly with probability \(\max_{1\leq i\leq\sigma}\{p_{i}\}\). If we are asked to guess the value of an element \(s[i]\) chosen uniformly at random from the sequence \(S\) with no context given, then our best strategy is to choose the most frequent element and, thus, guess correctly with probability \(\max_{a\in S}\frac{\mathsf{occ}(a,S)}{n}\). Following the example of empirical entropy, we call this probability the _0 th-order empirical predictability_\(P_{0}(S)\) of \(S\). We define the _\(k\)th-order empirical predictability_\(P_{k}(S)\) of \(S\) to be the expected predictability of the random variable \(s[i]\) in the following experiment: \(i\) is chosen uniformly at random between 1 and n; if \(i\leq k\), then we are told \(s[i]\); if \(i>k\), then we are told \(s[i-k\ldots i-1]\) and asked to guess \(s[i]\). Specifically,  
\[P_{k}(S)=\frac{1}{n}\left(k+\sum_{|\alpha|=k}|S_{\alpha}|P_{0}(S_{\alpha})\right)\]  
for \(k\geq 1\), where \(S_{\alpha}\) is again the concatenation of the elements in \(S\) immediately following occurrences of the \(k\)-tuple \(\alpha\).