Universal codes for finite sequences of integers drawn from a monotone distribution

Abstract We offer two noiseless codes for blocks of integers Xn = (X1; : : : ; Xn). We provide explicit bounds on the relative redundancy that are valid for any distribution F in the class of memoryless sources with a possibly infinite alphabet whose marginal distribution is monotone. Specifically we show that the expected code length L(Xn) of our first universal code is dominated by a linear function of the entropy of Xn. Further, we present a second universal code that is efficient in that its length is bounded by n HF + o(n HF), where HF is the entropy of F which is allowed to vary with n. Since these bounds hold for any n and any monotone F we are able to show that our codes are strongly minimax with respect to relative redundancy (as defined by Elias)