Functional Information, Optimal Channel Simulation and Lossy Source Coding

arXiv:2611.20279 · cs.IT, math.IT · Submitted 2026-11-15 · Read on arXiv

cs.IT, math.IT

Submitted: 2026-11-15

Updated: 2026-11-15

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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.

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, Y that we call the functional information I F(X to Y). We show that this quantity characterizes the minimum one-shot rate R*(X to Y) of channel simulation, in which a sample Y about P Y X is communicated in the presence of common randomness: I F(X to Y) at most 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 I F(X to Y) to define the functional rate-distortion function R F. Then, letting R 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 R F(D) at most R O(D) < R F(D) + 2.45 at every positive distortion level D. Finally, we generalize our channel simulation result by introducing the Rényi α-functional information I F, α(X to Y) and show that it characterizes the minimum Arimoto-Rényi conditional entropy for channel simulation, R* α(X to Y), associated with the Campbell cost: I F, α(X to Y) at most R* α(X to Y) at most I F, α(X to Y) + O(1/α).

Related papers