betaFeedback

WorksComputer Science

Functional Information, Optimal Channel Simulation and Lossy Source Coding

Abstract

We characterize, within a constant number of bits, the minimum achievable rate for several one-shot coding problems, such as channel simulation and lossy source coding. The basis of our work is a new information measure between random variables X,YX, Y that we call the functional information IF(X→Y)I_F(X \to Y). We show that this quantity characterizes the minimum one-shot rate R∗(X→Y)R^*(X \to Y) of channel simulation, in which a sample Y∼PY∣XY \sim P_{Y \mid X} is communicated in the presence of common randomness: IF(X→Y)≤R∗(X→Y)<IF(X→Y)+1.45I_F(X \to Y) \leq R^*(X \to Y) < I_F(X \to Y) + 1.45. For the achievability result, we construct an explicit code using the Poisson functional representation. Using these results, we develop new bounds for one-shot variable-rate lossy source coding: given some distortion measure ΔΔ, we use IF(X→Y)I_F(X \to Y) to define the functional rate-distortion function RFR_F. Then, letting ROR_O denote the one-shot operational rate-distortion function with private encoder randomness and distortion measure ΔΔ, we make use of our channel simulation result to show that RF(D)≤RO(D)<RF(D)+2.45R_F(D) \leq R_O(D) < R_F(D) + 2.45 at every positive distortion level DD. Finally, we generalize our channel simulation result by introducing the Rényi αα-functional information IF,α(X→Y)I_{F, α}(X \to Y) and show that it characterizes the minimum Arimoto-Rényi conditional entropy for channel simulation, Rα∗(X→Y){R^*_α(X \to Y)}, associated with the Campbell cost: IF,α(X→Y)≤Rα∗(X→Y)≤IF,α(X→Y)+O(1/α){I_{F, α}(X \to Y) \leq R^*_α(X \to Y) \leq I_{F, α}(X \to Y) + O(1/α)}.

Introduction

CHARACTERIZING the minimum number of bits required to encode some data is a central aim of information theory. Yet, despite some steady progress in recent years, the field still lacks tight nonasymptotic results for several fundamental problems. Our paper makes progress in addressing this gap.

Our foundational result is a tight nonasymptotic characterization of the best achievable rate for the problem known as channel simulation (relative entropy coding) [1], [2]. Let XX and YY be random variables taking values in the Polish spaces X\mathcal{X} and Y\mathcal{Y}, respectively, with joint distribution PX,YP_{X,Y}. Consider the induced Markov kernel (channel) PY∣X=xP_{Y\mid X=x} and the triplet (Z,enc,dec)(Z,\mathrm{enc},\mathrm{dec}) consisting of

  • Z∈ZZ \in\mathcal{Z}, a random variable independent of XX (denoted Z⊥XZ \perp X) called the common randomness, which is shared by the encoder and decoder;

  • enc:X×Z→{0,1}∗\mathrm{enc}:\mathcal{X} \times\mathcal{Z} \to\{0,1\}^{*}, an encoder mapping an input and a realization of the common randomness to a binary string, with the induced code being uniquely decodable for each realization of the common randomness (where {0,1}∗\{0,1\}^{*} is the set of all finite-length binary strings);

  • dec:{0,1}∗×Z→Y\mathrm{dec}:\{0,1\}^{*} \times\mathcal{Z} \to\mathcal{Y}, a decoder mapping the encoder output and common randomness to a point y∈Yy \in\mathcal{Y}.

We say that (Z,enc,dec)(Z,\mathrm{enc},\mathrm{dec}) is a stochastic code for PY∣XP_{Y\mid X} if, for PXP_X-almost all inputs x∈Xx \in\mathcal{X},

dec⁡(enc⁡(x,Z),Z)∼PY∣X=x.(1)\operatorname{dec}(\operatorname{enc}(x,Z),Z) \sim P_{Y\mid X=x}. \tag*{(1)}

