We introduce the problem of variable-length (VL) source resolvability, in which a given target probability distribution is approximated by encoding a VL uniform random number, and the asymptotically minimum average length rate of the uniform random number, called the VL resolvability, is investigated. We first analyze the VL resolvability with the variational distance as an approximation measure. Next, we investigate the case under the divergence as an approximation measure. When the asymptotically exact approximation is required, it is shown that the resolvability under two kinds of approximation measures coincides. We then extend the analysis to the case of channel resolvability, where the target distribution is the output distribution via a general channel due to a fixed general source as an input. The obtained characterization of channel resolvability is fully general in the sense that, when the channel is just an identity mapping, it reduces to general formulas for source resolvability. We also analyze the second-order VL resolvability.
We introduce the problem of variable-length (VL) source resolvability, in which a given target probability distribution is approximated by encoding a VL uniform random number, and the asymptotically minimum average length rate of the uniform random number, called the VL resolvability, is investigated. We first analyze the VL resolvability with the variational distance as an approximation measure. Next, we investigate the case under the divergence as an approximation measure. When the asymptotically exact approximation is required, it is shown that the resolvability under two kinds of approximation measures coincides. We then extend the analysis to the case of channel resolvability, where the target distribution is the output distribution via a general channel due to a fixed general source as an input. The obtained characterization of channel resolvability is fully general in the sense that, when the channel is just an identity mapping, it reduces to general formulas for source resolvability. We also analyze the second-order VL resolvability.
The problem of channel resolvability, where a given output probability distribution over a channel is approximated by encoding uniform random number as a channel input, is addressed. The channel resolvability has recently been generalized to the variable-length setting, where the variable-length uniform random number instead of the fixed-length one is encoded. Though the optimum resolvability rate can be reduced compared with the fixed-length resolvability, it is not yet clear how much resolvability rate can be saved even when the given source and channel are stationary and memoryless. Given a stationary memoryless source and a discrete memoryless channel, this paper establishes a single-letter formula for the variable-length resolvability under the variational distance as an approximation measure. When the channel is a full-rank discrete memoryless channel, the established formula reduces to a further simpler formula characterized by the mutual information between the source and the channel. The established formula also recovers a known formula for the variable-length source resolvability.
The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) Rényi divergence (with the Rényi parameter in [0,2]∪{∞}) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi parameter is larger than or equal to 1 as well as (lower and upper) bounds for the case when the same parameter is smaller than 1. We characterize the Rényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than~1, consistent with the traditional case where the Rényi parameter is equal to~1, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than 1 the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the Rényi resolvability. The optimal exponential rate of decay for i.i.d.\ random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeoff between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) Rényi divergence.
Eγ-Resolvability
The conventional channel resolvability refers to the minimum rate needed for an input process to approximate the channel output distribution in total variation distance. In this paper, we study Eγ-resolvability, in which total variation is replaced by the more general Eγdistance. A general one-shot achievability bound for the precision of such an approximation is developed. Let QX|Ube a random transformation, n be an integer, and E ∈ (0, +∞). We show that in the asymptotic setting where γ = exp(nE), a (nonnegative) randomness rate above inf QU:D(QXIIπX)≤E{D(QXIIπX) + I(QU, QX|U) - E} is sufficient to approximate the output distribution πX⊗nusing the channel QX|U⊗n, where QU→ QX|U→ QX, and is also necessary in the case of finite U and X . In particular, a randomness rate of inf QUI(QU, QX|U) - E is always sufficient. We also study the convergence of the approximation error under the high-probability criteria in the case of random codebooks. Moreover, by developing simple bounds relating Eγand other distance measures, we are able to determine the exact linear growth rate of the approximation errors measured in relative entropy and smooth Rényi divergences for a fixed-input randomness rate. The new resolvability result is then used to derive: 1) a one-shot upper bound on the probability of excess distortion in lossy compression, which is exponentially tight in the i.i.d. setting; 2) a one-shot version of the mutual covering lemma; and 3) a lower bound on the size of the eavesdropper list to include the actual message and a lower bound on the eavesdropper false-alarm probability in the wiretap channel problem, which is (asymptotically) ensemble-tight.
The conventional channel resolvability problem refers to the determination of the minimum rate required for an input process so that the output distribution approximates a target distribution in either the total variation distance or the relative entropy. In contrast to previous works, in this paper, we use the (normalized or unnormalized) Rényi divergence (with the Rényi parameter in[0, 2] U {∞}) to measure the level of approximation. We also provide asymptotic expressions for normalized Rényi divergence when the Rényi parameter is larger than or equal to 1 as well as (lower and upper) bounds for the case when the same parameter is smaller than 1. We characterize the Rényi resolvability, which is defined as the minimum rate required to ensure that the Rényi divergence vanishes asymptotically. The Rényi resolvabilities are the same for both the normalized and unnormalized divergence cases. In addition, when the Rényi parameter smaller than 1, consistent with the traditional case where the Rényi parameter is equal to 1, the Rényi resolvability equals the minimum mutual information over all input distributions that induce the target output distribution. When the Rényi parameter is larger than 1 the Rényi resolvability is, in general, larger than the mutual information. The optimal Rényi divergence is proven to vanish at least exponentially fast for both of these two cases, as long as the code rate is larger than the Rényi resolvability. The optimal exponential rate of decay for i.i.d. random codes is also characterized exactly. We apply these results to the wiretap channel, and completely characterize the optimal tradeoff between the rates of the secret and non-secret messages when the leakage measure is given by the (unnormalized) Rényi divergence. This tradeoff differs from the conventional setting when the leakage is measured by the traditional mutual information.
This paper deals with the source resolvability problem which is one of typical random number generation problems. In the literatures, the achievable rate in the source resolvability problem with respect to the variational distance as well as the Kullback-Leibler (KL) divergence have been analyzed. On the other hand, in this study we consider the problem with respect to a subclass of f-divergence. The f-divergence is a general non-negative measure between two probabilistic distributions and 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 source resolvability problem with respect to the f-divergence. We derive the general formula of the optimum achievable rate for a certain subclass of the f-divergence. Then, we reveal that it is easy to derive previous results from our general formula.
We study the problem of generating an approximately i.i.d. string at the output of a discrete memoryless channel using a limited amount of randomness at its input in presence of causal noiseless feedback. Feedback does not decrease the channel resolution, the minimum entropy rate required to achieve an accurate approximation of an i.i.d. output string. However, we show that, at least over a binary symmetric channel, a significantly larger resolvability exponent (the exponential decay rate of the divergence between the output distribution and product measure), compared to the best known achievable resolvability exponent in a system without feedback, is possible. We show that by employing a variable-length resolvability scheme and using an average number of coin-flips per channel use, the average divergence between the distribution of the output sequence and product measure decays exponentially fast in the average length of output sequence with an exponent equal to [R−I(U;V)]+ where I(U;V) is the mutual information developed across the channel.