UNIVERSAL REDUNDANCY RATES FOR THE CLASS OF B-PROCESSES DO NOT EXIST

We show that for any sequence 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 rho(n) for infinitely many n. This extends earlier work of the first author, whose examples had 0 entropy, [5]. 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, our 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.