A Lower-Bound for the Maximin Redundancy in Pattern Coding
A Lower-Bound for the Maximin Redundancy in Pattern Coding
复制标题
模式编码中最大最小冗余度的下界
DOI：
10.3390/e11040634
复制
发表时间：
2009
期刊：
影响因子：
2.7
通讯作者：
Aurélien Garivier
中科院分区：
文献类型：
--
作者：
Aurélien Garivier
我们证明了对于长度为n的消息，模式编码中的最大平均冗余度最终大于1.84(n/logn)1/3，这改进了最近关于模式冗余度的结果，尽管它没有填补已知的上下界之间的空白。字符串的模式是通过将每个符号替换为其第一次出现的索引来获得的。模式编码的问题令人感兴趣，因为已经证明对于模式存在强通用编码，而对于无限字母表上的无记忆信源，通用消息编码是不可能的。该证明使用了具有小和数的划分的精细组合结果。
We show that the maximin average redundancy in pattern coding is eventually larger than 1.84 (n/log n)1/3 for messages of length n. This improves recent results on pattern redundancy, although it does not fill the gap between known lower- and upper-bounds. The pattern of a string is obtained by replacing each symbol by the index of its first occurrence. The problem of pattern coding is of interest because strongly universal codes have been proved to exist for patterns while universal message coding is impossible for memoryless sources on an infinite alphabet. The proof uses fine combinatorial results on partitions with small summands.