Universal redundancy rates for B-processes do not exist
A. L. Shields, B. Weiss · 2002
Shows that for any sequence /spl rho/(n)=o(n) and any sequence of prefix codes, there is a B-process of entropy arbitrarily close to the maximum possible entropy for which the expected redundancy is at least as large as /spl rho/(n) for infinitely many n. This extends earlier work of the first author, whose examples had 0 entropy, [Shields, 1993]. The class of B-processes, that is, stationary codings of i.i.d. processes, includes the aperiodic Markov chains and functions thereof, aperiodic renewal and regenerative processes, and independent processes, as well as many other processes of interest. In particular, the results show that the search for a universal redundancy-rate for the class of all B-processes is doomed to failure, and redundancy rates for any given subclass must be obtained by direct analysis of that subclass.>