Uniform Random Number Generation from Markov Chains: Non-Asymptotic and Asymptotic Analyses

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.

There is no technical overlap with the latest version of arXiv:1309.7528

References in corpus (5)

• Relating different quantum generalizations of the conditional Renyi entropy
• More Efficient Privacy Amplification with Less Random Seeds via Dual Universal Hash Function
• Finite-length Analysis on Tail probability for Markov Chain and Application to Simple Hypothesis Testing
• A uniform Berry--Esseen theorem on $M$-estimators for geometrically ergodic Markov chains
• Universally composable privacy amplification against quantum adversaries

Cited by in corpus (13)

• More Efficient Privacy Amplification with Less Random Seeds via Dual Universal Hash Function
• Operational Interpretation of Renyi Information Measures via Composite Hypothesis Testing Against Product and Markov Distributions
• Finite-length Analysis on Tail probability for Markov Chain and Application to Simple Hypothesis Testing
• Recommendations on Statistical Randomness Test Batteries for Cryptographic Purposes
• Partially smoothed information measures
• Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory
• Moderate deviation expansion for fully quantum tasks
• Parallelization of Adaptive Quantum Channel Discrimination in the Non-Asymptotic Regime
• Finite-Block-Length Analysis in Classical and Quantum Information Theory
• Secure list decoding and its application to bit-string commitment
• Second Order Analysis for Joint Source-Channel Coding with Markovian Source
• Analysis of Remaining Uncertainties and Exponents under Various Conditional Rényi Entropies
• Semi-Finite Length Analysis for Information Theoretic Tasks