Minimax Pointwise Redundancy for Memoryless Models over Large Alphabets
Szpankowski, Wojciech; Weinberger, Marcelo J.
Keyword(s): data compression; redundancy; large alphabets; generating functions; saddle point method.
Abstract: We study the minimax pointwise redundancy of universal coding for memoryless models over large alphabets and present two main results: We first complete studies initiated in Orlitsky and Santhanam deriving precise asymptotics of the minimax pointwise redundancy for all ranges of the alphabet size relative to the sequence length. Second, we consider the minimax pointwise redundancy for a family of models in which some symbol probabilities are fixed. The latter problem leads to a binomial sum for functions with super-polynomial growth. Our findings can be used to approximate numerically the minimax pointwise redundancy for various ranges of the sequence length and the alphabet size. These results are obtained by analytic techniques such as tree-like generating functions and the saddle point method.
External Posting Date: April 23, 2012 [Fulltext]. Approved for External Publication
Internal Posting Date: April 23, 2012 [Fulltext]