Uniform Random Number Generation From Markov Chains: Non-Asymptotic and Asymptotic Analyses
- 15 February 2016
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 62 (4) , 1795-1822
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. Furthermore, we address the relative entropy rate and the modified mutual information rate for these problems.Keywords
All Related Versions
Funding Information
- Ministry of Education, Culture, Sports, Science, and Technology within the Grant-in-Aid for Scientific Research (A) (23246071)
- National Institute of Information and Communication Technology, Japan
- Japan Society for the Promotion of Science Post-Doctoral Fellowships for Research Abroad
This publication has 42 references indexed in Scilit:
- A uniform Berry–Esseen theorem on $M$-estimators for geometrically ergodic Markov chainsBernoulli, 2012
- Simple security proof of quantum key distribution based on complementarityNew Journal of Physics, 2009
- Secrecy Capacities for Multiple TerminalsIEEE Transactions on Information Theory, 2004
- On the Markov chain central limit theoremProbability Surveys, 2004
- Spectral theory and limit theorems for geometrically ergodic Markov processesThe Annals of Applied Probability, 2003
- Renyi's divergence and entropy rates for finite alphabet Markov sourcesIEEE Transactions on Information Theory, 2001
- Generalized privacy amplificationIEEE Transactions on Information Theory, 1995
- 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
- The Efficient Construction of an Unbiased Random SequenceThe Annals of Mathematical Statistics, 1972