Universal Compression of Piecewise iid Sources

Abstract

We consider the problem of compressing for discrete random processes taking values a nite set, whose statistical parameters are not known, but assumed to come from some class. For instance, the process might be iid or form a Markov chain. We consider the problem of estimating the probability of random sequences whose statistical parameters are unknown but assumed to come from some parametric class fP j 2 g (for example, iid sequences or markov chains). More precisely, suppose X1 Xn are random variables taking values in a nite set A, with joint distribution P for some (unknown) 2 . We seek a universal joint distribution Q : An ! [0 1] which is `not much worse' than any potential `true' distribution P 2 fPtheta j 2 g, where performance is measured by coding redundancy log P (x) Q(x) , x 2 An. The study of coding redundancy is motivated by probabilistic data compression, as it represents the di erence in compression using distribution Q instead of P . The problem of compressing optimally (and e ciently) with respect to a given distribution is solved (Hu man coding, arithmetic coding [6, 26]), so to compress a source with unknown parameter the problem remains to choose Q appropriately. We consider classes of \piecewise stationary" sources in which the parameters of the source occasionally change with i. [Include motivation??] For example, the sequence of random variables X1 Xn might be iid. with parameter (1) for X1 Xt and with parameter (2) for Xt+1 Xn. In the piecewise setting, we prove a bound on the redundancy of one prediction method Q which is already known to perform optimally for nite-memory stationary sources. This bound guarantees that our method is also universal over piecewise iid. sources, and therefore extends the class for which Q is universal.