Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Information Theory

Source and Channel Simulation Using Arbitrary Randomness

Yücel Altuğ, Aaron B. Wagner

Published Feb 28, 2012• 6 citations
Publisher

Abstract

Necessary and sufficient conditions for approximation of a general channel by a general source are proved. For the special case of a deterministic channel input, which corresponds to source simulation, we prove a stronger necessary condition. As the approximation criteria, vanishing variational distance between the original and the approximated quantity is used for both of the problems. Both necessary and sufficient conditions for the two problems are based on some individual properties of the sources and the channel and are relatively easy to evaluate. In particular, unlike prior results for this problem, our results do not require solving an optimization problem to test simulatability. The results are illustrated with several nonergodic examples.

DOI
10.1109/tit.2011.2178136

Related papers

Source and channel simulation using arbitrary randomness

Yücel Altuğ, Aaron B. Wagner

Necessary and sufficient conditions for approximation of a general channel by a general source are proved. For the special case in which the channel input is deterministic, which corresponds to source simulation, we prove a stronger necessary condition. As the approximation criteria, vanishing variational distance between the original and the approximated quantity is used for both of the problems. Both necessary and sufficient conditions for the two problems are based on some individual properties of the sources and the channel and are relatively easy to evaluate. In particular, unlike prior results for this problem, our results do not require solving an optimization problem to test simulatability.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2009•0 citations

Source and Channel Simulation Using Arbitrary Randomness

Yücel Altuğ, Aaron B. Wagner

Necessary and sufficient conditions for approximation of a general channel by a general source are proved. For the special case in which the channel input is deterministic, which corresponds to source simulation, we prove a stronger necessary condition. As the approximation criteria, vanishing variational distance between the original and the approximated quantity is used for both of the problems. Both necessary and sufficient conditions for the two problems are based on some individual properties of the sources and the channel and are relatively easy to evaluate. In particular, unlike prior results for this problem, our results do not require solving an optimization problem to test simulatability. The results are illustrated with several non-ergodic examples.

arXiv:0908.2141•Aug 14, 2009•0 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 Theory•Jan 1, 2000•12 citations

Variable-Length Resolvability for General Sources and Channels

Hideki Yagi, Te Sun Han

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.

arXiv:1701.08712•Entropy•Oct 19, 2023•7 citations

$E_{\gamma}$-Resolvability

Jingbo Liu, Paul Cuff, Sergio Verdú

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.

arXiv:1511.07829•IEEE Transactions on Information Theory•Jan 1, 2016•22 citations

Resolvability theory for the multiple-access channel

Yossef Steinberg

We study the randomness needed for approximating the output distribution of a multiple-access channel, where the original input processes are independent of each other. The approximation is achieved by simulating (possibly alternative) input processes at each of the entries, where the sources of randomness available for the simulators are independent of each other, and the simulators do not cooperate. The resolvability region of a multiple-access channel is defined as the set of all random-bit rate pairs at which accurate output approximation is possible, where the simulation accuracy is measured by the variational distance between finite-dimensional output distributions. Inner and outer bounds on the resolvability region are derived, and close relations between the concepts of resolvability region and capacity region are demonstrated.

IEEE Transactions on Information Theory•Mar 1, 1998•33 citations
Necessary and sufficient conditions for approximation of a general channel by a general source are proved. For the special case of a deterministic channel input, which corresponds to source simulation, we prove a stronger necessary condition. As the approximation criteria, vanishing variational distance between the original and the approximated quantity is used for both of the problems. Both necessary and sufficient conditions for the two problems are based on some individual properties of the sources and the channel and are relatively easy to evaluate. In particular, unlike prior results for this problem, our results do not require solving an optimization problem to test simulatability. The results are illustrated with several nonergodic examples.
Necessary and sufficient conditions for approximation of a general channel by a general source are proved. For the special case in which the channel input is deterministic, which corresponds to source simulation, we prove a stronger necessary condition. As the approximation criteria, vanishing variational distance between the original and the approximated quantity is used for both of the problems. Both necessary and sufficient conditions for the two problems are based on some individual properties of the sources and the channel and are relatively easy to evaluate. In particular, unlike prior results for this problem, our results do not require solving an optimization problem to test simulatability.
Necessary and sufficient conditions for approximation of a general channel by a general source are proved. For the special case in which the channel input is deterministic, which corresponds to source simulation, we prove a stronger necessary condition. As the approximation criteria, vanishing variational distance between the original and the approximated quantity is used for both of the problems. Both necessary and sufficient conditions for the two problems are based on some individual properties of the sources and the channel and are relatively easy to evaluate. In particular, unlike prior results for this problem, our results do not require solving an optimization problem to test simulatability. The results are illustrated with several non-ergodic examples.
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.
EγE_{\gamma}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.
We study the randomness needed for approximating the output distribution of a multiple-access channel, where the original input processes are independent of each other. The approximation is achieved by simulating (possibly alternative) input processes at each of the entries, where the sources of randomness available for the simulators are independent of each other, and the simulators do not cooperate. The resolvability region of a multiple-access channel is defined as the set of all random-bit rate pairs at which accurate output approximation is possible, where the simulation accuracy is measured by the variational distance between finite-dimensional output distributions. Inner and outer bounds on the resolvability region are derived, and close relations between the concepts of resolvability region and capacity region are demonstrated.