Introduction
This paper studies the communication rates that can be supported by a state-dependent discrete memoryless multi-access channel (SD-MAC) when, in addition to recovering the transmitted data reliably, the receiver must also recover the state sequence. We assume that the state is revealed to the transmitters causally and that the receiver must reconstruct the state sequence “almost losslessly,” i.e., that the error rate in its reconstruction of the state sequence must vanish with the blocklength.
We do not address the case where some distortion is allowed in the state reconstruction. Our work can thus be viewed as an extension of [3 ] to multi-access networks, albeit for the special case of zero distortion. We also do not consider feedback, which is studied in the single-user case (with distortion constraints) in [2 ] . Finally, we only consider memoryless SD-MACs where the state is IID. The general case is beyond the scope of this paper, but see [11 ] for the Gilbert-Elliott single-user channel.
To address different architectures, we model the state S S S as comprising three independent components: a component S 0 S_0 S 0 that is revealed to both encoders, a component S 1 S_1 S 1 that is revealed only to Encoder 1 and a component S 2 S_2 S 2 that is revealed only to Encoder 2; see Figure 1 . Special cases are the “common state” architecture (where the multi-access is governed by a single state sequence that is revealed to both encoders) and the “independent states” architecture (where the channel is governed by two independent states each of which is revealed to a different encoder).
Figure 1. The network under consideration.
Our main result is a characterization of the capacity region, i.e., the set of rate pairs that can be reliably transmitted over the network under the constraint that the receiver recover the state sequence “almost losslessly,” i.e., with vanishing symbol error rate. The coding scheme we propose is a Block-Markov scheme with backward decoding. Key is that, using superposition coding (as in [19 ] ), the transmitters cooperate to transmit some of the past state information that they share. To guarantee that, once transmission terminates, the backward decoding can commence, we assume that the capacity region of the SD-MAC (with causal side-information but without any state-reconstruction constraints) has a nonempty interior.
It is noteworthy that introducing the state-reconstruction constraints makes the problem more tractable: The capacity region of the SD-MAC with causal state information (and no state-reconstruction constraints) is still unknown. It was studied in [9 , 10 , 13 ] , where it was shown that Shannon strategies are not optimal and that strictly-causal state information is beneficial.
The literature on state-dependent channels is vast. We mention here a small fraction that focuses on both the data to be transmitted and the channel state. Sutivong et al. [20 ] studied joint message transmission and state estimation over Gaussian channels with noncausal encoder state information. Kim et al. [6 ] considered state amplification for both discrete and continuous channels with noncausal state information. Zhang et al. [22 ] studied joint message transmission and state estimation when the encoders know only the state distribution but not its realization; they also extended their results to multiple-access channels.
More recently, Li et al. [14 ] derived an achievable rate-distortion region for joint state and message communication over multiple-access channels with causal state information and generalized feedback. Subsequent work [15 ] developed a simultaneous-decoding approach and obtained improved achievable regions for multiuser channels. While our setting can be viewed as a special case of theirs (when the generalized feedback is useless, and the allowed distortion is zero), we provide an exact characterization of the capacity region for multiple-access channels under the nearly-lossless state-reconstruction requirement.
A complementary line of research concerns state masking, which seeks to limit the information about the state revealed to the receiver [17 ] . Le Treust and Bloch [12 ] studied both state masking and amplification within a unified framework. Also related are studies of integrated sensing and communication in which, rather than by the receivers, the state estimation is performed by the transmitters (utilizing channel feedback) [1 , 7 , 16 ] .
The rest of the paper is organized as follows. After some notation, we turn to § 2 , which describes the communication scenario in greater detail and which defines the capacity region we seek. § 3 presents the main theorem characterizing said region. The proof is presented in § 4 (converse) and § 5 (achievability).
Notation
When k k k is a positive integer, [ 1 : k ] [1 : k] [ 1 : k ] denotes the set { 1 , … , k } \{1, \ldots, k\} { 1 , … , k } . More generally, for any positive real number a > 0 a > 0 a > 0 , we use [ 1 : a ] [1 : a] [ 1 : a ] to denote the (possibly empty) set { 1 , 2 , … , ⌊ a ⌋ } \{1, 2, \ldots, \lfloor a \rfloor\} { 1 , 2 , … , ⌊ a ⌋} . Upper-case calligraphic fonts denote finite sets, e.g., S \mathcal{S} S denotes the set of possible channel states. The n n n -fold Cartesian product of a set A \mathcal{A} A with itself is denoted A × n \mathcal{A}^{\times n} A × n and comprises all n n n -tuples with entries from A \mathcal{A} A . The cardinality of a set A \mathcal{A} A is denoted ∣ A ∣ |\mathcal{A}| ∣ A ∣ , so ∣ S ∣ |\mathcal{S}| ∣ S ∣ denotes the number of channel states. A random variable taking values in the set A \mathcal{A} A is usually denoted A A A and its Probability Mass Function (PMF) P A P_A P A . Hence, the random channel state S S S takes values in S S S and its PMF is P S P_S P S . A generic realization of such a random variable is usually denoted a a a , so P S ( s ) P_S(s) P S ( s ) is the probability that S S S equals s s s . Given a PMF P X P_X P X and a conditional PMF P Y ∣ X P_{Y|X} P Y ∣ X , we write P X P Y ∣ X P_XP_{Y|X} P X P Y ∣ X for the joint PMF that assigns the pair ( x , y ) (x,y) ( x , y ) the probability P X ( x ) P Y ∣ X ( y ∣ x ) P_X(x)P_{Y|X}(y|x) P X ( x ) P Y ∣ X ( y ∣ x ) . The indicator function of an event E \mathcal{E} E is denoted I { E } \mathbb{I}\{\mathcal{E}\} I { E } and equals 1 if E \mathcal{E} E holds and equals 0 otherwise. For example, I { x = y } \mathbb{I}\{x=y\} I { x = y } is 1 if x = y x=y x = y , and is 0 otherwise.
The empirical PMF P a n P_{a^n} P a n of a sequence a n ∈ A n a^n \in\mathcal{A}^n a n ∈ A n is defined as
P a n ( a ) ≜ 1 n ∑ i = 1 n I { a i = a } , a ∈ A . (1) P_{a^n}(a) \triangleq\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}\{a_i=a\}, \qquad a \in\mathcal{A}. \tag*{(1)} P a n ( a ) ≜ n 1 i = 1 ∑ n I { a i = a } , a ∈ A . (1)
Given a PMF P A P_A P A on A \mathcal{A} A and some δ > 0 \delta>0 δ > 0 , the strongly δ \delta δ -typical set T δ ( n ) ( P A ) T_{\delta}^{(n)}(P_A) T δ ( n ) ( P A ) is defined as in [18 Definition 4.1] :
T δ ( n ) ( P A ) ≜ { a n ∈ A n : ( ∣ P a n ( a ) − P A ( a ) ∣ < δ ∣ A ∣ , ∀ a ∈ A ) and ( ( P A ( a ) = 0 ) ⇒ ( P a n ( a ) = 0 ) ) } . (2) T_{\delta}^{(n)}(P_A) \triangleq\left\{a^n \in\mathcal{A}^n : \left(\left|P_{a^n}(a)-P_A(a)\right| < \frac{\delta}{|\mathcal{A}|},\ \forall a \in\mathcal{A}\right) \text{ and } \left((P_A(a)=0) \Rightarrow(P_{a^n}(a)=0)\right)\right\}. \tag*{(2)} T δ ( n ) ( P A ) ≜ { a n ∈ A n : ( ∣ P a n ( a ) − P A ( a ) ∣ < ∣ A ∣ δ , ∀ a ∈ A ) and ( ( P A ( a ) = 0 ) ⇒ ( P a n ( a ) = 0 ) ) } . (2)
We abbreviate T δ ( n ) ( P A ) T_{\delta}^{(n)}(P_A) T δ ( n ) ( P A ) as T δ ( n ) ( A ) T_{\delta}^{(n)}(A) T δ ( n ) ( A ) . More generally, T δ ( n ) ( A 1 , … , A m ) T_{\delta}^{(n)}(A_1,\ldots,A_m) T δ ( n ) ( A 1 , … , A m ) denotes the strongly typical set with respect to the joint PMF P A 1 ⋯ A m P_{A_1\cdots A_m} P A 1 ⋯ A m on A 1 × ⋯ × A m \mathcal{A}_1 \times\cdots\times\mathcal{A}_m A 1 × ⋯ × A m . All logarithms are of base two. The binary entropy function is denoted by H b ( p ) H_b(p) H b ( p ) .
The Setup
We consider a two-to-one SD-MAC with finite input alphabets X 1 \mathcal{X}_1 X 1 , X 2 \mathcal{X}_2 X 2 and with a finite output alphabet Y \mathcal{Y} Y . The state alphabet S \mathcal{S} S is finite and has the form
S = S 0 × S 1 × S 2 (3) \mathcal{S} = \mathcal{S}_0 \times\mathcal{S}_1 \times\mathcal{S}_2 \tag*{(3)} S = S 0 × S 1 × S 2 (3)
so the time i i i state S i S_i S i is a triple
S i = ( S 0 , i , S 1 , i , S 2 , i ) . (4) S_i = (S_{0,i}, S_{1,i}, S_{2,i}). \tag*{(4)} S i = ( S 0 , i , S 1 , i , S 2 , i ) . (4)
The states { S i } \{S_i\} { S i } are IID ∼ P S \sim P_S ∼ P S , with P S P_S P S having the product form
P S = P S 0 P S 1 P S 2 . (5) P_S = P_{S_0}P_{S_1}P_{S_2}. \tag*{(5)} P S = P S 0 P S 1 P S 2 . (5)
The three components S 0 , i S_{0,i} S 0 , i , S 1 , i S_{1,i} S 1 , i , S 2 , i S_{2,i} S 2 , i of the Time-i i i state S i S_i S i are thus independent and of PMFs P S 0 P_{S_0} P S 0 , P S 1 P_{S_1} P S 1 , and P S 2 P_{S_2} P S 2 . By possibly redefining the state alphabet, we may assume—as we shall—that P S P_S P S is of full support (i.e., that P S ( s ) P_S(s) P S ( s ) is positive for every state s ∈ S s \in\mathcal{S} s ∈ S ). Conditional on the states, the channel is memoryless, and we denote its law by P Y ∣ X 1 X 2 S 0 S 1 S 2 P_{Y|X_1X_2S_0S_1S_2} P Y ∣ X 1 X 2 S 0 S 1 S 2 or W Y ∣ X 1 X 2 S 0 S 1 S 2 W_{Y|X_1X_2S_0S_1S_2} W Y ∣ X 1 X 2 S 0 S 1 S 2 .
Each encoder wishes to convey a message to the decoder: Encoder 1 wishes to convey M 1 M_1 M 1 and Encoder 2 M 2 M_2 M 2 . The two messages are independent, with M 1 M_1 M 1 uniformly distributed over the set M 1 = [ 1 : 2 n R 1 ] \mathcal{M}_1 = [1 : 2^{nR_1}] M 1 = [ 1 : 2 n R 1 ] , and with M 2 M_2 M 2 uniformly distributed over M 2 = [ 1 : 2 n R 2 ] \mathcal{M}_2 = [1 : 2^{nR_2}] M 2 = [ 1 : 2 n R 2 ] . Here n n n denotes the blocklength, and R 1 R_1 R 1 , R 2 R_2 R 2 denote the rates of transmission in bits per channel-use.
The sequences { S 0 , i } \{S_{0,i}\} { S 0 , i } and { S 1 , i } \{S_{1,i}\} { S 1 , i } are revealed to Encoder 1 causally, so the symbol X 1 , i = X 1 , i ( M 1 , S 0 i , S 1 i ) X_{1,i} = X_{1,i}(M_1,S_0^i,S_1^i) X 1 , i = X 1 , i ( M 1 , S 0 i , S 1 i ) it produces at Time-i i i can depend not only on its message M 1 M_1 M 1 but also on the present-and-past values of the sequences { S 0 , i } \{S_{0,i}\} { S 0 , i } and { S 1 , i } \{S_{1,i}\} { S 1 , i } . Encoder 1 is thus specified by n n n functions
f 1 , i : M 1 × S 0 × i × S 1 × i → X 1 , i ∈ [ 1 : n ] (6) f_{1,i}:\mathcal{M}_1 \times\mathcal{S}_0^{\times i} \times\mathcal{S}_1^{\times i} \to\mathcal{X}_1,\qquad i \in[1:n] \tag*{(6)} f 1 , i : M 1 × S 0 × i × S 1 × i → X 1 , i ∈ [ 1 : n ] (6)
where n n n is the blocklength. Likewise, Encoder 2, which is revealed the sequences { S 0 , i } \{S_{0,i}\} { S 0 , i } and { S 2 , i } \{S_{2,i}\} { S 2 , i } causally, produces the Time-i i i symbol X 2 , i = X 2 , i ( M 2 , S 0 i , S 2 i ) X_{2,i} = X_{2,i}(M_2,S_0^i,S_2^i) X 2 , i = X 2 , i ( M 2 , S 0 i , S 2 i ) in accordance with the n n n functions
f 2 , i : M 2 × S 0 × i × S 2 × i → X 2 , i ∈ [ 1 : n ] . (7) f_{2,i}:\mathcal{M}_2 \times\mathcal{S}_0^{\times i} \times\mathcal{S}_2^{\times i} \to\mathcal{X}_2,\qquad i \in[1:n]. \tag*{(7)} f 2 , i : M 2 × S 0 × i × S 2 × i → X 2 , i ∈ [ 1 : n ] . (7)
Based on the received output sequence Y n Y^n Y n , the receiver wishes to recover the messages as well as the state sequence. It thus has the form
ϕ : Y × n → M 1 × M 2 × S × n (8) \phi:\mathcal{Y}^{\times n} \to\mathcal{M}_1 \times\mathcal{M}_2 \times\mathcal{S}^{\times n} \tag*{(8)} ϕ : Y × n → M 1 × M 2 × S × n (8)
with the understanding that it maps Y n Y^n Y n to ( M ^ 1 , M ^ 2 , S ^ 0 n , S ^ 1 n , S ^ 2 n ) (\hat{M}_1,\hat{M}_2,\hat{S}_0^n,\hat{S}_1^n,\hat{S}_2^n) ( M ^ 1 , M ^ 2 , S ^ 0 n , S ^ 1 n , S ^ 2 n ) . The message-error decoding probability is
P e ( n ) ≜ Pr ( ( M ^ 1 , M ^ 2 ) ≠ ( M 1 , M 2 ) ) (9) P_{\mathrm{e}}^{(n)} \triangleq\Pr\left((\hat{M}_1,\hat{M}_2) \ne(M_1,M_2)\right) \tag*{(9)} P e ( n ) ≜ Pr ( ( M ^ 1 , M ^ 2 ) = ( M 1 , M 2 ) ) (9)
and the state-reconstruction symbol error-rate is
β ( n ) ≜ 1 n ∑ i = 1 n Pr ( ( S 0 , i , S 1 , i , S 2 , i ) ≠ ( S ^ 0 , i , S ^ 1 , i , S ^ 2 , i ) ) . (10) \beta^{(n)} \triangleq\frac{1}{n}\sum_{i=1}^{n}\Pr\left((S_{0,i},S_{1,i},S_{2,i}) \ne(\hat{S}_{0,i},\hat{S}_{1,i},\hat{S}_{2,i})\right). \tag*{(10)} β ( n ) ≜ n 1 i = 1 ∑ n Pr ( ( S 0 , i , S 1 , i , S 2 , i ) = ( S ^ 0 , i , S ^ 1 , i , S ^ 2 , i ) ) . (10)
A rate pair ( R 1 , R 2 ) ∈ R ≥ 0 2 (R_1,R_2) \in\mathbb{R}_{\ge0}^{2} ( R 1 , R 2 ) ∈ R ≥ 0 2 is said to be achievable if, for some ϵ 0 > 0 \epsilon_0 > 0 ϵ 0 > 0 , there exists a sequence of rate-( R 1 + ϵ 0 , R 2 + ϵ 0 ) (R_1+\epsilon_0,R_2+\epsilon_0) ( R 1 + ϵ 0 , R 2 + ϵ 0 ) encoders and decoders (indexed by the blocklength n n n ) such that both P e ( n ) P_{\mathrm{e}}^{(n)} P e ( n ) and β ( n ) \beta^{(n)} β ( n ) tend to zero. The capacity region C \mathcal{C} C is the closure of the set of all achievable rate pairs.
The added ϵ 0 \epsilon_0 ϵ 0 in the definition allows us to state and prove the main theorem without the intricacies of the zero-rate case.
Remark 1. The capacity region is a (possibly empty) convex compact subset of R 2 \mathbb{R}^2 R 2 .
Proof. The set is closed by definition; it is bounded because the alphabets are finite; and convexity can be established using a time-sharing argument.
Main Result
The main result of this paper is a characterization of the capacity region. It is derived, under the following assumption:
Assumption 1. The SD-MAC W ( y ∣ x 1 , x 2 , s 0 , s 1 , s 2 ) W(y|x_1,x_2,s_0,s_1,s_2) W ( y ∣ x 1 , x 2 , s 0 , s 1 , s 2 ) is such that, in the absence of a state-reconstruction requirement (i.e., when β ( n ) \beta^{(n)} β ( n ) need not tend to zero), there exists a positive rate pair ( R 1 , R 2 ) ∈ R ≥ 0 2 (R_1,R_2) \in\mathbb{R}^2_{\ge0} ( R 1 , R 2 ) ∈ R ≥ 0 2 that is achievable (when the encoders are causally informed).
Remark 2. In the “common state” case—i.e., when S 1 S_1 S 1 and S 2 S_2 S 2 are deterministic—Assumption 1 is equivalent to the assumption that some positive rate pair can be achieved over the SD-MAC using Shannon strategies. This equivalence need not hold in general.
Proof: See Appendix A.1.
To describe the capacity region, we need some preliminary definitions. Let P \mathcal{P} P denote the collection of all joint PMFs of the following form, where Q Q Q and V V V are finite auxiliary random variables:
P Q P S 0 P S 1 P S 2 P V ∣ Q P X 1 ∣ S 0 S 1 V Q P X 2 ∣ S 0 S 2 V Q W Y ∣ X 1 X 2 S 0 S 1 S 2 . (11) P_Q P_{S_0} P_{S_1} P_{S_2} P_{V|Q} P_{X_1|S_0S_1VQ} P_{X_2|S_0S_2VQ} W_{Y|X_1X_2S_0S_1S_2}. \tag*{(11)} P Q P S 0 P S 1 P S 2 P V ∣ Q P X 1 ∣ S 0 S 1 V Q P X 2 ∣ S 0 S 2 V Q W Y ∣ X 1 X 2 S 0 S 1 S 2 . (11)
For each P ∈ P P \in\mathcal{P} P ∈ P , let R < ( P ) \mathcal{R}_{<}(P) R < ( P ) denote the rate polytope
{ ( R 1 , R 2 ) ∈ R ≥ 0 2 ∣ R 1 < I ( X 1 , S 1 ; Y ∣ X 2 , S 0 , S 2 , V , Q ) − H ( S 1 ) , R 2 < I ( X 2 , S 2 ; Y ∣ X 1 , S 0 , S 1 , V , Q ) − H ( S 2 ) , R 1 + R 2 < I ( X 1 , X 2 , S 1 , S 2 ; Y ∣ S 0 , V , Q ) − H ( S 1 ) − H ( S 2 ) , R 1 + R 2 < I ( X 1 , X 2 , S 0 , S 1 , S 2 ; Y ∣ Q ) − H ( S 0 ) − H ( S 1 ) − H ( S 2 ) } . (12) \left\{
\begin{aligned}
(R_1,R_2) &\in\mathbb{R}^2_{\ge0} \ \bigg| \\
R_1 &< I(X_1,S_1;Y \mid X_2,S_0,S_2,V,Q)-H(S_1),\\
R_2 &< I(X_2,S_2;Y \mid X_1,S_0,S_1,V,Q)-H(S_2),\\
R_1+R_2 &< I(X_1,X_2,S_1,S_2;Y \mid S_0,V,Q)-H(S_1)-H(S_2),\\
R_1+R_2 &< I(X_1,X_2,S_0,S_1,S_2;Y \mid Q)-H(S_0)-H(S_1)-H(S_2)
\end{aligned}
\right\}. \tag*{(12)} ⎩ ⎨ ⎧ ( R 1 , R 2 ) R 1 R 2 R 1 + R 2 R 1 + R 2 ∈ R ≥ 0 2 < I ( X 1 , S 1 ; Y ∣ X 2 , S 0 , S 2 , V , Q ) − H ( S 1 ) , < I ( X 2 , S 2 ; Y ∣ X 1 , S 0 , S 1 , V , Q ) − H ( S 2 ) , < I ( X 1 , X 2 , S 1 , S 2 ; Y ∣ S 0 , V , Q ) − H ( S 1 ) − H ( S 2 ) , < I ( X 1 , X 2 , S 0 , S 1 , S 2 ; Y ∣ Q ) − H ( S 0 ) − H ( S 1 ) − H ( S 2 ) ⎭ ⎬ ⎫ . (12)
Finally, define
C ( 1 ) ≜ cl ( ⋃ P ∈ P R < ( P ) ) (13) \mathcal{C}^{(1)} \triangleq\operatorname{cl}\left(\bigcup_{P\in\mathcal{P}} \mathcal{R}_{<}(P)\right) \tag*{(13)} C ( 1 ) ≜ cl ( P ∈ P ⋃ R < ( P ) ) (13)
where cl ( ⋅ ) \operatorname{cl}(\cdot) cl ( ⋅ ) stands for the closure operator.
Proof: See Appendix A.2.
Theorem 1. Under Assumption 1,
C = C ( I ) . (16) \mathcal{C} = \mathcal{C}^{(I)}. \tag*{(16)} C = C ( I ) . (16)
Converse
We first prove the converse. Fix an achievable rate pair ( R 1 , R 2 ) (R_1, R_2) ( R 1 , R 2 ) . By definition, there exist a constant ϵ 0 > 0 \epsilon_0 > 0 ϵ 0 > 0 and a sequence of rate-( R 1 + ϵ 0 , R 2 + ϵ 0 ) (R_1 + \epsilon_0, R_2 + \epsilon_0) ( R 1 + ϵ 0 , R 2 + ϵ 0 ) coding schemes such that P e ( n ) → 0 P_{\mathrm{e}}^{(n)} \to0 P e ( n ) → 0 and β ( n ) → 0 \beta^{(n)} \to0 β ( n ) → 0 . Define
δ e ( n ) ≜ ( R 1 + R 2 + 2 ϵ 0 ) P e ( n ) + 1 n H b ( P e ( n ) ) (17) \delta_{\mathrm{e}}^{(n)} \triangleq(R_1 + R_2 + 2\epsilon_0)P_{\mathrm{e}}^{(n)} + \frac{1}{n} H_{\mathrm{b}}(P_{\mathrm{e}}^{(n)}) \tag*{(17)} δ e ( n ) ≜ ( R 1 + R 2 + 2 ϵ 0 ) P e ( n ) + n 1 H b ( P e ( n ) ) (17)
δ β ( n ) ≜ β ( n ) log ( ∣ S 0 ∣ ∣ S 1 ∣ ∣ S 2 ∣ − 1 ) + H b ( β ( n ) ) (18) \delta_{\beta}^{(n)} \triangleq\beta^{(n)} \log\bigl(|\mathcal{S}_0||\mathcal{S}_1||\mathcal{S}_2| - 1\bigr) + H_{\mathrm{b}}(\beta^{(n)}) \tag*{(18)} δ β ( n ) ≜ β ( n ) log ( ∣ S 0 ∣∣ S 1 ∣∣ S 2 ∣ − 1 ) + H b ( β ( n ) ) (18)
η n ≜ δ e ( n ) + δ β ( n ) . (19) \eta_n \triangleq\delta_{\mathrm{e}}^{(n)} + \delta_{\beta}^{(n)}. \tag*{(19)} η n ≜ δ e ( n ) + δ β ( n ) . (19)
Since P e ( n ) P_{\mathrm{e}}^{(n)} P e ( n ) and β ( n ) \beta^{(n)} β ( n ) tend to zero, so does η n \eta_n η n . Applying Fano’s inequality [18 Proposition 2.17] to the messages, we obtain
H ( M 1 , M 2 ∣ Y n ) ≤ n δ e ( n ) . (20) H(M_1, M_2 \mid Y^n) \le n\delta_{\mathrm{e}}^{(n)}. \tag*{(20)} H ( M 1 , M 2 ∣ Y n ) ≤ n δ e ( n ) . (20)
Define
p i ( n ) ≜ Pr ( ( S 0 , i , S 1 , i , S 2 , i ) ≠ ( S ^ 0 , i , S ^ 1 , i , S ^ 2 , i ) ) . (21) p_i^{(n)} \triangleq\Pr\bigl((S_{0,i}, S_{1,i}, S_{2,i}) \ne(\widehat{S}_{0,i}, \widehat{S}_{1,i}, \widehat{S}_{2,i})\bigr). \tag*{(21)} p i ( n ) ≜ Pr ( ( S 0 , i , S 1 , i , S 2 , i ) = ( S 0 , i , S 1 , i , S 2 , i ) ) . (21)
Since ( S ^ 0 , i , S ^ 1 , i , S ^ 2 , i ) (\widehat{S}_{0,i}, \widehat{S}_{1,i}, \widehat{S}_{2,i}) ( S 0 , i , S 1 , i , S 2 , i ) are functions of Y n Y^n Y n ,
H ( S 0 , i , S 1 , i , S 2 , i ∣ Y n ) ≤ H ( S 0 , i , S 1 , i , S 2 , i ∣ S ^ 0 , i , S ^ 1 , i , S ^ 2 , i ) (22) H(S_{0,i}, S_{1,i}, S_{2,i} \mid Y^n) \le H(S_{0,i}, S_{1,i}, S_{2,i} \mid\widehat{S}_{0,i}, \widehat{S}_{1,i}, \widehat{S}_{2,i}) \tag*{(22)} H ( S 0 , i , S 1 , i , S 2 , i ∣ Y n ) ≤ H ( S 0 , i , S 1 , i , S 2 , i ∣ S 0 , i , S 1 , i , S 2 , i ) (22)
≤ H b ( p i ( n ) ) + p i ( n ) log ( ∣ S 0 ∣ ∣ S 1 ∣ ∣ S 2 ∣ − 1 ) , (23) \le H_{\mathrm{b}}(p_i^{(n)}) + p_i^{(n)} \log\bigl(|\mathcal{S}_0||\mathcal{S}_1||\mathcal{S}_2| - 1\bigr), \tag*{(23)} ≤ H b ( p i ( n ) ) + p i ( n ) log ( ∣ S 0 ∣∣ S 1 ∣∣ S 2 ∣ − 1 ) , (23)
where the second inequality follows from Fano’s inequality.
By the chain rule, the fact that conditioning reduces entropy, and the concavity of H b ( ⋅ ) H_b(\cdot) H b ( ⋅ ) ,
H ( S 0 n , S 1 n , S 2 n ∣ Y n ) = ∑ i = 1 n H ( S 0 , i , S 1 , i , S 2 , i ∣ S 0 i − 1 , S 1 i − 1 , S 2 i − 1 , Y n ) ≤ ∑ i = 1 n H ( S 0 , i , S 1 , i , S 2 , i ∣ Y n ) ≤ ∑ i = 1 n H b ( p i ( n ) ) + ∑ i = 1 n p i ( n ) log ( ∣ S 0 ∣ ∣ S 1 ∣ ∣ S 2 ∣ − 1 ) ≤ n H b ( β ( n ) ) + n β ( n ) log ( ∣ S 0 ∣ ∣ S 1 ∣ ∣ S 2 ∣ − 1 ) = n δ β ( n ) . (24) \begin{aligned}
H(S_0^n,S_1^n,S_2^n \mid Y^n)
&= \sum_{i=1}^{n} H(S_{0,i},S_{1,i},S_{2,i} \mid S_0^{i-1},S_1^{i-1},S_2^{i-1},Y^n)\\
&\le\sum_{i=1}^{n} H(S_{0,i},S_{1,i},S_{2,i} \mid Y^n)\\
&\le\sum_{i=1}^{n} H_b(p_i^{(n)})+\sum_{i=1}^{n}p_i^{(n)}\log\left(\lvert\mathcal{S}_0\rvert\lvert\mathcal{S}_1\rvert\lvert\mathcal{S}_2\rvert-1\right)\\
&\le nH_b(\beta^{(n)})+n\beta^{(n)}\log\left(\lvert\mathcal{S}_0\rvert\lvert\mathcal{S}_1\rvert\lvert\mathcal{S}_2\rvert-1\right)\\
&=n\delta_\beta^{(n)}. \tag*{(24)}
\end{aligned} H ( S 0 n , S 1 n , S 2 n ∣ Y n ) = i = 1 ∑ n H ( S 0 , i , S 1 , i , S 2 , i ∣ S 0 i − 1 , S 1 i − 1 , S 2 i − 1 , Y n ) ≤ i = 1 ∑ n H ( S 0 , i , S 1 , i , S 2 , i ∣ Y n ) ≤ i = 1 ∑ n H b ( p i ( n ) ) + i = 1 ∑ n p i ( n ) log ( ∣ S 0 ∣ ∣ S 1 ∣ ∣ S 2 ∣ − 1 ) ≤ n H b ( β ( n ) ) + n β ( n ) log ( ∣ S 0 ∣ ∣ S 1 ∣ ∣ S 2 ∣ − 1 ) = n δ β ( n ) . (24)
From (20) and (22), we obtain
H ( M 1 , M 2 , S 0 n , S 1 n , S 2 n ∣ Y n ) ≤ H ( M 1 , M 2 ∣ Y n ) + H ( S 0 n , S 1 n , S 2 n ∣ Y n ) ≤ n ( δ ϵ ( n ) + δ β ( n ) ) = n η n . (25) \begin{aligned}
H(M_1,M_2,S_0^n,S_1^n,S_2^n \mid Y^n)
&\le H(M_1,M_2\mid Y^n)+H(S_0^n,S_1^n,S_2^n\mid Y^n)\\
&\le n\left(\delta_\epsilon^{(n)}+\delta_\beta^{(n)}\right)=n\eta_n. \tag*{(25)}
\end{aligned} H ( M 1 , M 2 , S 0 n , S 1 n , S 2 n ∣ Y n ) ≤ H ( M 1 , M 2 ∣ Y n ) + H ( S 0 n , S 1 n , S 2 n ∣ Y n ) ≤ n ( δ ϵ ( n ) + δ β ( n ) ) = n η n . (25)
Consequently, the conditional entropies obtained by revealing M 1 M_1 M 1 , M 2 M_2 M 2 , or any subset of the state sequences given Y n Y^n Y n are also at most n η n n\eta_n n η n .
For each i ∈ [ 1 : n ] i\in[1:n] i ∈ [ 1 : n ] , define the common-state history
V i ≜ S 0 i − 1 . (26) V_i\triangleq S_0^{i-1}. \tag*{(26)} V i ≜ S 0 i − 1 . (26)
Since the state sequence is IID, V i V_i V i is independent of ( S 0 , i , S 1 , i , S 2 , i ) (S_{0,i},S_{1,i},S_{2,i}) ( S 0 , i , S 1 , i , S 2 , i ) . Conditioned on ( S 0 , i , S 1 , i , S 2 , i , V i ) (S_{0,i},S_{1,i},S_{2,i},V_i) ( S 0 , i , S 1 , i , S 2 , i , V i ) , the inputs X 1 , i X_{1,i} X 1 , i and X 2 , i X_{2,i} X 2 , i are independent, because the private state histories and messages are independent. Hence, the factorization
P X 1 , i X 2 , i ∣ S 0 , i S 1 , i S 2 , i V i = P X 1 , i ∣ S 0 , i S 1 , i V i P X 2 , i ∣ S 0 , i S 2 , i V i . (27) P_{X_{1,i}X_{2,i}\mid S_{0,i}S_{1,i}S_{2,i}V_i}
=P_{X_{1,i}\mid S_{0,i}S_{1,i}V_i}P_{X_{2,i}\mid S_{0,i}S_{2,i}V_i}. \tag*{(27)} P X 1 , i X 2 , i ∣ S 0 , i S 1 , i S 2 , i V i = P X 1 , i ∣ S 0 , i S 1 , i V i P X 2 , i ∣ S 0 , i S 2 , i V i . (27)
Since the message M 1 M_1 M 1 that Encoder 1 wishes to convey and its private state S 1 n S_1^n S 1 n are independent and as a pair are independent of ( M 2 , S 0 n , S 2 n ) (M_2,S_0^n,S_2^n) ( M 2 , S 0 n , S 2 n ) ,
n ( R 1 + ϵ 0 + H ( S 1 ) ) = H ( M 1 , S 1 n ∣ M 2 , S 0 n , S 2 n ) (28) n\left(R_1+\epsilon_0+H(S_1)\right)
=H(M_1,S_1^n\mid M_2,S_0^n,S_2^n) \tag*{(28)} n ( R 1 + ϵ 0 + H ( S 1 ) ) = H ( M 1 , S 1 n ∣ M 2 , S 0 n , S 2 n ) (28)
≤ I ( M 1 , S 1 n ; Y n ∣ M 2 , S 0 n , S 2 n ) + n η n (29) \le I(M_1,S_1^n;Y^n\mid M_2,S_0^n,S_2^n)+n\eta_n \tag*{(29)} ≤ I ( M 1 , S 1 n ; Y n ∣ M 2 , S 0 n , S 2 n ) + n η n (29)
= ∑ i = 1 n [ H ( Y i ∣ Y i − 1 , M 2 , S 0 n , S 2 n ) − H ( Y i ∣ Y i − 1 , M 1 , M 2 , S 0 n , S 1 n , S 2 n ) ] + n η n (30) =\sum_{i=1}^{n}\left[H(Y_i\mid Y^{i-1},M_2,S_0^n,S_2^n)-H(Y_i\mid Y^{i-1},M_1,M_2,S_0^n,S_1^n,S_2^n)\right]+n\eta_n \tag*{(30)} = i = 1 ∑ n [ H ( Y i ∣ Y i − 1 , M 2 , S 0 n , S 2 n ) − H ( Y i ∣ Y i − 1 , M 1 , M 2 , S 0 n , S 1 n , S 2 n ) ] + n η n (30)
≤ ∑ i = 1 n [ H ( Y i ∣ X 2 , i , S 0 , i , S 2 , i , V i ) − H ( Y i ∣ X 1 , i , X 2 , i , S 0 , i , S 1 , i , S 2 , i , V i ) ] + n η n (31) \le\sum_{i=1}^{n}\left[H(Y_i\mid X_{2,i},S_{0,i},S_{2,i},V_i)-H(Y_i\mid X_{1,i},X_{2,i},S_{0,i},S_{1,i},S_{2,i},V_i)\right]+n\eta_n \tag*{(31)} ≤ i = 1 ∑ n [ H ( Y i ∣ X 2 , i , S 0 , i , S 2 , i , V i ) − H ( Y i ∣ X 1 , i , X 2 , i , S 0 , i , S 1 , i , S 2 , i , V i ) ] + n η n (31)
= ∑ i = 1 n I ( X 1 , i , S 1 , i ; Y i ∣ X 2 , i , S 0 , i , S 2 , i , V i ) + n η n , (32) =\sum_{i=1}^{n}I(X_{1,i},S_{1,i};Y_i\mid X_{2,i},S_{0,i},S_{2,i},V_i)+n\eta_n, \tag*{(32)} = i = 1 ∑ n I ( X 1 , i , S 1 , i ; Y i ∣ X 2 , i , S 0 , i , S 2 , i , V i ) + n η n , (32)
where (26d) holds because X 2 , i X_{2,i} X 2 , i is a function of ( M 2 , S 0 i , S 2 i ) (M_2,S_0^i,S_2^i) ( M 2 , S 0 i , S 2 i ) and because the channel is memoryless.
By symmetry,
n ( R 2 + ϵ 0 + H ( S 2 ) ) ≤ ∑ i = 1 n I ( X 2 , i , S 2 , i ; Y i ∣ X 1 , i , S 0 , i , S 1 , i , V i ) + n η n . (33) n(R_2+\epsilon_0+H(S_2))\le\sum_{i=1}^{n}I(X_{2,i},S_{2,i};Y_i\mid X_{1,i},S_{0,i},S_{1,i},V_i)+n\eta_n. \tag*{(33)} n ( R 2 + ϵ 0 + H ( S 2 )) ≤ i = 1 ∑ n I ( X 2 , i , S 2 , i ; Y i ∣ X 1 , i , S 0 , i , S 1 , i , V i ) + n η n . (33)
Conditioning on the common state sequence yields the private-state sum bound
n ( R 1 + R 2 + 2 ϵ 0 + H ( S 1 ) + H ( S 2 ) ) = H ( M 1 , M 2 , S 1 n , S 2 n ∣ S 0 n ) (34) \begin{aligned}
n(R_1+R_2+2\epsilon_0+H(S_1)+H(S_2)) \\
&=H(M_1,M_2,S_1^n,S_2^n\mid S_0^n) \tag*{(34)}
\end{aligned} n ( R 1 + R 2 + 2 ϵ 0 + H ( S 1 ) + H ( S 2 )) = H ( M 1 , M 2 , S 1 n , S 2 n ∣ S 0 n ) (34)
≤ I ( M 1 , M 2 , S 1 n , S 2 n ; Y n ∣ S 0 n ) + n η n (35) \le I(M_1,M_2,S_1^n,S_2^n;Y^n\mid S_0^n)+n\eta_n \tag*{(35)} ≤ I ( M 1 , M 2 , S 1 n , S 2 n ; Y n ∣ S 0 n ) + n η n (35)
= ∑ i = 1 n H ( Y i ∣ Y i − 1 , S 0 n ) − H ( Y i ∣ Y i − 1 , S 0 n , M 1 , M 2 , S 1 n , S 2 n ) + n η n (36) =\sum_{i=1}^{n}H(Y_i\mid Y^{i-1},S_0^n)-H(Y_i\mid Y^{i-1},S_0^n,M_1,M_2,S_1^n,S_2^n)+n\eta_n \tag*{(36)} = i = 1 ∑ n H ( Y i ∣ Y i − 1 , S 0 n ) − H ( Y i ∣ Y i − 1 , S 0 n , M 1 , M 2 , S 1 n , S 2 n ) + n η n (36)
≤ ∑ i = 1 n I ( X 1 , i , X 2 , i , S 1 , i , S 2 , i ; Y i ∣ S 0 , i , V i ) + n η n . (37) \le\sum_{i=1}^{n}I(X_{1,i},X_{2,i},S_{1,i},S_{2,i};Y_i\mid S_{0,i},V_i)+n\eta_n. \tag*{(37)} ≤ i = 1 ∑ n I ( X 1 , i , X 2 , i , S 1 , i , S 2 , i ; Y i ∣ S 0 , i , V i ) + n η n . (37)
Finally, accounting for all three states:
n ( R 1 + R 2 + 2 ϵ 0 + H ( S 0 ) + H ( S 1 ) + H ( S 2 ) ) = H ( M 1 , M 2 , S 0 n , S 1 n , S 2 n ) (38) \begin{aligned}
n(R_1+R_2+2\epsilon_0+H(S_0)+H(S_1)+H(S_2)) \\
&=H(M_1,M_2,S_0^n,S_1^n,S_2^n) \tag*{(38)}
\end{aligned} n ( R 1 + R 2 + 2 ϵ 0 + H ( S 0 ) + H ( S 1 ) + H ( S 2 )) = H ( M 1 , M 2 , S 0 n , S 1 n , S 2 n ) (38)
≤ I ( M 1 , M 2 , S 0 n , S 1 n , S 2 n ; Y n ) + n η n (39) \le I(M_1,M_2,S_0^n,S_1^n,S_2^n;Y^n)+n\eta_n \tag*{(39)} ≤ I ( M 1 , M 2 , S 0 n , S 1 n , S 2 n ; Y n ) + n η n (39)
= H ( Y n ) − H ( Y n ∣ M 1 , M 2 , S 0 n , S 1 n , S 2 n ) + n η n (40) =H(Y^n)-H(Y^n\mid M_1,M_2,S_0^n,S_1^n,S_2^n)+n\eta_n \tag*{(40)} = H ( Y n ) − H ( Y n ∣ M 1 , M 2 , S 0 n , S 1 n , S 2 n ) + n η n (40)
≤ ∑ i = 1 n [ H ( Y i ) − H ( Y i ∣ X 1 , i , X 2 , i , S 0 , i , S 1 , i , S 2 , i ) ] + n η n (41) \le\sum_{i=1}^{n}\left[H(Y_i)-H(Y_i\mid X_{1,i},X_{2,i},S_{0,i},S_{1,i},S_{2,i})\right]+n\eta_n \tag*{(41)} ≤ i = 1 ∑ n [ H ( Y i ) − H ( Y i ∣ X 1 , i , X 2 , i , S 0 , i , S 1 , i , S 2 , i ) ] + n η n (41)
= ∑ i = 1 n I ( X 1 , i , X 2 , i , S 0 , i , S 1 , i , S 2 , i ; Y i ) + n η n . (42) =\sum_{i=1}^{n}I(X_{1,i},X_{2,i},S_{0,i},S_{1,i},S_{2,i};Y_i)+n\eta_n. \tag*{(42)} = i = 1 ∑ n I ( X 1 , i , X 2 , i , S 0 , i , S 1 , i , S 2 , i ; Y i ) + n η n . (42)
To single-letterize, let J J J be uniform on [ 1 : n ] [1:n] [ 1 : n ] and independent of all the other random variables, and define
Q ≜ J , V ≜ V J , ( S 0 , S 1 , S 2 , X 1 , X 2 , Y ) ≜ ( S 0 , J , S 1 , J , S 2 , J , X 1 , J , X 2 , J , Y J ) . (43) Q \triangleq J,\qquad V \triangleq V_J,\qquad(S_0,S_1,S_2,X_1,X_2,Y) \triangleq(S_{0,J},S_{1,J},S_{2,J},X_{1,J},X_{2,J},Y_J). \tag*{(43)} Q ≜ J , V ≜ V J , ( S 0 , S 1 , S 2 , X 1 , X 2 , Y ) ≜ ( S 0 , J , S 1 , J , S 2 , J , X 1 , J , X 2 , J , Y J ) . (43)
For each n n n , denote the induced joint PMF by P ( n ) P^{(n)} P ( n ) . It factorizes as
P Q P S 0 P S 1 P S 2 P V ∣ Q P X 1 ∣ S 0 S 1 V Q P X 2 ∣ S 0 S 2 V Q W Y ∣ X 1 X 2 S 0 S 1 S 2 . (44) P_Q P_{S_0} P_{S_1} P_{S_2} P_{V|Q} P_{X_1|S_0S_1VQ} P_{X_2|S_0S_2VQ} W_{Y|X_1X_2S_0S_1S_2}. \tag*{(44)} P Q P S 0 P S 1 P S 2 P V ∣ Q P X 1 ∣ S 0 S 1 V Q P X 2 ∣ S 0 S 2 V Q W Y ∣ X 1 X 2 S 0 S 1 S 2 . (44)
Thus, P ( n ) ∈ P P^{(n)} \in\mathcal{P} P ( n ) ∈ P .
Dividing (26e), (27), (28d), and (29e) by n n n and subtracting the entropy terms from both sides yields
R 1 ≤ I ( X 1 , S 1 ; Y ∣ X 2 , S 0 , S 2 , V , Q ) − H ( S 1 ) − ϵ 0 + η n (45) R_1 \le I(X_1,S_1;Y|X_2,S_0,S_2,V,Q)-H(S_1)-\epsilon_0+\eta_n \tag*{(45)} R 1 ≤ I ( X 1 , S 1 ; Y ∣ X 2 , S 0 , S 2 , V , Q ) − H ( S 1 ) − ϵ 0 + η n (45)
R 2 ≤ I ( X 2 , S 2 ; Y ∣ X 1 , S 0 , S 1 , V , Q ) − H ( S 2 ) − ϵ 0 + η n (46) R_2 \le I(X_2,S_2;Y|X_1,S_0,S_1,V,Q)-H(S_2)-\epsilon_0+\eta_n \tag*{(46)} R 2 ≤ I ( X 2 , S 2 ; Y ∣ X 1 , S 0 , S 1 , V , Q ) − H ( S 2 ) − ϵ 0 + η n (46)
R 1 + R 2 ≤ I ( X 1 , X 2 , S 1 , S 2 ; Y ∣ S 0 , V , Q ) − H ( S 1 ) − H ( S 2 ) − 2 ϵ 0 + η n (47) R_1+R_2 \le I(X_1,X_2,S_1,S_2;Y|S_0,V,Q)-H(S_1)-H(S_2)-2\epsilon_0+\eta_n \tag*{(47)} R 1 + R 2 ≤ I ( X 1 , X 2 , S 1 , S 2 ; Y ∣ S 0 , V , Q ) − H ( S 1 ) − H ( S 2 ) − 2 ϵ 0 + η n (47)
R 1 + R 2 ≤ I ( X 1 , X 2 , S 0 , S 1 , S 2 ; Y ∣ Q ) − H ( S 0 ) − H ( S 1 ) − H ( S 2 ) − 2 ϵ 0 + η n , (48) R_1+R_2 \le I(X_1,X_2,S_0,S_1,S_2;Y|Q)-H(S_0)-H(S_1)-H(S_2)-2\epsilon_0+\eta_n, \tag*{(48)} R 1 + R 2 ≤ I ( X 1 , X 2 , S 0 , S 1 , S 2 ; Y ∣ Q ) − H ( S 0 ) − H ( S 1 ) − H ( S 2 ) − 2 ϵ 0 + η n , (48)
where the quantities on the right-hand sides are evaluated under P ( n ) P^{(n)} P ( n ) .
Since η n → 0 \eta_n \to0 η n → 0 , we can choose n n n sufficiently large so that η n < ϵ 0 \eta_n < \epsilon_0 η n < ϵ 0 . All four strict inequalities in (11) then hold under P ( n ) P^{(n)} P ( n ) , and hence
( R 1 , R 2 ) ∈ R < ( P ( n ) ) ⊆ ⋃ P ∈ P R < ( P ) . (49) (R_1,R_2) \in\mathcal{R}_{<}(P^{(n)}) \subseteq\bigcup_{P\in\mathcal{P}} \mathcal{R}_{<}(P). \tag*{(49)} ( R 1 , R 2 ) ∈ R < ( P ( n ) ) ⊆ P ∈ P ⋃ R < ( P ) . (49)
Thus, every achievable rate pair belongs to the above union, and C \mathcal{C} C —the closure of the set of all achievable rates—is thus contained in the closure of the RHS of (33), i.e., in C ( I ) \mathcal{C}^{(I)} C ( I ) .
Achievability
Given some fixed joint PMF of the form
P Q P S 0 P S 1 P S 2 P V ∣ Q P X 1 ∣ S 0 S 1 V Q P X 2 ∣ S 0 S 2 V Q P Y ∣ X 1 X 2 S 0 S 1 S 2 (50) P_Q P_{S_0} P_{S_1} P_{S_2} P_{V|Q} P_{X_1|S_0S_1VQ} P_{X_2|S_0S_2VQ} P_{Y|X_1X_2S_0S_1S_2} \tag*{(50)} P Q P S 0 P S 1 P S 2 P V ∣ Q P X 1 ∣ S 0 S 1 V Q P X 2 ∣ S 0 S 2 V Q P Y ∣ X 1 X 2 S 0 S 1 S 2 (50)
we need to establish the achievability of the polytope R < ( P ) \mathcal{R}_{<}(P) R < ( P ) , which we henceforth assume is nonempty . To that end, we first express it as the marginal distribution of a distribution involving Shannon strategies.
Introducing Shannon Strategies
By the Functional Representation Lemma [4 Appendix B] , there exist finite-alphabet random variables T 1 , T 2 T_1,T_2 T 1 , T 2 of some conditional PMFs P T 1 ∣ V Q P_{T_1|VQ} P T 1 ∣ V Q and P T 2 ∣ V Q P_{T_2|VQ} P T 2 ∣ V Q , and some deterministic functions x 1 ( ⋅ ) , x 2 ( ⋅ ) x_1(\cdot),x_2(\cdot) x 1 ( ⋅ ) , x 2 ( ⋅ ) such that
X 1 = x 1 ( T 1 , S 0 , S 1 ) , X 2 = x 2 ( T 2 , S 0 , S 2 ) . (51) X_1=x_1(T_1,S_0,S_1),\qquad X_2=x_2(T_2,S_0,S_2). \tag*{(51)} X 1 = x 1 ( T 1 , S 0 , S 1 ) , X 2 = x 2 ( T 2 , S 0 , S 2 ) . (51)
More specifically, the joint PMF of ( T 1 , T 2 ) (T_1,T_2) ( T 1 , T 2 ) and the other variables has the form
P Q S 0 S 1 S 2 V T 1 T 2 X 1 X 2 Y = P Q P S 0 P S 1 P S 2 P V ∣ Q P T 1 ∣ V Q P T 2 ∣ V Q ⋅ 1 { X 1 = x 1 ( T 1 , S 0 , S 1 ) } 1 { X 2 = x 2 ( T 2 , S 0 , S 2 ) } P Y ∣ X 1 X 2 S 0 S 1 S 2 . (52) \begin{aligned}
P_{QS_0S_1S_2VT_1T_2X_1X_2Y}
&=P_QP_{S_0}P_{S_1}P_{S_2}P_{V|Q}P_{T_1|VQ}P_{T_2|VQ}\\
&\quad\cdot\mathbb{1}\{X_1=x_1(T_1,S_0,S_1)\}\mathbb{1}\{X_2=x_2(T_2,S_0,S_2)\}P_{Y|X_1X_2S_0S_1S_2}. \tag*{(52)}
\end{aligned} P Q S 0 S 1 S 2 V T 1 T 2 X 1 X 2 Y = P Q P S 0 P S 1 P S 2 P V ∣ Q P T 1 ∣ V Q P T 2 ∣ V Q ⋅ 1 { X 1 = x 1 ( T 1 , S 0 , S 1 )} 1 { X 2 = x 2 ( T 2 , S 0 , S 2 )} P Y ∣ X 1 X 2 S 0 S 1 S 2 . (52)
In particular, the following are Markov chains:
( S 0 , S 1 , S 2 ) ⊸ ( V , Q ) ⊸ ( T 1 , T 2 ) (53) (S_0,S_1,S_2)\multimap(V,Q)\multimap(T_1,T_2) \tag*{(53)} ( S 0 , S 1 , S 2 ) ⊸ ( V , Q ) ⊸ ( T 1 , T 2 ) (53)
T 1 ⊸ ( V , Q ) ⊸ T 2 (54) T_1\multimap(V,Q)\multimap T_2 \tag*{(54)} T 1 ⊸ ( V , Q ) ⊸ T 2 (54)
( V , Q , T 1 , T 2 ) ⊸ ( X 1 , X 2 , S 0 , S 1 , S 2 ) ⊸ Y (55) (V,Q,T_1,T_2)\multimap(X_1,X_2,S_0,S_1,S_2)\multimap Y \tag*{(55)} ( V , Q , T 1 , T 2 ) ⊸ ( X 1 , X 2 , S 0 , S 1 , S 2 ) ⊸ Y (55)
T 1 ⊸ ( V , Q , X 1 , S 0 , S 1 ) ⊸ Y (56) T_1\multimap(V,Q,X_1,S_0,S_1)\multimap Y \tag*{(56)} T 1 ⊸ ( V , Q , X 1 , S 0 , S 1 ) ⊸ Y (56)
T 2 ⊸ ( V , Q , X 2 , S 0 , S 2 ) ⊸ Y (57) T_2\multimap(V,Q,X_2,S_0,S_2)\multimap Y \tag*{(57)} T 2 ⊸ ( V , Q , X 2 , S 0 , S 2 ) ⊸ Y (57)
( T 1 , S 1 ) ⊸ ( V , Q , S 0 ) ⊸ ( T 2 , S 2 ) . (58) (T_1,S_1)\multimap(V,Q,S_0)\multimap(T_2,S_2). \tag*{(58)} ( T 1 , S 1 ) ⊸ ( V , Q , S 0 ) ⊸ ( T 2 , S 2 ) . (58)
As we next argue, because X k X_k X k is a deterministic function of ( T k , S 0 , S k ) (T_k,S_0,S_k) ( T k , S 0 , S k ) , for each k ∈ { 1 , 2 } k \in\{1,2\} k ∈ { 1 , 2 } , and because the channel output depends on T 1 , T 2 T_1,T_2 T 1 , T 2 only through X 1 , X 2 X_1,X_2 X 1 , X 2 ,
I ( T 1 , S 1 ; Y ∣ T 2 , S 0 , S 2 , V , Q ) = I ( X 1 , S 1 ; Y ∣ X 2 , S 0 , S 2 , V , Q ) , (59) I(T_1,S_1;Y\mid T_2,S_0,S_2,V,Q)=I(X_1,S_1;Y\mid X_2,S_0,S_2,V,Q), \tag*{(59)} I ( T 1 , S 1 ; Y ∣ T 2 , S 0 , S 2 , V , Q ) = I ( X 1 , S 1 ; Y ∣ X 2 , S 0 , S 2 , V , Q ) , (59)
I ( T 2 , S 2 ; Y ∣ T 1 , S 0 , S 1 , V , Q ) = I ( X 2 , S 2 ; Y ∣ X 1 , S 0 , S 1 , V , Q ) , (60) I(T_2,S_2;Y\mid T_1,S_0,S_1,V,Q)=I(X_2,S_2;Y\mid X_1,S_0,S_1,V,Q), \tag*{(60)} I ( T 2 , S 2 ; Y ∣ T 1 , S 0 , S 1 , V , Q ) = I ( X 2 , S 2 ; Y ∣ X 1 , S 0 , S 1 , V , Q ) , (60)
I ( T 1 , T 2 , S 1 , S 2 ; Y ∣ S 0 , V , Q ) = I ( X 1 , X 2 , S 1 , S 2 ; Y ∣ S 0 , V , Q ) , (61) I(T_1,T_2,S_1,S_2;Y\mid S_0,V,Q)=I(X_1,X_2,S_1,S_2;Y\mid S_0,V,Q), \tag*{(61)} I ( T 1 , T 2 , S 1 , S 2 ; Y ∣ S 0 , V , Q ) = I ( X 1 , X 2 , S 1 , S 2 ; Y ∣ S 0 , V , Q ) , (61)
I ( V , T 1 , T 2 , S 0 , S 1 , S 2 ; Y ∣ Q ) = I ( X 1 , X 2 , S 0 , S 1 , S 2 ; Y ∣ Q ) . (62) I(V,T_1,T_2,S_0,S_1,S_2;Y\mid Q)=I(X_1,X_2,S_0,S_1,S_2;Y\mid Q). \tag*{(62)} I ( V , T 1 , T 2 , S 0 , S 1 , S 2 ; Y ∣ Q ) = I ( X 1 , X 2 , S 0 , S 1 , S 2 ; Y ∣ Q ) . (62)
Indeed, the first identity in (38) holds because
I ( T 1 , S 1 ; Y ∣ T 2 , S 0 , S 2 , V , Q ) = ( a ) H ( Y ∣ T 2 , X 2 , S 0 , S 2 , V , Q ) − H ( Y ∣ T 1 , X 1 , T 2 , X 2 , S 0 , S 1 , S 2 , V , Q ) = ( b ) H ( Y ∣ X 2 , S 0 , S 2 , V , Q ) − H ( Y ∣ X 1 , X 2 , S 0 , S 1 , S 2 , V , Q ) = I ( X 1 , S 1 ; Y ∣ X 2 , S 0 , S 2 , V , Q ) . (63) \begin{aligned}
I(T_1,S_1;Y\mid T_2,S_0,S_2,V,Q)
&\overset{(a)}{=}H(Y\mid T_2,X_2,S_0,S_2,V,Q)-H(Y\mid T_1,X_1,T_2,X_2,S_0,S_1,S_2,V,Q)\\
&\overset{(b)}{=}H(Y\mid X_2,S_0,S_2,V,Q)-H(Y\mid X_1,X_2,S_0,S_1,S_2,V,Q)\\
&=I(X_1,S_1;Y\mid X_2,S_0,S_2,V,Q). \tag*{(63)}
\end{aligned} I ( T 1 , S 1 ; Y ∣ T 2 , S 0 , S 2 , V , Q ) = ( a ) H ( Y ∣ T 2 , X 2 , S 0 , S 2 , V , Q ) − H ( Y ∣ T 1 , X 1 , T 2 , X 2 , S 0 , S 1 , S 2 , V , Q ) = ( b ) H ( Y ∣ X 2 , S 0 , S 2 , V , Q ) − H ( Y ∣ X 1 , X 2 , S 0 , S 1 , S 2 , V , Q ) = I ( X 1 , S 1 ; Y ∣ X 2 , S 0 , S 2 , V , Q ) . (63)
Here, ( a ) (a) ( a ) follows from the fact that X 1 X_1 X 1 and X 2 X_2 X 2 are deterministic functions of ( T 1 , S 0 , S 1 ) (T_1,S_0,S_1) ( T 1 , S 0 , S 1 ) and ( T 2 , S 0 , S 2 ) (T_2,S_0,S_2) ( T 2 , S 0 , S 2 ) , respectively, and ( b ) (b) ( b ) follows from the Markov chains (37c) and (37e). The remaining identities in (38) follow analogously.
We conclude that R < ( P ) \mathcal{R}_{<}(P) R < ( P ) can be expressed as
{ R 1 < I ( T 1 , S 1 ; Y ∣ T 2 , S 0 , S 2 , V , Q ) − H ( S 1 ) , R 2 < I ( T 2 , S 2 ; Y ∣ T 1 , S 0 , S 1 , V , Q ) − H ( S 2 ) , R 1 + R 2 < I ( T 1 , T 2 , S 1 , S 2 ; Y ∣ S 0 , V , Q ) − H ( S 1 ) − H ( S 2 ) , R 1 + R 2 < I ( T 1 , T 2 , S 0 , S 1 , S 2 ; Y ∣ Q ) − H ( S 0 ) − H ( S 1 ) − H ( S 2 ) (64) \left\{
\begin{aligned}
R_1 &< I(T_1,S_1;Y\mid T_2,S_0,S_2,V,Q)-H(S_1),\\
R_2 &< I(T_2,S_2;Y\mid T_1,S_0,S_1,V,Q)-H(S_2),\\
R_1+R_2 &< I(T_1,T_2,S_1,S_2;Y\mid S_0,V,Q)-H(S_1)-H(S_2),\\
R_1+R_2 &< I(T_1,T_2,S_0,S_1,S_2;Y\mid Q)-H(S_0)-H(S_1)-H(S_2)
\end{aligned}
\right. \tag*{(64)} ⎩ ⎨ ⎧ R 1 R 2 R 1 + R 2 R 1 + R 2 < I ( T 1 , S 1 ; Y ∣ T 2 , S 0 , S 2 , V , Q ) − H ( S 1 ) , < I ( T 2 , S 2 ; Y ∣ T 1 , S 0 , S 1 , V , Q ) − H ( S 2 ) , < I ( T 1 , T 2 , S 1 , S 2 ; Y ∣ S 0 , V , Q ) − H ( S 1 ) − H ( S 2 ) , < I ( T 1 , T 2 , S 0 , S 1 , S 2 ; Y ∣ Q ) − H ( S 0 ) − H ( S 1 ) − H ( S 2 ) (64)
The Polytope and its Vertices
For a fixed PMF P P P as in (36), define
A 1 ≜ I ( T 1 , S 1 ; Y ∣ V , T 2 , S 0 , S 2 , Q ) − H ( S 1 ) , A 2 ≜ I ( T 2 , S 2 ; Y ∣ V , T 1 , S 0 , S 1 , Q ) − H ( S 2 ) , C p ≜ I ( T 1 , T 2 , S 1 , S 2 ; Y ∣ V , S 0 , Q ) − H ( S 1 ) − H ( S 2 ) , C t ≜ I ( V , T 1 , T 2 , S 0 , S 1 , S 2 ; Y ∣ Q ) − H ( S 0 ) − H ( S 1 ) − H ( S 2 ) , C ≜ min { C p , C t } . (65) \begin{aligned}
A_1 &\triangleq I(T_1,S_1;Y\mid V,T_2,S_0,S_2,Q)-H(S_1),\\
A_2 &\triangleq I(T_2,S_2;Y\mid V,T_1,S_0,S_1,Q)-H(S_2),\\
C_p &\triangleq I(T_1,T_2,S_1,S_2;Y\mid V,S_0,Q)-H(S_1)-H(S_2),\\
C_t &\triangleq I(V,T_1,T_2,S_0,S_1,S_2;Y\mid Q)-H(S_0)-H(S_1)-H(S_2),\\
C &\triangleq\min\{C_p,C_t\}. \tag*{(65)}
\end{aligned} A 1 A 2 C p C t C ≜ I ( T 1 , S 1 ; Y ∣ V , T 2 , S 0 , S 2 , Q ) − H ( S 1 ) , ≜ I ( T 2 , S 2 ; Y ∣ V , T 1 , S 0 , S 1 , Q ) − H ( S 2 ) , ≜ I ( T 1 , T 2 , S 1 , S 2 ; Y ∣ V , S 0 , Q ) − H ( S 1 ) − H ( S 2 ) , ≜ I ( V , T 1 , T 2 , S 0 , S 1 , S 2 ; Y ∣ Q ) − H ( S 0 ) − H ( S 1 ) − H ( S 2 ) , ≜ min { C p , C t } . (65)
With these definitions, we can express the nonempty polytope R < ( P ) \mathcal{R}_{<}(P) R < ( P ) of (40) as comprising the rate pairs satisfying
0 ≤ R 1 < A 1 , 0 ≤ R 2 < A 2 , R 1 + R 2 < C . (66) 0\le R_1<A_1,\qquad0\le R_2<A_2,\qquad R_1+R_2<C. \tag*{(66)} 0 ≤ R 1 < A 1 , 0 ≤ R 2 < A 2 , R 1 + R 2 < C . (66)
We note that
C ≤ A 1 + A 2 . (67) C\le A_1+A_2. \tag*{(67)} C ≤ A 1 + A 2 . (67)
Indeed, the stronger inequality C p ≤ A 1 + A 2 C_p\le A_1+A_2 C p ≤ A 1 + A 2 holds because
A 1 + A 2 − C p = I ( T 1 , S 1 ; T 2 , S 2 ∣ Y , V , S 0 , Q ) , (68) A_1+A_2-C_p=I(T_1,S_1;T_2,S_2\mid Y,V,S_0,Q), \tag*{(68)} A 1 + A 2 − C p = I ( T 1 , S 1 ; T 2 , S 2 ∣ Y , V , S 0 , Q ) , (68)
as can be verified using the chain rule and the Markov condition (37f).
Let P + ≜ { P ∈ P : R < ( P ) ≠ ∅ } \mathcal{P}_+\triangleq\{P\in\mathcal{P}: \mathcal{R}_{<}(P)\ne\varnothing\} P + ≜ { P ∈ P : R < ( P ) = ∅ } denote the subfamily of PMFs that induce nonempty strict rate polytopes. From (43), we conclude that, for every P ∈ P + P\in\mathcal{P}_+ P ∈ P + , the polytope R < ( P ) \mathcal{R}_{<}(P) R < ( P ) has one of the four shapes depicted in Figure 2 . Its closure is the polytope R ≤ ( P ) \mathcal{R}_{\le}(P) R ≤ ( P ) obtained by replacing the strict inequalities in (66) with weak inequalities.
Figure 2. Subfigure 2.1: C ≥ A 1 C \ge A_1 C ≥ A 1 , C ≥ A 2 C \ge A_2 C ≥ A 2 ; Subfigure 2.2: C ≥ A 1 C \ge A_1 C ≥ A 1 , C < A 2 C < A_2 C < A 2 ; Subfigure 2.3: C < A 1 C < A_1 C < A 1 , C ≥ A 2 C \ge A_2 C ≥ A 2 ; Subfigure 2.4: C < A 1 C < A_1 C < A 1 , C < A 2 C < A_2 C < A 2 . The four possible shapes of a nonempty polytope R ≤ ( P ) \mathcal{R}_{\le}(P) R ≤ ( P ) . By symmetry, to establish that the endpoints of the dominant face are all in C \mathcal{C} C , it suffices to consider the colored vertices. The coding scheme for the blue vertices is described in § 5.5.1 , and for the red ones in § 5.5.2 .
The PMFs in P ∖ P + \mathcal{P} \setminus\mathcal{P}_{+} P ∖ P + contribute only empty sets to (13) . Moreover, replacing each set in a family by its closure does not change the closure of their union. Consequently,
C ( I ) = cl ( ⋃ P ∈ P + R ≤ ( P ) ) . (69) \mathcal{C}^{(I)}=\operatorname{cl}\left(\bigcup_{P\in\mathcal{P}_{+}}\mathcal{R}_{\le}(P)\right). \tag*{(69)} C ( I ) = cl P ∈ P + ⋃ R ≤ ( P ) . (69)
Let v ( 1 ) \mathbf{v}^{(1)} v ( 1 ) and v ( 2 ) \mathbf{v}^{(2)} v ( 2 ) denote the two endpoints of the dominant face of R ≤ ( P ) \mathcal{R}_{\le}(P) R ≤ ( P ) . We will show that both are in C \mathcal{C} C by establishing that every neighborhood of each of them contains an achievable rate pair. The convexity of C \mathcal{C} C will then establish that the dominant face is in C \mathcal{C} C , from which it will follow that the entire polytope is in C \mathcal{C} C .
By symmetry, it suffices to consider the following two types of endpoints:
the blue vertices ( A 1 , C − A 1 ) (A_1,C-A_1) ( A 1 , C − A 1 ) in Subfigures 2.1 and 2.2 when C > A 1 C>A_1 C > A 1 ;
the red vertices ( C , 0 ) (C,0) ( C , 0 ) in Subfigures 2.3 and 2.4 when C ≤ A 1 C\le A_1 C ≤ A 1 .
The coding scheme for the blue vertices is described in § 5.5.1 , and for the red ones in § 5.5.2 .
An Overview of the Block-Markov Scheme
We next turn to our proposed Block-Markov scheme with backward decoding. In each length-l l l block we draw random bins for the different (typical) state sequences and use superposition coding. We draw 2 l R 0 b 2^{lR_0^{\mathrm b}} 2 l R 0 b “S 0 S_0 S 0 -bins” that will be used in the next block to describe the S 0 S_0 S 0 state sequence prevailing during the current block; 2 l R 1 b 2^{lR_1^{\mathrm b}} 2 l R 1 b “S 1 S_1 S 1 -bins” that will be used to describe the S 1 S_1 S 1 state sequence; and 2 l R 2 b 2^{lR_2^{\mathrm b}} 2 l R 2 b “S 2 S_2 S 2 bins” for the S 2 S_2 S 2 -sequence. Each of the 2 l R 0 b 2^{lR_0^{\mathrm b}} 2 l R 0 b S 0 S_0 S 0 -bins is indexed by a “bin index” comprising l R 0 b lR_0^{\mathrm b} l R 0 b bits. The index of the S 0 S_0 S 0 -bin that contains the S 0 S_0 S 0 -sequence prevailing in the current block will be conveyed to the receiver in the next block. Likewise for the S 1 S_1 S 1 -bins and the S 2 S_2 S 2 -bins.
The superposition coding is used in order to create three reliable “bit pipes.” One bit pipe—“Encoder 1’s bit pipe”—is used by Encoder 1 to send bits it is cognizant of (e.g., fresh data, the bits that index the bin from the previous block that contained the previous block’s S 1 S_1 S 1 -sequence, and a subset of the bits that index the bin from the previous block that contained the previous block’s S 0 S_0 S 0 -sequence); another bit pipe—“Encoder 2’s bit pipe”—is similarly used by Encoder 2; and yet another bit pipe—the “common pipe”—is to convey bits that are known to both encoders (e.g., all or a subset of the bits that index the bin containing the S 0 S_0 S 0 -sequence of the previous block). If the common pipe cannot support the transmission of all the l R 0 b lR_0^{\mathrm b} l R 0 b bits that index the S 0 S_0 S 0 -bin, then it only conveys a subset of them and the rest are transmitted using Encoder 1’s bit pipe and/or Encoder 2’s bit pipe. Which bit pipe carries the extra bits is determined by the vertex under consideration.
The transmissions in future blocks and the backward decoding guarantee that, when faced with the task of decoding a given block, the decoder is cognizant of the indices of the bins containing the current block’s state sequences.
To simplify the exposition, we describe the transmission in a given block without specifying the nature of the bits transmitted over the bit pipes. They are merely viewed as IID random bits. Their nature depends on the rate pair we need to convey: different rate pairs in the capacity region will require different utilizations of the bit pipes. Moreover, when describing the decoding, we assume that the indices of the bins containing the current block’s state sequences are known to the receiver (thanks to future transmissions and the backward decoding).
A Single Block Favoring Encoder 1
We denote the length of the block l l l , the common message (comprising the common bits) M V M_V M V , and the private messages M 1 M_1 M 1 and M 2 M_2 M 2 . The latter three are of respective rates R V C R_V^C R V C , R 1 P R_1^P R 1 P , and R 2 P R_2^P R 2 P . The state sequences prevailing during the current block are denoted s 0 l s_0^l s 0 l , s 1 l s_1^l s 1 l , and s 2 l s_2^l s 2 l . Those—or more precisely, those that are typical—will be distributed among 2 l R 0 b 2^{lR_0^b} 2 l R 0 b , 2 l R 1 b 2^{lR_1^b} 2 l R 1 b , and 2 l R 2 b 2^{lR_2^b} 2 l R 2 b bins respectively; here R 0 b R_0^b R 0 b , R 1 b R_1^b R 1 b , R 2 b R_2^b R 2 b are the respective binning rates.
Let
δ l ≜ l − 1 / 4 (70) \delta_l \triangleq l^{-1/4} \tag*{(70)} δ l ≜ l − 1/4 (70)
be the typicality parameter, so δ l ↓ 0 \delta_l \downarrow0 δ l ↓ 0 and l δ l 2 = l l\delta_l^2 = \sqrt{l} l δ l 2 = l . We shall use the finite-alphabet strong-typicality bounds in Corollary 4.8 of [18 ] . Define
p min ≜ min { P Q V T 1 T 2 S 0 S 1 S 2 Y ( q , v , t 1 , t 2 , s 0 , s 1 , s 2 , y ) : P Q V T 1 T 2 S 0 S 1 S 2 Y ( q , v , t 1 , t 2 , s 0 , s 1 , s 2 , y ) > 0 } (71) p_{\min} \triangleq\min\left\{P_{QVT_1T_2S_0S_1S_2Y}(q,v,t_1,t_2,s_0,s_1,s_2,y) : P_{QVT_1T_2S_0S_1S_2Y}(q,v,t_1,t_2,s_0,s_1,s_2,y)>0\right\} \tag*{(71)} p m i n ≜ min { P Q V T 1 T 2 S 0 S 1 S 2 Y ( q , v , t 1 , t 2 , s 0 , s 1 , s 2 , y ) : P Q V T 1 T 2 S 0 S 1 S 2 Y ( q , v , t 1 , t 2 , s 0 , s 1 , s 2 , y ) > 0 } (71)
and
τ l ≜ − 2 δ l log p min . (72) \tau_l \triangleq-2\delta_l\log p_{\min}. \tag*{(72)} τ l ≜ − 2 δ l log p m i n . (72)
Since δ l ↓ 0 \delta_l \downarrow0 δ l ↓ 0 , we have τ l → 0 \tau_l \to0 τ l → 0 . The factor two is chosen so that τ l \tau_l τ l uniformly bounds the penalties in all conditional type-class and packing bounds used below.
Random binning and codebooks. For each k ∈ { 0 , 1 , 2 } k \in\{0,1,2\} k ∈ { 0 , 1 , 2 } , assign every typical sequence s k l s_k^l s k l uniformly and independently to one of 2 l R k b 2^{lR_k^b} 2 l R k b bins, and assign atypical sequences an arbitrary default bin. Set L k ( s k l ) L_k(s_k^l) L k ( s k l ) to be the bin index containing s k l s_k^l s k l .
Independently of that, generate a sequence Q l Q^l Q l IID ∼ P Q \sim P_Q ∼ P Q and reveal it to both encoders and to the decoder. For every possible common message m V ∈ [ 1 : 2 l R V C ] m_V \in[1:2^{lR_V^C}] m V ∈ [ 1 : 2 l R V C ] , generate
V l ( m V ) ∼ ∏ i = 1 l P V ∣ Q ( ⋅ ∣ Q i ) . (73) V^l(m_V) \sim\prod_{i=1}^{l}P_{V|Q}(\cdot|Q_i). \tag*{(73)} V l ( m V ) ∼ i = 1 ∏ l P V ∣ Q ( ⋅ ∣ Q i ) . (73)
For every ( m V , m k ) (m_V,m_k) ( m V , m k ) , where m k ∈ [ 1 : 2 l R k P ] m_k \in[1:2^{lR_k^P}] m k ∈ [ 1 : 2 l R k P ] , generate conditionally and independently
T k l ( m V , m k ) ∼ ∏ i = 1 l P T k ∣ V Q ( ⋅ ∣ V i ( m V ) , Q i ) , k ∈ { 1 , 2 } . (74) T_k^l(m_V,m_k) \sim\prod_{i=1}^{l}P_{T_k|VQ}(\cdot|V_i(m_V),Q_i),\qquad k \in\{1,2\}. \tag*{(74)} T k l ( m V , m k ) ∼ i = 1 ∏ l P T k ∣ V Q ( ⋅ ∣ V i ( m V ) , Q i ) , k ∈ { 1 , 2 } . (74)
The Time-i i i symbol produced by Encoder k k k is
X k , i = x k ( T k , i ( M V , M k ) , S 0 , i , S k , i ) , k ∈ { 1 , 2 } . (75) X_{k,i}=x_k\left(T_{k,i}(M_V,M_k),S_{0,i},S_{k,i}\right),\quad k\in\{1,2\}. \tag*{(75)} X k , i = x k ( T k , i ( M V , M k ) , S 0 , i , S k , i ) , k ∈ { 1 , 2 } . (75)
Successive decoding The decoder bases its decision on the indices ℓ 0 = L 0 ( S 0 l ) , ℓ 1 = L 1 ( S 1 l ) , ℓ 2 = L 2 ( S 2 l ) \ell_0=L_0(S_0^l),\ell_1=L_1(S_1^l),\ell_2=L_2(S_2^l) ℓ 0 = L 0 ( S 0 l ) , ℓ 1 = L 1 ( S 1 l ) , ℓ 2 = L 2 ( S 2 l ) of the bins containing the state sequences and on the observation Y l Y^l Y l . (Recall that in the Block-Markov scheme we shall employ, these indices will be available via the backward decoding.) It uses the following order to decode
S 0 l ⟶ M V ⟶ S 2 l ⟶ M 2 ⟶ S 1 l ⟶ M 1 . (76) S_0^l\longrightarrow M_V\longrightarrow S_2^l\longrightarrow M_2\longrightarrow S_1^l\longrightarrow M_1. \tag*{(76)} S 0 l ⟶ M V ⟶ S 2 l ⟶ M 2 ⟶ S 1 l ⟶ M 1 . (76)
More precisely, it performs the following six tests.
Among all the state sequences s ^ 0 l \hat{s}_0^l s ^ 0 l in Bin ℓ 0 \ell_0 ℓ 0 , it finds the unique s ^ 0 l \hat{s}_0^l s ^ 0 l with L 0 ( s ^ 0 l ) = ℓ 0 L_0(\hat{s}_0^l)=\ell_0 L 0 ( s ^ 0 l ) = ℓ 0 such that ( Q l , s ^ 0 l , Y l ) (Q^l,\hat{s}_0^l,Y^l) ( Q l , s ^ 0 l , Y l ) is jointly δ l \delta_l δ l -typical.
Given s ^ 0 l \hat{s}_0^l s ^ 0 l , it finds the unique m ^ V \hat{m}_V m ^ V such that ( Q l , V l ( m ^ V ) , s ^ 0 l , Y l ) (Q^l,V^l(\hat{m}_V),\hat{s}_0^l,Y^l) ( Q l , V l ( m ^ V ) , s ^ 0 l , Y l ) is jointly δ l \delta_l δ l -typical.
Given ( s ^ 0 l , m ^ V ) (\hat{s}_0^l,\hat{m}_V) ( s ^ 0 l , m ^ V ) , it finds the unique s ^ 2 l \hat{s}_2^l s ^ 2 l with L 2 ( s ^ 2 l ) = ℓ 2 L_2(\hat{s}_2^l)=\ell_2 L 2 ( s ^ 2 l ) = ℓ 2 such that ( Q l , V l ( m ^ V ) , s ^ 0 l , s ^ 2 l , Y l ) (Q^l,V^l(\hat{m}_V),\hat{s}_0^l,\hat{s}_2^l,Y^l) ( Q l , V l ( m ^ V ) , s ^ 0 l , s ^ 2 l , Y l ) is jointly δ l \delta_l δ l -typical.
Given ( s ^ 0 l , s ^ 2 l , m ^ V ) (\hat{s}_0^l,\hat{s}_2^l,\hat{m}_V) ( s ^ 0 l , s ^ 2 l , m ^ V ) , it finds the unique m ^ 2 \hat{m}_2 m ^ 2 such that
( Q l , V l ( m ^ V ) , T 2 l ( m ^ V , m ^ 2 ) , s ^ 0 l , s ^ 2 l , Y l ) ∈ T δ l ( l ) . (77) \left(Q^l,V^l(\hat{m}_V),T_2^l(\hat{m}_V,\hat{m}_2),\hat{s}_0^l,\hat{s}_2^l,Y^l\right)\in\mathcal{T}_{\delta_l}^{(l)}. \tag*{(77)} ( Q l , V l ( m ^ V ) , T 2 l ( m ^ V , m ^ 2 ) , s ^ 0 l , s ^ 2 l , Y l ) ∈ T δ l ( l ) . (77)
Given all previously recovered objects, it finds the unique s ^ 1 l \hat{s}_1^l s ^ 1 l with L 1 ( s ^ 1 l ) = ℓ 1 L_1(\hat{s}_1^l)=\ell_1 L 1 ( s ^ 1 l ) = ℓ 1 such that
( Q l , V l ( m ^ V ) , T 2 l ( m ^ V , m ^ 2 ) , s ^ 0 l , s ^ 1 l , s ^ 2 l , Y l ) ∈ T δ l ( l ) . (78) \left(Q^l,V^l(\hat{m}_V),T_2^l(\hat{m}_V,\hat{m}_2),\hat{s}_0^l,\hat{s}_1^l,\hat{s}_2^l,Y^l\right)\in\mathcal{T}_{\delta_l}^{(l)}. \tag*{(78)} ( Q l , V l ( m ^ V ) , T 2 l ( m ^ V , m ^ 2 ) , s ^ 0 l , s ^ 1 l , s ^ 2 l , Y l ) ∈ T δ l ( l ) . (78)
Finally, it finds the unique m ^ 1 \hat{m}_1 m ^ 1 such that
( Q l , V l ( m ^ V ) , T 1 l ( m ^ V , m ^ 1 ) , T 2 l ( m ^ V , m ^ 2 ) , s ^ 0 l , s ^ 1 l , s ^ 2 l , Y l ) ∈ T δ l ( l ) . (79) \left(Q^l,V^l(\hat{m}_V),T_1^l(\hat{m}_V,\hat{m}_1),T_2^l(\hat{m}_V,\hat{m}_2),\hat{s}_0^l,\hat{s}_1^l,\hat{s}_2^l,Y^l\right)\in\mathcal{T}_{\delta_l}^{(l)}. \tag*{(79)} ( Q l , V l ( m ^ V ) , T 1 l ( m ^ V , m ^ 1 ) , T 2 l ( m ^ V , m ^ 2 ) , s ^ 0 l , s ^ 1 l , s ^ 2 l , Y l ) ∈ T δ l ( l ) . (79)
An error is declared whenever a required index is absent or nonunique. Let P e ( l ) P_e^{(l)} P e ( l ) denote the probability that at least one of the six decisions is incorrect.
Lemma 1. For every sufficiently large l l l , there is a deterministic single-block code whose error probability vanishes at least as fast as 2 − Ω ( l ) 2^{-\Omega(\sqrt{l})} 2 − Ω ( l ) , provided
R 0 b > H ( S 0 ∣ Y , Q ) , (80) R_0^b > H(S_0 \mid Y,Q), \tag*{(80)} R 0 b > H ( S 0 ∣ Y , Q ) , (80) R V c < I ( V ; Y ∣ S 0 , Q ) or R V c = 0 , (81) R_V^c < I(V;Y \mid S_0,Q) \quad\text{or} \quad R_V^c = 0, \tag*{(81)} R V c < I ( V ; Y ∣ S 0 , Q ) or R V c = 0 , (81) R 2 b > H ( S 2 ∣ V , S 0 , Y , Q ) , (82) R_2^b > H(S_2 \mid V,S_0,Y,Q), \tag*{(82)} R 2 b > H ( S 2 ∣ V , S 0 , Y , Q ) , (82) R 2 p < I ( T 2 ; Y ∣ V , S 0 , S 2 , Q ) or R 2 p = 0 , (83) R_2^p < I(T_2;Y \mid V,S_0,S_2,Q) \quad\text{or} \quad R_2^p = 0, \tag*{(83)} R 2 p < I ( T 2 ; Y ∣ V , S 0 , S 2 , Q ) or R 2 p = 0 , (83) R 1 b > H ( S 1 ∣ V , T 2 , S 0 , S 2 , Y , Q ) , (84) R_1^b > H(S_1 \mid V,T_2,S_0,S_2,Y,Q), \tag*{(84)} R 1 b > H ( S 1 ∣ V , T 2 , S 0 , S 2 , Y , Q ) , (84) R 1 p < I ( T 1 ; Y ∣ V , T 2 , S 0 , S 1 , S 2 , Q ) . (85) R_1^p < I(T_1;Y \mid V,T_2,S_0,S_1,S_2,Q). \tag*{(85)} R 1 p < I ( T 1 ; Y ∣ V , T 2 , S 0 , S 1 , S 2 , Q ) . (85) Proof. By symmetry, we may assume WLG that ( M V , M 1 , M 2 ) = ( 1 , 1 , 1 ) (M_V,M_1,M_2)=(1,1,1) ( M V , M 1 , M 2 ) = ( 1 , 1 , 1 ) . Let E t y p \mathcal{E}_{\mathrm{typ}} E typ be the event that the transmitted tuple
( Q l , V l ( 1 ) , T 1 l ( 1 , 1 ) , T 2 l ( 1 , 1 ) , S 0 l , S 1 l , S 2 l , Y l ) (86) (Q^l,V^l(1),T_1^l(1,1),T_2^l(1,1),S_0^l,S_1^l,S_2^l,Y^l) \tag*{(86)} ( Q l , V l ( 1 ) , T 1 l ( 1 , 1 ) , T 2 l ( 1 , 1 ) , S 0 l , S 1 l , S 2 l , Y l ) (86) is not jointly δ l \delta_l δ l -typical. Let
κ ≜ ∣ Q ∣ ∣ V ∣ ∣ T 1 ∣ ∣ T 2 ∣ ∣ S 0 ∣ ∣ S 1 ∣ ∣ S 2 ∣ ∣ Y ∣ . (87) \kappa\triangleq|\mathcal{Q}||\mathcal{V}||\mathcal{T}_1||\mathcal{T}_2||\mathcal{S}_0||\mathcal{S}_1||\mathcal{S}_2||\mathcal{Y}|. \tag*{(87)} κ ≜ ∣ Q ∣∣ V ∣∣ T 1 ∣∣ T 2 ∣∣ S 0 ∣∣ S 1 ∣∣ S 2 ∣∣ Y ∣. (87) By the cardinality bounds established in Remark 3, κ \kappa κ is finite.
By the finite-alphabet large-deviation bound in Corollary 4.8 of [18 ] ,
Pr ( E t y p ) ≤ ( l + 1 ) κ 2 − l δ l 2 log e 2 κ 2 (88) \Pr(\mathcal{E}_{\mathrm{typ}}) \le(l+1)^\kappa2^{-\frac{l\delta_l^2\log e}{2\kappa^2}} \tag*{(88)} Pr ( E typ ) ≤ ( l + 1 ) κ 2 − 2 κ 2 l δ l 2 l o g e (88) = 2 − l E t y p , l , (89) =2^{-lE_{\mathrm{typ},l}}, \tag*{(89)} = 2 − l E typ , l , (89) where
E t y p , l ≜ δ l 2 log e 2 κ 2 − κ log ( l + 1 ) l , (90) E_{\mathrm{typ},l} \triangleq\frac{\delta_l^2\log e}{2\kappa^2}-\frac{\kappa\log(l+1)}{l}, \tag*{(90)} E typ , l ≜ 2 κ 2 δ l 2 log e − l κ log ( l + 1 ) , (90) and l E t y p , l → ∞ lE_{\mathrm{typ},l}\to\infty l E typ , l → ∞ by (46).
By (47)–(48), the same corollary shows that the finite-block slack in each conditional type-class and packing bound below is at most τ l \tau_l τ l .
We do not condition on correct decisions at preceding stages, since these events depend on Y l Y^l Y l and can change the channel statistics. Instead, we use the genie-aided proof technique in [5 Appendix C] and [21 Section 6.3] . At each stage, we assume there exists a genie that supplies the true values of all objects preceding that stage in (52) to the decoder. To be
specific, define
E S 0 ≜ { test 1 fails } , (91) \mathcal{E}_{S_0} \triangleq\{\text{test 1 fails}\}, \tag*{(91)} E S 0 ≜ { test 1 fails } , (91)
G V ≜ { test 2 fails with the true S 0 l supplied } , (92) \mathcal{G}_{V} \triangleq\{\text{test 2 fails with the true } S_0^l \text{ supplied}\}, \tag*{(92)} G V ≜ { test 2 fails with the true S 0 l supplied } , (92)
G S 2 ≜ { test 3 fails with the true ( S 0 l , M V ) supplied } , (93) \mathcal{G}_{S_2} \triangleq\{\text{test 3 fails with the true } (S_0^l,M_V) \text{ supplied}\}, \tag*{(93)} G S 2 ≜ { test 3 fails with the true ( S 0 l , M V ) supplied } , (93)
G 2 ≜ { test 4 fails with the true ( S 0 l , M V , S 2 l ) supplied } , (94) \mathcal{G}_{2} \triangleq\{\text{test 4 fails with the true } (S_0^l,M_V,S_2^l) \text{ supplied}\}, \tag*{(94)} G 2 ≜ { test 4 fails with the true ( S 0 l , M V , S 2 l ) supplied } , (94)
G S 1 ≜ { test 5 fails with the true ( S 0 l , M V , S 2 l , M 2 ) supplied } , (95) \mathcal{G}_{S_1} \triangleq\{\text{test 5 fails with the true } (S_0^l,M_V,S_2^l,M_2) \text{ supplied}\}, \tag*{(95)} G S 1 ≜ { test 5 fails with the true ( S 0 l , M V , S 2 l , M 2 ) supplied } , (95)
G 1 ≜ { test 6 fails with the true ( S 0 l , M V , S 2 l , M 2 , S 1 l ) supplied } . (96) \mathcal{G}_{1} \triangleq\{\text{test 6 fails with the true } (S_0^l,M_V,S_2^l,M_2,S_1^l) \text{ supplied}\}. \tag*{(96)} G 1 ≜ { test 6 fails with the true ( S 0 l , M V , S 2 l , M 2 , S 1 l ) supplied } . (96)
For example, in G V \mathcal{G}_{V} G V the decoder is given the true S 0 l S_0^l S 0 l and performs the second test without requiring the first test to succeed. All probabilities below are under the original random-coding law. We bound each genie-aided error intersected with E t y p c \mathcal{E}_{\mathrm{typ}}^c E typ c .
Error E S 0 \mathcal{E}_{S_0} E S 0 : a wrong S 0 l S_0^l S 0 l passes the first test. For each realized ( q l , y l ) (q^l,y^l) ( q l , y l ) , the number of sequences s 0 l s_0^l s 0 l that are jointly typical with ( q l , y l ) (q^l,y^l) ( q l , y l ) is at most
2 l ( H ( S 0 ∣ Y , Q ) + τ l ) . (97) 2^{l(H(S_0\mid Y,Q)+\tau_l)}. \tag*{(97)} 2 l ( H ( S 0 ∣ Y , Q ) + τ l ) . (97)
Every such competing sequence is assigned the true bin label independently with probability 2 − l R 0 b 2^{-lR_0^b} 2 − l R 0 b . If N S 0 N_{S_0} N S 0 denotes the number of wrong competitors in that bin, then Markov’s inequality gives
Pr ( E S 0 ∩ E t y p c ) ≤ Pr ( N S 0 ≥ 1 , E t y p c ) (98) \Pr(\mathcal{E}_{S_0}\cap\mathcal{E}_{\mathrm{typ}}^c)\leq\Pr(N_{S_0}\geq1,\mathcal{E}_{\mathrm{typ}}^c) \tag*{(98)} Pr ( E S 0 ∩ E typ c ) ≤ Pr ( N S 0 ≥ 1 , E typ c ) (98)
≤ E [ N S 0 1 { E t y p c } ] (99) \leq\mathbb{E}\left[N_{S_0}\mathbb{1}\{\mathcal{E}_{\mathrm{typ}}^c\}\right] \tag*{(99)} ≤ E [ N S 0 1 { E typ c } ] (99)
≤ 2 − l E S 0 , l , (100) \leq2^{-lE_{S_0,l}}, \tag*{(100)} ≤ 2 − l E S 0 , l , (100)
where
E S 0 , l ≜ R 0 b − H ( S 0 ∣ Y , Q ) − τ l . (101) E_{S_0,l}\triangleq R_0^b-H(S_0\mid Y,Q)-\tau_l. \tag*{(101)} E S 0 , l ≜ R 0 b − H ( S 0 ∣ Y , Q ) − τ l . (101)
Error G V \mathcal{G}_{V} G V : a wrong common message passes the second test. Here the genie supplies the true S 0 l S_0^l S 0 l , and the decoder applies the second test with s ^ 0 l = S 0 l \hat{s}_0^l=S_0^l s ^ 0 l = S 0 l . There are at most 2 l R V c 2^{lR_V^c} 2 l R V c wrong cloud center codewords. For every m V ′ ≠ 1 m'_V\ne1 m V ′ = 1 , V l ( m V ′ ) V^l(m'_V) V l ( m V ′ ) is independent of ( S 0 l , Y l ) (S_0^l,Y^l) ( S 0 l , Y l ) given Q l Q^l Q l . The joint-typicality packing bound therefore gives
Pr ( ( Q l , V l ( m V ′ ) , S 0 l , Y l ) ∈ T δ l ( l ) ) (102) \Pr\left((Q^l,V^l(m'_V),S_0^l,Y^l)\in\mathcal{T}_{\delta_l}^{(l)}\right) \tag*{(102)} Pr ( ( Q l , V l ( m V ′ ) , S 0 l , Y l ) ∈ T δ l ( l ) ) (102)
≤ 2 − l ( I ( V ; S 0 , Y ∣ Q ) − τ l ) (103) \le2^{-l(I(V;S_0,Y\mid Q)-\tau_l)} \tag*{(103)} ≤ 2 − l ( I ( V ; S 0 , Y ∣ Q ) − τ l ) (103)
= 2 − l ( I ( V ; Y ∣ S 0 , Q ) − τ l ) , (104) =2^{-l(I(V;Y\mid S_0,Q)-\tau_l)}, \tag*{(104)} = 2 − l ( I ( V ; Y ∣ S 0 , Q ) − τ l ) , (104)
where the equality uses V ⊥ S 0 V \perp S_0 V ⊥ S 0 given Q Q Q . Consequently,
Pr ( G V ∩ E t y p c ) ≤ 2 − l E V , l , (105) \Pr(G_V\cap\mathcal{E}_{\mathrm{typ}}^{c})\le2^{-lE_{V,l}}, \tag*{(105)} Pr ( G V ∩ E typ c ) ≤ 2 − l E V , l , (105)
where, for notational convenience, we set
E V , l ≜ { I ( V ; Y ∣ S 0 , Q ) − R V c − τ l , R V c > 0 , + ∞ , R V c = 0. (106) E_{V,l}\triangleq
\begin{cases}
I(V;Y\mid S_0,Q)-R_V^{\mathrm{c}}-\tau_l, & R_V^{\mathrm{c}}>0,\\
+\infty, & R_V^{\mathrm{c}}=0.
\end{cases} \tag*{(106)} E V , l ≜ { I ( V ; Y ∣ S 0 , Q ) − R V c − τ l , + ∞ , R V c > 0 , R V c = 0. (106)
When R V c = 0 R_V^{\mathrm{c}}=0 R V c = 0 , the cloud-center codebook is a singleton, so G V ∩ E t y p c = ∅ G_V\cap\mathcal{E}_{\mathrm{typ}}^{c}=\varnothing G V ∩ E typ c = ∅ .
Error G S 2 G_{S_2} G S 2 : a wrong S 2 l S_2^l S 2 l passes the third test. Here the genie supplies the true ( S 0 l , M V ) (S_0^l,M_V) ( S 0 l , M V ) , and the decoder applies the third test with s ^ 0 l = S 0 l \hat{s}_0^l=S_0^l s ^ 0 l = S 0 l and m ^ V = M V \hat{m}_V=M_V m ^ V = M V . For the genie-aided third test and fixed ( q l , v l , s 0 l , y l ) (q^l,v^l,s_0^l,y^l) ( q l , v l , s 0 l , y l ) , the conditional type-class bound gives at most
2 l ( H ( S 2 ∣ V , S 0 , Y , Q ) + τ l ) (107) 2^{l(H(S_2\mid V,S_0,Y,Q)+\tau_l)} \tag*{(107)} 2 l ( H ( S 2 ∣ V , S 0 , Y , Q ) + τ l ) (107)
jointly typical s 2 l s_2^l s 2 l sequences. Each has the true bin label with probability 2 − l R 2 b 2^{-lR_2^{\mathrm{b}}} 2 − l R 2 b . Thus
Pr ( G S 2 ∩ E t y p c ) ≤ 2 − l E S 2 , l , (108) \Pr(G_{S_2}\cap\mathcal{E}_{\mathrm{typ}}^{c})\le2^{-lE_{S_2,l}}, \tag*{(108)} Pr ( G S 2 ∩ E typ c ) ≤ 2 − l E S 2 , l , (108)
where
E S 2 , l ≜ R 2 b − H ( S 2 ∣ V , S 0 , Y , Q ) − τ l . (109) E_{S_2,l}\triangleq R_2^{\mathrm{b}}-H(S_2\mid V,S_0,Y,Q)-\tau_l. \tag*{(109)} E S 2 , l ≜ R 2 b − H ( S 2 ∣ V , S 0 , Y , Q ) − τ l . (109)
Error G 2 G_2 G 2 : a wrong Encoder 2 satellite message passes the fourth test. Here the genie supplies the true ( S 0 l , M V , S 2 l ) (S_0^l,M_V,S_2^l) ( S 0 l , M V , S 2 l ) , and the decoder applies the fourth test with s ^ 0 l = S 0 l \hat{s}_0^l=S_0^l s ^ 0 l = S 0 l , m ^ V = M V \hat{m}_V=M_V m ^ V = M V , and s ^ 2 l = S 2 l \hat{s}_2^l=S_2^l s ^ 2 l = S 2 l . For each m 2 ′ ≠ 1 m_2'\ne1 m 2 ′ = 1 , the codeword T 2 l ( 1 , m 2 ′ ) T_2^l(1,m_2') T 2 l ( 1 , m 2 ′ ) is independent of Y l Y^l Y l given ( Q l , V l ( 1 ) , S 0 l , S 2 l ) (Q^l,V^l(1),S_0^l,S_2^l) ( Q l , V l ( 1 ) , S 0 l , S 2 l ) . Hence
Pr ( ( Q l , V l ( 1 ) , T 2 l ( 1 , m 2 ′ ) , S 0 l , S 2 l , Y l ) ∈ T δ l ( l ) ) ≤ 2 − l ( I ( T 2 ; Y ∣ V , S 0 , S 2 , Q ) − τ l ) . (110) \Pr\left((Q^l,V^l(1),T_2^l(1,m_2'),S_0^l,S_2^l,Y^l)\in\mathcal{T}_{\delta_l}^{(l)}\right)
\le2^{-l(I(T_2;Y\mid V,S_0,S_2,Q)-\tau_l)}. \tag*{(110)} Pr ( ( Q l , V l ( 1 ) , T 2 l ( 1 , m 2 ′ ) , S 0 l , S 2 l , Y l ) ∈ T δ l ( l ) ) ≤ 2 − l ( I ( T 2 ; Y ∣ V , S 0 , S 2 , Q ) − τ l ) . (110)
There are at most 2 l R 2 p 2^{lR_2^{\mathrm{p}}} 2 l R 2 p competitors, and therefore
Pr ( G 2 ∩ E t y p c ) ≤ 2 − l E 2 , l , (111) \Pr(\mathcal{G}_2 \cap\mathcal{E}_{\mathrm{typ}}^{c}) \le2^{-l E_{2,l}}, \tag*{(111)} Pr ( G 2 ∩ E typ c ) ≤ 2 − l E 2 , l , (111)
where
E 2 , l ≜ { I ( T 2 ; Y ∣ V , S 0 , S 2 , Q ) − R 2 p − τ l , R 2 p > 0 , + ∞ , R 2 p = 0. (112) E_{2,l} \triangleq
\begin{cases}
I(T_2;Y \mid V,S_0,S_2,Q)-R_2^{\mathrm{p}}-\tau_l, & R_2^{\mathrm{p}}>0,\\
+\infty, & R_2^{\mathrm{p}}=0.
\end{cases} \tag*{(112)} E 2 , l ≜ { I ( T 2 ; Y ∣ V , S 0 , S 2 , Q ) − R 2 p − τ l , + ∞ , R 2 p > 0 , R 2 p = 0. (112)
When R 2 p = 0 R_2^{\mathrm{p}}=0 R 2 p = 0 , the Encoder 2 satellite codebook is a singleton, so G 2 ∩ E t y p c = ∅ \mathcal{G}_2 \cap\mathcal{E}_{\mathrm{typ}}^{c}=\varnothing G 2 ∩ E typ c = ∅ .
Error G S 1 \mathcal{G}_{S_1} G S 1 : a wrong S 1 l S_1^l S 1 l passes the fifth test. Here the genie supplies the true ( S 0 l , M V , S 2 l , M 2 ) (S_0^l,M_V,S_2^l,M_2) ( S 0 l , M V , S 2 l , M 2 ) , and the decoder applies the fifth test with s ^ 0 l = S 0 l \hat{s}_0^l=S_0^l s ^ 0 l = S 0 l , m ^ V = M V \hat{m}_V=M_V m ^ V = M V , s ^ 2 l = S 2 l \hat{s}_2^l=S_2^l s ^ 2 l = S 2 l , and m ^ 2 = M 2 \hat{m}_2=M_2 m ^ 2 = M 2 . For the genie-aided fifth test and every realized ( q l , v l , t 2 l , s 0 l , s 2 l , y l ) (q^l,v^l,t_2^l,s_0^l,s_2^l,y^l) ( q l , v l , t 2 l , s 0 l , s 2 l , y l ) , at most
2 l ( H ( S 1 ∣ V , T 2 , S 0 , S 2 , Y , Q ) + τ l ) (113) 2^{l(H(S_1\mid V,T_2,S_0,S_2,Y,Q)+\tau_l)} \tag*{(113)} 2 l ( H ( S 1 ∣ V , T 2 , S 0 , S 2 , Y , Q ) + τ l ) (113)
state sequences pass the typicality test. Random binning places each wrong sequence in the true bin with probability 2 − l R 1 b 2^{-lR_1^{\mathrm{b}}} 2 − l R 1 b , so
Pr ( G S 1 ∩ E t y p c ) ≤ 2 − l E S 1 , l , (114) \Pr(\mathcal{G}_{S_1}\cap\mathcal{E}_{\mathrm{typ}}^{c})\le2^{-lE_{S_1,l}}, \tag*{(114)} Pr ( G S 1 ∩ E typ c ) ≤ 2 − l E S 1 , l , (114)
where
E S 1 , l ≜ R 1 b − H ( S 1 ∣ V , T 2 , S 0 , S 2 , Y , Q ) − τ l . (115) E_{S_1,l}\triangleq R_1^{\mathrm{b}}-H(S_1\mid V,T_2,S_0,S_2,Y,Q)-\tau_l. \tag*{(115)} E S 1 , l ≜ R 1 b − H ( S 1 ∣ V , T 2 , S 0 , S 2 , Y , Q ) − τ l . (115)
Error G 1 \mathcal{G}_1 G 1 : a wrong Encoder 1 satellite message passes the last test. Here the genie supplies the true ( S 0 l , M V , S 2 l , M 2 , S 1 l ) (S_0^l,M_V,S_2^l,M_2,S_1^l) ( S 0 l , M V , S 2 l , M 2 , S 1 l ) , and the decoder applies the last test with s ^ 0 l = S 0 l \hat{s}_0^l=S_0^l s ^ 0 l = S 0 l , m ^ V = M V \hat{m}_V=M_V m ^ V = M V , s ^ 2 l = S 2 l \hat{s}_2^l=S_2^l s ^ 2 l = S 2 l , m ^ 2 = M 2 \hat{m}_2=M_2 m ^ 2 = M 2 , and s ^ 1 l = S 1 l \hat{s}_1^l=S_1^l s ^ 1 l = S 1 l . For every m 1 ′ ≠ 1 m'_1\ne1 m 1 ′ = 1 , T 1 l ( 1 , m 1 ′ ) T_1^l(1,m'_1) T 1 l ( 1 , m 1 ′ ) is independent of Y l Y^l Y l given ( Q l , V l ( 1 ) , T 2 l ( 1 , 1 ) , S 0 l , S 1 l , S 2 l ) (Q^l,V^l(1),T_2^l(1,1),S_0^l,S_1^l,S_2^l) ( Q l , V l ( 1 ) , T 2 l ( 1 , 1 ) , S 0 l , S 1 l , S 2 l ) . Thus
Pr ( ( Q l , V l ( 1 ) , T 1 l ( 1 , m 1 ′ ) , T 2 l ( 1 , 1 ) , S 0 l , S 1 l , S 2 l , Y l ) ∈ T δ ( l ) ) ≤ 2 − l ( I ( T 1 ; Y ∣ V , T 2 , S 0 , S 1 , S 2 , Q ) − τ l ) . (116) \Pr\left((Q^l,V^l(1),T_1^l(1,m'_1),T_2^l(1,1),S_0^l,S_1^l,S_2^l,Y^l)\in\mathcal{T}_{\delta}^{(l)}\right)
\le2^{-l(I(T_1;Y\mid V,T_2,S_0,S_1,S_2,Q)-\tau_l)}. \tag*{(116)} Pr ( ( Q l , V l ( 1 ) , T 1 l ( 1 , m 1 ′ ) , T 2 l ( 1 , 1 ) , S 0 l , S 1 l , S 2 l , Y l ) ∈ T δ ( l ) ) ≤ 2 − l ( I ( T 1 ; Y ∣ V , T 2 , S 0 , S 1 , S 2 , Q ) − τ l ) . (116)
After a union bound over at most 2 l R 1 p 2^{lR_1^{\mathrm{p}}} 2 l R 1 p competitors,
Pr ( G 1 ∩ E t y p c ) ≤ 2 − l E 1 , l , (117) \Pr(\mathcal{G}_1\cap\mathcal{E}_{\mathrm{typ}}^{c})\le2^{-lE_{1,l}}, \tag*{(117)} Pr ( G 1 ∩ E typ c ) ≤ 2 − l E 1 , l , (117)
where
E 1 , l ≜ I ( T 1 ; Y ∣ V , T 2 , S 0 , S 1 , S 2 , Q ) − R 1 p − τ l . (118) E_{1,l} \triangleq I(T_1;Y \mid V,T_2,S_0,S_1,S_2,Q)-R_1^p-\tau_l. \tag*{(118)} E 1 , l ≜ I ( T 1 ; Y ∣ V , T 2 , S 0 , S 1 , S 2 , Q ) − R 1 p − τ l . (118)
Let
E l ≜ min { E S 0 , l , E V , l , E S 2 , l , E 2 , l , E S 1 , l , E 1 , l } . (119) E_l \triangleq\min\{E_{S_0,l},E_{V,l},E_{S_2,l},E_{2,l},E_{S_1,l},E_{1,l}\}. \tag*{(119)} E l ≜ min { E S 0 , l , E V , l , E S 2 , l , E 2 , l , E S 1 , l , E 1 , l } . (119)
If the actual decoder makes an error on E t y p c \mathcal{E}_{\mathrm{typ}}^{\mathrm{c}} E typ c , consider its first failing test. All preceding decisions are then correct. Therefore, at this test, the actual decoder uses exactly the same preceding objects as those supplied by the genie in the corresponding genie-aided test. Consequently, the occurrence of this first failure implies the occurrence of the corresponding genie-aided error event. Hence,
{ actual decoder errors } ∩ E t y p c ⊆ ( E S 0 ∪ G V ∪ G S 2 ∪ G 2 ∪ G S 1 ∪ G 1 ) ∩ E t y p c . (120) \{\text{actual decoder errors}\}\cap\mathcal{E}_{\mathrm{typ}}^{\mathrm{c}}
\subseteq
(\mathcal{E}_{S_0}\cup\mathcal{G}_V\cup\mathcal{G}_{S_2}\cup\mathcal{G}_2\cup\mathcal{G}_{S_1}\cup\mathcal{G}_1)\cap\mathcal{E}_{\mathrm{typ}}^{\mathrm{c}}. \tag*{(120)} { actual decoder errors } ∩ E typ c ⊆ ( E S 0 ∪ G V ∪ G S 2 ∪ G 2 ∪ G S 1 ∪ G 1 ) ∩ E typ c . (120)
Therefore,
P e ( l ) ≤ Pr ( E t y p ) + Pr ( E S 0 ∩ E t y p c ) + Pr ( G V ∩ E t y p c ) + Pr ( G S 2 ∩ E t y p c ) + Pr ( G 2 ∩ E t y p c ) + Pr ( G S 1 ∩ E t y p c ) + Pr ( G 1 ∩ E t y p c ) (121) \begin{aligned}
P_e^{(l)} &\leq\Pr(\mathcal{E}_{\mathrm{typ}})+\Pr(\mathcal{E}_{S_0}\cap\mathcal{E}_{\mathrm{typ}}^{\mathrm{c}})+\Pr(\mathcal{G}_V\cap\mathcal{E}_{\mathrm{typ}}^{\mathrm{c}})+\Pr(\mathcal{G}_{S_2}\cap\mathcal{E}_{\mathrm{typ}}^{\mathrm{c}})\\
&\quad+\Pr(\mathcal{G}_2\cap\mathcal{E}_{\mathrm{typ}}^{\mathrm{c}})+\Pr(\mathcal{G}_{S_1}\cap\mathcal{E}_{\mathrm{typ}}^{\mathrm{c}})+\Pr(\mathcal{G}_1\cap\mathcal{E}_{\mathrm{typ}}^{\mathrm{c}}) \tag*{(121)}
\end{aligned} P e ( l ) ≤ Pr ( E typ ) + Pr ( E S 0 ∩ E typ c ) + Pr ( G V ∩ E typ c ) + Pr ( G S 2 ∩ E typ c ) + Pr ( G 2 ∩ E typ c ) + Pr ( G S 1 ∩ E typ c ) + Pr ( G 1 ∩ E typ c ) (121)
≤ 2 − l E t y p , l + 6 ⋅ 2 − l E l . (122) \leq2^{-lE_{\mathrm{typ},l}}+6\cdot2^{-lE_l}. \tag*{(122)} ≤ 2 − l E typ , l + 6 ⋅ 2 − l E l . (122)
Since τ l → 0 \tau_l\to0 τ l → 0 , each strict rate condition in (80) –(85) makes the corresponding error exponent positive for all sufficiently large l l l . Together with l E t y p , l → ∞ lE_{\mathrm{typ},l}\to\infty l E typ , l → ∞ , this implies P e ( l ) → 0 P_e^{(l)}\to0 P e ( l ) → 0 . Averaging over the random construction gives the existence of a deterministic one-block code with the same vanishing-error property.
The one-block lemma specifies only the binning and bit-pipe rates supported by the successive decoder. The message-rate allocation to fresh messages and previous-block state labels is postponed to the interblock construction.
Remark 4. We can also favor Encoder 2 by reversing the decoding order of (76) to have it be
S 0 l ⟶ M V ⟶ S 1 l ⟶ M 1 ⟶ S 2 l ⟶ M 2 . (123) S_0^l\longrightarrow M_V\longrightarrow S_1^l\longrightarrow M_1\longrightarrow S_2^l\longrightarrow M_2. \tag*{(123)} S 0 l ⟶ M V ⟶ S 1 l ⟶ M 1 ⟶ S 2 l ⟶ M 2 . (123)
This will demonstrate achievability whenever
R 0 b > H ( S 0 ∣ Y , Q ) , (124) R^{b}_{0} > H(S_{0} \mid Y,Q), \tag*{(124)} R 0 b > H ( S 0 ∣ Y , Q ) , (124)
R V c < I ( V ; Y ∣ S 0 , Q ) or R V c = 0 , (125) R^{c}_{V} < I(V;Y \mid S_{0},Q)\quad\text{or}\quad R^{c}_{V}=0, \tag*{(125)} R V c < I ( V ; Y ∣ S 0 , Q ) or R V c = 0 , (125)
R 1 b > H ( S 1 ∣ V , S 0 , Y , Q ) , (126) R^{b}_{1} > H(S_{1} \mid V,S_{0},Y,Q), \tag*{(126)} R 1 b > H ( S 1 ∣ V , S 0 , Y , Q ) , (126)
R 1 p < I ( T 1 ; Y ∣ V , S 0 , S 1 , Q ) or R 1 p = 0 , (127) R^{p}_{1} < I(T_{1};Y \mid V,S_{0},S_{1},Q)\quad\text{or}\quad R^{p}_{1}=0, \tag*{(127)} R 1 p < I ( T 1 ; Y ∣ V , S 0 , S 1 , Q ) or R 1 p = 0 , (127)
R 2 b > H ( S 2 ∣ V , T 1 , S 0 , S 1 , Y , Q ) , (128) R^{b}_{2} > H(S_{2} \mid V,T_{1},S_{0},S_{1},Y,Q), \tag*{(128)} R 2 b > H ( S 2 ∣ V , T 1 , S 0 , S 1 , Y , Q ) , (128)
R 2 p < I ( T 2 ; Y ∣ V , T 1 , S 0 , S 1 , S 2 , Q ) . (129) R^{p}_{2} < I(T_{2};Y \mid V,T_{1},S_{0},S_{1},S_{2},Q). \tag*{(129)} R 2 p < I ( T 2 ; Y ∣ V , T 1 , S 0 , S 1 , S 2 , Q ) . (129)
Note that Inequalities (84) are obtained from those of (56) by swapping the index 1 and the index 2 in all quantities of interest (namely, the rate indices, the state indices, and the strategy indices).
Rate selection and interblock allocation
We next describe the rate allocation that allows us to approach the vertices of the polytope; see Section 5.2. To guarantee that the required inequalities hold, we choose the rates R 0 b R^{b}_{0} R 0 b , R 1 b R^{b}_{1} R 1 b , R 1 p R^{p}_{1} R 1 p , R 2 b R^{b}_{2} R 2 b , R 2 p R^{p}_{2} R 2 p , in Lemma 1, for a sufficiently small ϵ > 0 \epsilon>0 ϵ > 0 , as
R 0 b = H ( S 0 ∣ Y , Q ) + ϵ , (130) R^{b}_{0}=H(S_{0}\mid Y,Q)+\epsilon, \tag*{(130)} R 0 b = H ( S 0 ∣ Y , Q ) + ϵ , (130)
R 2 b = H ( S 2 ∣ V , S 0 , Y , Q ) + ϵ , (131) R^{b}_{2}=H(S_{2}\mid V,S_{0},Y,Q)+\epsilon, \tag*{(131)} R 2 b = H ( S 2 ∣ V , S 0 , Y , Q ) + ϵ , (131)
R 2 p = max { I ( T 2 ; Y ∣ V , S 0 , S 2 , Q ) − ϵ , 0 } , (132) R^{p}_{2}=\max\left\{I(T_{2};Y\mid V,S_{0},S_{2},Q)-\epsilon,0\right\}, \tag*{(132)} R 2 p = max { I ( T 2 ; Y ∣ V , S 0 , S 2 , Q ) − ϵ , 0 } , (132)
R 1 b = H ( S 1 ∣ V , T 2 , S 0 , S 2 , Y , Q ) + ϵ , (133) R^{b}_{1}=H(S_{1}\mid V,T_{2},S_{0},S_{2},Y,Q)+\epsilon, \tag*{(133)} R 1 b = H ( S 1 ∣ V , T 2 , S 0 , S 2 , Y , Q ) + ϵ , (133)
R 1 p = I ( T 1 ; Y ∣ V , T 2 , S 0 , S 1 , S 2 , Q ) − ϵ . (134) R^{p}_{1}=I(T_{1};Y\mid V,T_{2},S_{0},S_{1},S_{2},Q)-\epsilon. \tag*{(134)} R 1 p = I ( T 1 ; Y ∣ V , T 2 , S 0 , S 1 , S 2 , Q ) − ϵ . (134)
As to rate R V c R^{c}_{V} R V c of the common pipe, we note that (81) requires either R V c < I ( V ; Y ∣ S 0 , Q ) R^{c}_{V}<I(V;Y\mid S_{0},Q) R V c < I ( V ; Y ∣ S 0 , Q ) or R V c = 0 R^{c}_{V}=0 R V c = 0 , so we do not want it to exceed max { I ( V ; Y ∣ S 0 , Q ) − ϵ , 0 } \max\{I(V;Y\mid S_{0},Q)-\epsilon,0\} max { I ( V ; Y ∣ S 0 , Q ) − ϵ , 0 } . And since it is only used to convey all (or some) of the bits that index the S 0 S_{0} S 0 -bin, we cap it at R 0 b R^{b}_{0} R 0 b . We therefore choose
R V c = min { R 0 b , max { I ( V ; Y ∣ S 0 , Q ) − ϵ , 0 } } . (135) R^{c}_{V}=\min\left\{R^{b}_{0},\max\left\{I(V;Y\mid S_{0},Q)-\epsilon,0\right\}\right\}. \tag*{(135)} R V c = min { R 0 b , max { I ( V ; Y ∣ S 0 , Q ) − ϵ , 0 } } . (135)
(Recall that if indexing the S 0 S_{0} S 0 -bin requires more bits than the common message can carry, the remaining bits are sent over the other bit pipes.)
We next show how the bit pipes are used to approach the different vertices of the polytope.
Blue vertex
We use the Encoder 1-favoring decoding order of § 5.4 . The common message carries l R V c lR_{\mathrm{V}}^{\mathrm{c}} l R V c of the l R 0 b lR_{0}^{\mathrm{b}} l R 0 b bits that index the S 0 S_{0} S 0 -bin. Encoder 1’s bit pipe carries Encoder 1’s fresh message and the preceding l R 1 b lR_{1}^{\mathrm{b}} l R 1 b bits that index the S 1 S_{1} S 1 -bin. Encoder 2’s bit pipe carries its fresh message, the preceding l R 2 b lR_{2}^{\mathrm{b}} l R 2 b bits that index the S 2 S_{2} S 2 -bin, and the remaining l ( R 0 b − R V c ) l(R_{0}^{\mathrm{b}}-R_{\mathrm{V}}^{\mathrm{c}}) l ( R 0 b − R V c ) bits that couldn’t be carried by the common bit pipe and that are still needed to complete the description of the S 0 S_{0} S 0 -bin. By (85), this allocation allows for the transmission rate
R 1 = R 1 p − R 1 b = I ( T 1 ; Y ∣ V , T 2 , S 0 , S 1 , S 2 , Q ) − H ( S 1 ∣ V , T 2 , S 0 , S 2 , Y , Q ) − 2 ϵ (136) R_{1}=R_{1}^{\mathrm{p}}-R_{1}^{\mathrm{b}}=I(T_{1};Y\mid V,T_{2},S_{0},S_{1},S_{2},Q)-H(S_{1}\mid V,T_{2},S_{0},S_{2},Y,Q)-2\epsilon \tag*{(136)} R 1 = R 1 p − R 1 b = I ( T 1 ; Y ∣ V , T 2 , S 0 , S 1 , S 2 , Q ) − H ( S 1 ∣ V , T 2 , S 0 , S 2 , Y , Q ) − 2 ϵ (136)
= A 1 − 2 ϵ . (137) =A_{1}-2\epsilon. \tag*{(137)} = A 1 − 2 ϵ . (137)
As to R 2 R_{2} R 2 , the above allocation results in
R 2 = R 2 p − ( R 2 b + ( R 0 b − R V c ) ) . (138) R_{2}=R_{2}^{\mathrm{p}}-\left(R_{2}^{\mathrm{b}}+\left(R_{0}^{\mathrm{b}}-R_{\mathrm{V}}^{\mathrm{c}}\right)\right). \tag*{(138)} R 2 = R 2 p − ( R 2 b + ( R 0 b − R V c ) ) . (138)
Using the fact that—by the definitions in (41), the chain rule, and the independence of S 0 S_{0} S 0 and Q Q Q —
C p − A 1 = I ( T 2 , S 2 ; Y ∣ V , S 0 , Q ) − H ( S 2 ) (139) C_{\mathrm{p}}-A_{1}=I(T_{2},S_{2};Y\mid V,S_{0},Q)-H(S_{2}) \tag*{(139)} C p − A 1 = I ( T 2 , S 2 ; Y ∣ V , S 0 , Q ) − H ( S 2 ) (139)
C t − A 1 = I ( V , T 2 , S 2 ; Y ∣ S 0 , Q ) − H ( S 0 ∣ Y , Q ) − H ( S 2 ) (140) C_{\mathrm{t}}-A_{1}=I(V,T_{2},S_{2};Y\mid S_{0},Q)-H(S_{0}\mid Y,Q)-H(S_{2}) \tag*{(140)} C t − A 1 = I ( V , T 2 , S 2 ; Y ∣ S 0 , Q ) − H ( S 0 ∣ Y , Q ) − H ( S 2 ) (140)
we obtain from (85)–(135) that
lim ϵ ↓ 0 ( R 2 p − ( R 2 b + ( R 0 b − R V c ) ) ) = min { C p − A 1 , C t − A 1 } = C − A 1 . (141) \lim_{\epsilon\downarrow0}\left(R_{2}^{\mathrm{p}}-\left(R_{2}^{\mathrm{b}}+\left(R_{0}^{\mathrm{b}}-R_{\mathrm{V}}^{\mathrm{c}}\right)\right)\right)=\min\{C_{\mathrm{p}}-A_{1},C_{\mathrm{t}}-A_{1}\}=C-A_{1}. \tag*{(141)} ϵ ↓ 0 lim ( R 2 p − ( R 2 b + ( R 0 b − R V c ) ) ) = min { C p − A 1 , C t − A 1 } = C − A 1 . (141)
As C > A 1 C>A_{1} C > A 1 (blue vertex), the right-hand side is strictly positive. Hence, for all sufficiently small ϵ > 0 \epsilon>0 ϵ > 0 , both fresh-message rates are strictly positive. Therefore, our scheme produces a rate pair approaching
( A 1 , C − A 1 ) . (142) (A_{1},C-A_{1}). \tag*{(142)} ( A 1 , C − A 1 ) . (142)
Red vertex
The red vertices occur when C ≤ A 1 C\le A_{1} C ≤ A 1 , which is thus what we now assume. They have the form ( C , 0 ) (C,0) ( C , 0 ) . The single-block scheme we propose to approach this vertex is a time-sharing scheme between the Encoder 1-favoring scheme of Lemma 1 and the Encoder 2-favoring scheme of Remark 4.
The formal calculation we performed to approach the blue vertex using the Encoder 1-favoring decoding order yields (as in (142) ) the “bookkeeping” pair
r ( 1 ) = ( A 1 , C − A 1 ) . (143) \mathbf{r}^{(1)} = (A_1, C-A_1). \tag*{(143)} r ( 1 ) = ( A 1 , C − A 1 ) . (143)
We can also perform a similar formal calculation for the Encoder 2-favoring decoding order: Recall that Inequalities (84) are obtained from those of (56) by swapping the index 1 and the index 2 in all quantities of interest (namely, the rate indices, the state indices, and the strategy indices). This also results in the swapping of A 1 A_1 A 1 with A 2 A_2 A 2 . Thus, the formal calculation yields the bookkeeping pair
r ( 2 ) = ( C − A 2 , A 2 ) . (144) \mathbf{r}^{(2)} = (C-A_2,A_2). \tag*{(144)} r ( 2 ) = ( C − A 2 , A 2 ) . (144)
We used “formal,” and “bookkeeping pair” (and not “rate pair”) because some of the components of r ( 1 ) \mathbf{r}^{(1)} r ( 1 ) and r ( 2 ) \mathbf{r}^{(2)} r ( 2 ) may be negative. Negative components merely mean that the bitpipes cannot support the transmission of the required part of the bin-index. It thus only represents a possible deficit after subtracting the bin-index bits; it does not represent a negative physical transmission rate. This is not an issue as long as the components that result from time-sharing are nonnegative, i.e., as long as the bitpipes we obtain after time sharing can support the transmission of the bin indices.
Since R < ( P ) \mathcal{R}_{<}(P) R < ( P ) is nonempty, we have A 2 > 0 A_2>0 A 2 > 0 . Together with C ≤ A 1 C\le A_1 C ≤ A 1 , this implies that A 1 + A 2 − C > 0 A_1+A_2-C>0 A 1 + A 2 − C > 0 .
For sufficiently small ϵ > 0 \epsilon>0 ϵ > 0 , choose the duty cycle
α ϵ ≜ A 2 A 1 + A 2 − C − ϵ . (145) \alpha_\epsilon\triangleq\frac{A_2}{A_1+A_2-C}-\sqrt{\epsilon}. \tag*{(145)} α ϵ ≜ A 1 + A 2 − C A 2 − ϵ . (145)
With this choice, 0 < α ϵ < 1 0<\alpha_\epsilon<1 0 < α ϵ < 1 and
α ϵ r ( 1 ) + ( 1 − α ϵ ) r ( 2 ) = ( C − ( A 1 + A 2 − C ) ϵ , ( A 1 + A 2 − C ) ϵ ) , (146) \alpha_\epsilon\mathbf{r}^{(1)}+(1-\alpha_\epsilon)\mathbf{r}^{(2)}
=
\left(C-(A_1+A_2-C)\sqrt{\epsilon},(A_1+A_2-C)\sqrt{\epsilon}\right), \tag*{(146)} α ϵ r ( 1 ) + ( 1 − α ϵ ) r ( 2 ) = ( C − ( A 1 + A 2 − C ) ϵ , ( A 1 + A 2 − C ) ϵ ) , (146)
which converges to ( C , 0 ) (C,0) ( C , 0 ) as ϵ ↓ 0 \epsilon\downarrow0 ϵ ↓ 0 .
Time-sharing can be implemented by dividing the length-l l l block into two subblocks of lengths
l 1 = ⌊ α ϵ l ⌋ , l 2 = l − l 1 . (147) l_1=\lfloor\alpha_\epsilon l\rfloor,\qquad l_2=l-l_1. \tag*{(147)} l 1 = ⌊ α ϵ l ⌋ , l 2 = l − l 1 . (147)
In the first subblock we employ the Encoder 1-favoring decoding order, and in the second the Encoder 2-favoring order. The rates in the second subblock are the symmetric counterparts of (85)–(86), i.e., the rates obtained by swapping the index 1 and the index 2 in all the variables. Let ( R 0 b , ( q ) , R 1 b , ( q ) , R 2 b , ( q ) , R V c , ( q ) , R 1 p , ( q ) , R 2 p , ( q ) ) (R_0^{\mathrm{b},(q)}, R_1^{\mathrm{b},(q)}, R_2^{\mathrm{b},(q)}, R_V^{\mathrm{c},(q)}, R_1^{\mathrm{p},(q)}, R_2^{\mathrm{p},(q)}) ( R 0 b , ( q ) , R 1 b , ( q ) , R 2 b , ( q ) , R V c , ( q ) , R 1 p , ( q ) , R 2 p , ( q ) ) denote the rates in the subblock q q q , where q ∈ { 1 , 2 } q \in\{1,2\} q ∈ { 1 , 2 } .
In each subblock, the common pipe carries as many bits of the preceding block’s S 0 S_0 S 0 -bin index as its rate permits. Some of the remaining S 0 S_0 S 0 -bin-index bits (if any) are assigned to Encoder 2’s bit pipe in the Encoder 1-favoring subblock (the first subblock), and the rest are assigned to Encoder 1’s bit pipe in the Encoder 2-favoring subblock (the second subblock).
In each subblock, each encoder uses its bit-pipe rate to carry its fresh message and all bin-index bits assigned to it: its own state bin-index bits and possibly some of the remaining S 0 S_0 S 0 -bin-index bits. Consequently, the fresh-message rates equal the total bit-pipe rates minus the total assigned bin-index rates:
R 1 ( ℓ ) = 1 ℓ { ℓ 1 ( R 1 p , ( 1 ) − R 1 b , ( 1 ) ) + ℓ 2 [ R 1 p , ( 2 ) − R 1 b , ( 2 ) − ( R 0 b , ( 2 ) − R V c , ( 2 ) ) ] } . (148) R_1^{(\ell)} = \frac{1}{\ell}\left\{\ell_1\left(R_1^{\mathrm{p},(1)}-R_1^{\mathrm{b},(1)}\right)+\ell_2\left[R_1^{\mathrm{p},(2)}-R_1^{\mathrm{b},(2)}-\left(R_0^{\mathrm{b},(2)}-R_V^{\mathrm{c},(2)}\right)\right]\right\}. \tag*{(148)} R 1 ( ℓ ) = ℓ 1 { ℓ 1 ( R 1 p , ( 1 ) − R 1 b , ( 1 ) ) + ℓ 2 [ R 1 p , ( 2 ) − R 1 b , ( 2 ) − ( R 0 b , ( 2 ) − R V c , ( 2 ) ) ] } . (148)
R 2 ( ℓ ) = 1 ℓ { ℓ 1 [ R 2 p , ( 1 ) − R 2 b , ( 1 ) − ( R 0 b , ( 1 ) − R V c , ( 1 ) ) ] + ℓ 2 ( R 2 p , ( 2 ) − R 2 b , ( 2 ) ) } . (149) R_2^{(\ell)} = \frac{1}{\ell}\left\{\ell_1\left[R_2^{\mathrm{p},(1)}-R_2^{\mathrm{b},(1)}-\left(R_0^{\mathrm{b},(1)}-R_V^{\mathrm{c},(1)}\right)\right]+\ell_2\left(R_2^{\mathrm{p},(2)}-R_2^{\mathrm{b},(2)}\right)\right\}. \tag*{(149)} R 2 ( ℓ ) = ℓ 1 { ℓ 1 [ R 2 p , ( 1 ) − R 2 b , ( 1 ) − ( R 0 b , ( 1 ) − R V c , ( 1 ) ) ] + ℓ 2 ( R 2 p , ( 2 ) − R 2 b , ( 2 ) ) } . (149)
Having described the time-sharing scheme, we can return to the limiting rate: The positive second coordinate in (146) is of order ϵ \sqrt{\epsilon} ϵ , whereas the rate loss caused by the coding slack is of order ϵ \epsilon ϵ . Consequently, for all sufficiently small fixed ϵ > 0 \epsilon>0 ϵ > 0 and all sufficiently large ℓ \ell ℓ , both fresh-message rates (especially R 2 ( ℓ ) R_2^{(\ell)} R 2 ( ℓ ) ) in (96) are strictly positive. Moreover,
( R 1 ( ℓ ) , R 2 ( ℓ ) ) ⟶ ( C , 0 ) , (150) \left(R_1^{(\ell)},R_2^{(\ell)}\right)\longrightarrow(C,0), \tag*{(150)} ( R 1 ( ℓ ) , R 2 ( ℓ ) ) ⟶ ( C , 0 ) , (150)
where the limit is taken first as ℓ → ∞ \ell\to\infty ℓ → ∞ for fixed ϵ \epsilon ϵ and then as ϵ ↓ 0 \epsilon\downarrow0 ϵ ↓ 0 .
The Terminating Block and Backward Decoding
To conclude the achievability proof, we now describe the last block and the backward decoding.
In the last block no fresh data are sent. Its purpose is to describe the bins containing the state sequences that prevailed during the previous (next-to-last) block. Recall that in the next-to-last block (as in all previous blocks) bins were generated for the different state sequences. Those are used in the last block. More specifically, Encoder 1 conveys to the decoder the index of the S 1 S_1 S 1 -bin that contains the S 1 S_1 S 1 -state sequence that prevailed in the next-to-last block. Likewise, Encoder 2 conveys the index of the S 2 S_2 S 2 -bin, and the two encoders can cooperate in sending the index of the S 0 S_0 S 0 -bin. The length ℓ ′ \ell' ℓ ′ of the last block is chosen so as to allow this transmission (with causal state information). Assumption 1 guarantees that l ′ l' l ′ is within a constant factor of l l l , i.e., l ′ ( l ) = O ( l ) l'(l) = O(l) l ′ ( l ) = O ( l ) .
Not sending data in the last block incurs a rate-loss that can be made arbitrarily small by having the number of blocks large. Also, the states prevailing in the last block are not conveyed to the receiver, and they thus contribute to the symbol error-rate in the state’s reconstruction. Again, this contribution to the symbol error-rate is arbitrarily small if the number of blocks is large.
Once the last block has terminated, the decoder can recover the indices of the bins containing the state sequences that prevailed during the next-to-last block and can thus proceed to decoding the next-to-last transmission. This backward decoding continues until the first block is decoded.
Note that the coding slack ϵ \epsilon ϵ used above is distinct from the ϵ 0 \epsilon_0 ϵ 0 in the definition of achievability. Given any neighborhood N \mathcal{N} N of either endpoint, choose ϵ \epsilon ϵ sufficiently small and let the blocklength and the number of blocks be large enough so that the construction above yields a strictly positive rate pair ( R 1 , R 2 ) ∈ N (R_1,R_2) \in\mathcal{N} ( R 1 , R 2 ) ∈ N with vanishing message and state-reconstruction errors. Since N \mathcal{N} N is open, there exists ϵ 0 > 0 \epsilon_0 > 0 ϵ 0 > 0 such that
( R 1 − ϵ 0 , R 2 − ϵ 0 ) ∈ N ∩ R ≥ 0 2 . (151) (R_1-\epsilon_0,R_2-\epsilon_0) \in\mathcal{N} \cap\mathbb{R}_{\geq0}^{2}. \tag*{(151)} ( R 1 − ϵ 0 , R 2 − ϵ 0 ) ∈ N ∩ R ≥ 0 2 . (151)
So ( R 1 − ϵ 0 , R 2 − ϵ 0 ) (R_1-\epsilon_0,R_2-\epsilon_0) ( R 1 − ϵ 0 , R 2 − ϵ 0 ) is achievable by definition. Thus, every neighborhood of either endpoint contains an achievable rate pair, which demonstrates that the vertex belongs to the closure of the achievable rate pairs, namely, the capacity region.
Acknowledgment
This work was supported by the Swiss National Science Foundation (SNSF) under Grant 200021-215090.
Deferred Proofs
Proof of Remark 2
Proof of Remark 2: To prove the equivalence, it suffices to show that if one encoder cannot transmit at positive rate using Shannon strategies, then nor can it using general causal strategies. The statement will then follow using a time-sharing argument. Suppose, then, that S 1 = S 2 = ∅ S_1=S_2=\emptyset S 1 = S 2 = ∅ and that every symbol in S 0 S_0 S 0 has positive probability under P S 0 P_{S_0} P S 0 .
Without loss of generality, assume that it is Encoder 1 that cannot transmit reliably at any positive rate using Shannon strategies.
This is equivalent to
W ~ ( ⋅ ∣ t 1 , t 2 ) = W ~ ( ⋅ ∣ t 1 ′ , t 2 ) , ∀ t 1 , t 1 ′ ∈ X 1 S 0 , t 2 ∈ X 2 S 0 , (152) \widetilde{W}(\cdot\mid t_1,t_2)=\widetilde{W}(\cdot\mid t'_1,t_2),\quad\forall t_1,t'_1\in\mathcal{X}_1^{\mathcal{S}_0},\ t_2\in\mathcal{X}_2^{\mathcal{S}_0}, \tag*{(152)} W ( ⋅ ∣ t 1 , t 2 ) = W ( ⋅ ∣ t 1 ′ , t 2 ) , ∀ t 1 , t 1 ′ ∈ X 1 S 0 , t 2 ∈ X 2 S 0 , (152)
where W ~ \widetilde{W} W denotes the channel induced by treating the Shannon strategies as inputs
W ~ ( ⋅ ∣ t 1 , t 2 ) = ∑ s 0 W ( ⋅ ∣ t 1 ( s 0 ) , t 2 ( s 0 ) , s 0 ) P S 0 ( s 0 ) (153) \widetilde{W}(\cdot\mid t_1,t_2)=\sum_{s_0}W(\cdot\mid t_1(s_0),t_2(s_0),s_0)P_{S_0}(s_0) \tag*{(153)} W ( ⋅ ∣ t 1 , t 2 ) = s 0 ∑ W ( ⋅ ∣ t 1 ( s 0 ) , t 2 ( s 0 ) , s 0 ) P S 0 ( s 0 ) (153)
and X 1 S 0 \mathcal{X}_1^{\mathcal{S}_0} X 1 S 0 and X 2 S 0 \mathcal{X}_2^{\mathcal{S}_0} X 2 S 0 denote the sets of Shannon strategies for Encoders 1 and 2, respectively. As we next argue, (152) implies that
W ( ⋅ ∣ x 1 , x 2 , s 0 ) = W ( ⋅ ∣ x 1 ′ , x 2 , s 0 ) , ∀ x 1 , x 1 ′ ∈ X 1 , x 2 ∈ X 2 , s 0 ∈ S 0 . (154) W(\cdot\mid x_1,x_2,s_0)=W(\cdot\mid x'_1,x_2,s_0),\quad\forall x_1,x'_1\in\mathcal{X}_1,\ x_2\in\mathcal{X}_2,\ s_0\in\mathcal{S}_0. \tag*{(154)} W ( ⋅ ∣ x 1 , x 2 , s 0 ) = W ( ⋅ ∣ x 1 ′ , x 2 , s 0 ) , ∀ x 1 , x 1 ′ ∈ X 1 , x 2 ∈ X 2 , s 0 ∈ S 0 . (154)
Indeed, if (154) fails for some tuple ( x ˉ 1 , x ˉ 1 ′ , x ˉ 2 , s ˉ 0 ) (\bar{x}_1,\bar{x}'_1,\bar{x}_2,\bar{s}_0) ( x ˉ 1 , x ˉ 1 ′ , x ˉ 2 , s ˉ 0 ) , then the strategies ( t 1 , t 1 ′ , t 2 ) (t_1,t'_1,t_2) ( t 1 , t 1 ′ , t 2 ) defined as
t 1 ( s 0 ) = x ˉ 1 , for all s 0 . (155) t_1(s_0)=\bar{x}_1,\quad\text{for all }s_0. \tag*{(155)} t 1 ( s 0 ) = x ˉ 1 , for all s 0 . (155)
t 1 ′ ( s 0 ) = { x ˉ 1 ′ s 0 = s ˉ 0 x ˉ 1 s 0 ≠ s ˉ 0 . (156) t'_1(s_0)=
\begin{cases}
\bar{x}'_1 & s_0=\bar{s}_0\\
\bar{x}_1 & s_0\ne\bar{s}_0.
\end{cases} \tag*{(156)} t 1 ′ ( s 0 ) = { x ˉ 1 ′ x ˉ 1 s 0 = s ˉ 0 s 0 = s ˉ 0 . (156)
t 2 ( s 0 ) = x ˉ 2 , for all s 0 . (157) t_2(s_0)=\bar{x}_2,\quad\text{for all }s_0. \tag*{(157)} t 2 ( s 0 ) = x ˉ 2 , for all s 0 . (157)
violate (152) .
We next argue that (154) implies that no positive rate tuple is achievable with any causal strategy (be it of the Shannon kind or not).
To that end, consider any blocklength-l l l causal strategies g 1 l = { g 1 , i : S 0 X 1 → X 1 } i = 1 l g_1^l=\{g_{1,i}:\mathcal{S}_0^{\mathcal{X}_1}\to\mathcal{X}_1\}_{i=1}^l g 1 l = { g 1 , i : S 0 X 1 → X 1 } i = 1 l , g 1 ′ l = { g 1 , i ′ : S 0 X 1 → X 1 } i = 1 l g'_1{}^l=\{g'_{1,i}:\mathcal{S}_0^{\mathcal{X}_1}\to\mathcal{X}_1\}_{i=1}^l g 1 ′ l = { g 1 , i ′ : S 0 X 1 → X 1 } i = 1 l , and g 2 l = { g 2 , i : S 0 X 2 → X 2 } i = 1 l g_2^l=\{g_{2,i}:\mathcal{S}_0^{\mathcal{X}_2}\to\mathcal{X}_2\}_{i=1}^l g 2 l = { g 2 , i : S 0 X 2 → X 2 } i = 1 l . We claim that ( g 1 l , g 2 l ) (g_1^l,g_2^l) ( g 1 l , g 2 l ) and ( g 1 ′ l , g 2 l ) (g'_1{}^l,g_2^l) ( g 1 ′ l , g 2 l ) induce identical distributions on Y l \mathcal{Y}^l Y l . Indeed,
Pr { Y l = y l ∣ g 1 l , g 2 l } = ∑ s 0 l ∈ S 0 l P S 0 l ( s 0 l ) W l ( y l ∣ g 1 l ( s 0 l ) , g 2 l ( s 0 l ) , s 0 l ) (158) \Pr\{Y^l=y^l\mid g_1^l,g_2^l\}
=\sum_{s_0^l\in\mathcal{S}_0^l}P_{S_0^l}(s_0^l)W^l\bigl(y^l\mid g_1^l(s_0^l),g_2^l(s_0^l),s_0^l\bigr) \tag*{(158)} Pr { Y l = y l ∣ g 1 l , g 2 l } = s 0 l ∈ S 0 l ∑ P S 0 l ( s 0 l ) W l ( y l ∣ g 1 l ( s 0 l ) , g 2 l ( s 0 l ) , s 0 l ) (158)
= ∑ s 0 l ∈ S 0 l P S 0 l ( s 0 l ) W l ( y l ∣ g 1 ′ l ( s 0 l ) , g 2 l ( s 0 l ) , s 0 l ) (159) =\sum_{s_0^l\in\mathcal{S}_0^l}P_{S_0^l}(s_0^l)W^l\bigl(y^l\mid g'_1{}^l(s_0^l),g_2^l(s_0^l),s_0^l\bigr) \tag*{(159)} = s 0 l ∈ S 0 l ∑ P S 0 l ( s 0 l ) W l ( y l ∣ g 1 ′ l ( s 0 l ) , g 2 l ( s 0 l ) , s 0 l ) (159)
= Pr { Y l = y l ∣ g 1 ′ l , g 2 l } , (160) =\Pr\{Y^l=y^l\mid g'_1{}^l,g_2^l\}, \tag*{(160)} = Pr { Y l = y l ∣ g 1 ′ l , g 2 l } , (160)
where (159) follows by applying (154) to the l l l -fold product channel. We can now conclude that R 1 R_1 R 1 must be zero also for causal strategies.
The same proof extends to general bipartite networks in the sense of [8 ] , as well as to non IID state sequences.
To prove the second statement of the remark, it suffices to provide an example. Let X 1 = X 2 = S 0 = S 2 = { 0 , 1 } \mathcal{X}_1=\mathcal{X}_2=\mathcal{S}_0=\mathcal{S}_2=\{0,1\} X 1 = X 2 = S 0 = S 2 = { 0 , 1 } , let S 1 = ∅ \mathcal{S}_1=\varnothing S 1 = ∅ , and let Y = { 0 , 1 } × { 0 , 1 } \mathcal{Y}=\{0,1\}\times\{0,1\} Y = { 0 , 1 } × { 0 , 1 } . The random variables S 0 S_0 S 0 and S 2 S_2 S 2 are independent Ber ( 0.5 ) \operatorname{Ber}(0.5) Ber ( 0.5 ) random bits, and
Y = { ( X 1 ⊕ S 2 , S 0 ) , S 0 = 1 , ( X 2 , S 0 ) , S 0 = 0. (161) Y=\begin{cases}
(X_1\oplus S_2,S_0), & S_0=1,\\
(X_2,S_0), & S_0=0.
\end{cases} \tag*{(161)} Y = { ( X 1 ⊕ S 2 , S 0 ) , ( X 2 , S 0 ) , S 0 = 1 , S 0 = 0. (161)
To see that no R 1 > 0 R_1>0 R 1 > 0 is achievable using Shannon strategies, consider any strategies t 1 : S 0 → X 1 t_1:\mathcal{S}_0\to\mathcal{X}_1 t 1 : S 0 → X 1 and t 2 : S 0 × S 2 → X 2 t_2:\mathcal{S}_0\times\mathcal{S}_2\to\mathcal{X}_2 t 2 : S 0 × S 2 → X 2 (where we have dropped the dependence of t 1 t_1 t 1 on S 1 \mathcal{S}_1 S 1 because the latter is deterministic). When S 0 = 1 S_0=1 S 0 = 1 , the output t 1 ( 1 ) ⊕ S 2 t_1(1)\oplus S_2 t 1 ( 1 ) ⊕ S 2 is uniform irrespective of t 1 t_1 t 1 . When S 0 = 0 S_0=0 S 0 = 0 , the output is ( t 2 ( 0 , S 2 ) , 0 ) (t_2(0,S_2),0) ( t 2 ( 0 , S 2 ) , 0 ) and hence, also in this case, does not depend on t 1 t_1 t 1 . Consequently, the induced Shannon-strategy channel satisfies
P Y ∣ T 1 T 2 ( ⋅ ∣ t 1 , t 2 ) = P Y ∣ T 1 T 2 ( ⋅ ∣ t 1 ′ , t 2 ) (162) P_{Y|T_1T_2}(\cdot\mid t_1,t_2)=P_{Y|T_1T_2}(\cdot\mid t'_1,t_2) \tag*{(162)} P Y ∣ T 1 T 2 ( ⋅ ∣ t 1 , t 2 ) = P Y ∣ T 1 T 2 ( ⋅ ∣ t 1 ′ , t 2 ) (162)
for every t 1 , t 1 ′ t_1,t'_1 t 1 , t 1 ′ , and therefore every Shannon-strategy achievable rate pair has R 1 = 0 R_1=0 R 1 = 0 .
We next provide a causal coding scheme (that is not based on Shannon strategies) that allows us to communicate reliably at positive rates, in fact, at rates ( 1 / 4 , 1 / 4 ) (1/4,1/4) ( 1/4 , 1/4 ) . Our scheme is based on the observation that when S 0 = 1 S_0=1 S 0 = 1 the reason the receiver cannot recover Encoder 1’s input symbol is that the state S 2 S_2 S 2 masks it. Had S 2 S_2 S 2 been conveyed to the receiver, the latter could have subtracted it and recovered Encoder 1’s symbol. In our scheme, Encoder 2 uses some of its throughput to convey S 2 S_2 S 2 to the receiver to facilitate this.
For a fixed 0 < δ < 1 / 4 0<\delta<1/4 0 < δ < 1/4 , our scheme divides each sufficiently long blocklength-n n n into two equal-length phases. During the first interval, Encoder 1 sends fresh information at the first ⌊ n ( 1 / 4 − δ ) ⌋ \lfloor n(1/4-\delta)\rfloor ⌊ n ( 1/4 − δ )⌋ time instances at which S 0 = 1 S_0=1 S 0 = 1 (with a block error if there are fewer than required such time instances). Note that, since S 0 S_0 S 0 is part of the channel output, these time instances are known to the receiver. Moreover, since S 0 S_0 S 0 is the common state, Encoder 2 is also cognizant of these time instances. It can therefore record the values of S 2 S_2 S 2 at these times. (Encoder 2 will convey these values to the receiver in the second phase.)
Also in the first phase, Encoder 2 sends its own fresh information in the first ⌊ n ( 1 / 4 − δ ) ⌋ \lfloor n(1/4-\delta)\rfloor ⌊ n ( 1/4 − δ )⌋ positions at which S 0 = 0 S_0=0 S 0 = 0 .
In the second phase Encoder 2 uses the first ⌊ n ( 1 / 4 − δ ) ⌋ \lfloor n(1/4-\delta)\rfloor ⌊ n ( 1/4 − δ )⌋ time instances at which S 0 = 0 S_0=0 S 0 = 0 to transmit the values of S 2 S_2 S 2 that it recorded in the first phase. All unused inputs are fixed dummy symbols. The decoder observes S 0 S_0 S 0 as the second component of Y Y Y , decodes Encoder 2’s bits directly, and uses the forwarded S 2 S_2 S 2 values to remove the masks from Encoder 1’s stored outputs. By the law of large numbers, all three required collections of positions have the prescribed size with probability tending to one. Hence ( 1 / 4 − δ , 1 / 4 − δ ) (1/4-\delta,1/4-\delta) ( 1/4 − δ , 1/4 − δ ) is achievable for every δ > 0 \delta> 0 δ > 0 , and closure gives ( R 1 , R 2 ) = ( 1 / 4 , 1 / 4 ) (R_1,R_2)=(1/4,1/4) ( R 1 , R 2 ) = ( 1/4 , 1/4 ) .
Proof of Remark 3
Proof: We apply Carathéodory’s theorem in the form stated in [18 Theorem 1.31] . Fix q ∈ Q q \in\mathcal{Q} q ∈ Q and an arbitrary y ⋆ ∈ Y y_\star\in\mathcal{Y} y ⋆ ∈ Y . For each v v v , consider the vector consisting of
( P Y ∣ V Q ( y ∣ v , q ) : y ∈ Y ∖ { y ⋆ } ) , H ( Y ∣ X 1 , X 2 , S 0 , S 1 , S 2 , V = v , Q = q ) , I ( X 1 , S 1 ; Y ∣ X 2 , S 0 , S 2 , V = v , Q = q ) , I ( X 2 , S 2 ; Y ∣ X 1 , S 0 , S 1 , V = v , Q = q ) , I ( X 1 , X 2 , S 1 , S 2 ; Y ∣ S 0 , V = v , Q = q ) . (163) \begin{aligned}
\bigl(&P_{Y|VQ}(y\mid v,q):y\in\mathcal{Y}\setminus\{y_\star\}\bigr),\\
&H(Y\mid X_1,X_2,S_0,S_1,S_2,V=v,Q=q),\\
&I(X_1,S_1;Y\mid X_2,S_0,S_2,V=v,Q=q),\\
&I(X_2,S_2;Y\mid X_1,S_0,S_1,V=v,Q=q),\\
&I(X_1,X_2,S_1,S_2;Y\mid S_0,V=v,Q=q). \tag*{(163)}
\end{aligned} ( P Y ∣ V Q ( y ∣ v , q ) : y ∈ Y ∖ { y ⋆ } ) , H ( Y ∣ X 1 , X 2 , S 0 , S 1 , S 2 , V = v , Q = q ) , I ( X 1 , S 1 ; Y ∣ X 2 , S 0 , S 2 , V = v , Q = q ) , I ( X 2 , S 2 ; Y ∣ X 1 , S 0 , S 1 , V = v , Q = q ) , I ( X 1 , X 2 , S 1 , S 2 ; Y ∣ S 0 , V = v , Q = q ) . (163)
These are ∣ Y ∣ + 3 |\mathcal{Y}|+3 ∣ Y ∣ + 3 functions of v v v . Their average under P V ∣ Q ( ⋅ ∣ q ) P_{V|Q}(\cdot\mid q) P V ∣ Q ( ⋅ ∣ q ) can therefore be preserved using at most ∣ Y ∣ + 4 |\mathcal{Y}|+4 ∣ Y ∣ + 4 values of v v v .
The last three entries of (163) preserve the first three mutual informations in (12) . The first ∣ Y ∣ − 1 |\mathcal{Y}|-1 ∣ Y ∣ − 1 entries preserve P Y ∣ Q ( ⋅ ∣ q ) P_{Y|Q}(\cdot\mid q) P Y ∣ Q ( ⋅ ∣ q ) and hence H ( Y ∣ Q = q ) H(Y\mid Q=q) H ( Y ∣ Q = q ) , while the remaining entropy entry preserves
H ( Y ∣ X 1 , X 2 , S 0 , S 1 , S 2 , Q = q ) = ∑ v P V ∣ Q ( v ∣ q ) ⋅ H ( Y ∣ X 1 , X 2 , S 0 , S 1 , S 2 , V = v , Q = q ) . (164) \begin{aligned}
H(Y\mid X_1,X_2,S_0,S_1,S_2,Q=q)
={}&\sum_v P_{V|Q}(v\mid q)\\
&{}\cdot H(Y\mid X_1,X_2,S_0,S_1,S_2,V=v,Q=q). \tag*{(164)}
\end{aligned} H ( Y ∣ X 1 , X 2 , S 0 , S 1 , S 2 , Q = q ) = v ∑ P V ∣ Q ( v ∣ q ) ⋅ H ( Y ∣ X 1 , X 2 , S 0 , S 1 , S 2 , V = v , Q = q ) . (164)
It follows from
I ( X 1 , X 2 , S 0 , S 1 , S 2 ; Y ∣ Q = q ) = H ( Y ∣ Q = q ) − H ( Y ∣ X 1 , X 2 , S 0 , S 1 , S 2 , Q = q ) (165) \begin{aligned}
I(X_1,X_2,S_0,S_1,S_2;Y\mid Q=q)
={}&H(Y\mid Q=q)\\
&{}-H(Y\mid X_1,X_2,S_0,S_1,S_2,Q=q) \tag*{(165)}
\end{aligned} I ( X 1 , X 2 , S 0 , S 1 , S 2 ; Y ∣ Q = q ) = H ( Y ∣ Q = q ) − H ( Y ∣ X 1 , X 2 , S 0 , S 1 , S 2 , Q = q ) (165)
that the fourth mutual information in (12) is preserved as well. The retained support points continue to define input kernels of the required product form in (11) .
After this reduction, associate with each q q q the vector in R 4 \mathbb{R}^4 R 4 whose entries are the four mutual informations on the right-hand side of (12) , before subtracting the state entropies. Their averages under P Q P_Q P Q are precisely the four mutual informations in (12) . A second application of Carathéodory’s theorem preserves this average using at most five values of q q q .