UNIVERSAL REDUNDANCY RATES DO NOT EXIST

The expected redundancy per symbol R(n)BAR(mu) of an n-block prefix code C(n) on a source mu measures how far the code is from being optimal for that source. The existence of sequences of codes with R(n)BAR (mu) = O((log n)/n) for ''nice'' classes of sources, such as Markov sources of a given order, is well known. In this paper it is shown that some restriction on the class of processes is necessary in order to obtain such redundancy bounds, for there is no universal redundancy rate for any sequence of prefix codes on the class E of all ergodic sources.