The Redundancy of Two-Part Codes for Finite-Length Parametric Sources
Ahmad Beirami, Faramarz Fekri · 2011
In this paper, we investigate the redundancy in the universal compression of finite length smooth parametric sources. Rissanen demonstrated that for a smooth parametric source with d unknown parameters, the expected redundancy for regular codes is asymp totically given by | logn + o(logn) for almost all sources. Clarke and Barron derived the "minimax expected redundancy" for memoryless sources, which is the maximum redundancy of the best code over the space of source parameters. However, the minimax redundancy is for a particular parameter value, which does not provide much insight about different source parameters. We derived a lower bound on the compression of finite-length memoryless sequences using a probabilistic treatment. In this paper, we extend our analysis to smooth parametric sequences. We focus on two part codes with an asymptotic 0(1) extra redundancy. We also require that the length function be regular, which is not restrictive since all codes that we know are regular.