Minimax Compression and Large Alphabet Approximation Through Poissonization and Tilting
Minimax Compression and Large Alphabet Approximation Through Poissonization and Tilting
复制标题
通过泊松化和倾斜进行极小极大压缩和大字母逼近
DOI：
--
复制
发表时间：
2017
影响因子：
2.5
通讯作者：
A. Barron
中科院分区：
文献类型：
--
作者：
Xiao Yang;A. Barron
本文介绍了一种方便的策略，用于编码和预测由大小为$m$的大字母表生成的独立的、同分布的随机变量序列。特别是，允许样本的大小是可变的。泊松模型和倾斜方法的使用通过独立性简化了实现和分析。所得到的策略在满足矩条件的分布类中是最优的，并且对于给定长度的字符串上的所有i.i.d分布类，它接近于最优。该方法还可用于编码和预测在有序计数尾部带有条件的字符串，并且它可以应用于信封类中的分布。此外，我们表明，我们的模型允许精确计算最小最大最优代码，对于所有字母大小，当条件对样本的大小。
This paper introduces a convenient strategy for coding and predicting sequences of independent, identically distributed random variables generated from a large alphabet of size $m$ . In particular, the size of the sample is allowed to be variable. The employment of a Poisson model and tilting method simplifies the implementation and analysis through independence. The resulting strategy is optimal within the class of distributions satisfying a moment condition, and it is close to optimal for the class of all i.i.d distributions on strings of a given length. The method also can be used to code and predict strings with a condition on the tail of the ordered counts, and it can be applied to distributions in an envelope class. Moreover, we show that our model permits exact computation of the minimax optimal code, for all alphabet sizes, when conditioning on the size of the sample.