Non-asymptotic and asymptotic analyses on Markov chains in several problems
Non-asymptotic and asymptotic analyses on Markov chains in several problems
复制标题
DOI：
10.1109/ita.2014.6804255
复制
发表时间：
2013-09
期刊：
影响因子：
--
通讯作者：
Masahito Hayashi;Shun Watanabe
中科院分区：
文献类型：
--
作者：
Masahito Hayashi;Shun Watanabe
本文给出了带边信息信源编码和带边信息随机数产生的非渐近可扩性和匡威界。我们的边界是有效的计算在这个意义上，计算复杂性不依赖于块的长度。我们还刻画了大偏差区和中等偏差区的渐近行为，这意味着我们的边界是渐近紧在这些地区。我们还显示了这些问题的二阶速率，并推导出表征二阶速率的方差的单字母形式。
In this paper, we derive non-asymptotic achievability and converse bounds on the source coding with side-information and the random number generation with side-information. Our bounds are efficiently computable in the sense that the computational complexity does not depend on the block length. We also characterize the asymptotic behaviors of the large deviation regime and the moderate deviation regime by using our bounds, which implies that our bounds are asymptotically tight in those regimes. We also show the second order rates of those problems, and derive single letter forms of the variances characterizing the second order rates.