Universal redundancy rates for the class of B-processes do not exist
Paul C. Shields, B. Weiss · IEEE Transactions on Information Theory · 1995
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 work of Shields (1993), whose examples had O entropy. The class of B-processes, that is, stationary codings of independent and identically distributed (i.i.d.) processes, includes the aperiodic Markov chains and functions thereof, aperiodic renewal and regenerative processes, and m-dependent 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.>