IEEE International Symposium on Information Theory (ISIT)

Second-order achievable rates in random number generation for mixed sources

Ryo Nomura, Te Sun Han

Published Jul 1, 2012• 0 citations

Abstract

The second-order achievable rates in typical random number generation problems are considered. In these problems, several researchers have derived the first-order and the second-order achievability rates for general sources using the information spectrum methods. Although these formulas are general, their computation are quite hard. Hence, an attempt to address explicit computation problems of achievable rates is meaningful. In this paper, we consider mixed sources of two i.i.d. sources and compute the second-order achievable rates explicitly.

DOI: 10.1109/isit.2012.6284673

Related papers

Second-Order Intrinsic Randomness for Correlated Non-Mixed and Mixed Sources

Tomohiko Uyematsu, Tetsunao Matsuta

We consider the intrinsic randomness problem for correlated sources. Specifically, there are three correlated sources, and we want to extract two mutually independent random numbers by using two separate mappings, where each mapping converts one of the output sequences from two correlated sources into a random number. In addition, we assume that the obtained pair of random numbers is also independent of the output sequence from the third source. We first show the δ-achievable rate region where a rate pair of two mappings must satisfy in order to obtain the approximation error within δ ∈ [0,1), and the second-order achievable rate region for correlated general sources. Then, we apply our results to non-mixed and mixed independently and identically distributed (i.i.d.) correlated sources, and reveal that the second-order achievable rate region for these sources can be represented in terms of the sum of normal distributions.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesJan 1, 20170 citations

Optimum Achievable Rates in Two Random Number Generation Problems with f-Divergences Using Smooth Rényi Entropy

Ryo Nomura, Hideki Yagi

Two typical fixed-length random number generation problems in information theory are considered for general sources. One is the source resolvability problem and the other is the intrinsic randomness problem. In each of these problems, the optimum achievable rate with respect to the given approximation measure is one of our main concerns and has been characterized using two different information quantities: the information spectrum and the smooth Rényi entropy. Recently, optimum achievable rates with respect to f-divergences have been characterized using the information spectrum quantity. The f-divergence is a general non-negative measure between two probability distributions on the basis of a convex function f. The class of f-divergences includes several important measures such as the variational distance, the KL divergence, the Hellinger distance and so on. Hence, it is meaningful to consider the random number generation problems with respect to f-divergences. However, optimum achievable rates with respect to f-divergences using the smooth Rényi entropy have not been clarified yet in both problems. In this paper, we try to analyze the optimum achievable rates using the smooth Rényi entropy and to extend the class of f-divergence. To do so, we first derive general formulas of the first-order optimum achievable rates with respect to f-divergences in both problems under the same conditions as imposed by previous studies. Next, we relax the conditions on f-divergence and generalize the obtained general formulas. Then, we particularize our general formulas to several specified functions f. As a result, we reveal that it is easy to derive optimum achievable rates for several important measures from our general formulas. Furthermore, a kind of duality between the resolvability and the intrinsic randomness is revealed in terms of the smooth Rényi entropy. Second-order optimum achievable rates and optimistic achievable rates are also investigated.

arXiv:2404.11097EntropySep 6, 20243 citations

Second-Order Achievable Rate Region of Slepian-Wolf Coding Problem in terms of Smooth Max-Entropy for General Sources

Shota Saito, Toshiyasu Matsushima

This letter deals with the Slepian-Wolf coding problem for general sources. The second-order achievable rate region is derived using quantity which is related to the smooth max-entropy and the conditional smooth max-entropy. Moreover, we show the relationship of the functions which characterize the second-order achievable rate region in our study and previous study.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesJan 1, 20160 citations

Communication-Constrained Secret Key Generation: Second-Order Bounds

Henri Hentilä, Yanina Y. Shkel, Visa Koivunen

We study communication-constrained secret key generation, where two legitimate parties would like to generate a secret key using communication subject to a rate constraint. The problem is studied in the finite-blocklength regime. In this regime, the use of auxiliary random variables subject to Markov chain conditions in the corresponding asymptotic bounds has proven to make most existing proof techniques insufficient. However, two recently proposed proof techniques – one for the achievability side based on Poisson matching, and another for the converse side based on reverse hypercontractivity – allow us to overcome these issues to some extent. Based on these techniques, novel one-shot and second-order achievability and converse bounds are derived for the problem. While the second-order bounds do not coincide, leaving a precise second-order characterization of the problem an open issue, they improve upon the previously known tightest bounds. The second-order bounds are demonstrated for two simple sources: the binary symmetric source and the Gaussian symmetric source. For the binary source, we find that the gap between the two bounds is mainly due to an unwanted constant in the converse bound, and the non-convexity of the achievability bound.

IEEE Transactions on Information TheorySep 13, 20243 citations

Separation of random number generation and resolvability

Karthik Visweswariah, Sanjeev R. Kulkarni, Sergio Verdú

We consider the problem of determining when a given source can be used to approximate the output due to any input to a given channel. We provide achievability and converse results for a general source and channel. For the special case of a full-rank discrete memoryless channel we give a stronger converse result than we can give for a general channel.

IEEE Transactions on Information TheoryJan 1, 200012 citations

Finite-precision intrinsic randomness and source resolvability

Yossef Steinberg, Sergio Verdú

Random number generators are important devices in randomized algorithms, Monte-Carlo methods, and in simulation studies of random systems. A random number generator is usually modeled as a random source emitting independent, equally likely random bits. In practice, the random source one has at hand can deviate from this idealized model, and the random number generator operates by applying a deterministic mapping on the output of the (nonideal) random source. The deterministic mapping is chosen so that the resulting process approximates, in some sense, a sequence of independent, equally likely random bits. A prime measure of the intrinsic randomness of a given source X is the maximal rate at which random bits can be extracted from X by suitably mapping its output. This maximal rate depends on the statistics of the source X and on the sense of approximation. We study the problem of finite-precision random bit generation, where the accuracy measure is the variational distance. The relevant information theory is addressed.

IEEE-IMS Workshop on Information Theory and StatisticsDec 17, 20021 citation