When no confusion arises, we identify YY with the code’s output dec⁡(enc⁡(X,Z),Z)\operatorname{dec}(\operatorname{enc}(X,Z),Z) on input XX. Let ∣s∣|s| denote the length of a binary string s∈{0,1}∗s \in\{0,1\}^{*}, we are interested in describing the minimum expected code-length of any stochastic code,

L∗(X→Y)≜inf⁡(Z,enc,dec)E[∣enc⁡(X,Z)∣],(2)L^{*}(X \to Y) \triangleq\inf_{(Z,\mathrm{enc},\mathrm{dec})} \mathbb{E}[|\operatorname{enc}(X,Z)|], \tag*{(2)}

where the infimum is taken over all stochastic codes.

While we keep the above quantity as the main object of practical interest, we can somewhat simplify the problem by instead considering the minimum conditional entropy of the output of a stochastic code,

R∗(X→Y)≜inf⁡(Z,enc,dec)H(Y∣Z).(3)R^{*}(X \to Y) \triangleq\inf_{(Z,\mathrm{enc},\mathrm{dec})} H(Y\mid Z). \tag*{(3)}

By standard lossless source coding results, these quantities have the simple relationship

R∗(X→Y)≤L∗(X→Y)≤R∗(X→Y)+1.(4)R^{*}(X \to Y) \le L^{*}(X \to Y) \le R^{*}(X \to Y) + 1. \tag*{(4)}

The minimum achievable rate of stochastic codes was first characterized for discrete channels in terms of the mutual information I(X;Y)I(X;Y) by Harsha et al. [3], and later generalized to arbitrary channels by Li and El Gamal [4]. General bounds on R∗(X→Y)R^{*}(X \to Y) were derived in the expanded version of [5], where it was shown that

I(X;Y)≤R∗(X→Y)<I(X;Y)+log⁡(I(X;Y)+1)+2.74.I(X;Y) \le R^{*}(X \to Y) < I(X;Y)+\log(I(X;Y)+1)+2.74.

While these results are undoubtedly remarkable, there remains a logarithmic gap (i.e., a gap of order log⁡(I(X;Y)+1)\log(I(X;Y)+1)) between the upper and lower bounds, which has been shown to be necessary in general: there exist channels for which R∗(X→Y)R^{*}(X \to Y) is within a constant of the upper bound and others for which it is within a constant of the lower bound [4, 6].

In light of the above fact, one suspects that a new information measure is needed to close this gap. To this end, we propose the functional information IF(X→Y)I_{\mathrm{F}}(X \to Y) (see Definition 3 in Section II-B) and prove the following result, which forms the basis of all further results in the paper.

Theorem 1. Let XX and YY be jointly distributed random variables over an arbitrary Polish space. Then,

IF(X→Y)≤R∗(X→Y)≤IF(X→Y)+log⁡e.(5)I_{\mathrm{F}}(X \to Y) \le R^{*}(X \to Y) \le I_{\mathrm{F}}(X \to Y) + \log e. \tag*{(5)}

Theorem 1 demonstrates that IF(X→Y)I_{\mathrm{F}}(X \to Y) is the “correct” information measure for the channel simulation problem. A special case of the lower bound in (5) for discrete YY has previously appeared in different notation as Proposition 1 in [4] and was later proven for arbitrary YY in [7, 8]. Here, we give a new, much-simplified proof of the general lower bound result (Theorem 4). Moreover, by analyzing the equality condition, we fully characterize the conditions for so-called perfect functional representations (see Proposition 6), thus significantly extending the results of [9]. The upper bound in (5) has only recently been shown to be achievable (within log⁡e\log e bits) for additive exchangeable noise channels with finite field input in [10]. However, contemporaneously, we independently developed a significantly more general achievability result for arbitrary channels in [11] by providing an explicit code constructed using rejection sampling. Unfortunately, the result in [11] only holds under restrictive assumptions on the joint distribution of XX and YY. In this paper, we construct a different code based on the Poisson functional representation [4] that completely removes this restriction (see Theorem 5 in Section IV-A). This allows us to state the upper and lower bounds at the same level of generality.1 Two immediate consequences of Theorem 1 are (i) a mutual information-based upper bound with a tighter constant than that in [5] (see Corollary 1) and (ii) the recovery, using Corollary 2, of the results of [8, 13] on the second-order redundancy of asymptotic channel simulation (see Corollary 3).

