Minimax Pointwise Redundancy for Memoryless Models over Large Alphabets

Szpankowski, Wojciech ; Weinberger, Marcelo J.

HP Development Company

关键词: data compression;    redundancy;    large alphabets;    generating functions;    saddle point method.;   

RP-ID  :  HPL-2012-87

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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.