Analytic variations on redundancy rates of renewal processes
Philippe Flajolet, Wojciech Szpankowski · IEEE Transactions on Information Theory · 2002
: Csisz'ar and Shields have recently proved that the minimax redundancy for a class of renewal processes is \\Theta( p n) where n is the block length. This interesting result provides a first non-trivial bound on redundancy for a non-parametric family of processes. The present paper provides a precise estimate up to the constant term of the redundancy rate for such sources. The asymptotic expansion is derived by complex--analytic methods that include generating function representations, Mellin transforms, singularity analysis and saddle point estimates. This work places itself within the framework of analytic information theory. Keywords. Analytic information theory, redundancy, Mellin transform, saddle point method, singularity analysis. Unit'e de recherche INRIA Rocquencourt Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY Cedex (France) T'el'ephone : (33) 01 39 63 55 11 -- T'el'ecopie : (33) 01 39 63 53 Variations analytiques sur le taux de redondance des processus de...