Redundancy of the Context-Tree Weighting Method on Renewal and Markov Renewal Processes

The Context Tree Weighting method (CTW) is shown to be almost adaptive on the classes of renewal and Markov renewal processes. Up to logarithmic factor, ctw achieves the minimax pointwise redundancy described by I. Csiszaacuter and P. Shields in IEEE Trans. Inf. Theory, vol. 42, no. 6, pp. 2065-2072, Nov. 1996. This result not only complements previous results on the adaptivity of the Context-Tree Weighting method on the relatively small class of all finite context-tree sources (which encompasses the class of all finite order Markov sources), it shows that almost minimax redundancy can be achieved on massive classes of sources (classes that cannot be smoothly parameterized by subsets of finite-dimensional spaces). Moreover, it shows that (almost) adaptive compression can be achieved in a computationally efficient way on those massive classes. While previous adaptivity results for CTW could rely on the fact that any Markov source is a finite-context-tree source, this is no longer the case for renewal sources. In order to prove almost adaptivity of CTW over renewal sources, it is necessary to establish that CTW carefully balances estimation error and approximation error.