Moreover, as the main application of Theorem 1, we characterize within a constant the best achievable rate in variable-rate lossy source coding for any finite blocklength in terms of the functional information. For a fixed source distribution PXP_X, given a distortion measure Δ:X×Y→[0,∞)\Delta:\mathcal{X}\times\mathcal{Y}\to[0,\infty), we define the functional rate-distortion function RF(D)R_{\mathrm{F}}(D) as

RF(D)≜inf⁡PY∣X:E[Δ(X,Y)]≤DIF(X→Y).(6)R_{\mathrm{F}}(D) \triangleq\inf_{P_{Y|X}:\mathbb{E}[\Delta(X,Y)]\le D} I_{\mathrm{F}}(X \to Y). \tag*{(6)}

Analogously, we define the variable-rate operational rate-distortion function as

RO(D)≜inf⁡PY∣X:E[Δ(X,Y)]≤Dcountably-valuedH(Y).(7)R_{\mathrm{O}}(D) \triangleq\inf_{P_{Y|X}:\mathbb{E}[\Delta(X,Y)]\le D\atop\text{countably-valued}} H(Y). \tag*{(7)}

Here the encoder uses private randomness to draw YY according to PY∣XP_{Y|X} and sends its index to the decoder. Following Li and El Gamal [4 Proof of Thm. 2], the encoder can achieve RO(D)R_{\mathrm{O}}(D) to arbitrary precision by randomizing between two deterministic quantizers Y=g0(X)Y=g_0(X) and Y=g1(X)Y=g_1(X). We prove the following result in Section V.

Theorem 2. Let X\mathcal{X} and Y\mathcal{Y} be Polish spaces. For any source distribution PXP_X and any D>0D>0,

RF(D)≤RO(D)≤RF(D)+log⁡e+1.(8)R_{\mathrm{F}}(D) \le R_{\mathrm{O}}(D) \le R_{\mathrm{F}}(D) + \log e + 1. \tag*{(8)}

Now let Xn=(X1,…,Xn)X^n=(X_1,\ldots,X_n) and Yn=(Y1,…,Yn)Y^n=(Y_1,\ldots,Y_n) be nn-blocks and consider the average single-letter distortion measure Δn(xn,yn)=1n∑i=1nΔ(xi,yi)\Delta_n(x^n,y^n)=\frac{1}{n}\sum_{i=1}^{n}\Delta(x_i,y_i). If we replace Δ\Delta with Δn\Delta_n and let RF,n(D)R_{\mathrm{F},n}(D) and RO,n(D)R_{\mathrm{O},n}(D) be the nnth-order versions of RF(D)R_{\mathrm{F}}(D) and RO(D)R_{\mathrm{O}}(D), normalized by nn, then Theorem 2 implies

RF,n(D)≤RO,n(D)≤RF,n(D)+log⁡e+1n.(9)R_{\mathrm{F},n}(D) \le R_{\mathrm{O},n}(D) \le R_{\mathrm{F},n}(D) + \frac{\log e + 1}{n}. \tag*{(9)}

The proof of Theorem 2 uses Theorem 1 and the two-quantizer construction. Classically, the fundamental limits of lossy compression were achievable only in the asymptotic limit. Previous finite-length bounds or refined asymptotic analyses (see [14] for an overview) provide lower and upper bounds with a logarithmic gap in the block-length of the encoded source, or are valid only for particular distortions and source distributions [15]. A recent single-shot upper bound [16] also leaves a logarithmic gap over the rate-distortion function lower bound. Our result, in terms of the functional information, is tight within a constant and valid for any source distribution, distortion measure, and blocklength. In particular, we are not aware of any previous result that gives lower and upper bounds on the optimal normalized rate in lossy coding nn-blocks under an expected distortion constraint with only an O(1/n)O(1/n) gap as in (9).

