Uniform Random Number Generation from Markov Chains: Non-Asymptotic and Asymptotic Analyses
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Exponential Decreasing Rate of Leaked Information in Universal Random Privacy AmplificationIEEE Transactions on Information Theory, 2011
- Channel Coding Rate in the Finite Blocklength RegimeIEEE Transactions on Information Theory, 2010
- On the Redundancy of Slepian–Wolf CodingIEEE Transactions on Information Theory, 2009
- Information Spectrum Approach to Second-Order Coding Rate in Channel CodingIEEE Transactions on Information Theory, 2009
- Simple security proof of quantum key distribution based on complementarityNew Journal of Physics, 2009
- Secrecy Capacities for Multiple TerminalsIEEE Transactions on Information Theory, 2004
- Information-Spectrum Methods in Information Theory2003
- Generating random bits from an arbitrary source: fundamental limitsIEEE Transactions on Information Theory, 1995
- Common randomness in information theory and cryptography. I. Secret sharingIEEE Transactions on Information Theory, 1993
- Secret key agreement by public discussion from common informationIEEE Transactions on Information Theory, 1993