Minimax Pointwise Redundancy for Memoryless Models Over Large Alphabets
Minimax Pointwise Redundancy for Memoryless Models Over Large Alphabets
复制标题
大字母表上无记忆模型的极小极大点冗余
DOI：
--
复制
发表时间：
2012
影响因子：
2.5
通讯作者：
M. Weinberger
中科院分区：
文献类型：
--
作者：
W. Szpankowski;M. Weinberger
我们研究了大型字母上无内存模型的通用编码的最小值冗余，并提出了两个主要结果。我们首先完成了在Orlitsky和Santhanam启动的研究，该研究衍生了最小值冗余的精确渐近差异，相对于序列长度，字母大小的所有范围。其次，我们考虑了一个固定某些符号概率的模型家族的最小值冗余。后一个问题导致了具有超级物质生长的功能的二项式总和。我们的发现可用于在数值上近似序列长度和字母大小的各个范围的最小值冗余。这些结果是通过分析技术（例如树状生成函数和鞍点方法）获得的。
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 superpolynomial 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.