1 Finite Memory Universal Coding of Individual Binary Sequences

We consider universal coding of individual binary sequences, with the constraint that the universal coder itself is a K-state time-invariant deterministic finite state (TI-DFS) machine. Actually we consider an equivalent problem of sequentially assigning a probability to the next outcome using a TI-DFS machine. We show that unlike the associated prediction problem, counters and finite window machines perform poorly for malicious sequences. We introduce a simple “exponential decaying memory ” machine whose normalized code length is greater than the sequence empirical entropy by an 3/2 K term. As a lower bound, we show that no K-state TI-DFS machine can achieve a redundancy less than 5/4 K for all sequences. I. Problem setting Imagine an observer receiving an arbitrary deterministic binary sequence and wishing to assign at time t a probability tp to the event that the next bit will be ‘1 ’ based on the past. Any encoder that assigns a probability of tp (written on the current state) pays a code length (or log-loss) of 2log ()tp in case the next bit is actually ‘1 ’ and 2log (1)tp in case the next bit is ‘0’. We would like to have a single universal encoder U that competes with the best encoder b of a certain comparison class B for every nx in the sense that ( ())ncodelength U x n is as close as possible to min n b B codelength b x n The universal predictor must be the same for every nx whereas the minimizing predictor b may depend on the entire sequence. The comparison class considered in this paper is the class of single state predictors, i.e., predictors assigning a constant tp. The best static predictor tuned to the sequence chooses tp to be the empirical probability; thus the reference code length is the empirical binary entropy of the sequence. This leads to the definition of the universal coding redundancy([2])