Third-Order Asymptotics of Variable-Length Compression Allowing Errors
Third-Order Asymptotics of Variable-Length Compression Allowing Errors
复制标题
允许误差的变长压缩的三阶渐近
DOI：
10.1109/tit.2021.3117591
复制
发表时间：
2021
影响因子：
2.5
通讯作者：
Tan Vincent Y. F.
中科院分区：
文献类型：
--
作者：
Sakai Yuta;Yavas Recep Can;Tan Vincent Y. F.
本研究研究了可变长度压缩的基本限制，其中不施加无前缀约束（即研究一对一代码）并且允许非消失错误概率。部分由于可变长度和固定长度压缩问题之间的关键关系，我们的分析需要在允许错误概率在块长度中接近零或一个多项式的设置中对固定长度压缩的基本限制进行仔细和精确的分析。为了获得改进，我们使用中等偏差和强大偏差的工具。最后，我们提供了具有非零误差概率的变长压缩问题的三阶渐近。我们表明，与已知三阶渐近的其他几个信息论问题不同，对于这里感兴趣的问题，三阶项取决于允许误差概率。
This study investigates the fundamental limits of variable-length compression in which prefix-free constraints are not imposed (i.e., one-to-one codes are studied) and non-vanishing error probabilities are permitted. Due in part to a crucial relation between the variable-length and fixed-length compression problems, our analysis requires a careful and refined analysis of the fundamental limits of fixed-length compression in the setting where the error probabilities are allowed to approach either zero or one polynomially in the blocklength. To obtain the refinements, we employ tools from moderate deviations and strong large deviations. Finally, we provide the third-order asymptotics for the problem of variable-length compression with non-vanishing error probabilities. We show that unlike several other information-theoretic problems in which the third-order asymptotics are known, for the problem of interest here, the third-order term depends on the permissible error probability.