Tight optimal bounds found for one-shot channel simulation and representation
The Optimal Constant for One-Shot Channel Simulation and Strong Functional Representation Lemma
Information Theory
Summary
This paper finds the best possible limits for simulating a communication channel in a single attempt, meaning it precisely describes how efficiently one can recreate output based on input information. The authors prove a stronger version of a known tool called the functional representation lemma with a constant term that cannot be improved. They also show their method closely matches the best known approaches and provide a simple formula to estimate simulation costs. These results help us understand the fundamental limits of encoding and simulating information accurately in communication systems.
What this means in practice
- •For communication system designers: Design more efficient encoding schemes for single-use or limited-use communication channels based on tight fundamental limits.
- •For data compression engineers: Optimize finite-blocklength compression algorithms by using bounds on channel simulation redundancy derived from the new tight results.
A theory result. No direct application yet.
Authors
Cheuk Ting Li
Abstract
We prove a tight bound for one-shot channel simulation via a stronger version of the strong functional representation lemma: for any random variables $X,Y$, there exists a random variable $Z$ with $I(Z;X)=H(Y|X,Z)=0$ and $H(Y|Z)\le I+\log I+(1-γ)\log e-\log\log e+O(I^{-1}\log I)$, where $I=I(X;Y)$ and $γ$ is the Euler-Mascheroni constant. A more convenient bound is $H(Y|Z)<I+\log(I+2)+1$. The first bound is notable in the sense that the constant term $(1-γ)\log e-\log\log e$ is optimal, and cannot be improved for any bound stated only in terms of $I$. Hence, this is the tightest form of the strong functional representation lemma up to the third order. We also prove that the Poisson functional representation is almost optimal up to a constant gap, and provide a simple finite-blocklength achievability bound that implies the $(1/2)\log n$ redundancy of the simulation of memoryless non-singular channel. These are proved via a generalization of the functional information, in particular, the exponential functional information, which closely approximates the cost of one-shot channel simulation.