Finally, in Section VI we define the Rényi generalization of the functional information IF,α(X→Y)I_{F,\alpha}(X \to Y) for α∈(0,1)\alpha\in(0,1), having the property lim⁡α→1IF,α(X→Y)=IF(X→Y)\lim_{\alpha\to1} I_{F,\alpha}(X \to Y) = I_F(X \to Y). Then, we show that it too operationally characterizes the channel simulation problem under the so-called Campbell cost [17]. Concretely, for t>0t > 0 let the Campbell (exponential) cost of the stochastic code (Z,enc⁡,dec⁡)(Z,\operatorname{enc},\operatorname{dec}) be

Lt≜1tlog⁡(E[2t∣enc⁡(X,Z)∣]),(10)L_t \triangleq\frac{1}{t}\log\left(\mathbb{E}\left[2^{t|\operatorname{enc}(X,Z)|}\right]\right), \tag*{(10)}

and define the optimal Campbell cost over all stochastic codes as

Lt∗(X→Y)≜inf⁡(Z,enc⁡,dec⁡)Lt.(11)L_t^*(X \to Y) \triangleq\inf_{(Z,\operatorname{enc},\operatorname{dec})} L_t. \tag*{(11)}

A related quantity is the minimum Arimoto-Rényi conditional entropy HαAH_\alpha^A of order α∈(0,1)\alpha\in(0,1) (defined in (85)) [18] over all stochastic codes:

Rα∗(X→Y)≜inf⁡(Z,enc⁡,dec⁡)HαA(Y∣Z).(12)R_\alpha^*(X \to Y) \triangleq\inf_{(Z,\operatorname{enc},\operatorname{dec})} H_\alpha^A(Y \mid Z). \tag*{(12)}

It follows from the main result of [17] that with α=1t+1\alpha= \frac{1}{t+1}, these quantities are related as

Rα∗(X→Y)≤Lt∗(X→Y)≤Rα∗(X→Y)+1.(13)R_\alpha^*(X \to Y) \le L_t^*(X \to Y) \le R_\alpha^*(X \to Y) + 1. \tag*{(13)}

Given the above, we prove the following result.

Theorem 3. Let X,YX,Y be jointly distributed random variables over arbitrary Polish spaces and let α∈(0,1)\alpha\in(0,1). Then,

IF,α(X→Y)≤Rα∗(X→Y)≤IF,α(X→Y)+1−αα+log⁡(1/α)1−α.(14)I_{F,\alpha}(X \to Y) \le R_\alpha^*(X \to Y) \le I_{F,\alpha}(X \to Y) + \frac{1-\alpha}{\alpha} + \frac{\log(1/\alpha)}{1-\alpha}. \tag*{(14)}

