Analytic variations on the redundancy rate of renewal processes

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 Θ(log n) where n is the block length. There was no interesting bound for a class of sources that lies between Θ(logn) and general o(n) until Csiszar and Shields (1996) designed a renewal class of sources that yields a Θ(√n) bound. In this paper, we provide a precise asymptotic expansion of the redundancy for renewal sources up to the constant term