2015/03/31 by Masahito Hayashi, Shun Watanabe
Computer Science · Mathematics · #cs.IT #cs.CR #math.IT
paper · pdf · doi:10.1109/tit.2016.2530084
published as IEEE Transactions on Information Theory Volume 62, Issue 4, 1795 - 1822 (2016) · There is no technical overlap with the latest version of arXiv:1309.7528
arxiv created 2016/02/02 · arxiv updated 2016/09/28
In this paper, we derive non-asymptotic achievability and converse bounds on the random number generation with/without 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. Further, we address the equivocation rates for these problems.