Inequalities for source coding: some are more equal than others

An important class of universal encoders is the one where the encoder is fed with two inputs: a) the incoming string of data to be compressed, b) a “training sequence” that consists of the last N data symbols that have been processed (i.e. a sliding window algorithm). We consider fixed-to-variable universal encoders that noiselessly compress blocks of some fixed length and derive universal bounds on the rate of approach of the compression to the l-th order (per letter) entropy H(X₁^l) or to the smaller conditional entropy H(X₁^l-k|X⁰_-k+1 ) as a function of l and of the length N of the training sequence X⁰_-N+1