Uniform Random Number Generation from Markov Chains: Non-Asymptotic and Asymptotic Analyses
arXiv:1503.04371 · doi:10.1109/TIT.2016.2530084
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.
arXiv commentThere is no technical overlap with the latest version of arXiv:1309.7528
References in corpus (17)
- Unconditional Security Of Quantum Key Distribution Over Arbitrarily Long Distances
- On quantum Renyi entropies: a new generalization and some properties
- Information Spectrum Approach to Second-Order Coding Rate in Channel Coding
- A Hierarchy of Information Quantities for Finite Block Length Analysis of Quantum Tasks
- Exponential decreasing rate of leaked information in universal random privacy amplification
- Relating different quantum generalizations of the conditional Renyi entropy
- More Efficient Privacy Amplification with Less Random Seeds via Dual Universal Hash Function
- Tight exponential analysis of universally composable privacy amplification and its applications
- Dual universality of hash functions and its applications to quantum cryptography
- Second-Order Coding Rates for Channels with State
- Finite-length Analysis on Tail probability for Markov Chain and Application to Simple Hypothesis Testing
- Large deviation analysis for quantum security via smoothing of Renyi entropy of order 2
- Second-Order Resolvability, Intrinsic Randomness, and Fixed-Length Source Coding for Mixed Sources: Information Spectrum Approach
- Universal Secure Multiplex Network Coding with Dependent and Non-Uniform Messages
- A uniform Berry--Esseen theorem on -estimators for geometrically ergodic Markov chains
- Universally composable privacy amplification against quantum adversaries
- Finite-Length Analyses for Source and Channel Coding on Markov Chains
Cited by in corpus (14)
- 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
- Security analysis of epsilon-almost dual universal2 hash functions: smoothing of min entropy vs. smoothing of Rényi entropy of order 2
- 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