References

  1. [1]C. T. Li, “Channel simulation: Theory and applications to lossy compression and differential privacy,” Foundations and Trends® in Communications and Information Theory, vol. 21, no. 6, pp. 847–1106, 2024.DOI
  2. [2]G. Flamich and D. Gündüz, “Data compression with stochastic codes,” arXiv preprint arXiv:2602.07635, 2026.arxiv.org/abs/2602.07635
  3. [3]P. Harsha, R. Jain, D. McAllester, and J. Radhakrishnan, “The communication complexity of correlation,” IEEE Transactions on Information Theory, vol. 56, no. 1, pp. 438–449, 2010.
  4. [4]C. T. Li and A. El Gamal, “Strong functional representation lemma and applications to coding theorems,” IEEE Transactions on Information Theory, vol. 64, no. 11, pp. 6967–6978, 2018.arxiv.org/abs/1701.02827
  5. [5]C. T. Li, “Discrete layered entropy, conditional compression and a tighter strong functional representation lemma,” in Proc. 2025 IEEE International Symposium on Information Theory (ISIT). IEEE, 2025, pp. 1–6.
  6. [6]M. Braverman and A. Garg, “Public vs private coin in bounded-round information,” in Proc. International Colloquium on Automata, Languages, and Programming. Springer, 2014, pp. 502–513.DOI
  7. [7]G. Flamich, “Data Compression with Relative Entropy Coding,” Ph.D. dissertation, University of Cambridge (United Kingdom), 2024.
  8. [8]G. Flamich, S. M. Sriramu, and A. B. Wagner, “The redundancy of non-singular channel simulation,” in Proc. 2025 IEEE International Symposium on Information Theory (ISIT). IEEE, 2025, pp. 1–6.arxiv.org/abs/2501.14053
  9. [9]S. E. Coban, Y. Y. Shkel, and E. Telatar, “On perfect functional representations,” in Proc. 2026 IEEE International Symposium on Information Theory (ISIT), 2026.DOI
  10. [10]J. Zhao and C. T. Li, “Rejection-sampled linear codes for lossy compression and channel simulation,” arXiv preprint arXiv:2506.09239, 2025.arxiv.org/abs/2506.09239
  11. [11]S. Hill, F. Alajaji, T. Linder, and G. Flamich, “Rejection sampling is optimal for relative entropy coding,” in Proc. 2026 IEEE International Information Theory Workshop (ITW), 2026, pp. 1–6.arxiv.org/abs/2604.23076
  12. [12]C. T. Li, “The optimal constant for one-shot channel simulation and strong functional representation lemma,” arXiv:2611.13397v1 [cs.IT], Nov. 2026.arxiv.org/abs/2611.13397
  13. [13]S. M. Sriramu and A. B. Wagner, “Optimal redundancy in exact channel synthesis,” in 2024 International Symposium on Information Theory (ISIT). IEEE, 2024, pp. 1913–1918.arxiv.org/abs/2401.16707
  14. [14]L. Zhou and M. Motani, “Finite blocklength lossy source coding for discrete memoryless sources,” Foundations and Trends® in Communications and Information Theory, vol. 20, no. 3, pp. 157–389, 2023.
  15. [15]O. Ordentlich, “The Voronoi spherical CDF for lattices and linear codes: New bounds for quantization and coding,” IEEE Transactions on Information Theory, vol. 72, no. 5, pp. 2931–2948, 2026.arxiv.org/abs/2506.19791
  16. [16]V. Kostina, “Single-shot lossy compression: mutual information bounds,” in Proceedings of the 2026 International Zurich Seminar on Information and Communication, Zurich, Switzerland, Feb. 2026.
  17. [17]L. L. Campbell, “A coding theorem and Rényi’s entropy,” Information and Control, vol. 8, no. 4, pp. 423–429, 1965.DOI
  18. [18]S. Arimoto, “Information measures and capacity of order α for discrete memoryless channels,” Topics in Information Theory, pp. 41–52, 1977.
  19. [19]S. Hill, F. Alajaji, and T. Linder, “Communication complexity of exact sampling under Rényi information,” IEEE Transactions on Information Theory, 2026.arxiv.org/abs/2506.12219
  20. [20]Y. Fan and A. B. Wagner, “Exact sampling under Campbell cost via Rényi channel simulation divergence,” arXiv preprint arXiv:2610.15656, 2026.arxiv.org/abs/2610.15656
  21. [21]D. Goc and G. Flamich, “On channel simulation with causal rejection samplers,” in Proc. 2024 IEEE International Symposium on Information Theory (ISIT), 2024.arxiv.org/abs/2401.16579
  22. [22]M. Hegazy and C. T. Li, “Randomized quantization with exact error distribution,” in Proc. 2022 IEEE Information Theory Workshop (ITW), 2022, pp. 350–355.DOI
  23. [23]G. Flamich, “Greedy Poisson rejection sampling,” Advances in Neural Information Processing Systems, vol. 36, pp. 37 089–37 127, 2023.arxiv.org/abs/2305.15313
  24. [24]E. H. Lieb and M. Loss, Analysis. American Mathematical Soc., 2001, vol. 14.
  25. [25]Y. M. Shtar’kov, “Universal sequential coding of single messages,” Problemy Peredachi Informatsii, vol. 23, no. 3, pp. 3–17, 1987.
  26. [26]G. Last and M. Penrose, Lectures on the Poisson process. Cambridge University Press, 2018, vol. 7.DOI
  27. [27]J. Liu and S. Verdu, “Rejection sampling and noncausal sampling under moment constraints,” in Proc. 2018 IEEE International Symposium on Information Theory (ISIT), 2018, pp. 1565–1569.DOI
  28. [28]G. Flamich, S. Markou, and J. M. Hernández-Lobato, “Fast relative entropy coding with A* coding,” in International Conference on Machine Learning. PMLR, 2022, pp. 6548–6577.arxiv.org/abs/2201.12857
  29. [29]G. Flamich and S. Hill, “Singular relative entropy coding with bits-back rejection sampling,” arXiv preprint arXiv:2604.06055, 2026.arxiv.org/abs/2604.06055
  30. [30]F. Alajaji, P.-N. Chen et al., An Introduction to Single-User Information Theory. Springer, 2018, vol. 3.DOI
  31. [31]J. Wei and M. Kountouris, “On the Rényi rate-distortion-perception function and functional representations,” arXiv preprint arXiv:2601.11862, 2026.arxiv.org/abs/2601.11862
  32. [32]F. Jelinek, “Buffer overflow in variable length coding of fixed rate sources,” IEEE Transactions on Information Theory, vol. 14, no. 3, pp. 490–501, 1968.DOI
  33. [33]P. Humblet, “Generalization of Huffman coding to minimize the probability of buffer overflow,” IEEE Transactions on Information Theory, vol. 27, no. 2, pp. 230–232, 1981.
  34. [34]A. C. Blumer and R. J. McEliece, “The Rényi redundancy of generalized Huffman codes,” IEEE Transactions on Information Theory, vol. 34, no. 5, pp. 1242–1249, 1988.DOI
  35. [35]A. Somazzi, P. Ferragina, and D. Garlaschelli, “On nonlinear compression costs: when Shannon meets Rényi,” IEEE Access, 2024.DOI
  36. [36]T. A. Courtade and S. Verdú, “Cumulant generating function of codeword lengths in optimal lossless compression,” in Proc. IEEE International Symposium on Information Theory (ISIT), 2014, pp. 2499–2503.DOI
  37. [37]———, “Variable-length lossy compression and channel coding: Non-asymptotic converses via cumulant generating functions,” in Proc. IEEE International Symposium on Information Theory (ISIT), 2014, pp. 2499–2503.DOI
  38. [38]S. Saito and T. Matsushima, “Non-asymptotic bounds of cumulant generating function of codeword lengths in variable-length lossy compression,” IEEE Transactions on Information Theory, vol. 69, no. 4, pp. 2113–2119, 2023.DOI
  39. [39]A. R. Esposito, M. Gastpar, and I. Issa, “Sibson α-mutual information and its variational representations,” IEEE Transactions on Information Theory, 2025.DOI
  40. [40]R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, ser. Grundlehren der mathematischen Wissenschaften. Berlin, Heidelberg: Springer, 1998, vol. 317.DOI
  41. [41]T. B. Phan and A. Khisti, “Channel simulation and distributed compression with ensemble rejection sampling,” Advances in Neural Information Processing Systems, vol. 38, pp. 43 066–43 123, 2026.arxiv.org/abs/2510.05552
  42. [42]G. Flamich and L. Theis, “Adaptive greedy rejection sampling,” in Proc. 2023 IEEE International Symposium on Information Theory (ISIT), 2023, pp. 454–459.DOI
  43. [43]P. Grunwald and P. Harremoës, “Finiteness of redundancy, regret, Shtarkov sums, and Jeffreys integrals in exponential families,” in Proc. 2009 IEEE International Symposium on Information Theory, 2009, pp. 714–718.DOI

Paper details

vlnc:W_xpkva82a
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-5.5 (bare), GPT 5.6, 6 (Astra)

View statement
Looking for related papers…
Contents