Introduction
C HARACTERIZING 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 X X X and Y Y Y be random variables taking values in the Polish spaces X \mathcal{X} X and Y \mathcal{Y} Y , respectively, with joint distribution P X , Y P_{X,Y} P X , Y . Consider the induced Markov kernel (channel) P Y ∣ X = x P_{Y\mid X=x} P Y ∣ X = x and the triplet ( Z , e n c , d e c ) (Z,\mathrm{enc},\mathrm{dec}) ( Z , enc , dec ) consisting of
Z ∈ Z Z \in\mathcal{Z} Z ∈ Z , a random variable independent of X X X (denoted Z ⊥ X Z \perp X Z ⊥ X ) called the common randomness , which is shared by the encoder and decoder;
e n c : X × Z → { 0 , 1 } ∗ \mathrm{enc}:\mathcal{X} \times\mathcal{Z} \to\{0,1\}^{*} enc : X × Z → { 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\}^{*} { 0 , 1 } ∗ is the set of all finite-length binary strings);
d e c : { 0 , 1 } ∗ × Z → Y \mathrm{dec}:\{0,1\}^{*} \times\mathcal{Z} \to\mathcal{Y} dec : { 0 , 1 } ∗ × Z → Y , a decoder mapping the encoder output and common randomness to a point y ∈ Y y \in\mathcal{Y} y ∈ Y .
We say that ( Z , e n c , d e c ) (Z,\mathrm{enc},\mathrm{dec}) ( Z , enc , dec ) is a stochastic code for P Y ∣ X P_{Y\mid X} P Y ∣ X if, for P X P_X P X -almost all inputs x ∈ X x \in\mathcal{X} x ∈ X ,
dec ( enc ( x , Z ) , Z ) ∼ P Y ∣ X = x . (1) \operatorname{dec}(\operatorname{enc}(x,Z),Z) \sim P_{Y\mid X=x}. \tag*{(1)} dec ( enc ( x , Z ) , Z ) ∼ P Y ∣ X = x . (1)
When no confusion arises, we identify Y Y Y with the code’s output dec ( enc ( X , Z ) , Z ) \operatorname{dec}(\operatorname{enc}(X,Z),Z) dec ( enc ( X , Z ) , Z ) on input X X X . Let ∣ s ∣ |s| ∣ s ∣ denote the length of a binary string s ∈ { 0 , 1 } ∗ s \in\{0,1\}^{*} s ∈ { 0 , 1 } ∗ , we are interested in describing the minimum expected code-length of any stochastic code,
L ∗ ( X → Y ) ≜ inf ( Z , e n c , d e c ) E [ ∣ enc ( X , Z ) ∣ ] , (2) L^{*}(X \to Y) \triangleq\inf_{(Z,\mathrm{enc},\mathrm{dec})} \mathbb{E}[|\operatorname{enc}(X,Z)|], \tag*{(2)} L ∗ ( X → Y ) ≜ ( Z , enc , dec ) inf E [ ∣ enc ( X , Z ) ∣ ] , (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 , e n c , d e c ) H ( Y ∣ Z ) . (3) R^{*}(X \to Y) \triangleq\inf_{(Z,\mathrm{enc},\mathrm{dec})} H(Y\mid Z). \tag*{(3)} R ∗ ( X → Y ) ≜ ( Z , enc , dec ) inf H ( Y ∣ Z ) . (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)} R ∗ ( X → Y ) ≤ L ∗ ( X → Y ) ≤ R ∗ ( X → Y ) + 1. (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) 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) R ∗ ( X → 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. I ( X ; Y ) ≤ R ∗ ( X → 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) 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) R ∗ ( X → 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 I F ( X → Y ) I_{\mathrm{F}}(X \to Y) I F ( X → 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 X X X and Y Y Y be jointly distributed random variables over an arbitrary Polish space. Then,
I F ( X → Y ) ≤ R ∗ ( X → Y ) ≤ I F ( 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)} I F ( X → Y ) ≤ R ∗ ( X → Y ) ≤ I F ( X → Y ) + log e . (5)
Theorem 1 demonstrates that I F ( X → Y ) I_{\mathrm{F}}(X \to Y) I F ( X → Y ) is the “correct” information measure for the channel simulation problem. A special case of the lower bound in (5) for discrete Y Y Y has previously appeared in different notation as Proposition 1 in [4 ] and was later proven for arbitrary Y Y Y 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 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 X X X and Y Y Y . 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 P X P_X P X , given a distortion measure Δ : X × Y → [ 0 , ∞ ) \Delta:\mathcal{X}\times\mathcal{Y}\to[0,\infty) Δ : X × Y → [ 0 , ∞ ) , we define the functional rate-distortion function R F ( D ) R_{\mathrm{F}}(D) R F ( D ) as
R F ( D ) ≜ inf P Y ∣ X : E [ Δ ( X , Y ) ] ≤ D I F ( 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)} R F ( D ) ≜ P Y ∣ X : E [ Δ ( X , Y )] ≤ D inf I F ( X → Y ) . (6)
Analogously, we define the variable-rate operational rate-distortion function as
R O ( D ) ≜ inf P Y ∣ X : E [ Δ ( X , Y ) ] ≤ D countably-valued H ( 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)} R O ( D ) ≜ countably-valued P Y ∣ X : E [ Δ ( X , Y )] ≤ D inf H ( Y ) . (7)
Here the encoder uses private randomness to draw Y Y Y according to P Y ∣ X P_{Y|X} P Y ∣ X and sends its index to the decoder. Following Li and El Gamal [4 Proof of Thm. 2] , the encoder can achieve R O ( D ) R_{\mathrm{O}}(D) R O ( D ) to arbitrary precision by randomizing between two deterministic quantizers Y = g 0 ( X ) Y=g_0(X) Y = g 0 ( X ) and Y = g 1 ( X ) Y=g_1(X) Y = g 1 ( X ) . We prove the following result in Section V.
Theorem 2. Let X \mathcal{X} X and Y \mathcal{Y} Y be Polish spaces. For any source distribution P X P_X P X and any D > 0 D>0 D > 0 ,
R F ( D ) ≤ R O ( D ) ≤ R F ( D ) + log e + 1. (8) R_{\mathrm{F}}(D) \le R_{\mathrm{O}}(D) \le R_{\mathrm{F}}(D) + \log e + 1. \tag*{(8)} R F ( D ) ≤ R O ( D ) ≤ R F ( D ) + log e + 1. (8)
Now let X n = ( X 1 , … , X n ) X^n=(X_1,\ldots,X_n) X n = ( X 1 , … , X n ) and Y n = ( Y 1 , … , Y n ) Y^n=(Y_1,\ldots,Y_n) Y n = ( Y 1 , … , Y n ) be n n n -blocks and consider the average single-letter distortion measure Δ n ( x n , y n ) = 1 n ∑ i = 1 n Δ ( x i , y i ) \Delta_n(x^n,y^n)=\frac{1}{n}\sum_{i=1}^{n}\Delta(x_i,y_i) Δ n ( x n , y n ) = n 1 ∑ i = 1 n Δ ( x i , y i ) . If we replace Δ \Delta Δ with Δ n \Delta_n Δ n and let R F , n ( D ) R_{\mathrm{F},n}(D) R F , n ( D ) and R O , n ( D ) R_{\mathrm{O},n}(D) R O , n ( D ) be the n n n th-order versions of R F ( D ) R_{\mathrm{F}}(D) R F ( D ) and R O ( D ) R_{\mathrm{O}}(D) R O ( D ) , normalized by n n n , then Theorem 2 implies
R F , n ( D ) ≤ R O , n ( D ) ≤ R F , n ( D ) + log e + 1 n . (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)} R F , n ( D ) ≤ R O , n ( D ) ≤ R F , n ( D ) + n log e + 1 . (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 n n n -blocks under an expected distortion constraint with only an O ( 1 / n ) O(1/n) O ( 1/ n ) gap as in (9) .
Finally, in Section VI we define the Rényi generalization of the functional information I F , α ( X → Y ) I_{F,\alpha}(X \to Y) I F , α ( X → Y ) for α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , having the property lim α → 1 I F , α ( X → Y ) = I F ( X → Y ) \lim_{\alpha\to1} I_{F,\alpha}(X \to Y) = I_F(X \to Y) lim α → 1 I F , α ( X → Y ) = I F ( X → Y ) . Then, we show that it too operationally characterizes the channel simulation problem under the so-called Campbell cost [17 ] . Concretely, for t > 0 t > 0 t > 0 let the Campbell (exponential) cost of the stochastic code ( Z , enc , dec ) (Z,\operatorname{enc},\operatorname{dec}) ( Z , enc , dec ) be
L t ≜ 1 t log ( E [ 2 t ∣ 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)} L t ≜ t 1 log ( E [ 2 t ∣ enc ( X , Z ) ∣ ] ) , (10)
and define the optimal Campbell cost over all stochastic codes as
L t ∗ ( X → Y ) ≜ inf ( Z , enc , dec ) L t . (11) L_t^*(X \to Y) \triangleq\inf_{(Z,\operatorname{enc},\operatorname{dec})} L_t. \tag*{(11)} L t ∗ ( X → Y ) ≜ ( Z , enc , dec ) inf L t . (11)
A related quantity is the minimum Arimoto-Rényi conditional entropy H α A H_\alpha^A H α A of order α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 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)} R α ∗ ( X → Y ) ≜ ( Z , enc , dec ) inf H α A ( Y ∣ Z ) . (12)
It follows from the main result of [17 ] that with α = 1 t + 1 \alpha= \frac{1}{t+1} α = t + 1 1 , these quantities are related as
R α ∗ ( X → Y ) ≤ L t ∗ ( 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)} R α ∗ ( X → Y ) ≤ L t ∗ ( X → Y ) ≤ R α ∗ ( X → Y ) + 1. (13)
Given the above, we prove the following result.
Theorem 3. Let X , Y X,Y X , Y be jointly distributed random variables over arbitrary Polish spaces and let α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) . Then,
I F , α ( X → Y ) ≤ R α ∗ ( X → Y ) ≤ I F , α ( 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)} I F , α ( X → Y ) ≤ R α ∗ ( X → Y ) ≤ I F , α ( X → Y ) + α 1 − α + 1 − α log ( 1/ α ) . (14)
As α → 1 \alpha\to1 α → 1 , the additive gap tends to log e \log e log e , recovering the constant in Theorem 1. We sharpen the channel simulation bounds of [19 ] by bounding R α ∗ ( X → Y ) R_\alpha^*(X \to Y) R α ∗ ( X → Y ) above and below in terms of the same quantity, I F , α ( X → Y ) I_{F,\alpha}(X \to Y) I F , α ( X → Y ) , with a gap depending only on α \alpha α . Fan and Wagner [20 ] independently obtained a related characterization for exact sampling with a fixed target and proposal. Our result treats the full channel simulation problem, in which a single code must simulate the conditional law P Y ∣ X ( ⋅ ∣ x ) P_{Y|X}(\mathord{\cdot}\mid x) P Y ∣ X ( ⋅ ∣ x ) for P X P_X P X -almost every x x x , with x x x known only to the encoder.
Organization
Section II introduces the channel simulation divergence and functional information and establishes their basic properties. Section III proves the one-shot lower bound in our main result and characterizes perfect functional representations. Section IV establishes the upper bound of the main result via the Poisson functional representation and derives consequences for one-shot and asymptotic channel simulation. Section V develops bounds for one-shot and finite-blocklength lossy compression using the functional rate-distortion function. Section VI extends the channel simulation bounds to Rényi functional information and the Campbell cost. The appendices contain additional proofs and rejection-sampling constructions.
Notation
We denote the binary logarithm as log \log log and the natural logarithm as ln \ln ln . For an event A A A , its indicator function is 1 [ A ] \mathbb{1}[A] 1 [ A ] . Unless otherwise stated, all random variables are assumed to take values in an arbitrary Polish space. Random variables are written in capital letters such as X X X . We write X ∼ P X X \sim P_X X ∼ P X to say that X X X has probability measure P X P_X P X , and use P X n P_X^n P X n for the joint distribution of n n n independent draws from P X P_X P X . We will occasionally write Law ( X ) \operatorname{Law}(X) Law ( X ) to refer to the distribution (law) of a random variable X X X . Random variable alphabets or spaces are denoted by calligraphic letters X ∈ X \mathcal{X} \in\mathcal{X} X ∈ X , Y ∈ Y Y \in\mathcal{Y} Y ∈ Y . We denote the expectation of X X X and the conditional expectation of X X X given Y Y Y as E [ X ] \mathbb{E}[X] E [ X ] and E [ X ∣ Y ] \mathbb{E}[X \mid Y] E [ X ∣ Y ] , respectively. We write X ⊥ Y X \perp Y X ⊥ Y to indicate that X X X and Y Y Y are independent and use i.i.d. as shorthand for independent and identically distributed. For two probability measures P P P and Q Q Q on the same measurable space, we write P ≪ Q P \ll Q P ≪ Q to indicate that P P P is absolutely continuous with respect to Q Q Q , and d P d Q \frac{\mathrm{d}P}{\mathrm{d}Q} d Q d P denotes their Radon-Nikodym derivative. For discrete distributions P P P and Q Q Q , we denote the Shannon entropy of P P P as H ( P ) H(P) H ( P ) and write H ( P ; Q ) ≜ E X ∼ P [ − log Q ( X ) ] H(P;Q) \triangleq\mathbb{E}_{X\sim P}[-\log Q(X)] H ( P ; Q ) ≜ E X ∼ P [ − log Q ( X )] for their cross-entropy. For a distribution P P P over the reals with density function f f f , we denote its differential entropy as h ( f ) h(f) h ( f ) or h ( P ) h(P) h ( P ) . For a Q Q Q -measurable function r r r , we denote its Q Q Q -essential supremum as ∥ r ∥ ∞ \lVert r\rVert_\infty ∥ r ∥ ∞ . All information measures are in bits.
Preliminaries
Channel Simulation Divergence
For two dependent random variables X , Y X, Y X , Y , the functional information of the channel X → Y X \to Y X → Y is defined as a conditional channel simulation divergence I F ( X → Y ) ≜ D C S ( P X ∣ Y ∥ P X ∣ P Y ) I_F(X \to Y) \triangleq D_{\mathrm{CS}}(P_{X|Y} \mathbin{\|} P_X \mid P_Y) I F ( X → Y ) ≜ D CS ( P X ∣ Y ∥ P X ∣ P Y ) . Thus, we begin the paper by first defining the channel simulation divergence and establishing its basic properties. Throughout this paper, we assume that X X X and Y Y Y are jointly distributed Polish space-valued random variables with finite mutual information I ( X ; Y ) < ∞ I(X;Y) < \infty I ( X ; Y ) < ∞ . This, in particular, implies that P Y ∣ X = x ≪ P Y P_{Y|X=x} \ll P_Y P Y ∣ X = x ≪ P Y for P X P_X P X -almost every (a.e.) x x x .
Definition 1 (Width function). Let P ≪ Q P \ll Q P ≪ Q be probability measures over an arbitrary Polish space. The width function w : [ 0 , ∞ ) → [ 0 , 1 ] w : [0,\infty) \to[0,1] w : [ 0 , ∞ ) → [ 0 , 1 ] of the pair ( P , Q ) (P,Q) ( P , Q ) is defined as
w ( ℓ ) ≜ Q ( d P d Q ≥ ℓ ) . (15) w(\ell) \triangleq Q\left(\frac{dP}{dQ} \ge\ell\right). \tag*{(15)} w ( ℓ ) ≜ Q ( d Q d P ≥ ℓ ) . (15)
Note that 0 ≤ w ( ℓ ) ≤ 1 0 \le w(\ell) \le1 0 ≤ w ( ℓ ) ≤ 1 and
∫ 0 ∞ w ( ℓ ) d ℓ = E X ∼ Q [ d P d Q ( X ) ] = 1. (16) \int_{0}^{\infty} w(\ell)\,d\ell= \mathbb{E}_{X \sim Q}\left[\frac{dP}{dQ}(X)\right] = 1. \tag*{(16)} ∫ 0 ∞ w ( ℓ ) d ℓ = E X ∼ Q [ d Q d P ( X ) ] = 1. (16)
Hence, w w w is a valid probability density function (PDF) over the nonnegative reals; it is illustrated in Figure 1 . Now, we make the following definitions.
Figure 1. Visualization of the width function when P = N ( 0.3 , 0.25 ) P = \mathcal{N}(0.3, 0.25) P = N ( 0.3 , 0.25 ) and Q = N ( 0 , 1 ) Q = \mathcal{N}(0, 1) Q = N ( 0 , 1 ) . Left: the density ratio d P d Q \frac{dP}{dQ} d Q d P ; the value of the width function at ℓ = 1.5 \ell= 1.5 ℓ = 1.5 is the width of the red line. Right: the width function w ( ℓ ) w(\ell) w ( ℓ ) , with the value at ℓ = 1.5 \ell= 1.5 ℓ = 1.5 also marked as in the left plot.
Definition 2 (Channel simulation divergence, conditional channel simulation divergence). Let P P P , Q Q Q and w w w be as in Definition 1. Then, the channel simulation divergence of P P P from Q Q Q is defined as the differential entropy of w w w :
D C S ( P ∥ Q ) ≜ h ( w ) = − ∫ 0 ∞ w ( ℓ ) log w ( ℓ ) d ℓ . (17) D_{\mathrm{CS}}(P \mathbin{\|} Q) \triangleq h(w) = -\int_{0}^{\infty} w(\ell) \log w(\ell)\,d\ell. \tag*{(17)} D CS ( P ∥ Q ) ≜ h ( w ) = − ∫ 0 ∞ w ( ℓ ) log w ( ℓ ) d ℓ . (17) Furthermore, for a probability measure P X P_X P X and two Markov kernels P Y ∣ X P_{Y|X} P Y ∣ X and Q Y ∣ X Q_{Y|X} Q Y ∣ X satisfying P Y ∣ X ≪ Q Y ∣ X P_{Y|X} \ll Q_{Y|X} P Y ∣ X ≪ Q Y ∣ X P X P_X P X -a.s., we first set w x ( ℓ ) ≜ Q Y ∣ X = x ( d P Y ∣ X d Q Y ∣ X ( Y ∣ x ) ≥ ℓ ) w_x(\ell) \triangleq Q_{Y|X=x}\left(\frac{dP_{Y|X}}{dQ_{Y|X}}(Y \mid x) \ge\ell\right) w x ( ℓ ) ≜ Q Y ∣ X = x ( d Q Y ∣ X d P Y ∣ X ( Y ∣ x ) ≥ ℓ ) to be the width function when X = x X=x X = x . Then, we define the conditional channel simulation divergence is defined as
D C S ( P Y ∣ X ∥ Q Y ∣ X ∣ P X ) ≜ E X ∼ P X [ h ( w X ) ] . (18) D_{\mathrm{CS}}(P_{Y|X} \mathbin{\|} Q_{Y|X} \mid P_X) \triangleq\mathbb{E}_{X \sim P_X}[h(w_X)]. \tag*{(18)} D CS ( P Y ∣ X ∥ Q Y ∣ X ∣ P X ) ≜ E X ∼ P X [ h ( w X )] . (18)
The channel simulation divergence was first defined in [21 ] , where the authors established some basic properties and used it to study channel simulation with so-called causal rejection samplers. One important property is its relation to the Kullback-Leibler (KL) divergence D K L ( ⋅ ∥ ⋅ ) D_{\mathrm{KL}}(\cdot\mathbin{\|} \cdot) D KL ( ⋅ ∥ ⋅ ) , which is summarized in the following proposition proved in [21 Lemma IV.1] .
Proposition 1 (Relation to relative entropy). Let P ≪ Q P \ll Q P ≪ Q be probability measures and let l ( x ) = x + log ( x + 1 ) + 1 l(x) = x + \log(x+1) + 1 l ( x ) = x + log ( x + 1 ) + 1 . Then,
D K L ( P ∥ Q ) ≤ D C S ( P ∥ Q ) ≤ l ( D K L ( P ∥ Q ) ) . (19) D_{\mathrm{KL}}(P \mathbin{\|} Q) \le D_{\mathrm{CS}}(P \mathbin{\|} Q) \le l\left(D_{\mathrm{KL}}(P \mathbin{\|} Q)\right). \tag*{(19)} D KL ( P ∥ Q ) ≤ D CS ( P ∥ Q ) ≤ l ( D KL ( P ∥ Q ) ) . (19)
The channel simulation divergence is also related to the recently defined layered entropy λ \lambda λ [22 ] and discrete layered entropy Λ \Lambda Λ [5 ] . For a more detailed study of the channel simulation divergence and its properties, we refer the interested reader to [7 ] . One property of the channel simulation divergence which is important to our results is that it is convex in its first variable [21 Lemma IV.1] ; a full proof is provided in Appendix A.
Proposition 2. For a fixed Q Q Q , the map P ↦ D C S ( P ∥ Q ) P \mapsto D_{\mathrm{CS}}(P \mathbin{\|} Q) P ↦ D CS ( P ∥ Q ) is convex.
Definition 3 (Functional Information). Let X , Y ∼ P X , Y X,Y \sim P_{X,Y} X , Y ∼ P X , Y be random variables. Then, the functional information of the channel X → Y X \to Y X → Y is defined as
I F ( X → Y ) ≜ D C S ( P X ∣ Y ∥ P X ∣ P Y ) = E Y [ h ( w Y ) ] , (20) I_F(X \to Y) \triangleq D_{\mathrm{CS}}(P_{X|Y}\|P_X\mid P_Y)=\mathbb{E}_Y[h(w_Y)], \tag*{(20)} I F ( X → Y ) ≜ D CS ( P X ∣ Y ∥ P X ∣ P Y ) = E Y [ h ( w Y )] , (20) where w y ( ℓ ) = P X ( d P Y ∣ X d P Y ( y ∣ X ) ≥ ℓ ) w_y(\ell)=P_X\left(\frac{dP_{Y|X}}{dP_Y}(y\mid X)\ge\ell\right) w y ( ℓ ) = P X ( d P Y d P Y ∣ X ( y ∣ X ) ≥ ℓ ) . More explicitly,
I F ( X → Y ) = − ∫ Y ∫ 0 ∞ w y ( ℓ ) log w y ( ℓ ) d ℓ d P Y ( y ) . I_F(X \to Y)=-\int_{\mathcal{Y}}\int_0^\infty w_y(\ell)\log w_y(\ell)\,d\ell\,dP_Y(y). I F ( X → Y ) = − ∫ Y ∫ 0 ∞ w y ( ℓ ) log w y ( ℓ ) d ℓ d P Y ( y ) .
As suggested by the arrow notation, unlike the mutual information, the functional information is not generally symmetric in X X X and Y Y Y . However, just as the channel simulation divergence is close to the KL divergence, I F ( X → Y ) I_F(X \to Y) I F ( X → Y ) is always “close” to the mutual information, with equality if and only if the channel X → Y X \to Y X → Y is singular [11 ] .
Definition 4 (Singular channel [13 ] ). Let X , Y ∼ P X , Y X,Y\sim P_{X,Y} X , Y ∼ P X , Y . We call the channel X → Y X\to Y X → Y singular if there exists a P Y P_Y P Y -measurable function g ( y ) g(y) g ( y ) such that
d P Y ∣ X d P Y ( y ∣ x ) = g ( y ) P X , Y -a.s. ; (21) \frac{dP_{Y|X}}{dP_Y}(y\mid x)=g(y)\quad P_{X,Y}\text{-a.s.}; \tag*{(21)} d P Y d P Y ∣ X ( y ∣ x ) = g ( y ) P X , Y -a.s. ; (21) otherwise, we call the channel X → Y X\to Y X → Y nonsingular.
Singular channels (such as the binary erasure channel and the uniform dither channel) have been shown to admit relative entropy codes with sub-logarithmic asymptotic redundancy [8 , 13 ] . The following proposition shows that this is not an accident. Indeed, we will obtain a significantly stronger statement: constant redundancy over the mutual information is possible for all singular channels (see Corollary 2).
Proposition 3 (Relation to the mutual information). Let X , Y ∼ P X , Y X,Y\sim P_{X,Y} X , Y ∼ P X , Y . Then we have
I ( X ; Y ) ≤ I F ( X → Y ) ≤ I ( X ; Y ) + log ( I ( X ; Y ) + 1 ) + 1. I(X;Y)\le I_F(X\to Y)\le I(X;Y)+\log(I(X;Y)+1)+1. I ( X ; Y ) ≤ I F ( X → Y ) ≤ I ( X ; Y ) + log ( I ( X ; Y ) + 1 ) + 1. Furthermore, the lower bound is achieved if and only if the channel X → Y X\to Y X → Y is singular.
Proof. See Appendix A.
It is a simple corollary of Proposition 3 that in the special case where X X X is discrete and X → Y X\to Y X → Y is the trivial channel Y = X Y=X Y = X , we have I F ( X → Y ) = H ( X ) I_F(X\to Y)=H(X) I F ( X → Y ) = H ( X ) . In addition to Proposition 3, I F ( X → Y ) I_F(X\to Y) I F ( X → Y ) and I ( X ; Y ) I(X;Y) I ( X ; Y ) also share some deeper properties. For example, the functional information satisfies a data processing inequality and analogous convexity/concavity properties, the proofs of which can be found in Appendix A.
Proposition 4 (Data processing inequality). Let X → Y → Z X\to Y\to Z X → Y → Z be a Markov chain. Then,
I F ( X → Y ) ≥ I F ( X → Z ) . (22) I_F(X\to Y)\ge I_F(X\to Z). \tag*{(22)} I F ( X → Y ) ≥ I F ( X → Z ) . (22)
Proposition 5 (Convexity/Concavity). Consider the joint distribution P X , Y P_{X,Y} P X , Y over X × Y \mathcal{X}\times\mathcal{Y} X × Y . Then:
For fixed P Y ∣ X P_{Y|X} P Y ∣ X , the map P X ↦ I F ( X → Y ) P_X\mapsto I_F(X\to Y) P X ↦ I F ( X → Y ) is concave.
For fixed P X P_X P X , the map P Y ∣ X ↦ I F ( X → Y ) P_{Y|X}\mapsto I_F(X\to Y) P Y ∣ X ↦ I F ( X → Y ) is convex.
One-Shot Rate Lower Bound and Perfect Functional Representations
In this section, we give a new and simpler proof of the lower bound I F ( X → Y ) ≤ R ∗ ( X → Y ) I_F(X\to Y)\le R^*(X\to Y) I F ( X → Y ) ≤ R ∗ ( X → Y ) first shown in [8 ] . A primary advantage of this proof is that there is only one inequality, permitting relatively simple analysis of the equality condition. For P X , Y P_{X,Y} P X , Y with finite X , Y \mathcal{X},\mathcal{Y} X , Y , we give necessary and sufficient conditions on the distribution for equality to be possible, generalizing the results of [9 ] .
Definition 5 (Functional Representation). Given a Polish space Z \mathcal{Z} Z , let Z ⊥ X Z\perp X Z ⊥ X be a Z \mathcal{Z} Z -valued random variable and let f : X × Z → Y f:\mathcal{X}\times\mathcal{Z}\to\mathcal{Y} f : X × Z → Y be measurable, with Y = f ( X , Z ) Y=f(X,Z) Y = f ( X , Z ) and P Y ∣ Z = z P_{Y|Z=z} P Y ∣ Z = z purely atomic for P Z P_Z P Z -a.e. z z z . The pair ( Z , f ) (Z,f) ( Z , f ) is called a functional representation for P X , Y P_{X,Y} P X , Y .
Note that for any pair of Polish space-valued random variables X , Y X,Y X , Y , a functional representation ( Z , f ) (Z,f) ( Z , f ) as just defined always exists; for example, we may choose the Poisson functional representation [4 ] or the greedy Poisson rejection sampler [23 ] . Also, any stochastic code, defined in the introduction, gives rise to a functional representation by letting f ( X , Z ) = dec ( enc ( X , Z ) , Z ) f(X,Z)=\operatorname{dec}(\operatorname{enc}(X,Z),Z) f ( X , Z ) = dec ( enc ( X , Z ) , Z ) , and any functional representation can be converted to a stochastic code by applying, conditioned on Z = z Z=z Z = z , a uniquely decodable code to the (conditionally) discrete output Y = f ( X , Z ) Y=f(X,Z) Y = f ( X , Z ) .
Theorem 4 (Functional Information Lower Bound). Let X , Y ∼ P X , Y X, Y \sim P_{X,Y} X , Y ∼ P X , Y be random variables with I ( X ; Y ) < ∞ I(X;Y) < \infty I ( X ; Y ) < ∞ . Let Z ⊥ X Z \perp X Z ⊥ X be such that Y = f ( X , Z ) Y = f(X,Z) Y = f ( X , Z ) for some measurable f : X × Z → Y f : \mathcal{X} \times\mathcal{Z} \to\mathcal{Y} f : X × Z → Y and P Y ∣ Z = z P_{Y|Z=z} P Y ∣ Z = z is purely atomic for P Z P_Z P Z -a.e. z z z . Then,
I F ( X → Y ) ≤ R ∗ ( X → Y ) . (23) I_F(X \to Y) \le R^*(X \to Y). \tag*{(23)} I F ( X → Y ) ≤ R ∗ ( X → Y ) . (23)
Proof. Let Z ⊥ X Z \perp X Z ⊥ X be any random variable admitting a functional representation Y = f ( X , Z ) Y = f(X,Z) Y = f ( X , Z ) for some measurable f f f such that P Y ∣ Z = z P_{Y|Z=z} P Y ∣ Z = z is purely atomic for P Z P_Z P Z -a.e. z z z . To prove (23) , it is sufficient to prove that I F ( X → Y ) ≤ H ( Y ∣ Z ) I_F(X \to Y) \le H(Y \mid Z) I F ( X → Y ) ≤ H ( Y ∣ Z ) .
For a fixed y ∈ Y y \in\mathcal{Y} y ∈ Y , define
q y ( z ) ≜ P Y ∣ Z = z ( y ) = ∫ X 1 [ f ( x , z ) = y ] d P X ( x ) . q_y(z) \triangleq P_{Y|Z=z}(y) = \int_{\mathcal{X}} \mathbf{1}[f(x,z)=y]\,dP_X(x). q y ( z ) ≜ P Y ∣ Z = z ( y ) = ∫ X 1 [ f ( x , z ) = y ] d P X ( x ) .
Let ν y \nu_y ν y be a regular conditional distribution of Z Z Z given Y = y Y=y Y = y . Note that P Y ∣ Z = z ( { y : q y ( z ) > 0 } ) = 1 P_{Y|Z=z}(\{y:q_y(z)>0\})=1 P Y ∣ Z = z ({ y : q y ( z ) > 0 }) = 1 for P Z P_Z P Z -a.e. z z z implies P ( q Y ( Z ) > 0 ∣ Z = z ) = 1 P(q_Y(Z)>0 \mid Z=z)=1 P ( q Y ( Z ) > 0 ∣ Z = z ) = 1 and hence P ( q Y ( Z ) > 0 ) = 1 P(q_Y(Z)>0)=1 P ( q Y ( Z ) > 0 ) = 1 . Hence, P ( q Y ( Z ) > 0 ∣ Y = y ) = 1 P(q_Y(Z)>0 \mid Y=y)=1 P ( q Y ( Z ) > 0 ∣ Y = y ) = 1 for P Y P_Y P Y -a.e. y y y . Thus, we can choose versions of ν y \nu_y ν y so that, for P Y P_Y P Y -a.e. y y y , q y ( z ) > 0 q_y(z)>0 q y ( z ) > 0 for ν y \nu_y ν y -a.e. z z z . The conditional entropy is therefore
H ( Y ∣ Z ) ⋅ ln 2 = E [ − ln q Y ( Z ) ] = ∫ Y ∫ Z − ln q y ( z ) d ν y ( z ) d P Y ( y ) . (24) H(Y \mid Z)\cdot\ln2 = \mathbb{E}[-\ln q_Y(Z)]
= \int_{\mathcal{Y}}\int_{\mathcal{Z}}-\ln q_y(z)\,d\nu_y(z)\,dP_Y(y). \tag*{(24)} H ( Y ∣ Z ) ⋅ ln 2 = E [ − ln q Y ( Z )] = ∫ Y ∫ Z − ln q y ( z ) d ν y ( z ) d P Y ( y ) . (24)
To prove I F ( X → Y ) ≤ H ( Y ∣ Z ) I_F(X \to Y) \le H(Y \mid Z) I F ( X → Y ) ≤ H ( Y ∣ Z ) , it suffices to prove for P Y P_Y P Y -a.e. y y y that
D C S ( P X ∣ Y = y ∥ P X ) ⋅ ln 2 ≤ ∫ Z − ln q y ( z ) d ν y ( z ) . (25) D_{\mathrm{CS}}(P_{X|Y=y}\mathbin\Vert P_X)\cdot\ln2 \le\int_{\mathcal{Z}}-\ln q_y(z)\,d\nu_y(z). \tag*{(25)} D CS ( P X ∣ Y = y ∥ P X ) ⋅ ln 2 ≤ ∫ Z − ln q y ( z ) d ν y ( z ) . (25)
We will achieve this using the representation
D C S ( P X ∣ Y = y ∥ P X ) ⋅ ln 2 = − 1 + ∫ 0 1 1 p ∫ 0 p w y − 1 ( u ) d u d p (26) D_{\mathrm{CS}}(P_{X|Y=y}\mathbin\Vert P_X)\cdot\ln2 = -1+\int_0^1\frac{1}{p}\int_0^p w_y^{-1}(u)\,du\,dp \tag*{(26)} D CS ( P X ∣ Y = y ∥ P X ) ⋅ ln 2 = − 1 + ∫ 0 1 p 1 ∫ 0 p w y − 1 ( u ) d u d p (26)
of [7 Lem. 3.1.2] , where
w y − 1 ( u ) ≜ sup { ℓ ≥ 0 : w y ( ℓ ) ≥ u } (27) w_y^{-1}(u)\triangleq\sup\{\ell\ge0:w_y(\ell)\ge u\} \tag*{(27)} w y − 1 ( u ) ≜ sup { ℓ ≥ 0 : w y ( ℓ ) ≥ u } (27)
is the generalized inverse of the width function w y w_y w y .
To begin, fix y y y and write
r ( y ∣ x ) = d P Y ∣ X d P Y ( y ∣ x ) . (28) r(y\mid x)=\frac{dP_{Y|X}}{dP_Y}(y\mid x). \tag*{(28)} r ( y ∣ x ) = d P Y d P Y ∣ X ( y ∣ x ) . (28)
Note that r ( y ∣ x ) = d P X ∣ Y = y d P X ( x ) r(y\mid x)=\frac{dP_{X|Y=y}}{dP_X}(x) r ( y ∣ x ) = d P X d P X ∣ Y = y ( x ) for P Y P_Y P Y -a.e. y y y , P X P_X P X -a.e. x x x since I ( X ; Y ) < ∞ I(X;Y)<\infty I ( X ; Y ) < ∞ implies P X , Y ≪ P X ⊗ P Y P_{X,Y}\ll P_X\otimes P_Y P X , Y ≪ P X ⊗ P Y .
For every measurable A ⊆ X A\subseteq\mathcal{X} A ⊆ X ,
P X ∣ Y = y ( A ) = ∫ Z P ( X ∈ A ∣ Y = y , Z = z ) d ν y ( z ) = ∫ Z ∫ A 1 [ f ( x , z ) = y ] d P X ( x ) q y ( z ) d ν y ( z ) , P_{X|Y=y}(A)=\int_{\mathcal{Z}}P(X\in A\mid Y=y,Z=z)\,d\nu_y(z)
=\int_{\mathcal{Z}}\frac{\int_A\mathbf{1}[f(x,z)=y]\,dP_X(x)}{q_y(z)}\,d\nu_y(z), P X ∣ Y = y ( A ) = ∫ Z P ( X ∈ A ∣ Y = y , Z = z ) d ν y ( z ) = ∫ Z q y ( z ) ∫ A 1 [ f ( x , z ) = y ] d P X ( x ) d ν y ( z ) ,
where the second equality uses the independence of Z Z Z and X X X and the fact that, given Z = z Z=z Z = z , the event { Y = y } \{Y=y\} { Y = y } is { f ( X , z ) = y } \{f(X,z)=y\} { f ( X , z ) = y } . Thus,
r ( y ∣ x ) = ∫ Z 1 [ f ( x , z ) = y ] q y ( z ) d ν y ( z ) P X -a.s. r(y\mid x)=\int_{\mathcal{Z}}\frac{\mathbf{1}[f(x,z)=y]}{q_y(z)}\,d\nu_y(z)\quad P_X\text{-a.s.} r ( y ∣ x ) = ∫ Z q y ( z ) 1 [ f ( x , z ) = y ] d ν y ( z ) P X -a.s.
Fix p ∈ [ 0 , 1 ] p\in[0,1] p ∈ [ 0 , 1 ] and consider any measurable b y : X → [ 0 , 1 ] b_y:\mathcal{X}\to[0,1] b y : X → [ 0 , 1 ] with P X ( b y ) = p P_X(b_y)=p P X ( b y ) = p , where we used the convention P ( g ) = ∫ g d P P(g)=\int g\,dP P ( g ) = ∫ g d P . Then,
P X ∣ Y = y ( b y ) = ∫ X b y ( x ) r ( y ∣ x ) d P X ( x ) = ∫ Z ∫ X b y ( x ) 1 [ f ( x , z ) = y ] d P X ( x ) q y ( z ) d ν y ( z ) ≤ ∫ Z min { p , q y ( z ) } q y ( z ) d ν y ( z ) , (29) P_{X|Y=y}(b_y)=\int_{\mathcal{X}}b_y(x)r(y\mid x)\,dP_X(x)
=\int_{\mathcal{Z}}\frac{\int_{\mathcal{X}}b_y(x)\mathbf{1}[f(x,z)=y]\,dP_X(x)}{q_y(z)}\,d\nu_y(z)
\le\int_{\mathcal{Z}}\frac{\min\{p,q_y(z)\}}{q_y(z)}\,d\nu_y(z), \tag*{(29)} P X ∣ Y = y ( b y ) = ∫ X b y ( x ) r ( y ∣ x ) d P X ( x ) = ∫ Z q y ( z ) ∫ X b y ( x ) 1 [ f ( x , z ) = y ] d P X ( x ) d ν y ( z ) ≤ ∫ Z q y ( z ) min { p , q y ( z )} d ν y ( z ) , (29)
where the inequality follows because
∫ X b y ( x ) 1 [ f ( x , z ) = y ] d P X ( x ) ≤ ∫ X b y ( x ) d P X ( x ) = p \int_{\mathcal{X}}b_y(x)\mathbf{1}[f(x,z)=y]\,dP_X(x)\le\int_{\mathcal{X}}b_y(x)\,dP_X(x)=p ∫ X b y ( x ) 1 [ f ( x , z ) = y ] d P X ( x ) ≤ ∫ X b y ( x ) d P X ( x ) = p
and
∫ X b y ( x ) 1 [ f ( x , z ) = y ] d P X ( x ) ≤ ∫ X 1 [ f ( x , z ) = y ] d P X ( x ) = q y ( z ) . \int_{\mathcal{X}}b_y(x)\mathbf{1}[f(x,z)=y]\,dP_X(x)\le\int_{\mathcal{X}}\mathbf{1}[f(x,z)=y]\,dP_X(x)=q_y(z). ∫ X b y ( x ) 1 [ f ( x , z ) = y ] d P X ( x ) ≤ ∫ X 1 [ f ( x , z ) = y ] d P X ( x ) = q y ( z ) .
Next, we note that
sup 0 ≤ b y ≤ 1 P X ( b y ) = p ∫ X b y r ( y ∣ x ) d P X ( x ) = ∫ 0 p w y − 1 ( u ) d u . (30) \sup_{\substack{0\le b_y\le1\\ P_X(b_y)=p}} \int_{\mathcal{X}} b_y r(y\mid x)\,dP_X(x)=\int_0^p w_y^{-1}(u)\,du. \tag*{(30)} 0 ≤ b y ≤ 1 P X ( b y ) = p sup ∫ X b y r ( y ∣ x ) d P X ( x ) = ∫ 0 p w y − 1 ( u ) d u . (30)
This representation is a standard result; see, e.g., [24 Theorem 1.14] . We provide a proof along with the structure of the maximizing b y b_y b y in Appendix A (Lemma 2) for completeness. With this representation, taking the supremum over all admissible b y b_y b y in (29) gives
∫ 0 p w y − 1 ( u ) d u ≤ ∫ Z min { p , q y ( z ) } q y ( z ) d ν y ( z ) . (31) \int_0^p w_y^{-1}(u)\,du\le\int_{\mathcal{Z}}\frac{\min\{p,q_y(z)\}}{q_y(z)}\,d\nu_y(z). \tag*{(31)} ∫ 0 p w y − 1 ( u ) d u ≤ ∫ Z q y ( z ) min { p , q y ( z )} d ν y ( z ) . (31)
We can multiply by 1 / p 1/p 1/ p and integrate to obtain
∫ 0 1 1 p ∫ 0 p w y − 1 ( u ) d u d p ≤ ∫ 0 1 1 p ∫ Z min { p , q y ( z ) } q y ( z ) d ν y ( z ) d p = ∫ Z ∫ 0 1 min { p , q y ( z ) } p q y ( z ) d p d ν y ( z ) = 1 + ∫ Z − ln q y ( z ) d ν y ( z ) , \begin{aligned}
\int_0^1\frac{1}{p}\int_0^p w_y^{-1}(u)\,du\,dp\le\int_0^1\frac{1}{p}\int_{\mathcal{Z}}\frac{\min\{p,q_y(z)\}}{q_y(z)}\,d\nu_y(z)\,dp \\
&=\int_{\mathcal{Z}}\int_0^1\frac{\min\{p,q_y(z)\}}{p q_y(z)}\,dp\,d\nu_y(z) \\
&=1+\int_{\mathcal{Z}}-\ln q_y(z)\,d\nu_y(z),
\end{aligned} ∫ 0 1 p 1 ∫ 0 p w y − 1 ( u ) d u d p ≤ ∫ 0 1 p 1 ∫ Z q y ( z ) min { p , q y ( z )} d ν y ( z ) d p = ∫ Z ∫ 0 1 p q y ( z ) min { p , q y ( z )} d p d ν y ( z ) = 1 + ∫ Z − ln q y ( z ) d ν y ( z ) ,
where the first equality follows from Tonelli’s theorem and the final equality follows from the computation
∫ 0 1 min { p , q } p q d p = ∫ 0 q p p q d p + ∫ q 1 q p q d p = 1 − ln q . \begin{aligned}
\int_0^1\frac{\min\{p,q\}}{pq}\,dp=\int_0^q\frac{p}{pq}\,dp+\int_q^1\frac{q}{pq}\,dp \\
&=1-\ln q.
\end{aligned} ∫ 0 1 pq min { p , q } d p = ∫ 0 q pq p d p + ∫ q 1 pq q d p = 1 − ln q .
Substituting in (26) gives that
D C S ( P X ∣ Y = y ∥ P X ) ⋅ ln 2 ≤ − 1 + ( 1 − ∫ Z ln q y ( z ) d ν y ( z ) ) = ∫ Z − ln q y ( z ) d ν y ( z ) . \begin{aligned}
D_{\mathrm{CS}}(P_{X\mid Y=y}\mathbin\Vert P_X)\cdot\ln2\le-1+\left(1-\int_{\mathcal{Z}}\ln q_y(z)\,d\nu_y(z)\right) \\
&=\int_{\mathcal{Z}}-\ln q_y(z)\,d\nu_y(z).
\end{aligned} D CS ( P X ∣ Y = y ∥ P X ) ⋅ ln 2 ≤ − 1 + ( 1 − ∫ Z ln q y ( z ) d ν y ( z ) ) = ∫ Z − ln q y ( z ) d ν y ( z ) .
In view of the definition of I F ( X → Y ) I_F(X\to Y) I F ( X → Y ) and (24), the result follows after integrating over Y \mathcal{Y} Y with respect to d P Y ( y ) dP_Y(y) d P Y ( y ) .
One can observe that the only inequality in the proof of Theorem 4 is (29). Therefore, if equality holds in (31) for a.e. p ∈ ( 0 , 1 ) p\in(0,1) p ∈ ( 0 , 1 ) and for P Y P_Y P Y -a.e. y y y , we have I F ( X → Y ) = H ( Y ∣ Z ) I_F(X\to Y)=H(Y\mid Z) I F ( X → Y ) = H ( Y ∣ Z ) , which we call a perfect functional representation (see also [9 ] for a slightly different definition; see our Remark 1 below).
Definition 6 (Perfect Functional Representation). For X , Y ∼ P X , Y X,Y\sim P_{X,Y} X , Y ∼ P X , Y , we call a functional representation ( Z , f ) (Z,f) ( Z , f ) perfect if H ( Y ∣ Z ) = I F ( X → Y ) H(Y\mid Z)=I_F(X\to Y) H ( Y ∣ Z ) = I F ( X → Y ) .
When X , Y \mathcal{X},\mathcal{Y} X , Y are finite, one can obtain necessary and sufficient conditions on P X , Y P_{X,Y} P X , Y for a perfect functional representation to exist. Suppose that X \mathcal{X} X and Y \mathcal{Y} Y are finite with ∣ X ∣ = n |\mathcal{X}|=n ∣ X ∣ = n and ∣ Y ∣ = m |\mathcal{Y}|=m ∣ Y ∣ = m . Assume without loss of generality that P X ( x ) > 0 P_X(x)>0 P X ( x ) > 0 and P Y ( y ) > 0 P_Y(y)>0 P Y ( y ) > 0 for all x ∈ X x\in\mathcal{X} x ∈ X and y ∈ Y y\in\mathcal{Y} y ∈ Y . To ease the notation, we write P Y ∣ X ( y ∣ x ) P_{Y\mid X}(y\mid x) P Y ∣ X ( y ∣ x ) for P Y ∣ X ( { y } ∣ x ) P_{Y\mid X}(\{y\}\mid x) P Y ∣ X ({ y } ∣ x ) .
Definition 7 (Compatible ordering, admissible maps). We call an ordering x y , 1 , x y , 2 , … , x y , n x_{y,1},x_{y,2},\ldots,x_{y,n} x y , 1 , x y , 2 , … , x y , n of X \mathcal{X} X y y y -compatible if
P Y ∣ X ( y ∣ x y , i ) ≥ P Y ∣ X ( y ∣ x y , j ) P_{Y\mid X}(y\mid x_{y,i})\ge P_{Y\mid X}(y\mid x_{y,j}) P Y ∣ X ( y ∣ x y , i ) ≥ P Y ∣ X ( y ∣ x y , j ) for all i < j i<j i < j . Given y y y -compatible orderings, one for each y ∈ Y y\in\mathcal{Y} y ∈ Y , we call a map φ : X → Y \varphi:\mathcal{X}\to\mathcal{Y} φ : X → Y admissible if, for every y ∈ Y y\in\mathcal{Y} y ∈ Y , the preimage φ − 1 ( y ) \varphi^{-1}(y) φ − 1 ( y ) satisfies
φ − 1 ( y ) = { x y , 1 , … , x y , k y } \varphi^{-1}(y)=\{x_{y,1},\ldots,x_{y,k_y}\} φ − 1 ( y ) = { x y , 1 , … , x y , k y } for some k y ∈ { 0 , 1 , … , n } k_y\in\{0,1,\ldots,n\} k y ∈ { 0 , 1 , … , n } , with the convention that the set is empty if k y = 0 k_y=0 k y = 0 . Equivalently, φ \varphi φ is admissible if each output cell { x : φ ( x ) = y } \{x:\varphi(x)=y\} { x : φ ( x ) = y } is an initial segment of the fixed ordering compatible with y y y .
To any admissible φ \varphi φ uniquely corresponds a binary (deterministic) n × m n\times m n × m channel transition matrix M φ = { M φ ( x , y ) } M_\varphi=\{M_\varphi(x,y)\} M φ = { M φ ( x , y )} such that M φ ( x , y ) = 1 M_\varphi(x,y)=1 M φ ( x , y ) = 1 if and only if φ ( x ) = y \varphi(x)=y φ ( x ) = y . We call such a binary matrix admissible for the given ordering.
Proposition 6 (Finite-Alphabet Perfect Representation). Assume that X \mathcal{X} X and Y \mathcal{Y} Y are finite. There exists a perfect functional representation if and only if there exist y y y -compatible orderings of X \mathcal{X} X , one for each y ∈ Y y\in\mathcal{Y} y ∈ Y , and a probability mass function α \alpha α on the set of admissible maps φ : X → Y \varphi:\mathcal{X}\to\mathcal{Y} φ : X → Y for these orderings, such that
P Y ∣ X ( y ∣ x ) = ∑ φ : φ ( x ) = y α ( φ ) (32) P_{Y\mid X}(y\mid x)=\sum_{\varphi:\varphi(x)=y}\alpha(\varphi) \tag*{(32)} P Y ∣ X ( y ∣ x ) = φ : φ ( x ) = y ∑ α ( φ ) (32)
for every x ∈ X x \in\mathcal{X} x ∈ X , y ∈ Y y \in\mathcal{Y} y ∈ Y . Equivalently, the channel matrix P Y ∣ X P_{Y|X} P Y ∣ X lies in the convex hull of the deterministic channel matrices associated with the maps admissible for some fixed choice of compatible orderings.
Proof. The proof can be found in Appendix B.
Remark 1. In [9 ] , the authors call a functional representation perfect if H ( Y ∣ Z ) = I ( X ; Y ) H(Y \mid Z) = I(X;Y) H ( Y ∣ Z ) = I ( X ; Y ) . For discrete and singular P X , Y P_{X,Y} P X , Y , they give a necessary and sufficient condition in terms of four matrix operations for a perfect functional representation to exist. They also cast the problem of checking perfect representability as a linear program. Their linear program follows from our more general convex hull condition, after applying the additional constraint that I F ( X → Y ) = I ( X ; Y ) I_{\mathrm{F}}(X \to Y) = I(X;Y) I F ( X → Y ) = I ( X ; Y ) , i.e., that the channel X → Y X \to Y X → Y is singular.
The conditions of Proposition 6 can be used to show that every binary-output channel admits a perfect representation, as was first shown in [4 Proposition 1] and achieved by the Poisson functional representation.
Proposition 7 (Binary-Output Perfect Functional Representation). Assume Y = { 0 , 1 } \mathcal{Y} = \{0,1\} Y = { 0 , 1 } and let Z ∼ Unif ( 0 , 1 ) Z \sim\operatorname{Unif}(0,1) Z ∼ Unif ( 0 , 1 ) be independent of X X X . Let f : X × Z → Y f:\mathcal{X} \times\mathcal{Z} \to\mathcal{Y} f : X × Z → Y be given by f ( x , z ) = 1 [ P Y ∣ X ( 1 ∣ x ) ≥ z ] f(x,z) = \mathbf{1}\left[P_{Y|X}(1 \mid x) \ge z\right] f ( x , z ) = 1 [ P Y ∣ X ( 1 ∣ x ) ≥ z ] . Then Y = f ( X , Z ) Y = f(X,Z) Y = f ( X , Z ) satisfies ( X , Y ) ∼ P X , Y (X,Y) \sim P_{X,Y} ( X , Y ) ∼ P X , Y and H ( Y ∣ Z ) = I F ( X → Y ) H(Y \mid Z) = I_{\mathrm{F}}(X \to Y) H ( Y ∣ Z ) = I F ( X → Y ) .
Proof. The proofs of correctness and optimality, both of which follow by computation, are deferred to Appendix B.
Remark 2. For the representation in Proposition 7, the conditional distribution of Y Y Y given Z = z Z=z Z = z is determined by
P Y ∣ Z ( 1 ∣ z ) = P X ( P Y ∣ X ( 1 ∣ X ) ≥ z ) = w 1 ( z P Y ( 1 ) ) . P_{Y|Z}(1 \mid z) = P_X\left(P_{Y|X}(1 \mid X) \ge z\right) = w_1\left(\frac{z}{P_Y(1)}\right). P Y ∣ Z ( 1 ∣ z ) = P X ( P Y ∣ X ( 1 ∣ X ) ≥ z ) = w 1 ( P Y ( 1 ) z ) . One can show that Huffman coding for this distribution minimizes the expected code length among all stochastic codes, with the convention that no bits are sent when Z Z Z determines Y Y Y .
The conditions in Proposition 6 are relatively restrictive, and are not satisfied by every channel. Below, we give an example of a discrete channel for which no perfect functional representation exists; the proof is in Appendix B.
Proposition 8. Let X = Y = { 1 , 2 , 3 } \mathcal{X} = \mathcal{Y} = \{1,2,3\} X = Y = { 1 , 2 , 3 } and define
P Y ∣ X = [ 1 − ϵ 0 ϵ ϵ 1 − ϵ 0 0 ϵ 1 − ϵ ] . P_{Y|X} =
\begin{bmatrix}
1-\epsilon& 0 & \epsilon\\
\epsilon& 1-\epsilon& 0 \\
0 & \epsilon& 1-\epsilon
\end{bmatrix}. P Y ∣ X = 1 − ϵ ϵ 0 0 1 − ϵ ϵ ϵ 0 1 − ϵ . where 1 / 3 < ϵ < 1 / 2 1/3 < \epsilon< 1/2 1/3 < ϵ < 1/2 . Then, there does not exist a perfect functional representation for this channel.
One-Shot Rate Upper Bound via Poisson Functional Representation
Having seen that perfect functional representations are not always possible, a natural question is whether there is a general algorithm that achieves a cost within a constant of the functional information lower bound. In this section, we answer this question in the positive by constructing an explicit code using the Poisson functional representation.
In Appendix § 12 , we also present a generalization of our previous rejection sampling-based code in [11 ] , called the generalized ring toss code. This code is of independent interest, as it turns out that rejection sampling is optimal (within a constant gap) under any admissible dominating distribution of the proposed samples in the common randomness, and that the choice which minimizes the runtime is a Shtarkov distribution [25 ] .
Poisson Functional Representation
In [11 ] , we constructed a rejection-sampling based code, called the ring toss code, that achieves a cost within a constant of the functional information lower bound. A limitation of this rejection sampling algorithm is that it requires a uniformly bounded density ratio d P Y ∣ X d P Y \frac{dP_{Y|X}}{dP_Y} d P Y d P Y ∣ X . Although our extension to an arbitrary proposal distribution relaxes this requirement to the channel having a finite Shtarkov integral (see Appendix § 12 ), this still excludes many channels of practical interest such as the additive white Gaussian noise channel.
In pursuit of removing this restriction, we study how to apply the insights of the ring toss code to the Poisson functional representation, which is a sampling algorithm for general channels [4 ] . In particular, we look to make use of the common randomness to design a better coding distribution for the minimizing sample index K K K than the Zipf distribution used to establish the fundamental upper bound in [1 ] . For random variables X , Y ∼ P X , Y X,Y \sim P_{X,Y} X , Y ∼ P X , Y , recall the Radon-Nikodym derivative r ( y ∣ x ) = d P Y ∣ X d P Y ( y ∣ x ) r(y \mid x) = \frac{dP_{Y|X}}{dP_Y}(y \mid x) r ( y ∣ x ) = d P Y d P Y ∣ X ( y ∣ x ) . The Poisson functional representation sets the common randomness Z = { ( Y i , T i ) } i ≥ 1 Z = \{(Y_i,T_i)\}_{i \ge1} Z = {( Y i , T i ) } i ≥ 1 to be a Poisson point process with intensity measure P Y ⊗ λ P_Y \otimes\lambda P Y ⊗ λ ; i.e., Y i ∼ i . i . d . P Y Y_i \overset{\mathrm{i.i.d.}}{\sim} P_Y Y i ∼ i.i.d. P Y and { T i } i ≥ 1 \{T_i\}_{i \ge1} { T i } i ≥ 1 is a rate-one Poisson process. On input X = x X=x X = x , it returns the index K K K given by
K = arg min i ≥ 1 T i r ( Y i ∣ x ) . (33) K = \underset{i \ge1}{\arg\min}\ \frac{T_i}{r(Y_i \mid x)}. \tag*{(33)} K = i ≥ 1 arg min r ( Y i ∣ x ) T i . (33)
Equivalently, the Poisson functional representation returns the index of the first arrival time of the transformed Poisson process { T i / r ( Y i ∣ x ) } i ≥ 1 \{T_i/r(Y_i \mid x)\}_{i\geq1} { T i / r ( Y i ∣ x ) } i ≥ 1 . It follows from the theory of Poisson processes that P Y K ∣ X = x = P Y ∣ X = x P_{Y_K\mid X=x}=P_{Y\mid X=x} P Y K ∣ X = x = P Y ∣ X = x for P X P_X P X -a.e. x x x . Moreover, [4 ] showed that
H ( K ) < I ( X ; Y ) + log ( I ( X ; Y ) + 1 ) + 4. (34) H(K)<I(X;Y)+\log(I(X;Y)+1)+4. \tag*{(34)} H ( K ) < I ( X ; Y ) + log ( I ( X ; Y ) + 1 ) + 4. (34)
The main result of this paper is that the Poisson functional representation is an optimal stochastic code within a constant gap. Additionally, like rejection sampling, the Poisson functional representation is also constant-gap optimal using any dominating proposal distribution { Y i } i ≥ 1 ∼ i . i . d . Q Y \{Y_i\}_{i\geq1}\overset{\mathrm{i.i.d.}}{\sim} Q_Y { Y i } i ≥ 1 ∼ i.i.d. Q Y , not just the marginal P Y P_Y P Y .
Theorem 5. Let X , Y ∼ P X , Y X,Y\sim P_{X,Y} X , Y ∼ P X , Y be random variables with I ( X ; Y ) < ∞ I(X;Y)<\infty I ( X ; Y ) < ∞ . Let Z = { ( Y i , T i ) } Z=\{(Y_i,T_i)\} Z = {( Y i , T i )} be a Poisson point process independent of X X X with mean measure Q Y ⊗ λ Q_Y\otimes\lambda Q Y ⊗ λ , where P Y ∣ X = x ≪ Q Y P_{Y\mid X=x}\ll Q_Y P Y ∣ X = x ≪ Q Y for P X P_X P X -a.e. x x x . Define r Q ( y ∣ x ) ≜ r ( y ∣ x ) d P Y d Q Y ( y ) r_Q(y\mid x)\triangleq r(y\mid x)\frac{dP_Y}{dQ_Y}(y) r Q ( y ∣ x ) ≜ r ( y ∣ x ) d Q Y d P Y ( y ) (with value zero where the latter derivative vanishes) and, for input X = x X=x X = x , define
K ≜ arg min i ≥ 1 T i r Q ( Y i ∣ x ) , t / 0 ≜ + ∞ , t > 0. (35) K\triangleq\operatorname*{arg\,min}_{i\geq1}\frac{T_i}{r_Q(Y_i\mid x)},\qquad t/0\triangleq+\infty,\ t>0. \tag*{(35)} K ≜ i ≥ 1 arg min r Q ( Y i ∣ x ) T i , t /0 ≜ + ∞ , t > 0. (35) Then P Y K ∣ X = x = P Y ∣ X = x P_{Y_K\mid X=x}=P_{Y\mid X=x} P Y K ∣ X = x = P Y ∣ X = x for P X P_X P X -a.e. x x x and
H ( Y K ∣ Z ) ≤ I F ( X → Y ) + log e . (36) H(Y_K\mid Z)\leq I_F(X\to Y)+\log e. \tag*{(36)} H ( Y K ∣ Z ) ≤ I F ( X → Y ) + log e . (36) Moreover, this upper bound is achievable within one bit by encoding K K K conditioned on Z Z Z using the Shannon-Fano code for the distribution
Q K ∣ Z ( k ∣ z ) ≜ a Y k Q ( t k ) ζ ( z ) , (37) Q_{K\mid Z}(k\mid z)\triangleq\frac{a^Q_{Y_k}(t_k)}{\zeta(z)}, \tag*{(37)} Q K ∣ Z ( k ∣ z ) ≜ ζ ( z ) a Y k Q ( t k ) , (37) where, for t > 0 t>0 t > 0 ,
a y Q ( t ) ≜ ∫ X exp ( − t r Q ( y ∣ x ) ) d P X ( x ) , (38) a^Q_y(t)\triangleq\int_{\mathcal{X}}\exp\left(-\frac{t}{r_Q(y\mid x)}\right)dP_X(x), \tag*{(38)} a y Q ( t ) ≜ ∫ X exp ( − r Q ( y ∣ x ) t ) d P X ( x ) , (38) and ζ ( z ) = ∑ k = 1 ∞ a y k Q ( t k ) \zeta(z)=\sum_{k=1}^{\infty}a^Q_{y_k}(t_k) ζ ( z ) = ∑ k = 1 ∞ a y k Q ( t k ) is a normalizing factor.
Proof. For fixed x x x , discard points with r Q ( y ∣ x ) = 0 r_Q(y\mid x)=0 r Q ( y ∣ x ) = 0 and set s = t / r Q ( y ∣ x ) s=t/r_Q(y\mid x) s = t / r Q ( y ∣ x ) . The transformed process has intensity measure P Y ∣ X = x ⊗ λ P_{Y\mid X=x}\otimes\lambda P Y ∣ X = x ⊗ λ and its first arrival time θ Q \theta_Q θ Q is distributed as θ Q ∼ Exp ( 1 ) \theta_Q\sim\operatorname{Exp}(1) θ Q ∼ Exp ( 1 ) , independently of its first mark, which has distribution P Y ∣ X = x P_{Y\mid X=x} P Y ∣ X = x ; see [4 Appendix A] . This establishes the correctness of the Poisson functional representation under arbitrary proposal Q Y Q_Y Q Y . Thus,
( X , Y K ) ∼ P X , Y , θ Q ∼ Exp ( 1 ) , and θ Q ⊥ ( X , Y K ) . (39) (X,Y_K)\sim P_{X,Y},\ \theta_Q\sim\operatorname{Exp}(1),\ \text{and }\theta_Q\perp(X,Y_K). \tag*{(39)} ( X , Y K ) ∼ P X , Y , θ Q ∼ Exp ( 1 ) , and θ Q ⊥ ( X , Y K ) . (39)
We next show that H ( Y K ∣ Z ) ≤ I F ( X → Y ) + log e H(Y_K\mid Z)\leq I_F(X\to Y)+\log e H ( Y K ∣ Z ) ≤ I F ( X → Y ) + log e by bounding the entropy as
H ( Y K ∣ Z ) ≤ H ( P K ∣ Z ; Q K ∣ Z ) = E [ − log a Y K Q ( T K ) ] + E [ log ζ ( Z ) ] . (40) \begin{aligned}
H(Y_K\mid Z)&\leq H(P_{K\mid Z};Q_{K\mid Z})\\
&=\mathbb{E}[-\log a^Q_{Y_K}(T_K)]+\mathbb{E}[\log\zeta(Z)]. \tag*{(40)}
\end{aligned} H ( Y K ∣ Z ) ≤ H ( P K ∣ Z ; Q K ∣ Z ) = E [ − log a Y K Q ( T K )] + E [ log ζ ( Z )] . (40)
The finiteness of both expectations will be verified below. For the second term in (40), note that, by Campbell’s formula [26 Proposition 2.7] ,
E [ ζ ( Z ) ] = ∫ Y ∫ 0 ∞ a y Q ( t ) d t d Q Y ( y ) (41) \mathbb{E}[\zeta(Z)]=\int_{\mathcal{Y}}\int_0^\infty a^Q_y(t)\,dt\,dQ_Y(y) \tag*{(41)} E [ ζ ( Z )] = ∫ Y ∫ 0 ∞ a y Q ( t ) d t d Q Y ( y ) (41)
= ∫ Y ∫ X r Q ( y ∣ x ) d P X ( x ) d Q Y ( y ) (42) =\int_{\mathcal{Y}}\int_{\mathcal{X}}r_Q(y\mid x)\,dP_X(x)\,dQ_Y(y) \tag*{(42)} = ∫ Y ∫ X r Q ( y ∣ x ) d P X ( x ) d Q Y ( y ) (42)
= ∫ Y d P Y d Q Y ( y ) d Q Y ( y ) = 1. (43) =\int_{\mathcal{Y}}\frac{dP_Y}{dQ_Y}(y)\,dQ_Y(y)=1. \tag*{(43)} = ∫ Y d Q Y d P Y ( y ) d Q Y ( y ) = 1. (43)
Therefore, ζ ( Z ) \zeta(Z) ζ ( Z ) is almost surely finite. Also, ζ ( Z ) ≥ a Y K Q ( T K ) > 0 \zeta(Z)\geq a^Q_{Y_K}(T_K)>0 ζ ( Z ) ≥ a Y K Q ( T K ) > 0 almost surely, so Q K ∣ Z Q_{K\mid Z} Q K ∣ Z is a well-defined probability distribution. Moreover, by Jensen’s inequality,
E [ log ζ ( Z ) ] ≤ log E [ ζ ( Z ) ] = 0. (44) \mathbb{E}[\log\zeta(Z)]\leq\log\mathbb{E}[\zeta(Z)]=0. \tag*{(44)} E [ log ζ ( Z )] ≤ log E [ ζ ( Z )] = 0. (44)
To bound the first term in (40), write R Q = r Q ( Y K ∣ X ) R_Q=r_Q(Y_K\mid X) R Q = r Q ( Y K ∣ X ) and R = r ( Y K ∣ X ) R=r(Y_K\mid X) R = r ( Y K ∣ X ) , so that T K = R Q θ Q T_K=R_Q\theta_Q T K = R Q θ Q . For t > 0 t>0 t > 0 , define a y ( t ) ≜ ∫ X exp ( − t / r ( y ∣ x ) ) d P X ( x ) a_y(t)\triangleq\int_{\mathcal{X}}\exp(-t/r(y\mid x))\,dP_X(x) a y ( t ) ≜ ∫ X exp ( − t / r ( y ∣ x )) d P X ( x ) , with the same convention when r ( y ∣ x ) = 0 r(y\mid x)=0 r ( y ∣ x ) = 0 . Since 0 < d P Y d Q Y ( Y K ) < ∞ 0<\frac{dP_Y}{dQ_Y}(Y_K)<\infty 0 < d Q Y d P Y ( Y K ) < ∞ almost surely, we have
a Y K Q ( T K ) = ∫ X exp ( − T K r Q ( Y K ∣ x ) ) d P X ( x ) (45) a^Q_{Y_K}(T_K)=\int_{\mathcal{X}}\exp\left(-\frac{T_K}{r_Q(Y_K\mid x)}\right)dP_X(x) \tag*{(45)} a Y K Q ( T K ) = ∫ X exp ( − r Q ( Y K ∣ x ) T K ) d P X ( x ) (45)
= ∫ X exp ( − R Q d P Y d Q Y ( Y K ) r ( Y K ∣ x ) d P Y d Q Y ( Y K ) ) d P X ( x ) (46) =\int_{\mathcal{X}}\exp\left(-\frac{R_Q\frac{dP_Y}{dQ_Y}(Y_K)}{r(Y_K\mid x)\frac{dP_Y}{dQ_Y}(Y_K)}\right)dP_X(x) \tag*{(46)} = ∫ X exp ( − r ( Y K ∣ x ) d Q Y d P Y ( Y K ) R Q d Q Y d P Y ( Y K ) ) d P X ( x ) (46)
= ∫ X exp ( − R θ Q r ( Y K ∣ x ) ) d P X ( x ) = a Y K ( R θ Q ) . (47) = \int_{\mathcal{X}} \exp\left(-\frac{R\theta_Q}{r(Y_K \mid x)}\right) dP_X(x) = a_{Y_K}(R\theta_Q). \tag*{(47)} = ∫ X exp ( − r ( Y K ∣ x ) R θ Q ) d P X ( x ) = a Y K ( R θ Q ) . (47)
Therefore,
E [ − log a Y K Q ( T K ) ] = E [ − log a Y K ( R θ Q ) ] . (48) \mathbb{E}\left[-\log a^Q_{Y_K}(T_K)\right] = \mathbb{E}\left[-\log a_{Y_K}(R\theta_Q)\right]. \tag*{(48)} E [ − log a Y K Q ( T K ) ] = E [ − log a Y K ( R θ Q ) ] . (48)
Using d P X ∣ Y = y ( x ) = r ( y ∣ x ) d P X ( x ) dP_{X\mid Y=y}(x)=r(y\mid x)dP_X(x) d P X ∣ Y = y ( x ) = r ( y ∣ x ) d P X ( x ) gives, for P Y P_Y P Y -a.e. y y y and t > 0 t>0 t > 0 ,
f R θ Q ∣ Y K = y ( t ) = ∫ { r ( y ∣ x ) > 0 } e − t / r ( y ∣ x ) r ( y ∣ x ) P X ∣ Y = y ( d x ) = a y ( t ) . (49) f_{R\theta_Q\mid Y_K=y}(t)=\int_{\{r(y\mid x)>0\}}\frac{e^{-t/r(y\mid x)}}{r(y\mid x)}P_{X\mid Y=y}(dx)=a_y(t). \tag*{(49)} f R θ Q ∣ Y K = y ( t ) = ∫ { r ( y ∣ x ) > 0 } r ( y ∣ x ) e − t / r ( y ∣ x ) P X ∣ Y = y ( d x ) = a y ( t ) . (49)
Therefore,
E [ − log a Y K ( R θ Q ) ] = h ( R θ Q ∣ Y K ) . (50) \mathbb{E}\left[-\log a_{Y_K}(R\theta_Q)\right]=h(R\theta_Q\mid Y_K). \tag*{(50)} E [ − log a Y K ( R θ Q ) ] = h ( R θ Q ∣ Y K ) . (50)
The remainder of the proof will be upper-bounding this differential entropy. Define independent variables U ∼ Unif ( 0 , 1 ) U\sim\operatorname{Unif}(0,1) U ∼ Unif ( 0 , 1 ) and V ∼ Gamma ( 2 , 1 ) V\sim\operatorname{Gamma}(2,1) V ∼ Gamma ( 2 , 1 ) , independent of ( X , Z ) (X,Z) ( X , Z ) , and set
A = R U , B = A V = R U V . (51) A=RU,\qquad B=AV=RUV. \tag*{(51)} A = R U , B = A V = R U V . (51)
Here V V V has density f V ( v ) = v e − v 1 [ v > 0 ] f_V(v)=ve^{-v}\mathbf{1}[v>0] f V ( v ) = v e − v 1 [ v > 0 ] . We obtain, for a > 0 a>0 a > 0 , that
f A ∣ Y K = y ( a ) = ∫ { r ( y ∣ x ) > 0 } 1 [ 0 < a ≤ r ( y ∣ x ) ] r ( y ∣ x ) P X ∣ Y = y ( d x ) = w y ( a ) . \begin{aligned}
f_{A\mid Y_K=y}(a)=\int_{\{r(y\mid x)>0\}}\frac{\mathbf{1}[0<a\le r(y\mid x)]}{r(y\mid x)}P_{X\mid Y=y}(dx) \\
&=w_y(a).
\end{aligned} f A ∣ Y K = y ( a ) = ∫ { r ( y ∣ x ) > 0 } r ( y ∣ x ) 1 [ 0 < a ≤ r ( y ∣ x )] P X ∣ Y = y ( d x ) = w y ( a ) .
Hence,
h ( A ∣ Y K ) = I F ( X → Y ) . (52) h(A\mid Y_K)=I_F(X\to Y). \tag*{(52)} h ( A ∣ Y K ) = I F ( X → Y ) . (52)
Moreover,
f U V ( s ) = ∫ s ∞ 1 v v e − v d v = e − s , s > 0 , (53) f_{UV}(s)=\int_s^\infty\frac{1}{v}ve^{-v}\,dv=e^{-s},\qquad s>0, \tag*{(53)} f U V ( s ) = ∫ s ∞ v 1 v e − v d v = e − s , s > 0 , (53)
so U V ∼ Exp ( 1 ) UV\sim\operatorname{Exp}(1) U V ∼ Exp ( 1 ) and ( B , Y K ) (B,Y_K) ( B , Y K ) has the same distribution as ( R θ Q , Y K ) (R\theta_Q,Y_K) ( R θ Q , Y K ) . Conditioned on Y K Y_K Y K , V → U V → B V\to UV\to B V → U V → B is a Markov chain. The data processing inequality, along with the fact that ( U , V ) (U,V) ( U , V ) is independent of Y K Y_K Y K , gives
I ( V ; B ∣ Y K ) ≤ I ( V ; U V ∣ Y K ) = I ( V ; U V ) . (54) I(V;B\mid Y_K)\le I(V;UV\mid Y_K)=I(V;UV). \tag*{(54)} I ( V ; B ∣ Y K ) ≤ I ( V ; U V ∣ Y K ) = I ( V ; U V ) . (54)
Then, the scaling property of differential entropy gives
h ( B ∣ V , Y K ) = h ( A ∣ Y K ) + E [ log V ] , h ( U V ∣ V ) = E [ log V ] . h(B\mid V,Y_K)=h(A\mid Y_K)+\mathbb{E}[\log V],\qquad h(UV\mid V)=\mathbb{E}[\log V]. h ( B ∣ V , Y K ) = h ( A ∣ Y K ) + E [ log V ] , h ( U V ∣ V ) = E [ log V ] .
Since I F ( X → Y ) < ∞ I_F(X\to Y)<\infty I F ( X → Y ) < ∞ by Proposition 3 and E [ ∣ log V ∣ ] < ∞ \mathbb{E}[|\log V|]<\infty E [ ∣ log V ∣ ] < ∞ , the preceding identities and (54) justify the following entropy calculation:
h ( R θ Q ∣ Y K ) = h ( B ∣ Y K ) = h ( B ∣ V , Y K ) + I ( V ; B ∣ Y K ) = h ( A ∣ Y K ) + E [ log V ] + I ( V ; B ∣ Y K ) ≤ h ( A ∣ Y K ) + E [ log V ] + I ( V ; U V ) = h ( A ∣ Y K ) + h ( U V ) = I F ( X → Y ) + log ( e ) , (55) \begin{aligned}
h(R\theta_Q\mid Y_K)&=h(B\mid Y_K)\\
&=h(B\mid V,Y_K)+I(V;B\mid Y_K)\\
&=h(A\mid Y_K)+\mathbb{E}[\log V]+I(V;B\mid Y_K)\\
&\le h(A\mid Y_K)+\mathbb{E}[\log V]+I(V;UV)\\
&=h(A\mid Y_K)+h(UV)\\
&=I_F(X\to Y)+\log(e), \tag*{(55)}
\end{aligned} h ( R θ Q ∣ Y K ) = h ( B ∣ Y K ) = h ( B ∣ V , Y K ) + I ( V ; B ∣ Y K ) = h ( A ∣ Y K ) + E [ log V ] + I ( V ; B ∣ Y K ) ≤ h ( A ∣ Y K ) + E [ log V ] + I ( V ; U V ) = h ( A ∣ Y K ) + h ( U V ) = I F ( X → Y ) + log ( e ) , (55)
where the last equality follows since U V ∼ Exp ( 1 ) UV\sim\operatorname{Exp}(1) U V ∼ Exp ( 1 ) . This proves that E [ − log a Y K Q ( T K ) ] \mathbb{E}[-\log a^Q_{Y_K}(T_K)] E [ − log a Y K Q ( T K )] is finite. Since 0 < a Y K Q ( T K ) ≤ 1 0<a^Q_{Y_K}(T_K)\le1 0 < a Y K Q ( T K ) ≤ 1 and ζ ( Z ) ≥ a Y K Q ( T K ) \zeta(Z)\ge a^Q_{Y_K}(T_K) ζ ( Z ) ≥ a Y K Q ( T K ) , the negative part of log ζ ( Z ) \log\zeta(Z) log ζ ( Z ) is bounded by − log a Y K Q ( T K ) -\log a^Q_{Y_K}(T_K) − log a Y K Q ( T K ) ; its positive part is integrable because E [ ζ ( Z ) ] = 1 \mathbb{E}[\zeta(Z)]=1 E [ ζ ( Z )] = 1 . Thus, (40) is justified and gives the claimed entropy bound. Finally, a Shannon code for Q K ∣ Z Q_{K\mid Z} Q K ∣ Z assigns lengths ⌈ − log Q K ∣ Z ( k ∣ z ) ⌉ \lceil-\log Q_{K\mid Z}(k\mid z)\rceil ⌈ − log Q K ∣ Z ( k ∣ z )⌉ on its support, so its expected length is less than H ( P K ∣ Z ; Q K ∣ Z ) + 1 ≤ I F ( X → Y ) + log e + 1 H(P_{K\mid Z};Q_{K\mid Z})+1\le I_F(X\to Y)+\log e+1 H ( P K ∣ Z ; Q K ∣ Z ) + 1 ≤ I F ( X → Y ) + log e + 1 .
Our coding distribution Q K ∣ Z Q_{K\mid Z} Q K ∣ Z for the Poisson functional representation also has an intuitive explanation. For fixed X = x X=x X = x , the density ratio of the returned point ( Y K , T K ) (Y_K,T_K) ( Y K , T K ) with respect to the proposal Q Y ⊗ λ Q_Y\otimes\lambda Q Y ⊗ λ is
d P Y K , T K ∣ X = x d Q Y ⊗ λ ( y , t ) = exp ( − t r Q ( y ∣ x ) ) . (56) \frac{dP_{Y_K,T_K\mid X=x}}{dQ_Y\otimes\lambda}(y,t)=\exp\left(-\frac{t}{r_Q(y\mid x)}\right). \tag*{(56)} d Q Y ⊗ λ d P Y K , T K ∣ X = x ( y , t ) = exp ( − r Q ( y ∣ x ) t ) . (56)
Intuitively, a point ( y , t ) (y,t) ( y , t ) will be returned if it is the minimum value of the transformed process, which is equivalent to no point T i / r Q ( Y i ∣ x ) T_i/r_Q(Y_i\mid x) T i / r Q ( Y i ∣ x ) falling into the interval [ 0 , t / r Q ( y ∣ x ) ) [0,t/r_Q(y\mid x)) [ 0 , t / r Q ( y ∣ x )) . Treating the remaining points as an independent, unobserved Poisson process, this probability is exactly exp ( − t / r Q ( y ∣ x ) ) \exp(-t/r_Q(y\mid x)) exp ( − t / r Q ( y ∣ x )) . Integrating this density over all possible values of X X X , we obtain
∫ X exp ( − T K r Q ( Y K ∣ x ) ) d P X ( x ) = a Y K Q ( T K ) . (57) \int_{\mathcal{X}}\exp\left(-\frac{T_K}{r_Q(Y_K\mid x)}\right)dP_X(x)=a^Q_{Y_K}(T_K). \tag*{(57)} ∫ X exp ( − r Q ( Y K ∣ x ) T K ) d P X ( x ) = a Y K Q ( T K ) . (57)
After normalizing to be a probability distribution, this is exactly Q K ∣ Z Q_{K|Z} Q K ∣ Z .
Remark 3 (Computational Complexity). Following [11 ] , we call the encoding of K K K using the conditional coding distribution Q K ∣ Z Q_{K|Z} Q K ∣ Z , defined in (37), the ring toss code. The ring toss code for the Poisson functional representation removes the requirement in [11 ] that the density ratio d P Y ∣ X d P Y \frac{\mathrm{d}P_{Y|X}}{\mathrm{d}P_Y} d P Y d P Y ∣ X be bounded while being optimal within log e \log e log e bits. However, this comes at a price: the distribution Q K ∣ Z Q_{K|Z} Q K ∣ Z is likely quite difficult to use, requiring computing an infinite sum. In light of this limitation, we view the coding distribution Q K ∣ Z Q_{K|Z} Q K ∣ Z as primarily a theoretical tool for bounding H ( Y ∣ Z ) H(Y \mid Z) H ( Y ∣ Z ) rather than a practical coding distribution. Moreover, the Poisson functional representation is a noncausal [27 ] algorithm, meaning it cannot be implemented on a computer. There exist implementable variants such as A* coding [28 ] , but they require that
inf Q Y E X [ ess sup y ∼ Q Y d P Y ∣ X d Q Y ( y ∣ X ) ] < ∞ . (58) \inf_{Q_Y}\mathbb{E}_X\left[\underset{y\sim Q_Y}{\operatorname{ess\,sup}}\frac{\mathrm{d}P_{Y|X}}{\mathrm{d}Q_Y}(y \mid X)\right] < \infty. \tag*{(58)} Q Y inf E X [ y ∼ Q Y ess sup d Q Y d P Y ∣ X ( y ∣ X ) ] < ∞. (58)
We expect that the insights of this work can be used to design practical coding distributions for general channels with unbounded Shtarkov integral. In Appendix D, we exhibit an encoding scheme of the index returned by greedy Poisson rejection sampling [23 ] , a causal algorithm for general channels, which is optimal within 2 log e + 2 2\log e + 2 2 log e + 2 bits.
Remark 4. During the final preparation of this manuscript, Li [12 ] independently established the constant-gap optimality of the Poisson functional representation for channel simulation. Specifically, Li introduced a family of generalized functional information measures, of which the exponential functional information I E ( X → Y ) I_{\mathrm{E}}(X \to Y) I E ( X → Y ) is a special case, and proved that the Poisson functional representation with proposal distribution P Y P_Y P Y and common randomness Z Z Z satisfies
H ( Y ∣ Z ) ≤ I E ( X → Y ) + log e . H(Y \mid Z) \le I_{\mathrm{E}}(X \to Y) + \log e. H ( Y ∣ Z ) ≤ I E ( X → Y ) + log e .
In Li’s family of generalized functional information measures, a uniform auxiliary variable on ( 0 , 1 ) (0,1) ( 0 , 1 ) recovers the likelihood-ratio tail formula for I F ( X → Y ) I_{\mathrm{F}}(X \to Y) I F ( X → Y ) , while an exponential auxiliary variable of rate e e e gives I E ( X → Y ) I_{\mathrm{E}}(X \to Y) I E ( X → Y ) . It was also proved in [12 ] that I E ( X → Y ) ≤ I F ( X → Y ) I_{\mathrm{E}}(X \to Y) \le I_{\mathrm{F}}(X \to Y) I E ( X → Y ) ≤ I F ( X → Y ) . Together with the converse I F ( X → Y ) ≤ R ∗ ( X → Y ) I_{\mathrm{F}}(X \to Y) \le R^*(X \to Y) I F ( X → Y ) ≤ R ∗ ( X → Y ) of Flamich, Sriramu, and Wagner [8 ] , this shows that the conditional entropy of the Poisson functional representation is within log e \log e log e bits of optimal.
We draw the following differences between our result and that of [12 ] . First, Li [12 ] considers the Poisson functional representation with the marginal distribution P Y P_Y P Y as its proposal distribution, whereas our result applies to an arbitrary dominating proposal distribution Q Y Q_Y Q Y . This additional flexibility allows the proposal distribution to be chosen independently of the channel output marginal. Second, our proof is constructive: we give an explicit coding distribution Q K ∣ Z Q_{K|Z} Q K ∣ Z for the index K K K , conditioned on the common randomness Z Z Z . The proof in [12 ] considers P K ∣ Z ( k ∣ z ) P_{K|Z}(k \mid z) P K ∣ Z ( k ∣ z ) as the P X P_X P X -mass of the set of inputs for which point K = k K=k K = k , in contrast, each unnormalized weight in (37) depends only on the corresponding point ( y k , t k ) (y_k,t_k) ( y k , t k ) , so our code avoids computing these set probabilities.
Corollaries of the Upper Bound
In this section, we collect some immediate corollaries of our main results. While we state the results for the Poisson functional representation, which has fewer assumptions, for any channel with bounded Shtarkov integral the same results can be achieved using rejection sampling.
Theorem 5, along with the lower bound of Theorem 4, gives a characterization of the one-shot rate of channel simulation that is complete up to a constant.
Theorem 1. Let X , Y X, Y X , Y be jointly distributed random variables over an arbitrary Polish space. Then,
I F ( X → Y ) ≤ R ∗ ( X → Y ) ≤ I F ( X → Y ) + log e . I_{\mathrm{F}}(X \to Y) \le R^*(X \to Y) \le I_{\mathrm{F}}(X \to Y) + \log e. I F ( X → Y ) ≤ R ∗ ( X → Y ) ≤ I F ( X → Y ) + log e .
The cost of channel simulation can also be written in terms of the mutual information, improving the constant from 2.74 to 2.45 in the bound of [5 ] .
Corollary 1. For any X , Y ∼ P X , Y X, Y \sim P_{X,Y} X , Y ∼ P X , Y with I ( X ; Y ) < ∞ I(X;Y) < \infty I ( X ; Y ) < ∞ ,
R ∗ ( X → Y ) ≤ I ( X ; Y ) + log ( I ( X ; Y ) + 1 ) + 1 + log e ≤ I ( X ; Y ) + log ( I ( X ; Y ) + 1 ) + 2.45. \begin{aligned}
R^*(X \to Y) \le I(X;Y) + \log(I(X;Y)+1) + 1 + \log e \\
&\le I(X;Y) + \log(I(X;Y)+1) + 2.45.
\end{aligned} R ∗ ( X → Y ) ≤ I ( X ; Y ) + log ( I ( X ; Y ) + 1 ) + 1 + log e ≤ I ( X ; Y ) + log ( I ( X ; Y ) + 1 ) + 2.45.
Proof. The result follows immediately by applying the upper bound in Proposition 3 to the result of Theorem 5 and invoking Jensen’s inequality. □
Singular channels have been previously shown to admit relative entropy codes with sub-logarithmic redundancy in the asymptotic case [13 ] , [29 ] . Using Theorem 5, we immediately obtain a significantly stronger statement: all singular channels achieve a constant one-shot redundancy over the mutual information.
Corollary 2. Let X , Y ∼ P X , Y X, Y \sim P_{X,Y} X , Y ∼ P X , Y with X → Y X \to Y X → Y singular. Then,
R ∗ ( X → Y ) ≤ I ( X ; Y ) + log e . (59) R^*(X \to Y) \le I(X;Y) + \log e. \tag*{(59)} R ∗ ( X → Y ) ≤ I ( X ; Y ) + log e . (59)
Together, Theorem 5 and Corollary 2 immediately recover previous results on the asymptotic rate of relative entropy coding [8 , 13 ] . Concretely, given P X , Y P_{X,Y} P X , Y , consider the problem of simulating n n n independent copies of the channel X → Y X \to Y X → Y , i.e., letting ( X n , Y n ) ∼ ( P X , Y ) ⊗ n (X^n,Y^n) \sim(P_{X,Y})^{\otimes n} ( X n , Y n ) ∼ ( P X , Y ) ⊗ n , letting the proposal distribution be P Y ⊗ n P_Y^{\otimes n} P Y ⊗ n and, upon input X n ∼ P X ⊗ n X^n \sim P_X^{\otimes n} X n ∼ P X ⊗ n , sending a binary message so the decoder can generate a sample Y n ∼ P Y n ∣ X n = x n Y^n \sim P_{Y^n|X^n=x^n} Y n ∼ P Y n ∣ X n = x n . In this problem, of interest is the best achievable rate per dimension
R n ≜ 1 n inf ( Z , e n c , d e c ) E [ ∣ e n c ( X n , Z ) ∣ ] . (60) R_n \triangleq\frac{1}{n}\inf_{(Z,\mathrm{enc},\mathrm{dec})} \mathbb{E}[|\mathrm{enc}(X^n,Z)|]. \tag*{(60)} R n ≜ n 1 ( Z , enc , dec ) inf E [ ∣ enc ( X n , Z ) ∣ ] . (60)
The distribution P X n , Y n P_{X^n,Y^n} P X n , Y n satisfies I ( X n ; Y n ) = n I ( X ; Y ) I(X^n;Y^n) = nI(X;Y) I ( X n ; Y n ) = n I ( X ; Y ) , and hence R n → I ( X ; Y ) R_n \to I(X;Y) R n → I ( X ; Y ) as n → ∞ n \to\infty n → ∞ . Given the fundamental lower bound H ( Y ∣ Z ) ≥ I ( X ; Y ) H(Y \mid Z) \ge I(X;Y) H ( Y ∣ Z ) ≥ I ( X ; Y ) , this is the optimal limit. In light of the logarithmic gap over the mutual information in the one-shot case, [8 , 13 ] study the logarithmic redundancy
R log ≜ lim n → ∞ n ( R n − I ( X ; Y ) ) log n . (61) R^{\log} \triangleq\lim_{n\to\infty} \frac{n(R_n-I(X;Y))}{\log n}. \tag*{(61)} R l o g ≜ n → ∞ lim log n n ( R n − I ( X ; Y )) . (61)
Whenever the limit exists, the preceding bounds give 0 ≤ R log ≤ 1 0 \le R^{\log} \le1 0 ≤ R l o g ≤ 1 . As a corollary to Theorem 5, we obtain the same characterization of R log R^{\log} R l o g as [8 ] :
Corollary 3. Under the asymptotic setup previously described, for any X , Y ∼ P X , Y X,Y \sim P_{X,Y} X , Y ∼ P X , Y whose information density has a finite second moment,
R log = { 0 , X → Y singular 1 / 2 , X → Y nonsingular . (62) R^{\log} =
\begin{cases}
0, & X \to Y\ \text{singular}\\
1/2, & X \to Y\ \text{nonsingular}.
\end{cases} \tag*{(62)} R l o g = { 0 , 1/2 , X → Y singular X → Y nonsingular . (62)
Proof. The singular case is immediate from Corollary 2. For the nonsingular case, we use a result from the proof of Theorem 3.1.6 in [8 ] , which shows that nonsingular channels whose information density has a finite second moment satisfy
lim n → ∞ I F ( X n → Y n ) − I ( X n ; Y n ) log n = 1 2 . (63) \lim_{n\to\infty} \frac{I_F(X^n \to Y^n)-I(X^n;Y^n)}{\log n} = \frac{1}{2}. \tag*{(63)} n → ∞ lim log n I F ( X n → Y n ) − I ( X n ; Y n ) = 2 1 . (63)
Combining the above result with Theorem 5 completes the proof.
Our construction has the advantage over [13 , 29 ] of being significantly simpler and one-shot optimal. In contrast, in the singular case, the achievability algorithms of both [13 ] and [29 ] incur an O ( log log n ) O(\log\log n) O ( log log n ) penalty in total length over n I ( X ; Y ) nI(X;Y) n I ( X ; Y ) .
One-shot and finite-blocklength lossy compression
An immediate and quite interesting application of our results is the tight characterization of finite blocklength lossy source coding. For a source P X P_X P X and (measurable) distortion measure Δ : X × Y → [ 0 , ∞ ) \Delta: \mathcal{X} \times\mathcal{Y} \to[0,\infty) Δ : X × Y → [ 0 , ∞ ) , the classical rate-distortion function
R ( D ) = inf P Y ∣ X : E [ Δ ( X , Y ) ] ≤ D I ( X ; Y ) (64) R(D) = \inf_{P_{Y|X}:\mathbb{E}[\Delta(X,Y)]\le D} I(X;Y) \tag*{(64)} R ( D ) = P Y ∣ X : E [ Δ ( X , Y )] ≤ D inf I ( X ; Y ) (64)
is achievable in general by letting the blocklength grow to ∞ \infty ∞ . Using our results, we are able to tightly characterize the achievable-rate region for any blocklength n n n . Our proofs rely on the channel simulation results proved earlier. Our characterization relies on a measure we call the functional rate-distortion function . We formally state the definitions in (6) and (7).
Definition 8 (Functional rate-distortion function). Fix a source P X P_X P X and a distortion measure Δ \Delta Δ . We make the usual assumption that min y ∈ Y Δ ( x , y ) = 0 \min_{y\in\mathcal{Y}}\Delta(x,y)=0 min y ∈ Y Δ ( x , y ) = 0 for all x ∈ X x \in\mathcal{X} x ∈ X and that E [ Δ ( X , y ∗ ) ] < ∞ \mathbb{E}[\Delta(X,y^*)] < \infty E [ Δ ( X , y ∗ )] < ∞ for some y ∗ ∈ Y y^* \in\mathcal{Y} y ∗ ∈ Y . Then, the functional rate-distortion function is defined as
R F ( D ) ≜ inf P Y ∣ X : E [ Δ ( X , Y ) ] ≤ D I F ( X → Y ) . (65) R_F(D) \triangleq\inf_{P_{Y|X}:\mathbb{E}[\Delta(X,Y)]\le D} I_F(X \to Y). \tag*{(65)} R F ( D ) ≜ P Y ∣ X : E [ Δ ( X , Y )] ≤ D inf I F ( X → Y ) . (65)
Note that R F ( D ) R_F(D) R F ( D ) is nonincreasing, and by Proposition 5, it is also convex in D D D on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) . We are interested in bounding the rate of variable-length lossy source coding of X X X subject to a distortion constraint. As in the introduction, the operational rate-distortion function is
R O ( D ) ≜ inf P Y ∣ X : Y countably-valued E [ Δ ( X , Y ) ] ≤ D H ( Y ) . (66) R_O(D) \triangleq\inf_{\substack{P_{Y|X}:Y\ \text{countably-valued}\\ \mathbb{E}[\Delta(X,Y)]\le D}} H(Y). \tag*{(66)} R O ( D ) ≜ P Y ∣ X : Y countably-valued E [ Δ ( X , Y )] ≤ D inf H ( Y ) . (66)
The encoder may use private randomness to generate the reproduction Y Y Y . It sends a uniquely decodable description of Y Y Y to the decoder. We have the following result.
Theorem 2. Let X \mathcal{X} X and Y \mathcal{Y} Y be Polish spaces. For any source distribution P X P_X P X and any D > 0 D>0 D > 0 ,
R F ( D ) ≤ R O ( D ) ≤ R F ( D ) + log e + 1. (67) R_F(D) \le R_O(D) \le R_F(D) + \log e + 1. \tag*{(67)} R F ( D ) ≤ R O ( D ) ≤ R F ( D ) + log e + 1. (67)
For the upper bound, the encoder draws a single Bernoulli variable B B B independently of X X X and encodes the pair ( B , g B ( X ) ) (B,g_B(X)) ( B , g B ( X )) , as in [4 Proof of Thm. 2] . The selector contributes at most one bit to the joint entropy.
Theorem 2 has an immediate consequence for finite-blocklength lossy source coding. Let X n = ( X 1 , … , X n ) X^n=(X_1,\ldots,X_n) X n = ( X 1 , … , X n ) be an n n n -block of X \mathcal{X} X -valued random variables and let the reproduction n n n -block be Y n = ( Y 1 , … , Y n ) Y^n=(Y_1,\ldots,Y_n) Y n = ( Y 1 , … , Y n ) . Define Δ n ( x n , y n ) = 1 n ∑ i = 1 n Δ ( x i , y i ) \Delta_n(x^n,y^n)=\frac{1}{n}\sum_{i=1}^n\Delta(x_i,y_i) Δ n ( x n , y n ) = n 1 ∑ i = 1 n Δ ( x i , y i ) and let R F , n ( D ) R_{F,n}(D) R F , n ( D ) and R O , n ( D ) R_{O,n}(D) R O , n ( D ) be the n n n th-order functional and operational rate-distortion functions, respectively, defined by replacing Δ \Delta Δ with Δ n \Delta_n Δ n , X X X with X n X^n X n , Y Y Y with Y n Y^n Y n in (65) and (66), and normalizing by the block-length n n n . Then Theorem 2 gives the following corollary.
Corollary 4. For any block distribution P X n P_{X^n} P X n and any D > 0 D>0 D > 0 ,
R F , n ( D ) ≤ R O , n ( D ) ≤ R F , n ( D ) + log e + 1 n . (68) R_{F,n}(D)\le R_{O,n}(D)\le R_{F,n}(D)+\frac{\log e+1}{n}. \tag*{(68)} R F , n ( D ) ≤ R O , n ( D ) ≤ R F , n ( D ) + n log e + 1 . (68)
Remark 5. Note that for simplicity we have used the Shannon entropy H ( Y ) H(Y) H ( Y ) as the rate of the code when defining R O ( D ) R_O(D) R O ( D ) . If, instead, one defined the rate as the expected codeword length E [ ∣ enc ( Y ) ∣ ] \mathbb{E}[|\operatorname{enc}(Y)|] E [ ∣ enc ( Y ) ∣ ] of a uniquely decodable description enc ( Y ) \operatorname{enc}(Y) enc ( Y ) , then the constant 1 in the upper bounds of Theorem 2 and Corollary 4 would become 2. For example, in this case the upper bound in Theorem 2 would be R O ( D ) ≤ R F ( D ) + log e + 2 R_O(D)\le R_F(D)+\log e+2 R O ( D ) ≤ R F ( D ) + log e + 2 .
Proof of Theorem 2. For the lower bound, every feasible countably valued Y Y Y satisfies R F ( D ) ≤ I F ( X → Y ) ≤ H ( Y ) R_F(D)\le I_F(X\mathbin{\to}Y)\le H(Y) R F ( D ) ≤ I F ( X → Y ) ≤ H ( Y ) , where the second inequality follows from Theorem 4 and H ( Y ∣ Z ) ≤ H ( Y ) H(Y\mid Z)\le H(Y) H ( Y ∣ Z ) ≤ H ( Y ) for any functional representation. For the upper bound we use the following lemma from the proof of [4 Thm. 2] .
Lemma 1 (Randomization between two quantizers). For arbitrary source and reproduction alphabets X \mathcal{X} X and Y \mathcal{Y} Y and distortion measure Δ : X × Y → [ 0 , ∞ ) \Delta:\mathcal{X}\times\mathcal{Y}\to[0,\infty) Δ : X × Y → [ 0 , ∞ ) , let Z Z Z be independent of X X X and Y = g ( X , Z ) Y=g(X,Z) Y = g ( X , Z ) for some measurable g g g . If E [ Δ ( X , Y ) ] ≤ D \mathbb{E}[\Delta(X,Y)]\le D E [ Δ ( X , Y )] ≤ D and H ( Y ∣ Z ) < ∞ H(Y\mid Z)<\infty H ( Y ∣ Z ) < ∞ , then there exist measurable maps g 0 , g 1 : X → Y g_0,g_1:\mathcal{X}\to\mathcal{Y} g 0 , g 1 : X → Y with countable range and a Bernoulli variable B ⊥ X B\perp X B ⊥ X such that, with Y ~ = g B ( X ) \widetilde{Y}=g_B(X) Y = g B ( X ) ,
E [ Δ ( X , Y ~ ) ] ≤ D (69) \mathbb{E}[\Delta(X,\widetilde{Y})]\le D \tag*{(69)} E [ Δ ( X , Y )] ≤ D (69) and
H ( B , Y ~ ) = H ( B ) + H ( Y ~ ∣ B ) ≤ 1 + H ( Y ∣ Z ) . (70) H(B,\widetilde{Y})=H(B)+H(\widetilde{Y}\mid B)\le1+H(Y\mid Z). \tag*{(70)} H ( B , Y ) = H ( B ) + H ( Y ∣ B ) ≤ 1 + H ( Y ∣ Z ) . (70)
The encoder draws the binary selector B B B privately and includes it in the description of Y ~ \widetilde{Y} Y .
Let D > 0 D>0 D > 0 and fix ϵ > 0 \epsilon>0 ϵ > 0 . We may assume R F ( D ) < ∞ R_F(D)<\infty R F ( D ) < ∞ . Choose P Y ∣ X P_{Y\mid X} P Y ∣ X such that E [ Δ ( X , Y ) ] ≤ D \mathbb{E}[\Delta(X,Y)]\le D E [ Δ ( X , Y )] ≤ D and I F ( X → Y ) ≤ R F ( D ) + ϵ I_F(X\mathbin{\to}Y)\le R_F(D)+\epsilon I F ( X → Y ) ≤ R F ( D ) + ϵ . Then Theorem 5 gives common randomness Z Z Z independent of X X X such that Y = g ( X , Z ) Y=g(X,Z) Y = g ( X , Z ) and H ( Y ∣ Z ) ≤ I F ( X → Y ) + log e H(Y\mid Z)\le I_F(X\mathbin{\to}Y)+\log e H ( Y ∣ Z ) ≤ I F ( X → Y ) + log e . Applying Lemma 1 yields a feasible reproduction Y ~ \widetilde{Y} Y with
R O ( D ) ≤ H ( Y ~ ) ≤ H ( B , Y ~ ) ≤ R F ( D ) + log e + 1 + ϵ , R_O(D)\le H(\widetilde{Y})\le H(B,\widetilde{Y})\le R_F(D)+\log e+1+\epsilon, R O ( D ) ≤ H ( Y ) ≤ H ( B , Y ) ≤ R F ( D ) + log e + 1 + ϵ ,
which, because ϵ \epsilon ϵ was arbitrary, gives the result. □ \square □
If P X P_X P X is atomless (for example, if X X X has a density on R n \mathbb{R}^n R n ), a deterministic quantizer suffices for the same upper bound. Indeed, on each cell { g 0 = a , g 1 = b } \{g_0=a,g_1=b\} { g 0 = a , g 1 = b } , assign b b b to the fraction P ( B = 1 ) \mathbb{P}(B=1) P ( B = 1 ) of the cell’s mass with the smallest values of Δ ( x , b ) − Δ ( x , a ) \Delta(x,b)-\Delta(x,a) Δ ( x , b ) − Δ ( x , a ) , splitting ties by atomlessness, and assign a a a elsewhere. This preserves the output distribution of g B ( X ) g_B(X) g B ( X ) and can only decrease its expected distortion.
Theorem 2 demonstrates the importance of R F ( D ) R_F(D) R F ( D ) to rate-distortion theory, motivating a thorough study of its properties. As a small first step toward this, we show that R F ( D ) R_F(D) R F ( D ) has considerable structure when the spaces X , Y \mathcal{X},\mathcal{Y} X , Y are finite.
Proposition 9 (Piecewise linearity of R F R_F R F ). Let X , Y \mathcal{X},\mathcal{Y} X , Y be finite. Then, R F ( D ) R_F(D) R F ( D ) is a piecewise linear function of D D D on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) .
Proof. See Appendix A. □ \square □
Examples of Functional Rate-Distortion Functions
Bernoulli Source with Hamming Distortion. Let X X X be Bernoulli with parameter 0 < p < 1 0<p<1 0 < p < 1 , X ∼ Bern ( p ) X\sim\operatorname{Bern}(p) X ∼ Bern ( p ) , and consider the functional rate-distortion function with Hamming distortion constraint P ( X ≠ Y ) ≤ D \mathbb{P}(X\ne Y)\le D P ( X = Y ) ≤ D . Then, it follows after computation that
R F ( D ) = { h b ( p ) ( 1 − D p min ) , 0 ≤ D < p min 0 , D ≥ p min , (71) R_F(D)=
\begin{cases}
h_b(p)\left(1-\dfrac{D}{p_{\min}}\right), & 0\le D<p_{\min}\\
0, & D\ge p_{\min},
\end{cases} \tag*{(71)} R F ( D ) = ⎩ ⎨ ⎧ h b ( p ) ( 1 − p m i n D ) , 0 , 0 ≤ D < p m i n D ≥ p m i n , (71)
where p min ≜ min ( p , 1 − p ) p_{\min}\triangleq\min(p,1-p) p m i n ≜ min ( p , 1 − p ) and h b ( ⋅ ) h_b(\cdot) h b ( ⋅ ) is the binary entropy function. Comparing this to the classical rate-distortion function
R ( D ) = { h b ( p ) − h b ( D ) , 0 ≤ D < p min 0 , D ≥ p min , (72) R(D)=
\begin{cases}
h_b(p)-h_b(D), & 0\le D<p_{\min}\\
0, & D\ge p_{\min},
\end{cases} \tag*{(72)} R ( D ) = { h b ( p ) − h b ( D ) , 0 , 0 ≤ D < p m i n D ≥ p m i n , (72)
we see that
{ R F ( D ) > R ( D ) , 0 < D < p min R F ( D ) = R ( D ) , D = 0 or D ≥ p min . (73) \begin{cases}
R_F(D)>R(D), & 0<D<p_{\min}\\
R_F(D)=R(D), & D=0\text{ or }D\ge p_{\min}. \tag*{(73)}
\end{cases} { R F ( D ) > R ( D ) , R F ( D ) = R ( D ) , 0 < D < p m i n D = 0 or D ≥ p m i n . (73)
N-ary Uniform Source. Let X X X be an N N N -ary uniform source with alphabet X = { 1 , 2 , … , N } \mathcal{X}=\{1,2,\ldots,N\} X = { 1 , 2 , … , N } . Let Y = X ∪ { e } \mathcal{Y}=\mathcal{X}\cup\{e\} Y = X ∪ { e } , where e e e is the erasure symbol, and define the distortion measure
Δ ( x , y ) = { 0 , x = y 1 , y = e , ∞ , y ∈ X , y ≠ x . (74) \Delta(x,y)=
\begin{cases}
0, & x=y\\
1, & y=e,\\
\infty, & y\in\mathcal{X},\ y\ne x.
\end{cases} \tag*{(74)} Δ ( x , y ) = ⎩ ⎨ ⎧ 0 , 1 , ∞ , x = y y = e , y ∈ X , y = x . (74)
For 0 ≤ D ≤ 1 0\le D\le1 0 ≤ D ≤ 1 , it is well known (e.g., [30 Prob. 6.5] ) that the rate-distortion function is given by R ( D ) = ( 1 − D ) log N R(D)=(1-D)\log N R ( D ) = ( 1 − D ) log N . In our case, the minimizing channel P Y ∣ X P_{Y|X} P Y ∣ X is singular, and hence
R F ( D ) = R ( D ) = ( 1 − D ) log N . (75) R_F(D)=R(D)=(1-D)\log N. \tag*{(75)} R F ( D ) = R ( D ) = ( 1 − D ) log N . (75)
Moreover, this channel satisfies the convex hull condition of Proposition 6. The encoder can erase X X X with probability D D D , independently of X X X , and reproduce X X X otherwise. The resulting output has entropy ( 1 − D ) log N + h b ( D ) (1-D)\log N+h_b(D) ( 1 − D ) log N + h b ( D ) , so
( 1 − D ) log N ≤ R O ( D ) ≤ ( 1 − D ) log N + 1. (76) (1-D)\log N\le R_O(D)\le(1-D)\log N+1. \tag*{(76)} ( 1 − D ) log N ≤ R O ( D ) ≤ ( 1 − D ) log N + 1. (76)
For D ≥ 1 D\ge1 D ≥ 1 , all three rate-distortion functions are zero.
We also remark that our rate-distortion framework immediately extends to the problem of approximate variable-length channel simulation. Setting the distortion to be, for example, the total variation distance with the desired conditional distribution, Theorem 2 shows that the optimal method for approximate channel simulation is to exactly simulate, using the Poisson functional representation, a ‘nearby’ channel.
Rényi Generalization
As in [19 ] , [31 ] , one may be concerned about channel simulation under costs other than the expected message length. In particular, we study channel simulation under the Campbell cost [17 ] , an exponential storage cost appropriate for applications where buffer overflow can occur [32 , 33 , 34 , 35 ] , and therefore, the cost of long codewords is especially significant [36 , 37 , 38 ] . This setup motivates the definition of a Rényi functional information, which shares similar properties with functional information, including closely characterizing the minimum Campbell cost of any stochastic code.
Definition 9 (Rényi Channel Simulation Divergence). For two probability measures P ≪ Q P\ll Q P ≪ Q with width function w w w and α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , define the Rényi channel simulation divergence D α C S ( P ∥ Q ) D_{\alpha}^{\mathrm{CS}}(P\mathbin\Vert Q) D α CS ( P ∥ Q ) as
D α C S ( P ∥ Q ) ≜ h α ( w ) = 1 1 − α log ( ∫ 0 ∞ w ( ℓ ) α d ℓ ) , (77) D_{\alpha}^{\mathrm{CS}}(P\mathbin\Vert Q)\triangleq h_{\alpha}(w)=\frac{1}{1-\alpha}\log\left(\int_{0}^{\infty}w(\ell)^{\alpha}\,\mathrm{d}\ell\right), \tag*{(77)} D α CS ( P ∥ Q ) ≜ h α ( w ) = 1 − α 1 log ( ∫ 0 ∞ w ( ℓ ) α d ℓ ) , (77) where h α h_{\alpha} h α is the differential Rényi entropy.
Definition 10 (Rényi Functional Information). For α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) and X , Y ∼ P X , Y X,Y\sim P_{X,Y} X , Y ∼ P X , Y , the Rényi functional information is defined as
I F , α ( X → Y ) ≜ 1 1 − α log ( E Y [ 2 ( 1 − α ) D α C S ( P X ∣ Y ∥ P X ) ] ) . (78) I_{F,\alpha}(X\to Y)\triangleq\frac{1}{1-\alpha}\log\left(\mathbb{E}_{Y}\left[2^{(1-\alpha)D_{\alpha}^{\mathrm{CS}}(P_{X|Y}\mathbin\Vert P_X)}\right]\right). \tag*{(78)} I F , α ( X → Y ) ≜ 1 − α 1 log ( E Y [ 2 ( 1 − α ) D α CS ( P X ∣ Y ∥ P X ) ] ) . (78) More explicitly,
I F , α ( X → Y ) = 1 1 − α log ( ∫ Y ∫ 0 ∞ w y ( ℓ ) α d ℓ d P Y ( y ) ) , I_{F,\alpha}(X\to Y)=\frac{1}{1-\alpha}\log\left(\int_{\mathcal{Y}}\int_{0}^{\infty}w_y(\ell)^{\alpha}\,\mathrm{d}\ell\,\mathrm{d}P_Y(y)\right), I F , α ( X → Y ) = 1 − α 1 log ( ∫ Y ∫ 0 ∞ w y ( ℓ ) α d ℓ d P Y ( y ) ) , where w y ( ℓ ) = P X ( d P Y ∣ X d P Y ( y ∣ X ) ≥ ℓ ) w_y(\ell)=P_X\left(\frac{\mathrm{d}P_{Y|X}}{\mathrm{d}P_Y}(y\mid X)\ge\ell\right) w y ( ℓ ) = P X ( d P Y d P Y ∣ X ( y ∣ X ) ≥ ℓ ) .
The Rényi functional information satisfies the basic properties that one expects of a mutual information. Before presenting these properties, we recall the definitions of the Rényi divergence and the Sibson α \alpha α -mutual information [39 ] .
Definition 11 (Rényi divergence). For P ≪ Q P\ll Q P ≪ Q probability distributions and α ∈ ( 0 , 1 ) ∪ ( 1 , ∞ ) \alpha\in(0,1)\cup(1,\infty) α ∈ ( 0 , 1 ) ∪ ( 1 , ∞ ) , the Rényi divergence of order α \alpha α between P P P and Q Q Q is defined as
D α ( P ∥ Q ) ≜ 1 α − 1 log ( E X ∼ Q [ ( d P d Q ( X ) ) α ] ) . (79) D_{\alpha}(P\mathbin\Vert Q)\triangleq\frac{1}{\alpha-1}\log\left(\mathbb{E}_{X\sim Q}\left[\left(\frac{\mathrm{d}P}{\mathrm{d}Q}(X)\right)^{\alpha}\right]\right). \tag*{(79)} D α ( P ∥ Q ) ≜ α − 1 1 log ( E X ∼ Q [ ( d Q d P ( X ) ) α ] ) . (79)
Definition 12 (Sibson α \alpha α -Mutual Information). For random variables X , Y ∼ P X , Y X,Y\sim P_{X,Y} X , Y ∼ P X , Y and for any α ∈ ( 0 , 1 ) ∪ ( 1 , ∞ ) \alpha\in(0,1)\cup(1,\infty) α ∈ ( 0 , 1 ) ∪ ( 1 , ∞ ) , the Sibson α \alpha α -mutual information is defined as
I α S ( X ; Y ) ≜ inf Q Y : P Y ≪ Q Y D α ( P X , Y ∥ P X ⊗ Q Y ) . (80) I_{\alpha}^{\mathrm{S}}(X;Y)\triangleq\inf_{Q_Y:P_Y\ll Q_Y}D_{\alpha}(P_{X,Y}\mathbin\Vert P_X\otimes Q_Y). \tag*{(80)} I α S ( X ; Y ) ≜ Q Y : P Y ≪ Q Y inf D α ( P X , Y ∥ P X ⊗ Q Y ) . (80)
Proposition 10 (Properties of the Rényi functional information). Let X , Y ∼ P X , Y X,Y\sim P_{X,Y} X , Y ∼ P X , Y and α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) . Then,
(Nonnegativity) I F , α ( X → Y ) ≥ 0 I_{F,\alpha}(X\to Y)\ge0 I F , α ( X → Y ) ≥ 0 , with equality iff X ⊥ Y X\perp Y X ⊥ Y .
(Recovers I F I_F I F as α → 1 \alpha\to1 α → 1 ) If I F , α 0 ( X → Y ) < ∞ I_{F,\alpha_0}(X\to Y)<\infty I F , α 0 ( X → Y ) < ∞ for some α 0 ∈ ( 0 , 1 ) \alpha_0\in(0,1) α 0 ∈ ( 0 , 1 ) , then lim α → 1 I F , α ( X → Y ) = I F ( X → Y ) \lim_{\alpha\to1}I_{F,\alpha}(X\to Y)=I_F(X\to Y) lim α → 1 I F , α ( X → Y ) = I F ( X → Y ) .
(Self-information) For X X X discrete, I F , α ( X → X ) = H α ( X ) I_{F,\alpha}(X \to X) = H_\alpha(X) I F , α ( X → X ) = H α ( X ) , the Rényi entropy of X X X .
Proof. See Appendix E.
The Rényi functional information is connected to the Sibson α \alpha α -mutual information analogously to how functional information relates to the mutual information.
Proposition 11 (Relationship to the Sibson α \alpha α -Mutual Information). For any α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) and X , Y ∼ P X , Y X,Y \sim P_{X,Y} X , Y ∼ P X , Y such that I F , α ( X → Y ) < ∞ I_{F,\alpha}(X \to Y) < \infty I F , α ( X → Y ) < ∞ , we have
I 1 α S ( X ; Y ) ≤ I F , α ( X → Y ) . (81) I_{\frac{1}{\alpha}}^{\mathrm{S}}(X;Y) \le I_{F,\alpha}(X \to Y). \tag*{(81)} I α 1 S ( X ; Y ) ≤ I F , α ( X → Y ) . (81) Equality holds if and only if X → Y X \to Y X → Y is singular.
Proof. See Appendix E.
The Rényi functional information has an operational characterization connected to the minimum Campbell (exponential) cost of channel simulation [17 ] , [19 ] .
Definition 13 (Campbell Cost). Let t > 0 t > 0 t > 0 and let M M M be a binary message. The Campbell cost L t L_t L t of order t t t is defined as
L t ≜ 1 t log ( E [ 2 t ∣ M ∣ ] ) . (82) L_t \triangleq\frac{1}{t}\log\left(\mathbb{E}\left[2^{t|M|}\right]\right). \tag*{(82)} L t ≜ t 1 log ( E [ 2 t ∣ M ∣ ] ) . (82)
As t → 0 t \to0 t → 0 in (82) , we recover the expected message length E [ ∣ M ∣ ] \mathbb{E}[|M|] E [ ∣ M ∣ ] provided L t 0 < ∞ L_{t_0} < \infty L t 0 < ∞ for some t 0 > 0 t_0 > 0 t 0 > 0 . Campbell [17 ] showed that for a random variable V V V encoded into a uniquely decodable binary message M M M , H α ( V ) ≤ L t H_\alpha(V) \le L_t H α ( V ) ≤ L t for α = 1 1 + t \alpha= \frac{1}{1+t} α = 1 + t 1 . A suitable prefix code achieves L t < H α ( V ) + 1 L_t < H_\alpha(V) + 1 L t < H α ( V ) + 1 whenever H α ( V ) < ∞ H_\alpha(V) < \infty H α ( V ) < ∞ . This provides a Rényi generalization of Shannon’s lossless source coding theorem.
One can ask about the fundamental limits of relative entropy coding/channel simulation under the Campbell cost, for which we have the following result. Recall the definition of a stochastic code ( Z , enc , dec ) (Z,\operatorname{enc},\operatorname{dec}) ( Z , enc , dec ) for P Y ∣ X P_{Y|X} P Y ∣ X in (1).
The Campbell cost associated with such a stochastic code, as defined in (10), is
L t = 1 t log ( E [ 2 t ∣ enc ( X , Z ) ∣ ] ) , (83) L_t = \frac{1}{t}\log\left(\mathbb{E}\left[2^{t|\operatorname{enc}(X,Z)|}\right]\right), \tag*{(83)} L t = t 1 log ( E [ 2 t ∣ enc ( X , Z ) ∣ ] ) , (83)
and the minimum Campbell cost over all stochastic encoders is (as seen in (11)) given by
L t ∗ ( X → Y ) = inf ( Z , enc , dec ) L t . (84) L_t^*(X \to Y) = \inf_{(Z,\operatorname{enc},\operatorname{dec})} L_t. \tag*{(84)} L t ∗ ( X → Y ) = ( Z , enc , dec ) inf L t . (84)
The associated conditional entropy is the Arimoto-Rényi conditional entropy of order α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) [18 ]
H α A ( Y ∣ Z ) ≜ α 1 − α log E Z [ ( ∑ y P Y ∣ Z ( y ∣ Z ) α ) 1 α ] , (85) H_\alpha^{\mathrm{A}}(Y \mid Z) \triangleq\frac{\alpha}{1-\alpha}\log\mathbb{E}_Z\left[\left(\sum_y P_{Y|Z}(y \mid Z)^\alpha\right)^{\frac{1}{\alpha}}\right], \tag*{(85)} H α A ( Y ∣ Z ) ≜ 1 − α α log E Z ( y ∑ P Y ∣ Z ( y ∣ Z ) α ) α 1 , (85)
and we consider (as per (12))
R α ∗ ( X → Y ) = inf ( Z , enc , dec ) H α A ( Y ∣ Z ) = inf ( Z , f ) H α A ( Y ∣ Z ) , (86) R_\alpha^*(X \to Y) = \inf_{(Z,\operatorname{enc},\operatorname{dec})} H_\alpha^{\mathrm{A}}(Y \mid Z) = \inf_{(Z,f)} H_\alpha^{\mathrm{A}}(Y \mid Z), \tag*{(86)} R α ∗ ( X → Y ) = ( Z , enc , dec ) inf H α A ( Y ∣ Z ) = ( Z , f ) inf H α A ( Y ∣ Z ) , (86)
where ( Z , f ) (Z,f) ( Z , f ) ranges over the functional representations specified in Definition 5. It follows from [17 ] (after accounting for the side information Z Z Z ) that when α = 1 t + 1 \alpha= \frac{1}{t+1} α = t + 1 1 , these quantities are related as
R α ∗ ( X → Y ) ≤ L t ∗ ( X → Y ) ≤ R α ∗ ( X → Y ) + 1. (87) R_\alpha^*(X \to Y) \le L_t^*(X \to Y) \le R_\alpha^*(X \to Y) + 1. \tag*{(87)} R α ∗ ( X → Y ) ≤ L t ∗ ( X → Y ) ≤ R α ∗ ( X → Y ) + 1. (87)
When Z ⊥ Y Z \perp Y Z ⊥ Y , H α A ( Y ∣ Z ) = H α ( Y ) H_\alpha^{\mathrm{A}}(Y \mid Z) = H_\alpha(Y) H α A ( Y ∣ Z ) = H α ( Y ) and (87) recovers the above Rényi generalization of Shannon’s lossless coding theorem.
The next theorem is the Rényi-Campbell generalization of our main result, Theorem 1.
Theorem 3. Let X , Y X,Y X , Y be jointly distributed random variables over arbitrary Polish spaces and let α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) . Then,
I F , α ( X → Y ) ≤ R α ∗ ( X → Y ) ≤ I F , α ( X → Y ) + 1 − α α + log ( 1 / α ) 1 − α . (88) 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*{(88)} I F , α ( X → Y ) ≤ R α ∗ ( X → Y ) ≤ I F , α ( X → Y ) + α 1 − α + 1 − α log ( 1/ α ) . (88) Proof. See Appendix E. We note that the upper bound is achieved by the Poisson functional representation with any proposal Q Y Q_Y Q Y such that P Y ∣ X = x ≪ Q Y P_{Y|X=x} \ll Q_Y P Y ∣ X = x ≪ Q Y for P X P_X P X -a.e. x x x .
As α → 1 \alpha\to1 α → 1 in (14), the constant tends to log e \log e log e . For the minimum Campbell cost L t ∗ ( X → Y ) L_t^*(X \to Y) L t ∗ ( X → Y ) , the additive constant in the upper bound increases by one bit.
In [19 Cor. 2] it was shown that for any α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) and ϵ > 0 \epsilon> 0 ϵ > 0 , there exists an encoding of the Poisson functional representation satisfying
L t ≤ ( 1 + ϵ ) I 1 + ϵ ( 1 − α ) α S ( X ; Y ) + c ( α , ϵ ) , (89) L_t \le(1+\epsilon)I_{\frac{1+\epsilon(1-\alpha)}{\alpha}}^{\mathrm{S}}(X;Y) + c(\alpha,\epsilon), \tag*{(89)} L t ≤ ( 1 + ϵ ) I α 1 + ϵ ( 1 − α ) S ( X ; Y ) + c ( α , ϵ ) , (89)
where α = 1 1 + t \alpha= \frac{1}{1+t} α = 1 + t 1 and c ( α , ϵ ) c(\alpha,\epsilon) c ( α , ϵ ) is a constant. Theorem 3 provides a near-matching lower bound in terms of the Rényi functional information (and therefore, also the Sibson ( 1 / α ) (1/\alpha) ( 1/ α ) -mutual information). Theorem 3 improves on [19 ] by constructing tight upper and lower bounds. Recently, [20 ] independently defined the Rényi channel simulation divergence and proved upper and lower bounds in the problem of exact sampling. The upper bound is achieved using a layered sampling scheme with Poisson processes. However, this lower bound does not extend to all relative entropy codes like that of Theorem 3, and it is not immediately clear if the (more complex) layered sampling scheme is constant-gap optimal in our setting. In particular, one would need to construct an encoding of the index K K K which does not depend on the input X X X , which is unobservable by the decoder.
Conclusion and Open Questions
In this paper, we have introduced the functional information I F ( X → Y ) I_F(X \to Y) I F ( X → Y ) and shown that it characterizes the minimum one-shot conditional entropy cost of exact channel simulation to within log e \log e log e bits. A coding distribution adapted to the common randomness gives this upper bound for the Poisson functional representation under any dominating proposal distribution, and rejection sampling satisfies the same bound when the corresponding density ratios are uniformly bounded. These results close the logarithmic gap in earlier characterizations based on mutual information. We have also characterized perfect functional representations for finite alphabets and given a construction attaining the lower bound for every binary-output channel. For lossy compression with private encoder randomness, we have obtained bounds on the operational entropy rate, placing it within ( log e + 1 ) / n (\log e + 1)/n ( log e + 1 ) / n bits per symbol of the functional rate-distortion function at blocklength n n n . Finally, our Rényi generalization characterizes the minimum Campbell cost of channel simulation within an additive constant depending only on the Rényi order.
We believe the functional information and ring toss code have many applications in one-shot information theory, ranging from source coding to learned compression. Having established the importance of the functional information and channel simulation divergence to information theory, we would like to understand their basic properties. It is also important to practical applications to develop fast estimators of these measures, given that they often do not admit simple formulas.
AI Use Statement
AI tools (ChatGPT 5.5, 5.6, and 6) were used to simplify and correct proofs. In particular, GPT 5.5 was used to isolate the single inequality condition (31) in Theorem 4, simplify the form of Proposition 6 and construct the example in Proposition 8, and GPT 5.6 and 6 (Astra) were used to correct and simplify the proof of the key upper bound Theorem 5, originally written by the first two coauthors. All derivations and final proofs were manually verified by the authors.
Additional Proofs
Lemma 2 (Reverse Bathtub Identity). Let ( Ω , F , μ ) (\Omega,\mathcal{F},\mu) ( Ω , F , μ ) be a probability space and let f : Ω → [ 0 , ∞ ) f:\Omega\to[0,\infty) f : Ω → [ 0 , ∞ ) be integrable. Define the generalized inverse
f − 1 ( u ) ≜ sup { t ≥ 0 : μ ( { ω : f ( ω ) ≥ t } ) ≥ u } , (90) f^{-1}(u) \triangleq\sup\{t \ge0:\mu(\{\omega:f(\omega)\ge t\}) \ge u\}, \tag*{(90)} f − 1 ( u ) ≜ sup { t ≥ 0 : μ ({ ω : f ( ω ) ≥ t }) ≥ u } , (90) for 0 ≤ u ≤ 1 0 \le u \le1 0 ≤ u ≤ 1 . Then, for every 0 ≤ p ≤ 1 , 0 \le p \le1, 0 ≤ p ≤ 1 ,
sup 0 ≤ b ≤ 1 ∫ b d μ = p ∫ b f d μ = ∫ 0 p f − 1 ( u ) d u . (91) \sup_{\substack{0\le b\le1\\ \int b\,d\mu=p}} \int bf\,d\mu= \int_0^p f^{-1}(u)\,du. \tag*{(91)} 0 ≤ b ≤ 1 ∫ b d μ = p sup ∫ b f d μ = ∫ 0 p f − 1 ( u ) d u . (91)
Proof. This is a standard result; see, e.g., [24 Theorem 1.14] for the form of the maximizer. We include the proof for completeness. Let b : Ω → [ 0 , 1 ] b:\Omega\to[0,1] b : Ω → [ 0 , 1 ] be admissible. By the layer cake formula,
∫ b f d μ = ∫ 0 ∞ ∫ b ( x ) 1 [ f ( x ) ≥ t ] d μ ( x ) d t ≤ ∫ 0 ∞ min { p , μ ( f ≥ t ) } d t , \begin{aligned}
\int bf\,d\mu= \int_0^\infty\int b(x)\mathbf{1}[f(x)\ge t]\,d\mu(x)\,dt \\
&\le\int_0^\infty\min\{p,\mu(f\ge t)\}\,dt,
\end{aligned} ∫ b f d μ = ∫ 0 ∞ ∫ b ( x ) 1 [ f ( x ) ≥ t ] d μ ( x ) d t ≤ ∫ 0 ∞ min { p , μ ( f ≥ t )} d t ,
because 0 ≤ b ≤ 1 0\le b\le1 0 ≤ b ≤ 1 and 0 ≤ 1 [ f ≥ t ] 0\le\mathbf{1}[f\ge t] 0 ≤ 1 [ f ≥ t ] imply that
∫ b 1 [ f ≥ t ] d μ ≤ ∫ b d μ = p and ∫ b 1 [ f ≥ t ] d μ ≤ μ ( f ≥ t ) . \int b\mathbf{1}[f\ge t]\,d\mu\le\int b\,d\mu=p
\quad\text{and}\quad
\int b\mathbf{1}[f\ge t]\,d\mu\le\mu(f\ge t). ∫ b 1 [ f ≥ t ] d μ ≤ ∫ b d μ = p and ∫ b 1 [ f ≥ t ] d μ ≤ μ ( f ≥ t ) .
Then, we can write
∫ 0 ∞ min { p , μ ( f ≥ t ) } d t = ∫ 0 ∞ ∫ 0 p 1 [ u ≤ μ ( f ≥ t ) ] d u d t = ∫ 0 p ∫ 0 ∞ 1 [ t ≤ f − 1 ( u ) ] d t d u = ∫ 0 p f − 1 ( u ) d u . \begin{aligned}
\int_0^\infty\min\{p,\mu(f\ge t)\}\,dt
= \int_0^\infty\int_0^p \mathbf{1}[u\le\mu(f\ge t)]\,du\,dt \\
&= \int_0^p\int_0^\infty\mathbf{1}[t\le f^{-1}(u)]\,dt\,du \\
&= \int_{0}^{p} f^{-1}(u)\,du.
\end{aligned} ∫ 0 ∞ min { p , μ ( f ≥ t )} d t = ∫ 0 ∞ ∫ 0 p 1 [ u ≤ μ ( f ≥ t )] d u d t = ∫ 0 p ∫ 0 ∞ 1 [ t ≤ f − 1 ( u )] d t d u = ∫ 0 p f − 1 ( u ) d u .
We have shown that every admissible b b b satisfies
∫ b f d μ ≤ ∫ 0 p f − 1 ( u ) d u . \int bf\,d\mu\le\int_{0}^{p} f^{-1}(u)\,du. ∫ b f d μ ≤ ∫ 0 p f − 1 ( u ) d u .
All that remains is to show that this upper bound is attained. The case p = 0 p=0 p = 0 is trivially true, so assume 0 < p ≤ 1 0<p\le1 0 < p ≤ 1 and set
a = f − 1 ( p ) , A + = { f > a } , A 0 = { f = a } . a=f^{-1}(p), \qquad A_{+}=\{f>a\}, \qquad A_{0}=\{f=a\}. a = f − 1 ( p ) , A + = { f > a } , A 0 = { f = a } .
Then,
μ ( A + ) ≤ p ≤ μ ( A + ) + μ ( A 0 ) . \mu(A_{+})\le p\le\mu(A_{+})+\mu(A_{0}). μ ( A + ) ≤ p ≤ μ ( A + ) + μ ( A 0 ) .
Here the upper bound follows from μ ( f ≥ a ) ≥ p \mu(f\ge a)\ge p μ ( f ≥ a ) ≥ p . For the lower bound, if μ ( f > a ) > p \mu(f>a)>p μ ( f > a ) > p , continuity from below would imply μ ( f ≥ a + ϵ ) > p \mu(f\ge a+\epsilon)>p μ ( f ≥ a + ϵ ) > p for some ϵ > 0 \epsilon>0 ϵ > 0 , contradicting the definition of a a a .
Choose α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] so that
μ ( A + ) + α μ ( A 0 ) = p , \mu(A_{+})+\alpha\mu(A_{0})=p, μ ( A + ) + α μ ( A 0 ) = p ,
and define b p = 1 [ A + ] + α 1 [ A 0 ] b_p=\mathbf{1}[A_{+}]+\alpha\mathbf{1}[A_{0}] b p = 1 [ A + ] + α 1 [ A 0 ] . Then, 0 ≤ b p ≤ 1 0\le b_p\le1 0 ≤ b p ≤ 1 and ∫ b p d μ = p \int b_p\,d\mu=p ∫ b p d μ = p by construction. We compute
∫ 0 p f − 1 ( u ) d u = ∫ 0 ∞ min { p , μ ( f ≥ t ) } d t = a p + ∫ a ∞ μ ( f ≥ t ) d t ( μ ( f ≥ t ) < p for t > a ) = a p + ∫ ( f − a ) 1 [ A + ] d μ ( layer-cake formula ) = a ( p − μ ( A + ) ) + ∫ A + f d μ = a ( α μ ( A 0 ) ) + ∫ A + f d μ ( by the choice of α ) = α ∫ A 0 f d μ + ∫ A + f d μ ( f = a on A 0 ) = ∫ b p f d μ . \begin{aligned}
\int_{0}^{p} f^{-1}(u)\,du
&=\int_{0}^{\infty}\min\{p,\mu(f\ge t)\}\,dt\\
&=ap+\int_{a}^{\infty}\mu(f\ge t)\,dt
&&(\mu(f\ge t)<p\text{ for }t>a)\\
&=ap+\int(f-a)\mathbf{1}[A_{+}]\,d\mu
&&(\text{layer-cake formula})\\
&=a\bigl(p-\mu(A_{+})\bigr)+\int_{A_{+}}f\,d\mu\\
&=a\bigl(\alpha\mu(A_{0})\bigr)+\int_{A_{+}}f\,d\mu
&&(\text{by the choice of }\alpha)\\
&=\alpha\int_{A_{0}}f\,d\mu+\int_{A_{+}}f\,d\mu
&& (f=a\text{ on }A_{0})\\
&=\int b_pf\,d\mu.
\end{aligned} ∫ 0 p f − 1 ( u ) d u = ∫ 0 ∞ min { p , μ ( f ≥ t )} d t = a p + ∫ a ∞ μ ( f ≥ t ) d t = a p + ∫ ( f − a ) 1 [ A + ] d μ = a ( p − μ ( A + ) ) + ∫ A + f d μ = a ( α μ ( A 0 ) ) + ∫ A + f d μ = α ∫ A 0 f d μ + ∫ A + f d μ = ∫ b p f d μ . ( μ ( f ≥ t ) < p for t > a ) ( layer-cake formula ) ( by the choice of α ) ( f = a on A 0 )
Thus, the upper bound is attained by b p b_p b p .
Proof of Proposition 2. We show, more generally, that the channel simulation divergence is separately convex in P P P and Q Q Q on the domain P ≪ Q P\ll Q P ≪ Q . For w ( ℓ ) = Q ( d P d Q ≥ ℓ ) w(\ell)=Q\left(\frac{dP}{dQ}\ge\ell\right) w ( ℓ ) = Q ( d Q d P ≥ ℓ ) and w − 1 w^{-1} w − 1 its generalized inverse, we recall the representation of Lemma 2
∫ 0 p w − 1 ( u ) d u = sup 0 ≤ b ≤ 1 ∫ b d Q = p ∫ b ( x ) d P ( x ) . (92) \int_{0}^{p}w^{-1}(u)\,du=\sup_{\substack{0\le b\le1\\\int b\,dQ=p}}\int b(x)\,dP(x). \tag*{(92)} ∫ 0 p w − 1 ( u ) d u = 0 ≤ b ≤ 1 ∫ b d Q = p sup ∫ b ( x ) d P ( x ) . (92)
For p ∈ [ 0 , 1 ] p\in[0,1] p ∈ [ 0 , 1 ] , we define T ( p ) ≜ sup { ∫ b d P : 0 ≤ b ≤ 1 , ∫ b d Q = p } T(p)\triangleq\sup\left\{\int b\,dP:0\le b\le1,\ \int b\,dQ=p\right\} T ( p ) ≜ sup { ∫ b d P : 0 ≤ b ≤ 1 , ∫ b d Q = p } , writing (90) as
∫ 0 p w − 1 ( u ) d u = T ( p ) . (93) \int_{0}^{p}w^{-1}(u)\,du=T(p). \tag*{(93)} ∫ 0 p w − 1 ( u ) d u = T ( p ) . (93)
Since ∫ 0 1 w − 1 ( u ) d u = 1 \int_{0}^{1}w^{-1}(u)\,du=1 ∫ 0 1 w − 1 ( u ) d u = 1 , T T T is continuous and nondecreasing on [ 0 , 1 ] [0,1] [ 0 , 1 ] , with T ( 0 ) = 0 T(0)=0 T ( 0 ) = 0 and T ( 1 ) = 1 T(1)=1 T ( 1 ) = 1 . For fixed Q Q Q , T ( p ) T(p) T ( p ) is a supremum of linear functions of P P P over a constraint set that does not involve P P P . Therefore, T ( p ) T(p) T ( p ) is convex in P P P for a fixed Q Q Q . Using the representation
D C S ( P ∥ Q ) ⋅ ln 2 = − 1 + ∫ 0 1 T ( p ) p d p (94) D_{\mathrm{CS}}(P\mathbin{\|}Q)\cdot\ln2=-1+\int_{0}^{1}\frac{T(p)}{p}\,dp \tag*{(94)} D CS ( P ∥ Q ) ⋅ ln 2 = − 1 + ∫ 0 1 p T ( p ) d p (94)
recalled in (26) and [7 Lem. 3.1.2, item 2] , we conclude that D C S ( ⋅ ∥ Q ) D_{\mathrm{CS}}(\cdot\mathbin{\|}Q) D CS ( ⋅ ∥ Q ) is convex in P P P , since integration preserves convexity. For a fixed P P P and a ∈ [ 0 , 1 ] a\in[0,1] a ∈ [ 0 , 1 ] , define the generalized inverse T − 1 ( a ) = inf { p ∈ [ 0 , 1 ] : T ( p ) ≥ a } T^{-1}(a)=\inf\{p\in[0,1]:T(p)\ge a\} T − 1 ( a ) = inf { p ∈ [ 0 , 1 ] : T ( p ) ≥ a } . By continuity and monotonicity of T T T , T − 1 ( a ) ≤ p T^{-1}(a)\le p T − 1 ( a ) ≤ p if and only if a ≤ T ( p ) a\le T(p) a ≤ T ( p ) . Hence,
D C S ( P ∥ Q ) ⋅ ln 2 + 1 = ∫ 0 1 T ( p ) p d p = ∫ 0 1 1 p ∫ 0 1 1 [ T − 1 ( a ) ≤ p ] d a d p = ∫ 0 1 ∫ T − 1 ( a ) 1 1 p d p d a = ∫ 0 1 − ln T − 1 ( a ) d a . \begin{aligned}
D_{\mathrm{CS}}(P\mathbin{\|}Q)\cdot\ln2+1=\int_{0}^{1}\frac{T(p)}{p}\,dp
=\int_{0}^{1}\frac{1}{p}\int_{0}^{1}\mathbf{1}[T^{-1}(a)\le p]\,da\,dp \\
&= \int_0^1 \int_{T^{-1}(a)}^1 \frac{1}{p}\,dp\,da \\
&= \int_0^1 -\ln T^{-1}(a)\,da.
\end{aligned} D CS ( P ∥ Q ) ⋅ ln 2 + 1 = ∫ 0 1 p T ( p ) d p = ∫ 0 1 p 1 ∫ 0 1 1 [ T − 1 ( a ) ≤ p ] d a d p = ∫ 0 1 ∫ T − 1 ( a ) 1 p 1 d p d a = ∫ 0 1 − ln T − 1 ( a ) d a .
Note that we may write
T − 1 ( a ) = inf { ∫ b d Q : 0 ≤ b < 1 , ∫ b d P ≥ a } (95) T^{-1}(a)=\inf\left\{\int b\,dQ:0\le b<1,\ \int b\,dP\ge a\right\} \tag*{(95)} T − 1 ( a ) = inf { ∫ b d Q : 0 ≤ b < 1 , ∫ b d P ≥ a } (95)
Indeed, any admissible b b b satisfies ∫ b d P ≤ T ( ∫ b d Q ) \int b\,dP\le T(\int b\,dQ) ∫ b d P ≤ T ( ∫ b d Q ) , so ∫ b d Q ≥ T − 1 ( a ) \int b\,dQ\ge T^{-1}(a) ∫ b d Q ≥ T − 1 ( a ) . Conversely, the maximizer in Lemma 2 at p = T − 1 ( a ) p=T^{-1}(a) p = T − 1 ( a ) satisfies ∫ b d Q = T − 1 ( a ) \int b\,dQ=T^{-1}(a) ∫ b d Q = T − 1 ( a ) and ∫ b d P = T ( T − 1 ( a ) ) ≥ a \int b\,dP=T(T^{-1}(a))\ge a ∫ b d P = T ( T − 1 ( a )) ≥ a . For each fixed a ∈ ( 0 , 1 ] a\in(0,1] a ∈ ( 0 , 1 ] , and a fixed b b b , ∫ b d Q \int b\,dQ ∫ b d Q is linear in Q Q Q . As the constraint set does not depend on Q Q Q , T − 1 ( a ) T^{-1}(a) T − 1 ( a ) is therefore concave in Q Q Q . As − ln -\ln − ln is convex and decreasing, − ln T − 1 ( a ) -\ln T^{-1}(a) − ln T − 1 ( a ) is convex in Q Q Q ; integrating over a a a preserves convexity and hence, D C S ( P ∥ ⋅ ) D_{\mathrm{CS}}(P\parallel\cdot) D CS ( P ∥ ⋅ ) is convex in Q Q Q .
Proof of Proposition 3. Recall that I F ( X → Y ) = D C S ( P X ∣ Y ∥ P X ∣ P Y ) I_{\mathrm{F}}(X\to Y)=D_{\mathrm{CS}}(P_{X|Y}\parallel P_X\mid P_Y) I F ( X → Y ) = D CS ( P X ∣ Y ∥ P X ∣ P Y ) . Then, from the lower bound in Proposition 1 we immediately get
I F ( X → Y ) = D C S ( P X ∣ Y ∥ P X ∣ P Y ) ≥ D K L ( P X ∣ Y ∥ P X ∣ P Y ) = I ( X ; Y ) . \begin{aligned}
I_{\mathrm{F}}(X\to Y)&=D_{\mathrm{CS}}(P_{X|Y}\parallel P_X\mid P_Y)\\
&\ge D_{\mathrm{KL}}(P_{X|Y}\parallel P_X\mid P_Y)\\
&=I(X;Y).
\end{aligned} I F ( X → Y ) = D CS ( P X ∣ Y ∥ P X ∣ P Y ) ≥ D KL ( P X ∣ Y ∥ P X ∣ P Y ) = I ( X ; Y ) .
Next, from the upper bound in Proposition 1, we get
I F ( X → Y ) = D C S ( P X ∣ Y ∥ P X ∣ P Y ) ≤ E Y [ D K L ( P X ∣ Y ∥ P X ) + log ( D K L ( P X ∣ Y ∥ P X ) + 1 ) + 1 ] ≤ I ( X ; Y ) + log ( I ( X ; Y ) + 1 ) + 1. \begin{aligned}
I_{\mathrm{F}}(X\to Y)&=D_{\mathrm{CS}}(P_{X|Y}\parallel P_X\mid P_Y)\\
&\le\mathbb{E}_Y\left[D_{\mathrm{KL}}(P_{X|Y}\parallel P_X)\right.\\
&\qquad\left.+\log(D_{\mathrm{KL}}(P_{X|Y}\parallel P_X)+1)+1\right]\\
&\le I(X;Y)+\log(I(X;Y)+1)+1.
\end{aligned} I F ( X → Y ) = D CS ( P X ∣ Y ∥ P X ∣ P Y ) ≤ E Y [ D KL ( P X ∣ Y ∥ P X ) + log ( D KL ( P X ∣ Y ∥ P X ) + 1 ) + 1 ] ≤ I ( X ; Y ) + log ( I ( X ; Y ) + 1 ) + 1.
(Jensen)
For the equality condition in the lower bound, since I ( X ; Y ) < ∞ I(X;Y)<\infty I ( X ; Y ) < ∞ , equality holds if and only if the conditional lower bound is an equality for P Y P_Y P Y -a.e. y y y . Recalling that
w y ( h ) = P X ( d P X ∣ Y = y d P X ≥ h ) (96) w_y(h)=P_X\left(\frac{dP_{X|Y=y}}{dP_X}\ge h\right) \tag*{(96)} w y ( h ) = P X ( d P X d P X ∣ Y = y ≥ h ) (96)
the proof of Proposition 1 in [21 ] shows that the conditional lower bound is an equality if and only if
∫ 0 h w y ( ℓ ) d ℓ ≥ h w y ( h ) \int_0^h w_y(\ell)\,d\ell\ge h w_y(h) ∫ 0 h w y ( ℓ ) d ℓ ≥ h w y ( h )
holds with equality for w y ( h ) d h w_y(h)\,dh w y ( h ) d h -a.e. h h h . Since w y w_y w y is nonnegative, nonincreasing, and integrates to one, this holds if and only if, for some g ( y ) ∈ [ 1 , ∞ ) g(y)\in[1,\infty) g ( y ) ∈ [ 1 , ∞ ) ,
w y ( h ) = 1 g ( y ) 1 [ 0 < h ≤ g ( y ) ] for a.e. h > 0. w_y(h)=\frac{1}{g(y)}\mathbf{1}[0<h\le g(y)]\quad\text{for a.e. }h>0. w y ( h ) = g ( y ) 1 1 [ 0 < h ≤ g ( y )] for a.e. h > 0.
Indeed, equality at h h h forces w y ( ℓ ) = w y ( h ) w_y(\ell)=w_y(h) w y ( ℓ ) = w y ( h ) for a.e. ℓ ∈ ( 0 , h ) \ell\in(0,h) ℓ ∈ ( 0 , h ) . The displayed form of w y w_y w y is equivalent to d P X ∣ Y = y d P X ( x ) ∈ { 0 , g ( y ) } \frac{dP_{X|Y=y}}{dP_X}(x)\in\{0,g(y)\} d P X d P X ∣ Y = y ( x ) ∈ { 0 , g ( y )} for P X P_X P X -a.e. x x x , or, equivalently, d P X ∣ Y = y d P X ( x ) = g ( y ) \frac{dP_{X|Y=y}}{dP_X}(x)=g(y) d P X d P X ∣ Y = y ( x ) = g ( y ) for P X ∣ Y = y P_{X|Y=y} P X ∣ Y = y -a.e. x x x . Finally, d P X ∣ Y d P X ( x ∣ y ) = d P Y ∣ X d P Y ( y ∣ x ) \frac{dP_{X|Y}}{dP_X}(x\mid y)=\frac{dP_{Y|X}}{dP_Y}(y\mid x) d P X d P X ∣ Y ( x ∣ y ) = d P Y d P Y ∣ X ( y ∣ x ) for P X , Y P_{X,Y} P X , Y -a.e. ( x , y ) (x,y) ( x , y ) , so the equality condition is precisely that X → Y X\to Y X → Y is singular.
Proof of Proposition 4. By the Markov property, P X ∣ Z = E [ P X ∣ Y ∣ Z ] P_{X|Z}=\mathbb{E}[P_{X|Y}\mid Z] P X ∣ Z = E [ P X ∣ Y ∣ Z ] , where the conditional expectation is understood setwise. Thus,
I F ( X → Z ) = D C S ( P X ∣ Z ∥ P X ∣ P Z ) = D C S ( E [ P X ∣ Y ∣ Z ] ∥ P X ∣ P Z ) ≤ D C S ( P X ∣ Y ∥ P X ∣ P Y , Z ) = D C S ( P X ∣ Y ∥ P X ∣ P Y ) = I F ( X → Y ) . \begin{aligned}
I_{\mathrm{F}}(X\to Z)&=D_{\mathrm{CS}}(P_{X|Z}\parallel P_X\mid P_Z)\\
&=D_{\mathrm{CS}}(\mathbb{E}[P_{X|Y}\mid Z]\parallel P_X\mid P_Z)\\
&\le D_{\mathrm{CS}}(P_{X|Y}\parallel P_X\mid P_{Y,Z})\\
&=D_{\mathrm{CS}}(P_{X|Y}\parallel P_X\mid P_Y)\\
&=I_{\mathrm{F}}(X\to Y).
\end{aligned} I F ( X → Z ) = D CS ( P X ∣ Z ∥ P X ∣ P Z ) = D CS ( E [ P X ∣ Y ∣ Z ] ∥ P X ∣ P Z ) ≤ D CS ( P X ∣ Y ∥ P X ∣ P Y , Z ) = D CS ( P X ∣ Y ∥ P X ∣ P Y ) = I F ( X → Y ) .
(Markov structure)
(Proposition 2)
Proof of Proposition 5. Concavity in P X P_X P X . Let p ∈ ( 0 , 1 ) p\in(0,1) p ∈ ( 0 , 1 ) , set p ˉ = 1 − p \bar{p}=1-p p ˉ = 1 − p for convenience and let θ ∼ Bern ( p ) \theta\sim\operatorname{Bern}(p) θ ∼ Bern ( p ) . The cases p = 0 p=0 p = 0 and p = 1 p=1 p = 1 are immediate. Now, for two distributions P 0 , P 1 P_0,P_1 P 0 , P 1 over X X X , let X ∣ θ ∼ P θ X\mid\theta\sim P_\theta X ∣ θ ∼ P θ . For j ∈ { 0 , 1 } j\in\{0,1\} j ∈ { 0 , 1 } , let ( X j , Y j ) (X_j,Y_j) ( X j , Y j ) have source distribution P j P_j P j and channel P Y ∣ X P_{Y|X} P Y ∣ X . Now, note that θ → X → Y \theta\to X\to Y θ → X → Y is a Markov chain. Therefore,
I F ( θ , X → Y ) = D C S ( P θ , X ∣ Y ∥ P θ , X ∣ P Y ) = D C S ( P θ ∣ X P X ∣ Y ∥ P θ ∣ X P X ∣ P Y ) . \begin{aligned}
I_{\mathrm{F}}(\theta,X\to Y)&=D_{\mathrm{CS}}(P_{\theta,X|Y}\parallel P_{\theta,X}\mid P_Y)\\
&=D_{\mathrm{CS}}(P_{\theta|X}P_{X|Y}\parallel P_{\theta|X}P_X\mid P_Y).
\end{aligned} I F ( θ , X → Y ) = D CS ( P θ , X ∣ Y ∥ P θ , X ∣ P Y ) = D CS ( P θ ∣ X P X ∣ Y ∥ P θ ∣ X P X ∣ P Y ) .
( θ ⊥ Y ∣ X \theta\perp Y\mid X θ ⊥ Y ∣ X )
= D C S ( P X ∣ Y ∥ P X ∣ P Y ) = I F ( X → Y ) , (97) \begin{aligned}
=D_{\mathrm{CS}}(P_{X|Y}\parallel P_X\mid P_Y) \\
&=I_F(X\to Y), \tag*{(97)}
\end{aligned} = D CS ( P X ∣ Y ∥ P X ∣ P Y ) = I F ( X → Y ) , (97)
where (95) holds because
P θ , X ∼ P θ , X ( d P θ , X ∣ Y d P θ , X ( θ , X ∣ y ) ≥ ℓ ) = P θ , X ∼ P θ , X ( d P X ∣ Y d P X ( X ∣ y ) ≥ ℓ ) = w y ( ℓ ) . \begin{aligned}
\mathbb{P}_{\theta,X\sim P_{\theta,X}}\left(\frac{dP_{\theta,X|Y}}{dP_{\theta,X}}(\theta,X\mid y)\ge\ell\right) \\
&=\mathbb{P}_{\theta,X\sim P_{\theta,X}}\left(\frac{dP_{X|Y}}{dP_X}(X\mid y)\ge\ell\right) \\
&=w_y(\ell).
\end{aligned} P θ , X ∼ P θ , X ( d P θ , X d P θ , X ∣ Y ( θ , X ∣ y ) ≥ ℓ ) = P θ , X ∼ P θ , X ( d P X d P X ∣ Y ( X ∣ y ) ≥ ℓ ) = w y ( ℓ ) .
For j ∈ { 0 , 1 } j\in\{0,1\} j ∈ { 0 , 1 } , put c j ( y ) = d P Y j d P Y ( y ) c_j(y)=\frac{dP_{Y_j}}{dP_Y}(y) c j ( y ) = d P Y d P Y j ( y ) , which exists since P Y = p ˉ P Y 0 + p P Y 1 P_Y=\bar pP_{Y_0}+pP_{Y_1} P Y = p ˉ P Y 0 + p P Y 1 . The chain rule gives, for P Y P_Y P Y -a.e. y y y and P θ , X P_{\theta,X} P θ , X -a.e. ( θ , x ) (\theta,x) ( θ , x ) ,
d P θ , X ∣ Y d P θ , X ( θ , x ∣ y ) = c θ ( y ) d P X ∣ Y , θ d P X ∣ θ ( x ∣ y , θ ) , \frac{dP_{\theta,X|Y}}{dP_{\theta,X}}(\theta,x\mid y)
=c_\theta(y)\frac{dP_{X|Y,\theta}}{dP_{X|\theta}}(x\mid y,\theta), d P θ , X d P θ , X ∣ Y ( θ , x ∣ y ) = c θ ( y ) d P X ∣ θ d P X ∣ Y , θ ( x ∣ y , θ ) ,
where the right-hand side is taken as zero when c θ ( y ) = 0 c_\theta(y)=0 c θ ( y ) = 0 . Thus, for h > 0 h>0 h > 0 ,
w y ( h ) = P θ , X ( d P θ , X ∣ Y d P θ , X ( ⋅ ∣ y ) ≥ h ) = P θ , X ( c θ ( y ) d P X ∣ Y , θ d P X ∣ θ ( ⋅ ∣ y , ⋅ ) ≥ h ) = E θ [ w y , θ ( h / c θ ( y ) ) ] , \begin{aligned}
w_y(h)=P_{\theta,X}\left(\frac{dP_{\theta,X|Y}}{dP_{\theta,X}}(\cdot\mid y)\ge h\right) \\
&=P_{\theta,X}\left(c_\theta(y)\frac{dP_{X|Y,\theta}}{dP_{X|\theta}}(\cdot\mid y,\cdot)\ge h\right) \\
&=\mathbb{E}_\theta[w_{y,\theta}(h/c_\theta(y))],
\end{aligned} w y ( h ) = P θ , X ( d P θ , X d P θ , X ∣ Y ( ⋅ ∣ y ) ≥ h ) = P θ , X ( c θ ( y ) d P X ∣ θ d P X ∣ Y , θ ( ⋅ ∣ y , ⋅ ) ≥ h ) = E θ [ w y , θ ( h / c θ ( y ))] ,
where w y , j ( h ) = P j ( d P X j ∣ Y j = y d P j ≥ h ) w_{y,j}(h)=P_j\left(\frac{dP_{X_j|Y_j=y}}{dP_j}\ge h\right) w y , j ( h ) = P j ( d P j d P X j ∣ Y j = y ≥ h ) . For c j ( y ) = 0 c_j(y)=0 c j ( y ) = 0 , interpret w y , j ( h / c j ( y ) ) w_{y,j}(h/c_j(y)) w y , j ( h / c j ( y )) and c j ( y ) h ( w y , j ) c_j(y)h(w_{y,j}) c j ( y ) h ( w y , j ) as zero. From this, via the differential entropy definition of the functional information, we get that
I F ( θ , X → Y ) = E Y [ h ( w Y ) ] ≥ E θ [ E Y [ c θ ( Y ) h ( w Y , θ ) ] ] \begin{aligned}
I_F(\theta,X\to Y)=\mathbb{E}_Y[h(w_Y)] \\
&\ge\mathbb{E}_\theta[\mathbb{E}_Y[c_\theta(Y)h(w_{Y,\theta})]]
\end{aligned} I F ( θ , X → Y ) = E Y [ h ( w Y )] ≥ E θ [ E Y [ c θ ( Y ) h ( w Y , θ )]]
(concavity of h ( ⋅ ) h(\cdot) h ( ⋅ ) )
= p ˉ I F ( X 0 → Y 0 ) + p I F ( X 1 → Y 1 ) . =\bar pI_F(X_0\to Y_0)+pI_F(X_1\to Y_1). = p ˉ I F ( X 0 → Y 0 ) + p I F ( X 1 → Y 1 ) .
The last equality uses c j ( y ) d P Y ( y ) = d P Y j ( y ) c_j(y)dP_Y(y)=dP_{Y_j}(y) c j ( y ) d P Y ( y ) = d P Y j ( y ) . Putting everything together, we have shown that
I F ( X → Y ) ≥ p ˉ I F ( X 0 → Y 0 ) + p I F ( X 1 → Y 1 ) , I_F(X\to Y)\ge\bar pI_F(X_0\to Y_0)+pI_F(X_1\to Y_1), I F ( X → Y ) ≥ p ˉ I F ( X 0 → Y 0 ) + p I F ( X 1 → Y 1 ) ,
where P X = p ˉ P 0 + p P 1 P_X=\bar pP_0+pP_1 P X = p ˉ P 0 + p P 1 , as desired.
Convexity in P Y ∣ X P_{Y|X} P Y ∣ X . Let p ∈ [ 0 , 1 ] p\in[0,1] p ∈ [ 0 , 1 ] , set p ˉ = 1 − p \bar p=1-p p ˉ = 1 − p for convenience and let θ ∼ Bern ( p ) \theta\sim\operatorname{Bern}(p) θ ∼ Bern ( p ) be independent of X X X . Now, for two Markov kernels P 0 ( x ) , P 1 ( x ) P_0(x),P_1(x) P 0 ( x ) , P 1 ( x ) over Y \mathcal{Y} Y , let Y ∣ X , θ ∼ P θ ( X ) Y\mid X,\theta\sim P_\theta(X) Y ∣ X , θ ∼ P θ ( X ) . For j ∈ { 0 , 1 } j\in\{0,1\} j ∈ { 0 , 1 } , let Y j ∣ X ∼ P j ( X ) Y_j\mid X\sim P_j(X) Y j ∣ X ∼ P j ( X ) . Since P X ∣ Y = E [ P X ∣ Y , θ ∣ Y ] P_{X|Y}=\mathbb{E}[P_{X|Y,\theta}\mid Y] P X ∣ Y = E [ P X ∣ Y , θ ∣ Y ] , we have
p ˉ I F ( X → Y 0 ) + p I F ( X → Y 1 ) = D C S ( P X ∣ Y , θ ∥ P X ∣ θ ∣ P Y , θ ) = D C S ( P X ∣ Y , θ ∥ P X ∣ P Y , θ ) \begin{aligned}
\bar pI_F(X\to Y_0)+pI_F(X\to Y_1)
=D_{\mathrm{CS}}(P_{X|Y,\theta}\parallel P_{X|\theta}\mid P_{Y,\theta}) \\
&=D_{\mathrm{CS}}(P_{X|Y,\theta}\parallel P_X\mid P_{Y,\theta})
\end{aligned} p ˉ I F ( X → Y 0 ) + p I F ( X → Y 1 ) = D CS ( P X ∣ Y , θ ∥ P X ∣ θ ∣ P Y , θ ) = D CS ( P X ∣ Y , θ ∥ P X ∣ P Y , θ )
( X ⊥ θ ) (X\perp\theta) ( X ⊥ θ )
≥ D C S ( P X ∣ Y ∥ P X ∣ P Y ) \ge D_{\mathrm{CS}}(P_{X|Y}\parallel P_X\mid P_Y) ≥ D CS ( P X ∣ Y ∥ P X ∣ P Y )
(Proposition 2)
= I F ( X → Y ) . =I_F(X\to Y). = I F ( X → Y ) .
□ \square □
Proof of Proposition 9. We use the following lemma.
Lemma 3 (Piecewise linearity and polyhedral convexity). Let X = { 1 , … , n } \mathcal{X}=\{1,\ldots,n\} X = { 1 , … , n } and Y = { 1 , … , m } \mathcal{Y}=\{1,\ldots,m\} Y = { 1 , … , m } , and fix X ∼ P X X\sim P_X X ∼ P X . Identify P Y ∣ X P_{Y|X} P Y ∣ X with its channel matrix K = ( K i y ) K=(K_{iy}) K = ( K i y ) , where K i y = P Y ∣ X ( y ∣ i ) K_{iy}=P_{Y|X}(y\mid i) K i y = P Y ∣ X ( y ∣ i ) , in the polytope
K ≜ { K ∈ R n × m : K i y ≥ 0 , ∑ y = 1 m K i y = 1 , i = 1 , … , n } . \mathcal{K}\triangleq\left\{K\in\mathbb{R}^{n\times m}:K_{iy}\ge0,\ \sum_{y=1}^{m}K_{iy}=1,\ i=1,\ldots,n\right\}. K ≜ { K ∈ R n × m : K i y ≥ 0 , y = 1 ∑ m K i y = 1 , i = 1 , … , n } . Then K ↦ I F ( X → Y ) K\mapsto I_F(X\to Y) K ↦ I F ( X → Y ) is continuous and piecewise linear on K \mathcal{K} K : there is a finite covering of K \mathcal{K} K by closed polyhedral cells on each of which I F ( X → Y ) I_F(X\to Y) I F ( X → Y ) is a linear function of K K K . Its extension by + ∞ +\infty + ∞ outside K \mathcal{K} K is proper polyhedral convex, meaning that its epigraph is a polyhedron.
Proof of Lemma 3. Put p i = P X ( i ) p_i=P_X(i) p i = P X ( i ) and η ( s ) = − s log s \eta(s)=-s\log s η ( s ) = − s log s for s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] , with 0 log 0 = 0 0\log0=0 0 log 0 = 0 , and define
q y ≜ ∑ i = 1 n p i K i y , v y ( t ) ≜ ∑ i = 1 n p i 1 [ K i y ≥ t ] . (98) q_y\triangleq\sum_{i=1}^{n}p_iK_{iy},\qquad
v_y(t)\triangleq\sum_{i=1}^{n}p_i\mathbf{1}[K_{iy}\ge t]. \tag*{(98)} q y ≜ i = 1 ∑ n p i K i y , v y ( t ) ≜ i = 1 ∑ n p i 1 [ K i y ≥ t ] . (98)
For q y > 0 q_y>0 q y > 0 , the width function of P X ∣ Y = y P_{X\mid Y=y} P X ∣ Y = y relative to P X P_X P X is w y ( ℓ ) = v y ( q y ℓ ) w_y(\ell)=v_y(q_y\ell) w y ( ℓ ) = v y ( q y ℓ ) . The definition of functional information and the substitution t = q y ℓ t=q_y\ell t = q y ℓ therefore give
I F ( X → Y ) = ∑ y : q y > 0 q y ∫ 0 ∞ η ( w y ( ℓ ) ) d ℓ = ∑ y = 1 m ∫ 0 1 η ( v y ( t ) ) d t . (99) I_F(X\to Y)=\sum_{y:q_y>0}q_y\int_0^\infty\eta(w_y(\ell))\,d\ell
=\sum_{y=1}^{m}\int_0^1\eta(v_y(t))\,dt. \tag*{(99)} I F ( X → Y ) = y : q y > 0 ∑ q y ∫ 0 ∞ η ( w y ( ℓ )) d ℓ = y = 1 ∑ m ∫ 0 1 η ( v y ( t )) d t . (99)
Indeed, v y ( t ) = 0 v_y(t)=0 v y ( t ) = 0 for t > 1 t>1 t > 1 ; if q y = 0 q_y=0 q y = 0 , then v y ( t ) = 0 v_y(t)=0 v y ( t ) = 0 for every t > 0 t>0 t > 0 , so that output contributes zero.
For each y ∈ Y y\in\mathcal{Y} y ∈ Y , choose a permutation π y \pi_y π y of X \mathcal{X} X such that, writing k y , i ≜ K π y ( i ) , y k_{y,i}\triangleq K_{\pi_y(i),y} k y , i ≜ K π y ( i ) , y ,
k y , 1 ≥ ⋯ ≥ k y , n , k_{y,1}\ge\cdots\ge k_{y,n}, k y , 1 ≥ ⋯ ≥ k y , n ,
and put
k y , n + 1 = 0 , S y , 0 = 0 , S y , i ≜ ∑ j = 1 i p π y ( j ) . k_{y,n+1}=0,\qquad S_{y,0}=0,\qquad S_{y,i}\triangleq\sum_{j=1}^{i}p_{\pi_y(j)}. k y , n + 1 = 0 , S y , 0 = 0 , S y , i ≜ j = 1 ∑ i p π y ( j ) .
On each nonempty interval k y , i + 1 < t < k y , i k_{y,i+1}<t<k_{y,i} k y , i + 1 < t < k y , i , we have v y ( t ) = S y , i v_y(t)=S_{y,i} v y ( t ) = S y , i . Consequently,
I F ( X → Y ) = ∑ y = 1 m ∑ i = 1 n ( k y , i − k y , i + 1 ) η ( S y , i ) (100) I_F(X\to Y)=\sum_{y=1}^{m}\sum_{i=1}^{n}(k_{y,i}-k_{y,i+1})\eta(S_{y,i}) \tag*{(100)} I F ( X → Y ) = y = 1 ∑ m i = 1 ∑ n ( k y , i − k y , i + 1 ) η ( S y , i ) (100)
= ∑ y = 1 m ∑ i = 1 n K π y ( i ) , y [ η ( S y , i ) − η ( S y , i − 1 ) ] . (101) =\sum_{y=1}^{m}\sum_{i=1}^{n}K_{\pi_y(i),y}\left[\eta(S_{y,i})-\eta(S_{y,i-1})\right]. \tag*{(101)} = y = 1 ∑ m i = 1 ∑ n K π y ( i ) , y [ η ( S y , i ) − η ( S y , i − 1 ) ] . (101)
For a fixed tuple Π = ( π 1 , … , π m ) \Pi=(\pi_1,\ldots,\pi_m) Π = ( π 1 , … , π m ) , the last expression is a linear function L Π ( K ) L_\Pi(K) L Π ( K ) , valid on the closed polyhedral cell
C Π ≜ { K ∈ K : K π y ( 1 ) , y ≥ ⋯ ≥ K π y ( n ) , y for every y ∈ Y } . C_\Pi\triangleq\left\{K\in\mathcal{K}:K_{\pi_y(1),y}\ge\cdots\ge K_{\pi_y(n),y}\text{ for every }y\in\mathcal{Y}\right\}. C Π ≜ { K ∈ K : K π y ( 1 ) , y ≥ ⋯ ≥ K π y ( n ) , y for every y ∈ Y } .
These at most ( n ! ) m (n!)^m ( n ! ) m cells cover K \mathcal{K} K . Ties cause no difficulty, since the corresponding intervals in (97) have zero length. The linear formulas agree on overlapping cells, since each equals (96). The finite closed covering therefore also proves continuity on K \mathcal{K} K .
By Proposition 5, the map K ↦ I F ( X → Y ) K\mapsto I_F(X\to Y) K ↦ I F ( X → Y ) is convex on K \mathcal{K} K . Its extension by + ∞ +\infty + ∞ outside K \mathcal{K} K is thus proper, convex, and piecewise affine on its effective domain. By [40 Theorem 2.49] , its epigraph is a polyhedron, proving the final assertion.
Use the notation of Lemma 3 and write
d ( K ) ≜ ∑ i = 1 n ∑ y = 1 m P X ( i ) K i y Δ ( i , y ) . d(K)\triangleq\sum_{i=1}^{n}\sum_{y=1}^{m}P_X(i)K_{iy}\Delta(i,y). d ( K ) ≜ i = 1 ∑ n y = 1 ∑ m P X ( i ) K i y Δ ( i , y ) .
For every feasible D D D , the set { K ∈ K : d ( K ) ≤ D } \{K\in\mathcal{K}:d(K)\le D\} { K ∈ K : d ( K ) ≤ D } is compact. By Lemma 3, I F ( X → Y ) I_F(X\to Y) I F ( X → Y ) is finite and continuous in K K K , so the infimum defining R F ( D ) R_F(D) R F ( D ) is attained. As usual, set R F ( D ) = + ∞ R_F(D)=+\infty R F ( D ) = + ∞ when the constraint is infeasible. Feasible distortion levels exist because Δ \Delta Δ is finite on the finite alphabets.
By the same lemma, the epigraph
E ≜ { ( K , t ) ∈ K × R : I F ( X → Y ) ≤ t } \mathcal{E}\triangleq\{(K,t)\in\mathcal{K}\times\mathbb{R}:I_F(X\to Y)\le t\} E ≜ {( K , t ) ∈ K × R : I F ( X → Y ) ≤ t }
is a polyhedron, where the joint distribution of ( X , Y ) (X,Y) ( X , Y ) is determined by P X P_X P X and K K K . Since d ( K ) d(K) d ( K ) is linear, the set
P ≜ { ( K , D , t ) : ( K , t ) ∈ E , d ( K ) ≤ D } \mathcal{P}\triangleq\{(K,D,t):(K,t)\in\mathcal{E},\ d(K)\le D\} P ≜ {( K , D , t ) : ( K , t ) ∈ E , d ( K ) ≤ D }
is also a polyhedron, being the intersection of a polyhedral cylinder and a closed half-space. Attainment of the minimum gives
epi R F = { ( D , t ) : there exists K with ( K , D , t ) ∈ P } . (102) \operatorname{epi}R_F=\{(D,t):\text{ there exists }K\text{ with }(K,D,t)\in\mathcal{P}\}. \tag*{(102)} epi R F = {( D , t ) : there exists K with ( K , D , t ) ∈ P } . (102)
A linear projection of a polyhedron is a polyhedron [40 Proposition 3.55(a)] . Thus R F R_F R F is proper polyhedral convex, and [40 Theorem 2.49] gives finitely many real coefficients a j , b j a_j,b_j a j , b j such that
R F ( D ) = max 1 ≤ j ≤ M ( a j D + b j ) R_F(D)=\max_{1\le j\le M}(a_jD+b_j) R F ( D ) = 1 ≤ j ≤ M max ( a j D + b j )
on its domain [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) . This proves piecewise affinity with finitely many pieces, which is the meaning of piecewise linearity in the proposition. The displayed representation also proves continuity on this domain, including right continuity at 0 0 0 ; the nonincreasing property follows from nesting of the feasible sets.
Perfect Functional Representations
In this appendix, we will provide proofs of the results in § 4 . We first explicitly state the condition on a functional representation ( Z , f ) (Z,f) ( Z , f ) for it to be perfect.
Lemma 4. Let X , Y ∼ P X , Y X,Y\sim P_{X,Y} X , Y ∼ P X , Y with I ( X ; Y ) < ∞ I(X;Y)<\infty I ( X ; Y ) < ∞ , and let Z ⊥ X Z\perp X Z ⊥ X be such that Y = f ( X , Z ) Y=f(X,Z) Y = f ( X , Z ) for a measurable f f f and P Y ∣ Z = z P_{Y\mid Z=z} P Y ∣ Z = z is purely atomic for P Z P_Z P Z -a.e. z z z . Let ν y \nu_y ν y be a regular conditional distribution of Z Z Z given Y = y Y=y Y = y , and put q y ( z ) = P Y ∣ Z = z ( { y } ) q_y(z)=P_{Y\mid Z=z}(\{y\}) q y ( z ) = P Y ∣ Z = z ({ y }) , as in the proof of Theorem 4. The representation ( Z , f ) (Z,f) ( Z , f ) is perfect if and only if, for P Y P_Y P Y -a.e. y y y , there exists a measurable family of bathtub maximizers b y , p : X → [ 0 , 1 ] b_{y,p}:\mathcal{X}\to[0,1] b y , p : X → [ 0 , 1 ] , p ∈ ( 0 , 1 ) p\in(0,1) p ∈ ( 0 , 1 ) , for r ( y ∣ ⋅ ) r(y\mid\cdot) r ( y ∣ ⋅ ) under the constraint ∫ b y , p d P X = p \int b_{y,p}\,\mathrm{d}P_X=p ∫ b y , p d P X = p , as in Lemma 2, such that, for d p ⊗ ν y \mathrm{d}p\otimes\nu_y d p ⊗ ν y -a.e. ( p , z ) (p,z) ( p , z ) ,
∫ X b y , p ( x ) 1 [ f ( x , z ) = y ] d P X ( x ) = min { p , q y ( z ) } . (103) \int_{\mathcal{X}} b_{y,p}(x)\mathbf{1}[f(x,z)=y]\,\mathrm{d}P_X(x)=\min\{p,q_y(z)\}. \tag*{(103)} ∫ X b y , p ( x ) 1 [ f ( x , z ) = y ] d P X ( x ) = min { p , q y ( z )} . (103)
Proof. This condition follows immediately from the inequality (29) in the proof of Theorem 4.
Proof of Proposition 6. Recall the standing assumptions P X ( x ) > 0 P_X(x)>0 P X ( x ) > 0 and P Y ( y ) > 0 P_Y(y)>0 P Y ( y ) > 0 on the finite alphabets. First, suppose that y y y -compatible orderings and the probability mass function α \alpha α on the admissible maps φ : X → Y \varphi:\mathcal{X}\to\mathcal{Y} φ : X → Y are given satisfying
P Y ∣ X ( y ∣ x ) = ∑ φ : φ ( x ) = y α ( φ ) . (104) P_{Y\mid X}(y\mid x)=\sum_{\varphi:\varphi(x)=y}\alpha(\varphi). \tag*{(104)} P Y ∣ X ( y ∣ x ) = φ : φ ( x ) = y ∑ α ( φ ) . (104)
We will show that P X , Y P_{X,Y} P X , Y admits a perfect functional representation. Define Z ⊥ X Z\perp X Z ⊥ X to take values in the space of admissible maps, with P ( Z = φ ) = α ( φ ) P(Z=\varphi)=\alpha(\varphi) P ( Z = φ ) = α ( φ ) . Set f ( x , φ ) = φ ( x ) f(x,\varphi)=\varphi(x) f ( x , φ ) = φ ( x ) . Then, ( Z , f ) (Z,f) ( Z , f ) is a functional realization of the channel. Indeed, for each x ∈ X , y ∈ Y x\in\mathcal{X},y\in\mathcal{Y} x ∈ X , y ∈ Y ,
P ( f ( x , Z ) = y ) = ∑ z : f ( x , z ) = y P ( Z = z ) = ∑ φ : φ ( x ) = y α ( φ ) = P Y ∣ X ( y ∣ x ) . P(f(x,Z)=y)=\sum_{z:f(x,z)=y}P(Z=z)
=\sum_{\varphi:\varphi(x)=y}\alpha(\varphi)=P_{Y\mid X}(y\mid x). P ( f ( x , Z ) = y ) = z : f ( x , z ) = y ∑ P ( Z = z ) = φ : φ ( x ) = y ∑ α ( φ ) = P Y ∣ X ( y ∣ x ) .
We next show that ( Z , f ) (Z,f) ( Z , f ) satisfies the equality condition in Lemma 4. Fix y ∈ Y y\in\mathcal{Y} y ∈ Y . For 0 ≤ p < 1 0\leq p<1 0 ≤ p < 1 , let k = max { i ∈ { 0 , … , n − 1 } : ∑ j = 1 i P X ( x y , j ) ≤ p } k=\max\left\{i\in\{0,\ldots,n-1\}:\sum_{j=1}^{i}P_X(x_{y,j})\leq p\right\} k = max { i ∈ { 0 , … , n − 1 } : ∑ j = 1 i P X ( x y , j ) ≤ p } , where the empty sum is zero. Define A y , p = { x y , 1 , … , x y , k } A_{y,p}=\{x_{y,1},\ldots,x_{y,k}\} A y , p = { x y , 1 , … , x y , k } , with A y , p = ∅ A_{y,p}=\varnothing A y , p = ∅ when k = 0 k=0 k = 0 , and put
b y , p ( x ) = 1 [ A y , p ] ( x ) + p − P X ( A y , p ) P X ( x y , k + 1 ) 1 [ x = x y , k + 1 ] , (105) b_{y,p}(x)=\mathbf{1}[A_{y,p}](x)+\frac{p-P_X(A_{y,p})}{P_X(x_{y,k+1})}\mathbf{1}[x=x_{y,k+1}], \tag*{(105)} b y , p ( x ) = 1 [ A y , p ] ( x ) + P X ( x y , k + 1 ) p − P X ( A y , p ) 1 [ x = x y , k + 1 ] , (105)
and set b y , 1 ( x ) = 1 b_{y,1}(x)=1 b y , 1 ( x ) = 1 for all x x x . Then, 0 ≤ b y , p ≤ 1 0\leq b_{y,p}\leq1 0 ≤ b y , p ≤ 1 and ∫ b y , p ( x ) d P X ( x ) = p \int b_{y,p}(x)\,\mathrm{d}P_X(x)=p ∫ b y , p ( x ) d P X ( x ) = p . Because the ordering is y y y -compatible, this is a measurable family of bathtub maximizers for r ( y ∣ x ) = P Y ∣ X ( y ∣ x ) / P Y ( y ) r(y\mid x)=P_{Y\mid X}(y\mid x)/P_Y(y) r ( y ∣ x ) = P Y ∣ X ( y ∣ x ) / P Y ( y ) . Let φ \varphi φ be an admissible mapping with α ( φ ) > 0 \alpha(\varphi)>0 α ( φ ) > 0 . Recall that φ − 1 ( y ) \varphi^{-1}(y) φ − 1 ( y ) is an initial segment of the ordering of x x x . If p ≤ q y ( φ ) p\leq q_y(\varphi) p ≤ q y ( φ ) , then { b y , p > 0 } ⊆ φ − 1 ( y ) \{b_{y,p}>0\}\subseteq\varphi^{-1}(y) { b y , p > 0 } ⊆ φ − 1 ( y ) and hence
∑ x ∈ X b y , p ( x ) 1 [ φ ( x ) = y ] P X ( x ) = ∑ x ∈ X b y , p ( x ) P X ( x ) = p . \sum_{x\in\mathcal{X}}b_{y,p}(x)\mathbf{1}[\varphi(x)=y]P_X(x)=\sum_{x\in\mathcal{X}}b_{y,p}(x)P_X(x)=p. x ∈ X ∑ b y , p ( x ) 1 [ φ ( x ) = y ] P X ( x ) = x ∈ X ∑ b y , p ( x ) P X ( x ) = p .
Alternatively, if p > q y ( φ ) p>q_y(\varphi) p > q y ( φ ) , then φ − 1 ( y ) ⊆ { b y , p = 1 } \varphi^{-1}(y)\subseteq\{b_{y,p}=1\} φ − 1 ( y ) ⊆ { b y , p = 1 } and hence
∑ x ∈ X b y , p ( x ) 1 [ φ ( x ) = y ] P X ( x ) = ∑ x ∈ X 1 [ φ ( x ) = y ] P X ( x ) = q y ( φ ) . \sum_{x\in\mathcal{X}}b_{y,p}(x)\mathbf{1}[\varphi(x)=y]P_X(x)
=\sum_{x\in\mathcal{X}}\mathbf{1}[\varphi(x)=y]P_X(x)=q_y(\varphi). x ∈ X ∑ b y , p ( x ) 1 [ φ ( x ) = y ] P X ( x ) = x ∈ X ∑ 1 [ φ ( x ) = y ] P X ( x ) = q y ( φ ) .
Therefore,
∫ X b y , p ( x ) 1 [ φ ( x ) = y ] d P X ( x ) = min { p , q y ( φ ) } , \int_{\mathcal{X}}b_{y,p}(x)\mathbf{1}[\varphi(x)=y]\,\mathrm{d}P_X(x)=\min\{p,q_y(\varphi)\}, ∫ X b y , p ( x ) 1 [ φ ( x ) = y ] d P X ( x ) = min { p , q y ( φ )} ,
and ( Z , f ) (Z,f) ( Z , f ) is a perfect representation.
Conversely, suppose that a representation ( Z , f ) (Z,f) ( Z , f ) is perfect. Let Φ = { φ : X → Y } \Phi=\{\varphi:\mathcal{X}\to\mathcal{Y}\} Φ = { φ : X → Y } be the set of all functions from X \mathcal{X} X to Y \mathcal{Y} Y . For any functional representation Y = f ( X , Z ) Y=f(X,Z) Y = f ( X , Z ) with Z ⊥ X Z\perp X Z ⊥ X , we have f ( ⋅ , z ) ∈ Φ f(\cdot,z)\in\Phi f ( ⋅ , z ) ∈ Φ for any z ∈ Z z\in\mathcal{Z} z ∈ Z , thus f ( ⋅ , Z ) f(\cdot,Z) f ( ⋅ , Z ) is a Φ \Phi Φ -valued random variable. For φ ∈ Φ \varphi\in\Phi φ ∈ Φ , let α ( φ ) = P ( f ( ⋅ , Z ) = φ ) \alpha(\varphi)=P(f(\cdot,Z)=\varphi) α ( φ ) = P ( f ( ⋅ , Z ) = φ ) . Then, we can introduce an equivalent discrete representation with Z = Φ \mathcal{Z}=\Phi Z = Φ , P ( Z = φ ) = α ( φ ) P(Z=\varphi)=\alpha(\varphi) P ( Z = φ ) = α ( φ ) , X X X and Z Z Z independent and f ( x , φ ) = φ ( x ) f(x,\varphi)=\varphi(x) f ( x , φ ) = φ ( x ) . This preserves H ( Y ∣ Z ) H(Y\mid Z) H ( Y ∣ Z ) , since the conditional distribution of Y Y Y given Z = z Z=z Z = z depends only on the map f ( ⋅ , z ) f(\cdot,z) f ( ⋅ , z ) . Thus the new representation is also perfect. By definition, such a representation satisfies (32). All that remains is to show that the maps with α ( φ ) > 0 \alpha(\varphi)>0 α ( φ ) > 0 are admissible for some fixed y y y -compatible orderings. In the remainder of the proof, consider only maps with positive α \alpha α -probability. Recall that φ \varphi φ is admissible if, for every y ∈ Y y\in\mathcal{Y} y ∈ Y ,
φ − 1 ( y ) = { x y , 1 , … , x y , k y } \varphi^{-1}(y)=\{x_{y,1},\ldots,x_{y,k_y}\} φ − 1 ( y ) = { x y , 1 , … , x y , k y }
for an index k y ∈ { 0 , … , n } k_y \in\{0,\ldots,n\} k y ∈ { 0 , … , n } and ordering x y , 1 , … , x y , n x_{y,1},\ldots,x_{y,n} x y , 1 , … , x y , n satisfying
P Y ∣ X ( y ∣ x y , i ) ≥ P Y ∣ X ( y ∣ x y , j ) , (106) P_{Y\mid X}(y\mid x_{y,i}) \ge P_{Y\mid X}(y\mid x_{y,j}), \tag*{(106)} P Y ∣ X ( y ∣ x y , i ) ≥ P Y ∣ X ( y ∣ x y , j ) , (106)
for all i < j i<j i < j .
Fix y ∈ Y y \in\mathcal{Y} y ∈ Y . Then
q y ( φ ) = P Y ∣ Z = φ ( y ) = P X ( φ − 1 ( y ) ) , ν y ( φ ) = α ( φ ) q y ( φ ) P Y ( y ) . q_y(\varphi)=P_{Y\mid Z=\varphi}(y)=P_X\left(\varphi^{-1}(y)\right), \qquad\nu_y(\varphi)=\frac{\alpha(\varphi)q_y(\varphi)}{P_Y(y)}. q y ( φ ) = P Y ∣ Z = φ ( y ) = P X ( φ − 1 ( y ) ) , ν y ( φ ) = P Y ( y ) α ( φ ) q y ( φ ) .
Choose a family b y , p b_{y,p} b y , p as in Lemma 4. Since there are only finitely many maps, there is a full-measure set of p ∈ ( 0 , 1 ) p\in(0,1) p ∈ ( 0 , 1 ) on which (100) holds simultaneously for every φ \varphi φ with ν y ( φ ) > 0 \nu_y(\varphi)>0 ν y ( φ ) > 0 . All choices of p p p below are made in this set. We claim that, for φ , ψ \varphi,\psi φ , ψ with q y ( φ ) , q y ( ψ ) > 0 q_y(\varphi),q_y(\psi)>0 q y ( φ ) , q y ( ψ ) > 0 , q y ( φ ) ≤ q y ( ψ ) q_y(\varphi)\le q_y(\psi) q y ( φ ) ≤ q y ( ψ ) implies φ − 1 ( y ) ⊆ ψ − 1 ( y ) \varphi^{-1}(y)\subseteq\psi^{-1}(y) φ − 1 ( y ) ⊆ ψ − 1 ( y ) . Indeed, if q y ( φ ) < q y ( ψ ) q_y(\varphi)<q_y(\psi) q y ( φ ) < q y ( ψ ) , choose q y ( φ ) < p < q y ( ψ ) q_y(\varphi)<p<q_y(\psi) q y ( φ ) < p < q y ( ψ ) . Then (100) gives
φ − 1 ( y ) ⊆ { b y , p = 1 } ⊆ { b y , p > 0 } ⊆ ψ − 1 ( y ) . (107) \varphi^{-1}(y)\subseteq\{b_{y,p}=1\}\subseteq\{b_{y,p}>0\}\subseteq\psi^{-1}(y). \tag*{(107)} φ − 1 ( y ) ⊆ { b y , p = 1 } ⊆ { b y , p > 0 } ⊆ ψ − 1 ( y ) . (107)
Similarly, if q y ( φ ) = q y ( ψ ) = q q_y(\varphi)=q_y(\psi)=q q y ( φ ) = q y ( ψ ) = q , then for p < q p<q p < q , (100) implies { b y , p > 0 } ⊆ φ − 1 ( y ) ∩ ψ − 1 ( y ) \{b_{y,p}>0\}\subseteq\varphi^{-1}(y)\cap\psi^{-1}(y) { b y , p > 0 } ⊆ φ − 1 ( y ) ∩ ψ − 1 ( y ) . Since ∫ b y , p d P X = p \int b_{y,p}\,dP_X=p ∫ b y , p d P X = p , this implies
P X ( φ − 1 ( y ) ∩ ψ − 1 ( y ) ) ≥ p . (108) P_X\left(\varphi^{-1}(y)\cap\psi^{-1}(y)\right)\ge p. \tag*{(108)} P X ( φ − 1 ( y ) ∩ ψ − 1 ( y ) ) ≥ p . (108)
Letting p ↑ q p\uparrow q p ↑ q through the full-measure set gives that the intersection has mass at least q q q . Since both cells have mass q q q and P X ( x ) > 0 P_X(x)>0 P X ( x ) > 0 for every x x x , they are equal. Thus, the sets φ − 1 ( y ) \varphi^{-1}(y) φ − 1 ( y ) form a nested chain ordered by their masses q y ( φ ) q_y(\varphi) q y ( φ ) .
Next, for any φ \varphi φ with q y ( φ ) > 0 q_y(\varphi)>0 q y ( φ ) > 0 , we claim that for every x ∈ φ − 1 ( y ) x\in\varphi^{-1}(y) x ∈ φ − 1 ( y ) and x ′ ∉ φ − 1 ( y ) x'\notin\varphi^{-1}(y) x ′ ∈ / φ − 1 ( y ) , P Y ∣ X ( y ∣ x ) ≥ P Y ∣ X ( y ∣ x ′ ) P_{Y\mid X}(y\mid x)\ge P_{Y\mid X}(y\mid x') P Y ∣ X ( y ∣ x ) ≥ P Y ∣ X ( y ∣ x ′ ) . Suppose, toward a contradiction, that the reverse strict inequality holds for some such x , x ′ x,x' x , x ′ . Let q = q y ( φ ) q=q_y(\varphi) q = q y ( φ ) and choose p ∈ ( q , q + P X ( x ′ ) ) p\in(q,q+P_X(x')) p ∈ ( q , q + P X ( x ′ )) in the full-measure set. By (100), φ − 1 ( y ) ⊆ { b y , p = 1 } \varphi^{-1}(y)\subseteq\{b_{y,p}=1\} φ − 1 ( y ) ⊆ { b y , p = 1 } . As b y , p b_{y,p} b y , p maximizes the integral against P Y ∣ X ( y ∣ x ) / P Y ( y ) P_{Y\mid X}(y\mid x)/P_Y(y) P Y ∣ X ( y ∣ x ) / P Y ( y ) , we must also have b y , p ( x ′ ) = 1 b_{y,p}(x')=1 b y , p ( x ′ ) = 1 : otherwise, transferring a small amount of P X P_X P X -mass of b y , p b_{y,p} b y , p from x x x to x ′ x' x ′ would increase the objective while preserving ∫ b y , p d P X = p \int b_{y,p}\,dP_X=p ∫ b y , p d P X = p . Therefore,
∫ X b y , p ( x ) d P X ( x ) ≥ q + P X ( x ′ ) > p , (109) \int_{\mathcal{X}} b_{y,p}(x)\,dP_X(x)\ge q+P_X(x')>p, \tag*{(109)} ∫ X b y , p ( x ) d P X ( x ) ≥ q + P X ( x ′ ) > p , (109)
contradicting the definition of b y , p b_{y,p} b y , p . This establishes the claim.
We now construct the y y y -compatible ordering of X \mathcal{X} X . Sort X \mathcal{X} X according to decreasing P Y ∣ X ( y ∣ x ) P_{Y\mid X}(y\mid x) P Y ∣ X ( y ∣ x ) . Within each tie group, order the points by when they enter the nested chain of cells φ − 1 ( y ) \varphi^{-1}(y) φ − 1 ( y ) , placing points that never enter last and breaking any remaining ties arbitrarily. This ordering is, by definition, y y y -compatible. By the two claims, every φ − 1 ( y ) \varphi^{-1}(y) φ − 1 ( y ) contains all points preceding any of its points, so it is an initial segment.
Finally, if α ( φ ) > 0 \alpha(\varphi)>0 α ( φ ) > 0 but ν y ( φ ) = 0 \nu_y(\varphi)=0 ν y ( φ ) = 0 , then q y ( φ ) = 0 q_y(\varphi)=0 q y ( φ ) = 0 and, since P X ( x ) > 0 P_X(x)>0 P X ( x ) > 0 for every x x x , φ − 1 ( y ) = ∅ \varphi^{-1}(y)=\varnothing φ − 1 ( y ) = ∅ , which is an initial segment of any ordering. □
Proof of Proposition 7. Let Y = { 0 , 1 } \mathcal{Y}=\{0,1\} Y = { 0 , 1 } , Z ∼ Unif ( 0 , 1 ) Z\sim\operatorname{Unif}(0,1) Z ∼ Unif ( 0 , 1 ) , and let f ( x , z ) = 1 [ P Y ∣ X ( 1 ∣ x ) ≥ z ] f(x,z)=\mathbf{1}[P_{Y\mid X}(1\mid x)\ge z] f ( x , z ) = 1 [ P Y ∣ X ( 1 ∣ x ) ≥ z ] . Then, for every x x x ,
P ( f ( x , Z ) = 1 ) = P Y ∣ X ( 1 ∣ x ) , \mathbb{P}(f(x,Z)=1)=P_{Y\mid X}(1\mid x), P ( f ( x , Z ) = 1 ) = P Y ∣ X ( 1 ∣ x ) ,
and therefore Y = f ( X , Z ) Y=f(X,Z) Y = f ( X , Z ) . For 0 ≤ ℓ ≤ 1 / P Y ( y ) 0\le\ell\le1/P_Y(y) 0 ≤ ℓ ≤ 1/ P Y ( y ) , we can then compute
w y ( ℓ ) = P X ( d P Y ∣ X d P Y ( y ∣ X ) ≥ ℓ ) = P X ( P Y ∣ X ( y ∣ X ) ≥ ℓ P Y ( y ) ) = { P Y ∣ Z ( 1 ∣ ℓ P Y ( 1 ) ) , y = 1 , P Y ∣ Z ( 0 ∣ 1 − ℓ P Y ( 0 ) ) , y = 0. \begin{aligned}
w_y(\ell)
&=P_X\left(\frac{dP_{Y\mid X}}{dP_Y}(y\mid X)\ge\ell\right)\\
&=P_X\left(P_{Y\mid X}(y\mid X)\ge\ell P_Y(y)\right)\\
&=
\begin{cases}
P_{Y\mid Z}(1\mid\ell P_Y(1)), & y=1,\\
P_{Y\mid Z}(0\mid1-\ell P_Y(0)), & y=0.
\end{cases}
\end{aligned} w y ( ℓ ) = P X ( d P Y d P Y ∣ X ( y ∣ X ) ≥ ℓ ) = P X ( P Y ∣ X ( y ∣ X ) ≥ ℓ P Y ( y ) ) = { P Y ∣ Z ( 1 ∣ ℓ P Y ( 1 )) , P Y ∣ Z ( 0 ∣ 1 − ℓ P Y ( 0 )) , y = 1 , y = 0.
where the last equality holds for a.e. ℓ \ell ℓ . Substituting z = ℓ P Y ( 1 ) z=\ell P_Y(1) z = ℓ P Y ( 1 ) for y = 1 y=1 y = 1 and z = 1 − ℓ P Y ( 0 ) z=1-\ell P_Y(0) z = 1 − ℓ P Y ( 0 ) for y = 0 y=0 y = 0 , we obtain that
I F ( X → Y ) = − ∑ y = 0 1 P Y ( y ) ∫ 0 1 / P Y ( y ) w y ( ℓ ) log w y ( ℓ ) d ℓ = − ∑ y = 0 1 P Y ( y ) ∫ 0 1 P Y ∣ Z ( y ∣ z ) log P Y ∣ Z ( y ∣ z ) 1 P Y ( y ) d z = E Z [ h b ( P Y ∣ Z ( 1 ∣ Z ) ) ] = H ( Y ∣ Z ) . \begin{aligned}
I_F(X\to Y)
&=-\sum_{y=0}^{1}P_Y(y)\int_0^{1/P_Y(y)}w_y(\ell)\log w_y(\ell)\,d\ell\\
&=-\sum_{y=0}^{1}P_Y(y)\int_0^1P_{Y\mid Z}(y\mid z)\log P_{Y\mid Z}(y\mid z)\frac{1}{P_Y(y)}\,dz\\
&=\mathbb{E}_Z\left[h_b\left(P_{Y\mid Z}(1\mid Z)\right)\right]\\
&=H(Y\mid Z).
\end{aligned} I F ( X → Y ) = − y = 0 ∑ 1 P Y ( y ) ∫ 0 1/ P Y ( y ) w y ( ℓ ) log w y ( ℓ ) d ℓ = − y = 0 ∑ 1 P Y ( y ) ∫ 0 1 P Y ∣ Z ( y ∣ z ) log P Y ∣ Z ( y ∣ z ) P Y ( y ) 1 d z = E Z [ h b ( P Y ∣ Z ( 1 ∣ Z ) ) ] = H ( Y ∣ Z ) .
We conclude that ( Z , f ) (Z,f) ( Z , f ) is a perfect functional representation. □
Proof of Proposition 8. Let Y = X = { 1 , 2 , 3 } \mathcal{Y}=\mathcal{X}=\{1,2,3\} Y = X = { 1 , 2 , 3 } and define
P Y ∣ X = [ 1 − ϵ 0 ϵ ϵ 1 − ϵ 0 0 ϵ 1 − ϵ ] . P_{Y\mid X}=
\begin{bmatrix}
1-\epsilon& 0 & \epsilon\\
\epsilon& 1-\epsilon& 0\\
0 & \epsilon& 1-\epsilon
\end{bmatrix}. P Y ∣ X = 1 − ϵ ϵ 0 0 1 − ϵ ϵ ϵ 0 1 − ϵ .
where 1 / 3 < ϵ < 1 / 2 1/3<\epsilon<1/2 1/3 < ϵ < 1/2 . We claim that no perfect functional representation exists for this channel. Let ( Z , f ) (Z,f) ( Z , f ) be a functional representation of Y Y Y . As in the proof of Proposition 6, we will replace this with an equivalent discrete representation Z = Φ Z=\Phi Z = Φ with f ( x , φ ) = φ ( x ) f(x,\varphi)=\varphi(x) f ( x , φ ) = φ ( x ) and P ( Z = φ ) = α ( φ ) \mathbb{P}(Z=\varphi)=\alpha(\varphi) P ( Z = φ ) = α ( φ ) . The y y y -compatible orderings are unique and are
{ 1 , 2 , 3 , y = 1 2 , 3 , 1 , y = 2 3 , 1 , 2 , y = 3. (110) \begin{cases}
1,2,3, & y=1\\
2,3,1, & y=2\\
3,1,2, & y=3. \tag*{(110)}
\end{cases} ⎩ ⎨ ⎧ 1 , 2 , 3 , 2 , 3 , 1 , 3 , 1 , 2 , y = 1 y = 2 y = 3. (110)
Since P Y ∣ X ( 2 ∣ 1 ) = P Y ∣ X ( 3 ∣ 2 ) = P Y ∣ X ( 1 ∣ 3 ) = 0 P_{Y\mid X}(2\mid1)=P_{Y\mid X}(3\mid2)=P_{Y\mid X}(1\mid3)=0 P Y ∣ X ( 2 ∣ 1 ) = P Y ∣ X ( 3 ∣ 2 ) = P Y ∣ X ( 1 ∣ 3 ) = 0 , all φ \varphi φ with α ( φ ) > 0 \alpha(\varphi)>0 α ( φ ) > 0 must satisfy
φ ( 1 ) ∈ { 1 , 3 } , φ ( 2 ) ∈ { 1 , 2 } , φ ( 3 ) ∈ { 2 , 3 } . \varphi(1)\in\{1,3\},\qquad\varphi(2)\in\{1,2\},\qquad\varphi(3)\in\{2,3\}. φ ( 1 ) ∈ { 1 , 3 } , φ ( 2 ) ∈ { 1 , 2 } , φ ( 3 ) ∈ { 2 , 3 } .
Therefore, the only support-compatible maps are
( 1 , 1 , 2 ) , ( 1 , 1 , 3 ) , ( 1 , 2 , 2 ) , ( 1 , 2 , 3 ) , (1,1,2),(1,1,3),(1,2,2),(1,2,3), ( 1 , 1 , 2 ) , ( 1 , 1 , 3 ) , ( 1 , 2 , 2 ) , ( 1 , 2 , 3 ) ,
( 3 , 1 , 2 ) , ( 3 , 1 , 3 ) , ( 3 , 2 , 2 ) , ( 3 , 2 , 3 ) , (3,1,2),(3,1,3),(3,2,2),(3,2,3), ( 3 , 1 , 2 ) , ( 3 , 1 , 3 ) , ( 3 , 2 , 2 ) , ( 3 , 2 , 3 ) ,
where a triple denotes ( φ ( 1 ) , φ ( 2 ) , φ ( 3 ) ) (\varphi(1),\varphi(2),\varphi(3)) ( φ ( 1 ) , φ ( 2 ) , φ ( 3 )) . Among these, the only maps admissible for the y y y -compatible ordering in (110) are
φ 1 = ( 1 , 1 , 3 ) , φ 2 = ( 1 , 2 , 2 ) , φ 3 = ( 1 , 2 , 3 ) , φ 4 = ( 3 , 2 , 3 ) . \varphi_1=(1,1,3),\quad\varphi_2=(1,2,2),\quad\varphi_3=(1,2,3),\quad\varphi_4=(3,2,3). φ 1 = ( 1 , 1 , 3 ) , φ 2 = ( 1 , 2 , 2 ) , φ 3 = ( 1 , 2 , 3 ) , φ 4 = ( 3 , 2 , 3 ) .
Indeed, their cells are
Table 1.
For ( Z , f ) (Z,f) ( Z , f ) to be perfect, the convex hull requirement of Proposition 6 must hold for some weights α 1 , … , α 4 \alpha_1,\ldots,\alpha_4 α 1 , … , α 4 . This means
α 4 = P Y ∣ X ( 3 ∣ 1 ) = ϵ , \alpha_4=P_{Y\mid X}(3\mid1)=\epsilon, α 4 = P Y ∣ X ( 3 ∣ 1 ) = ϵ ,
as the only map which sends input 1 to output 3 is φ 4 \varphi_4 φ 4 . Similarly, we must have that
α 1 = P Y ∣ X ( 1 ∣ 2 ) = ϵ , α 2 = P Y ∣ X ( 2 ∣ 3 ) = ϵ . \alpha_1=P_{Y\mid X}(1\mid2)=\epsilon,\qquad\alpha_2=P_{Y\mid X}(2\mid3)=\epsilon. α 1 = P Y ∣ X ( 1 ∣ 2 ) = ϵ , α 2 = P Y ∣ X ( 2 ∣ 3 ) = ϵ .
Therefore,
α 1 + α 2 + α 3 + α 4 ≥ 3 ϵ > 1. \alpha_1+\alpha_2+\alpha_3+\alpha_4\ge3\epsilon>1. α 1 + α 2 + α 3 + α 4 ≥ 3 ϵ > 1.
violating the requirement that α \alpha α be a probability distribution. We conclude that a perfect functional representation cannot exist for this channel.
The Generalized Ring Toss Code
Rejection Sampling
Given a target distribution P ≪ Q P\ll Q P ≪ Q with r = d P d Q ≤ M r=\frac{dP}{dQ}\le M r = d Q d P ≤ M , rejection sampling draws { ( Y i , U i ) } i ≥ 1 ∼ i . i . d . Q ⊗ Unif ( 0 , 1 ) \{(Y_i,U_i)\}_{i\ge1}\mathrel{\overset{\mathrm{i.i.d.}}{\sim}} Q\otimes\operatorname{Unif}(0,1) {( Y i , U i ) } i ≥ 1 ∼ i.i.d. Q ⊗ Unif ( 0 , 1 ) and returns the index
K = min { i : U i ≤ 1 M r ( Y i ) } . K=\min\left\{i:U_i\le\frac{1}{M}r(Y_i)\right\}. K = min { i : U i ≤ M 1 r ( Y i ) } .
Then Y K ∼ P Y_K\sim P Y K ∼ P . For channel simulation, suppose d P Y ∣ X d P Y ≤ M \frac{dP_{Y\mid X}}{dP_Y}\le M d P Y d P Y ∣ X ≤ M uniformly and use the shared randomness Z = { ( Y i , U i ) } i ≥ 1 ∼ i . i . d . P Y ⊗ Unif ( 0 , 1 ) Z=\{(Y_i,U_i)\}_{i\ge1}\mathrel{\overset{\mathrm{i.i.d.}}{\sim}}P_Y\otimes\operatorname{Unif}(0,1) Z = {( Y i , U i ) } i ≥ 1 ∼ i.i.d. P Y ⊗ Unif ( 0 , 1 ) . Given X = x X=x X = x , the encoder applies rejection sampling to P Y ∣ X = x P_{Y\mid X=x} P Y ∣ X = x and sends a prefix-free description of K K K , allowing the decoder to recover the simulated output Y = Y K Y=Y_K Y = Y K . As K K K is geometrically distributed with success parameter 1 / M 1/M 1/ M , which we write as K ∼ Geom ( 1 / M ) K\sim\operatorname{Geom}(1/M) K ∼ Geom ( 1/ M ) , we have
H ( Y ∣ Z ) ≤ H ( K ∣ Z ) ≤ H ( K ) ≤ log M + log e . (111) H(Y\mid Z)\le H(K\mid Z)\le H(K)\le\log M+\log e. \tag*{(111)} H ( Y ∣ Z ) ≤ H ( K ∣ Z ) ≤ H ( K ) ≤ log M + log e . (111)
This ignores the decoder’s knowledge of Z Z Z , and log M \log M log M can greatly exceed I F ( X → Y ) I_F(X\to Y) I F ( X → Y ) . Conditioning the coding distribution on Z Z Z gives the tighter bound below. Related sorting constructions achieve I ( X ; Y ) + O ( log ( I ( X ; Y ) + 1 ) ) I(X;Y)+O(\log(I(X;Y)+1)) I ( X ; Y ) + O ( log ( I ( X ; Y ) + 1 )) bits [7 ] , [41 ] .
The conventional proposal Q Y = P Y Q_Y = P_Y Q Y = P Y minimizes the conditional relative entropy:
min Q Y D K L ( P Y ∣ X ∥ Q Y ∣ P X ) = I ( X ; Y ) . \min_{Q_Y} D_{\mathrm{KL}}(P_{Y\mid X} \mathbin\Vert Q_Y\mid P_X) = I(X;Y). Q Y min D KL ( P Y ∣ X ∥ Q Y ∣ P X ) = I ( X ; Y ) .
Theorem 6 instead gives a bound uniform over all admissible proposals, allowing Q Y Q_Y Q Y to be chosen for ease of sampling or computational efficiency [42 ] .
Theorem 6 (Constant-Gap Optimality of Rejection Sampling). Given the joint distribution P X , Y P_{X,Y} P X , Y , let Q Y Q_Y Q Y be any proposal distribution such that P Y ∣ X = x ≪ Q Y P_{Y\mid X=x} \ll Q_Y P Y ∣ X = x ≪ Q Y for P X P_X P X -a.e. x x x and there exists M > 0 M > 0 M > 0 such that some version satisfies d P Y ∣ X d Q Y ( y ∣ x ) ≤ M \frac{dP_{Y\mid X}}{dQ_Y}(y\mid x) \le M d Q Y d P Y ∣ X ( y ∣ x ) ≤ M for every x , y x,y x , y . Let Z = { ( Y i , U i ) } i ≥ 1 ∼ i . i . d . Q Y ⊗ Unif ( 0 , 1 ) Z = \{(Y_i,U_i)\}_{i\ge1} \mathrel{\overset{\mathrm{i.i.d.}}{\sim}} Q_Y \otimes\operatorname{Unif}(0,1) Z = {( Y i , U i ) } i ≥ 1 ∼ i.i.d. Q Y ⊗ Unif ( 0 , 1 ) be independent of X X X and define
K ≜ min { i : M U i ≤ d P Y ∣ X d Q Y ( Y i ∣ X ) } . (112) K \triangleq\min\left\{i: MU_i \le\frac{dP_{Y\mid X}}{dQ_Y}(Y_i\mid X)\right\}. \tag*{(112)} K ≜ min { i : M U i ≤ d Q Y d P Y ∣ X ( Y i ∣ X ) } . (112) Then, P Y K ∣ X = x = P Y ∣ X = x P_{Y_K\mid X=x} = P_{Y\mid X=x} P Y K ∣ X = x = P Y ∣ X = x for P X P_X P X -a.e. x x x and, with Y = Y K Y = Y_K Y = Y K ,
H ( Y ∣ Z ) ≤ I F ( X → Y ) + log e . (113) H(Y\mid Z) \le I_F(X\to Y) + \log e. \tag*{(113)} H ( Y ∣ Z ) ≤ I F ( X → Y ) + log e . (113) Moreover, this upper bound is achieved within one bit by encoding K K K conditioned on Z Z Z using the Shannon-Fano code for the coding distribution
Q K ∣ Z ( k ∣ z ) ≜ w Y k Q ( M u k ) ∏ i = 1 k − 1 ( 1 − w Y i Q ( M u i ) ) , (114) Q_{K\mid Z}(k\mid z) \triangleq w_{Y_k}^Q(Mu_k)\prod_{i=1}^{k-1}(1-w_{Y_i}^Q(Mu_i)), \tag*{(114)} Q K ∣ Z ( k ∣ z ) ≜ w Y k Q ( M u k ) i = 1 ∏ k − 1 ( 1 − w Y i Q ( M u i )) , (114) for w y Q w_y^Q w y Q a width function given by
w y Q ( ℓ ) = P X ( d P Y ∣ X d Q Y ( y ∣ X ) ≥ ℓ ) . (115) w_y^Q(\ell) = P_X\left(\frac{dP_{Y\mid X}}{dQ_Y}(y\mid X)\ge\ell\right). \tag*{(115)} w y Q ( ℓ ) = P X ( d Q Y d P Y ∣ X ( y ∣ X ) ≥ ℓ ) . (115)
Proof. The correctness of this scheme, i.e., that P Y K ∣ X = x = P Y ∣ X = x P_{Y_K\mid X=x} = P_{Y\mid X=x} P Y K ∣ X = x = P Y ∣ X = x for P X P_X P X -a.e. x x x , follows from the correctness of standard rejection sampling.
Note that Q K ∣ Z Q_{K\mid Z} Q K ∣ Z is a valid probability distribution, as 0 ≤ Q K ∣ Z ( k ∣ z ) ≤ 1 0 \le Q_{K\mid Z}(k\mid z) \le1 0 ≤ Q K ∣ Z ( k ∣ z ) ≤ 1 for each k k k and, by using the identity that w = 1 − ( 1 − w ) w = 1-(1-w) w = 1 − ( 1 − w ) , we get
Q K ∣ Z ( k ∣ z ) = ∏ i = 1 k − 1 ( 1 − w Y i Q ( M u i ) ) − ∏ i = 1 k ( 1 − w Y i Q ( M u i ) ) . Q_{K\mid Z}(k\mid z) = \prod_{i=1}^{k-1}(1-w_{Y_i}^Q(Mu_i))-\prod_{i=1}^{k}(1-w_{Y_i}^Q(Mu_i)). Q K ∣ Z ( k ∣ z ) = i = 1 ∏ k − 1 ( 1 − w Y i Q ( M u i )) − i = 1 ∏ k ( 1 − w Y i Q ( M u i )) .
This is a telescoping series, giving
∑ k = 1 ∞ Q K ∣ Z ( k ∣ z ) = 1 − lim n → ∞ ∏ i = 1 n ( 1 − w Y i Q ( M u i ) ) . \sum_{k=1}^{\infty}Q_{K\mid Z}(k\mid z)=1-\lim_{n\to\infty}\prod_{i=1}^{n}(1-w_{Y_i}^Q(Mu_i)). k = 1 ∑ ∞ Q K ∣ Z ( k ∣ z ) = 1 − n → ∞ lim i = 1 ∏ n ( 1 − w Y i Q ( M u i )) .
However, note that the limit vanishes P Z P_Z P Z -a.e., as the w Y i Q ( M U i ) ∈ [ 0 , 1 ] w_{Y_i}^Q(MU_i)\in[0,1] w Y i Q ( M U i ) ∈ [ 0 , 1 ] are i.i.d. with mean 1 M > 0 \frac{1}{M}>0 M 1 > 0 .
Since H ( Y ∣ Z ) ≤ H ( K ∣ Z ) ≤ H ( P K ∣ Z ; Q K ∣ Z ) H(Y\mid Z)\le H(K\mid Z)\le H(P_{K\mid Z};Q_{K\mid Z}) H ( Y ∣ Z ) ≤ H ( K ∣ Z ) ≤ H ( P K ∣ Z ; Q K ∣ Z ) , we show (113) by upper bounding the cross-entropy H ( P K ∣ Z ; Q K ∣ Z ) H(P_{K\mid Z};Q_{K\mid Z}) H ( P K ∣ Z ; Q K ∣ Z ) between Q K ∣ Z Q_{K\mid Z} Q K ∣ Z and the true conditional distribution P K ∣ Z P_{K\mid Z} P K ∣ Z of K K K given Z Z Z . We can compute
H ( P K ∣ Z ; Q K ∣ Z ) = E K , Z [ − log Q K ∣ Z ( K ∣ Z ) ] = E Y K , U K [ − log w Y K Q ( M U K ) ] − E K , Z [ ∑ i = 1 K − 1 log ( 1 − w Y i Q ( M U i ) ) ] . (116) \begin{aligned}
H(P_{K\mid Z};Q_{K\mid Z}) &= \mathbb{E}_{K,Z}[-\log Q_{K\mid Z}(K\mid Z)]\\
&= \mathbb{E}_{Y_K,U_K}[-\log w_{Y_K}^Q(MU_K)]\\
&\quad-\mathbb{E}_{K,Z}\left[\sum_{i=1}^{K-1}\log(1-w_{Y_i}^Q(MU_i))\right]. \tag*{(116)}
\end{aligned} H ( P K ∣ Z ; Q K ∣ Z ) = E K , Z [ − log Q K ∣ Z ( K ∣ Z )] = E Y K , U K [ − log w Y K Q ( M U K )] − E K , Z [ i = 1 ∑ K − 1 log ( 1 − w Y i Q ( M U i )) ] . (116)
We will address each term in (113) separately; however, before doing so, let us determine the joint distribution of ( Y K , U K ) (Y_K,U_K) ( Y K , U K ) . We use the notation r Q ( y ∣ x ) ≜ d P Y ∣ X d Q Y ( y ∣ x ) r^Q(y\mid x)\triangleq\frac{dP_{Y\mid X}}{dQ_Y}(y\mid x) r Q ( y ∣ x ) ≜ d Q Y d P Y ∣ X ( y ∣ x ) . By the definition of rejection sampling, we have
d P Y K , U K ∣ X d ( Q Y ⊗ Unif ( 0 , 1 ) ) ( y , u ∣ X ) = M ⋅ 1 [ M u ≤ r Q ( y ∣ X ) ] . (117) \frac{dP_{Y_K,U_K\mid X}}{d(Q_Y\otimes\operatorname{Unif}(0,1))}(y,u\mid X)=M\cdot\mathbf{1}[Mu\le r^Q(y\mid X)]. \tag*{(117)} d ( Q Y ⊗ Unif ( 0 , 1 )) d P Y K , U K ∣ X ( y , u ∣ X ) = M ⋅ 1 [ M u ≤ r Q ( y ∣ X )] . (117)
Note that since we are using a universal upper bound M M M , we have K ∣ X ∼ Geom ( 1 / M ) K\mid X\sim\operatorname{Geom}(1/M) K ∣ X ∼ Geom ( 1/ M ) irrespective of X X X ; i.e., K K K conditioned on X X X is geometrically distributed with parameter 1 / M 1/M 1/ M . In particular, P ( K ≥ k ∣ X ) = ( 1 − 1 M ) k − 1 \mathbb{P}(K\ge k\mid X)=(1-\frac{1}{M})^{k-1} P ( K ≥ k ∣ X ) = ( 1 − M 1 ) k − 1 and E [ K ∣ X ] = M \mathbb{E}[K\mid X]=M E [ K ∣ X ] = M . In expectations over proposals below, ( Y , U ) ∼ Q Y ⊗ Unif ( 0 , 1 ) (Y,U)\sim Q_Y\otimes\operatorname{Unif}(0,1) ( Y , U ) ∼ Q Y ⊗ Unif ( 0 , 1 ) is independent of X X X . With 0 ⋅ ( − ∞ ) = 0 0\cdot(-\infty)=0 0 ⋅ ( − ∞ ) = 0 , we get
E Y K , U K [ − log w Y K Q ( M U K ) ] = E X [ E Y K , U K ∣ X [ − log w Y K Q ( M U K ) ∣ X ] ] = − E Y , U , X [ M 1 [ M U ≤ r Q ( Y ∣ X ) ] log w Y Q ( M U ) ] . \begin{aligned}
\mathbb{E}_{Y_K,U_K}[-\log w_{Y_K}^Q(MU_K)]
&=\mathbb{E}_X\left[\mathbb{E}_{Y_K,U_K\mid X}[-\log w_{Y_K}^Q(MU_K)\mid X]\right]\\
&=-\mathbb{E}_{Y,U,X}\left[M\mathbf{1}[MU\le r^Q(Y\mid X)]\log w_Y^Q(MU)\right].
\end{aligned} E Y K , U K [ − log w Y K Q ( M U K )] = E X [ E Y K , U K ∣ X [ − log w Y K Q ( M U K ) ∣ X ] ] = − E Y , U , X [ M 1 [ M U ≤ r Q ( Y ∣ X )] log w Y Q ( M U ) ] .
(by (114))
= − E Y , U [ M E X ∣ Y , U [ 1 { M U ≤ r Q ( Y ∣ X ) } ∣ Y , U ] log w Y Q ( M U ) ] = − E Y , U [ M ⋅ w Y Q ( M U ) log w Y Q ( M U ) ] = − E Y [ ∫ 0 1 M ⋅ w Y Q ( M u ) log w Y Q ( M u ) d u ] = − E Y [ ∫ 0 M w Y Q ( ℓ ) log w Y Q ( ℓ ) d ℓ ] = − ∫ Y ∫ 0 ∞ w y ( ℓ d P Y d Q Y ( y ) ) log w y ( ℓ d P Y d Q Y ( y ) ) d ℓ d Q Y ( y ) = − ∫ Y ∫ 0 ∞ w y ( h ) log w y ( h ) d h d P Y d Q Y ( y ) d Q Y ( y ) = I F ( X → Y ) . (118) \begin{aligned}
=-\mathbb{E}_{Y,U}\left[M\mathbb{E}_{X\mid Y,U}\left[\mathbf{1}\left\{MU\le r^{Q}(Y\mid X)\right\}\mid Y,U\right]\log w_Y^{Q}(MU)\right] \\
&=-\mathbb{E}_{Y,U}\left[M\cdot w_Y^{Q}(MU)\log w_Y^{Q}(MU)\right] \\
&=-\mathbb{E}_{Y}\left[\int_{0}^{1}M\cdot w_Y^{Q}(Mu)\log w_Y^{Q}(Mu)\,du\right] \\
&=-\mathbb{E}_{Y}\left[\int_{0}^{M}w_Y^{Q}(\ell)\log w_Y^{Q}(\ell)\,d\ell\right] \\
&=-\int_{\mathcal{Y}}\int_{0}^{\infty}w_y\left(\frac{\ell}{\frac{dP_Y}{dQ_Y}(y)}\right)\log w_y\left(\frac{\ell}{\frac{dP_Y}{dQ_Y}(y)}\right)\,d\ell\,dQ_Y(y) \\
&=-\int_{\mathcal{Y}}\int_{0}^{\infty}w_y(h)\log w_y(h)\,dh\,\frac{dP_Y}{dQ_Y}(y)\,dQ_Y(y) \\
&=I_F(X\to Y). \tag*{(118)}
\end{aligned} = − E Y , U [ M E X ∣ Y , U [ 1 { M U ≤ r Q ( Y ∣ X ) } ∣ Y , U ] log w Y Q ( M U ) ] = − E Y , U [ M ⋅ w Y Q ( M U ) log w Y Q ( M U ) ] = − E Y [ ∫ 0 1 M ⋅ w Y Q ( M u ) log w Y Q ( M u ) d u ] = − E Y [ ∫ 0 M w Y Q ( ℓ ) log w Y Q ( ℓ ) d ℓ ] = − ∫ Y ∫ 0 ∞ w y ( d Q Y d P Y ( y ) ℓ ) log w y ( d Q Y d P Y ( y ) ℓ ) d ℓ d Q Y ( y ) = − ∫ Y ∫ 0 ∞ w y ( h ) log w y ( h ) d h d Q Y d P Y ( y ) d Q Y ( y ) = I F ( X → Y ) . (118)
For Q Y Q_Y Q Y -a.e. y y y with d P Y d Q Y ( y ) = 0 \frac{dP_Y}{dQ_Y}(y)=0 d Q Y d P Y ( y ) = 0 , w y Q ( ℓ ) = 0 w_y^{Q}(\ell)=0 w y Q ( ℓ ) = 0 for ℓ > 0 \ell>0 ℓ > 0 ; the integrands in the change of variables are defined to be zero there.
We next address the second term in (113). Let R i = log ( 1 − w Y i Q ( M U i ) ) ⋅ ( 1 − 1 { M U i ≤ r Q ( Y i ∣ X ) } ) R_i=\log(1-w_{Y_i}^{Q}(MU_i))\cdot(1-\mathbf{1}\{MU_i\le r^{Q}(Y_i\mid X)\}) R i = log ( 1 − w Y i Q ( M U i )) ⋅ ( 1 − 1 { M U i ≤ r Q ( Y i ∣ X )}) and write
E K , Z [ ∑ i = 1 K − 1 log ( 1 − w Y i Q ( M U i ) ) ] = E X [ E [ ∑ i = 1 K R i ∣ X ] ] = E X [ E [ K ∣ X ] E Y , U ∣ X [ ( 1 − 1 { M U ≤ r Q ( Y ∣ X ) } ) ⋅ log ( 1 − w Y Q ( M U ) ) ] ] = M E X , Y , U [ ( 1 − 1 { M U ≤ r Q ( Y ∣ X ) } ) log ( 1 − w Y Q ( M U ) ) ] = M E Y , U [ E X ∣ Y , U [ 1 − 1 { M U ≤ r Q ( Y ∣ X ) } ∣ Y , U ] ⋅ log ( 1 − w Y Q ( M U ) ) ] (119) \begin{aligned}
\mathbb{E}_{K,Z}\left[\sum_{i=1}^{K-1}\log(1-w_{Y_i}^{Q}(MU_i))\right] \\
&=\mathbb{E}_{X}\left[\mathbb{E}\left[\left.\sum_{i=1}^{K}R_i\right|X\right]\right] \\
&=\mathbb{E}_{X}\left[\mathbb{E}[K\mid X]\mathbb{E}_{Y,U\mid X}\left[(1-\mathbf{1}\{MU\le r^{Q}(Y\mid X)\})\cdot\log(1-w_Y^{Q}(MU))\right]\right] \\
&=M\mathbb{E}_{X,Y,U}\left[(1-\mathbf{1}\{MU\le r^{Q}(Y\mid X)\})\log(1-w_Y^{Q}(MU))\right] \\
&=M\mathbb{E}_{Y,U}\left[\mathbb{E}_{X\mid Y,U}\left[1-\mathbf{1}\{MU\le r^{Q}(Y\mid X)\}\mid Y,U\right]\cdot\log(1-w_Y^{Q}(MU))\right] \tag*{(119)}
\end{aligned} E K , Z [ i = 1 ∑ K − 1 log ( 1 − w Y i Q ( M U i )) ] = E X [ E [ i = 1 ∑ K R i X ] ] = E X [ E [ K ∣ X ] E Y , U ∣ X [ ( 1 − 1 { M U ≤ r Q ( Y ∣ X )}) ⋅ log ( 1 − w Y Q ( M U )) ] ] = M E X , Y , U [ ( 1 − 1 { M U ≤ r Q ( Y ∣ X )}) log ( 1 − w Y Q ( M U )) ] = M E Y , U [ E X ∣ Y , U [ 1 − 1 { M U ≤ r Q ( Y ∣ X )} ∣ Y , U ] ⋅ log ( 1 − w Y Q ( M U )) ] (119)
= M E Y , U [ ( 1 − w Y Q ( M U ) ) log ( 1 − w Y Q ( M U ) ) ] (120) =M\mathbb{E}_{Y,U}\left[(1-w_Y^{Q}(MU))\log(1-w_Y^{Q}(MU))\right] \tag*{(120)} = M E Y , U [ ( 1 − w Y Q ( M U )) log ( 1 − w Y Q ( M U )) ] (120)
≥ M E Y [ − ∫ 0 1 w Y Q ( M u ) log e d u ] = − ∫ Y ∫ 0 M w y Q ( ℓ ) log e d ℓ d Q Y ( y ) = − log e ∫ Y d P Y d Q Y d Q Y ( y ) = − log e , (121) \begin{aligned}
\ge M\mathbb{E}_{Y}\left[-\int_{0}^{1}w_Y^{Q}(Mu)\log e\,du\right] \\
&=-\int_{\mathcal{Y}}\int_{0}^{M}w_y^{Q}(\ell)\log e\,d\ell\,dQ_Y(y) \\
&=-\log e\int_{\mathcal{Y}}\frac{dP_Y}{dQ_Y}\,dQ_Y(y) \\
&=-\log e, \tag*{(121)}
\end{aligned} ≥ M E Y [ − ∫ 0 1 w Y Q ( M u ) log e d u ] = − ∫ Y ∫ 0 M w y Q ( ℓ ) log e d ℓ d Q Y ( y ) = − log e ∫ Y d Q Y d P Y d Q Y ( y ) = − log e , (121)
where in (116) we applied Tonelli’s theorem to ∑ i ≥ 1 ( − R i ) 1 [ K ≥ i ] \sum_{i\ge1}(-R_i)\mathbf{1}[K\ge i] ∑ i ≥ 1 ( − R i ) 1 [ K ≥ i ] (given X X X , the R i R_i R i are identically distributed and R i R_i R i is independent of { K ≥ i } \{K\ge i\} { K ≥ i } ) and the fact that ∑ i ≥ 1 P ( K ≥ i ∣ X ) = E [ K ∣ X ] \sum_{i\ge1}\mathbb{P}(K\ge i\mid X)=\mathbb{E}[K\mid X] ∑ i ≥ 1 P ( K ≥ i ∣ X ) = E [ K ∣ X ] . Equation (117) follows from the definition of w y Q w_y^{Q} w y Q . Equation (118) follows using the inequality ( 1 − x ) log ( 1 − x ) ≥ − x log e (1-x)\log(1-x)\ge-x\log e ( 1 − x ) log ( 1 − x ) ≥ − x log e . Combining (113), (115), and the above inequality completes the proof.
Given Z Z Z , the decoder knows the acceptance sets S i = { x ∈ X : d P Y ∣ X d Q Y ( Y i ∣ x ) ≥ M U i } S_i=\left\{x\in\mathcal{X}:\frac{dP_{Y\mid X}}{dQ_Y}(Y_i\mid x)\ge MU_i\right\} S i = { x ∈ X : d Q Y d P Y ∣ X ( Y i ∣ x ) ≥ M U i } illustrated in Figure 2 . The acceptance test is
Figure 2. Acceptance regions for Y = X + N Y=X+N Y = X + N , with X ∼ N ( 0 , 0.75 ) X\sim\mathcal{N}(0,0.75) X ∼ N ( 0 , 0.75 ) and N ∼ N ( 0 , 0.25 ) N\sim\mathcal{N}(0,0.25) N ∼ N ( 0 , 0.25 ) ; X X X and Y Y Y are truncated to ensure a bounded density ratio. For x = − 0.5 x=-0.5 x = − 0.5 , proposals Y 1 = 0.3 Y_1=0.3 Y 1 = 0.3 , Y 2 = − 0.4 Y_2=-0.4 Y 2 = − 0.4 have heights L 1 = 1.5 L_1=1.5 L 1 = 1.5 , L 2 = 1.1 L_2=1.1 L 2 = 1.1 , where L i ≜ M U i L_i\triangleq MU_i L i ≜ M U i . Since x ∉ S 1 x\notin S_1 x ∈ / S 1 and x ∈ S 2 x\in S_2 x ∈ S 2 , the first proposal is rejected and the second accepted. Each S i S_i S i has P X P_X P X -probability w Y i ( L i ) w_{Y_i}(L_i) w Y i ( L i ) .
M U i ≤ d P Y ∣ X d Q Y ( Y i ∣ x ) . (122) MU_i\le\frac{dP_{Y\mid X}}{dQ_Y}(Y_i\mid x). \tag*{(122)} M U i ≤ d Q Y d P Y ∣ X ( Y i ∣ x ) . (122)
Although the decoder does not know x x x , it can compute the marginal acceptance probability
P X ( d P Y ∣ X d Q Y ( Y i ∣ X ) ≥ M U i ) = w Y i Q ( M U i ) . (123) P_X\left(\frac{dP_{Y\mid X}}{dQ_Y}(Y_i\mid X)\ge MU_i\right)=w_{Y_i}^{Q}(MU_i). \tag*{(123)} P X ( d Q Y d P Y ∣ X ( Y i ∣ X ) ≥ M U i ) = w Y i Q ( M U i ) . (123)
Since K = k K=k K = k precisely when x ∈ S k x\in S_k x ∈ S k and x ∉ S i x\notin S_i x ∈ / S i for i < k i<k i < k , the exact conditional distribution is
P K ∣ Z ( k ∣ z ) = P X ( S k ∖ ⋃ i = 1 k − 1 S i ) . (124) P_{K\mid Z}(k\mid z)=P_X\left(S_k\setminus\bigcup_{i=1}^{k-1}S_i\right). \tag*{(124)} P K ∣ Z ( k ∣ z ) = P X ( S k ∖ i = 1 ⋃ k − 1 S i ) . (124)
The coding distribution Q K ∣ Z Q_{K|Z} Q K ∣ Z avoids computing these set differences by treating the accept/reject decisions as independent. The functional information lower bound implies that using the exact conditional distribution can reduce the cross-entropy by at most log e \log e log e bits.
The uniform bound in Theorem 6 allows the proposal to be chosen to minimize the expected number of proposals. With the smallest admissible rejection bound M M M , this expectation is
E [ K ] = ess sup ( x , y ) ∼ P X ⊗ Q Y d P Y ∣ X d Q Y ( y ∣ x ) . (125) \mathbb{E}[K]=\mathop{\operatorname{ess\,sup}}_{(x,y)\sim P_X\otimes Q_Y}\frac{\mathrm{d}P_{Y|X}}{\mathrm{d}Q_Y}(y\mid x). \tag*{(125)} E [ K ] = ess sup ( x , y ) ∼ P X ⊗ Q Y d Q Y d P Y ∣ X ( y ∣ x ) . (125)
Minimizing (125) over proposals dominating P Y ∣ X = x P_{Y|X=x} P Y ∣ X = x for P X P_X P X -a.e. x x x gives the essential-supremum form of the Shtarkov solution [25 ] , [43 ] :
min Q Y ess sup ( x , y ) ∼ P X ⊗ Q Y d P Y ∣ X d Q Y ( y ∣ x ) = E Y ∼ P Y [ ess sup x ∼ P X d P Y ∣ X d P Y ( Y ∣ x ) ] ≜ M ∗ . (126) \min_{Q_Y}\mathop{\operatorname{ess\,sup}}_{(x,y)\sim P_X\otimes Q_Y}\frac{\mathrm{d}P_{Y|X}}{\mathrm{d}Q_Y}(y\mid x)=\mathbb{E}_{Y\sim P_Y}\left[\mathop{\operatorname{ess\,sup}}_{x\sim P_X}\frac{\mathrm{d}P_{Y|X}}{\mathrm{d}P_Y}(Y\mid x)\right]\triangleq M^*. \tag*{(126)} Q Y min ess sup ( x , y ) ∼ P X ⊗ Q Y d Q Y d P Y ∣ X ( y ∣ x ) = E Y ∼ P Y [ ess sup x ∼ P X d P Y d P Y ∣ X ( Y ∣ x ) ] ≜ M ∗ . (126)
When M ∗ < ∞ M^*<\infty M ∗ < ∞ , the unique minimizing proposal is the Shtarkov distribution Q Y ∗ Q_Y^* Q Y ∗ , defined for any σ \sigma σ -finite dominating measure ν \nu ν with P Y ∣ X = x ≪ ν P_{Y|X=x}\ll\nu P Y ∣ X = x ≪ ν P X P_X P X -a.s. by
d Q Y ∗ d ν ( y ) = ess sup x ∼ P X d P Y ∣ X d ν ( y ∣ x ) ∫ ess sup x ∼ P X d P Y ∣ X d ν ( y ∣ x ) d ν ( y ) . (127) \frac{\mathrm{d}Q_Y^*}{\mathrm{d}\nu}(y)=\frac{\mathop{\operatorname{ess\,sup}}_{x\sim P_X}\frac{\mathrm{d}P_{Y|X}}{\mathrm{d}\nu}(y\mid x)}{\int\mathop{\operatorname{ess\,sup}}_{x\sim P_X}\frac{\mathrm{d}P_{Y|X}}{\mathrm{d}\nu}(y\mid x)\,\mathrm{d}\nu(y)}. \tag*{(127)} d ν d Q Y ∗ ( y ) = ∫ ess sup x ∼ P X d ν d P Y ∣ X ( y ∣ x ) d ν ( y ) ess sup x ∼ P X d ν d P Y ∣ X ( y ∣ x ) . (127)
Thus M ∗ < ∞ M^*<\infty M ∗ < ∞ guarantees an admissible proposal with rejection bound M ∗ M^* M ∗ and yields the following result.
Proposition 12 (Shtarkov distribution is optimal for rejection sampling). Let P X , Y P_{X,Y} P X , Y be such that the Shtarkov integral M ∗ M^* M ∗ of P Y ∣ X P_{Y|X} P Y ∣ X , as given in (126) , is finite. Then, the expected number of proposals in rejection sampling is Poisson functional representation ed by setting Z = { ( Y i , U i ) } i ≥ 1 ∼ i . i . d . Q Y ∗ ⊗ Unif ( 0 , 1 ) Z=\{(Y_i,U_i)\}_{i\geq1}\mathrel{\overset{\mathrm{i.i.d.}}{\sim}}Q_Y^*\otimes\operatorname{Unif}(0,1) Z = {( Y i , U i ) } i ≥ 1 ∼ i.i.d. Q Y ∗ ⊗ Unif ( 0 , 1 ) , for Q Y ∗ Q_Y^* Q Y ∗ defined in (127) . With Z ⊥ X Z\perp X Z ⊥ X and rejection bound M = M ∗ M=M^* M = M ∗ ,
E [ K ] = E Y ∼ P Y [ ess sup x ∼ P X d P Y ∣ X d P Y ( Y ∣ x ) ] , (128) \mathbb{E}[K]=\mathbb{E}_{Y\sim P_Y}\left[\mathop{\operatorname{ess\,sup}}_{x\sim P_X}\frac{\mathrm{d}P_{Y|X}}{\mathrm{d}P_Y}(Y\mid x)\right], \tag*{(128)} E [ K ] = E Y ∼ P Y [ ess sup x ∼ P X d P Y d P Y ∣ X ( Y ∣ x ) ] , (128) and H ( Y ∣ Z ) ≤ I F ( X → Y ) + log e H(Y\mid Z)\leq I_F(X\to Y)+\log e H ( Y ∣ Z ) ≤ I F ( X → Y ) + log e .
Ring Toss Code for Greedy Poisson Rejection Sampling
Let X , Y ∼ P X , Y X,Y\sim P_{X,Y} X , Y ∼ P X , Y and consider
r ( y ∣ x ) = d P Y ∣ X d P Y ( y ∣ x ) , r(y\mid x)=\frac{\mathrm{d}P_{Y|X}}{\mathrm{d}P_Y}(y\mid x), r ( y ∣ x ) = d P Y d P Y ∣ X ( y ∣ x ) ,
w y ( h ) = P X ∼ P X [ r ( y ∣ X ) ≥ h ] , w_y(h)=\mathbb{P}_{X\sim P_X}[r(y\mid X)\geq h], w y ( h ) = P X ∼ P X [ r ( y ∣ X ) ≥ h ] ,
w x ( h ) = P Y ∼ P Y [ r ( Y ∣ x ) ≥ h ] . w^x(h)=\mathbb{P}_{Y\sim P_Y}[r(Y\mid x)\geq h]. w x ( h ) = P Y ∼ P Y [ r ( Y ∣ x ) ≥ h ] .
Let G x ( h ) = ∫ h ∞ w x ( η ) d η G_x(h)=\int_h^\infty w^x(\eta)\,\mathrm{d}\eta G x ( h ) = ∫ h ∞ w x ( η ) d η . Then, define
σ x ( h ) ≜ ∫ 0 h 1 G x ( η ) d η . \sigma^x(h)\triangleq\int_0^h\frac{1}{G_x(\eta)}\,\mathrm{d}\eta. σ x ( h ) ≜ ∫ 0 h G x ( η ) 1 d η .
We take σ x ( h ) = + ∞ \sigma^{x}(h)=+\infty σ x ( h ) = + ∞ when G x ( h ) = 0 G_{x}(h)=0 G x ( h ) = 0 . Let Z = { ( Y k , T k ) } k = 1 ∞ Z=\{(Y_{k},T_{k})\}_{k=1}^{\infty} Z = {( Y k , T k ) } k = 1 ∞ be a Poisson process independent of X X X with mean measure P Y ⊗ λ P_{Y}\otimes\lambda P Y ⊗ λ , indexed in increasing order of T k T_{k} T k , where λ \lambda λ is Lebesgue measure on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) . Then, greedy Poisson rejection sampling (GPRS) returns [23 ]
K ( x , Z ) ≜ min { k ∈ N ∣ T k ≤ σ x ( r ( Y k ∣ x ) ) } . K(x,Z)\triangleq\min\{k\in\mathbb{N}\mid T_{k}\leq\sigma^{x}(r(Y_{k}\mid x))\}. K ( x , Z ) ≜ min { k ∈ N ∣ T k ≤ σ x ( r ( Y k ∣ x ))} .
We write K x = K ( x , Z ) K_{x}=K(x,Z) K x = K ( x , Z ) and K = K ( X , Z ) K=K(X,Z) K = K ( X , Z ) . For P X P_{X} P X -a.e. x x x , Y K x ∼ P Y ∣ X = x Y_{K_{x}}\sim P_{Y\mid X=x} Y K x ∼ P Y ∣ X = x (see [7 ] , [23 ] ). Write Y = Y K Y=Y_{K} Y = Y K for the simulated output and S x ( t ) = P [ T K x ≥ t ] S_{x}(t)=\mathbb{P}[T_{K_{x}}\geq t] S x ( t ) = P [ T K x ≥ t ] . The joint density of the first accepted point is
d P Y K , T K ∣ X d P Y ⊗ λ ( y , t ∣ x ) = 1 [ t ≤ σ x ( r ( y ∣ x ) ) ] S x ( t ) . \frac{dP_{Y_{K},T_{K}\mid X}}{dP_{Y}\otimes\lambda}(y,t\mid x)=\mathbb{1}[t\leq\sigma^{x}(r(y\mid x))]S_{x}(t). d P Y ⊗ λ d P Y K , T K ∣ X ( y , t ∣ x ) = 1 [ t ≤ σ x ( r ( y ∣ x ))] S x ( t ) .
where S x ( t ) = G x ( ( σ x ) − 1 ( t ) ) S_{x}(t)=G_{x}((\sigma^{x})^{-1}(t)) S x ( t ) = G x (( σ x ) − 1 ( t )) by [23 Appendix A, Eq. (50)] . From this, we can easily work out the conditional distribution of T K ∣ Y K , X T_{K}\mid Y_{K},X T K ∣ Y K , X :
d P Y K , T K ∣ X d P Y ⊗ λ ( y , t ∣ x ) = d P Y K , T K ∣ X d P Y K ∣ X ⊗ λ ( y , t ∣ x ) ⋅ d P Y K ∣ X d P Y ( y ∣ x ) = d P T K ∣ Y K , X d λ ( t ∣ y , x ) ⋅ r ( y ∣ x ) . \begin{aligned}
\frac{dP_{Y_{K},T_{K}\mid X}}{dP_{Y}\otimes\lambda}(y,t\mid x)=\frac{dP_{Y_{K},T_{K}\mid X}}{dP_{Y_{K}\mid X}\otimes\lambda}(y,t\mid x)\cdot\frac{dP_{Y_{K}\mid X}}{dP_{Y}}(y\mid x) \\
&=\frac{dP_{T_{K}\mid Y_{K},X}}{d\lambda}(t\mid y,x)\cdot r(y\mid x).
\end{aligned} d P Y ⊗ λ d P Y K , T K ∣ X ( y , t ∣ x ) = d P Y K ∣ X ⊗ λ d P Y K , T K ∣ X ( y , t ∣ x ) ⋅ d P Y d P Y K ∣ X ( y ∣ x ) = d λ d P T K ∣ Y K , X ( t ∣ y , x ) ⋅ r ( y ∣ x ) .
Hence, for P X , Y P_{X,Y} P X , Y -a.e. ( x , y ) (x,y) ( x , y ) , where r ( y ∣ x ) > 0 r(y\mid x)>0 r ( y ∣ x ) > 0 ,
d P T K ∣ Y K , X d λ ( t ∣ y , x ) = 1 [ t ≤ σ x ( r ( y ∣ x ) ) ] r ( y ∣ x ) S x ( t ) . \frac{dP_{T_{K}\mid Y_{K},X}}{d\lambda}(t\mid y,x)=\frac{\mathbb{1}[t\leq\sigma^{x}(r(y\mid x))]}{r(y\mid x)}S_{x}(t). d λ d P T K ∣ Y K , X ( t ∣ y , x ) = r ( y ∣ x ) 1 [ t ≤ σ x ( r ( y ∣ x ))] S x ( t ) .
For t > 0 t>0 t > 0 , taking expectation with respect to P X ∣ Y = y P_{X\mid Y=y} P X ∣ Y = y gives
d P T K ∣ Y d λ ( t ∣ y ) = E X ∼ P X ∣ Y = y [ 1 [ t ≤ σ X ( r ( y ∣ X ) ) ] r ( y ∣ X ) S X ( t ) ] = E X ∼ P X [ 1 [ t ≤ σ X ( r ( y ∣ X ) ) ] S X ( t ) ] . \begin{aligned}
\frac{dP_{T_{K}\mid Y}}{d\lambda}(t\mid y)
=\mathbb{E}_{X\sim P_{X\mid Y=y}}\left[\frac{\mathbb{1}[t\leq\sigma^{X}(r(y\mid X))]}{r(y\mid X)}S_{X}(t)\right] \\
&=\mathbb{E}_{X\sim P_{X}}\left[\mathbb{1}[t\leq\sigma^{X}(r(y\mid X))]S_{X}(t)\right].
\end{aligned} d λ d P T K ∣ Y ( t ∣ y ) = E X ∼ P X ∣ Y = y [ r ( y ∣ X ) 1 [ t ≤ σ X ( r ( y ∣ X ))] S X ( t ) ] = E X ∼ P X [ 1 [ t ≤ σ X ( r ( y ∣ X ))] S X ( t ) ] .
For convenience, let f ( t ∣ y ) = d P T K ∣ Y d λ ( t ∣ y ) f(t\mid y)=\frac{dP_{T_{K}\mid Y}}{d\lambda}(t\mid y) f ( t ∣ y ) = d λ d P T K ∣ Y ( t ∣ y ) . Now, put
ζ ( Z ) ≜ ∑ ( Y , T ) ∈ Z f ( T ∣ Y ) , \zeta(Z)\triangleq\sum_{(Y,T)\in Z}f(T\mid Y), ζ ( Z ) ≜ ( Y , T ) ∈ Z ∑ f ( T ∣ Y ) ,
Q K ∣ Z ( k ) ≜ f ( T k ∣ Y k ) ζ ( Z ) . Q_{K\mid Z}(k)\triangleq\frac{f(T_{k}\mid Y_{k})}{\zeta(Z)}. Q K ∣ Z ( k ) ≜ ζ ( Z ) f ( T k ∣ Y k ) .
Since T K T_{K} T K given Y K = y Y_{K}=y Y K = y has PDF f ( ⋅ ∣ y ) f(\cdot\mid y) f ( ⋅ ∣ y ) , we have ζ ( Z ) ≥ f ( T K ∣ Y K ) > 0 \zeta(Z)\geq f(T_{K}\mid Y_{K})>0 ζ ( Z ) ≥ f ( T K ∣ Y K ) > 0 a.s. Also, ζ ( Z ) < ∞ \zeta(Z)<\infty ζ ( Z ) < ∞ a.s., because
E [ ζ ( Z ) ] = E [ ∑ ( Y , T ) ∈ Z f ( T ∣ Y ) ] = ∫ ∫ 0 ∞ f ( t ∣ y ) d t d P Y ( y ) (Campbell) = 1. ( f is a PDF in t ) \begin{aligned}
\mathbb{E}[\zeta(Z)]=\mathbb{E}\left[\sum_{(Y,T)\in Z}f(T\mid Y)\right] \\
&=\int\int_{0}^{\infty}f(t\mid y)\,dt\,dP_{Y}(y) \qquad\text{(Campbell)} \\
&=1. \qquad\text{(}f\text{ is a PDF in }t\text{)}
\end{aligned} E [ ζ ( Z )] = E ( Y , T ) ∈ Z ∑ f ( T ∣ Y ) = ∫ ∫ 0 ∞ f ( t ∣ y ) d t d P Y ( y ) (Campbell) = 1. ( f is a PDF in t )
Thus, Q K ∣ Z Q_{K\mid Z} Q K ∣ Z is a proper probability distribution. Furthermore,
H ( P K ∣ Z ; Q K ∣ Z ) = E [ − log f ( T K ∣ Y K ) ] + E [ log ζ ( Z ) ] ≤ E [ − log f ( T K ∣ Y K ) ] (Jensen and E [ ζ ( Z ) ] = 1 ) = h ( T K ∣ Y K ) . \begin{aligned}
H(P_{K\mid Z};Q_{K\mid Z})=\mathbb{E}[-\log f(T_{K}\mid Y_{K})]+\mathbb{E}[\log\zeta(Z)] \\
&\leq\mathbb{E}[-\log f(T_{K}\mid Y_{K})] \qquad\text{(Jensen and }\mathbb{E}[\zeta(Z)]=1\text{)} \\
&=h(T_{K}\mid Y_{K}).
\end{aligned} H ( P K ∣ Z ; Q K ∣ Z ) = E [ − log f ( T K ∣ Y K )] + E [ log ζ ( Z )] ≤ E [ − log f ( T K ∣ Y K )] (Jensen and E [ ζ ( Z )] = 1 ) = h ( T K ∣ Y K ) .
Put H x = ( σ x ) − 1 ( T K x ) H_{x}=(\sigma^{x})^{-1}(T_{K_{x}}) H x = ( σ x ) − 1 ( T K x ) . In the joint density of ( Y K , T K ) (Y_{K},T_{K}) ( Y K , T K ) given X = x X=x X = x , change variables from t t t to h h h via t = σ x ( h ) t=\sigma^{x}(h) t = σ x ( h ) . Since S x ( σ x ( h ) ) ( σ x ) ′ ( h ) = 1 S_{x}(\sigma^{x}(h))(\sigma^{x})'(h)=1 S x ( σ x ( h )) ( σ x ) ′ ( h ) = 1 for G x ( h ) > 0 G_{x}(h)>0 G x ( h ) > 0 , we obtain
P Y K , H X ∣ X = x ( d y , d h ) = 1 [ 0 < h ≤ r ( y ∣ x ) ] P Y ( d y ) d h . P_{Y_{K},H_{X}\mid X=x}(dy,dh)=\mathbb{1}[0<h\leq r(y\mid x)]P_{Y}(dy)\,dh. P Y K , H X ∣ X = x ( d y , d h ) = 1 [ 0 < h ≤ r ( y ∣ x )] P Y ( d y ) d h .
Integrating out y y y or x x x , respectively, shows that H X H_{X} H X given X = x X=x X = x has PDF w x w^{x} w x , and H X H_{X} H X given Y = y Y=y Y = y has PDF w y w_{y} w y . Since G x ≤ 1 G_{x}\leq1 G x ≤ 1 is nonincreasing,
H X ≤ T K = σ X ( H X ) ≤ H X ⋅ ( σ X ) ′ ( H X ) = H X G X ( H X ) . \begin{aligned}
H_{X}\leq T_{K}=\sigma^{X}(H_{X}) \\
&\le H_X \cdot(\sigma^X)'(H_X)
= \frac{H_X}{G_X(H_X)}.
\end{aligned} H X ≤ T K = σ X ( H X ) ≤ H X ⋅ ( σ X ) ′ ( H X ) = G X ( H X ) H X .
By the probability integral transform, G X ( H X ) G_X(H_X) G X ( H X ) given X X X is uniform on ( 0 , 1 ) (0,1) ( 0 , 1 ) . To construct a comparison density, let U ∼ Unif ( 0 , 1 ) U \sim\operatorname{Unif}(0,1) U ∼ Unif ( 0 , 1 ) be independent of ( H X , Y ) (H_X,Y) ( H X , Y ) and put A = H X / U A=H_X/U A = H X / U . Let g ( a ∣ y ) g(a\mid y) g ( a ∣ y ) denote the PDF of A ∣ Y = y A\mid Y=y A ∣ Y = y . Then, one can find that
g ( a ∣ y ) ≜ 1 a 2 ∫ 0 a h w y ( h ) d h . g(a\mid y) \triangleq\frac{1}{a^2}\int_0^a h w_y(h)\,\mathrm{d}h. g ( a ∣ y ) ≜ a 2 1 ∫ 0 a h w y ( h ) d h .
At y = Y K y=Y_K y = Y K , we have
g ( T K ∣ y ) = 1 T K 2 ∫ 0 T K h w y ( h ) d h ≥ 1 T K 2 ∫ 0 H X h w y ( h ) d h ≥ w y ( H X ) T K 2 ∫ 0 H X h d h = w y ( H X ) 2 ⋅ ( H X T K ) 2 ≥ 1 2 w y ( H X ) G X ( H X ) 2 . \begin{aligned}
g(T_K\mid y)=\frac{1}{T_K^2}\int_0^{T_K}h w_y(h)\,\mathrm{d}h \\
&\ge\frac{1}{T_K^2}\int_0^{H_X}h w_y(h)\,\mathrm{d}h \\
&\ge\frac{w_y(H_X)}{T_K^2}\int_0^{H_X}h\,\mathrm{d}h \\
&= \frac{w_y(H_X)}{2}\cdot\left(\frac{H_X}{T_K}\right)^2 \\
&\ge\frac{1}{2}w_y(H_X)G_X(H_X)^2.
\end{aligned} g ( T K ∣ y ) = T K 2 1 ∫ 0 T K h w y ( h ) d h ≥ T K 2 1 ∫ 0 H X h w y ( h ) d h ≥ T K 2 w y ( H X ) ∫ 0 H X h d h = 2 w y ( H X ) ⋅ ( T K H X ) 2 ≥ 2 1 w y ( H X ) G X ( H X ) 2 .
Finally, from this we get that
h ( T K ∣ Y K ) ≤ E [ − log g ( T K ∣ Y K ) ] ≤ E [ − log w Y ( H X ) ] − 2 E [ log G X ( H X ) ] + 1 = h ( H X ∣ Y K ) + 2 log e + 1 = I F ( X → Y ) + 2 log e + 1. \begin{aligned}
h(T_K\mid Y_K)\le\mathbb{E}[-\log g(T_K\mid Y_K)] \\
&\le\mathbb{E}[-\log w_Y(H_X)]-2\mathbb{E}[\log G_X(H_X)]+1 \\
&=h(H_X\mid Y_K)+2\log e+1 \\
&=I_F(X\to Y)+2\log e+1.
\end{aligned} h ( T K ∣ Y K ) ≤ E [ − log g ( T K ∣ Y K )] ≤ E [ − log w Y ( H X )] − 2 E [ log G X ( H X )] + 1 = h ( H X ∣ Y K ) + 2 log e + 1 = I F ( X → Y ) + 2 log e + 1.
This shows that
H ( P K ∣ Z ; Q K ∣ Z ) ≤ I F ( X → Y ) + 2 log e + 1. H(P_{K\mid Z};Q_{K\mid Z})\le I_F(X\to Y)+2\log e+1. H ( P K ∣ Z ; Q K ∣ Z ) ≤ I F ( X → Y ) + 2 log e + 1.
A Shannon-Fano code for Q K ∣ Z Q_{K\mid Z} Q K ∣ Z therefore has expected length less than I F ( X → Y ) + 2 log e + 2 I_F(X\to Y)+2\log e+2 I F ( X → Y ) + 2 log e + 2 .
Rényi Generalization Proofs
Proof of Proposition 10.
Nonnegativity. By Proposition 11, I F , α ( X → Y ) ≥ I 1 / α S ( X ; Y ) ≥ 0 I_{F,\alpha}(X\to Y)\ge I^{\mathrm{S}}_{1/\alpha}(X;Y)\ge0 I F , α ( X → Y ) ≥ I 1/ α S ( X ; Y ) ≥ 0 , and the Sibson information vanishes only when X X X and Y Y Y are independent [39 Theorem 4.1] , in which case the channel is singular, so equality holds throughout.
Recovers I F I_F I F as α → 1 \alpha\to1 α → 1 . Let V V V given Y = y Y=y Y = y have density w y w_y w y , and put B = − log w Y ( V ) B=-\log w_Y(V) B = − log w Y ( V ) . Then I F , 1 − s ( X → Y ) = log E [ 2 s B ] I_{F,1-s}(X\to Y)=\log\mathbb{E}[2^{sB}] I F , 1 − s ( X → Y ) = log E [ 2 s B ] for 0 < s < 1 0<s<1 0 < s < 1 . By hypothesis, E [ 2 ( 1 − α 0 ) B ] < ∞ \mathbb{E}[2^{(1-\alpha_0)B}]<\infty E [ 2 ( 1 − α 0 ) B ] < ∞ , so differentiating log E [ 2 s B ] \log\mathbb{E}[2^{sB}] log E [ 2 s B ] at s = 0 s=0 s = 0 gives the limit E [ B ] = I F ( X → Y ) \mathbb{E}[B]=I_F(X\to Y) E [ B ] = I F ( X → Y ) .
Self-information. For X X X discrete, fix x x x with P X ( x ) > 0 P_X(x)>0 P X ( x ) > 0 and define Q x Q_x Q x as the measure Q x ( A ) = 1 [ x ∈ A ] Q_x(A)=1[x\in A] Q x ( A ) = 1 [ x ∈ A ] . One can compute that the width function w x w_x w x between Q x Q_x Q x and P X P_X P X is given by
w x ( ℓ ) = P X ′ ∼ P X ( 1 [ X ′ = x ] P X ( X ′ ) ≥ ℓ ) = P X ( x ) 1 [ ℓ ≤ 1 P X ( x ) ] , ℓ > 0. \begin{aligned}
w_x(\ell)=\mathbb{P}_{X'\sim P_X}\left(\frac{1[X'=x]}{P_X(X')}\ge\ell\right) \\
&=P_X(x)1\left[\ell\le\frac{1}{P_X(x)}\right],\qquad\ell>0.
\end{aligned} w x ( ℓ ) = P X ′ ∼ P X ( P X ( X ′ ) 1 [ X ′ = x ] ≥ ℓ ) = P X ( x ) 1 [ ℓ ≤ P X ( x ) 1 ] , ℓ > 0.
Hence,
∫ 0 ∞ w x ( ℓ ) α d ℓ = ∫ 0 1 P X ( x ) P X ( x ) α d ℓ = P X ( x ) α − 1 , \int_0^\infty w_x(\ell)^\alpha\,\mathrm{d}\ell
=\int_0^{\frac{1}{P_X(x)}}P_X(x)^\alpha\,\mathrm{d}\ell
=P_X(x)^{\alpha-1}, ∫ 0 ∞ w x ( ℓ ) α d ℓ = ∫ 0 P X ( x ) 1 P X ( x ) α d ℓ = P X ( x ) α − 1 ,
and direct computation yields
I F , α ( X → X ) = 1 1 − α log E X [ ∫ 0 ∞ w X ( ℓ ) α d ℓ ] = 1 1 − α log E X [ P X ( X ) α − 1 ] = H α ( X ) . \begin{aligned}
I_{F,\alpha}(X\to X)=\frac{1}{1-\alpha}\log\mathbb{E}_X\left[\int_0^\infty w_X(\ell)^\alpha\,\mathrm{d}\ell\right] \\
&=\frac{1}{1-\alpha}\log\mathbb{E}_X\left[P_X(X)^{\alpha-1}\right]=H_\alpha(X).
\end{aligned} I F , α ( X → X ) = 1 − α 1 log E X [ ∫ 0 ∞ w X ( ℓ ) α d ℓ ] = 1 − α 1 log E X [ P X ( X ) α − 1 ] = H α ( X ) .
Proof of Proposition 11. Put p = 1 / α > 1 p = 1/\alpha> 1 p = 1/ α > 1 and write ∥ ⋅ ∥ p \|\cdot\|_p ∥ ⋅ ∥ p for the L p ( P X ) L^p(P_X) L p ( P X ) norm. By [39 Eq. 26] ,
I 1 / α s ( X ; Y ) = 1 1 − α log E Y [ ∥ r ( Y ∣ ⋅ ) ∥ p ] . (129) I^s_{1/\alpha}(X;Y) = \frac{1}{1-\alpha}\log\mathbb{E}_Y\left[\|r(Y\mid\cdot)\|_p\right]. \tag*{(129)} I 1/ α s ( X ; Y ) = 1 − α 1 log E Y [ ∥ r ( Y ∣ ⋅ ) ∥ p ] . (129)
For P Y P_Y P Y -a.e. y y y , the layer cake representation and Minkowski’s integral inequality give
∥ r ( y ∣ ⋅ ) ∥ p = ∥ ∫ 0 ∞ 1 [ r ( y ∣ ⋅ ) ≥ ℓ ] d ℓ ∥ p ≤ ∫ 0 ∞ ∥ 1 [ r ( y ∣ ⋅ ) ≥ ℓ ] ∥ p d ℓ = ∫ 0 ∞ w y ( ℓ ) α d ℓ . \begin{aligned}
\|r(y\mid\cdot)\|_p
&= \left\|\int_0^\infty\mathbf{1}[r(y\mid\cdot)\geq\ell]\,d\ell\right\|_p\\
&\leq\int_0^\infty\|\mathbf{1}[r(y\mid\cdot)\geq\ell]\|_p\,d\ell
= \int_0^\infty w_y(\ell)^\alpha\,d\ell.
\end{aligned} ∥ r ( y ∣ ⋅ ) ∥ p = ∫ 0 ∞ 1 [ r ( y ∣ ⋅ ) ≥ ℓ ] d ℓ p ≤ ∫ 0 ∞ ∥ 1 [ r ( y ∣ ⋅ ) ≥ ℓ ] ∥ p d ℓ = ∫ 0 ∞ w y ( ℓ ) α d ℓ .
Substitution into (126) gives (80).
If the channel is singular, then for P Y P_Y P Y -a.e. y y y the nonzero level-set indicators agree P X P_X P X -a.s. for ℓ > 0 \ell> 0 ℓ > 0 , so equality holds in Minkowski’s inequality and hence in (80). Conversely, by finiteness, equality in (80) requires equality in Minkowski’s inequality for P Y P_Y P Y -a.e. y y y . For each such y y y , almost every level-set indicator with w y ( ℓ ) > 0 w_y(\ell) > 0 w y ( ℓ ) > 0 is then proportional to r ( y ∣ ⋅ ) r(y\mid\cdot) r ( y ∣ ⋅ ) in L p ( P X ) L^p(P_X) L p ( P X ) . Hence r ( y ∣ ⋅ ) r(y\mid\cdot) r ( y ∣ ⋅ ) is equal to a constant where it is positive, up to a P X P_X P X -null set. Since E X [ r ( y ∣ X ) ] = 1 \mathbb{E}_X[r(y\mid X)] = 1 E X [ r ( y ∣ X )] = 1 , this constant is g ( y ) = 1 / P X [ r ( y ∣ X ) > 0 ] g(y) = 1/P_X[r(y\mid X) > 0] g ( y ) = 1/ P X [ r ( y ∣ X ) > 0 ] , which is measurable in y y y . This proves that the channel is singular.
Proof of Theorem 3. Let Z ⊥ X Z \perp X Z ⊥ X be such that Y = f ( X , Z ) Y = f(X,Z) Y = f ( X , Z ) and P Y ∣ Z = z P_{Y\mid Z=z} P Y ∣ Z = z is purely atomic for P Z P_Z P Z -a.e. z z z . We will show that I F , α ( X → Y ) ≤ H α A ( Y ∣ Z ) I_{F,\alpha}(X \to Y) \leq H^A_\alpha(Y\mid Z) I F , α ( X → Y ) ≤ H α A ( Y ∣ Z ) , where
H α A ( Y ∣ Z ) = α 1 − α log E Z [ ( ∑ y P Y ∣ Z ( y ∣ Z ) α ) 1 α ] . H^A_\alpha(Y\mid Z) = \frac{\alpha}{1-\alpha}\log\mathbb{E}_Z\left[\left(\sum_y P_{Y\mid Z}(y\mid Z)^\alpha\right)^{\frac{1}{\alpha}}\right]. H α A ( Y ∣ Z ) = 1 − α α log E Z ( y ∑ P Y ∣ Z ( y ∣ Z ) α ) α 1 .
is Arimoto’s conditional entropy [18 ] . Taking the infimum over these representations will give the lower bound. Following (31) in the proof of Theorem 4, we may write
∫ 0 p w y − 1 ( u ) d u ≤ ∫ Z min { p , q y ( z ) } q y ( z ) d ν y ( z ) , (130) \int_0^p w_y^{-1}(u)\,du \leq\int_{\mathcal{Z}}\frac{\min\{p,q_y(z)\}}{q_y(z)}\,d\nu_y(z), \tag*{(130)} ∫ 0 p w y − 1 ( u ) d u ≤ ∫ Z q y ( z ) min { p , q y ( z )} d ν y ( z ) , (130)
for q y ( z ) = P Y ∣ Z = z ( y ) q_y(z) = P_{Y\mid Z=z}(y) q y ( z ) = P Y ∣ Z = z ( y ) and ν y \nu_y ν y a regular conditional distribution of Z ∣ Y = y Z\mid Y=y Z ∣ Y = y . For P Y P_Y P Y -a.e. y y y , 0 < q y ( z ) ≤ 1 0 < q_y(z) \leq1 0 < q y ( z ) ≤ 1 for ν y \nu_y ν y -a.e. z z z . Extend w y − 1 ( u ) = 0 w_y^{-1}(u) = 0 w y − 1 ( u ) = 0 for u > 1 u > 1 u > 1 . The inequality then also holds for p ≥ 1 p \geq1 p ≥ 1 , since both sides equal one. Fixing such a y y y , we compute
∫ 0 ∞ α ( 1 − α ) p α − 2 ( ∫ 0 p w y − 1 ( u ) d u ) d p ≤ ∫ 0 ∞ α ( 1 − α ) p α − 2 ( ∫ Z min { p , q y ( z ) } q y ( z ) d ν y ( z ) ) d p = ∫ Z ∫ 0 ∞ α ( 1 − α ) p α − 2 ( min { p , q y ( z ) } q y ( z ) ) d p d ν y ( z ) (Tonelli) = ∫ Z q y ( z ) α − 1 d ν y ( z ) . \begin{aligned}
\int_0^\infty\alpha(1-\alpha)p^{\alpha-2}\left(\int_0^p w_y^{-1}(u)\,du\right)\,dp
&\leq\int_0^\infty\alpha(1-\alpha)p^{\alpha-2}\left(\int_{\mathcal{Z}}\frac{\min\{p,q_y(z)\}}{q_y(z)}\,d\nu_y(z)\right)\,dp\\
&= \int_{\mathcal{Z}}\int_0^\infty\alpha(1-\alpha)p^{\alpha-2}\left(\frac{\min\{p,q_y(z)\}}{q_y(z)}\right)\,dp\,d\nu_y(z) \quad\text{(Tonelli)}\\
&= \int_{\mathcal{Z}}q_y(z)^{\alpha-1}\,d\nu_y(z).
\end{aligned} ∫ 0 ∞ α ( 1 − α ) p α − 2 ( ∫ 0 p w y − 1 ( u ) d u ) d p ≤ ∫ 0 ∞ α ( 1 − α ) p α − 2 ( ∫ Z q y ( z ) min { p , q y ( z )} d ν y ( z ) ) d p = ∫ Z ∫ 0 ∞ α ( 1 − α ) p α − 2 ( q y ( z ) min { p , q y ( z )} ) d p d ν y ( z ) (Tonelli) = ∫ Z q y ( z ) α − 1 d ν y ( z ) .
Above, the final equality follows from the identity (for any q > 0 q > 0 q > 0 and α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) )
α ( 1 − α ) ∫ 0 ∞ p α − 2 min { p , q } d p = α ( 1 − α ) [ ∫ 0 q p α − 1 d p + ∫ q ∞ q p α − 2 d p ] = α ( 1 − α ) [ 1 α q α + 1 α − 1 ( − q α − 1 ) q ] = ( 1 − α ) q α + α q α = q α . \begin{aligned}
\alpha(1-\alpha)\int_0^\infty p^{\alpha-2}\min\{p,q\}\,dp
&= \alpha(1-\alpha)\left[\int_0^q p^{\alpha-1}\,dp+\int_q^\infty qp^{\alpha-2}\,dp\right]\\
&= \alpha(1-\alpha)\left[\frac{1}{\alpha}q^\alpha+\frac{1}{\alpha-1}(-q^{\alpha-1})q\right]\\
&= (1-\alpha)q^\alpha+\alpha q^\alpha\\
&=q^\alpha.
\end{aligned} α ( 1 − α ) ∫ 0 ∞ p α − 2 min { p , q } d p = α ( 1 − α ) [ ∫ 0 q p α − 1 d p + ∫ q ∞ q p α − 2 d p ] = α ( 1 − α ) [ α 1 q α + α − 1 1 ( − q α − 1 ) q ] = ( 1 − α ) q α + α q α = q α .
Then, we can compute
α ( 1 − α ) ∫ 0 ∞ p α − 2 ( ∫ 0 p w y − 1 ( u ) d u ) d p = α ( 1 − α ) ∫ 0 ∞ w y − 1 ( u ) ∫ u ∞ p α − 2 d p d u (Tonelli) = α ( 1 − α ) ∫ 0 ∞ w y − 1 ( u ) ( u α − 1 1 − α ) d u = ∫ 0 ∞ ∫ 0 w y ( ℓ ) α u α − 1 d u d ℓ = ∫ 0 ∞ w y ( ℓ ) α d ℓ . \begin{aligned}
\alpha(1-\alpha)\int_0^\infty p^{\alpha-2}\left(\int_0^p w_y^{-1}(u)\,du\right)\,dp
&= \alpha(1-\alpha)\int_0^\infty w_y^{-1}(u)\int_u^\infty p^{\alpha-2}\,dp\,du \quad\text{(Tonelli)} \\
&= \alpha(1-\alpha)\int_{0}^{\infty} w_y^{-1}(u)\left(\frac{u^{\alpha-1}}{1-\alpha}\right)\,du \\
&= \int_{0}^{\infty}\int_{0}^{w_y(\ell)} \alpha u^{\alpha-1}\,du\,d\ell\\
&= \int_{0}^{\infty} w_y(\ell)^\alpha\,d\ell.
\end{aligned} α ( 1 − α ) ∫ 0 ∞ p α − 2 ( ∫ 0 p w y − 1 ( u ) d u ) d p = α ( 1 − α ) ∫ 0 ∞ w y − 1 ( u ) ∫ u ∞ p α − 2 d p d u (Tonelli) = α ( 1 − α ) ∫ 0 ∞ w y − 1 ( u ) ( 1 − α u α − 1 ) d u = ∫ 0 ∞ ∫ 0 w y ( ℓ ) α u α − 1 d u d ℓ = ∫ 0 ∞ w y ( ℓ ) α d ℓ .
Together, we have shown the pointwise bound
∫ 0 ∞ w y ( ℓ ) α d ℓ ≤ ∫ Z q y ( z ) α − 1 d ν y ( z ) . (131) \int_{0}^{\infty} w_y(\ell)^\alpha\,d\ell\leq\int_{\mathcal{Z}} q_y(z)^{\alpha-1}\,d\nu_y(z). \tag*{(131)} ∫ 0 ∞ w y ( ℓ ) α d ℓ ≤ ∫ Z q y ( z ) α − 1 d ν y ( z ) . (131)
Integration with respect to P Y P_Y P Y , taking logarithms, and dividing by 1 − α > 0 1-\alpha>0 1 − α > 0 (all of which preserve the inequality) give that
I F , α ( X → Y ) = 1 1 − α log E Y [ ∫ 0 ∞ w Y ( ℓ ) α d ℓ ] ≤ 1 1 − α log ∫ Y ∫ Z q y ( z ) α − 1 ν y ( d z ) d P Y ( y ) = 1 1 − α log E Z [ ∑ y q y ( Z ) α ] = α 1 − α log [ E Z [ ( ∑ y q y ( Z ) α ) 1 / α ] ] ≤ α 1 − α log E Z [ ( ∑ y q y ( Z ) α ) 1 / α ] = H α A ( Y ∣ Z ) , \begin{aligned}
I_{F,\alpha}(X\to Y)
&= \frac{1}{1-\alpha}\log\mathbb{E}_Y\left[\int_{0}^{\infty}w_Y(\ell)^\alpha\,d\ell\right]\\
&\leq\frac{1}{1-\alpha}\log\int_{\mathcal{Y}}\int_{\mathcal{Z}}q_y(z)^{\alpha-1}\nu_y(dz)\,dP_Y(y)\\
&= \frac{1}{1-\alpha}\log\mathbb{E}_Z\left[\sum_y q_y(Z)^\alpha\right]\\
&= \frac{\alpha}{1-\alpha}\log\left[\mathbb{E}_Z\left[\left(\sum_y q_y(Z)^\alpha\right)^{1/\alpha}\right]\right]\\
&\leq\frac{\alpha}{1-\alpha}\log\mathbb{E}_Z\left[\left(\sum_y q_y(Z)^\alpha\right)^{1/\alpha}\right]\\
&= H_\alpha^A(Y\mid Z),
\end{aligned} I F , α ( X → Y ) = 1 − α 1 log E Y [ ∫ 0 ∞ w Y ( ℓ ) α d ℓ ] ≤ 1 − α 1 log ∫ Y ∫ Z q y ( z ) α − 1 ν y ( d z ) d P Y ( y ) = 1 − α 1 log E Z [ y ∑ q y ( Z ) α ] = 1 − α α log E Z ( y ∑ q y ( Z ) α ) 1/ α ≤ 1 − α α log E Z ( y ∑ q y ( Z ) α ) 1/ α = H α A ( Y ∣ Z ) ,
where the inequality follows since x ↦ x 1 / α x\mapsto x^{1/\alpha} x ↦ x 1/ α is convex if α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) . We now turn to showing the upper bound in (14). Specifically, for Z = { ( Y i , T i ) } i ≥ 1 Z=\{(Y_i,T_i)\}_{i\geq1} Z = {( Y i , T i ) } i ≥ 1 the Poisson process independent of X X X with intensity measure Q Y ⊗ λ Q_Y\otimes\lambda Q Y ⊗ λ , where P Y ∣ X = x ≪ Q Y P_{Y\mid X=x}\ll Q_Y P Y ∣ X = x ≪ Q Y for P X P_X P X -a.e. x x x , we will show that the output Y = Y K Y=Y_K Y = Y K of the Poisson functional representation in Theorem 5 satisfies
H α A ( Y ∣ Z ) ≤ I F , α ( X → Y ) + 1 − α α + log ( 1 / α ) 1 − α . (132) H_\alpha^A(Y\mid Z)\leq I_{F,\alpha}(X\to Y)+\frac{1-\alpha}{\alpha}+\frac{\log(1/\alpha)}{1-\alpha}. \tag*{(132)} H α A ( Y ∣ Z ) ≤ I F , α ( X → Y ) + α 1 − α + 1 − α log ( 1/ α ) . (132)
This gives the upper bound since R α ∗ ( X → Y ) ≤ H α A ( Y ∣ Z ) R_\alpha^*(X\to Y)\leq H_\alpha^A(Y\mid Z) R α ∗ ( X → Y ) ≤ H α A ( Y ∣ Z ) .
Multiplying both sides of (132) by 1 − α > 0 1-\alpha>0 1 − α > 0 and exponentiating, this inequality is equivalent to
( E Z ∥ P Y ∣ Z ∥ α ) α ≤ 2 ( 1 − α ) 2 / α α 2 ( 1 − α ) I F , α ( X → Y ) , (133) \left(\mathbb{E}_Z\left\|P_{Y\mid Z}\right\|_\alpha\right)^\alpha
\leq\frac{2^{(1-\alpha)^2/\alpha}}{\alpha}2^{(1-\alpha)I_{F,\alpha}(X\to Y)}, \tag*{(133)} ( E Z P Y ∣ Z α ) α ≤ α 2 ( 1 − α ) 2 / α 2 ( 1 − α ) I F , α ( X → Y ) , (133)
Here ∥ P ∥ α = ( ∑ u P ( u ) α ) 1 / α \|P\|_\alpha=\left(\sum_u P(u)^\alpha\right)^{1/\alpha} ∥ P ∥ α = ( ∑ u P ( u ) α ) 1/ α for a purely atomic P P P , with the sum over its atoms. By subadditivity of x ↦ x α x\mapsto x^\alpha x ↦ x α , for P Z P_Z P Z -a.e. z z z we have
∥ P Y ∣ Z = z ∥ α ≤ ∥ P K ∣ Z = z ∥ α . (134) \left\|P_{Y\mid Z=z}\right\|_\alpha\leq\left\|P_{K\mid Z=z}\right\|_\alpha. \tag*{(134)} P Y ∣ Z = z α ≤ P K ∣ Z = z α . (134)
As we do not know that E Z ∥ P K ∣ Z ∥ α \mathbb{E}_Z\|P_{K\mid Z}\|_\alpha E Z ∥ P K ∣ Z ∥ α is finite a priori, fix L > 0 L>0 L > 0 and write ∥ P K ∣ Z ∥ α ∧ L = min { ∥ P K ∣ Z ∥ α , L } \|P_{K\mid Z}\|_\alpha\wedge L=\min\{\|P_{K\mid Z}\|_\alpha,L\} ∥ P K ∣ Z ∥ α ∧ L = min { ∥ P K ∣ Z ∥ α , L } . Then,
E Z [ ∥ P K ∣ Z ∥ α ∧ L ] ≤ E Z [ ∥ P K ∣ Z ∥ α α ( ∥ P K ∣ Z ∥ α ∧ L ) 1 − α ] = E Z [ ∑ k P K ∣ Z ( k ∣ Z ) α ( ∥ P K ∣ Z ∥ α ∧ L ) 1 − α ] . (135) \begin{aligned}
\mathbb{E}_Z\left[\|P_{K\mid Z}\|_\alpha\wedge L\right]
&\leq\mathbb{E}_Z\left[\|P_{K\mid Z}\|_\alpha^\alpha\left(\|P_{K\mid Z}\|_\alpha\wedge L\right)^{1-\alpha}\right]\\
&=\mathbb{E}_Z\left[\sum_k P_{K\mid Z}(k\mid Z)^\alpha\left(\|P_{K\mid Z}\|_\alpha\wedge L\right)^{1-\alpha}\right]. \tag*{(135)}
\end{aligned} E Z [ ∥ P K ∣ Z ∥ α ∧ L ] ≤ E Z [ ∥ P K ∣ Z ∥ α α ( ∥ P K ∣ Z ∥ α ∧ L ) 1 − α ] = E Z [ k ∑ P K ∣ Z ( k ∣ Z ) α ( ∥ P K ∣ Z ∥ α ∧ L ) 1 − α ] . (135)
For common randomness Z = z Z=z Z = z and a point ( y , t ) (y,t) ( y , t ) , define
S y , t ( z ) = { x : t r Q ( y ∣ x ) ≤ min ( y ′ , t ′ ) ∈ z t ′ r Q ( y ′ ∣ x ) } . (136) S_{y,t}(z)=\left\{x:\frac{t}{r_Q(y\mid x)}\leq\min_{(y',t')\in z}\frac{t'}{r_Q(y'\mid x)}\right\}. \tag*{(136)} S y , t ( z ) = { x : r Q ( y ∣ x ) t ≤ ( y ′ , t ′ ) ∈ z min r Q ( y ′ ∣ x ) t ′ } . (136)
to be the inputs for which ( y , t ) (y,t) ( y , t ) would be the returned point for the common randomness z ∪ { ( y , t ) } z \cup\{(y,t)\} z ∪ {( y , t )} , up to ties, which have zero measure in the integral below. We can apply Mecke’s identity to the sum in (135) to yield that
E Z [ ∑ k P K ∣ Z ( k ∣ Z ) α ( ∥ P K ∣ Z ∥ α ∧ L ) 1 − α ] = ∫ Y ∫ 0 ∞ E Z [ P X ( S y , t ( Z ) ) α ( ∥ P K ∣ Z ( ⋅ ∣ Z ∪ { ( y , t ) } ) ∥ α ∧ L ) 1 − α ] d t d Q Y ( y ) . (137) \mathbb{E}_{Z}\left[\sum_{k} P_{K|Z}(k \mid Z)^{\alpha}\left(\left\|P_{K|Z}\right\|_{\alpha}\wedge L\right)^{1-\alpha}\right]
= \int_{\mathcal{Y}}\int_{0}^{\infty}\mathbb{E}_{Z}\left[P_{X}(S_{y,t}(Z))^{\alpha}\left(\left\|P_{K|Z}(\cdot\mid Z\cup\{(y,t)\})\right\|_{\alpha}\wedge L\right)^{1-\alpha}\right]dt\,dQ_{Y}(y). \tag*{(137)} E Z [ k ∑ P K ∣ Z ( k ∣ Z ) α ( P K ∣ Z α ∧ L ) 1 − α ] = ∫ Y ∫ 0 ∞ E Z [ P X ( S y , t ( Z ) ) α ( P K ∣ Z ( ⋅ ∣ Z ∪ {( y , t )}) α ∧ L ) 1 − α ] d t d Q Y ( y ) . (137)
For the extended common randomness z ∪ { ( y , t ) } z\cup\{(y,t)\} z ∪ {( y , t )} , give the inserted point index 0 and retain the original indices of the other points. This relabeling preserves the norm. Then,
∥ P K ∣ Z = z ∪ { ( y , t ) } ∥ α α = P X ( S y , t ( z ) ) α + ∑ k P ( K = k , X ∉ S y , t ( z ) ∣ Z = z ) α ≤ ∑ k ( P ( K = k , X ∈ S y , t ( z ) ∣ Z = z ) α + P ( K = k , X ∉ S y , t ( z ) ∣ Z = z ) α ) (138) \begin{aligned}
\left\|P_{K|Z=z\cup\{(y,t)\}}\right\|_{\alpha}^{\alpha}
= P_{X}(S_{y,t}(z))^{\alpha}+\sum_{k}\mathbb{P}(K=k,X\notin S_{y,t}(z)\mid Z=z)^{\alpha} \\
&\leq\sum_{k}\left(\mathbb{P}(K=k,X\in S_{y,t}(z)\mid Z=z)^{\alpha}+\mathbb{P}(K=k,X\notin S_{y,t}(z)\mid Z=z)^{\alpha}\right) \tag*{(138)}
\end{aligned} P K ∣ Z = z ∪ {( y , t )} α α = P X ( S y , t ( z ) ) α + k ∑ P ( K = k , X ∈ / S y , t ( z ) ∣ Z = z ) α ≤ k ∑ ( P ( K = k , X ∈ S y , t ( z ) ∣ Z = z ) α + P ( K = k , X ∈ / S y , t ( z ) ∣ Z = z ) α ) (138)
≤ 2 1 − α ∑ k P ( K = k ∣ Z = z ) α = 2 1 − α ∥ P K ∣ Z = z ∥ α α . (139) \begin{aligned}
\leq2^{1-\alpha}\sum_{k}\mathbb{P}(K=k\mid Z=z)^{\alpha} \\
&=2^{1-\alpha}\left\|P_{K|Z=z}\right\|_{\alpha}^{\alpha}. \tag*{(139)}
\end{aligned} ≤ 2 1 − α k ∑ P ( K = k ∣ Z = z ) α = 2 1 − α P K ∣ Z = z α α . (139)
Above, (135) holds by the subadditivity of x ↦ x α x\mapsto x^{\alpha} x ↦ x α and (136) holds by a α + b α ≤ 2 1 − α ( a + b ) α a^{\alpha}+b^{\alpha}\leq2^{1-\alpha}(a+b)^{\alpha} a α + b α ≤ 2 1 − α ( a + b ) α for a , b ≥ 0 a,b\geq0 a , b ≥ 0 . Therefore,
E Z [ ∥ P K ∣ Z ∥ α ∧ L ] ≤ ∫ Y ∫ 0 ∞ E Z [ P X ( S y , t ( Z ) ) α ( 2 1 − α α ∥ P K ∣ Z ∥ α ∧ L ) 1 − α ] d t d Q Y ( y ) \mathbb{E}_{Z}\left[\left\|P_{K|Z}\right\|_{\alpha}\wedge L\right]
\leq\int_{\mathcal{Y}}\int_{0}^{\infty}\mathbb{E}_{Z}\left[P_{X}(S_{y,t}(Z))^{\alpha}\left(2^{\frac{1-\alpha}{\alpha}}\left\|P_{K|Z}\right\|_{\alpha}\wedge L\right)^{1-\alpha}\right]dt\,dQ_{Y}(y) E Z [ P K ∣ Z α ∧ L ] ≤ ∫ Y ∫ 0 ∞ E Z [ P X ( S y , t ( Z ) ) α ( 2 α 1 − α P K ∣ Z α ∧ L ) 1 − α ] d t d Q Y ( y )
≤ 2 ( 1 − α ) 2 α E Z [ ( ∫ Y ∫ 0 ∞ P X ( S y , t ( Z ) ) α d t d Q Y ( y ) ) ( ∥ P K ∣ Z ∥ α ∧ L ) 1 − α ] , \leq2^{\frac{(1-\alpha)^{2}}{\alpha}}\mathbb{E}_{Z}\left[\left(\int_{\mathcal{Y}}\int_{0}^{\infty}P_{X}(S_{y,t}(Z))^{\alpha}\,dt\,dQ_{Y}(y)\right)\left(\left\|P_{K|Z}\right\|_{\alpha}\wedge L\right)^{1-\alpha}\right], ≤ 2 α ( 1 − α ) 2 E Z [ ( ∫ Y ∫ 0 ∞ P X ( S y , t ( Z ) ) α d t d Q Y ( y ) ) ( P K ∣ Z α ∧ L ) 1 − α ] ,
where the last inequality uses ( c a ) ∧ L ≤ c ( a ∧ L ) (ca)\wedge L\leq c(a\wedge L) ( c a ) ∧ L ≤ c ( a ∧ L ) for c ≥ 1 c\geq1 c ≥ 1 , a ≥ 0 a\geq0 a ≥ 0 , and Tonelli’s theorem. We next apply Hölder’s and Minkowski’s inequalities to obtain
E Z [ ( ∫ Y ∫ 0 ∞ P X ( S y , t ( Z ) ) α d t d Q Y ( y ) ) ( ∥ P K ∣ Z ∥ α ∧ L ) 1 − α ] ≤ E Z [ ( ∫ Y ∫ 0 ∞ P X ( S y , t ( Z ) ) α d t d Q Y ( y ) ) 1 α ] α × ( E Z [ ∥ P K ∣ Z ∥ α ∧ L ] ) 1 − α ≤ ( ∫ Y ∫ 0 ∞ E Z [ P X ( S y , t ( Z ) ) ] α d t d Q Y ( y ) ) × ( E Z [ ∥ P K ∣ Z ∥ α ∧ L ] ) 1 − α . \begin{aligned}
\mathbb{E}_{Z}\left[\left(\int_{\mathcal{Y}}\int_{0}^{\infty}P_{X}(S_{y,t}(Z))^{\alpha}\,dt\,dQ_{Y}(y)\right)\left(\left\|P_{K|Z}\right\|_{\alpha}\wedge L\right)^{1-\alpha}\right] \\
&\leq\mathbb{E}_{Z}\left[\left(\int_{\mathcal{Y}}\int_{0}^{\infty}P_{X}(S_{y,t}(Z))^{\alpha}\,dt\,dQ_{Y}(y)\right)^{\frac{1}{\alpha}}\right]^{\alpha}
\times\left(\mathbb{E}_{Z}\left[\left\|P_{K|Z}\right\|_{\alpha}\wedge L\right]\right)^{1-\alpha} \\
&\leq\left(\int_{\mathcal{Y}}\int_{0}^{\infty}\mathbb{E}_{Z}\left[P_{X}(S_{y,t}(Z))\right]^{\alpha}\,dt\,dQ_{Y}(y)\right)
\times\left(\mathbb{E}_{Z}\left[\left\|P_{K|Z}\right\|_{\alpha}\wedge L\right]\right)^{1-\alpha}.
\end{aligned} E Z [ ( ∫ Y ∫ 0 ∞ P X ( S y , t ( Z ) ) α d t d Q Y ( y ) ) ( P K ∣ Z α ∧ L ) 1 − α ] ≤ E Z [ ( ∫ Y ∫ 0 ∞ P X ( S y , t ( Z ) ) α d t d Q Y ( y ) ) α 1 ] α × ( E Z [ P K ∣ Z α ∧ L ] ) 1 − α ≤ ( ∫ Y ∫ 0 ∞ E Z [ P X ( S y , t ( Z )) ] α d t d Q Y ( y ) ) × ( E Z [ P K ∣ Z α ∧ L ] ) 1 − α .
Above, the first inequality is Hölder’s inequality with conjugate exponents 1 / α 1/\alpha 1/ α and 1 / ( 1 − α ) 1/(1-\alpha) 1/ ( 1 − α ) , and the second inequality is Minkowski’s integral inequality with exponent 1 / α 1/\alpha 1/ α .
Following the discussion in § 5 -A, we have that
E Z [ P X ( S y , t ( Z ) ) ] = a y Q ( t ) = ∫ X exp ( − t r Q ( y ∣ x ) ) d P X ( x ) . \mathbb{E}_{Z}\left[P_{X}(S_{y,t}(Z))\right]=a_{y}^{Q}(t)=\int_{\mathcal{X}}\exp\left(-\frac{t}{r_{Q}(y\mid x)}\right)dP_{X}(x). E Z [ P X ( S y , t ( Z )) ] = a y Q ( t ) = ∫ X exp ( − r Q ( y ∣ x ) t ) d P X ( x ) .
Therefore, dividing both sides of our original inequality by ( E Z [ ∥ P K ∣ Z ∥ α ∧ L ] ) 1 − α \left(\mathbb{E}_{Z}\left[\left\|P_{K|Z}\right\|_{\alpha}\wedge L\right]\right)^{1-\alpha} ( E Z [ P K ∣ Z α ∧ L ] ) 1 − α , which is finite and strictly positive, and letting L ↑ ∞ L\uparrow\infty L ↑ ∞ by monotone convergence, we obtain from (134)
( E Z ∥ P Y ∣ Z ∥ α ) α ≤ 2 ( 1 − α ) 2 α ∫ Y ∫ 0 ∞ a y Q ( t ) α d t d Q Y ( y ) . (140) \left(\mathbb{E}_{Z}\left\|P_{Y|Z}\right\|_{\alpha}\right)^{\alpha}
\leq2^{\frac{(1-\alpha)^{2}}{\alpha}}\int_{\mathcal{Y}}\int_{0}^{\infty}a_{y}^{Q}(t)^{\alpha}\,dt\,dQ_{Y}(y). \tag*{(140)} ( E Z P Y ∣ Z α ) α ≤ 2 α ( 1 − α ) 2 ∫ Y ∫ 0 ∞ a y Q ( t ) α d t d Q Y ( y ) . (140)
Finally, we claim that, for Q Y Q_{Y} Q Y -a.e. y y y ,
∫ 0 ∞ a y Q ( t ) α d t ≤ 1 α ∫ 0 ∞ w y Q ( ℓ ) α d ℓ . (141) \int_{0}^{\infty}a_{y}^{Q}(t)^{\alpha}\,dt\leq\frac{1}{\alpha}\int_{0}^{\infty}w_{y}^{Q}(\ell)^{\alpha}\,d\ell. \tag*{(141)} ∫ 0 ∞ a y Q ( t ) α d t ≤ α 1 ∫ 0 ∞ w y Q ( ℓ ) α d ℓ . (141)
To show (141) , fix y , t > 0 y,t>0 y , t > 0 , and note that, for every x x x ,
exp ( − t r Q ( y ∣ x ) ) = ( ∫ 0 ∞ 1 [ s r Q ( y ∣ x ) ≥ t ] α e − α s d s ) 1 / α (142) \exp\left(-\frac{t}{r_Q(y\mid x)}\right)=\left(\int_0^\infty\mathbf{1}[sr_Q(y\mid x)\ge t]^\alpha e^{-\alpha s}\,ds\right)^{1/\alpha} \tag*{(142)} exp ( − r Q ( y ∣ x ) t ) = ( ∫ 0 ∞ 1 [ s r Q ( y ∣ x ) ≥ t ] α e − α s d s ) 1/ α (142)
Thus,
a y Q ( t ) ≤ ( ∫ 0 ∞ ( ∫ X 1 [ s r Q ( y ∣ x ) ≥ t ] d P X ( x ) ) α α e − α s d s ) 1 / α = ( ∫ 0 ∞ α e − α s w y Q ( t / s ) α d s ) 1 / α . \begin{aligned}
a_y^Q(t)\le\left(\int_0^\infty\left(\int_{\mathcal{X}}\mathbf{1}[sr_Q(y\mid x)\ge t]\,dP_X(x)\right)^\alpha\alpha e^{-\alpha s}\,ds\right)^{1/\alpha} \\
&=\left(\int_0^\infty\alpha e^{-\alpha s}w_y^Q(t/s)^\alpha\,ds\right)^{1/\alpha}.
\end{aligned} a y Q ( t ) ≤ ( ∫ 0 ∞ ( ∫ X 1 [ s r Q ( y ∣ x ) ≥ t ] d P X ( x ) ) α α e − α s d s ) 1/ α = ( ∫ 0 ∞ α e − α s w y Q ( t / s ) α d s ) 1/ α .
Above, the inequality follows from the reverse Minkowski integral inequality for nonnegative functions with 0 < α < 1 0<\alpha<1 0 < α < 1 (equivalently, apply Minkowski in L 1 / α ( P X ) L^{1/\alpha}(P_X) L 1/ α ( P X ) to the integral in s s s before taking the 1 / α 1/\alpha 1/ α power). Raising both sides to the power of α \alpha α and integrating over t t t yields
∫ 0 ∞ a y Q ( t ) α d t ≤ ∫ 0 ∞ α s e − α s d s ∫ 0 ∞ w y Q ( ℓ ) α d ℓ = 1 α ∫ 0 ∞ w y Q ( ℓ ) α d ℓ . \begin{aligned}
\int_0^\infty a_y^Q(t)^\alpha\,dt\le\int_0^\infty\alpha s e^{-\alpha s}\,ds\int_0^\infty w_y^Q(\ell)^\alpha\,d\ell\\
&=\frac{1}{\alpha}\int_0^\infty w_y^Q(\ell)^\alpha\,d\ell.
\end{aligned} ∫ 0 ∞ a y Q ( t ) α d t ≤ ∫ 0 ∞ α s e − α s d s ∫ 0 ∞ w y Q ( ℓ ) α d ℓ = α 1 ∫ 0 ∞ w y Q ( ℓ ) α d ℓ .
Substituting (141) into (140) yields
( E Z ∥ P Y ∣ Z ∥ α ) α ≤ 2 ( 1 − α ) 2 / α α ( ∫ Y ∫ 0 ∞ w y Q ( ℓ ) α d ℓ d Q Y ( y ) ) (143) \left(\mathbb{E}_Z\left\|P_{Y\mid Z}\right\|_\alpha\right)^\alpha\le\frac{2^{(1-\alpha)^2/\alpha}}{\alpha}\left(\int_{\mathcal{Y}}\int_0^\infty w_y^Q(\ell)^\alpha\,d\ell\,dQ_Y(y)\right) \tag*{(143)} ( E Z P Y ∣ Z α ) α ≤ α 2 ( 1 − α ) 2 / α ( ∫ Y ∫ 0 ∞ w y Q ( ℓ ) α d ℓ d Q Y ( y ) ) (143)
from which the result follows by the change of variables below. Where d P Y d Q Y ( y ) = 0 \frac{dP_Y}{dQ_Y}(y)=0 d Q Y d P Y ( y ) = 0 , w y Q ( ℓ ) = 0 w_y^Q(\ell)=0 w y Q ( ℓ ) = 0 for ℓ > 0 \ell>0 ℓ > 0 , and the integrand is taken to be zero there. Thus,
∫ Y ∫ 0 ∞ w y Q ( ℓ ) α d ℓ d Q Y ( y ) = ∫ Y ∫ 0 ∞ w y ( ℓ d P Y d Q Y ( y ) ) α d ℓ d Q Y ( y ) = ∫ Y ∫ 0 ∞ w y ( h ) α d P Y d Q Y ( y ) d h d Q Y ( y ) (sub. h = ℓ / d P Y d Q Y ( y ) ) = ∫ Y ∫ 0 ∞ w y ( h ) α d h d P Y ( y ) . \begin{aligned}
\int_{\mathcal{Y}}\int_0^\infty w_y^Q(\ell)^\alpha\,d\ell\,dQ_Y(y) \\
&=\int_{\mathcal{Y}}\int_0^\infty w_y\left(\frac{\ell}{\frac{dP_Y}{dQ_Y}(y)}\right)^\alpha\,d\ell\,dQ_Y(y) \\
&=\int_{\mathcal{Y}}\int_0^\infty w_y(h)^\alpha\frac{dP_Y}{dQ_Y}(y)\,dh\,dQ_Y(y)\qquad\text{(sub. }h=\ell/\frac{dP_Y}{dQ_Y}(y)\text{)} \\
&=\int_{\mathcal{Y}}\int_0^\infty w_y(h)^\alpha\,dh\,dP_Y(y).
\end{aligned} ∫ Y ∫ 0 ∞ w y Q ( ℓ ) α d ℓ d Q Y ( y ) = ∫ Y ∫ 0 ∞ w y ( d Q Y d P Y ( y ) ℓ ) α d ℓ d Q Y ( y ) = ∫ Y ∫ 0 ∞ w y ( h ) α d Q Y d P Y ( y ) d h d Q Y ( y ) (sub. h = ℓ / d Q Y d P Y ( y ) ) = ∫ Y ∫ 0 ∞ w y ( h ) α d h d P Y ( y ) .