Analytic variations on the redundancy rate of renewal processes
Philippe Flajolet, W. Szpankowski · 2002
The redundancy-rate problem of universal fixed-to-variable length coding for a class of sources consists of determining by how much the actual code length exceeds the optimal (ideal) code length. In a minimax scenario one finds the additional "price" on top of entropy incurred (at least) by any code in order to be able to cope with all sources. While Shields (1993) proved that there is no function o(n) which is a rate bound on the redundancy for the class of all ergodic processes, it has been known for some time (cf.Rissanen 1984) that, for certain parametric families of sources (e.g., memoryless and Markov sources), the redundancy can be as small as /spl Theta/(log n) where n is the block length. There was no interesting bound for a class of sources that lies between /spl Theta/(logn) and general o(n) until Csiszar and Shields (1996) designed a renewal class of sources that yields a /spl Theta/(/spl radic/n) bound. In this paper, we provide a precise asymptotic expansion of the redundancy for renewal sources up to the constant term.